缓存无关模型

缓存无关算法并非拒绝分块，而是让递归在许多尺度上同时产生局部块。分析者事后针对任意实际 $B,M$，在递归树中找到刚好装入缓存的子问题层；代码无需知道这一层在哪里，连续访问仍能把同一块中的数据充分复用。

失败边界 ​

任意递归并不自动最优：糟糕布局仍会逐元素跨块。现实组相联、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 也不在最简模型里，应作为实现边界而非否定渐近结论。

该模型允许用同一份递归布局或访问程序同时分析 L1、末级缓存和外存层级。缓存无关搜索树公理库缓存无关搜索树cache-oblivious search tree · cache-oblivious B-tree在程序不知道块大小与缓存容量时，通过递归布局使搜索在各级存储上同时获得对数块传输界。、van Emde Boas 布局公理库van Emde Boas 布局van Emde Boas layout · vEB layout递归切分树高并连续摆放上下子树，使根叶路径对未知块大小保持局部性。与递归矩阵算法由此共享“代码无参数、界仍含参数”的接口；若某项保证还依赖 tall-cache、连续布局或最优替换，应用结论必须把这些条件一并带上。