GPU Programming

On a GPU you want to compact only the elements meeting a condition into another array (each thread outputs 0 or 1 items). Which parallel computation is commonly used to determine each thread's write position?

  1. AA matrix transpose
  2. BA prefix sum (scan, the running total from the start)
  3. CA fast Fourier transform
Show answer and explanation

Answer: B. A prefix sum (scan, the running total from the start)

Representing whether each thread outputs as 0 or 1 and computing the running total from the start (an exclusive prefix sum) gives each thread "the number of outputting threads before me", which is exactly its write address. A scan can be computed in parallel with a tree structure, like a reduction. It is the basic tool for compacting variable per-element output in parallel.

  • A. A transpose does not determine write positions.
  • B. Correct. The number of outputs before you is your write position.
  • C. Frequency transforms are unrelated.
Practice this topic Back to topic

More GPU Programming questions

  1. Which assumption must be respected when writing GPU kernels?
  2. When transposing a large matrix on a GPU (b[j][i] = a[i][j]), what is the main purpose of going through shared memory?
  3. In CUDA, what generally happens right after the CPU-side program launches a kernel?
  4. How do the design philosophies of CPUs and GPUs differ?
  5. Which characteristic best describes work that GPUs process quickly?