liveBook · Manning

Two-pass reduction

As explained in GPU Programming with Triton

A two-pass reduction first computes per-program-instance partial results and then reduces those partials in a subsequent kernel pass.

A two-pass reduction splits a large reduction across GPU program instances without making them contend for one output address. Each instance reduces its tile and writes a partial sum; a second kernel reduces those partials. If they do not fit in one block, repeat the pattern in additional passes. section 4.1.2

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

Shows how independent tile reductions feed a final reduction. section 4.1.2

Listing 4.2 Two-pass global sum using partial results
import torch
import triton
import triton.language as tl

@triton.jit
def partial_sum_kernel(x_ptr, partial_ptr, n_elements,
                       BLOCK_SIZE: tl.constexpr):
    pid = tl.program_id(0)
    offsets = pid * BLOCK_SIZE + tl.arange(0, BLOCK_SIZE)
    mask = offsets < n_elements

    x = tl.load(x_ptr + offsets, mask=mask, other=0.0)
    part = tl.sum(x, axis=0, dtype=tl.float32) #1
    tl.store(partial_ptr + pid, part) #2


@triton.jit
def final_sum_kernel(partial_ptr, out_ptr, n_partials,
                     BLOCK_SIZE: tl.constexpr):
    offsets = tl.arange(0, BLOCK_SIZE)
    mask = offsets < n_partials

    x = tl.load(partial_ptr + offsets, mask=mask, other=0.0) #3
    total = tl.sum(x, axis=0, dtype=tl.float32) #4
    tl.store(out_ptr, total)


def sum_two_pass(x: torch.Tensor, block_size: int = 1024):
    assert x.is_cuda and x.ndim == 1
    n = x.numel()
    grid0 = (triton.cdiv(n, block_size),)
    partial = torch.empty((grid0[0],), device=x.device, dtype=torch.float32)
    partial_sum_kernel[grid0](x, partial, n, BLOCK_SIZE=block_size)
    assert partial.numel() <= block_size #5
    out = torch.empty((1,), device=x.device, dtype=torch.float32)
    final_sum_kernel[(1,)](partial, out, partial.numel(),
                           BLOCK_SIZE=block_size)

    return out[0]

A Triton implementation of the two kernels for summing a one-dimensional array. section 4.1.2

How GPU Programming with Triton covers it

How deep it goes
Explains tile-local reduction, partial storage, final reduction, and repeating passes when partials exceed one block.
Examples
Uses a one-dimensional array-to-scalar sum, with each tile producing one partial result.
What you can do after
Build it from scratch with Triton kernels that write partial sums and reduce them in a second pass.
How it connects
Connects global reduction with GPU program instances, partial sums, and atomic operations.

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.