矩阵乘法优化
问题描述
矩阵乘法 C = A × B，三层嵌套循环。不同的循环排序导致完全不同的缓存性能。
六种循环顺序
按不命中率从优到劣分为三个梯队：
第一梯队（不命中率 ）
$kij: for k, for i, for j → C[i][j] += A[i][k] * B[k][j]$
$ikj: for i, for k, for j → C[i][j] += A[i][k] * B[k][j]$
A[i][k]提取到寄存器，不重复访问- 内层循环 j 遍历 C 和 B 的行
- 空间局部性最佳
第二梯队（不命中率 ）
$ijk: for i, for j, for k → C[i][j] += A[i][k] * B[k][j]$
$jik: for j, for i, for k → C[i][j] += A[i][k] * B[k][j]$
第三梯队（不命中率 ）
$jki: for j, for k, for i → C[i][j] += A[i][k] * B[k][j]$
$kji: for k, for j, for i → C[i][j] += A[i][k] * B[k][j]$
关键优化：ikj 模式
在 ikj 模式中：
A[i][k]被提取到寄存器（标量替代），完全消除对 A 的重复读取- 内层 j 循环对 C 和 B 进行步长为 1 的遍历
- 充分利用
根本原因
C 语言中数组是行优先（Row-major）存储，内层循环沿 j 遍历是最自然的。