Reduction tree
A reduction tree is a structure that combines values through successive stages of partial results to produce an aggregate.
GPU Programming with Triton
A hierarchical reduction that combines values through a tree of partial results.
- How it is used
- Organizes GPU cooperation for many-to-one statistics used in normalization and softmax.
- How deep it goes
- Explains hardware communication stages and Triton synchronization limits, with tile-local and multi-launch reduction procedures.
- Examples
- Uses row-wise sum and maximum, a two-pass global sum, and an unfused softmax with repeated partial reductions.
- What you can do after
- Apply it via Triton to tile-local and grid-wide reductions while accounting for masking, synchronization scope, and numerical precision.
Read how GPU Programming with Triton explains reduction tree →
Grokking GPU Programming
A reduction tree is a tree structure in which values are combined through successive levels to produce an aggregate.
- How it is used
- Combines many values into one in parallel using an associative operation.
- 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.
CUDA for LLMs
A hierarchical reduction combines values in stages across progressively larger groups of parallel threads.
- How it is used
- Uses staged thread cooperation to compute softmax row statistics in CUDA kernels.
- How deep it goes
- Traces logarithmic shared-memory stages and barriers, then relates warp shuffles to reducing synchronization and latency.
- Examples
- Works through an eight-value maximum and CUDA softmax reductions of partial maxima and normalization sums.
- What you can do after
- Build it from scratch in a CUDA softmax kernel using shared-memory stages and synchronization.
What to know first
- GPU memoryGPU memory is memory available to a graphics processing unit for storing data and state used in graphics or computation.
- shared memoryShared memory is a memory region accessible to multiple processes, threads, or other concurrent execution contexts for sharing data.
- online softmaxOnline softmax is an incremental algorithm that computes softmax by updating normalization statistics as input values or blocks are processed.
- scanA scan computes a cumulative aggregate for every prefix of an ordered sequence, typically using an associative operation.
Related concepts
- block-level reductionuses · A block-level reduction combines values across threads within a GPU thread block into an aggregate result.
- strideuses · Stride is the step or spacing between successive positions in an array access or successive placements of an operation over input data.
- warp-level reductionuses · A warp-level reduction combines values held by threads in a single warp into one aggregate result using warp-synchronous operations.
- reduction operationkind of · A reduction operation combines multiple input values according to a rule to produce fewer results, often a single aggregate.
- block sizeconfigures · Block size is a parameter specifying the quantity, dimensions, or number of units grouped or processed as one block.
- __syncthreads()uses · __syncthreads() is a CUDA block-level barrier that makes threads in a thread block wait until all participating threads reach it and ensures prior memory accesses are visible within the block.
Questions about reduction tree
What is reduction tree?
A reduction tree is a structure that combines values through successive stages of partial results to produce an aggregate.
Which Manning books explain reduction tree?
GPU Programming with Triton, Grokking GPU Programming and CUDA for LLMs.
What should I know before learning reduction tree?
Manning books that teach reduction tree usually introduce GPU memory, shared memory, online softmax and scan first.
What is reduction tree a kind of?
Reduction tree is a kind of reduction operation. A reduction operation combines multiple input values according to a rule to produce fewer results, often a single aggregate.
What is reduction tree also called?
Reduction tree is also called hierarchical reduction or tree reduction.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.


