01先把问题说具体
矩阵太大时,相同数据可能从内存反复读取。如何让一小块数据在离开缓存前多做几次计算?
02一步步得到方法
以输出小块为单位思考
C 的一个 b×b 块需要累加 A 的若干 b×b 块与 B 的对应块之积。沿共有维度遍历块,每一对块都贡献到同一个 C 块,直到所有 k 块完成。
分块不改变 Cᵢⱼ=ΣₚAᵢₚBₚⱼ 的数学定义,只改变循环与访存次序。局部数据能在缓存中复用时,访问更慢层级内存的次数可能降低。
六个循环也不意味着六次方复杂度
外三层枚举块,内三层枚举块中的元素。每个合法的三元组 (i,p,j) 仍然只执行一次乘加,所以总工作仍为 O(mkn)。
矩阵维度不一定是块大小的整数倍。最后的边界块必须用 min 截断,不能跳过尾部,也不能访问越界。
块大小是一种资源选择
块太小会增加循环与调度开销,太大可能装不进目标缓存。理想大小受元素类型、缓存容量、关联性和其他活跃数据影响,不存在一份跨所有硬件通用的数值。
下面的 Python 实现用于检验索引与结果。Python 对象开销及解释器循环使它不适合证明缓存优化的速度;真实性能应在目标语言、布局与硬件上测量。
03把一个小例子完全算清楚
A 为 2×3,B 为 3×2,块大小 b=2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 共有维度第一块 p=0,1 | C₀₀=1×7+2×9=25 | 先累计前两项 |
| 共有维度尾块 p=2 | 再加 3×11=33 | 边界块只有一项 |
| 完整输出 | C₀₀=58,其余同理 | 分块覆盖所有乘加 |
窄屏可左右滑动表格,阅读完整计算与理由。
输出仍为 [[58,64],[139,154]],与普通矩阵乘法一致。
04为什么这个方法成立
- 每个块内循环的索引落在其截断区间,块之间区间不重叠且覆盖全部维度。
- 因此每个 (i,p,j) 被访问一次,既不遗漏也不重复。
- 对固定输出 (i,j),所有 p 的贡献都累积到同一 Cᵢⱼ,得到原矩阵乘法定义。
05把推导翻译成代码
Python · 分块矩阵乘法的正确性参考
def tiled_matmul(A,B,block=2):
if block<1 or not A or not B or not A[0] or not B[0]:
raise ValueError("invalid input")
m,k,n = len(A),len(A[0]),len(B[0])
if len(B)!=k or any(len(row)!=k for row in A) or any(len(row)!=n for row in B):
raise ValueError("shape mismatch")
C = [[0]*n for _ in range(m)]
for ii in range(0,m,block):
for jj in range(0,n,block):
for pp in range(0,k,block):
for i in range(ii,min(ii+block,m)):
for p in range(pp,min(pp+block,k)):
for j in range(jj,min(jj+block,n)):
C[i][j] += A[i][p]*B[p][j]
return C
print(tiled_matmul([[1,2,3],[4,5,6]],[[7,8],[9,10],[11,12]]))逐个理解关键决定
for pp in range(0,k,block)- 同一个 C 块沿共有维度持续累加,不应每次把 C 块清零。
min(pp+block,k)- 正确处理末尾不足一个完整块的维度。
for j- 当前内层连续访问 B 的一行和 C 的一行,便于理解行布局下的局部性。
06时间、空间与实现范围
乘加工作 O(mkn),输出空间 O(mn),本实现没有显式复制缓存块。
理想 b×b 显式工作块常需 O(b²) 快速存储,但真正内存流量取决于缓存行为和循环安排。
07改变条件,检查哪里会出错
分块后算术量自动变少
改变的是数据复用与组织,经典乘加次数不变。
大块一定更快
超出快速存储容量会降低复用,需实测而非凭块大小推断。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
5×5 矩阵按 b=2 分块,每个方向几块?
需要一点提示
向上取整。
查看解析与答案
3 块,边界块长度为 1。
为何不能在每轮 pp 开始时清空 C 块?
需要一点提示
前一个共有维度块已经产生部分和。
查看解析与答案
会丢掉之前的贡献,只留下最后一个块的结果。
怎样验证分块实现?
需要一点提示
同时检查数值与不整除边界。
查看解析与答案
用普通矩阵乘法作参考,比较多种矩形形状和块大小,再单独测性能。