Chapter 8

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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.