LRU、FIFO、随机

Question

当出现页面错误或缓存未命中时，我们可以使用最近最少使用 (LRU)、先入先出 (FIFO) 或随机替换算法。我想知道，哪一个提供了最好的性能，也称为未来缓存丢失/页面错误最少的可能性？

架构：Coldfire 处理器

Answer 1

您指定的架构是 68000，它是一个 CPU，而不是 GPU 或 USB 控制器，或者其他可能访问缓存的硬件...

因此，您在 68000 上运行的代码将对问题“最少可能的未来缓存丢失/页面错误”。

在这方面，您区分了缓存未命中和页面错误，我不确定您到底指的是哪种coldfire架构，但我假设这没有硬件TLB替换，它使用软件机制（因此缓存将是与应用程序的数据共享）。

在替换策略中最重要的因素是关联（或方式）的数量。

直接映射缓存（1 路）直接与地址的低位相关（几乎总是如此）（位数指定缓存的大小），因此 32k 缓存将是较低的 15 位。在这种情况下，替换算法 LRU、FIFO 或 Random 将毫无用处，因为只有一种可能的选择。

然而，缓存的回写或直写选择会产生更大的效果。仅适用于写入内存 直写意味着高速缓存行未分配，与写回高速缓存相反，其中当前位于高速缓存中的共享相同低 15 位的行被从高速缓存中弹出并读回然后修改，以供使用 IF CPU 上运行的代码使用此数据）。

对于写入数据且不对数据执行多个操作的操作，直写通常要好得多，在现代处理器上也是如此（我不知道该架构是否支持它），但可以在 TLB/Page 上选择 Writethrough 或 Writeback基础。这对缓存的影响比策略大得多，您可以对系统进行编程以匹配每个页面中的数据类型，尤其是在直接地图缓存中;-)

因此直接地图缓存非常容易理解，它是也很容易理解缓存的最坏情况、最好情况和平均情况的基础。

想象一个 memcpy 例程，它复制与缓存大小对齐的数据。例如，一个 32k 直接映射缓存，两个 32k 缓冲区在 32k 边界上对齐......

0x0000 -> read
0x8000 -> write
0x8004 -> read
0x8004 -> write
...
0x8ffc -> read
0x8ffc -> write

在这里您可以看到复制每个数据字时的读取和写入，请注意每个读取和写入操作的低 15 位是相同的。

使用写回的直接映射缓存（记住写回分配行执行以下操作）

0x0000 -> read
 cache performs: (miss)
   0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)

0x8000 -> write
  cache performs: (miss)
    invalidate 0x0000:0x001f (line 0)
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
    0x8000           (modify this location in the cache with the read source data)

<loop>

0x0004 -> read
  cache performs: (miss)
    writeback 0x8000:0x801f -> WRITE to main memory (ie. write 32 bytes to the desitnation)
    0x0000:0x001f -> READ from main memory (ie. read 32 bytes of source (the same as we did just before)

0x8004 -> write
  cache performs: (miss)
    invalidate 0x0000:0x001f (line 0)
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
    0x8004           (modify this location in the cache with the read source data)

</loop>  <--- (side note XML is not a language but we use it as such)

当您看到大量内存操作正在进行时，这实际上称为“颠簸”，并且是最坏情况场景的最佳示例。

现在想象一下我们使用 writethrough 缓存，这些是操作：

<loop>
0x0000 -> read
 cache performs: (miss)
   0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)

0x8000 -> write
  cache performs: (not a miss)
   (not a lot, the write is "posted" to main memory) (posted is like a letter you just place it in the mailbox and you don't care if it takes a week to get there).

  <loop>

  0x0004 -> read
    cache performs: (hit)
      (not a lot, it just pulls the data it fetched last time which it has in it's memory so it goes very quickly to the CPU)

  0x8004 -> write
    cache performs: (not a miss)
     (not a lot, the write is "posted" to main memory)

  </loop until next 32 bytes>
</loop until end of buffer>

正如您所看到的巨大差异，我们现在不会崩溃，事实上我们是本示例中的最佳情况。

好的，这就是直写与回写的简单情况。

然而，直接映射缓存现在不太常见，大多数人使用 2,4 或 8 路缓存，即一行中有 2、4 或 8 个不同的可能分配。所以我们可以在4路或8路缓存中同时存储0x0000、0x8000、0x1000、0x1800（显然8路也可以存储0x2000、0x2800、0x3000、0x3800）。

这将避免这个颠簸问题。

只是为了澄清 32k 直接映射缓存中的行号是地址的底部 15 位。
在 32k 2 方式中，它是底部 14 位。
在 32k 4 方式中，它是底部 13 位。
在 32k 8 方式中，它是底部 12 位。

在全关联高速缓存中，它是行大小（或 32 字节行的底部 5 位）。你不能少于一行。 32 字节通常是 DDR 内存系统中最佳的操作（还有其他原因，有时 16 或有时 64 字节可能更好，并且在算法情况下 1 字节是最佳的，我们使用 32，因为这很常见）

为了帮助理解 LRU、FIFO 和随机，我们认为缓存是完全关联的，在 32k 32 字节行缓存中，这是 1024 行。

随机替换策略会随机导致最坏情况每 1024 个替换命中一次（即 99.9% 命中），在 LRU 或 FIFO 中我总是可以编写一个会“颠簸”的程序，即。总是会导致最坏情况的行为（即 0% 命中）。

显然，如果您有一个完全关联的缓存，那么只有在程序已知并且程序的确切行为已知的情况下，您才会选择 LRU 或 FIFO。

对于任何不是 99.9% 可预测的事情，你都会选择随机，它只是不最差的最好的，也是平均的最好的之一，但是最好的情况（我得到最好的性能）怎么样......

好吧基本上取决于方法的数量...

2 种方法，我可以优化诸如 memcpy 和其他算法之类的东西来做好工作。随机的时候有一半会出错。
4 种方式，当我在其他任务之间切换时，我可能不会对缓存造成太大破坏，以至于它们的数据仍然是本地的。随机有四分之一的时间会出错。
现在统计数据可以生效的 8 种方式 memcpy 上的 7/8% 命中率不如 1023/1024%（完全关联或优化的代码），但对于非优化的代码来说，它会产生影响。

那么为什么人们不使用随机替换策略来制作完全关联的缓存呢！

好吧，这并不是因为它们不能生成好的随机数，事实上伪随机数生成器也同样好，是的，我可以编写一个程序来获得 100% 的丢失率，但这不是重点，我不能编写一个 100% 未命中的有用程序，我可以使用 LRU 或 FIFO 算法来实现。

32k 32 字节行全关联高速缓存要求您比较 1024 个值，在硬件中这是通过 CAM 完成的，但这是一个昂贵的硬件，而且不可能在“快速”处理中比较这么多值时间，我想知道量子计算机是否可以……

无论如何，回答你的问题哪个更好：

1. 考虑写通是否比写回更好。
2. 大路的 RANDOM 更好
3. 未知代码 RANDOM 对于 4 路或以上更好。
4. 如果它是单一功能，或者您希望从愿意优化的东西中获得最大速度，或者您不关心最坏的情况，那么 LRU 可能就是您想要的。
5. 如果您的方式很少，那么 LRU 可能就是您想要的，除非您有非常具体的场景，那么 FIFO 可能就可以。

参考文献：

• http://www.freescale.com/files/training/doc/ APF_ENT_T0801_5225_COLDFIRE_MCU.pdf
• http://en.wikipedia.org/wiki/Cache_algorithms

Answer 2

不存在完美的缓存策略，因为它需要了解未来（程序如何访问内存）。

但是，在常见的内存访问模式情况下，有些明显优于其他。 LRU 就是这种情况。 LRU 历史上在整体使用中给出了非常好的性能。

但是，对于您想要做的事情，另一种政策可能会更好。总有一些内存访问模式会导致缓存策略表现不佳。

您可能会发现此线程很有帮助（而且更详细！）
为什么 LRU 比 FIFO 更好？

Answer 3

在这三者之间，我推荐 LRU。首先，当假设局部性时，这是对最优调度的一个很好的近似（事实证明这是一个很好的假设）。随机调度不能从局部性中受益。其次，它不会受到 Belady 异常的影响（如 FIFO）；也就是说，更大的缓存意味着更好的性能，但对于 FIFO 来说不一定如此。

只有当您的特定问题域强烈建议使用其他东西时，LRU 在一般情况下才很难被击败。

Answer 4

在这三者中，LRU 通常是最好的，而 FIFO 是最差的，而随机则介于两者之间。您可以构建三种访问模式，其中任何一种都优于其他任何一种，但这有些棘手。有趣的是，这个顺序也粗略地表示了它们的实现成本——LRU 是最昂贵的，而 FIFO 是最便宜的。只是去表演，天下没有免费的午餐

Answer 5

我研究过的许多架构都使用 LRU，因为它通常不仅提供实现效率，而且平均而言在防止遗漏方面也相当出色。然而，在最新的 x86 架构中，我认为发生了一些更复杂的事情。 LRU 是一种基本模型。

这实际上取决于您在设备上执行的操作类型。根据作业类型的不同，不同的疏散策略会发挥更好的作用。例如，FIFO 可以很好地按顺序遍历内存。

Answer 6

如果您想要两全其美，请考虑采用自适应方法，根据实际使用模式改变策略。例如，查看 IBM 的算法自适应替换缓存：http://code.activestate.com/recipes/576532-adaptive-replacement-cache-in-python/