GPU Programming

Building a histogram of pixel values on a GPU can be slow if every thread does atomicAdd directly on 256 bins in global memory. What is a good improvement?

  1. ADrop atomicAdd and use plain additions on global memory
  2. BMerge all bins into one
  3. CBuild a partial histogram per block in shared memory, then add it into the global bins at the end
Show answer and explanation

Answer: C. Build a partial histogram per block in shared memory, then add it into the global bins at the end

When many threads atomicAdd to the same bin at once, the updates are serialized, and slow global memory makes the waits long. If each block keeps its own histogram in shared memory, counts there and adds it to the global bins once at the end, contention in slow memory falls to the number of blocks times the number of bins. Atomics in shared memory are much faster.

  • A. A data race would lose counts.
  • B. The histogram would become meaningless.
  • C. Correct. Contention on slow global memory drops sharply.
Practice this topic Back to topic

More GPU Programming questions

  1. When summing many values on a GPU, why use a tree-shaped reduction (repeatedly adding neighbors to halve the count)?
  2. How many stages does a tree-shaped reduction need to sum 1024 values?
  3. In a program using a discrete GPU, what is generally true about CPU-side and GPU-side memory?
  4. 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?
  5. Why does pinning (page-locking) CPU memory before transferring it to the GPU speed up the transfer?