第12章 归约算法

归约（reduction）是一类并行算法，对传入的O（N）个输入数据，使用一个二元的符合结合律的操作符 $\oplus$ ，生成0（1）个结果。这类操作包括取最小、取最大、求和、平方求和、逻辑与、逻辑或、向量点积。归约也是其他高级运算中要用的基础算法，例如将在下一章介绍的扫描。

除非操作符 $\oplus$ 的求解代价极高，否则归约倾向于带宽受限型任务（bandwidth-bound）。本章对归约的介绍，先基于SDK示例reduction提供几个两遍方法的实现。接下来，使用SDK示例threadFenceReduction演示如何采用单遍方法执行归约，单遍方法中只需调用一个内核来执行该操作。最后，本章讨论并总结了如何使用__syncthreads_count()内置函数（SM 2.0加入）实现快速的二元归约以及如何使用线程束洗牌指令（SM 3.0加入）执行归约。