缓存无关模型

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

递归转置的状态演化 ​

设输入是按行存储的 $m\times n$ 矩阵 $A$，输出写入另一块按行存储的 $n\times m$ 矩阵 $D$。算法沿输入子矩形的较长维切半，同时切分对应的输出区域；递归到单个元素时执行 $D[j,i]\leftarrow A[i,j]$。整个过程完成 $\mathrm{\Theta }(mn)$ 次元素处理。

在满足 tall-cache 条件 $M=\mathrm{\Omega }(B^2)$ 的理想缓存中，递归会到达源、目标子矩形连同边界块都能装入缓存的尺度。之后的局部访问复用这些块。对子矩形的行边界开销与递归层数一起计数，可得 $O(1+mn/B)$ 次缓存缺失，与读写全部元素的块数量同阶。

相比之下，朴素逐列读取行主序矩阵时，相邻访问相隔一整行；矩阵足够大时，每次读取都可能落到已经被逐出的块。两种方法的 CPU 工作量同为 $\mathrm{\Theta }(mn)$，数据传输量却可以相差一个块因子。

与显式分块的区别 ​

Cache-aware 分块会根据 $M,B$ 选择块尺寸，例如把方形 tile 的边长取为适当常数倍的 $\sqrt{M}$，使输入、输出和临时空间一起装入缓存。Cache-oblivious 递归则隐式产生多个尺度的块，同一份代码可以针对不同缓存参数分别分析。两种策略都依赖数据布局与访问顺序之间的配合。

模型与硬件 ​

全相联允许块放入任意缓存位置，最优替换则按整个访问序列选择最有利的淘汰策略；这是分析成本的模型假设。实际硬件的组相联理路组相联缓存Set-associative cache · Cache ways and sets在固定容量下区分组数与路数，逐组匹配tag，并比较同一程序轨迹在两种配置中的命中。会把块限制在特定组内，可能产生冲突缺失；实际缺失分类理路局部性与缓存缺失分类Cache locality · Compulsory capacity and conflict misses · 3C model用明确的影子缓存区分首次、容量与冲突缺失，并通过改变对象布局而非算法验证局部性。需要声明对照缓存和替换策略。TLB、预取、脏块写回理路缓存写策略与脏块回写Write-back and write-through · Write allocation policy · Dirty cache line分开写命中传播与写缺失分配两条策略轴，追踪脏块逐出和终末flush，区分回写与持久化。、递归基础阈值和并行伪共享也会影响运行时间。理想缓存界刻画数据传输的结构，具体性能还取决于这些实现因素。

对满足相应正则条件的缓存无关算法，两级传输界可以推广到多级存储分析。每一级代入自己的容量和块大小，便可比较同一访问程序在不同层级的代价。

该模型允许用同一份递归布局或访问程序同时分析 L1、末级缓存和外存层级。缓存无关搜索树理路缓存无关搜索树cache-oblivious search tree在程序不知道块大小与缓存容量时，通过递归布局使搜索在各级存储上同时获得对数块传输界。、van Emde Boas 布局理路van Emde Boas 布局van Emde Boas layout · vEB layout递归切分树高并连续摆放上下子树，使根叶路径对未知块大小保持局部性。与递归矩阵算法由此共享“代码无参数、界仍含参数”的接口，相应复杂度界使用各自证明中的容量、布局与替换假设。