Chapter 4: Reduction patterns
Introduces reductions as GPU collective operations that turn distributed values into a shared statistic through coordinated communication.
After this chapter you will be able to
- Shared statistics require cooperation. Explain why computing a statistic such as a softmax denominator requires GPU threads to cooperate when the input row is distributed among them.
- Safe hierarchical reduction trees. Describe why GPU reductions use a parallel tree to combine partial results, and how communication differs within a warp, within a block, and across program instances.
- Reduction outputs and dependencies. Explain how a reduction combines many values into fewer outputs and why, unlike an elementwise kernel, it requires partial results to be combined.
- Tree reduction critical path. Trace the pairwise stages of an eight-value tree reduction and explain why its critical path is shorter than a serial accumulation.
- GPU reduction communication hierarchy. Describe how partial results move between lanes within a warp, warps within a block, and different blocks, including the synchronization and cost implications taught here.
- Floating-point addition order. Explain why regrouping a floating-point sum can change its result, even though real-number addition is associative.
- Parallel reduction variability. Describe how a parallel reduction's grouping affects its result and why that matters for comparisons and downstream computations.
- Higher-precision accumulation. Explain how accumulating low-precision inputs in a higher-precision format reduces rounding error in a reduction.
- Stable softmax reformulation. Describe how subtracting a per-row maximum puts softmax inputs in a safer range before exponentiation.
- Program-local reduction scope. Explain that tl.sum, tl.max, and related primitives reduce a tl.tensor within one program instance, not values held by other instances. Describe why a grid-wide result needs coordination beyond a single tile-local reduction.
- Row-wise blocked accumulation. Trace how one program instance computes a full-row sum and maximum by iterating through column blocks, updating accumulators, and finally applying tl.sum and tl.max. Explain why masked lanes use zero for sum and negative infinity for max.
- Multi-pass global reduction. Trace a grid-wide sum in which each program instance writes a tile’s partial result to global memory and another kernel reduces those partials. Explain when the same approach needs additional passes.
- Atomic updates and contention. Explain how an atomic read-modify-write prevents lost updates when program instances add partials to one address. Contrast its one-pass convenience with contention and floating-point reproducibility costs.
- Atomic writes versus stores. Distinguish when multiple program instances need an atomic update from when each instance can use tl.store. Explain why a histogram bin needs atomic addition but a uniquely owned output region does not.
- Contention and local reduction. Explain why atomics targeting the same output serialize at L2 and how reducing within each program instance before an atomic update limits that cost.
- Reduction synchronization boundaries. Explain what synchronization Triton supplies for a reduction within one program instance and what coordination the programmer must provide across instances.
- RMSNorm reduce-then-map pattern. Explain how RMSNorm computes an inverse RMS from a vector’s mean of squares and uses it, with an optional learned per-element scale, to normalize the vector. Distinguish it from LayerNorm’s mean subtraction.
- Two-pass storage trade-off. Justify why a large-row RMSNorm kernel often reads its input twice rather than holding the whole row while it calculates the statistic.
- Batched row-wise mapping. Describe how the batched kernel assigns work to rows and applies the shared learned scale.
- Softmax Probability Normalization. Explain that softmax turns logits into a probability distribution whose outputs are non-negative and sum to one.
- Exponential Overflow Challenge. Explain why exponentiation makes a straightforward softmax computation numerically vulnerable and identify the max reduction as the additional reduction used in practice to prevent overflow.
- Vector Wide Sum Dependency. Describe why softmax normalization requires a reduction across the vector and why that creates a parallel dependency on the GPU.
- Maximum shift for stable softmax. Explain why subtracting the vector maximum before exponentiating preserves softmax probabilities while preventing exponential overflow, and describe what can still happen to very small contributions.
- Global memory traffic costs. Explain why the unfused baseline is memory bound despite softmax's modest arithmetic per element. Identify the repeated global-memory passes, materialized exponentials, and reduction-tree launches that create the cost.
- Fused reduction locality. Explain why a fused one-dimensional softmax needs one program instance to cover the entire vector. Describe the resulting read–reduce–shift–exponentiate–reduce–normalize–write sequence and its on-chip resource tradeoff.
- Single-program softmax fusion. Explain why a 1D softmax can use a fused kernel when its entire axis fits in one program instance, and where the reductions and intermediate values live.
What it builds on
- The Single Program, Multiple Data model (chapter 2) · GPU programs process separate portions of data.
- Shared memory enables cooperation (chapter 3) · Shared memory enables cooperation within a block.
- Embarrassingly parallel tasks: the baseline GPU pattern (chapter 3) · The independence of embarrassingly parallel elementwise tasks.
- Thinking in blocks, not threads (chapter 2) · The block-based model in which a program instance works on a tile.
- Handling edges with a mask (chapter 2) · Masking loads at data boundaries.
- Registers hold what matters right now (chapter 3) · The limited capacity of registers.
- The launch grid (chapter 2) · A launch grid assigning work to program instances.
- Arithmetic intensity and the memory wall (chapter 3) · The relationship between arithmetic work and memory traffic.
Section by section
Introduction
Introduces reductions as GPU collective operations that turn distributed values into a shared statistic through coordinated communication.
- Shared statistics require cooperation: Explain why computing a statistic such as a softmax denominator requires GPU threads to cooperate when the input row is distributed among them.
Why it matters: This explains why reductions need a different GPU pattern from independent per-element calculations. - Safe hierarchical reduction trees: Describe why GPU reductions use a parallel tree to combine partial results, and how communication differs within a warp, within a block, and across program instances.
Why it matters: The communication pattern determines how distributed partial results can become one correct result.
Key terms: reduction, collective operation, global statistics, parallel tree, partial results, warp, shared memory, global memory
4.1 The mechanics of reduction
This section explains why reductions require combining partial results, how a tree shortens that work, and how communication costs depend on GPU hardware hierarchy.
- Reduction outputs and dependencies: Explain how a reduction combines many values into fewer outputs and why, unlike an elementwise kernel, it requires partial results to be combined.
Why it matters: This distinction explains why reductions need a different parallel pattern from elementwise kernels. - Tree reduction critical path: Trace the pairwise stages of an eight-value tree reduction and explain why its critical path is shorter than a serial accumulation.
Why it matters: The tree shows how parallel work reduces the sequential bottleneck without eliminating it. - GPU reduction communication hierarchy: Describe how partial results move between lanes within a warp, warps within a block, and different blocks, including the synchronization and cost implications taught here.
Why it matters: Where partial results must meet determines the communication overhead of a GPU reduction.
Key terms: reduction, combining operation, partial results, elementwise kernel, tree reduction, partial sums, critical path, lanes, warp, block
4.1.1 Floating-point associativity and numerical concerns
This section explains why floating-point reduction order affects results and introduces ways to reduce numerical error.
- Floating-point addition order: Explain why regrouping a floating-point sum can change its result, even though real-number addition is associative.
Why it matters: This explains why mathematically equivalent sums need not produce identical floating-point answers. - Parallel reduction variability: Describe how a parallel reduction's grouping affects its result and why that matters for comparisons and downstream computations.
Why it matters: A different reduction result may be correct yet still affect a bitwise test or a sensitive later calculation. - Higher-precision accumulation: Explain how accumulating low-precision inputs in a higher-precision format reduces rounding error in a reduction.
Why it matters: The accumulation format is a practical choice for making large reductions more stable. - Stable softmax reformulation: Describe how subtracting a per-row maximum puts softmax inputs in a safer range before exponentiation.
Why it matters: This is the section's concrete example of improving stability by changing the form of a computation. - Log-space product tradeoff: Explain when a log-space transformation can help a product reduction and what limits its use.
Why it matters: It shows that improving reduction stability can introduce both a computational cost and an input constraint.
Key terms: associative, finite precision, rounding errors, tree reduction, tile shape, warps, bitwise identical, atomic floating-point updates, higher-precision accumulation, fp32
4.1.2 Triton’s primitives for reduction
This section explains the scope and API of Triton’s tile-local reductions, then shows how to build row-wise and grid-wide reductions with accumulation, multiple passes, or atomics.
- Program-local reduction scope: Explain that tl.sum, tl.max, and related primitives reduce a tl.tensor within one program instance, not values held by other instances. Describe why a grid-wide result needs coordination beyond a single tile-local reduction.
Why it matters: This boundary determines whether a reduction primitive is sufficient or a grid-wide strategy is needed. - Reduction axes and output shapes: Describe how axis selects a tile dimension to collapse and how keep_dims retains a length-one dimension for broadcasting. State the output shapes for reducing either axis of a two-dimensional tile.
Why it matters: The resulting shape determines how a row statistic can be applied back to its elements. - Row-wise blocked accumulation: Trace how one program instance computes a full-row sum and maximum by iterating through column blocks, updating accumulators, and finally applying tl.sum and tl.max. Explain why masked lanes use zero for sum and negative infinity for max.
Why it matters: It shows how to obtain a row statistic even when the row is processed in smaller blocks. - Structured custom reduction state: Explain when tl.reduce is useful and describe its combine function as merging two partial states. Describe why a reduction can carry a tuple of values that must be updated together.
Why it matters: Some statistics require several related running values rather than one sum or maximum. - Multi-pass global reduction: Trace a grid-wide sum in which each program instance writes a tile’s partial result to global memory and another kernel reduces those partials. Explain when the same approach needs additional passes.
Why it matters: Multiple passes combine independent blocks without requiring a barrier inside one kernel. - Atomic updates and contention: Explain how an atomic read-modify-write prevents lost updates when program instances add partials to one address. Contrast its one-pass convenience with contention and floating-point reproducibility costs.
Why it matters: Atomics can produce a correct compact reduction, but their shared-address costs make them a deliberate alternative to multiple passes.
Key terms: tl.tensor, program instance, tile, axis, tl.sum, keep_dims, broadcast, row-wise, column blocks, accumulators
4.1.3 Atomic operations
This section explains when Triton kernels need atomic writes, why contention makes them costly, and where Triton’s automatic reduction synchronization stops.
- Atomic writes versus stores: Distinguish when multiple program instances need an atomic update from when each instance can use tl.store. Explain why a histogram bin needs atomic addition but a uniquely owned output region does not.
Why it matters: Choosing the right write operation determines both correctness and unnecessary coordination cost. - Contention and local reduction: Explain why atomics targeting the same output serialize at L2 and how reducing within each program instance before an atomic update limits that cost.
Why it matters: Reducing locally can turn a heavily contended kernel into a much faster one without giving up correct accumulation. - Atomic accumulation contract: Describe what tl.atomic_add does and why its output buffer must be initialized before accumulation. State how its mask and relaxed memory semantics affect a simple accumulation.
Why it matters: An atomic operation cannot produce a valid sum if it starts from uninitialized output. - Native atomics and CAS: Explain how unsupported atomic operations can be implemented with compare-and-swap retries and why this can be slower under contention.
Why it matters: The same-looking atomic call can have different costs across data types and GPUs. - Floating-point atomic reproducibility: Explain why atomic floating-point accumulation can yield different last bits across runs and how a fixed-order two-pass reduction differs.
Why it matters: Small run-to-run differences may be acceptable in training but matter when testing requires bitwise reproducibility. - Reduction synchronization boundaries: Explain what synchronization Triton supplies for a reduction within one program instance and what coordination the programmer must provide across instances.
Why it matters: The within-program guarantee makes reductions straightforward to use, but assuming it extends across programs would break an algorithm that needs global coordination.
Key terms: atomic operations, tl.atomic_add, tl.store, data-dependent write destinations, L2 cache, contention, tl.sum, reduce first, then write atomically, pointer, val
4.1.4 RMS normalization in Triton
This section uses RMSNorm to show how Triton reduces a row to a scalar statistic, applies it to each element, and extends the kernel from one vector to a batch of rows.
- RMSNorm reduce-then-map pattern: Explain how RMSNorm computes an inverse RMS from a vector’s mean of squares and uses it, with an optional learned per-element scale, to normalize the vector. Distinguish it from LayerNorm’s mean subtraction.
Why it matters: The same reduce-then-map shape appears in other deep-learning operations. - Two-pass storage trade-off: Justify why a large-row RMSNorm kernel often reads its input twice rather than holding the whole row while it calculates the statistic.
Why it matters: It explains why an extra memory read can be a sensible GPU design choice. - Single-vector kernel boundaries: Describe how the single-vector Triton kernel reduces squared inputs, computes the inverse RMS, and safely handles lanes beyond the vector length.
Why it matters: Masking lets the same block-sized kernel handle vectors whose lengths do not fill the block. - Batched row-wise mapping: Describe how the batched kernel assigns work to rows and applies the shared learned scale.
Why it matters: It shows how the single-vector reduction becomes independent work across a batch. - Batched compile-time choices: Explain why the batched kernel makes N compile-time known while leaving eps as a runtime value, and state the benefit given for tl.rsqrt.
Why it matters: These choices distinguish values needed for compilation from values that can vary without recompiling.
Key terms: RMSNorm, inverse RMS, learned scale, reduce-then-map, ε, two passes, registers, shared memory, global memory, occupancy
4.2 Numerical stability and chained reductions (Softmax)
Introduces softmax as a probability normalization whose GPU implementation requires a vector-wide sum and attention to exponential overflow.
- Softmax Probability Normalization: Explain that softmax turns logits into a probability distribution whose outputs are non-negative and sum to one.
Why it matters: These output properties explain what the softmax computation must preserve. - Exponential Overflow Challenge: Explain why exponentiation makes a straightforward softmax computation numerically vulnerable and identify the max reduction as the additional reduction used in practice to prevent overflow.
Why it matters: The overflow risk explains why softmax needs more than a straightforward normalization. - Vector Wide Sum Dependency: Describe why softmax normalization requires a reduction across the vector and why that creates a parallel dependency on the GPU.
Why it matters: The shared denominator is what makes softmax a reduction problem rather than a purely elementwise operation.
Key terms: softmax, logits, probability distribution, numerical stability, exponential, overflow, max reduction, denominator, sum, reduction
4.2.1 The "exploding exponential" problem
Explains why naive softmax exponentials can overflow and how subtracting the input maximum keeps the computation in range without changing the probabilities.
- Exponential overflow across precisions: Explain why directly exponentiating softmax inputs can overflow, and why this happens at smaller inputs in float16 than in float32.
Why it matters: Recognizing the overflow risk explains why softmax needs a numerically stable form. - Maximum shift for stable softmax: Explain why subtracting the vector maximum before exponentiating preserves softmax probabilities while preventing exponential overflow, and describe what can still happen to very small contributions.
Why it matters: This shift makes large-input softmax calculations safe without changing their mathematical result.
Key terms: float32, float16, overflow, dynamic range, softmax, invariance, maximum value, underflow
4.2.2 Case study: softmax in Triton
This section uses an unfused softmax baseline to show the cost of global reductions and intermediate memory traffic, then explains the locality needed to fuse the pipeline.
- Unfused softmax reduction pipeline: Trace the unfused one-dimensional softmax pipeline from a global maximum through exponentials, a global sum, and normalization. Describe how tile-level partial results are repeatedly reduced when one program instance cannot cover the vector.
Why it matters: The unfused pipeline makes clear which reductions and intermediate values fusion must account for. - Global memory traffic costs: Explain why the unfused baseline is memory bound despite softmax's modest arithmetic per element. Identify the repeated global-memory passes, materialized exponentials, and reduction-tree launches that create the cost.
Why it matters: It explains why a mathematically simple softmax can be expensive and motivates fusion. - Fused reduction locality: Explain why a fused one-dimensional softmax needs one program instance to cover the entire vector. Describe the resulting read–reduce–shift–exponentiate–reduce–normalize–write sequence and its on-chip resource tradeoff.
Why it matters: It states both the condition that makes this fusion possible and the resource cost of avoiding intermediate memory traffic.
Key terms: unfused baseline, hierarchical reduction, partial value, reduction tree, global memory, intermediate tensor, memory bound, kernel launches, HBM, tl.max
4.2.3 Fused softmax kernel
This section explains when softmax reductions can be fused into one Triton program, how the kernel handles masked lanes, and why fusion improves performance.
- Single-program softmax fusion: Explain why a 1D softmax can use a fused kernel when its entire axis fits in one program instance, and where the reductions and intermediate values live.
Why it matters: The one-program constraint determines whether this simple fused softmax can compute full reductions without intermediate tensors. - Masked lane reduction behavior: Trace why loading masked lanes with other=-inf keeps both the maximum and sum reductions correct when N is not a power of two.
Why it matters: This explains how a tile larger than the vector can still produce the right softmax denominator. - Warp count tuning tradeoff: Explain what num_warps changes within a fused softmax program and why both too few and too many warps can hurt performance.
Why it matters: Warp count is a performance choice even when the fused algorithm and tile size stay the same. - Fusion speedup and limits: Describe the measured advantage of fused softmax, why the source of that advantage shifts with vector length, and the size limit of this single-tile design.
Why it matters: The benchmark shows both why fusion pays off and when the demonstrated kernel no longer applies.
Key terms: softmax axis, BLOCK_SIZE, program instance, tl.max, tl.sum, fusion, masking, other=-inf, tl.exp, max reduction
4.3 Summary
Where this is used later
- The tl.dot block contraction (chapter 5) · Numerical concerns associated with floating-point computation.
Concepts explained in this chapter
- atomicityAn atomic operation performs a memory read-modify-write update as one indivisible transaction that cannot be interleaved at the target address.
- tl.atomic_addtl.atomic_add is a Triton API operation that atomically adds a value to a global-memory location and returns its previous value.
- reduction operationA reduction combines multiple values into fewer values using an associative operation such as a sum, maximum, or minimum.
- reduction treeA hierarchical reduction that combines values through a tree of partial results.
- tl.sumtl.sum is a Triton operation that reduces elements along a specified dimension and can select an accumulator data type.
- CAS loopA CAS loop repeatedly reads a value, computes an update, attempts compare-and-swap, and retries when another thread changes the value.
- atomic accumulationAtomic accumulation is the concurrent combination of contributions into shared output locations using atomic updates.
- block-level reductionA block-level reduction combines values within one GPU block or Triton program instance using on-chip resources and synchronization.
- histogram binningThe assignment and counting of data values into discrete intervals called bins.
- implicit barrierAn implicit barrier is compiler-generated synchronization that ensures producing threads complete a stage before consuming threads use its results.
- memory contentionCompetition among concurrent operations for access to the same memory location or cache line.
- memory orderingMemory ordering semantics specify which memory operations may be reordered around an atomic operation and when their effects become visible.
- memory_order_relaxedRelaxed memory ordering guarantees atomicity of the update without imposing ordering constraints on other memory accesses.
- scatter operationA scatter operation updates output locations selected by per-element indices or data-dependent addresses.
- split-k matrix multiplicationSplit-K matrix multiplication partitions the contracting matrix dimension across program instances that produce partial results for shared output tiles.
- tl.atomic_castl.atomic_cas is a Triton compare-and-swap operation that writes a new value only when the stored value equals an expected comparison value.
- tl.maxtl.max is a Triton operation that selects the maximum value along one or more tensor dimensions, optionally returning its index.
- softmaxSoftmax normalization exponentiates scores and divides by their sum to produce nonnegative values that sum to one.
- global reductionA global reduction combines values distributed across all program instances in a kernel launch grid into fewer global results.
- tl.mintl.min is a Triton operation that selects the minimum value along one or more tensor dimensions, optionally returning its index.
- tl.reducetl.reduce is a Triton operation that reduces tensor values with a programmer-provided binary combine function.
- two-pass reductionA two-pass reduction first computes per-program-instance partial results and then reduces those partials in a subsequent kernel pass.
- communication hierarchyA communication hierarchy is an ordered set of communication mechanisms whose scope and storage locations vary across threads, warps, blocks, and the grid.
- kernel fusionKernel fusion is an optimization technique that combines multiple operations into fewer GPU kernel launches to reduce intermediate data movement and launch overhead.
- materializationMaterialization is the process of writing an intermediate computational result to memory so that a later operation can read it.
- reduce-then-mapA computation pattern that first reduces values to a statistic and then uses that statistic to transform each element.
- rmsnormRMSNorm normalizes activations using their root-mean-square magnitude without subtracting the mean.
- accumulation precisionHigher-precision accumulation performs an aggregate computation in a numerical format with greater precision than the input format.
- associativityAssociativity is the algebraic property that regrouping operands does not change an operation's result.
- floating-point additionFloating-point addition is addition performed on finite-precision floating-point representations with rounding of the computed result.
- stable reformulationA stable reformulation rewrites a numerical computation to reduce amplification of overflow, underflow, or cancellation errors.
- numerical overflowA numerical condition in which a computed value exceeds the range representable by its number format.
- precisionThe fineness with which a numerical representation distinguishes nearby values.
- fused softmax kernelA fused softmax kernel computes the softmax reductions and elementwise operations in one GPU kernel while retaining intermediate values on chip.
- hardware registerA register is a small, private storage location associated with a GPU thread for operands, intermediate results, and other active values.
- inverse RMSThe inverse RMS is the reciprocal of a vector's root mean square and serves as its normalization factor.
- learned scale vectorA learned scale vector is a trainable vector of per-element multiplicative factors applied to normalized activations.
- root mean squareThe root mean square is the square root of the arithmetic mean of squared values.
- two-pass computationTwo-pass computation performs one pass to calculate a statistic and a separate pass to use that statistic for the final transformation.
- tl.argmaxtl.argmax is a Triton operation that returns the index of a maximum value along a tensor dimension.
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.
