上一节看到了重复搬运。现在设想我们可以决定一次先完成哪个格子:是把一个结果彻底算完,还是趁一个输入刚被取来,让它参与更多结果?
预计用时:45 分钟。本节的可运行实现是 assets/math-lab/algorithms.js 中的 multiply,可在 数据的旅程 对照。
i、j、k 分别标记结果的行、列和一次乘积的位置。逐格实现的核心如下,属于源码节选:
for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
let sum = 0;
for (let k = 0; k < n; k++) sum += a[i * n + k] * b[k * n + j];
c[i * n + j] = sum;
}
它先固定结果格子,沿 A 的行与 B 的列前进。局部变量保存一个部分和,结构直接,C 的写入次数也少。但 B 的访问会跨过一整行。
把内外两层的 j、k 对换后,固定一个 a[i*n+k],让它更新 C 的一整行:
for (let i = 0; i < n; i++) for (let k = 0; k < n; k++) {
const aik = a[i * n + k];
for (let j = 0; j < n; j++) c[i * n + j] += aik * b[k * n + j];
}
内层对 B、C 的访问变得连续。C 必须先清零,因为我们一直向已有位置累加;Float64Array 的新数据区满足这里的初始化需要。若复用旧缓冲区而忘记清零,结果会混入前一次计算。
整行也可能很大。分块把 i、j、k 的范围先拆成小区间,在一组小区间中完成可复用的工作,再换到下一组。代码中因此多了 ii、jj、kk 三层块循环。
这段程序里的块只是访问范围,未另行复制成紧凑的打包缓冲。成熟矩阵库还可能采用专门的打包布局、向量指令与微内核;不要把本实验的三种 JavaScript 循环等同于它们的全部实现。
对于边长 5、块边长 2,范围是 [0,2)、[2,4)、[4,5)。最后一块不完整,因此循环上限写成 Math.min(块起点 + tile, n)。多出来的边界代码维护的是结果覆盖范围。
块太大,想复用的内容可能留不住;块太小,循环与边界判断增加,工作组织也可能不利于实际编译器。真实最优点取决于输入、硬件、内核与测量范围。
先在模型里对块边长 2、4、8 分别预测,再观察装入次数。如果某个结果与“块越小越好”冲突,请保留。我们正在寻找条件,不是在给一个固定参数取一个“最优”的名字。
三个实现的 n³ 乘法增长阶相同。大 O 描述规模增大时的增长方式,不能单独给出同一规模下的毫秒数;这次差别主要来自被简化的成本项与实现细节。
在副本中调用真实 multiply,比较 n=1、5、17、tile=1、2、4、32 的结果。教材自测已覆盖这些不能整除的边界。你应解释为什么 tile 大于 n 仍能完成一次完整计算。
选做:给 multiplyRows 增加分块访问。保持输入与输出行范围约定,返回值只包含 [start,end) 对应的结果。验收需要覆盖首行、末行、空行段与分块尾部;用独立整数参考逐项比较,再讨论性能。
当前可停在“每次只改变一种访问安排,并核对覆盖与结果”。接下来学习 怎样相信一次快慢比较。