上一篇博客讨论了 CUDA 性能优化的基本方法:先确认瓶颈,再从 Warp、全局内存、共享内存、Occupancy 和同步等角度逐项分析。这次把这些知识集中到一个算子上:Reduce(规约)。
Reduce 看起来只是把一组数加起来,却同时包含了 GPU 编程中最典型的难题:输入很多、输出很少;线程之间需要交换中间结果;不同实现会产生分支分歧、共享内存冲突、空闲线程和不必要的同步。AIInfraGuide 的这篇文章从 V0 到 V7 逐步优化 CUDA Reduce,很适合作为理解“一个 Kernel 如何被持续打磨”的案例。
本文以 Sum Reduce 为主线,目标是计算:
文中性能数字来自教程给出的 A100 80GB SXM4、CUDA 12.x、N = 2^{27}(128M 个 float,约 512 MB)示例。它们不是本文在当前环境中的实测结果。不同 GPU、时钟、ECC、编译选项、输入数据和计时边界都会改变结果。
1. Reduce 为什么值得单独学习?
Reduce 是典型的“多输入到少量输出”算子。除了 Sum,还包括:
1 | Sum S = x0 + x1 + ... + xN-1 |
每个元素的读取和局部计算可以并行,但最终多个部分结果必须合并。串行循环需要大约 N - 1 次合并;二叉树形规约每轮把候选数量缩小一半,理论上只需要 O(log2 N) 层。
Reduce 的一个重要特征是算术强度低。对 Sum Reduce,每个元素大致需要一次 4 字节读取和一次加法:
因此它通常是内存带宽受限的任务。优化重点不是让加法本身更复杂,而是:
- 尽量合并地读取全局内存;
- 减少无效线程和额外指令;
- 让线程间通信走更合适的层次;
- 减少屏障、循环控制和原子争用;
- 让每次 Kernel 启动处理更多有效数据。
1.1 Reduce 的输出通常是分层产生的
一个大型数组通常不会由一个线程块直接得到最终结果。更常见的流程是:
1 | 输入数组 |
本文中的 V0~V7 主要优化“每个 Block 内如何得到一个 partial sum”。如果 Grid 中有很多 Block,还必须处理 partial sum 的第二阶段。可以把 partial sums 拷回 CPU 做最后累加,也可以启动第二个 GPU Kernel,或者使用 CUB 等库。
1.2 正确性不只是“数值相等”
浮点加法不满足严格结合律:
树形规约的加法顺序与 CPU 的线性循环不同,结果最后几位出现差异是正常的。测试时应:
- 用较高精度或可信库构造参考值;
- 同时使用绝对误差和相对误差;
- 检查 NaN 和 Inf;
- 对不同 Block 大小和不同优化版本分别验证。
如果 Sum Reduce 中包含正负数相消,误差可能比简单的全正输入更明显。性能提升不能以悄悄改变数值契约为代价。
2. V0:把每个 Block 搬到共享内存,再做朴素树形规约
2.1 思路
假设一个 Block 有 256 个线程:
- 每个线程从全局内存读取一个元素,写入共享内存;
step = 1时,线程 0 加线程 1,线程 2 加线程 3;step = 2时,线程 0 加线程 2,线程 4 加线程 6;- 步长不断翻倍,直到线程 0 保存整个 Block 的和。
2.2 朴素实现
1 | __global__ void reduceV0(const float* input, float* output, int n) { |
启动时动态共享内存大小至少是 blockSize * sizeof(float):
1 | int blockSize = 256; |
最后一个 Block 可能没有填满输入,越界线程写入加法单位元 0。所有线程都执行 __syncthreads(),这样规约阶段读取的共享内存都有定义。
2.3 V0 的第一个瓶颈:Warp Divergence
GPU 以 Warp 为重要的执行单位。V0 的判断条件是:
1 | tid % (2 * step) == 0 |
同一个 Warp 中有些线程满足条件,有些线程不满足,硬件需要用不同活跃掩码执行路径。以 256 线程 Block 为例:
| Step | 活跃线程 | 直观问题 |
|---|---|---|
| 1 | tid = 0, 2, 4, ... |
一个 Warp 中约一半线程有工作 |
| 2 | tid = 0, 4, 8, ... |
更多 lane 空闲 |
| 4 | tid = 0, 8, 16, ... |
工作线程更加稀疏 |
| 更大 step | 少量低编号线程 | 大多数线程只等待同步 |
教程在特定 A100 环境中测得 V0 带宽利用率约 15%,但这个数字不应当被当作所有机器的固定结果。这里真正值得学习的是访问模式:活跃线程在 Warp 中交错出现,导致分歧和低利用率。
3. V1:改变线程映射,减少分支分歧
3.1 用连续线程表示连续工作
V1 仍然从小步长向大步长迭代,但把判断改成:
1 | int index = tid * 2 * step; |
在 step = 1、blockDim = 256 时,线程 0~127 整体进入分支,线程 128~255 整体跳过。前四个 Warp 不分歧,后四个 Warp 也不分歧。只有当活跃线程数少于一个 Warp 后,Warp 0 内才会出现部分 lane 活跃。
1 | __global__ void reduceV1(const float* input, float* output, int n) { |
V1 的经验是:线程映射本身就是性能设计的一部分。 同样的数学运算,换一种线程与数据的对应关系,就可能改变 Warp 分歧和内存访问模式。
3.2 V1 仍然不够好
V1 减少了控制流分歧,但它从小步长开始时,活跃线程访问的共享内存地址间隔较大。以 Warp 0 的部分线程为例,可能同时访问 shared[0]、shared[32]、shared[64] 等地址。它们映射到同一个 Bank 的不同地址时,会产生 Bank Conflict。
所以,消除了一个瓶颈,不代表 Kernel 已经接近最佳状态。下一步需要重新画出每个 Warp 在共享内存中的地址。
4. V2:反转规约方向,同时改善 Bank Conflict
4.1 共享内存的 Bank 访问模型
在常见 32 位共享内存模式中,可以把 Bank 编号近似理解为:
同一个 Warp 的线程访问 32 个不同 Bank 时,可以并行服务;访问同一个 Bank 的不同地址时,请求可能串行化。多个线程读取同一个地址通常可以广播,不属于同一种冲突。
4.2 从大步长向下折半
V2 使用经典的“连续线程、步长减半”模式:
1 | for (int step = blockDim.x / 2; step > 0; step >>= 1) { |
以 256 线程为例,第一轮 step = 128,线程 0~127 工作,正好是连续的四个 Warp。每个 Warp 中的线程分别访问相邻地址,访问模式规整;后续 step = 64、32、16... 继续保留低编号的连续活跃线程。
1 | __global__ void reduceV2(const float* input, float* output, int n) { |
V2 同时改善了两件事:低编号线程连续活跃,减少 Warp 分歧;相邻线程访问连续共享内存,减少典型 Bank Conflict。教程在示例硬件上给出的带宽利用率约为 40%。
4.3 为什么 Bank Conflict 不能只看数组声明?
__shared__ float shared[256] 本身没有“好”或“坏”的访问模式。冲突取决于同一条指令中一个 Warp 的 32 个线程访问哪些下标。
矩阵转置里经常使用 tile[32][33] 的 Padding,是因为列访问会让多个线程落入相同 Bank;一维 Reduce 的 V2 则主要通过改变规约方向和线程下标,让访问自然连续。两种场景的解决方法不同,不能机械套用 Padding。
5. V3:每个线程先处理两个元素
5.1 V2 中的一半线程很快会闲置
V2 每个线程只加载一个元素。第一轮规约后,Block 中只有一半线程继续参与;后续轮次中活跃线程越来越少。另一半线程在加载阶段做过一次搬运,之后大部分时间只是等待屏障。
V3 让每个线程加载两个元素,先在寄存器中相加:
1 | int gid = blockIdx.x * (blockDim.x * 2) + tid; |
完整版本:
1 | __global__ void reduceV3(const float* input, float* output, int n) { |
此时 Grid 大小必须同步修改:
1 | int gridSize = (n + blockSize * 2 - 1) / (blockSize * 2); |
如果忘记这个变化,部分输入会没有线程处理,或者多出的 Block 会重复处理数据。
V3 不减少每个 Block 的规约轮数,却让每个 Block 处理两倍输入,减少了 Block 数量和调度开销,并让加载阶段的线程做了更多有用工作。教程示例中的带宽利用率约为 45%。
每线程处理两个元素不是越多越好。继续增加元素数量可能增加寄存器压力、降低 Occupancy、拉长单线程依赖链,甚至让内存访问并行度下降。应通过实验比较 1、2、4 等处理粒度。
6. V4:展开最后一个 Warp
6.1 最后一个 Warp 不需要 Block 屏障
V3 的循环在 step = 128、64、32、16、8、4、2、1 都调用 __syncthreads()。当 step <= 32 时,只有线程 0~31 还在执行加法,也就是一个 Warp。若这 32 个线程走同一个规约路径,Block 级屏障已经没有必要。
可以保留 step > 32 的循环,再手动展开最后一个 Warp:
1 | __device__ void reduceLastWarp(volatile float* shared, int tid) { |
调用方式:
1 | for (int step = blockDim.x / 2; step > 32; step >>= 1) { |
教程的传统写法把共享内存指针标成 volatile,用来阻止编译器把跨线程通信的中间值完全缓存到寄存器。这是一个较老的共享内存展开模式。对现代 CUDA,更推荐使用 __shfl_down_sync 表达 Warp 内通信,后文 V6 会给出这种写法;若使用共享内存展开版本,必须结合目标架构、编译器生成代码和正确的同步语义验证,不能把 volatile 当成通用同步原语。
V4 的核心收益来自减少最后几个规约阶段的屏障,不是来自“展开”这个词本身。教程示例中带宽利用率约为 52%。
7. V5:用模板让规约循环在编译期展开
7.1 运行时循环还有固定开销
V4 的前几轮仍然有循环变量更新、比较、跳转和边界判断。如果 Block 大小在调用点已经选择为 128、256 或 512,那么这些轮次其实是已知的。
把 Block 大小写成模板参数,可以让编译器删除永远不会成立的条件,并生成更紧凑的指令序列:
1 | template <int BlockSize> |
调用时显式选择实例:
1 | int grid = (n + 2 * 256 - 1) / (2 * 256); |
模板展开会增加编译产物数量和维护复杂度。如果 Block 大小在运行时任意变化,不能简单地把运行时变量当作模板参数;可以为常用配置预编译多个实例,再用 switch 选择。
编译期展开也不是必然更快:现代编译器可能自动展开一部分循环,完全展开可能增大代码体积、寄存器用量或指令缓存压力。教程在示例环境中测得 V5 带宽利用率约 62%,仍应以本地 Profile 为准。
8. V6:用 Warp Shuffle 替换 Warp 内共享内存
8.1 Warp 内规约
__shfl_down_sync 让当前线程读取同一 Warp 中更高 lane 的寄存器值:
1 | __device__ float warpReduceSum(float value, unsigned mask) { |
相比通过共享内存交换值,Shuffle 不需要为 Warp 内的每一步单独写入和读取共享内存,也不需要把 Warp 内规约写成多轮 Block 屏障。
8.2 两级规约
Shuffle 只能在一个 Warp 内工作。256 线程 Block 有 8 个 Warp,因此通常分两层:
- 每个 Warp 用 Shuffle 得到一个 Warp sum;
- 每个 Warp 的 lane 0 把结果写入共享内存;
- 第一个 Warp 读取这些 Warp sums,再用 Shuffle 得到 Block sum;
- Block 的线程 0 写出 partial sum。
1 | __global__ void reduceV6(const float* input, float* output, int n) { |
对于常见的完整 Block 和尾部用 0 填充场景,也可以使用完整 Warp 掩码。这里展示动态掩码,是为了强调 Shuffle 的参与线程必须和算法实际一致。使用掩码时,要保证被命名的参与线程都能执行同一个 Warp 原语;不能只让一个分支中的线程调用,却把掩码写成全 Warp。
V6 的优势来自减少共享内存访问和同步,而不是让全局读取消失。它仍然需要一次 Warp 间的共享内存交换和一次 Block 屏障。教程给出的示例带宽利用率约 72%。
8.3 Warp Shuffle 版本的通用边界
- Block 大小最好是 Warp 大小的倍数;否则最后一个 Warp 的掩码与 Warp 数需要特别处理。
__shfl_down_sync的源 lane 必须存在于参与掩码中,或由算法保证读取结果不会被使用。- Shuffle 只交换寄存器值,不能替代 Block 级同步,也不能让不同 Block 互相通信。
- 对 Max、Min、乘法等 Reduce,只需要替换规约运算和单位元,但要考虑 NaN 规则。
9. V7:向量化加载与 Grid-stride Loop
9.1 为什么尝试 float4?
Reduce 需要从全局内存流式读取大量数据。每个线程每次读取一个 float 时,内存总字节数没有问题,但加载指令、循环控制和地址计算也有固定开销。
如果地址满足 16 字节对齐,可以一次加载四个 float:
1 | const float4* input4 = reinterpret_cast<const float4*>(input); |
向量化加载可能减少内存指令数量,提高单线程的指令级并行度,但它不会把算法的总数据量变成原来的四分之一。一个 Warp 的线程总共读取的数据量仍由输入规模决定。
9.2 对齐与尾部必须显式处理
cudaMalloc 返回的基地址通常满足足够大的对齐要求,但指针偏移可能破坏它:
1 | float* offset = input + 1; // 4 字节偏移,不能直接当作 float4 基址 |
长度 n 也可能不是 4 的倍数。安全的策略是:主体部分用 float4,剩余 1~3 个元素用标量加载。伪代码如下:
1 | int vectorCount = n / 4; |
如果基地址并不对齐,应先处理头部元素,直到地址对齐,再执行向量化主体。对齐错误不是性能小问题,而可能造成未对齐访问、错误结果或未定义行为。
9.3 Grid-stride Loop 让线程复用
V0~V6 通常让每个 Block 覆盖固定数量的元素;V7 让每个线程不断以总线程数为步长取下一段数据:
1 | int threadId = blockIdx.x * blockDim.x + threadIdx.x; |
结合 float4 时,循环下标通常以向量元素为单位。Grid 可以选择为 SM 数量的若干倍,使足够的 Block 能驻留并隐藏访存延迟;实际倍数不能照搬到不同 GPU,应通过设备属性和 Profile 选择。
9.4 一个教学版 V7 结构
下面只展示结构,省略了最后的完整错误检查和第二阶段 Reduce:
1 | __global__ void reduceV7(const float* input, float* output, int n) { |
这个片段表达了 V7 的三个思想:一个线程累计多个值、用向量类型读取连续数据、用 Shuffle 完成块内规约。真正可复用的生产代码还需要根据参与掩码、Block 配置、尾部数据和指针偏移补齐边界约束。
10. V0 到 V7:每一步在解决什么?
教程给出的 A100 示例汇总如下:
| 版本 | 主要变化 | 示例带宽利用率 | 相对速度 |
|---|---|---|---|
| V0 | 朴素树形规约 | 约 15% | 1.0x |
| V1 | 交错寻址,减少 Warp 分歧 | 约 32% | 约 2.1x |
| V2 | 反转步长,改善 Bank Conflict | 约 40% | 约 2.7x |
| V3 | 每线程处理两个元素 | 约 45% | 约 3.0x |
| V4 | 展开最后一个 Warp | 约 52% | 约 3.5x |
| V5 | 模板参数展开规约阶段 | 约 62% | 约 4.1x |
| V6 | Warp Shuffle + 两级规约 | 约 72% | 约 4.8x |
| V7 | float4 + Grid-stride Loop |
约 85% | 约 5.7x |
这些数字应该被理解为同一测试环境中逐步演进的示例,而不是所有 GPU 的性能承诺。每个版本最好单独编译、预热、测量,并使用同一份输入和相同的计时边界。
优化收益可以按来源归类:
1 | V1/V2:减少 Warp 分歧与共享内存冲突 |
这些优化会相互制约。每线程处理更多数据可能提高吞吐,也可能增加寄存器压力;向量化加载可能提高 ILP,也可能让尾部处理和对齐更复杂;更小的 Grid 可以减少调度压力,也可能无法提供足够的并行度。
11. Reduce 的第二阶段:partial sum 如何继续合并?
每个 Block 只写 output[blockIdx.x],并没有自动得到最终标量。常见的三种方案是:
11.1 CPU 汇总
适合部分和数量不大、数据本来就要回到 CPU 的场景。它简单可靠,但如果 partial sum 很多,D2H 拷贝和 CPU 循环会影响端到端性能。
11.2 第二个 GPU Kernel
先运行第一阶段,再对 partial sum 启动第二阶段:
1 | reduceV6<<<grid1, block, sharedBytes>>>(d_input, d_partial, n); |
同一个 Stream 中,第二个 Kernel 会在第一个完成后开始,Kernel 边界提供清晰的 Grid 级阶段顺序。大型输入可能需要递归地减少 partial sum,直到只剩一个 Block。
11.3 使用 CUB
生产环境中通常优先考虑:
1 |
|
上面是 API 结构示意,实际使用还要处理临时内存生命周期、Stream、错误检查和数据类型。CUB 针对多个架构维护了成熟实现,通常比手写教学版本更适合业务代码。手写 V0~V7 的价值在于理解瓶颈和建立优化能力,而不是替代经过验证的库。
12. 小结
Reduce 的优化过程可以浓缩成一条链:
1 | V0 朴素交错规约 |
最重要的收获不是记住哪个版本的带宽利用率,而是学会把一个慢 Kernel 拆成几个具体问题:线程是否分歧?共享内存是否冲突?线程是否很快闲置?屏障是否仍然必要?循环是否可以在编译期展开?数据读取是否对齐并且足够连续?
这些问题同样会出现在点积、Softmax、LayerNorm、直方图和 Attention 等算子中。掌握 Reduce,实际上是在练习一套通用的 GPU 优化方法。