GPU Gems 3 · Chapter 39. Parallel Prefix Sum (Scan) with CUDA

先问：怎样让“前面所有元素的总和”同时算出来

给一列数字，每个位置都想知道它左边数字的总和。最直接的做法是从左到右累加：第一个位置算完，第二个才能开始，像一条只有一个人能走的队列。

但很多任务真正需要的不是“下一个位置必须等上一个位置”，而是每个位置最终拥有一个可写入的地址或累计值。只要把中间的部分和组织成树，许多位置就能同时工作；这个小小的改写，后来会变成筛选、排序、图结构和图像滤波的共同积木。

1. Scan 先要说清楚“当前元素算不算”

输入 [3, 1, 7, 0, 4, 1, 6, 3] 的 exclusive scan 是 [0, 3, 4, 11, 11, 15, 16, 22]。第一个位置放入加法的 identity 0，位置 j 得到输入中 j 之前所有元素的和。它也可以使用任意满足结合律的二元操作，不必局限于加法，但操作必须有明确的 identity。

同一个输入的 inclusive scan 是 [3, 4, 11, 11, 15, 16, 22, 25]。两者只差一个边界约定，却会影响后续地址是否从零开始、最后一个总和放在哪里，以及一个 predicate 的结果能否直接用作 scatter 位置。实现接口时应把这个约定写进名字或文档，不要让调用者靠猜。

scan 的价值在于把看似顺序的循环改写成两段并行工作：先让每个元素独立计算 f(input[j])，再对临时数组做 scan。这样原本的 out[j] 依赖 out[j - 1]，就变成一个可以在 GPU 上分层处理的全局原语。

2. Naive scan 有并行度，但没有工作效率

最容易想到的 GPU 版本让 offset 依次取 1、2、4、8。每一轮中，位置 k 读取 k - offset，把较远的部分和加到自己身上。单轮有很多线程，视觉上很并行；但每个 offset 都会重新访问许多元素。

长度为 n 的顺序 scan 做 O(n) 次加法，而 naive offset doubling 做 O(n log n) 次。对小数组，额外工作可能还没有显现；对大数组，log₂ n 因子会直接转成更多指令、更多 shared-memory 访问和更长的同步链。work-efficient 的目标不是让每一轮看起来更热闹，而是让所有线程合计做的工作接近顺序下界。

在 GPU 上还有一个更隐蔽的问题：warp 是硬件执行批次，不是无限多的独立处理器。一个线程块里的线程并不会同时完成所有位置；如果每个线程原地覆盖数组，而另一个 warp 还要读取旧值，结果就可能互相覆盖。双缓冲能让每一轮明确区分 input 与 output，但它无法挽救 O(n log n) 的工作量。

3. 平衡树用 up-sweep 和 down-sweep 回收前缀

work-efficient scan 把输入看成一棵平衡二叉树。第一阶段 up-sweep 从叶子向根做 reduce，根节点得到整个数组的总和；随后把根清零，因为 exclusive scan 的第一个输出必须从 identity 开始。第二阶段 down-sweep 从根向叶子走，每次交换左子树的部分和，并把旧的左和加到右子树，最终每个叶子都拥有自己的 exclusive prefix。

一棵有 n 个叶子的树有 n - 1 个内部节点。up-sweep 和 down-sweep 各访问一次，整体约做 2n - 2 次加法，仍是 O(n)。树是推导线程行为的概念，不需要在内存中创建指针结构；实际 CUDA 代码只要按层计算 index、在每层同步，并在 shared memory 中原地更新即可。

一个适合教学和调试的伪代码形状如下；它展示的是阶段关系，不是直接可编译的 kernel：

load block into shared memory
up-sweep:  combine pairs toward the root
shared[last] = identity
down-sweep: exchange and propagate toward the leaves
write exclusive results

4. 从单 block 推到大数组

单个线程块可以在 shared memory 中扫描自己负责的片段，但大数组远超一个 block 的容量。扩展方法是把数组分成 block：每个 block 做 local scan，同时把 local total 写入 SUMS；再对 SUMS 做一次 scan 得到每个 block 的 INCR；最后运行 uniform add，把 INCR[i] 加到 block i 的每个局部输出上。

这三层职责很清楚：local scan 解决 block 内部顺序，SUMS 记录 block 之间的边界，INCR 把前面 block 的总量传播回来。数组不是 block size 的整倍数时，可以 padding 到下一个 block multiple；scan 不依赖尾部 padding 之后的无效元素，最后一个 block 仍可复用同一套 kernel。

5. Work-efficient 还要经过 shared memory 的硬件现实

平衡树已经把加法次数降到 O(n)，但 index 访问模式可能让多个线程集中到同一个 shared-memory bank。bank conflict 会把本来并行的请求拆开；算法复杂度没有变，实际 latency 却会大幅增加。解决思路是给地址插入 padding 或 conflict-free offset，让相邻线程分散到不同 bank，再重新测量同步和吞吐。

原书还通过每线程处理多个元素来覆盖 global-memory latency：每个线程先在 registers 中顺序扫描自己的两个 float4，只把 partial sums 放进 shared memory；树扫描完成后，再把线程寄存器里的局部结果加上 block prefix。这让更多计算发生在寄存器中，也减少了循环、地址计算和 global load 的相对成本。固定 block size 时，把 tree loop 展开还能进一步减少控制指令。

6. 一个 scan 原语可以生成很多并行地址

对每个输入先生成 0/1 mask，再做 exclusive scan。mask 为 1 的位置，其 scan 结果就是它在 dense output 中的 destination address；随后 scatter 写入即可。scan 不负责判断元素是否保留，它负责把局部判断变成全局且无冲突的写入位置。

同一个原语还可以按行、按列生成 summed-area table，让任意宽度的 box filter 在每个像素处用固定数量的查找完成；radix sort 则用 scan 计算每个 bit predicate 的稳定位置。scan 的力量来自它把“前面有多少个满足条件的元素”变成一个可直接索引的地址。

动手走一遍：从单 block 到应用地址

7. 用 CUDA Scan Lab 比较算法和硬件代价

猜一猜：保持 1,024 elements，把 work-efficient tree 换成 naive offset doubling，再打开 bank conflicts present，哪个变化影响 modeled additions，哪个变化只影响内存服务时间？

先只切换 algorithm，比较 naive 的 O(n log n) additions 与 tree 的约 2n - 2 additions；再只切换 shared-memory access，观察 bank conflict 如何降低 relative throughput；最后将 values per thread 从 2 调到 8，思考 registers 中的 partial sums 为什么可能隐藏 global-memory latency，也为什么可能增加 register pressure。

Lab 还可以切换到 stream compaction 或 summed-area table，让你看到 scan 的输出不是最终答案，而是下一阶段的写入地址或行列累计值。数字是教学模型，不执行真实 CUDA kernel；GPU Gems 3 的历史结果显示优化后的 CUDA scan 可达到顺序 CPU 版本约 20 倍、同 GPU OpenGL 版本约 7 倍，但这些结果属于特定硬件和实现条件。

小结

• exclusive 与 inclusive 的差别是 identity 和当前位置是否进入前缀。
• naive offset scan 有并行度，却多做 O(n log n) 次加法。
• up-sweep、清根、down-sweep 组成 O(n) 的 work-efficient tree scan。
• 大数组需要 SUMS、INCR 和 uniform add 传播 block prefix。
• bank conflict、寄存器、多元素/线程和 loop unroll 决定硬件效率。

练习