Scan, also known as prefix scan, prefix sum, or parallel prefix sum, is an important primitive in parallel programming, used as a building block for many different algorithms, including but not limited to:
Radix sort,
Quicksort,
Stream compaction and stream splitting,
Sparse matrix-vector multiplication,
Minimum spanning tree construction,
Computation of summed area tables.
This chapter starts with a description of the algorithm and a few variations, shows how Scan algorithms can be expressed as circuit diagrams, then gives detailed descriptions of Scan implementations for CUDA – culminating in the single-pass decoupled look-back algorithm that the CUB and Thrust libraries use today. The References section covers both the Scan algorithm and the parallel prefix sum circuit problem in hardware design.