GPU Gems 2 · Chapter 36. Stream Reduction Operations for GPGPU Applications

先解决“货物变少了，传送带怎么办”

想象传送带上每个工位都必须在自己的格子里放一件货物，但检查后有些货物要被丢弃。工位不能把剩下的货物直接推到左边空出来的格子；它只能在原位留下一个可识别的空标记，再由后续工序重新安排。

本章解决的问题是：当每个输入元素可能产生零个、一个或多个后续元素时，怎样仍然使用固定输出位置的 GPU stream？如果硬把 CPU 的“删掉并向前移动”照搬过来，就会需要 fragment processor 不支持的任意 scatter，或者把整条最大长度的空传送带一直带到后面。

1. data filtering：先保留原长度，再制造可识别的空洞

fragment processor 可以为每个固定输出位置生成一个结果，却不能根据当前输入决定“这个位置不写，后面的元素往前挪”。过滤的第一步因此不是缩短 stream，而是为每个输入位置写出两种结果：要保留的值，或一个正常算法不会产生的特殊值。

原章使用浮点 infinity 作为 null 的例子：predicate 通过的元素输出原值，否则输出 infinity。这个哨兵必须和业务数据的合法范围分离，并且在所有后续 pass 中使用同一判定规则；否则 scan 可能把真实数据误当成空洞。

// 固定输出位置的 filtering pass
float value = inputValue;
bool keep = value > threshold;
float nullRecord = 1.0 / 0.0;
outputValue = keep ? value : nullRecord;

这段代码只完成“标记”，还没有产生紧凑输出。把空洞移动到末尾需要知道每个保留元素左侧有多少个 null，这正是下一节 scan 的任务。

2. scan：用多 pass 计算每个元素的移动距离

要把一个保留元素移动到正确位置，只需要知道它左边有多少个 null。串行循环可以从左到右累计，但 GPU 更适合用多轮固定偏移：第一轮看左边 1 个位置，第二轮看左边 2 个位置，第三轮看左边 4 个位置，直到偏移覆盖整个输入。

第 i 轮的输入来自第 i−1 轮的独立 stream，因此同一轮的元素仍可并行；代价是大约 log₂(n) 个 pass 和每轮一次中间 stream。最右边的累计值还告诉我们总共有多少个 null，从而得到紧凑输出的长度。

3. compaction：把累计结果变成没有空洞的 stream

scan 给了“每个位置左边有多少空洞”，但 fragment processor 仍不能让输入记录自己 scatter 到新地址。直接用稳定排序把 null 推到尾部当然可行，却会引入 bitonic sort 的额外比较与多轮；原章的替代方案是让每个目标位置搜索对应来源，再 gather。

在实践中要分开看两种成本：scan 有跨 pass 的数据依赖，每一轮必须结束才能进入下一轮；search 的不同试探可以写成依赖 texture read，某些硬件支持 data-dependent looping 时可在一个 pass 内完成。若硬件不支持动态循环边界，也可以针对应用规模编译固定次数的搜索 kernel。

4. search/gather：反过来询问“谁应该填这里”

scan 结果是单调递增的，因此每个输出位置都可以独立做并行搜索：猜一个输入位置，比较累计 null 数与目标距离，再把猜测范围缩小一半。找到来源后，输出 kernel 在自己固定的位置读取 value[source]。从数据流角度看，记录没有被推送，输出位置主动把想要的记录取过来。

这种 compaction 的总工作量是 O(n log n)：n 个输出位置各做约 log n 步搜索。它的优势是适配 fragment processor 的 gather 限制；代价是依赖读取、scan 中间 pass、边界处理和浮点地址精度。删除比例很低时，应先比较额外 pass 是否值得。

5. 碰撞检测：过滤候选，再展开非叶节点

GPU filtering 的价值不只在删除数组元素。碰撞检测可以把两个包围盒树的候选节点对放入 stream：明显不相交的 pair 被过滤掉，相交且仍是非叶节点的 pair 被展开为子节点 pair，下一轮继续处理；叶节点才进入实际三角形检测。

这是一种 breadth-first 的 GPU 友好表达：每一轮都面对一个当前长度已知的 candidate stream，先做固定位置的 overlap test，再用 filtering 产生更短的 active list 或更长的 child list。与“从最大可能的三角形对开始、把绝大多数空位置带到底”相比，它把树的 pruning 价值保留下来。

6. 自适应细分：过滤完成项，展开 active 项

自适应 subdivision 展示了过滤的另一面：已达到尺寸条件的三角形应停止并进入渲染 stream，仍需细分的三角形则生成 children，并携带新的邻居信息进入下一轮。

这里不能只保存一个“指向邻居的指针”然后期待 GPU 随时维护动态邻接表。原章选择让三角形携带邻居坐标，牺牲一部分存储换取较少的 dependent texture lookup；每轮生成新的 Triangle 和 Neighbor stream，再根据 edge flags 进行过滤。为了防止相邻三角形对同一顶点做出不同决定，浮点加法的顺序也必须保持一致。

先猜一猜：在 Reduction Lab 中把模式从 collision 切到 subdivide，再把 filtered ratio 调低，哪一个指标会变大？打开实验后一次只改一个控件，观察 active records、scan passes、output records 和 expansion factor。

三步验收：从空洞到变长 stream

本章小结

• null record 让固定输出 pass 能表达“这个元素不要”。
• scan 用约 log₂(n) 轮累计每个元素的移动距离。
• search/gather 在固定输出位置重建紧凑 stream，绕开 scatter。
• 碰撞检测把过滤与树节点展开组合成 breadth-first stream。
• 自适应细分同时需要过滤完成项和展开 active 项。