algorithm - 实际的CPU缓存中使用了哪些缓存失效算法？

Question

我谈到了缓存和映射以及缓存未命中以及当所有 block 都已满时如何以什么顺序替换缓存 block 的主题。

有最近最少使用算法或fifo算法或最不频繁算法和随机替换，...​​

但是在实际的 cpu 缓存上使用了哪些算法？或者您可以使用全部，然后...操作系统决定最佳算法是什么？

---

编辑:即使我选择了答案，也欢迎提供更多信息；)

Answer 1

正如 hivert 所说 - 很难清楚地了解具体的算法，但可以根据提示或巧妙的逆向工程推断出一些信息。

您没有指定您指的是哪个 CPU，每个 CPU 都可以有不同的策略(实际上，即使在同一个 CPU 中，不同的缓存级别也可能有不同的策略，更不用说 TLB 和其他也可能有此类策略的关联数组) .我确实找到了一些关于 Intel(特别是 Ivy bridge)的提示，所以我们将使用它作为行业级“标准”的基准(可能适用也可能不适用于其他地方)。

首先，Intel 在这里展示了一些 LRU 相关的特性—— http://www.hotchips.org/wp-content/uploads/hc_archives/hc24/HC24-1-Microprocessor/HC24.28.117-HotChips_IvyBridge_Power_04.pdf

幻灯片 46 提到了“Quad-Age LRU”——这显然是一个基于年龄的 LRU，它根据预测的重要性为每一行分配了一些“年龄”。他们提到预取会进入中年，因此需求可能会分配到更高的年龄(或更低的年龄，无论存活时间最长)，并且所有线路都可能逐渐老化，因此最老的首先被替换。不如完美的“fifo-like”LRU，但请记住，大多数缓存都没有实现它，而是一个复杂的 pseudo-LRU。解决方案，所以这可能是一个改进。

那里提到的另一个有趣的机制是自适应填充策略，它比经典的 LRU 更进一步。这里有一个很好的分析 - http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/ ，但简而言之(如果博客是正确的，并且他似乎确实与他的结果匹配得很好)，缓存会在两个 LRU 策略之间动态选择，试图决定这些行是否将被重用(和应保留或不保留)。

我想这可以在某种程度上回答您关于多个 LRU 方案的问题。就硬件而言，实现多个方案可能既困难又昂贵，但是当您有一些足够复杂以具有参数的策略时，可以使用动态选择、设置决斗等技巧。