liveBook · Manning

Reduction operation

As explained in Grokking GPU Programming

The reduction pattern combines many input values into one result using an associative operation, often by combining partial results in parallel.

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

How Grokking GPU Programming covers it

How deep it goes
Develops a shared-memory tree reduction through synchronization and multi-block combination, then notes library implementations and floating-point ordering effects.
Examples
Uses exam-score subtotals, an integer-array sum, and PyTorch sum, maximum, and product calls.
What you can do after
Builds a CUDA integer-sum reduction from scratch and applies reductions via PyTorch.
How it connects
Connects reduction to map, scan, race conditions, shared memory, synchronization, and atomic operations.

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 Grokking GPU Programming. The section links point to the parts of the book it draws on.