GPU Gems 1 · Chapter 37. A Toolkit for Computation on GPUs

GPU Gems 1 第 37 章的主张很直接：GPU 不必只渲染 shaded pixels。它可以把粒子、网格点、物理方程和数组记录作为输入，通过可编程 fragment pipeline 并行计算。原章使用旧式 floating-point textures 与 pbuffers 说明方法；今天可以把这些对象理解为 GPU buffer/texture 上的中间数据，而不是把历史 API 当成唯一实现。

1. Stream programming model：把记录交给 kernel

stream processor 的关键不是暴露多少并行线程，而是把工作表达成 record stream 与独立计算。CPU 常按顺序更新共享内存；GPU 则把同一个函数应用于大量输入记录，让硬件自行安排并行执行。

在这个模型里，<Term def="对 stream 中每条记录执行一次的计算函数，通常对应一个 fragment program 或其他 GPU 程序阶段">kernel</Term> 读取当前记录、计算结果并写入对应输出位置。它不能假设另一个记录已经完成，也不能写入邻居会同时读取的共享区域。这个限制看似严格，却让独立粒子、点、像素和数组元素能够自然并行。

input stream:  position[i], velocity[i], orientation[i]
kernel:        nextPosition = integrate(position[i], velocity[i])
output stream: newPosition[i]

为什么值得这样做？历史 GPU 在浮点计算和内存带宽上都可能领先当时 CPU，且当 CPU 已经成为瓶颈、GPU 仍有空闲周期时，把一部分工作移过去还能实现 load balancing。但性能判断必须比较端到端时间：上传、pass、同步、readback 和后续工作不能被“kernel 很快”掩盖。

2. Map：逐记录更新粒子和数组

map 是最容易映射到 GPU 的通用操作。粒子模拟可以把位置、速度和方向存入 floating-point texture；绘制一个大 quad，让 fragment 数量对应粒子数量，再用 texture coordinates 找到当前粒子的记录。fragment program 计算新位置，结果写回另一个 pbuffer 或 texture。

map 的正确性条件是每个输出只依赖一个输入记录和常量参数。布料中某个点若只读取上一帧缓存的邻居位置，可以把依赖冻结在输入纹理；但如果它要读取“本次 pass 已更新的邻居”，就必须把更新拆成下一次 pass，不能假设写入立即可见。

// conceptual fragment kernel, one invocation per particle
float4 updateParticle(float2 recordUv, samplerRECT state, float dt) {
  float4 positionVelocity = texRECT(state, recordUv);
  float3 nextPosition = integrate(positionVelocity.xyz, dt);
  return float4(nextPosition, positionVelocity.w);
}

map 适合逐像素 tone adjustment、粒子积分、点云属性变换和独立的物理更新。它不负责把很多记录合成一个结果，也不负责建立有序关系；一旦输出基数改变，就要转向 reduce 或其他 primitive。

3. Reduce：多 pass 得到 min、max 或单值

reduce 解决“GPU 通常一条输入对应一条输出，但我只需要一个结果”的问题。原章以 tone mapping 为例：不要每帧把整张 HDR 图读回 CPU 找最大值，而是让每个 fragment 读取局部四个值并输出最大值，再把更小的 quad 作为下一轮输入。

每一轮可以把二维纹理的宽和高各缩小一半，因此记录数量约变为原来的四分之一；重复若干轮就能得到一个值或一个足够小的结果块。对非二次幂尺寸，要明确边界填充和无效 texel 的处理；不一定非要 reduce 到单个像素，读回一个小方块再由 CPU 做最后聚合有时更划算。

pass 0:  [a b] [c d]  →  [max(a,b,c,d)]
pass 1:  four local maxima → one local maximum
repeat:  keep reducing the active texture

reduce 的限制来自 fragment 指令数和 output 数。一个 pass 如果需要输出多个四分量矩阵，却只有一个 RGBA 输出槽，就必须拆分布局或增加 pass。算法设计要先问“这一轮能安全写出多少结果”，再决定一次合并多少输入。

4. Sort 与 Search：为粒子碰撞建立 uniform grid

粒子碰撞若让每个粒子和所有其他粒子比较，计算量会随粒子数量平方增长，而且远距离粒子的大部分比较没有价值。uniform grid 把空间划成 cell，让相邻粒子落入同一或相邻 cell；构建它需要先按 cell id 排序，再为每个 cell 找到有序列表的起始位置。

4.1 Bitonic merge sort

bitonic merge sort 适合 GPU，不是因为它在所有规模上都比 CPU 快，而是因为每个 stage 都有规则的并行比较和交换。输入存在 texture memory；每个 rendering pass 读取上一阶段纹理，计算当前元素需要比较的 partner，按方向写入 min 或 max，再将新纹理交给下一阶段。

若数据规模是 n，原章给出的 pass 数按 log n 乘以 log n 加一再除以二增长。排序一百万元素可能要约两百多个 pass，这时单纯追求 GPU 计算并不明智；较小的 4096 元素集合则可能在合适硬件上获得实际收益，尤其当排序结果无需读回 CPU 时。

辅助函数需要把一维数组地址映射成二维 texture 坐标。这个转换应保持整数索引、纹理宽度和边界条件一致；任何一处坐标误差都会在多轮 compare-and-swap 后扩大为错误排序。

4.2 Binary search

binary search 依赖已经排序的 list。uniform grid 中每个 cell 可以独立发起一次查找，寻找它在 sorted particle list 中的起始位置。每个 fragment 执行一段固定次数的依赖 texture lookup，步骤大约随 log n 增长，最后需要一次 correction 比较处理“第一个相等位置”边界。

与 sort 相比，binary search 常能在单个 rendering pass 中完成大量 query，因此当排序结果可以持续驻留 GPU 时，整体构建 grid 的成本可能很低。它不能替代 sort：无序列表上二分查找没有语义，必须明确数据生命周期和排序缓存。

5. GPU 计算的三个现实约束

5.1 有限输出

fragment program 的 output 数量和每个 output 的宽度会限制一个 pass 能保留的中间状态。ray tracing 中一个输入 ray 可能产生 reflection、transmission 和 shadow 多个结果；若硬件只提供少数输出槽，就要拆成多个 pass，或把结果重新打包到纹理的不同区域。多 pass 不是免费，它会增加读写和调度成本。

5.2 慢 readback

GPU 计算完成后若立刻把数据读回 CPU，往往需要同步 GPU、跨总线传输并阻塞后续工作。粒子位置在 GPU 更新后若必须由 CPU 做碰撞，就可能抵消 offload 的收益。更好的安排是把碰撞、排序和邻域查找也留在 GPU；只有最终摘要、少量查询或 CPU 确实必须接管的阶段才 readback。

5.3 GPU 与 CPU 的边界

CPU 上成熟的排序、调试器和 profiler 仍然很有价值。GPU 的强项是大量独立记录、规则的多 pass 和高带宽数据流；CPU 可能更适合复杂分支、强依赖和小数据集。不要为了“纯 GPU”牺牲可观测性，应以端到端 benchmark 选择 GPU、CPU 或混合 pipeline。

6. 交互实验：选择 primitive 而不是追逐算力

实验把四类 primitive 放到同一个关系模型中：map 的 pass 数固定但依赖并行独立性；reduce 的 pass 数随数据规模逐层增长；sort 的 pass 数增长更快；search 需要 sorted input 却常能在单 pass 中处理许多 query。关闭 GPU residency 会显式加入 readback penalty，减少 output slots 会让某些多结果算法需要额外拆分。

7. 可复用的 GPU 算法决策

把一个 CPU 算法迁移到 GPU 前，可以按以下顺序检查：

1. 记录化：能否把输入组织成固定格式的 stream，每条记录是否有清晰的输出位置？
2. 并行化：一个 output 是否只依赖当前 input 或上一个稳定 pass 的结果？
3. 基数变化：输出是 N、N/4 还是单值？这决定 map、reduce 和 pass 组织。
4. 顺序需求：是否需要排序后才能搜索？排序成本是否会被后续 query 数量摊薄？
5. 驻留策略：中间数据能否留在 GPU，避免每个 primitive 之间往返 CPU？
6. 端到端证据：记录 kernel、pass、纹理读写、同步、readback 和 CPU 对照，而不是只比较算术吞吐。

这套决策也解释了原章的四个核心操作：map 让大量独立记录更新成为可能，reduce 将流压缩为摘要，sort 建立有序空间索引，search 在索引上高效查询。它们不是四个孤立技巧，而是一套把通用算法重新表达为 GPU-friendly 数据流的工具箱。

小结

• GPU 的通用计算模型是 stream 加 kernel：每条记录独立处理，结果写回另一个 stream，不依赖共享可写邻居。
• map 保持记录数量，适合粒子和数组逐元素更新；reduce 通过多 pass 合并局部结果，适合 min、max、sum 和 tone mapping。
• bitonic merge sort 用规则的 parallel compare-and-swap 适应 GPU，但 pass 数可能让大数据集输给 CPU。
• binary search 依赖排序结果，能够让多个 query 并行查找 cell 起点，常适合单 pass 的依赖 texture lookup。
• 有限输出槽位、慢 readback、同步和成熟度不足的工具会改变迁移收益；GPU residency 是重要的设计选择。
• 先验证并行性、数据基数变化、pass 数和驻留策略，再用端到端数据决定 GPU、CPU 或混合实现。