CPU 缓存替换算法

组满了,淘汰谁?

在《CPU cache 原理》里讲到,现代 CPU 缓存普遍采用组相联结构:一个内存块先按 Index 定位到某个组,再在该组的若干路(way)里选一个位置存放。L1 常是 8 路,L3 可能 16 路甚至更多。

那么问题来了:当一次访问 miss,需要把新的缓存行搬进来,而这一组的所有路都已经占满时,该把哪一路的数据踢出去?

这就是 缓存替换策略(Cache Replacement Policy) 要回答的问题。它直接决定缓存里"留什么、扔什么",选错了会把最常用的数据踢出去,导致接下来的访问连续 miss。

这一篇讲四种常见的替换算法:FIFO、LRU、树形 pLRU、QLRU,重点放在它们的实现原理、硬件开销和适用场景上。

替换策略要解决什么

替换策略的唯一目标是把最不可能再用到的数据踢出去,也就是让缓存命中率(miss rate 越低越好)尽量接近理论最优。

理论上的最优解叫 Belady 最优算法(OPT):淘汰"未来最久才会被访问"的那一行。但 OPT 需要预知未来,硬件做不到,只能作为上界来衡量其他算法的好坏。

所有实际算法都在做同一件事:用"过去的访问历史"去猜"未来最不可能用到谁",猜得越准,命中率越高。区别在于——用什么信息去猜、要花多少硬件代价去记这些信息。

而硬件代价是硬约束:替换策略的状态(记录访问历史的那些 bit)要跟每个组绑定,一组一份。L1 有几千个组,每个组多一个 bit,加起来就是一笔不小的硅面积和功耗。所以替换算法从来不是"越准越好",而是命中率与硬件开销的折中。

带着这个视角,看下面四个算法。

FIFO:最早进来的先出去

FIFO(First In First Out)的思路最直白:淘汰最早进入这一组的那一路,不看它之后有没有被频繁使用。

实现原理

硬件上常用一个 循环指针(round-robin) 近似实现:每组维护一个计数器,指向"下一个要淘汰"的路。

一组有 4 路 way[0..3],指针 ptr 初始指向 0

发生 miss 需要替换时:
1. 淘汰 way[ptr]
2. 把新缓存行写进 way[ptr]
3. ptr = (ptr + 1) % 4

命中时指针不动,只有发生替换时指针才往前走。所以每个组只需要 log2(路数) 个 bit 记指针,是所有算法里最便宜的。

优缺点

• 优点:实现最简单,硬件开销最小。
• 缺点:完全忽略访问频率。一个被反复访问的"热数据"如果恰好是组里最早进来的,一样会被无差别踢掉,下次访问又要 miss 再搬回来。它没有利用时间局部性。

适用场景

FIFO 在追求极低成本、且访问模式比较均匀的场景能用,但现代 CPU 的主流缓存几乎不用它做替换策略。它的价值更多是教学基线:理解它,才能理解 LRU 到底"多记了什么信息"。

LRU:淘汰最久没用的

LRU(Least Recently Used)利用时间局部性:一个数据最近被用过,短时间内很可能再用,所以要保留;淘汰最久没有被访问过的那一路。

直觉上它是最接近 OPT 的策略——OPT 淘汰"未来最久才用",LRU 淘汰"过去最久没用",二者在时间局部性强的负载下表现非常接近。

实现原理

LRU 要维护一个"最近访问顺序",知道每一路到底多久没被碰过。常见的硬件实现是给每路一个年龄计数器:

一组有 4 路 way[0..3],每路有一个 age 计数器

访问命中 way[i] 时:
  age[i] = 0              // 刚被访问,年龄归零
  其他所有路 age[j] += 1   // 没被访问的,年龄 +1

需要替换时:
  淘汰 age 最大的那一路   // 年龄最大 = 最久没用

这个实现直观,但它不是最优的:每路要 log2(路数) 个 bit,还要能比较大小。另一种实现是维护一个"谁比谁新"的引用矩阵(bit matrix),开销是 路数 × (路数-1) / 2 个 bit。

开销为什么会爆炸

LRU 的本质是要记住 N 路的完整先后顺序,信息论下界是 log2(N!) 个 bit:

而且这只是理论下界,实际电路(计数器或矩阵)要花的 bit 更多。每组都要这么一份,再乘上几千个组,硅面积和功耗就上去了。这就是 LRU 无法直接用在高相联度缓存上的根本原因。

适用场景

LRU 用在低相联度的缓存上——比如 L1 常见 4 路、8 路,这时顺序状态的 bit 还付得起,换来接近 OPT 的命中率很划算。相联度一高,就得换近似算法了,也就是下面两个。

树形 pLRU:用一棵二叉树近似 LRU

pLRU(Pseudo-LRU,伪 LRU)不追求记住完整顺序,只记一部分信息,用更少的 bit 换接近 LRU 的命中率。最经典的是树形 pLRU(Tree-PLRU)。

实现原理

把一组里的 N 路(N 是 2 的幂)排成一棵二叉树。树的每个内部节点存 1 个 bit,用来记住"它的两个孩子里,哪一边最近被访问过"。

以 4 路为例,需要 3 个 bit(b0 是根,b1、b2 是左右子节点):

          [b0]
         /    \
       [b1]   [b2]
       / \     / \
      W0  W1  W2  W3

约定:某个节点的 bit = 0 表示"左子树更近被访问",bit = 1 表示"右子树更近被访问"。于是这 3 个 bit 就像一组"箭头",指向最近访问过的方向。

两条操作规则:

• 访问某个 way 时:从根走到这个 way 的叶子,沿途把每个节点的 bit 改成"指向刚才经过的那一侧",把这个 way 标记成最近的。
• 需要替换时:从根出发,每一步都走"箭头没指向的那一侧"(也就是更旧的一侧),一路走到叶子,那片叶子就是要淘汰的 way。

用一个具体序列走一遍。初始三个 bit 都是 0,依次访问 W0、W1、W2、W3:

初始:           b0=0, b1=0, b2=0

1. 访问 W0:    根→左(b0 仍指左),左节点→W0(b1 仍指左)
               结果: b0=0, b1=0, b2=0

2. 访问 W1:    根→左(b0 指左),左节点→W1(b1 翻成 1 指右)
               结果: b0=0, b1=1, b2=0

3. 访问 W2:    根→右(b0 翻成 1 指右),右节点→W2(b2 指左)
               结果: b0=1, b1=1, b2=0

4. 访问 W3:    根→右(b0 指右),右节点→W3(b2 翻成 1 指右)
               结果: b0=1, b1=1, b2=1

现在 4 路都满,需要淘汰一个:
   从根 b0=1 出发 → 右是"最近",走左边
   到左节点 b1=1  → W1 是"最近",走 W0
   淘汰 W0  ✓

访问顺序是 W0→W1→W2→W3,真正的 LRU 就是最早访问的 W0,树形 pLRU 选对了。

它只是"近似"

树形 pLRU 只用 N-1 个 bit,记的是两两比较的结果,记不住全局顺序,所以有时会选错。看这个序列:

依次访问 W0、W1、W3 后淘汰:

1. 访问 W0: b0=0, b1=0, b2=0
2. 访问 W1: b0=0, b1=1, b2=0
3. 访问 W3: b0=1, b1=1, b2=1

淘汰时:根 b0=1 → 走左;左节点 b1=1 → 淘汰 W0

但真实 LRU 应该是 W2——它从头到尾没被访问过,比 W0 更久没用。树形 pLRU 却选了 W0,因为它只在"W0 和 W1 谁更旧"之间做了比较,压根没记住 W2 的存在。

这正是"伪"的含义:它用很少的 bit 换来了接近 LRU 的效果,但不保证每次都选对。

开销对比

相联度越高,树形 pLRU 省得越多,而命中率损失很小。

适用场景

树形 pLRU 是高相联度缓存和 TLB 的主力替换策略。L2、L3 这种 8 路、16 路的缓存,以及处理器的 TLB,完整 LRU 太贵,树形 pLRU 就成了事实标准。

QLRU:分象限的两级近似

QLRU(Quadrant LRU,四象限 LRU)是另一种近似思路,AMD 处理器(如 L1/L2 缓存)中常见。它不在一整组上做近似,而是把组里的路拆成小象限,分级决策。

实现原理

核心是"两级"结构:把一组内的 N 路按每 4 路一组,分成若干个象限(quadrant),替换时分两步走:

一组 16 路,拆成 4 个象限,每个象限 4 路:

   [ 象限间:粗选哪个象限最旧 ]
      |       |       |       |
   [Q0:4路] [Q1:4路] [Q2:4路] [Q3:4路]
      |       |       |       |
   [ 象限内:细选象限里哪一路最旧 ]

• 第一级(粗选):在所有象限之间,用一个开销很小的机制(比如对 4 个象限再做一次树形 pLRU,或一个计数器)选出"最久没用的那个象限"。
• 第二级(细选):在选中的象限内部,用一个 2 bit 的 LRU 计数器选出具体淘汰哪一路。

访问命中时,更新对应象限内部的状态(把命中的那一路标成最近),必要时也更新象限之间的状态。

为什么能省开销

以 16 路为例算笔账:

QLRU 用约四分之一的 bit,换来了接近 LRU 的命中率。代价是精度比完整 LRU 略低,但比树形 pLRU 多了一点"象限内"的精细信息。

适用场景

QLRU 的价值在于展示了一种工程思路:把大问题拆小,分级近似。与其在 16 路上硬算完整 LRU,不如拆成 4 个 4 路的子问题,每层都只处理小规模,状态开销大幅下降。具体实现各代处理器有差异,但"分象限 + 两级决策"这个框架是一致的。

四种算法对比与选型

选型的核心只有一句话:相联度越高,越不能承受完整 LRU 的开销,越需要靠 pLRU / QLRU 这类近似方案在 bit 数和命中率之间找平衡。

再往深走,现代 CPU 还有更复杂的策略,比如 RRIP(Re-Reference Interval Prediction):不再记"最近多久没用",而是记"被再次引用还需要多久",用更少的 bit 预测复用距离。以及少数场景用随机替换(random):开销为零,没有最坏情况,在部分缓存(如某些 L3 或 TLB)里表现意外地不差。这些属于进阶方向,面试能提到 RRIP 是加分项。

面试高频追问

Q1:为什么高相联度缓存不用完整 LRU?

因为完整 LRU 要记住 N 路的全序,状态 bit 随相联度指数级增长(16 路就要 45 bit),再乘上几千个组,面积和功耗都扛不住。所以高相联度用树形 pLRU、QLRU 这类近似算法,用少量 bit 换接近 LRU 的命中率。

Q2:树形 pLRU 为什么能比 LRU 省 bit,它丢了什么信息?

树形 pLRU 只记 N-1 个"两两比较"的 bit,而 LRU 要记完整的 N! 种顺序。它丢的是"全局顺序":比如 W2 和 W0 谁更旧这种跨子树的比较它记不住,所以有时会选出并非真正 LRU 的那一路。但大部分时候够用。

Q3:FIFO 和 LRU 的本质区别是什么?

FIFO 只记录"进来的时间",命中也不会改变它的淘汰顺序,完全无视时间局部性;LRU 记录"最近访问时间",每次命中都会刷新,充分利用了"最近用过还会再用"的规律。代价就是 LRU 要多记很多状态。

Q4:替换发生在什么粒度上?

发生在**组(set)**内,不是整个缓存。一次 miss 时,先按 Index 定位到唯一的一组,然后只在这个组的几路里选一路淘汰。所以替换策略的状态是"每组一份",这也是为什么 bit 开销如此敏感。

总结

• 替换策略解决的是"组满时淘汰哪一路",目标是让命中率接近 OPT,同时把硬件开销控制在可接受范围。
• FIFO 最便宜但无视局部性,基本只作教学基线;LRU 命中率接近最优,但状态开销随相联度暴涨,只适合低相联度缓存。
• 树形 pLRU 用 N-1 个 bit 的二叉树近似 LRU,是高相联度缓存和 TLB 的主力;QLRU 把组拆成象限、两级决策,是 AMD 的典型方案。
• 选型本质是相联度与开销的折中:相联度越高,越依赖近似算法。

替换策略是 CPU cache 三篇里的最后一块拼图:地址映射决定"数据放哪",写入策略和 MESI 决定"数据怎么改、怎么保持一致",替换策略决定"满的时候扔谁"。三者合起来,才是完整的缓存工作机制。

与本文相关的另两篇:《CPU cache 原理》、《缓存写入策略与 MESI 一致性协议》。