This chapter introduces parallel scan (prefix-sum), an important parallel computation pattern and the concept of work-efficiency for parallel algorithms. It introduces three styles of kernels: Kogge-Stone, Brent-Kung, and two-phase hybrid. Each of these kernels presents a different tradeoff in terms of work-efficiency, speed, and complexity. The chapter then introduces two hierarchical parallel scan algorithms that are designed to process arbitrarily long input lists while maintaining work efficiency.
Scan; prefix sum; reduction; work efficiency; linear recurrence; Kogge–Stone; Brent–Kung; hierarchical ...