chapter seven

7 Work-efficient scan: Blelloch

 

This chapter covers

  • Making scan work-efficient with the Blelloch algorithm
  • Implementing both phases in one CUDA kernel with a single shared memory buffer and one index formula
  • Why total work matters and when each algorithm wins
  • Scaling past one block
  • How sorting, filtering, and memory allocation on GPUs are built on scan

Chapter 6 gave us a working parallel scan, but at a cost. Hillis-Steele finishes in ⌈log₂(n)⌉ rounds, but it pays for the speed with O(n log n) additions: for a million elements, roughly twenty times the work of the sequential loop. On a GPU, that extra work is not free: every addition costs time and energy, and the cores it occupies are cores other blocks cannot use. This chapter brings the total work down to O(n), the same order as the sequential loop, while keeping the number of rounds logarithmic. The result is called a work-efficient scan.

Blelloch’s algorithm gets there with a two-phase structure: a reduction-style up-sweep built on the tree you already know from chapter 5, followed by a down-sweep that turns those partial sums into an exclusive scan. One difference from chapter 5’s kernel is that here the stride doubles instead of halving, so the total ends up in the last slot rather than in slot 0.

The Blelloch algorithm

Up-sweep: building the reduction tree

Seed and down-sweep: distributing the prefix sums

Why does this work?

Programming the Blelloch algorithm with CUDA

Part 1: Load data into shared memory

Part 2: Up-sweep (the reduction phase)

Part 3: Clear the root (start of the down-sweep)

Part 4: Down-sweep (the distribution phase)

Part 5: Write the result back

Complete Blelloch exclusive scan

Hillis-Steele versus Blelloch

Scan in the real world

Stream compaction

Memory allocation

Radix sort

Partitioning

Scan in PyTorch

Common mistakes

Mistake 1: Mixing devices in PyTorch scans

Summary