缓存无关模型

理想缓存 ​

它沿用外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。的缓存 (M) 与块 (B)，再假设全相联和最优替换；算法代码不知道 (M,B)，分析仍以二者计 cache misses。Tall-cache 如 (M=\Omega(B^2)) 是某些证明的额外条件。

递归矩阵转置是该模型上的一种构造策略，而不是模型定义的一部分：它不断把矩形切半；当子问题首次装入任一级缓存后，在内部复用连续块，因而同一代码适配多层尺度。这是“无参数但有局部性证明”，不是不考虑缓存。

失败边界 ​

任意递归并不自动最优：糟糕布局仍会逐元素跨块。现实组相联、TLB、预取和写回偏离 ideal cache，模型结论是传输上界而非精确计时。递归栈与基础阈值也有成本。

Cache-aware 算法显式按 $B,M$ 分块；cache-oblivious 只是不在代码中使用参数，两者都必须给复杂度。

最优替换是假想分析器，不是算法知道未来。Cache-oblivious 证明若依 ideal-cache 的包含性质，可逐层分析多级缓存；现实 conflict miss 仍可能改变常数。数据布局与递归访问顺序必须相配，仅有其中一项不保证局部性。

递归转置的状态演化 ​

对 $m\times n$ 子矩形，沿较长维对半切，递归到单元后交换。递归树某层首次出现能装入 $M$ 的子矩形；从该层向下，块一旦读入便完成所有局部访问，子问题仅付其连续覆盖块数。所有叶合计 $O(1+mn/B)$ misses。

朴素行主序矩阵按列扫描时，相邻访问相距整行，若行长大于缓存，每元素都可能 miss。二者 CPU 操作同为 $\mathrm{\Theta }(mn)$，cache complexity 却不同。

Ideal-cache 假设的作用 ​

全相联与最优替换保证只要工作集不超过 $M$ 就能驻留；tall-cache $M=\mathrm{\Omega }(B^2)$ 让二维基础块同时有足够行列。证明若用这些条件必须列出，不能把它们解释成实际硬件自动满足。

Cache-aware blocking 直接选 tile 边长约 $\sqrt{M}$；cache-oblivious 递归在所有尺度隐式产生 tiles。后者不是 cache-unaware：若递归布局与访问顺序不匹配，照样可能产生冲突和 TLB 开销。

多级和失败边界 ​

Ideal-cache 的包含/最优性可让两级分析逐级应用到多层，但现实 set associativity 会产生 conflict misses。基础阈值、递归栈和并行 false sharing 也不在最简模型里，应作为实现边界而非否定渐近结论。

参考资料

• Frigo et al., “Cache-Oblivious Algorithms,” FOCS 1999.
• Harald Prokop, Cache-Oblivious Algorithms, MIT thesis, 1999.