5 The Reduction pattern
This chapter covers
- Combining many values into a single result with the reduction pattern
- Why naive parallel reduction fails: race conditions
- Tree-based reduction
- Fast communication within a block using shared memory
- Combining per-block results safely in global memory with atomic operations
Back in the grading room from chapter 1, the 1,000 exams are finally graded, and now you need the class average. Step one: add up all 1,000 scores. You could do it yourself, one score at a time, punching all 1,000 into a calculator. Or you could find a clever solution.
So you split the pile into 50 stacks and hand one to each group of helpers. Each group totals its stack and calls out the subtotal, and you add up those 50 numbers in seconds. This is the two-step plan chapter 3 hinted at: sum each chunk separately, then combine the partial sums. But the groups can be clever too. Instead of adding the scores in a stack one by one, they can pair up numbers and combine the pairs in rounds: 20 scores become 10 subtotals, then 5, then 3, then 2, then 1. If several hands add the pairs at the same moment, each of those five steps takes one round: five rounds instead of nineteen additions in a row. That pairing trick is the idea behind parallel reduction.
In chapter 4, you learned the Map pattern: applying the same operation independently to every element. But many computations need to combine values. For those, you need the Reduction pattern.