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 left us with 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 gets the bill down to O(n) without giving up the logarithmic finish: the property algorithm designers call work efficiency.
The algorithm that does it is Blelloch’s, and its efficiency comes from 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 a complete 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.