7 Work-efficient scan: Blelloch
Chapter 7 introduces a more work-efficient way to compute scan on the GPU. The earlier Hillis-Steele approach is fast in terms of rounds, but it performs far too many additions, which matters on a GPU because extra arithmetic consumes time, energy, and block resources. The Blelloch method keeps the parallel depth logarithmic while reducing the total work to linear, making it the better choice when efficiency at scale matters.
The algorithm has two phases: an up-sweep that builds a reduction tree and accumulates partial sums, followed by a down-sweep that turns those partial sums into an exclusive prefix sum. The chapter walks through the process on a small array, showing how the active positions shrink each round in the up-sweep until the total lands in the last slot, then how a zero seed at the root flows back down through swap-and-add steps to produce the final exclusive scan. The key idea is that each phase preserves a simple invariant, which explains why the method is correct.
The CUDA implementation fits in one kernel using shared memory, one buffer, and synchronized rounds. The same index formula selects the active right-child positions in both phases, and the root is cleared before the down-sweep begins. The chapter also explains when Blelloch is preferable to Hillis-Steele, how to extend scan to larger inputs by scanning blocks and then propagating offsets, and why scan underlies practical GPU tasks such as stream compaction, memory allocation, radix sort, and partitioning. It closes by noting real-world concerns like power-of-two padding, bank conflicts, and using built-in scan operations in libraries such as NumPy, PyTorch, Thrust, and CUB.
The Blelloch scan in two phases. The up-sweep builds an implicit reduction tree across 3 rounds; the seed step replaces the root with 0; the down-sweep distributes prefix sums back down across 3 rounds. Dotted boxes are unchanged, dashed boxes are computed by add, and solid boxes are computed by swap-and-add.
Loading the input from global memory into shared memory. Each thread copies one element from data[] into buf[]; subsequent rounds read and write only buf[], avoiding the cost of repeated global-memory access.
Up-sweep Round 1 (stride = 1). The four right-sibling positions absorb their left neighbors: position 1 = 1+3 = 4 (sum of data[0..1]), position 3 = 0+7 = 7 (data[2..3]), position 5 = 1+4 = 5 (data[4..5]), position 7 = 3+6 = 9 (data[6..7]). Dashed boxes are positions just computed by add; dotted boxes are unchanged. Solid boxes, for swap-and-add, do not appear until the down-sweep.
Up-sweep Round 2 (stride = 2). Two positions remain active. Position 3 absorbs position 1 to produce the sum of data[0..3] = 11; position 7 absorbs position 5 to produce the sum of data[4..7] = 14. Half the threads of Round 1 have dropped out.
Up-sweep Round 3 (stride = 4). Only position 7 is active. It absorbs position 3 to produce the sum of data[0..7] = 25, the total of the whole array. The up-sweep has built the reduction tree in 3 rounds.
Seed step and Down-sweep Round 1 (stride = 4). After the seed sets position 7 to 0, only position 7 (with its left sibling at position 3) is active. The swap-and-add gives position 3 the seed value 0 and position 7 the seed plus position 3’s old value (0+11 = 11). Solid boxes mark swap-and-add computations.
Down-sweep Round 2 (stride = 2). Two pairs are active. Position 3 (value 0) distributes to position 1, which becomes 0; position 3 itself becomes 0+4 = 4. Position 7 (value 11) distributes to position 5, which becomes 11; position 7 itself becomes 11+5 = 16.
Down-sweep Round 3 (stride = 1). Four pairs reach every position. After this final round, each cell holds its exclusive prefix sum: [0, 3, 4, 11, 11, 15, 16, 22].
Summary
- The Blelloch algorithm is work-efficient, performing only O(n) total work in O(log n) depth: specifically 2log₂(n) rounds, twice the constant factor of Hillis-Steele. It runs in two phases: an up-sweep that builds partial sums up a binary tree, followed by a down-sweep that distributes them back to produce an exclusive scan.
- Each phase is correct because it preserves an invariant: after up-sweep round r, an active position holds the sum of the 2ʳ elements ending at itself; after each down-sweep round, a visited node holds the sum of everything before its subtree, starting from the 0 seeded at the root.
- Unlike Hillis-Steele, Blelloch needs no double buffer: within each round, the positions a thread writes and the positions other threads read do not overlap, so a single shared memory buffer is safe.
- One index formula, index = (tid + 1) × stride × 2 − 1, selects the active positions in both phases: the up-sweep walks the stride up from 1, and the down-sweep walks it back down from n/2.
- Choosing between the two algorithms is a work-versus-depth trade-off: Hillis-Steele finishes in fewer rounds but does O(n log n) work; Blelloch does O(n) work in twice the rounds. Comparing core count with element count gives a first guess, but memory traffic, barriers, and occupancy (how many warps an SM keeps resident at once; it’s covered in chapter 14) move the crossover.
- Blelloch produces an exclusive scan by construction, and exclusive is the flavor the “where do I write?” step needs: a keeper’s scan value is its destination index directly, with no off-by-one correction. Turning the result into an inclusive scan costs one extra map over the array.
- Scan is at work behind many parallel patterns, including stream compaction, parallel memory allocation, radix sort, and array partitioning.
- NumPy’s np.cumsum() computes the scan on the CPU, while PyTorch’s torch.cumsum() runs a GPU scan whenever its tensor lives on a CUDA device. Use either before writing a kernel of your own.
- Arrays larger than a single block need a multi-block strategy. The classic one takes three steps: scan each block locally, scan the array of block sums, and then add those offsets back into each block. Production libraries like CUB fuse these steps into a single pass.
Grokking GPU Programming ebook for free