02 · CUDA from a Systems Engineer’s Eyes · 报告 03

归约六级优化:一道纯带宽题

仍是同一块 RTX 4090。归约没有复用可做:每个元素只读一次, 所以上限一秒钟就能算出来:4N ÷ 1008 GB/s。 于是这一章只有一张成绩单:一个百分比。含糊的地方都会暴露。 书按顺序给了五个 kernel,每一步都有一套漂亮的分析。 开跑前,我先写死了五条预测和判决标准。 结果:五步优化只有一步打中了瓶颈, 它让每个元素快 292 倍;其余四步的收益是零。

读法一道纯带宽题↑

一、上限一秒钟算出来↑

N 元素的求和归约只有一件必须做的事:把 N 个 float 从显存读进来。 读 4N 字节,只读一次,不可能更少。写只有原子加: 次数等于 grid 数,每次 4 字节,和 1 GiB 相比可以忽略。

下限时间 = 4N 字节 ÷ 1008 GB/s

N = 2²⁸(1 GiB)   →   1,073,741,824 ÷ 1008e9 = 1.0652 ms
N = 任意           →   永远是这条线

// 报告 01/02 那套"算术强度 → roofline"的推导,在这里退化成一条水平线。
// 省掉了所有争论 —— 但也意味着任何"减少指令条数"的优化都动不了它。

所以这一章唯一有意义的成绩单是一个百分比:下限时间 ÷ 实测时间(达成率)。 这个下限简单到在纸上一秒就能算出来, 所以含糊的地方都会暴露。

二、没有算术强度可谈↑

roofline 在这一章退化成一条水平线 横轴是算术强度(对数轴),灰色折线是 4090 的屋顶。 0.1 1 10 100 带宽限:性能 = AI × 1008 GB/s 算力限 82.6 TFLOP/s 脊点 83.4 归约 R1–R6 六个版本 全部在这一条线上,一步也挪不动 K3 分块 SGEMM K5 二维粗化 算术强度(FLOP/byte,对数轴)
图 · 六个版本全部落在同一条竖线上,一步也挪不动。 SGEMM 能往右走,是因为 A 的一行要和 B 的很多列相乘,读一次能用很多次。 归约里每个元素只参与一次加法,没有复用可做。 这不是"还没想到办法",是数学上就没有。
浮点运算数 = N − 1        // 归约树总操作数,和串行一样
必须搬的字节 = 4N         // 每个 float 读一次,就这一次
算术强度 = (N−1) / 4N ≈ 0.25 FLOP/B

脊点 = 82.6 TFLOP/s ÷ 1008 GB/s = 83.4 FLOP/B
0.25 ÷ 83.4 = 1/334        // 比脊点低两个半数量级

// 对比这一路走来的几个 kernel(报告 02 §1 主表)
K1 朴素 SGEMM        0.250 FLOP/B   // 巧了,一样
K3 分块 SGEMM        7.969
K5 二维粗化 SGEMM   12.720
归约(任何版本)     0.250 —— 而且没有任何办法提高它

三、六级总表↑

五步优化 · 书里衡量什么 · 这台 4090 上的实际战果
这一步做了什么书里衡量的实际收益说明
R1 → R2消除控制 / 访存发散资源利用率 29.5% → 66.4%微秒级定性有效,定量不可信
R2 → R3搬进 shared memory显存访问 ~N·log N → N+1零8 KB 工作集全在 L1 里;收益甚至略负
R3 → R4分段 + 原子加书里只说"能处理任意长度"每元素快 292 倍唯一打中瓶颈的一步
R4 → R5线程粗化__syncthreads() 次数与原子加都除以 4零1.1203 → 1.1211 ms
R5 → R6warp shuffle(书里没有)最后 5 轮不走 shared memory零1.1211 → 1.1212 ms
书用 23 页讲前三步,2 页讲第四步;在 4090 上前者贡献 0%,后者贡献 100% 五步优化,只有一步打在瓶颈上 —— 这是开跑之前就写死的预测。 R1 → R2 消除控制/访存发散 书里衡量的:资源利用率 29.5% → 66.4% 微秒级抖动,定性有效、定量不可信 R2 → R3 搬进 shared 书里衡量的:全局访问 ~N·log N → N+1 零,甚至略负 —— 8 KB 工作集全在 L1 里 R3 → R4 分段 + 原子加 书里衡量的:书里只说"能处理任意长度" 每元素快 292 倍 ← 唯一打中瓶颈的一步 R4 → R5 线程粗化 书里衡量的:同步次数与原子加都除以 4 零(1.1203 → 1.1211 ms) R5 → R6 warp shuffle 书里衡量的:最后 5 轮不走 shared 零(1.1211 → 1.1212 ms) 实际战果 R4 一步就到达成率 95.1%,后面三行一个百分点都没再动。 以后看见"优化了 XX,减少了 YY%% 的指令",第一反应该是:YY 是这台机器上的瓶颈吗?
图 · 书用 23 页讲前三步,2 页讲第四步。 在这台 4090 上,前三步贡献 0%,第四步贡献 100%。 这不是说书错了。R1→R3 的分析在 一个 SM 内部每一条都对;它衡量的是另一样东西, 而那样东西在这张卡上不是最紧的约束。

四、跑之前写死的五条预测↑

判决标准在开跑前定死,所以 §8·二 那一栏没有商量余地。 这个做法直接沿用报告 02 §3 的"先算上限、再测、再对账"。

五条预测 · 判决标准在跑之前就定死
#预测判决标准理由
①R1 → R2 有明显加速净耗时之比 > 2×两者都只用 1 个 SM,但请求条数确实少了
②R2 → R3 再快一截净耗时之比 > 1.5×显存访问降到 N+1,向下限靠近
③R3 → R4 是数量级的跳变每元素耗时之比 > 50×本章的主赌注 —— 第一次动到真正的瓶颈
④R4 → R5 收益很小加速 < 1.2×字节账没变,收益只能来自启动开销和原子加
⑤R5 → R6 收益更小加速 < 1.1×如果 R5 已经到八成带宽,这一步基本看不见

R1朴素:交错寻址,owner 越来越远↑

一、代码↑

// ---------------------------------------------------------------------
__global__ void reduce_r1(float *input, float *output) {
    unsigned int i = 2 * threadIdx.x;
    for (unsigned int stride = 1; stride <= blockDim.x; stride *= 2) {
        if (threadIdx.x % stride == 0)          // 编号是 stride 倍数的才干活
            input[i] += input[i + stride];      // → warp 内部分裂 = 控制发散
        __syncthreads();                        // 必须在 if 外面
    }
    if (threadIdx.x == 0) *output = input[0];
}

二、谁在算,谁在陪跑↑

R1 的设计遵循"owner computes":每个位置只归一个线程所有,只有它能写。 线程 t 认领 input[2t], 即偶数位置。stride 从 1 开始翻倍, 条件 threadIdx.x % stride == 0 挑出这一轮的活跃线程。

R1 · 交错寻址:owner 是偶数位置 2t,活跃线程越来越稀疏 对照原书 Figure 10.7。16 个元素、8 个线程;时间自上而下,每一行是 for 循环的一轮。 owner = input[2·tid] T0 T1 T2 T3 T4 T5 T6 T7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 初始 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 1 T0–T7 全部活跃 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 2 只剩 4 个 → warp 内发散 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 4 只剩 2 个 → 发散更重 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 8 只剩 T0 → 31/32 的槽位在空转 问题不在"算得多",在"谁来算" 活跃线程是 0、2、4… 撒在每个 warp 里 —— 一个 warp 只要还有一个线程活着,就占满 32 个槽位。 随着 stride 变大,owner 之间越来越远,发散越来越重。这就是 10.4 节要治的病。
图 · 对照原书 Figure 10.7 重画。 时间自上而下,每一行是 for 循环的一轮;深色格子是这一轮被写入的位置。 第 1 轮偶数位置拿到成对的和(0–1、2–3…), 第 2 轮下标是 4 的倍数的位置拿到四个相邻元素的和(0–3、4–7…)。 问题在于:owner 之间越来越远, 活跃线程撒在每个 warp 里。

三、利用率:255 ÷ 864 = 29.5%↑

"执行资源利用率"衡量的是:硬件腾出的线程槽位里,有多少真的产出了结果。 它是一个分数:分子是产出,分母是占用。 下面分别数这两个量。

取 N = 256:启动 N/2 = 128 个线程,即 4 个 warp(warp w 装 tid 32w … 32w+31)。 stride 从 1 翻倍到 128,共 8 轮; 每轮由 tid % stride == 0 挑出活跃线程。

stride         1     2     4     8    16    32    64   128

活跃线程     128    64    32    16     8     4     2     1     ← tid % stride == 0
每 warp 几个   32    16     8     4     2     1     ·     ·
活跃 warp       4     4     4     4     4     4     2     1     ← 有一个活的就算一个
             └────────── 前 6 轮 4 个 warp 全在场 ──────────┘

// 要 stride 走到 64,才第一次出现"整个 warp 一个活跃线程都没有"。
分子 · 真正提交的结果
  128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
  // = N − 1。把 256 个数归约成 1 个,本来就需要 255 次加法 —— 串行也是这个数。

分母 · 被占住的线程槽位
  (4 + 4 + 4 + 4 + 4 + 4 + 2 + 1) × 32 = 27 × 32 = 864
  // 27 是"活跃 warp 数"在 8 轮里的总和,×32 是每个 warp 占满一整组槽位。

利用率 = 255 ÷ 864 = 29.5%
  // 硬件掏出去的槽位里,只有不到三成产出了一次加法。

浪费从哪来:分子固定,分母被"陪跑"撑大

分子 255 是任何归约实现都躲不掉的下限,它不会变。 所以要提高利用率,只能压低分母。 分母是 864,因为前 6 轮里每一个 warp 都至少留着一个活跃线程: 第 6 轮只有 4 个线程在干活,却仍占着 4×32 = 128 个槽位。 根源在 owner 的摆法: 2t 让活跃线程均匀撒在每个 warp 里,哪个 warp 都退不了休。

下一节的 R2 只改了三处:分子一个数都没动,分母从 864 降到 384, 利用率从 29.5% 升到 66.4%。

R2收敛:只改三处,治两个病↑

一、代码↑

// ---------------------------------------------------------------------
__global__ void reduce_r2(float *input, float *output) {
    unsigned int i = threadIdx.x;
    for (unsigned int stride = blockDim.x; stride >= 1; stride /= 2) {
        if (threadIdx.x < stride)               // 活跃的永远是编号最小的一批
            input[i] += input[i + stride];
        __syncthreads();
    }
    if (threadIdx.x == 0) *output = input[0];
}

二、warp 整批退休↑

owner 从 2*threadIdx.x 换成 threadIdx.x, stride 从 blockDim.x 开始减半,条件从 % 换成 <。 加法次数不变, 变的只是"谁来干"。

R2 · 收敛寻址:owner 换成 tid,stride 由大变小 对照原书 Figure 10.8。同样 16 个元素、8 个线程 —— 加法次数一个不多一个不少。 owner = input[tid] T0 T1 T2 T3 T4 T5 T6 T7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 初始 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 8 T0–T7 全部活跃 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 4 T4–T7 整批退休 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 2 活跃线程仍然挨在一起 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 stride 1 只有最后这几轮还发散 一处改动治两个病 ① 控制发散:warp 整批退休 —— 退了的那些一个槽位也不占。 ② 访存发散:相邻线程读相邻地址 —— 每次访问只触发 1 条请求(R1 前 5 轮要 2 条)。
图 · 对照原书 Figure 10.8 重画。 ⚠ 注意:操作数被重排了。 要结果不变,运算必须同时满足结合律和交换律。 R1 只改变加括号的方式,R2 改变的是加数的顺序。 后面 FlashAttention 能把 softmax 分块算再合并,靠的也是这个前提。

三、两本账:利用率 66.4%,请求 141 → 36↑

仍取 N = 256:128 个线程,即 4 个 warp;stride 从 128 减半到 1,共 8 轮。 下表照 §2·三 的表再列一遍, 末尾多加一行。两本账都能从这张表里读出来。

stride       128    64    32    16     8     4     2     1

活跃线程     128    64    32    16     8     4     2     1     ← tid < stride
活跃 warp       4     2     1     1     1     1     1     1     ← 整批退休
每条访问几条请求  1     1     1     1     1     1     1     1     ← 地址连号,永远只落在一条线上

// 对比 R1 的同两行:活跃 warp  4  4  4  4  4  4  2  1
//                 每条访问      2  2  2  2  2  1  1  1  ← 为什么是 2,见下面那一栏
账一 · 执行资源利用率
  分子 = 128 + 64 + … + 1 = 255          // 和 R1 一模一样,加法一次没少
  分母 = (4 + 2 + 1 + 1 + 1 + 1 + 1 + 1) × 32 = 12 × 32 = 384

  利用率 = 255 ÷ 384 = 66.4%       // R1 是 255 ÷ 864 = 29.5%

账二 · 发给显存的请求条数
  每个活跃线程每轮 2 读 + 1 写 = 3 次访问,每次访问按上表折算成请求:
  R2 = (4 + 2 + 1 + 1 + 1 + 1 + 1 + 1) × 1 × 3 = 12 × 3 = 36
  R1 = (4×2 + 4×2 + 4×2 + 4×2 + 4×2 + 4 + 2 + 1) × 3 = 47 × 3 = 141

  141 ÷ 36 = 3.9 倍

逐轮看一遍 R1:为什么中间几轮还是 2,到 stride = 32 才变 1

每一轮,warp 0 里活着的 lane 各请求一个地址;下表看这组地址落在哪几条线上。 活跃 lane 由 tid % stride == 0 挑出。 下表以三条访问里的第一条(读 input[i])为例, 另外两条结论相同。

stride   warp 0 还活着的 tid   它们 owner 的下标      落在哪几条线   请求
   1     0,1,…,31(32 个)     0,2,…,62             线0 + 线1        2
   2     0,2,…,30(16 个)     0,4,…,60             线0 + 线1        2
   4     0,4,…,28(8 个)      0,8,…,56             线0 + 线1        2
   8     0,8,16,24(4 个)     0,16,32,48           线0 + 线1        2
  16     0,16(2 个)          0,32                 线0 + 线1        2
  32     0(1 个)             0                    只剩线0          1

// 关键:活跃 lane 越来越少,但剩下的那几个地址仍然【一头一尾地跨着两条线】——
// 最小的永远是 input[0](线0);最大的只要还有第二个 lane 活着,就一定 ≥ input[32](线1)。
// 所以 lane 数从 32 掉到 2,请求数一直是 2。直到只剩 tid 0 一个人,才塌回 1 条。
// 这就是 2 2 2 2 2 1 1 1 的由来 —— 变的是"跨不跨线",不是"有几个 lane"。

// 一轮里其实有三条访问(读 input[i]、读 input[i+stride]、写 input[i]),各判各的,
// 但三条的结论在这里完全一致,所以上面那笔账才能直接乘 3。

R2 那一行全是 1,原因一句话就能说清: 活跃 lane 是 tid < stride 挑出的一段连号,请求的地址就是 input[0…stride−1], 最宽 32 个 float = 128 字节,正好一条线。 lane 变少只会让这段更短,永远跨不到第二条线。

⚠ 要当心的是模型本身,不是这套算术。 现代 GPU 的 L1/L2 按 32 字节 sector 计数, 和"一块 128 字节 = 一条请求"不是一一对应。方向是对的,但倍数不要当成硬件上的精确值。

N 越大,两边差得越多。 R1 的浪费正比于 warp 总数;R2 的浪费是常数, 因为只有尾巴上那几轮剩一个 warp 在发散。

N = 2048(1024 线程 = 32 个 warp)

  利用率   R1 2047 ÷ 7136 = 28.7%      R2 2047 ÷ 2176 = 94.1%
  请求数   R1 383 × 3 = 1149           R2  68 × 3 = 204        1149 ÷ 204 = 5.6 倍

// R2 剩下的那点浪费,全在"活跃线程掉到 32 以下之后"的最后几轮 ——
// 整棵树困在一个 warp 里,R2 治不了。那正是 R6 要收拾的尾巴。

R3shared:字节账触底↑

一、代码↑

// ---------------------------------------------------------------------
__global__ void reduce_r3(const float *input, float *output) {
    extern __shared__ float s[];
    unsigned int t = threadIdx.x;
    s[t] = input[t] + input[t + blockDim.x];    // 第 1 轮 + 搬进 shared
    for (unsigned int stride = blockDim.x / 2; stride >= 1; stride /= 2) {
        __syncthreads();                        // 挪到循环头:同步上一行那次写
        if (t < stride) s[t] += s[t + stride];
    }
    if (t == 0) *output = s[0];
}

二、第一轮在循环外做掉↑

R3 · 第一轮在循环外做掉,顺手把结果搬进 shared 对照原书 Figure 10.10。16 个全局元素、8 个线程 —— 每人读 2 个、加完再写进 shared。 全局 input 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N 次读 —— 全部合并 shared s[8] s0 s1 s2 s3 s4 s5 s6 s7 ← 第 1 轮已经做完了 s0 s1 s2 s3 s4 s5 s6 s7 stride 4 全程在片上 s0 s1 s2 s3 s4 s5 s6 s7 stride 2 全程在片上 s0 s1 s2 s3 s4 s5 s6 s7 stride 1 全程在片上 字节账到此触底 —— 后面三步一个字节也省不掉了 全局访问 = N 次读 + 1 次写;合并之后请求数 = N/32 + 1。N=256 时从 R2 的 36 条降到 9 条,又少 4 倍。 顺带一个好处:input 不再被改写 —— R1/R2 都是原地归约,跑完输入就毁了。 ⚠ 但 N=2048 时这一步没有带来加速,反而略慢:8 KB 的工作集本来就全在 L1 里, 省掉的那些"全局访问"一次 DRAM 都没碰过。详见 §8·二。
图 · 对照原书 Figure 10.10 重画。 每个线程从 global memory 读两个元素,相加后直接写进 shared memory,归约树的第 1 轮就此做完。 所以循环从 blockDim.x/2 起步,__syncthreads() 也挪到了循环头。 另一个好处:R3 不再改写 input。 R1/R2 都是原地归约,跑完输入就毁了。

三、请求账 36 → 9:字节账到此触底↑

R3 访问 global memory 的地方只剩三处,请求账很好算。 三处是开头的两条读和结尾的一次写,中间的归约树全在片上。 数法和 §3·三 相同。

// N = 256 → 128 个线程 = 4 个 warp。全局访问就这三条:

读 input[t]                warp 0 的地址 0 … 31     连号 → 线 0    1 条
                           4 个 warp 各 1 条                   4 条

读 input[t + blockDim.x]   warp 0 的地址 128 … 159  连号 → 线 4    1 条
                           4 个 warp 各 1 条                   4 条

写 output                  只有 tid 0 发                       1 条
                                                          ─────────
                                                  合计    9 条

// 换个角度数,同一个答案:N 个元素每个只读一次,连号 —— 
// N 个 float ÷ 32 个 float/线 = N/32 = 8 条线,再加 1 次写 = 9。

请求数   R2 = 36   →   R3 = 9      又少 4 倍

剧透:在 N=2048 上,这一步没有变快,反而略慢

8 KB 的工作集本来就全在 L1 里, R3 省掉的那些 global memory 访问一次也没到过显存。 书说 global memory 访问从 ~N·log N 降到 N+1,这没错。 但它数的是访问次数,不是显存流量。 完整分析见 §8·三。

R4分段:叫醒另外 127 个 SM↑

一、代码↑

// ---------------------------------------------------------------------
__global__ void reduce_r4(const float *input, float *output) {
    extern __shared__ float s[];
    unsigned int segment = 2 * blockDim.x * blockIdx.x;   // 我这个 block 的段起点
    unsigned int i = segment + threadIdx.x;
    unsigned int t = threadIdx.x;
    s[t] = input[i] + input[i + blockDim.x];
    for (unsigned int stride = blockDim.x / 2; stride >= 1; stride /= 2) {
        __syncthreads();
        if (t < stride) s[t] += s[t + stride];
    }
    if (t == 0) atomicAdd(output, s[0]);        // 每个 block 交一次答卷
}

二、单 block 的天花板↑

R4 · 把输入切成段,每段一个 block,各自跑完再原子加汇总 对照原书 Figure 10.12。跨 block 没有屏障可用 —— 所以只能让它们各跑各的,最后在一个地址上碰头。 全局 input(N 个元素) 段 0 2 × blockDim.x 个元素 段 1 2 × blockDim.x 个元素 段 2 2 × blockDim.x 个元素 段 3 2 × blockDim.x 个元素 … segment = 2 · blockDim.x · blockIdx.x block 0 树跑完 → s[0] block 1 树跑完 → s[0] block 2 树跑完 → s[0] block 3 树跑完 → s[0] output(1 个 float) ← atomicAdd,每个 block 交一次答卷 这一步换来的不是"少搬字节",是"多用 127 个 SM" 书里只说它"能处理任意长度"。但 R1/R2/R3 都只能开一个 block,而一个 block 只能待在一个 SM 上 —— 这才是真正的天花板。
图 · 对照原书 Figure 10.12 重画。 输入切成若干段,每段 2*blockDim.x 个元素。每个 block 独立跑完自己那一段的树, 再用 atomicAdd 把部分和加到同一个 output 上。 __syncthreads() 管不到 block 之间,所以只能分这两层。
前三步在一个 SM 里精打细算,第四步把另外 127 个 SM 叫醒 R1/R2/R3 靠 __syncthreads() 协调,而它只在 block 内有效 —— 一个 block 只能待在一个 SM 上。 R1 / R2 / R3 1 / 128 个 SM 在工作 R4 / R5 / R6 128 / 128 个 SM 在工作 R3 处理 2,048 个元素用 0.0025 ms,R4 处理 268,435,456 个元素用 1.1203 ms 数据量 ×131,072,耗时只 ×448 → 每元素 1.2207 ns → 0.0042 ns,快 292 倍
图 · 书里只说 R4"能处理任意长度",没提它同时把并行度乘了 128。 R1/R2/R3 无论怎么优化,都只用到 4090 的 1/128: __syncthreads() 只在 block 内有效,而一个 block 只能待在一个 SM 上。

三、唯一打中瓶颈的一步↑

R3:处理 2048 个元素,耗时 0.0025 ms   →  每元素 1.2207 ns
R4:处理 268435456 个元素,耗时 1.1203 ms   →  每元素 0.0042 ns

数据量  ×131072   ←─ 十三万倍
耗时    ×448      ←─ 只多了四百多倍
每元素  快 292 倍   (用净耗时口径算也有 82 倍)

// 128 个 SM 闲着的时候,你在那一个 SM 里做什么优化都是徒劳。

R4 一步把达成率推到 95.1%。达成率只有一个公式,有两种等价写法:

达成率 = 下限时间 ÷ 实测时间  =  (4N ÷ 峰值带宽) ÷ 耗时
       = 有效带宽 ÷ 峰值带宽  =  (4N ÷ 耗时) ÷ 峰值带宽

// 两种写法里 4N 都在分子分母间约掉了 —— 本质上就是"你比理论下限慢了多少"。

代进 R4 的数(N = 2²⁸,耗时 1.1203 ms):

① 先算有效带宽
   4N = 4 × 268,435,456 = 1,073,741,824 字节 = 1 GiB
   有效带宽 = 1,073,741,824 ÷ 0.001120 s = 958.5 GB/s
   达成率   = 958.5 ÷ 1008 = 95.1%

② 先算下限时间(同一个数)
   下限   = 1,073,741,824 ÷ 1008e9 = 1.0652 ms
   达成率 = 1.0652 ÷ 1.1203 = 95.1%

R4 跑完,墙上已经没有空间留给 R5 和 R6 了。 1008 GB/s 是理论峰值。STREAM 类基准通常只能到 85–93%, 归约是纯顺序读,所以能更贴墙。

R5粗化:把欠载的步数变少↑

一、代码↑

// ---------------------------------------------------------------------
__global__ void reduce_r5(const float *input, float *output) {
    extern __shared__ float s[];
    unsigned int segment = COARSE_FACTOR * 2 * blockDim.x * blockIdx.x;
    unsigned int i = segment + threadIdx.x;
    unsigned int t = threadIdx.x;

    float sum = input[i];                                  // 粗化循环:全员活跃
    for (unsigned int tile = 1; tile < COARSE_FACTOR * 2; ++tile)
        sum += input[i + tile * blockDim.x];               // 步长 = blockDim.x → 合并
    s[t] = sum;

    for (unsigned int stride = blockDim.x / 2; stride >= 1; stride /= 2) {
        __syncthreads();
        if (t < stride) s[t] += s[t + stride];
    }
    if (t == 0) atomicAdd(output, s[0]);
}

二、先自己吃掉几个,再爬树↑

R5 · 粗化:先让每个线程自己吃掉 4 个元素,再开始爬树 对照原书 Figure 10.14 —— 在 10.10 的基础上按 COARSE_FACTOR = 2 粗化:一个 block 从 16 个元素变成 32 个,每线程从 2 个变成 4 个。 全局 input(32 个元素,8 个线程) tile 0 tile 1 tile 2 tile 3 ① 粗化循环 · 3 步 全员活跃 不碰 shared 不用同步 sum += input[i + 1·blockDim.x] 8 个线程全部在干活 sum += input[i + 2·blockDim.x] 8 个线程全部在干活 sum += input[i + 3·blockDim.x] 8 个线程全部在干活 ② 归约树 · 3 步 每步一半退休 每步要屏障 每步碰 shared 4 / 8 个线程在干活 2 / 8 个线程在干活 1 / 8 个线程在干活 粗化把"满载的步数"变多,把"欠载的步数"变少 而欠载的那几步,每一步都要搭上一次屏障和一次 shared 读写 —— 那才是这一步想省的东西。
图 · 对照原书 Figure 10.14 重画。 上半那三步不碰 shared memory、不用同步,因为部分和一直累在寄存器 sum 里,四个元素全加完才写进 shared memory,线程之间没有依赖。 ⚠ 我们的 reduce_ch10.cu 用的是 4,是图里的 2 倍(每线程 8 个元素、粗化循环 7 步)。

三、书的推理对,但墙在另一侧↑

为什么粗化能省:把两个 block 的活交给一个 对照原书 Figure 10.16。场景:32 个元素、每个 block 8 个线程。两边做的加法一样多(都是 31 次),差别只在"归约树跑了几遍"。 满 每人把自己负责的几个元素加起来—— 8 个线程全在干活,部分和累在寄存器里,不用屏障、不碰 shared 欠 爬归约树 8→4→2→1 —— 每步一半线程退休,而且每步都要一次屏障 + 一次 shared 读写 A · 不粗化:每 block 吃 16 个元素,32 个元素要两个 block block 0 满 欠 欠 欠 每人 2 个 → 1 次加法,再爬 3 层树 block 1 满 欠 欠 欠 另外 16 个元素,同样 4 步 共 8 步 2 满 + 6 欠 硬件排不下就串着跑 —— 归约树那 3 步被付了两遍。 B · 粗化 ×2:一个 block 吃下全部 32 个元素 满 满 满 欠 欠 欠 每人 4 个 → 3 次加法(全程寄存器),再爬 3 层树 共 6 步 3 满 + 3 欠 "满"多了 2 步,但"欠"少了 3 步 —— 归约树只付一遍。 账面上确实省了:欠载步数 6 → 3,屏障和 shared 访问都减半 而且"block 会被硬件串行"这个前提在这里是成立的:R4 在 N = 2²⁸ 下要跑 524,288 个 block, 而 4090 同时只驻留得下约 768 个(128 SM × 每 SM 6 个)—— 串行了约 680 轮。R5 把 block 数砍到 131,072,账面收益是实打实的。 ⚠ 可实测收益仍然是零。因为这个 kernel 卡在 DRAM 带宽上:SM 本来就在等访存,省下的屏障和 shared 访问被那段等待盖住了。 省下来的是"算"的时间,而墙在"搬"那一侧 —— 详见 §8·二。
图 · 对照原书 Figure 10.16 重画。 账面上确实省了:8 步 → 6 步,欠载步数 6 → 3,__syncthreads() 和 shared memory 访问都减半。 书这套推理的前提是"硬件资源不够、block 会被串行"。 这个前提在 4090 上确实成立:R4 要跑 52 万个 block,同时只驻留得下几百个。 但实测收益还是零, 因为省下的是"算"的时间,而这个 kernel 的墙在"搬"那一侧。

字节账一分没变,这一步改的全是开销账。 实测是 R4 的 0.999×, 即收益为零(1.1203 → 1.1211 ms)。

R6warp shuffle:书里没有的一版↑

一、代码↑

按行号逐行读。注释里标了四个阶段: ① 粗化循环(和 R5 一字不差)→ ② warp 内 5 轮 shuffle → ③ 每个 warp 交一个数 → ④ 第一个 warp 收尾。 新增的只有 ②③④, 它们只省下一件事:__syncthreads() 从 8 次降到 1 次。

01  __global__ void reduce_r6(const float *input, float *output) {
02      extern __shared__ float warp_s[];        // 只要 blockDim.x/32 个 float —— R5 要 blockDim.x 个
03      unsigned int segment = COARSE_FACTOR * 2 * blockDim.x * blockIdx.x;
04      unsigned int i = segment + threadIdx.x;  // 03–05 行和 R5 一字不差
05      unsigned int t = threadIdx.x;
06      unsigned int lane = t & 31, warp = t >> 5;   // 我是第几个 warp 的第几个 lane
07      unsigned int nWarps = blockDim.x >> 5;       // BLOCK=256 → 8 个 warp
08
09      float sum = input[i];                    // ① 粗化循环:和 R5 完全相同
10      for (unsigned int tile = 1; tile < COARSE_FACTOR * 2; ++tile)
11          sum += input[i + tile * blockDim.x]; //    这一段才是真正搬字节的地方
12
13      for (int off = 16; off > 0; off >>= 1)   // ② warp 内 5 轮,全在寄存器
14          sum += __shfl_down_sync(0xffffffffu, sum, off);
15                                               //    做完:每个 warp 的 lane 0 手里是本 warp 32 个数的和
16      if (lane == 0) warp_s[warp] = sum;       // ③ 8 个 warp 各交 1 个数
17      __syncthreads();                         //    全 kernel 唯一一次屏障(R5 有 8 次)
18
19      if (warp == 0) {                         // ④ 头一个 warp 收尾 —— 32 个 lane 整齐进出,mask 才合法
20          sum = (lane < nWarps) ? warp_s[lane] : 0.0f;   // 多出来的 lane 取单位元 0
21          for (int off = 16; off > 0; off >>= 1)
22              sum += __shfl_down_sync(0xffffffffu, sum, off);
23          if (lane == 0) atomicAdd(output, sum);
24      }
25  }

二、它省了什么↑

R6 · 树的最后 5 层根本不需要 shared(书里没有这一版) 活跃线程掉到 32 以下之后,整棵树的剩余部分就困在一个 warp 里 —— 而 warp 内 32 个 lane 天然同步、寄存器还能互相读。 warp 的 32 个 lane off 16 16 个 lane off 8 8 个 lane off 4 off 2 off 1 sum += __shfl_down_sync(0xffffffff, sum, off) —— 5 轮,全在寄存器里,一次屏障都不要 这 5 轮全程在寄存器里完成 32 个 lane 从头到尾步调一致 —— shared 0 次、屏障 0 次、发散 0 轮(没有"退休"这回事)。
图 · 省掉的正是 §3·三 那张表尾巴上的一串 1。 R2 的"活跃 warp"那行是 4 2 1 1 1 1 1 1,尾巴上一共六个 1: 从 stride = 32 起,整棵树只剩一个 warp。 第一个 1 那轮还是满员的 32 个 lane,不发散; 问题出在后五个:warp 内只剩 16、8、4、2、1 个 lane 在干活, 却每轮还要访问 shared memory、调一次 __syncthreads()。 R6 让这 5 轮改走寄存器;每个 warp 只交一个数给 shared memory, 再由 warp 0 收尾。全 kernel 只剩一次 __syncthreads()。

R6 是整条链上唯一一个书里没有的版本,也是唯一一个"理论上该有收益"的收尾优化。 实测收益同样为零:1.000× (1.1211 → 1.1212 ms)。 原因是 R4 已经站在带宽墙上, 省掉再多指令也没有地方可以变快。

三、第 02、06–07 行:先把几个数字分清↑

第 06–07 行的三个位运算都基于一件事:32 = 2⁵。 "除以 32"就是右移 5 位,"模 32"就是保留低 5 位。 换句话说,线程编号的二进制本来就分成两段: 高位段是 warp 号,低 5 位是 lane 号。 这两行不是技巧, 只是读出这个数本来的结构。

// 拿 t = 77 摊开(BLOCK = 256)
t      = 0b …0100 1101   (77)
31     = 0b …0001 1111          ← 低 5 位全 1,高位全 0
t & 31 = 0b …0000 1101   (13)   ← lane:我在本 warp 里排第 13
t >> 5 = 0b …0000 0010   (2)    ← warp:我在第 2 个 warp(低 5 位整个移出去丢掉)

t = 77 :   0000010  01101          验算:2 × 32 + 13 = 77 ✓
           └──┬──┘  └─┬─┘
          warp = 2   lane = 13

为什么这几个变量一律写成 unsigned int

对 unsigned,% 32 和 & 31 编译出的机器码完全一样—— 写位运算只是表意习惯("我在取 lane"比"我在取余数"直白)。 换成 signed int 就不等价了:

-1 % 32  ==  -1        而   -1 & 31  ==  31
-1 / 32  ==   0        而   -1 >> 5  ==  -1     // 算术右移向负无穷取整,除法向零取整

所以对 signed,编译器不能做这个替换, 必须插额外指令处理符号位。 这条对整份 CUDA 代码都成立: 从 threadIdx / blockIdx 派生的下标一律用 unsigned ——这样语义正确,这些除法和取模也真正免费。

这么切为什么是"对的",以及多维 block 的经典 bug

硬件规则:把 block 内的线程按线性编号排好, 每 32 个连续编号切一刀。这个划分是固定的,改不了。 一维 block 的线性编号就是 threadIdx.x, 所以可以直接写 t & 31 / t >> 5。 多维 block 必须先线性化: threadIdx.x + blockDim.x*threadIdx.y + blockDim.x*blockDim.y*threadIdx.z。 在二维 block 里直接把 threadIdx.x & 31 当 lane 是错的。

第 02 行的 extern 是 CUDA 借用的关键字, 和 C 里"符号定义在别的编译单元"的含义无关。

// 静态:大小写死在代码里,编译期确定 —— 书里 Fig. 10.13 / 10.15 的写法
__shared__ float input_s[BLOCK_DIM];     // BLOCK_DIM 必须是编译期常量

// 动态:大小留空,运行期才确定 —— 本报告 R3–R6 的写法
extern __shared__ float warp_s[];        // 注意数组没有维度:是 float[] 不是 float[8]

没有维度的数组是不完整类型。标准 C 只允许 extern 声明这样写,CUDA 借这个语法位置表达另一件事: "这块 shared memory 有多大,不由 kernel 决定,由启动方在运行时给出。" 给出大小的地方是 <<< >>> 的第三个参数:

reduce_r6<<<grid, block, smem>>>(in, out);
                         ^^^^ 动态 shared 的字节数,省略则为 0

// reduce_ch10.cu 的 launch 里给 R6 算的就是它:
size_t smem = (kind == K_R6) ? (block.x / 32) * sizeof(float)   // 8 个 float = 32 B
                             : block.x * sizeof(float);         // R5 要 256 个 = 1 KB

// 单位是字节,不是元素个数 —— 两个高频错误:
<<<grid, block, block.x / 32>>>   // ✗ 漏了 sizeof,只给 8 字节(要 32)
<<<grid, block>>>                 // ✗ 干脆忘了第三个参数 → 0 字节 → 第 16 行立即越界
// 两种都能编译、都能跑,只是结果错或随机崩。compute-sanitizer --tool memcheck 能抓到。

一个限制:整个 kernel 只有一块动态 shared memory

extern __shared__ float a[];
extern __shared__ int   b[];      // a 和 b 是同一块内存,不是两块

// 要放多个数组,得自己切:
extern __shared__ char smem[];
float* a = (float*)smem;
int*   b = (int*)(smem + n * sizeof(float));

数组名和类型只是一个"视角" ——数组名代表的总是那块内存的起始地址,类型只决定怎么解释里面的字节。 R6 用动态写法,是为了在命令行上换 BLOCK 而不必重编译; 代价是多了"忘传第三个参数"这个出错点。

四、第 13–14 行:一行代码 = 32 件同时发生的事↑

难点多半在第 13–14 行。先记住一条:sum 不是一个变量,是 32 个变量。 第 09 行 float sum = input[i]; 在每个线程里各执行一遍。一个 warp 有 32 个线程,就有 32 个互不相干的 sum, 各自在自己的寄存器里。它们同名,但不是同一个东西。 不先明确这一点,第 14 行出现两次的 sum 就读不通。

// off = 16 时,第 14 行展开后是这 32 条语句,【同时】发生(下标 = lane 号):

lane  0 :  sum₀  =  sum₀  + sum₁₆        ← 拿 lane 0+16 的值
lane  1 :  sum₁  =  sum₁  + sum₁₇
  ⋮
lane 15 :  sum₁₅ =  sum₁₅ + sum₃₁        ← 以上 16 个有意义
─────────────────────────────────────
lane 16 :  sum₁₆ =  sum₁₆ + sum₁₆        ← 想拿 lane 32,越界 → 拿到自己 → 翻倍
  ⋮
lane 31 :  sum₃₁ =  sum₃₁ + sum₃₁        ← 以上 16 个算出垃圾,但没人要

// __shfl_down_sync(0xffffffffu, sum, 16) 对 lane i 而言,返回值就是 sum(i+16)。
// 仅此而已 —— 它不改任何人的值,只是让 lane i 能读到 lane i+16 的寄存器。

"lane 0 读 sum₁₆ 时,lane 16 会不会已经把自己改了?"

不会。这是 __shfl_*_sync 这条指令的语义保证的: 参与的 lane 先在这条指令上汇合,每个 lane 读到的都是伙伴在这条指令之前的 sum,再各自做加法写回。 等号右边读到的都是这一轮开始前的旧值, 所以不存在"谁先谁后"。也因此不需要额外的 __syncwarp(): __shfl_*_sync 自带 warp 内汇合,mask 就是为此而设。 这是 shuffle 比 shared memory 快的根本原因: shared memory 那条路是"我写内存 → __syncthreads() → 你读内存",shuffle 是寄存器直连。

五、第 19–24 行:收尾那一个 warp↑

先看清执行到第 19 行时还剩什么。

warp_s[0] = warp 0 那 32 个 lane 的和
  ⋮                                        // BLOCK=256 → nWarps = 8
warp_s[7] = warp 7 那 32 个 lane 的和

// 而每个线程寄存器里的 sum 此刻是垃圾:上一段跑完只有各 warp 的 lane 0 是对的,
// 那个值已经在第 16 行存进 shared 了。
// 所以第三段只剩一句话要做:把 shared 里这 8 个数归约成 1 个。

① 第 19 行 if (warp == 0):只剩 8 个数,一个 warp 的 32 个 lane 足够; 其余 7 个 warp(224 个线程)到这里直接退出,不再占用执行资源。它们所在 block 的 shared memory 和 block 槽位,要等整个 block 结束才释放。 warp == 0 等价于 t < 32, 分支边界正好落在 warp 边界上。所以第 22 行那个 0xffffffffu 的承诺成立 (§7·四);而且分支发生在 warp 之间,warp 内没有线程走两条路, 不产生发散。 "留一个 warp 收尾,其他 warp 退出"是通用模式, 切法必须对齐 warp 边界。

② 第 20 行 sum = (lane < nWarps) ? warp_s[lane] : 0.0f :注意是 =,不是 +=。 寄存器里原来的 sum 是垃圾,必须整个覆盖; 当成"继续累加"就全错了。这一行同时做三件事:

(一)装载      lane 0…7 各读一格 warp_s[lane],落在 8 个不同 bank,无 bank conflict。
(二)填单位元  lane 8…31 填 0.0f。mask 承诺了 32 个 lane 到场,得让它们到场又不干扰结果 ——
                0 是加法单位元,加几个都不改答案。用单位元把队伍填齐,比精确控制谁参与更简单也更安全。
(三)防越界    warp_s 只分配了 nWarps = 8 个 float(32 字节)。
                写成 sum = warp_s[lane],lane 8…31 会去读 warp_s[8] … warp_s[31],全部越界。
                所以 lane < nWarps 不只是为了填单位元,它还是这段唯一的边界守卫。

③ 第 21–22 行和第 13–14 行逐字相同 ,只是这时 32 个 lane 里只有 8 个装着真数据。 设 warp_s[w] = w+1(1…8,总和 36),跟踪 lane 0:

  轮   off   lane 0 的搭档              搭档的值   lane 0 变成
起始     —   —                                 —   1
   1    16   lane 16                           0   1 + 0  = 1     ← 空转
   2     8   lane 8                            0   1 + 0  = 1     ← 空转
   3     4   lane 4                            5   1 + 5  = 6
   4     2   lane 2                     3+7 = 10   6 + 10 = 16
   5     1   lane 1             (2+6)+(4+8) = 20   16 + 20 = 36   ✓

// 5 轮里只有后 3 轮(log₂8)在干实事。想省掉就得按 nWarps 动态算起始 off,
// 那要引入运行时计算或分支;而这里的代价只是每个 block 多 2 条 shuffle,还只有一个 warp 在跑。

④ 第 23 行 if (lane == 0) atomicAdd(output, sum); 5 轮走完,只有 lane 0 手里是整个 block 的和,其余 31 个是中间值。 这个 if 确实是 warp 内发散,但只有一条指令,而且 atomicAdd 打在同一地址上本来就串行。 这里 lane == 0 和 t == 0 等价,前者更贴合"warp 坐标系"的语境。

为什么必须是"三段",以及一个刚好封闭的边界

第一段   8 个 warp 并行,各自 32 → 1   全在寄存器,0 次屏障
  ↓      8 个数必须过一趟 shared       ← 卡点只在这里
第三段   1 个 warp 把 8 → 1            全在寄存器,0 次屏障

// 根本原因一条:__shfl_* 的作用域是 warp,跨 warp 交换它无能为力。
// 所以中间那次 写/屏障/读 省不掉 —— 这就是屏障只能从 8 次降到 1 次、而不是 0 次的原因。

边界刚好封闭:BLOCK 最大 1024 → nWarps 最大 32 → 正好填满一个 warp。 如果 block 能开到 2048 个线程,nWarps 就是 64,一个 warp 装不下, 第三段还要再分一次,结构会变成四段甚至递归。 CUDA"每个 block 最多 1024 个线程"这条硬限制,正好让三段式封闭。

⚠ 第 17 行的 __syncthreads() 必须放在 if (warp == 0) 外面。 它要求 block 内全部 256 个线程都到达;挪进 if, 另外 7 个 warp 永远到不了,结果是死锁。反过来看:正因为它在外面, 第 20 行的 lane 0 才能安全读到 warp 7 写的 warp_s[7]。

六、同一棵树,换了个载体↑

R5 树里的那一行和 R6 的这一行是同一棵树,只是"格子"换了地方。

BLOCK = 256 的一个 block,两种走法
R5 shared memory 树R6 warp shuffle
我的累加器s[t] shared memory 第 t 格sum 我自己的寄存器
我要加的搭档s[t + stride]__shfl_down_sync(…, sum, off) lane t+off 的寄存器
每轮折半的距离stride = 128, 64, …, 1off = 16, 8, 4, 2, 1
挡住多余线程if (t < stride) 必须有没有 if —— 理由见下框
同步每轮一次 __syncthreads()不需要 lane 天然同步
一个 block 的开销shared memory 访问 1022 次、__syncthreads() 8 次、占 1 KBshared memory 访问 16 次、__syncthreads() 1 次、占 32 B
发散的轮数后 5 轮0 轮
搬的字节4N4N 一分没变

off 从 16 开始而不是 32,因为第一轮要把 32 个 lane 折成 16 对 ——这和 R5 的 stride = blockDim.x/2 同构。 循环正好 5 轮,因为 32 = 2⁵。

为什么 R6 敢去掉 if,R5 不敢:这是两者唯一的实质区别

R5 如果去掉 if (t < stride),本该退出的线程算出的垃圾会 写进 shared memory;下一轮别人读这些格子就读到垃圾,污染会扩散。

R6 去掉 if 完全无害,因为 shuffle 不写任何共享存储—— lane 16…31 的垃圾只留在自己的寄存器里;它们摆出去给别人读的那份, 是上一轮结束时的合法值。 一句话:R5 用 if 挡住多余线程, 是为了保护 shared memory;R6 不需要挡,因为没有共享的东西会被弄脏。 收益是发散轮数 5 → 0:32 个 lane 从头到尾步调一致, 不发生分支。代价是一半的加法白算了,但那些 lane 本来也闲着。

用真数字验证:设 lane i 的初值 = i+1(即 1, 2, … 32),总和应为 528。跟踪 lane 0:

轮   off   lane 0 的搭档   搭档此刻的值   lane 0 变成      此时 lane 0 覆盖了哪些原始 lane
起始  —      —              —             1               {0}
 1   16     lane 16         17            1 + 17  = 18    {0, 16}
 2    8     lane 8          34            18 + 34 = 52    {0,16,8,24}
 3    4     lane 4          68            52 + 68 = 120   上面 4 个,各自 +4 → 8 个
 4    2     lane 2         136           120 +136 = 256   16 个
 5    1     lane 1         272           256 +272 = 528   全部 32 个 ✓

// 每一轮 lane 0 的搭档,都是"另外半棵树的根"—— 它手里的值恰好是那半棵树的全部和。

实测两个实验,一张成绩单↑

2026-09-21 实跑,RTX 4090 (sm_89) · 128 SM · 峰值带宽 1008 GB/s · 每 SM 1536 线程。 六个 kernel 全部校验通过, compute-sanitizer --tool racecheck 报告 0 hazards。 编译期检查也没有问题:全是 0 bytes stack frame、0 spill,寄存器最多 20 个。

一、实验 A / 实验 B↑

实验 A · N=2,048 · 单 block · 1000 次取平均
kernel原始耗时减去空 kernel相对 R1(净)
空 kernel0.0018 ms—基线
R1 朴素0.0040 ms2.2 µs1.00×
R2 收敛0.0023 ms0.5 µs4.40×
R3 shared0.0025 ms0.7 µs3.14×

这张表只能看定性结论

净耗时只有 0.5–2.2 µs, 而空 kernel 本身就要 1.8 µs。 减掉空 kernel 后,剩下的量级和 cudaEvent 的分辨率同阶, ±0.1 µs 的抖动就能让倍数翻一番。按原始耗时算,R1→R2 只快 1.74×, R2→R3 是 0.92×(R3 略慢)。 两种口径的定性结论相同: R1→R2 变快了,R2→R3 没有变快。

实验 B · N=268,435,456(1 GiB)· 整卡 · 11 次取平均
kernel耗时有效带宽达成率相对上一行原子加
下限 4N ÷ 1008 GB/s1.0652 ms1008 GB/s100%——
R4 分段1.1203 ms958.5 GB/s95.1%距下限 +5.2%524,288
R5 粗化1.1211 ms957.8 GB/s95.0%0.999×131,072
R6 shuffle1.1212 ms957.7 GB/s95.0%1.000×131,072
R5 @ BLOCK=10241.1224 ms956.7 GB/s94.9%0.999×32,768

R4 一步就到 95.1%,后面三行一个百分点都没再动。 1.1203 / 1.1211 / 1.1212 ms 三个数的差别在噪声范围内。

二、五条逐条判决↑

五条逐条判决 —— 押中四条
#预测标准实测判决
①R1→R2 有明显加速净 > 2×净 4.40×,原始口径 1.74×押中 数字脆弱
②R2→R3 再快一截净 > 1.5×0.71× —— R3 反而慢没押中
③R3→R4 数量级跳变每元素 > 50×292×(净口径也有 82×)押中 远超标准
④R4→R5 收益很小< 1.2×0.999×押中 不是"小",是零
⑤R5→R6 收益更小< 1.1×1.000×押中 同样是零

第 ③ 条是核心,它押中得毫无悬念。 注意:这一条必须按每元素耗时比。 实验 B 的 N 是实验 A 的 13 万倍,直接比总时间没有意义。 第 ④⑤ 条预测"收益很小",实测的收益不是"小", 是零。

"没收益"可以有三种原因,得排除掉后两种才算预测成立:

(a) 带宽真的满了,上面没空间。            ✓ 这就是答案。
    R4 达成率 95.1%,而 1008 GB/s 是理论峰值 —— R4 已经站在墙上了。

(b) 原子加本来就不是瓶颈,所以减少它没用。 ✓ 顺带也证实了。
    原子加次数 524,288 → 131,072 → 32,768,跨度 16 倍,
    耗时 1.1203 / 1.1211 / 1.1224 ms —— 纹丝不动。

(c) 测量噪声把收益盖住了。                ✗ 排除。
    实验 B 在毫秒量级、跑了 11 次取平均,三者最多相差 2.1 µs(0.19%)。

所以第 ④⑤ 条不只是押中了,而且是按预测时给的理由押中的。 对账要核对的正是这一点。

三、失手那条比押中的值钱↑

// N = 2048 时,全部数据只有 8 KB。
// 第一次读完就整个躺在 L1 里了 —— R2 那些"反复读全局",实际上一次 DRAM 都没碰。
// 于是 R3 省掉的那些全局访问,本来就是免费的。
// 而 R3 额外付出了:shared 的写 + 读、以及一次额外的 __syncthreads 协调。
// 净效果:持平到略负。

写第 ② 条预测时,我犯了 §1·一 警告过的错:拿书的指标当时间。 R3 的价值在 N=2048 时体现不出来。N 大到装不进 cache 时它才有用, 而那时已经必须用 R4 的分段结构了。

方法论教训:第 ① 条的 4.40× 也不可靠

净耗时只有 0.5–2.2 µs,空 kernel 本身就要 1.8 µs, 减掉之后的量级和计时分辨率同阶。 按原始耗时算只快 1.74×,没达到 2× 的标准。 定性结论(R1→R2 变快了)成立,具体倍数不成立。 下次做这类实验, 要把 N 加大到启动开销可以忽略,或者用 ncu 直接读 kernel 内部计数器。

意外两个计划外的发现↑

一、占用率(occupancy)打平↑

BLOCK = 1024  (每 SM 只放得下 1 个 block,1024/1536 = 66.7%)   1.1224 ms
BLOCK =  256  (100%)                                        1.1211 ms
                                                    差 0.1%

这条结论有前提,而且方向和 SGEMM 相反

只有当占用率不足导致延迟藏不住时,它才是问题。 归约是纯顺序读,66.7% 的 warp 已经能喂饱显存带宽, 再补上剩下的 33% 也没有带宽可用。 报告 01 §7 的 K5 把占用率从 75% 降到 33.3%, 反而快 1.66 倍。那边是"降低占用率换寄存器复用", 这边是"提高占用率什么也换不到"。方向相反,道理相同:看瓶颈在哪。

二、52 万次原子加没声音↑

开跑前的担心可以划掉:"524,288 次原子加全打在同一个地址上,会不会堵死?" 现代 GPU 的 atomicAdd 在 L2 里完成, 524,288 次分摊到 1.1 ms 里,耗时上看不出影响。

别误读 ptxas 的 "used 1 barriers"

它的意思是占用了 1 个 barrier 硬件资源,不是"执行了 1 次 __syncthreads()"。 R5 循环里的几次 __syncthreads() 共用同一个 barrier 资源, 所以 R5 和 R6 的这一行完全相同。 ptxas -v 看不出 __syncthreads() 次数的减少。

延伸推理栈里的位置与复现↑

一、归约出现在哪↑

SGEMM 是推理里最费时间的算子,归约是最频繁的算子。 Transformer 的每一层、每一个 token 都要跑好几次归约。

归约在推理栈里出现的地方
它出现在哪是什么形式的归约这一章的哪一课用得上
LayerNorm / RMSNorm每一行求和 + 求平方和一个 block 管一行,就是 R3 的结构;行长几千,一个 block 正好装得下
Softmax两次归约:先求 max,再求 exp 的和max 归约可复现,sum 归约不可复现
FlashAttention在线 softmax:边扫 KV 分块边维护 running max / sum这一章的直接延伸 —— 本质是"能增量合并的归约"
张量并行 allreduce跨 GPU 求和(NCCL ring / tree)同一棵树,换了一层硬件:lane → warp → block → GPU → 节点
采样 / top-k / top-pmax、排序、前缀和归约是前缀和的基础
量化的 scale每个 tensor / 每一行求 absmax把加法换成 max 的归约

二、和 SGEMM 两份报告的关系↑

报告 01/02(SGEMM)   算术强度 0.250 → 12.720,靠分块/粗化/向量化把复用做出来
本报告(归约)        算术强度 0.250 恒定,一步也挪不动

// 同一个优化,在两边的命运完全相反:
线程粗化   SGEMM K3→K4  3.359×       归约 R4→R5  0.999×
提高占用率 SGEMM K5      降到 33.3% 反而快  归约      66.7% 和 100% 打平

SGEMM 教你怎么把复用做出来,归约教你在没有复用可做时该看什么。 推理里一大半算子属于后者,它们都卡在带宽上。 所以"算一遍下限、量一次达成率"这个动作, 比任何单个优化技巧都值钱。

三、复现↑

nvcc -O3 -arch=sm_89 -lineinfo reduce_ch10.cu -o reduce_ch10

# 实验 A:单 block,N = 2048(先拿空 kernel 作启动开销基线)
./reduce_ch10 none 2048 1000
./reduce_ch10 r1   2048 1000
./reduce_ch10 r2   2048 1000
./reduce_ch10 r3   2048 1000

# 实验 B:整卡,N = 2²⁸
./reduce_ch10 r4 268435456 11
./reduce_ch10 r5 268435456 11
./reduce_ch10 r6 268435456 11
./reduce_ch10 r5 268435456 11 1024      # occupancy 对照

# 编译期体检 + 竞态检查
nvcc -O3 -arch=sm_89 -Xptxas -v -c reduce_ch10.cu 2>&1 | grep -A2 reduce_r
compute-sanitizer --tool racecheck ./reduce_ch10 r6 2048 1

原始数据一条没删: Results/Reduction/reduce_20260921.txt 是当天的原样终端输出。 本报告里每个数字都由构建脚本从它现场解析,没有一个是手抄的。 换一张卡,这里所有绝对数字都会变; 但"R4 之后达成率不再动"这个定性结论,在任何带宽受限的卡上都应该成立。

两项还没测

这一批没有测两项:小 N(2¹⁶)下 R5/R6 的对比,以及 cuobjdump -sass | grep SHFL 的条数。 所以"R6 编出了 SHFL 指令"目前只是推断。 报告 01 §8 当初对 float4 也是这样,那边后来用反汇编证实了, 这边还没有。