7 Work-efficient Scan: Blelloch

This chapter explains how to improve scan so it does the minimum necessary work while still finishing in logarithmic time. The earlier Hillis-Steele approach is fast in terms of rounds, but it repeats a lot of additions, which makes it expensive on a GPU. Blelloch’s scan fixes that by being work-efficient: it keeps total work linear in the number of elements while still using parallel rounds to get the job done.

The core idea is a two-phase tree process. In the up-sweep, pairs of values are combined level by level until the last position holds the total sum. Then the algorithm seeds that root with the identity element, zero for addition, and runs a down-sweep that distributes prefix information back through the same tree. This produces an exclusive scan, and the chapter shows how the same index pattern can drive both phases in a single CUDA kernel using shared memory, one buffer, and synchronization after each round.

The chapter also shows why Blelloch matters beyond the kernel itself. Because it uses only one shared-memory buffer and O(n) total work, it is a practical choice for large inputs where efficiency matters more than shaving off a round or two. It also serves as a building block for other GPU algorithms, including stream compaction, memory allocation, radix sort, and partitioning, all of which depend on scans to decide where each output element should go. For larger-than-one-block inputs, the text outlines the standard multi-block strategy: scan each block, scan the block totals, then add offsets back to each block.

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.

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

• 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, growing out of 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 never 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 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 move the crossover, so benchmark both on your data.
• 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. Reach for 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.

FAQ