liveBook · Manning

Reduction tree

Also called hierarchical reduction, tree reduction

A reduction tree is a structure that combines values through successive stages of partial results to produce an aggregate.

How 3 Manning books explain it

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.

Read how Grokking GPU Programming explains reduction tree →

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.

Read how CUDA for LLMs explains reduction tree →

What to know first

Related concepts

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.