GPU Programming

When summing many values on a GPU, why use a tree-shaped reduction (repeatedly adding neighbors to halve the count)?

  1. AIt needs far fewer additions than one thread summing sequentially
  2. BMany threads add simultaneously at each stage, summing n values in log2 n stages
  3. CIt always eliminates floating-point error
Show answer and explanation

Answer: B. Many threads add simultaneously at each stage, summing n values in log2 n stages

Summing sequentially in one thread takes n - 1 steps, but with a tree, n/2 threads add neighboring pairs in the first stage, n/4 in the second and so on, finishing in log2 n stages. The total number of additions is the same, but far fewer stages make it fast in parallel. Within a block the stages proceed in shared memory, and per-block results are combined at the end.

  • A. Both need n - 1 additions.
  • B. Correct. It restructures the sum to be parallel.
  • C. Error does not vanish, though it may shrink.
Practice this topic Back to topic

More GPU Programming questions

  1. How many stages does a tree-shaped reduction need to sum 1024 values?
  2. In a program using a discrete GPU, what is generally true about CPU-side and GPU-side memory?
  3. Sending data to a GPU for light work such as adding array elements once can be slower than computing on the CPU. What is the main reason?
  4. Why does pinning (page-locking) CPU memory before transferring it to the GPU speed up the transfer?
  5. What is the main purpose of using multiple CUDA streams?