GPU Gems 2 · Chapter 46. Improved GPU Sorting

排序是透明物体可见性、early-z 利用、粒子距离和碰撞空间结构的共同基础。CPU 上可以自由读写数组，但 GPU 更像大量同步执行的 SIMD lane：算法必须事先规定每个位置在每个 pass 比较谁、把结果写到哪里。

本章从简单的 odd-even transition network 出发，再转向 odd-even merge 和 bitonic merge。优化的重点不是减少某一条比较，而是让 fragment、vertex processor 和 rasterizer 都参与工作，并把 key/index 记录压紧到更少的 fetch 和 fragment 中。

1. data-independent sorting 和 compare-swap

data-independent sorting 不根据当前 key 选择下一步算法路径；同样数量的 item、stage 和 pass 总会执行同样的比较网络。这种确定结构很适合 GPU，因为线程无需互相等待或动态分配工作。

sorting network 的一个基本单元接收两个 key，把较小值送到升序通道，把较大值送到降序通道。多个单元排成一列就是一个 pass；输入从左向右经过多列后逐渐有序。

最直接的 odd-even transition sort 每轮只比较相邻位置。最坏情况下最小值每次只移动一步，因此要用 O(n²) 的 pass 才能完成 n 个元素的排序；单个 pass 很便宜，但总 pass 数在实时场景里太昂贵。

2. odd-even merge：减少全排序 pass

odd-even merge sort 把排序分成 stage 和 pass。排序 m 个元素的 stage 需要 log(m) 个 pass，所有 n 个元素总体是 O(n log²(n) + log(n)) 的 pass 结构。它仍然比 CPU 常见的 O(n log(n)) 多一些，但比逐步相邻交换少得多。

原章的 GPU 实现用 CPU 上的两个循环只传 stage、pass 和派生 uniform，然后绘制 full-size quad。fragment shader 读取当前位置和 partner 位置，执行 less-than 或 greater-equal，并写到 target buffer。问题是有些值只被复制、不需要比较，但复制和比较仍然消耗同样的 fragment 时间。

3. bitonic merge：让每个 fragment 都有工作

bitonic merge sort 让每个 stage 产生一组升序和降序子序列，然后逐步合并。第 i 个 stage 有 i 个 pass；比较距离由 stage 和 pass 决定，能够用位操作、取模和符号方向表达。

直接在 fragment 中计算所有 modulo、位移和 partner 地址并不一定高效。更好的做法是把一组具有相同参数的 fragment 组成 quad：vertex program 只给 quad 两侧一个 +1 与 −1 的 flag，rasterizer 线性插值它，fragment shader 根据 flag 的符号选择比较方向。这样 vertex processor 和 rasterizer 分担了原本由 fragment 重复完成的工作。

对于二维 field，行 pass 使用水平 compare distance，列 pass 则转置 quad 并使用垂直距离。两种方向共享同一个 sorting network 逻辑，但 texture 坐标必须分别保证 partner 位于正确的行或列。

4. key/index packing：减少 fetch，同时保留关联

key/index pair 是粒子排序和透明物体排序的关键。key 可以是 viewer distance，index 则指向粒子或几何对象；交换时二者必须一起交换。

GPU 使用四分量向量，因此可以把两个 key/index pair 装到一个 RGBA texel，切掉一半 row width。bitonic 每个 stage 的最后一级只比较相邻 item，这时两个 item 已经在同一个 fragment 中，可以把比较折叠到一次 shader 调用并省掉第二次 texture fetch。

// 逻辑上是两个 key/index pair；实际由一个 RGBA texel 携带
float4 packed = tex2D(source, texcoord);
Pair left  = unpackPair(packed.xy);
Pair right = unpackPair(packed.zw);
Pair small = left.key < right.key ? left : right;
Pair large = left.key < right.key ? right : left;
return packPairForDirection(small, large, direction);

这里的 direction 由 pass 的升序/降序区域决定，而不是由输入数据动态决定。pack 之后要测试 n 不是 2 的倍数时的尾部、index 精度和 key 的排序稳定性。

5. 动手实验：逐 pass 观察排序网络

先预测：bitonic 的某个 stage 尚未完成时，序列会不会已经全局有序？打开 packing 后，比较次数会变少，还是只会减少需要处理的 fragment groups？

实验执行真实的 bitonic 与 odd-even pass：每次推进都会生成新的 key/index 数组，比较次数按实际比较单元累加；packing 只改变逻辑 item 到 fragment group 的映射，不改变排序结果。黄色柱表示当前 pass 触及的 partner，编号表示 index 仍然跟着 key 移动。

6. 实时应用的取舍

odd-even merge 的优势是中间结果更适合逐帧观察，排序过程可以更自然地分摊到多帧；bitonic merge 的优势是更积极地重排并更充分地使用 GPU 资源，但每个 stage 的中间状态并不保持全局有序，不能随意当成“已经可显示的最终排序”。

GPU 的 pass 数仍然要结合 field 大小、纹理带宽和目标设备测量。原章报告了在 GeForce 6800 Ultra 上，bitonic 对 256²、512²、1024² field 的 pass 数和吞吐；这些数字是历史硬件实验，不应直接当作现代设备的基准。应保留算法结构，重新测量实际平台。

粒子按 camera distance 排序时，短暂的小误差有时比让应用完全停顿更可接受；但透明混合、阴影或严格碰撞排序可能需要完整有序结果。排序算法的选择必须跟视觉/物理容错契约一起做，而不是只看“GPU 比 CPU 快”。

小结

• data-independent sorting 用固定网络把比较路径交给 GPU 并行执行。
• odd-even transition 简单但 pass 太多，odd-even merge 通过 stage 降低总成本。
• bitonic merge 让每个 pass 更规则，并利用 vertex/rasterizer 生成方向和地址参数。
• 双缓冲隔离 source/target，key/index pair packing 减少 fetch 但必须保留关联。
• bitonic 与 odd-even 的中间状态和响应特性不同，应按实时容错选择。