Chapter 13. Scan

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

• 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, 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 ...

Get The CUDA Handbook: A Comprehensive Guide to GPU Programming now with O’Reilly online learning.

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