liveBook · Manning

Reduction operation

As explained in GPU Programming with Triton

A reduction combines multiple values into fewer values using an associative operation such as a sum, maximum, or minimum.

A reduction combines many values into fewer values using an operation such as addition, maximum, or minimum. It often collapses one tensor dimension: summing a vector produces a scalar, while taking each matrix row’s maximum produces a vector. Reductions supply shared statistics for tasks such as normalization and softmax. section 4.1 section 4.0

Unlike an elementwise operation, a reduction requires partial results to be combined. A parallel tree shortens the dependency path: eight values can be summed in three pairwise stages rather than seven sequential additions. For N values, tree depth grows proportionally to log₂(N). section 4.1

Figure 4.1 A tree reduction combines eight values in three stages. Each stage halves the number of values, producing a critical path of log_2(N) steps rather than N sequential additions
CH04 F01 Fartale

Follow the three stages of an eight-value sum. section 4.1

Communication cost depends on where partial results reside. Lanes within a warp exchange values through register shuffles; warps within a block use shared memory and barriers. Separate blocks coordinate through global memory, typically across kernel launches. section 4.1 section 4.3

Triton provides tl.sum, tl.max, tl.min, tl.argmax, tl.argmin, and tl.reduce for custom combining operations. These operate on a tile local to one program instance: axis selects a tile dimension, not a dimension across the entire launch grid. section 4.1.2

For a global sum spanning program instances, choose an explicit coordination pattern:

  • Use two passes: reduce each tile and write its partial sum to global memory, then launch a second kernel to reduce the partials. section 4.1.2
  • Use tl.atomic_add to combine each tile’s partial into a shared output initialized to zero. This avoids a second reduction kernel but introduces contention at the shared address. section 4.1.2 section 4.3
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

Trace partial sums from independent tiles through the second reduction pass. section 4.1.2

Floating-point addition is not truly associative: rounding can make a tree sum differ from a sequential sum or from a different tile or warp configuration. Atomic updates can also vary with update order. Accumulating fp16 or bf16 inputs in fp32 and using stable formulations help limit numerical error. section 4.1.1 section 4.3

Fused softmax

When the whole vector fits in one program instance, reduce it to a maximum, subtract that maximum, exponentiate, and reduce again to obtain the denominator. Masked lanes load negative infinity: they do not affect the maximum and become zero after exponentiation, so they do not affect the sum. Keeping intermediates local avoids extra global-memory traffic and kernel launches. section 4.2.3

Listing 4.7 Fused softmax when the entire vector fits in one tile
import torch
import triton
import triton.language as tl

@triton.jit
def softmax_fused_1d_kernel(x_ptr, y_ptr, N, BLOCK_SIZE: tl.constexpr):
    offsets = tl.arange(0, BLOCK_SIZE)
    mask = offsets < N
    x = tl.load(x_ptr + offsets, mask=mask, other=-float("inf")).to(
        tl.float32)
    m = tl.max(x, axis=0)
    x = x - m
    num = tl.exp(x)
    den = tl.sum(num, axis=0)
    y = num / den
    tl.store(y_ptr + offsets, y, mask=mask)

def softmax_fused_1d(x: torch.Tensor, y: torch.Tensor, N: int):
    BLOCK_SIZE = triton.next_power_of_2(N) #1
    if BLOCK_SIZE > 1024:
        raise ValueError("This fused example assumes N <= 1024 so the full
         vector fits in one program instance.")

    num_warps = 8 if BLOCK_SIZE >= 512 else 4 #2
    softmax_fused_1d_kernel[(1,)](x, y, N, BLOCK_SIZE=BLOCK_SIZE,
    num_warps=num_warps)

Inspect the tile-local max and sum reductions in a fused softmax kernel. section 4.2.3

How GPU Programming with Triton covers it

How deep it goes
Explains reduction trees, GPU communication, numerical behavior, and Triton implementation patterns through fused kernels.
Examples
Uses an eight-value tree sum, two-pass and atomic global sums, and a fused softmax kernel.
What you can do after
Apply reductions via Triton primitives, choosing tile-local, two-pass, or atomic patterns and accounting for numerical precision.
How it connects
Connects reductions to parallel trees, synchronization, atomic operations, kernel fusion, and softmax.

Also explained in

Compare how 15 books explain reduction operation →

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.