Overview

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

FAQ

What is the main idea behind Blelloch scan?Blelloch scan is a work-efficient parallel prefix-sum algorithm. It computes the same result as a scan, but with O(n) total work instead of O(n log n), while still keeping logarithmic depth. It does this in two phases: an up-sweep that builds partial sums, and a down-sweep that distributes prefix sums back through the tree.
Why is Blelloch scan considered more work-efficient than Hillis-Steele?Hillis-Steele performs additions in every round for many threads, which leads to O(n log n) total work. Blelloch reduces the number of active threads by half each round during the up-sweep, and then reuses that tree during the down-sweep. This lowers total work to O(n), which is better for large inputs and GPU efficiency.
What happens during the up-sweep phase?During the up-sweep, neighboring partial sums are combined into larger sums in a tree-like pattern. The stride starts at 1 and doubles each round, so positions 1, 3, 5, 7 combine first, then positions 3 and 7, and so on. By the end, the last element holds the total sum of the array.
Why does the last element hold the total sum after the up-sweep?The up-sweep is a reduction tree built in place. Each round combines two smaller ranges into one larger range, and the right child absorbs the left child’s value. Because the tree grows upward through the array, the root ends up stored in the last slot instead of in the first slot.
Why is the root set to 0 before the down-sweep?The root is replaced with 0 to seed the exclusive scan. Zero is the identity element for addition, so it represents “nothing comes before the whole array.” This allows the down-sweep to propagate correct exclusive prefix sums to every position.
How does the down-sweep phase work?The down-sweep walks back down the tree from the root and turns partial sums into prefix sums. Each active pair performs a swap-and-add: the left child gets the parent’s prefix value, and the right child gets the parent’s prefix plus the left subtree’s total. After the final round, every position contains its exclusive prefix sum.
Why can Blelloch scan use only one shared memory buffer?In Blelloch scan, reads and writes are arranged so they do not overlap in the same round. In the up-sweep, each active thread reads one value and writes to a different position; in the down-sweep, each thread owns a unique pair of slots. That makes single-buffer shared memory safe, unlike Hillis-Steele, which needs double buffering.
Why does the Blelloch implementation require n to be a power of 2?The code assumes a complete binary tree layout, which is simplest when the array length is a power of 2. If n is not a power of 2, you pad the input with the identity element, such as 0 for addition, up to the next power of 2. The extra padded values do not affect the result.
How do you convert Blelloch exclusive scan into an inclusive scan?Save the original value of each element before the scan overwrites it, then add that saved value back after the exclusive scan finishes. In other words, inclusive = exclusive + original. This is just a parallel map operation after the scan.
What are some real-world GPU uses of scan?Scan is used in stream compaction, memory allocation, radix sort, and partitioning. In stream compaction, scan tells each kept element where to write. In memory allocation, it tells each thread where its block starts. In radix sort and partitioning, scan helps assign output positions in parallel.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more


Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Grokking GPU Programming Grokking GPU Programming ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Grokking GPU Programming Grokking GPU Programming ebook for free