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
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
