局部性与缓存缺失分类

形式陈述

时间局部性指近期访问的数据有机会再次使用；空间局部性指邻近地址的数据有机会被一起使用。它们是访问轨迹的结构特征，是否转化为命中还要结合块大小、容量、映射和替换规则。

本页固定单核、无预取、无一致性失效的3C诊断：为实际缓存同步维护同容量、同块大小的全相联LRU影子缓存，影子处理每一次访问。对实际发生的缺失，依次分类：从未访问过该块为首次（compulsory）；否则影子也缺失为容量（capacity）；否则为冲突（conflict）。

这是一种明示参考策略的操作性分类。存在一致性失效、主动flush或不同替换策略时，不能把所有额外缺失都硬塞进“容量不足”的直觉解释。分类中的“容量”也不是某次访问永远不可能被任何策略命中的证明。

直觉

“以前看过吗”排除冷启动，“同样容量但没有组限制能留下它吗”区分本次冲突与参考容量压力。影子缓存像一个对照实验，帮助定位位置限制的影响。

空间邻近只有在真的用到邻近数据时才有价值。大块把更多邻居一起带来，也消耗更多容量；若每块只用一个word，剩下的搬运可能全是浪费。

例子与边界

四行直接映射、B=8，读取地址序列 00,20,00,20。前两次是首次缺失，后两次实际缓存缺失而四行全相联影子命中，因此是冲突缺失。把第二对象整体移至0x28，变成 00,28,00,28，得到首次、首次、命中、命中。

逻辑程序仍交替读取两个不同对象，算法步骤没有减少。改变布局修复的是组碰撞，不能把其收益记成降低了算法渐近操作数。

仍取B=8，四字节word顺序读 00,04,08,0c。在空缓存且无其他访问时，每块的第一次访问缺失，第二个word命中，共两次缺失。若改读 00,08,10,18，每次落到新块，共四次缺失；两轨迹都读取四个word，数据传输不同。

共同任务访问的块基址依次为 00,00,20,00,40,20,00,08,28,08,40。前五种不同块各自第一次访问产生5个首次缺失。最后重新读0x40时，四块全相联LRU影子也已逐出了它，因此该次是容量缺失。

按本页参考规则，直接映射的10个缺失分为5首次、4冲突、1容量；两路缓存的8个缺失分为5首次、2冲突、1容量。实际命中不再强行分配3C标签，即使某个参考缓存可能有不同结果。

推论与应用

缓存无关算法通过多尺度递归组织数据复用，但其理想缓存分析没有替本页实际映射免除冲突。布局、分块与工作集分析要保留模型层次。

多核中由其他核心写权限引起的失效，需要另查缓存一致性；其中对不同变量的同块争用是伪共享。把这些缺失都归为“访问顺序差”，会把优化方向带偏。

参考资料

Mark D. Hill and Alan Jay Smith, “Evaluating Associativity in CPU Caches,” IEEE Transactions on Computers 38(12), 1989, pp. 1612–1630；缺失分类与相联度分析背景。
David A. Patterson and John L. Hennessy, Computer Organization and Design RISC-V Edition, 2nd ed., 2021，Ch. 5。本文特意固定全相联LRU影子，避免不同分类口径混算。