A reduction tree combines many values into one through successive pairwise steps. Instead of having one thread add every value in sequence, groups of threads combine partial results in parallel; fewer threads remain active after each round. section 5.26 section 5.7
In a CUDA block, threads can place values in shared memory and combine them over several rounds. A halving stride pairs each active thread with another value; a block-wide barrier makes each round’s writes visible before the next. The final total sits in sdata[0]. section 5.12
Keep these correctness details in view:
- The simple halving-stride loop requires a power-of-two block size. With six values, it can skip a partial sum and return an incorrect result. section 5.12
- Synchronize threads between rounds so they do not read shared-memory values before other threads have written them. section 5.12
- For partial blocks, padding out-of-bounds threads with the operation’s identity element preserves correctness. section 5.26
Eight values, three rounds
With eight values, four active positions combine pairs first; two combine the resulting partial sums next; and one combines the final pair. In a separate Blelloch example, the up-sweep combines [3, 1, 7, 0, 4, 1, 6, 3] into 25 in three rounds. That up-sweep builds a reduction tree; a scan then adds a down-sweep to produce prefix sums. section 5.12 section 7.2 section 7.1
Figure 5.5 Act 2 (Reduce): three rounds of pairwise addition in shared memory. Each round, active threads read two values from sdata into registers, add them, and write the result back, halving the number of active threads each time (4 → 2 → 1). By the end of Round 3, the block's total sum (36) sits in sdata[0], ready to be written back to global memory.

Follow the three pairwise-addition rounds and see how the block total reaches sdata[0]. section 5.12


