Prefix sum (scan)
An introduction to work efficiency in parallel algorithms
With special contributions from Li-Wen Chang, Juan Gómez-Luna and John Owens
Abstract
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. These kernels each present 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.
Keywords
Scan; prefix sum; reduction; linear recursion; resource allocation; work ...
Get Programming Massively Parallel Processors, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
