跳到主要内容
CMU 15-779 学习专题
技术

CMU 15-779 学习记录 07:矩阵分块、数据复用与树形归约

用 CPU 模型统计矩阵分块的输入读取次数,再比较串行求和和树形归约的依赖深度,记录补零、同步与浮点加法顺序的边界。

矩阵积木在共享托盘中复用,旁边的小珠沿树形管道逐层合并的浅色手绘插画
文章目录

GPU Architecture & CUDA Programming 的个人配套实验。首次记录用 CPU 模型检查数据复用与依赖深度;后续补入单卡 GPU 原生 CUDA 矩阵验证,以及 Triton 两阶段归约和矩阵乘法实测。

上一节解决线程如何找到自己的元素。这次沿着原课 GPU/CUDA 幻灯片的矩阵乘法与归约部分,观察两件事:多个输出怎样共用输入,以及求和怎样缩短依赖链。

对应脚本为 26_matmul_tiling.py、27_tree_reduction.py,原始结果保存在随附的实验归档中。脚本编号是个人练习编号,不对应官方作业。

历史 CPU 代码版本 · 下载代码与结果 ZIP

相邻输出会反复读取同一份输入#

矩阵乘法中,一个输出元素是:

Cij=∑k=0K−1AikBkj.C_{ij}=\sum_{k=0}^{K-1}A_{ik}B_{kj}.

如果每个输出独立从输入矩阵取数,计算 C[i, j] 和 C[i, j+1] 时,都会读同一行 A[i, :]。共享内存分块先把一小块 A 和 B 加载进来,再让同一 block 中的多个输出使用它们。

CPU 模型把这个过程分成加载、计算、写回三个阶段,并在实际执行的循环中累计读取次数。它统计的是算法层面的 A/B 标量读取,不包含 C 写回、缓存命中、合并访存或真实 DRAM 事务。

对两个 8×8 矩阵,原始结果如下:

计算方式输入读取写入乘加
朴素方式102464512
分块 T=1102464512
分块 T=251264512
分块 T=425664512
分块 T=812864512

各配置的输出与 PyTorch 对照完全一致,每个有效输出也只写入一次。这里的输入采用可精确表示的二进制分数,不能把这次完全一致推广成所有浮点矩阵都逐位相同。

当方阵边长 N 能被 T 整除时,输出块有 (N/T)² 个,每个输出块沿 K 方向加载 N/T 轮,每轮读取两块 T² 个元素。因此:

输入读取数=(NT)2NT 2T2=2N3T.\text{输入读取数}=\left(\frac{N}{T}\right)^2\frac{N}{T}\,2T^2=\frac{2N^3}{T}.

这解释了表里的读取变化。它没有给出 GPU 加速比:同步、缓存、共享内存用量和占用率还会影响真实运行时间。

非整除尺寸不能只套方阵公式#

另一组原始结果使用 A[3,5] @ B[5,7],T=4。输出是 3×7,但模型启动两个 4×4 输出块,最后的 K 分块也不完整。

模型对越界加载补零,只写有效输出,实测计数为:

指标朴素方式分块方式
A/B 输入读取21065
输出写入2121
执行的乘加105256

分块模型的 256 次乘加包含补零位置和越界输出线程所做的计算;有效结果需要的乘加仍是 105 次。模型另外记录了 63 次共享槽位补零。读取减少的同时,边缘块可能引入额外计算。

附带的 CUDA 文件使用相同的阶段划分:所有线程协作加载,__syncthreads() 后使用共享块;用完再同步,下一轮才能覆盖它。边界线程不能因为不写 C 就提前离开整个同步流程。NVIDIA 的共享内存说明可作为对照。

CPU 循环按阶段执行,验证不了真实 GPU 的竞争和同步安全。首次记录中的 cuda/26_matmul_tiling.cu 仅为未编译、未执行的参考源码;本次补入了下文的 GPU 续验。

树形归约缩短的是依赖链#

接下来把问题从数据复用换成求和。27_tree_reduction.py 保存了这棵小树:

text
3  1  7  0  4  1  6  3
 4     7     5     9
    11          14
          25

8 个数一共做 7 次加法。串行累加需要依次等待前一个和;树形结构中,同层的独立加法可以并行,依赖深度只有 3。

默认的 257 个数得到:

指标串行结构树形结构
加法总数256256
依赖深度2569
最终和-3.75-3.75

脚本还按每组 32 个输入分阶段求和:先得到 9 个局部和,再把 9 个局部和合成 1 个结果,总加法数仍为 256。这个结构可以帮助理解分阶段归约,但本次普通 CPU 循环没有并行执行,依赖深度不是计时结果。

加法顺序会改变浮点结果#

同一份 JSON 还保留了一个不能忽略的反例:

text
输入:[1e16, 1.0, -1e16, 1.0]
串行求和:1.0
树形求和:0.0
math.fsum:2.0

有限精度下,大数和小数相加会丢失信息。改变加法顺序,结果可能不同;归约正确性检查需要结合数据类型、数值尺度和容差,而不能要求任意浮点输入都逐位等于串行求和。

复现与证据#

整理时从冻结副本复跑了两份矩阵报告和归约报告,数值与计数均复现。矩阵测试有 7 项,覆盖 500 组小尺寸配置、随机输入、补零、计数与非法参数;归约测试还检查了多种长度、块大小及上述浮点反例。完整代码仓库中的矩阵、归约、Attention 测试共 21 项,整理时全部通过。

ZIP 包含本篇两份脚本、CUDA 矩阵源码、三份原始 JSON、原始矩阵测试输出、矩阵测试和依赖说明。复跑结果另存:

bash
python3.11 -m venv .venv
.venv/bin/python -m pip install -r requirements.txt
.venv/bin/python 26_matmul_tiling.py --output results/matmul-rerun.json
.venv/bin/python 26_matmul_tiling.py --m 3 --k 5 --n 7 --tile 4 \
  --output results/rectangular-rerun.json
.venv/bin/python 27_tree_reduction.py --output results/reduction-rerun.json
.venv/bin/python -m unittest discover -s tests -v

本篇完成的是数据复用、计数和归约依赖结构的 CPU 验证。该 CPU 快照没有 GPU 时间、实际显存流量或 CUDA 内存/同步检查。后续 GPU 实测另列如下;原课寄存器分块没有新增独立实验结果。

历史 CPU GitHub 代码 · 下载代码与结果 ZIP

后续补充:原生 CUDA 与 Triton 实测#

学习聊天在单卡 CUDA 环境实际编译、运行了 cuda/26_matmul_tiling.cu,同时保留了前文 CPU 报告。设备报告 RTX 4080 SUPER、compute capability 8.9,CUDA Toolkit 12.8;GPU Python 环境为 Python 3.12.3、PyTorch 2.7.0+cu128、Triton 3.3.0。

原生程序的 13 组配置包含非方阵、非整除边缘、K=0 和 T=1/2/4/8/16。两组空输出无需启动,其余配置的 naive/tiled 两个实现均通过逐元素对照。memcheck、synccheck 均报告 0 errors,racecheck 报告 0 hazards(0 errors、0 warnings),命令退出码均为 0。这比 CPU 按阶段执行的循环多了一份真实设备检查,但只覆盖给定案例与工具范围。

原生矩阵程序没有计时,也没有测量显存事务。前文的 2N³/T 仍只是模型读取计数,不能换成真实带宽节省比例。

两阶段归约:顺序变化留下数值误差#

38 号脚本先让每个 Triton program 归约一块,再用第二个 kernel 归约局部和。float32 输入长度覆盖 0、1、17、257、1048576,以 GPU 上 float64 求和作为正确性参考,均通过 atol=1e-3, rtol=3e-5。

N=1048576 时,最大绝对误差为 0.0002373360823。CUDA event 中位数如下:

调用中位数(ms)
Triton 两阶段 float32 sum0.128512
PyTorch float32 sum0.022426

float64 结果用于误差对照,表中 PyTorch 计时则是 float32 sum。这份教学实现慢于库函数,缩短依赖结构本身并不保证更好的实现性能。

分块矩阵乘法:保留慢于 PyTorch 的结果#

Triton 矩阵实现使用 float32 IEEE tl.dot,PyTorch 参考禁用 TF32。验证形状包括 1×1、97×65 @ 65×129、512 和 1024 阶方阵;分块配置为 (32,32,32) 和 (64,64,32),数值对照全部通过 atol=1e-3, rtol=1e-4。

1024 阶、(64,64,32) 配置的最大绝对误差为 0.0002212524414:

调用event 中位数(ms)
Triton 分块矩阵乘法0.125338
同组 PyTorch 矩阵乘法0.088678

这仍是一份较朴素的实现,没有据此完成参数调优或证明 Triton 自动加速。计时先 warmup 5 次,取 15 个样本的中位数;矩阵每个样本平均 5 次调用,归约为 10 次。区间排除初次 JIT 与主机/设备传输,但可能包含 Python 提交/分配造成的 GPU 空闲,不是单 kernel 的隔离测量。

最新 ZIP 与记录 06共享,复跑命令及独立 GPU 依赖见 GPU_REPRODUCE.md。发布端核对了哈希、24 组计时的逐次样本和原生命令输出,没有在 Mac 上复跑 GPU;原 CPU ZIP 保留其原始版本。

最新 GPU 代码版本 · 下载 GPU 代码与原始结果 ZIP

Series

CMU 15-779

  1. 01 CMU 15-779 学习记录 01:PyTorch 自动求导与线性回归
  2. 02 CMU 15-779 学习记录 02:nn.Linear、张量形状与 ReLU
  3. 03 CMU 15-779 学习记录 03:DataLoader、模型保存与批量推理
  4. 04 CMU 15-779 学习记录 04:多输出线性层、ReLU 与绝对值网络
  5. 05 CMU 15-779 学习记录 05:Profiler、算子调用与批量推理
  6. 06 CMU 15-779 学习记录 06:CUDA 线程索引与边界检查
  7. 07 CMU 15-779 学习记录 07:矩阵分块、数据复用与树形归约
  8. 08 CMU 15-779 学习记录 08:分块 Attention、在线 Softmax 与 KV cache
  9. 09 CMU 15-779 学习记录 09:CPU 编译优化、合法重写与候选搜索
  10. 10 CMU 15-779 学习记录 10:加权梯度、状态分片与同步流水线
  11. 11 CMU 15-779 学习记录 11:分页 KV、连续批处理与推测采样
  12. 12 CMU 15-779 学习记录 12:LoRA 首步梯度、权重合并与均匀 4-bit 打包
  13. 13 CMU 15-779 学习记录 13:MoE 路由、稀疏分发与容量溢出
  14. 14 CMU 15-779 学习记录 14:KV 页大小、共享边界与 CPU 实现成本

评论

评论由 GitHub Discussions 驱动,使用 GitHub 账号登录即可留言。