时间戳

首页 > 解决方案 > 缓存替换策略

caching - 缓存替换策略

问题描述

你能给出一个伪代码/详细解释以下缓存替换策略是如何实现的吗？

  1. 先进先出
  2. LRU
  3. 随机的

我很难对它们如何一步一步地工作有一个扎实的理解。因此，我相信每个策略的算法都会非常清晰。

标签： cachingcpu-architecturefifocpu-cachelru

解决方案

从逻辑上讲，它们的实现方式是一组中的缓存行是有序的，因此它们形成了一个队列。队列的头部是下次缓存需要在该集合中分配一行时将被逐出的行。

新行分配在队列的末尾，离“砧板”最远。如果集合中有无效行，则不需要驱逐：元素移动以填补队列中的空白。否则需要逐出以在该集合中腾出空间。

对于 LRU，在命中时，该行将移动到最近使用 (MRU) 的位置。对于先进先出，它没有。

对于随机，没有队列；如果集合中没有无效行，缓存只会选择一个随机行来替换。

为了最大限度地减少缓存污染，非临时加载或预取可以将行分配在 LRU 位置（下一个要被驱逐的行）而不是通常的 LRU。这对于您不希望在被驱逐之前多次读取的数据很有用。（我认为 AMD CPU 对于 NT 预取实际上是这样工作的。英特尔 CPUprefetchnta通过将其限制为仅填充 L3 缓存中任何集合的 1 或 2 种方式来实现。）

从物理上讲，它们的实现方式可能会有所不同，只要它们实现了所需的算法。IDK 如果实际复制数据是典型的（在读取命中后将其全部写回缓存阵列，对于 LRU），或者使用标签中的额外位来记录排序并只写回那些。我想这将是一个更宽的额外写入端口与 3 个额外标签位之间的权衡。

快速 L1d 缓存通常并行读取标签 + 数据，因此集合中所有方式的数据都可以根据标签比较器结果从中挑选。但是对于等待标签检查然后只从命中的方式（如果有命中）获取数据的更节能的缓存，复制数据是不切实际的。

我认为 LRU 逻辑很可能通常是用额外的标签位实现的，这些标签位给出了一组方式的顺序。不过，你的心智模型可以忽略这一点，只看线条移动的位置。

或者，不用我编造东西，只需阅读 Paul Clayton 关于如何在 CPU 中实现 LRU 缓存的答案？

显然，一些设计使用伪 LRU 而不是真正的 LRU，以减少每组的额外位数。例如，大型最后一级缓存中的 16 路中的每一个都使用 4 位数，或者 8 路缓存中的 8x 3 位数。（加上并行执行 LRU 逻辑的硬件将非常重要。）或者，您可以将队列的可能状态编码为每组少至 16 位，而不是简单地对每种方式进行编号。但这仍然很重要。

（我不知道现代高性能 x86 CPU 在实践中使用什么——真正的 LRU 是否值得为小/快 L1d 和/或更大/更慢的 L2 和 L3 付出代价）

推荐阅读