考研笔记

Cache 中主存块的替换算法

只有当目标位置不止一个时才谈得上”替换”。所以第一句话必须是：直接映射不需要替换算法（见 3.5.3），全相联在全部行里挑，组相联在组内 行里挑。

四种算法本身在 OS 3.2.4 页面置换里已经出现过一遍，规则完全相同。这一节真正值得花时间的是它们在硬件里怎么实现——同一个 LRU，在 Cache 里、在操作系统里、在一道算法题里，最优实现完全不同。这个差别本身就是一个考点，也是理解”硬件和软件的成本模型不一样”的最好例子。

机制

四种算法

随机算法 RAND：随机挑一行。实现最简单，完全不考虑局部性，命中率不稳定。

先进先出 FIFO：淘汰最先调入的那一行。实现简单（一个指针轮转即可），但”最先调入”与”最不常用”没有关系——一个从头用到尾的块会被无辜淘汰。FIFO 会出现 Belady 异常。

近期最少使用 LRU：淘汰最久没有被访问的那一行。

  • 依据的正是时间局部性，因此命中率最高、最常考
  • 是栈算法，不会出现 Belady 异常
  • 硬件实现有代价，见下

最不经常使用 LFU：淘汰访问次数最少的那一行。

  • 依据的是访问频率，不是时间
  • 缺陷明显：早期频繁使用、后来不再使用的块会长期赖着不走（计数值已经很高）
  • 实际很少单独使用

边界辨析：LRU 和 LFU 的判据一个是"多久没用"，一个是"用过几次"

这两个名字太像，是这一节唯一的记忆坑。 LRU（Least Recently Used）看的是”最后一次访问在多久以前”——时间维度。 LFU（Least Frequently Used）看的是”总共被访问过多少次”——频率维度。 一个刚刚被访问过 1 次的块，在 LRU 下最安全，在 LFU 下最危险。

Belady 异常

给 FIFO 增加行数，命中率反而可能下降。 这个反直觉的现象叫 Belady 异常。

LRU、LFU、OPT 都不会出现，因为它们是栈算法：容量为 时驻留的块集合，永远是容量为 时驻留集合的子集，所以容量增大不可能把原本会命中的访问变成缺失。

FIFO 不满足这个包含关系，因此可能出现异常。这一条与 OS 3.2.4完全一致，两科考的是同一件事。

LRU 的硬件实现

计数器法：给组内每一行配一个计数器，位数 （ 为路数）。

  • 命中某行时：该行计数器清 0，所有比它小的计数器
  • 缺失需替换时：淘汰计数值最大的那一行
  • 4 路组相联只需每行 2 位，一组共 8 位

比较对法（矩阵法）：用触发器记录每一对行的先后关系， 路需要 个触发器。4 路只需 6 个。

两种实现的共同点：所需的位数随路数增长，这就是相联度不能太高的又一个理由——它同时增加比较器和替换控制位。

疑问点：LRU 用计数器维护效率太低，用队列（哈希表 + 双向链表）实现不是更好

这个判断在软件里完全正确，在硬件里恰好相反——两边用的是不同的成本模型。

先确认对计数器法的理解：是的，淘汰的就是计数值最大、也就是最久没有被访问的那一行。 也确认队列方案：命中就把该项拉到队首、未满就从队首插入、要淘汰就删队尾——这正是 LRU 的标准软件实现（哈希表 + 双向链表），每步 ，是那道经典算法题的标准答案。

关键在于”+1 太慢”这个判断的适用范围：

软件（一段程序）硬件（Cache 控制器）
成本单位指令条数 / 访存次数门电路面积 / 关键路径延迟
” 个计数器全部 +1”要循环 次， 个独立寄存器在同一个时钟沿并行完成，，一个周期
”双向链表移动节点”改几个指针，，很便宜需要指针存储、间接寻址、多拍读改写，很贵

硬件里没有”循环”，只有并行的组合逻辑。 个计数器是 套彼此独立的加法电路，它们在同一个时钟沿同时更新——这不是把软件里的 for 循环搬进硬件，而是把它彻底展开成并行电路。代价是面积： 套计数器和比较网络的面积随 增长，又一次是”面积换时间”。 反过来，硬件里没有便宜的”指针跳转”：链表节点要占存储、要多拍访问、要串行地追指针，在一个必须一拍出结果的关键路径上完全不可行。

所以结论是：同一个算法，在不同的成本模型下有不同的最优实现。 这个观察还有第三种情形—— 操作系统里的页面置换同样想用 LRU，但软件无法在每次访存时都去更新链表（访存由硬件完成，操作系统根本插不进去），于是退而用硬件提供的访问位 + CLOCK 算法做近似，见 OS 3.2.4。 三个场合、同一个 LRU、三种实现：Cache 用计数器/矩阵（硬件全并行）、算法题用哈希加双链表（软件 ）、操作系统用 CLOCK 近似（软件无法介入每次访问）。判断哪种实现好，先问”这里什么是贵的”。

抖动

若程序的访问模式恰好与映射方式冲突（例如步长使得连续访问的块总是映射到同一组），Cache 会在少数几个块之间反复替换，命中率极低。这种现象称为抖动（颠簸）。

提高相联度是缓解抖动的主要手段——这也是纯直接映射的 Cache 早已不用的原因。

边界

替换算法只在缺失且无空闲行时才启动。 有空闲行（有效位为 0）时直接装入，不需要淘汰任何块。“每次缺失都要执行替换算法”是错的。

替换发生在组内，不是全 Cache。 组相联的替换范围是该组的 行，与其他组无关。这一条在做 trace 时最容易搞错。

LRU 的命中率不一定高于 FIFO。 在特定访问序列下 FIFO 可以更好，LRU 只是平均而言更好。绝对最优的是 OPT（淘汰将来最晚被用到的），但它需要预知未来，不可实现，只作为衡量其他算法的上界。

LRU 不会出现 Belady 异常，FIFO 会。 这是判断题的固定问法。

Cache 的替换与 OS 的页面置换规则相同、实现不同。 规则可以互相套用，实现细节不能。

对照速查

算法判据Belady 异常硬件代价命中率
RAND随机—最低最差
FIFO最先调入会出现低一般
LRU最久未访问不会中~高最好（可实现的）
LFU访问次数最少不会中一般
OPT将来最晚使用不会不可实现理论上界
LRU 实现场合代价
计数器 / 矩阵法Cache 硬件面积（每行 位或 个触发器）
哈希 + 双向链表软件，指针存储
CLOCK（近似 LRU）操作系统页置换只需访问位

考点

  • 直接映射不需要替换算法；替换只在组内进行
  • 有空闲行时不启动替换算法
  • LRU 看时间，LFU 看次数
  • FIFO 会出现 Belady 异常，LRU/LFU/OPT 不会（栈算法）
  • LRU 硬件用计数器法或矩阵法，位数随路数增长
  • “计数器 +1 慢”只在软件成本模型下成立，硬件里 个计数器并行更新
  • OPT 不可实现，只作上界
  • 抖动靠提高相联度缓解

链接

反向链接