Scan, also known as prefix scan, prefix sum, or parallel prefix sum, is an important primitive in parallel programming and is used as a building block for many different algorithms, including but not limited to the following.
• Radix sort
• 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, discusses an early implementation strategy and how Scan algorithms can be described in terms of circuit diagrams, and then provides detailed descriptions of Scan implementations for CUDA. The References section covers both the Scan algorithm and the parallel ...