6 The Scan pattern: Hillis-Steele
This chapter covers
- Inclusive versus exclusive scan
- Comparing parallel algorithms
- The Hillis-Steele algorithm
- Using double buffering to avoid collisions
Imagine you’re checking your bank statement. You start the month with $500. Then you spend $20 on coffee, receive a $1,000 paycheck, spend $60 on groceries, and so on. The bank shows you a running balance on every line.
Now imagine you’re the bank, and you have a million transactions to process. You could compute each running balance one at a time: transaction 1, then 2, then 3, all the way to a million. That works, but it’s slow. What you need is to split the work across thousands of helpers and still get every running balance correct.
That’s a scan, also called a prefix sum.
In chapter 5, you learned the Reduction pattern: combining a million values into one result. Instead of throwing away the intermediate results, scan keeps every one of them. Because of this property, scan lies behind sorting, filtering, memory allocation, and many other GPU algorithms; chapter 7 covers the first three.