liveBook · Manning

Reduction tree

As explained in Grokking GPU Programming

A reduction tree is a tree structure in which values are combined through successive levels to produce an aggregate.

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

How Grokking GPU Programming covers it

How deep it goes
Traces stride updates, active threads, shared-memory synchronization, and a power-of-two constraint.
Examples
Uses an eight-value CUDA reduction and a Blelloch up-sweep that sums eight inputs to 25.
What you can do after
Build it from scratch as a CUDA reduction kernel using shared memory, a halving stride, and thread barriers.
How it connects
Connects reduction trees to shared memory, parallel scans, MPI_Allreduce, and OpenMP reduction clauses.

Also explained in

Compare how 3 books explain reduction tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.