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

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 缓存使缓存线处于独占状态来处理的。实际上有一场比赛，一个核心将获得独占访问权。如果只有一个写入核心已经将缓存线处于共享状态，则它可能更有可能赢得比赛。当缓存线处于共享状态时，缓存只需要向缓存线的其他潜在持有者发送失效请求；当缓存线不存在时，写入通常需要请求数据的缓存线以及请求独占状态。

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