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

Question

我来到主题缓存和映射以及缓存未命中以及当所有块已满时缓存块如何以什么顺序替换.

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

但是在实际的cpu缓存上使用了哪些算法？或者你可以使用所有...操作系统决定最佳算法是什么？

---

编辑:即使我选择了答案,欢迎任何进一步的信息;)

Answer 1

正如hivert所说 - 很难对特定算法有清晰的了解,但可以根据提示或巧妙的逆向工程推断出一些信息.

您没有指定您所指的CPU,每个CPU可以有不同的策略(实际上即使在同一CPU中,不同的缓存级别可能有不同的策略,更不用说TLB和其他也可能具有此类策略的关联阵列).我确实找到了一些关于英特尔(特别是常春藤桥)的提示,因此我们将其用作行业级"标准"的基准(可能适用于其他地方也可能不适用).

首先,英特尔在此提出了一些与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"的LRU,但请记住,大多数缓存都没有实现,而是一个复杂的伪LRU解决方案,所以这可能是一个改进.

另外一个有趣的机制是自适应填充策略,它超越了经典的LRU.这里有一个非常好的分析 - http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/,但简而言之(如果博客是正确的,他似乎确实与他的一个很好的匹配结果),缓存在两个LRU策略之间动态选择,试图决定是否要重用这些行(并且应该保留或不保留).

我想这可以在某种程度上回答你关于多个LRU方案的问题.在硬件方面实现几种方案可能既硬又昂贵,但是当你有一些复杂到足以拥有参数的策略时,可以使用动态选择,设置决斗等技巧.

Answer 2

以下是实际处理器中使用的替换策略的一些示例.

PowerPC 7450的8路L1高速缓存使用二叉树pLRU.二叉树PLRU使用每对的方式设置一个LRU该对一个比特,则一个LRU位对于每对对的方式,等等.8路L2中使用的伪随机置换特权软件(操作系统)可设置使用每个时钟周期递增的3位计数器或基于移位寄存器的伪随机数发生器.

StrongARM SA-1110 32路L1数据高速缓存使用FIFO.它还有一个用于瞬态数据的双向小型缓存,它似乎也使用了FIFO.(Intel StrongARM SA-1110微处理器开发人员手册指出"minicache中的替换使用与主数据高速缓存中相同的循环指针机制.但是,由于此高速缓存只是双向组关联,因此替换算法减少为简单的最近最少使用(LRU)机制";但2路FIFO是不一样的LRU即使只有两种方式,但对于流数据它的作品了相同]).

HP PA 7200具有64块全关联"辅助缓存",可与片外直接映射数据缓存并行访问.辅助缓存使用FIFO替换,可选择驱逐到片外L1缓存.加载和存储指令有"仅限本地"的提示; 如果通过这样的存储器访问加载了辅助高速缓存条目,则它将被驱逐到绕过片外L1的存储器.

对于双向关联性,真正的LRU可能是最常见的选择,因为它具有良好的行为(并且顺便提一下,当只有两种方式时,它与二叉树pLRU相同).例如,Fairchild Clipper缓存和内存管理单元使用LRU进行双向缓存.FIFO比LRU稍微便宜,因为替换信息仅在无论如何写入标记时更新,即,当插入新的高速缓存块时,但是具有比基于计数器的伪随机替换(其具有更低的开销)更好的行为.HP PA 7300LC使用FIFO作为其双向L1高速缓存.

Itanium 9500系列(Poulson)将NRU用于L1和L2数据高速缓存,L2指令高速缓存和L3高速缓存(L1指令高速缓存记录为使用LRU).对于Itanium 2 6M(麦迪逊)中的24路L3缓存,为NRU提供了每个块的位,可以访问块设置与其设置和方式相对应的位("Itanium 2处理器6M:更高频率和更大频率" L3 Cache",Stefan Rusu等,2004).这类似于时钟页面替换算法.

我似乎记得在其他地方读过这些比特在所有设置完成时被清除(而不是保持设置最后一个未设置位的那个)并且通过找到第一个未设置的比特扫描来选择受害者.这将具有硬件优势,即只需要在高速缓存未命中时读取信息(其存储在来自L3标签但不在L3标签附近的不同阵列中); 缓存命中可以简单地设置适当的位.顺便说一下,这种类型的NRU避免了真实LRU的一些不良特性(例如,LRU在某些情况下降级到FIFO,并且在某些情况下甚至随机替换可以提高命中率).

Answer 3

对于 Intel CPU，更换策略通常没有记录。我做了一些实验来揭示最近的 Intel CPU 中的策略，其结果可以在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 策略的概括，每个缓存块使用两位。此策略的不同变体用于 L3 缓存（从 Ivy Bridge 开始）和 L2 缓存（从 Skylake 开始）。
• 自适应策略： Ivy Bridge、Haswell 和 Broadwell CPU 可以在两种不同的 QLRU 变体之间动态选择。这是通过集合决斗实现的：少数专用集合始终使用相同的 QLRU 变体；其余组是“跟随组”，它们使用在专用组上表现更好的变体。另请参阅http://blog.stuffedcow.net/2013/01/ivb-cache-replacement/。