专题进阶 · 并行算法推荐总顺序 · 第 133 / 148 课

将矩阵乘法分成可复用的小块,理解边界块、缓存局部性和计算量不变。

先学会这些,再进入本课 矩阵乘法
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 并行算法

分块Tiling

把计算切成适合缓存的小块,在数据被移出前反复使用。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

将矩阵乘法分成可复用的小块,理解边界块、缓存局部性和计算量不变。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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,1C₀₀=1×7+2×9=25先累计前两项
共有维度尾块 p=2再加 3×11=33边界块只有一项
完整输出C₀₀=58,其余同理分块覆盖所有乘加

窄屏可左右滑动表格,阅读完整计算与理由。

输出仍为 [[58,64],[139,154]],与普通矩阵乘法一致。

04为什么这个方法成立

  1. 每个块内循环的索引落在其截断区间,块之间区间不重叠且覆盖全部维度。
  2. 因此每个 (i,p,j) 被访问一次,既不遗漏也不重复。
  3. 对固定输出 (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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

5×5 矩阵按 b=2 分块,每个方向几块?

需要一点提示

向上取整。

查看解析与答案

3 块,边界块长度为 1。

练习 2 · 边界与辨析

为何不能在每轮 pp 开始时清空 C 块?

需要一点提示

前一个共有维度块已经产生部分和。

查看解析与答案

会丢掉之前的贡献,只留下最后一个块的结果。

练习 3 · 变式与迁移

怎样验证分块实现?

需要一点提示

同时检查数值与不整除边界。

查看解析与答案

用普通矩阵乘法作参考,比较多种矩形形状和块大小,再单独测性能。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

NVIDIA · CUDA Best Practices Guide

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。