第13章 扫描算法

扫描（Scan），也称为前缀扫描（prefix scan）、前缀求和（prefix sum）或并行前缀求和（parallel prefix sum），是并行编程的一个重要原语，并作为基本模块用于许多不同的算法，包括很多算法但不限于以下内容：

• 基数排序 (radix sort)
  ·快速排序（quicksort）
  ·流压缩（stream compaction）和流拆分（stream splitting）
  · 稀疏矩阵与向量的乘法
  · 最小生成树构建
  面积表的求和计算

本章首先对该算法和它的一些变形予以描述，讨论一个早期的实现策略以及扫描算法如何使用电路图进行描述，然后提供CUDA扫描算法实现的细节。参考文献部分同时给出了硬件设计中的扫描算法和并行前缀求和电路问题。