我要谈论的话题是缓存、映射和缓存未命中，以及当所有块已满时缓存块被替换的顺序。
有最近最少使用算法、先进先出算法、最不经常使用算法和随机替换等算法...
但实际的CPU缓存使用哪些算法呢？或者你可以使用全部算法，...操作系统会决定使用哪种最佳算法吗？
编辑：即使我选择了一个答案，任何进一步的信息也是欢迎的；）
3个回答
11
正如hivert所说-很难对具体算法有清晰的认识，但可以根据提示或巧妙的反向工程来推断一些信息。
你没有指定哪个CPU，每个CPU都可能有不同的策略（实际上即使在同一个CPU内部，不同的缓存级别也可能有不同的策略，更不用说其他可能存在这种策略的关联数组，比如TLB）。我确实找到了一些关于Intel（特别是Ivy Bridge）的线索，因此我们将以此为行业水平“标准”（可能适用于其他地方，也可能不适用）。
首先，英特尔在这里介绍了一些与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好，但请记住，大多数缓存都没有实现它，而是使用了一种复杂的伪LRU解决方案，因此这可能是一个改进。
你没有指定哪个CPU，每个CPU都可能有不同的策略（实际上即使在同一个CPU内部，不同的缓存级别也可能有不同的策略，更不用说其他可能存在这种策略的关联数组，比如TLB）。我确实找到了一些关于Intel（特别是Ivy Bridge）的线索，因此我们将以此为行业水平“标准”（可能适用于其他地方，也可能不适用）。
首先，英特尔在这里介绍了一些与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好，但请记住，大多数缓存都没有实现它，而是使用了一种复杂的伪LRU解决方案，因此这可能是一个改进。
另一个有趣的机制提到了，它超越了经典的LRU，这就是自适应填充策略。这里有一个相当不错的分析-http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/，但简而言之（如果博客是正确的，他的结果似乎很匹配），缓存动态选择两个LRU策略之间进行切换，试图决定行是否会被重用（并且是否应该保留）。
我猜这可能在某种程度上回答了你关于多个LRU方案的问题。实施几个方案可能在硬件方面很困难和昂贵，但是当您拥有复杂到具有参数的策略时，可以使用诸如动态选择、集合对决等技巧。
- Leeor
11
以下是一些实际处理器中使用的替换策略示例。
PowerPC 7450的8路L1缓存使用二叉树pLRU。二叉树pLRU使用每对路的一个比特来设置该对的LRU，然后使用每对路对的一个LRU位，等等。8路L2使用伪随机替换，可以由特权软件（操作系统）设置为使用每个时钟周期递增的3位计数器或基于移位寄存器的伪随机数字发生器。
StrongARM SA-1110的32路L1数据缓存使用FIFO。它还具有一个用于瞬态数据的2路小缓存，该缓存似乎也使用了FIFO。（Intel StrongARM SA-1110 Microprocessor Developer's Manual 指出：“小缓存中的替换使用与主数据缓存中相同的轮询指针机制。但是，由于此缓存仅是2路组相联的，所以替换算法简化为简单的最近最少使用（LRU）机制。”；但即使只有两路，2路FIFO也不是相同的LRU，但对于流数据，它的效果相同。）
HP PA 7200具有64块全关联的“辅助缓存”，可与片外直接映射的数据缓存并行访问。辅助缓存使用FIFO替换，并可选择将其逐出到片外L1缓存。Load和store指令具有“仅局部性”提示；如果通过这样的内存访问加载了辅助缓存条目，则会将其逐出到内存，绕过片外L1。
PowerPC 7450的8路L1缓存使用二叉树pLRU。二叉树pLRU使用每对路的一个比特来设置该对的LRU，然后使用每对路对的一个LRU位，等等。8路L2使用伪随机替换，可以由特权软件（操作系统）设置为使用每个时钟周期递增的3位计数器或基于移位寄存器的伪随机数字发生器。
StrongARM SA-1110的32路L1数据缓存使用FIFO。它还具有一个用于瞬态数据的2路小缓存，该缓存似乎也使用了FIFO。（Intel StrongARM SA-1110 Microprocessor Developer's Manual 指出：“小缓存中的替换使用与主数据缓存中相同的轮询指针机制。但是，由于此缓存仅是2路组相联的，所以替换算法简化为简单的最近最少使用（LRU）机制。”；但即使只有两路，2路FIFO也不是相同的LRU，但对于流数据，它的效果相同。）
HP PA 7200具有64块全关联的“辅助缓存”，可与片外直接映射的数据缓存并行访问。辅助缓存使用FIFO替换，并可选择将其逐出到片外L1缓存。Load和store指令具有“仅局部性”提示；如果通过这样的内存访问加载了辅助缓存条目，则会将其逐出到内存，绕过片外L1。
针对2路关联性，真正的LRU可能是最常见的选择，因为它具有良好的行为（顺便说一下，在只有两条路时与二叉树pLRU相同）。例如，Fairchild Clipper Cache和Memory Management Unit在其2路缓存中使用了LRU。FIFO比LRU稍微便宜一些，因为替换信息仅在写入标签时更新，也就是插入新缓存块时，但其行为比基于计数器的伪随机替换要好（后者的开销更低）。HP PA 7300LC在其2路L1缓存中使用了FIFO。
Itanium 9500系列（Poulson）在L1和L2数据缓存、L2指令缓存以及L3缓存中使用NRU。 L1指令缓存记录为使用LRU。对于Itanium 2 6M（Madison）中的24路L3缓存，每个块都提供了一个用于NRU的位，访问块会设置其所在集合和路的位（“Itanium 2 Processor 6M：Higher Frequency and Larger L3 Cache”，Stefan Rusu等人，2004）。这类似于时钟页面替换算法。
我记得在别处读到过，当所有位都设置时（而不是保留设置最后一位的那个位），位将被清除，并且受害者是通过查找第一个未设置的位来选择的。这具有硬件优势，可以仅在缓存未命中时读取信息（该信息存储在L3标记旁边但不同的数组中）；缓存命中时可以简单地设置相应的位。顺便说一下，这种类型的NRU避免了真正的LRU的一些不良特性（例如，在某些情况下，LRU会退化为FIFO，在其中一些情况下，甚至随机替换也会增加命中率）。
- user2467198
6
对于英特尔处理器，替换策略通常是未记录的。我已经进行了一些实验，以揭示最近英特尔处理器中的策略，结果可在https://uops.info/cache.html上找到。我使用的代码可在GitHub上找到。
以下是我的发现摘要。
- Tree-PLRU：所有我测试过的CPU的L1数据缓存都使用此策略，Nehalem、Westmere、Sandy Bridge、Ivy Bridge、Haswell和Broadwell CPU的L2缓存也使用此策略。 - 随机化Tree-PLRU：某些Core 2 Duo CPU在其L2缓存中使用Tree-PLRU的变体，其中树中的最低位或最高位被（伪）随机性替换。 - MRU：有时也称为NRU。每个缓存块使用一个位。对块的访问将位设置为0。如果最后一个1位设置为0，则所有其他位都设置为1。在缺失时，将替换第一个位为1的块。Nehalem、Westmere和Sandy Bridge CPU的L3缓存使用此策略。 - Quad-Age LRU（QLRU）：这是MRU策略的一般化，每个缓存块使用两个位。从Ivy Bridge开始，使用此策略的不同变体用于L3缓存；从Skylake开始，用于L2缓存。 - 自适应策略：Ivy Bridge、Haswell和Broadwell CPU可以在两种不同的QLRU变体之间动态选择。这通过“集合对决”实现：少数专用集合始终使用相同的QLRU变体；其余集合是“跟随者集合”，使用在专用集合上表现更好的变体。另请参见http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/。
以下是我的发现摘要。
- Tree-PLRU：所有我测试过的CPU的L1数据缓存都使用此策略，Nehalem、Westmere、Sandy Bridge、Ivy Bridge、Haswell和Broadwell CPU的L2缓存也使用此策略。 - 随机化Tree-PLRU：某些Core 2 Duo CPU在其L2缓存中使用Tree-PLRU的变体，其中树中的最低位或最高位被（伪）随机性替换。 - MRU：有时也称为NRU。每个缓存块使用一个位。对块的访问将位设置为0。如果最后一个1位设置为0，则所有其他位都设置为1。在缺失时，将替换第一个位为1的块。Nehalem、Westmere和Sandy Bridge CPU的L3缓存使用此策略。 - Quad-Age LRU（QLRU）：这是MRU策略的一般化，每个缓存块使用两个位。从Ivy Bridge开始，使用此策略的不同变体用于L3缓存；从Skylake开始，用于L2缓存。 - 自适应策略：Ivy Bridge、Haswell和Broadwell CPU可以在两种不同的QLRU变体之间动态选择。这通过“集合对决”实现：少数专用集合始终使用相同的QLRU变体；其余集合是“跟随者集合”，使用在专用集合上表现更好的变体。另请参见http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/。
- Andreas Abel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接