GPU Gems 2 · Chapter 31. Mapping Computational Concepts to GPUs

先建立一张翻译表

本章的任务不是把 CPU 代码逐行改写成 shader，而是建立一个可检查的翻译过程。GPU 以许多并行处理器对 stream elements 应用 kernel；因此，问题首先要回答“元素能否独立处理、数据能否批量驻留、阶段能否在边界处分开”，然后才讨论 API 细节。

1. 什么样的计算适合 GPU

GPU 最擅长的是大 stream 上重复执行相同 kernel，且每个元素只需要少量、规则的邻域信息。矩阵和向量运算、图像与体数据处理、网格上的物理模拟，以及 all-pairs 一类算法，都容易找到这种形状。相反，元素数量很少、分支路径高度不规则或每一步都要等待前一个元素的任务，通常无法充分利用并行处理器。

用 $AI=\frac{\text{operations}}{\text{words transferred}}$ 粗略表示计算密度。GPU 的计算单元增长往往快于降低内存延迟的缓存资源，所以想获得高吞吐，不能只把大量数据搬来搬去；应让每次读入的数据支撑足够多的算术工作。这里的比值是建模工具，不是跨设备可直接比较的性能分数。

网格是天然的计算域

二维网格可以自然表示为 texture，GPU 的纹理缓存也针对二维 locality 做了优化。网格上的每一步通常更新整个 grid，并且必须在下一步开始前完成；在 stream processing 的语言里，grid cells 是 stream elements，算法步骤是 kernels，每个 kernel 产生供下一步消费的新 stream。

一维地址也可以编码到二维网格中，但编码改变了索引和边界条件，不能假设它自动保留 CPU 数组的访问局部性。先定义坐标域、边界策略和元素格式，再选纹理尺寸与采样方式。

2. stream communication：gather 与 scatter

以网格模拟为例，中心单元可能要读取上、下、左、右四个邻居，这就是 gather：当前输出位置固定，但输入读取可以指向其他地址。scatter 则相反，当前元素要决定把值写到哪些输出位置。传统内存术语中，gather 需要随机读，scatter 需要随机写。

fragment processor 能从 texture 中多次读取数据，因此 gather 通常是自然路径；fragment 输出位置由已生成的 fragment 决定，并不能在 kernel 中任意改写，所以 scatter 不是它的原生能力。需要 scatter 语义时，优先考虑改写为 gather：让每个输出位置主动收集产生它所需的输入。若确实无法改写，就要显式设计地址编码、冲突处理和额外 pass。

读接口与写接口是两条边界

Texture unit 可以看成 read-only memory interface，render-to-texture 可以看成 write-only memory interface。fragment program 可以在 kernel 内读取多次，但输出写入发生在 kernel 结束时。这样的分离不是语法偏好，而是 GPU stream model 的资源约束：一个阶段读输入 stream，完成后生成输出 stream。

如果输出要成为下一阶段的输入，就把它写入 texture memory。不要在同一个 pass 中把同一 buffer 既绑定成输入又绑定成输出；这种 read/write alias 会破坏阶段边界，也会让结果依赖未定义的执行顺序。

3. CPU 概念与 GPU 概念的对应

这张翻译表可以这样使用：CPU array 变成 texture 或 vertex array；CPU inner loop 变成 fragment program；一次函数调用变成一次 draw geometry；数组索引变成 texture coordinates；输出范围变成 vertex coordinates；跨步骤反馈变成 render-to-texture。每个映射都保留一个可验证的边界，而不是把整段程序压成“GPU 版函数”。

纹理坐标由顶点携带，rasterizer 为每个 fragment 插值；在 GPGPU 中可以把插值后的坐标看成数组索引。输入 domain 和输出 range 可以同形，也可以发生 amplification 或 minification。四边形通常用来覆盖代表网格的矩形 fragment stream，顶点坐标则控制最终生成的输出范围。

4. 反馈、归约与阶段同步

多步模拟通常需要上一时间步的结果。CPU 的统一内存模型允许程序在任意位置读写；GPU 侧则要把当前输出写入 texture，再把它绑定成下一次 kernel 的输入。实际实现常用两个 buffer 交替承担 read 与 write 的角色：pass 完整结束后交换指针，而不是在同一 buffer 内原地更新。

归约不是逐元素独立的 map。以求和或最大值为例，一个 fragment 读取两个或更多值并写出一个结果；下一 pass 再对更短的 buffer 重复操作。若每次大致把范围减半，$n$ 个元素需要 $O(\log n)$ 个 pass 才能收敛到单一值。

归约的关键证据不是“最后得到了一个数字”，而是每一 pass 的 computational range、读取数量、写入数量和运算符是否保持结合性。浮点加法不满足严格结合律，因此并行归约与 CPU 顺序归约可能有微小差异；验证时应事先定义容差或采用稳定的累加策略。

5. 从映射到一个可执行框架

把概念落地时，可以用下面的顺序检查一个最小框架：初始化 GPU；加载 kernel；分配可读、可写或双向 buffer；把输入 stream 绑定到 buffer；绑定 domain 与常量；用几何指定 range 并运行 kernel；必要时在最后一次 pass 才把结果取回 CPU。旧版 GPU 框架把这些职责分别封装成 buffer、program、domain、range 和 reduction 操作，现代 API 的名字会变化，但边界仍然有用。

gpuInit()
input  = allocateBuffer(readOnly)
output = allocateBuffer(writeOnly)
program = loadKernel("stencil")
bindStream(program, "concentration", input)
bindDomain(program, gridDomain)
run(program, output, gridRange)
swap(input, output)

这段伪代码的重点是资源方向和阶段顺序，而不是某个历史 API 的可编译性。真实项目还要核对纹理格式、浮点精度、边界采样、同步、读回是否触发 pipeline flush，以及设备是否支持目标数据类型。GPU Gems 2 原章使用 Grey-Scott reaction-diffusion 作为小型例子：两个反应物浓度放在一张 texture 的两个 channel 中，kernel 对中心和四邻居做局部读取，再把新状态写入另一张 texture。

实验中的 read transactions 是由 stream length、operation 和 locality 推导出的比较量。切换到 gather 会增加每个元素的读取，切换到 reduce 会缩短输出范围并增加 pass；调整 locality 只影响读事务估算，不会改变逻辑上的元素数量。它帮助你练习“由映射推导指标”，但不能取代目标 GPU 上的 profiler。

三步验收：先保证语义，再观察代价

本章小结

• GPU 适合 data-parallel、元素独立且 arithmetic intensity 较高的 stream 计算。
• texture/vertex array 对应 CPU array，fragment program 对应 inner loop，draw geometry 负责 invocation。
• gather 是当前元素读其他位置，scatter 是当前元素写其他位置；fragment 路径通常更容易表达 gather。
• render-to-texture 把一个 kernel 的输出变成下一步的输入，双 buffer 交换能保持读写边界清楚。
• reduction 通过多个 pass 缩小 computational range，通常需要 $O(\log n)$ 个 pass；派生指标仍需真实 profiler 验证。