5 The Reduction pattern
This chapter covers
- The Reduction Pattern: combining many values into a single result
- Why naive parallel reduction fails: the dreaded race condition
- Tree-based reduction: log₂(n) rounds instead of n sequential steps
- Shared memory: fast communication within a block
- Atomic operations: safely combining per-block results in global memory
- When the GPU loses: why the right parallel structure matters more than porting the loop
Imagine you’re a teacher at the end of the semester, staring at a pile of 1,000 exam papers. You need the class average. Step one: add up all 1,000 scores. You could add every score yourself: one by one, hunched over a calculator until midnight. Or you could be clever about it.
You split the pile into 50 stacks and hand one to each student helper. Each helper totals their stack, hands you a sticky note with their subtotal, and you combine those 50 numbers in seconds. But how does each helper total their own stack? They could add scores one by one, or they could pair up numbers and combine them in rounds, finishing in a fraction of the time. That recursive trick is the key insight of this chapter. (In our analogy, we used 50 helpers for convenience. On the GPU, the actual implementation uses pair-wise combining at every level; you’ll see exactly how in the “Tree reduction” section below, and figure 5.1 draws it as a tournament bracket.)
You just performed a parallel reduction.