caching - LRU 缓存是如何在 CPU 中实现的？

Question

我正在准备面试，并想刷新我对缓存的记忆。如果一个 CPU 有一个带有 LRU 替换策略的缓存，那它是如何在芯片上实际实现的呢？每个缓存行会存储一个时间戳记吗？

此外，在双核系统中两个 CPU 同时写入一个地址的情况下会发生什么？

Answer 1

对于只有两种方式的传统缓存，每组单个位可用于跟踪 LRU。在任何访问命中的集合时，该位可以设置为未命中的方式。

对于更大的关联性，状态的数量会急剧增加：方式数量的阶乘。因此，4 路缓存将有 24 个状态，每组需要 5 位，而 8 路缓存将有 40,320 个状态，每组需要 16 位。除了存储开销之外，更新值的开销也更大。

对于 4 路高速缓存，以下状态编码似乎工作得相当好：两位表示最近使用的路号，两位表示下一个最近使用的路号，以及指示较高或最近使用了较低编号的方式。

• 在 MRU 命中时，状态不变。
• 在下一个 MRU 命中时，交换两个位字段。
• 在其他命中时，对其他两个路的编号进行解码，命中的路号放在第一个两位部分中，前一个 MRU 路号放在第二个两位部分中。根据下一个 MRU 路数是否高于或低于最近使用较少但未命中的路数来设置最后一位。
• 在未命中时，状态会更新，就好像发生了 LRU 命中一样。

因为 LRU 跟踪有这样的开销，所以经常使用像二叉树伪 LRU 这样更简单的机制。在一次命中时，这只是更新树的每个分支部分，其中一半的关联路径是命中的。对于两个路径数 W 的幂，二叉树 pLRU 缓存将具有每组 W-1 位状态. 命中 8 路缓存（使用 3 级二叉树）的路 6 将清除树底部的位，以指示路的下半部分 (0,1,2,3) 更少最近使用，清除下一级的高位以指示这些方式的下半部分 (4,5) 最近使用较少，并在最后一级设置高位以指示这些方式的上半部分 (7)最近很少使用。不必为了更新它而读取这个状态可以简化硬件。

对于偏斜关联性，其中不同的方式使用不同的散列函数，已经提出了类似缩写时间戳的东西（例如，“斜关联缓存的分析和替换”，Mark Brehob 等人，1997）。使用未命中计数器比循环计数更合适，但基本思想是相同的。

对于两个内核尝试同时写入同一高速缓存行时发生的情况，这是通过仅允许一个 L1 高速缓存在给定时间使高速缓存行处于独占状态来处理的。实际上有一场比赛，一个核心将获得独占访问权。如果只有一个写入核心已经拥有处于共享状态的高速缓存行，那么它可能更有可能赢得比赛。缓存线处于共享状态，缓存只需向缓存线的其他潜在持有者发送失效请求；在不存在高速缓存行的情况下，写入通常需要请求数据的高速缓存行以及请求独占状态。

不同内核对同一缓存线的写入（无论是相同的特定地址，还是在错误共享的情况下，写入数据行中的另一个地址）可能导致“缓存线乒乓”，其中不同的内核使缓存无效其他缓存中的行以获得独占访问（执行写入），以便缓存行像乒乓球一样在系统周围反弹。

Answer 2

有一个很好的幻灯片页面替换算法，它讨论了各种页面替换方案。它还很好地解释了使用 mxm 矩阵的 LRU 实现。