分块优化

概念

分块优化（Blocking / Tiling）将大矩阵分成能完全放入缓存的小块，对每个块单独计算，最大化。

核心条件

对于矩阵乘法 C = A × B 的分块优化：

3B² < C

其中：

B = 块大小（每个维度）
C = 缓存容量
3B² = A/B/C 每个块各占 B²，共 3 个块

确保 A、B、C 的三个块能同时放入缓存。

不命中次数分析

无分块

每个 A[i][k] 被读取 n 次（内层 j 循环）
每个 B[k][j] 被读取 n 次 -总不命中次数 $\approx n^{3}$ （每次外层循环重新加载）

分块后

每个块被加载到缓存后，在块内计算时被完全复用 -总不命中次数 $\approx (n / B)^{3} \times (3 B^{2}) = 3 n^{3} / B$
其中 3B² 是每个块加载次数

推导概要

总不命中次数 = (块数 × 每块不命中次数)
= (n/B)³ × (A块B² + B块B² + C块B²)
= 3n³/B

本质原理

分块优化将全局的容量不命中转化为缓存容量范围内的命中：

分块前：外层循环导致反复加载和驱逐
分块后：块在计算期间留在缓存中

与 ikj 的关系

主要改善空间局部性
分块主要改善时间局部性
两者可以结合使用

相关笔记：

链接到

上一个知识点：6.19 矩阵乘法优化
下一个知识点：无（本章最后一个知识点）