chapter five

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.

A million values, one answer

You already know reduction

Use cases for reduction

Why naive parallelism fails

The sequential approach

The shared-variable trap: many threads, one counter

Tree reduction: from concept to code

The tournament analogy

Where threads share data: shared memory

Building the kernel step by step

Act 1: Everyone writes on the whiteboard

Act 2: The tournament begins

Act 3: Report the block’s result

The barrier: __syncthreads()

The last piece: atomic operations

Putting it all together: the complete kernel

Beyond addition: max, min, and more

Reduction in NumPy and PyTorch

NumPy

PyTorch

Common mistakes

Mistake 1: Missing __syncthreads()

Mistake 2: Forgetting to initialize result

Mistake 3: Regular add instead of atomic

Mistake 4: Shared memory size mismatch

Summary