Parallel patterns: prefix sum
An introduction to work efficiency in parallel algorithms
Li-Wen Chang and Juan Gómez-Luna
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. 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.
Keywords
Scan; prefix sum; reduction; work efficiency; linear recurrence; Kogge–Stone; Brent–Kung; hierarchical ...
Get Programming Massively Parallel Processors, 3rd 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.
