Suppose you need the total of 1,000 exam scores. Adding them one at a time works, but each addition waits for the running total. Instead, groups can add separate stacks and then combine their subtotals. This is a reduction: combining many values into one result with an associative operation. section 5.0 section 5.26
A tournament of additions
To sum [1, 2, 3, 4, 5], first add pairs: [3, 7, 5]. Carry the unpaired 5 forward, then combine again: [10, 5], and finally 15. Additions within a round can happen simultaneously, but the next round must wait for their results. section 5.0 section 5.16 section 1.5
This tree approach still performs about the same total number of additions as a sequential sum. With enough workers, though, it needs only O(log n) rounds instead of O(n) sequential steps. Actual speed depends on available parallelism and overhead. section 1.4 section 5.26
Associativity permits values to be regrouped: (a + b) + c gives the same mathematical result as a + (b + c). Maximum, minimum, and product can also use reduction; each needs a suitable combining operation and identity value, such as 0 for addition. Floating-point addition only approximates associativity because each addition rounds, so a parallel sum can differ slightly from a sequential sum or another run. section 5.26 section 5.16
A CUDA reduction needs coordination at each level:
- Load each block’s slice into shared memory. Pad threads beyond the input with the operation’s identity, such as 0 for a sum. section 5.16 section 5.26
- Combine pairs in shared memory, synchronize the block, and repeat with a halved stride. This halving scheme requires a power-of-two block size. section 5.16 section 5.26
- Combine the resulting block totals safely, for example with atomicAdd for a sum or a second kernel that reduces the partial results. Initialize the final sum to 0 first. section 5.16
A common mistake is letting many threads update one ordinary accumulator: their updates can race, producing unpredictable wrong totals. Another is skipping a synchronization barrier, allowing a round to read unfinished partial results. Use barriers within each block and a safe cross-block combine. section 5.26
Reduction also appears in library calls, SQL aggregation, and distributed or multicore programs. Map applies an operation independently to each input; reduction combines values. Scan is a close relative that keeps every running total rather than only the final one. section 5.3 section 5.20
import torch tensor = torch.tensor([5, 3, 8, 2, 7, 1, 6, 4]) tensor.sum() # tensor(36) ← sum reduction tensor.max() # tensor(8) ← max reduction tensor.prod() # tensor(40320) ← product reduction
These PyTorch calls reduce the same tensor to a sum, maximum, or product. section 5.20














