缓存替换策略
Cache replacement policy
能否给出伪代码/详细解释以下缓存替换策略是如何实现的？
- 先进先出
- LRU
- 随机
我很难对他们是如何一步一步地工作有一个深刻的理解。因此，我相信每个策略的算法都会crystal清晰。
逻辑上它们的实现方式是集合中的缓存行是有序的，因此它们形成一个队列。队列的头部是下次缓存需要在该集合中分配一行时将被逐出的行。
新行分配在队列的末尾，距离 "chopping block" 最远。如果集合中有无效行，则不需要驱逐：元素移动以填补队列中的空白。否则需要驱逐才能在此集合中腾出空间。
对于 LRU，命中时该行移动到最近使用 (MRU) 的位置。对于 FIFO，它没有。
随机不排队；如果集合中没有无效行，缓存只会选择一个随机行来替换。
为了最大限度地减少缓存污染，非临时加载或预取可以在 LRU 位置（下一个要逐出的行）而不是通常的 LRU 分配行。这对于您不希望在数据被逐出之前多次读取的数据很有用。 （我认为 AMD CPU 对于 NT 预取实际上是这样工作的。英特尔 CPU 通过将其限制为仅填充 L3 缓存中任何集合的 1 或 2 种方式来实现 prefetchnta。）
物理上它们的实现方式可能会有所不同，只要它们实现了所需的算法。 IDK 如果实际复制数据是典型的（在读取命中后将其全部写回缓存阵列，对于 LRU），或者在标签中使用额外的位来记录顺序并且只写回这些数据。我想这将是一个更宽的额外写入端口与 3 个额外标记位之间的权衡。
快速 L1d 缓存并行读取标签 + 数据是很常见的，因此一组中所有方式的数据都可以根据标签比较器结果从中挑选。
但是对于等待标签检查然后只从命中的方式获取数据（如果有命中）的更节能的缓存，复制数据是不切实际的。
我认为 LRU 逻辑很可能通常是用额外的标记位来实现的，这些标记位给出了集合中路径的顺序。不过，您的心智模型可以忽略这一点，只看移动位置的线条。
或者不要让我编造东西，只需阅读 Paul Clayton 在 How is an LRU cache implemented in a CPU?
上的回答
显然，一些设计使用伪 LRU 而不是真正的 LRU，以减少每组额外的位数。例如大型末级高速缓存中 16 路中的每路 4 位数字，或 8 路高速缓存中的 8x 3 位数字。 （加上并行执行 LRU 逻辑的硬件将非常重要。）或者您可以将队列的可能状态编码为每组 16 位，而不是简单地对每种方式进行编号。但这仍然很重要。
（我不知道现代高性能 x86 CPU 在实践中使用了什么——真正的 LRU 是否值得为 small/fast L1d and/or 为 larger/slower L2 和 L3 付出代价)
能否给出伪代码/详细解释以下缓存替换策略是如何实现的？
- 先进先出
- LRU
- 随机
我很难对他们是如何一步一步地工作有一个深刻的理解。因此，我相信每个策略的算法都会crystal清晰。
逻辑上它们的实现方式是集合中的缓存行是有序的，因此它们形成一个队列。队列的头部是下次缓存需要在该集合中分配一行时将被逐出的行。
新行分配在队列的末尾，距离 "chopping block" 最远。如果集合中有无效行，则不需要驱逐：元素移动以填补队列中的空白。否则需要驱逐才能在此集合中腾出空间。
对于 LRU，命中时该行移动到最近使用 (MRU) 的位置。对于 FIFO，它没有。
随机不排队；如果集合中没有无效行，缓存只会选择一个随机行来替换。
为了最大限度地减少缓存污染，非临时加载或预取可以在 LRU 位置（下一个要逐出的行）而不是通常的 LRU 分配行。这对于您不希望在数据被逐出之前多次读取的数据很有用。 （我认为 AMD CPU 对于 NT 预取实际上是这样工作的。英特尔 CPU 通过将其限制为仅填充 L3 缓存中任何集合的 1 或 2 种方式来实现 prefetchnta。）
物理上它们的实现方式可能会有所不同，只要它们实现了所需的算法。 IDK 如果实际复制数据是典型的（在读取命中后将其全部写回缓存阵列，对于 LRU），或者在标签中使用额外的位来记录顺序并且只写回这些数据。我想这将是一个更宽的额外写入端口与 3 个额外标记位之间的权衡。
快速 L1d 缓存并行读取标签 + 数据是很常见的，因此一组中所有方式的数据都可以根据标签比较器结果从中挑选。 但是对于等待标签检查然后只从命中的方式获取数据（如果有命中）的更节能的缓存，复制数据是不切实际的。
我认为 LRU 逻辑很可能通常是用额外的标记位来实现的，这些标记位给出了集合中路径的顺序。不过，您的心智模型可以忽略这一点，只看移动位置的线条。
或者不要让我编造东西，只需阅读 Paul Clayton 在 How is an LRU cache implemented in a CPU?
上的回答显然，一些设计使用伪 LRU 而不是真正的 LRU，以减少每组额外的位数。例如大型末级高速缓存中 16 路中的每路 4 位数字，或 8 路高速缓存中的 8x 3 位数字。 （加上并行执行 LRU 逻辑的硬件将非常重要。）或者您可以将队列的可能状态编码为每组 16 位，而不是简单地对每种方式进行编号。但这仍然很重要。
（我不知道现代高性能 x86 CPU 在实践中使用了什么——真正的 LRU 是否值得为 small/fast L1d and/or 为 larger/slower L2 和 L3 付出代价)