GPU Programming

How many stages does a tree-shaped reduction need to sum 1024 values?

  1. A10
  2. B512
  3. C1023
Show answer and explanation

Answer: A. 10

Each stage halves the number of values, 1024 → 512 → 256 → ... → 1, which takes 10 halvings, so the number of stages is log2 1024 = 10. The total number of additions is 512 + 256 + ... + 1 = 1023, the same as one thread summing in sequence, but with only 10 stages it finishes very quickly given enough threads.

  • A. Correct. 2^10 = 1024.
  • B. 512 is the number of threads needed in the first stage.
  • C. 1023 is the total number of additions.
Practice this topic Back to topic

More GPU Programming questions

  1. In a program using a discrete GPU, what is generally true about CPU-side and GPU-side memory?
  2. 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?
  3. Why does pinning (page-locking) CPU memory before transferring it to the GPU speed up the transfer?
  4. What is the main purpose of using multiple CUDA streams?
  5. A program that launches a very small kernel thousands of times in a row is slow. What is the most suitable improvement?