liveBook · Manning

Reduction tree

As explained in GPU Programming with Triton

A hierarchical reduction that combines values through a tree of partial results.

A reduction tree combines many values into a single result through successive layers of partial results. For example, a sum of eight values can combine pairs in parallel, then combine the four partial sums, and finally combine the remaining two. The tree takes log₂(N) stages for N values, rather than N sequential accumulation steps. section 4.3 section 4.0

On a GPU, the tree is also a communication plan. Lanes within a warp exchange values through register shuffles; warps within a block use shared memory and a barrier; separate program instances coordinate through global memory, usually across kernel launches. These boundaries ensure that partial results are available before they are combined. section 4.3 section 4.0

In Triton, the reduction scope determines the implementation:

  • Use tl.sum, tl.max, or another reduction primitive to combine values within one program instance’s tile. The axis selects a tile dimension, not the entire tensor. section 4.3
  • For a row processed in column blocks, maintain per-lane accumulators across blocks, then reduce them within the tile. Masked lanes need the operation’s neutral value: zero for a sum and negative infinity for a maximum. section 4.1.2
  • For a grid-wide reduction, write one partial result per program instance to global memory, then reduce the partials in another launch. Alternatively, tl.atomic_add combines partials at a shared address, with contention and potentially variable accumulation order. section 4.3 section 4.1.1
Figure 4.3 Two-pass reduction dataflow. The first kernel reduces tiles independently, writing one partial sum per program instance to global memory. The second kernel reduces those partials to a single output value
CH04 F03 Fartale

The two-pass dataflow shows where tile-local partial sums cross the program-instance boundary. section 4.1.2

Unfused softmax

An unfused softmax computes a maximum and a sum using separate reduction trees. Each kernel reduces a tile to a partial value; host-side loops repeatedly launch kernels over smaller arrays of partials. Intermediate results travel through global memory, so repeated memory traffic and launches make fusion important for performance. section 4.2.2

Floating-point addition is not associative: changing the tree, tile shape, or number of warps can change rounding, so results may be numerically close without being bitwise identical. Accumulating fp16 or bf16 inputs in fp32 reduces rounding error. For softmax, subtracting the row maximum before exponentiation is another stability measure. section 4.1.1 section 4.3

print((0.1 + 1e20) - 1e20)  # 0.0
print(0.1 + (1e20 - 1e20))  # 0.1

This small calculation shows how regrouping the same additions changes the result. section 4.1.1

How GPU Programming with Triton covers it

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.
How it connects
Connects reduction trees to synchronization, floating-point associativity, atomic operations, kernel fusion, and softmax.

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 GPU Programming with Triton. The section links point to the parts of the book it draws on.