3

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

架构：Coldfire 处理器

4

6 回答 6

10

“没有愚蠢的问题”这句话非常适合这一点。这是一个很好的问题，我必须创建一个帐户并在其上发布并分享我作为在几个 CPU 上建模缓存的人的观点。

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

因此，您在 68000 上运行的代码将对“未来最少可能发生的缓存未命中/页面错误”问题的一部分产生巨大影响。

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

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

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

但是，缓存的 Writeback 或 Writethrough 选择会产生更大的影响。仅用于写入内存 直写意味着缓存行没有分配给回写缓存，其中当前在缓存中共享相同低 15 位的行被弹出缓存并读回然后修改，用于 IF CPU 上运行的代码使用此数据）。

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

所以直接地图缓存很容易理解，也很容易理解缓存的最坏情况、最佳情况和平均情况的基础。

想象一个 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)

正如您看到的大量内存操作，这实际上被称为“抖动”并且是最坏情况场景的最佳示例。

现在假设我们使用直写缓存，这些是操作：

<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 位。

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

为了帮助理解 LRU、FIFO 和 Random，考虑缓存是完全关联的，在 32k 32 字节行缓存中，这是 1024 行。

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

很明显，如果你有一个完全关联的缓存，你只会选择 LRU 或 FIFO，如果程序是已知的并且它是已知的程序的确切行为。

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

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

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 可能就可以了。

参考：

于 2014-06-06T02:17:29.563 回答
8

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

但是，在常见的内存访问模式案例中，有些比其他的要好得多。LRU 就是这种情况。LRU 历来在整体使用中提供了非常好的性能。

但是，对于您正在尝试做的事情，另一种策略可能会更好。总会有一些内存访问模式会导致缓存策略性能不佳。

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

于 2011-08-03T18:01:42.443 回答
2

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

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

希望这会有所帮助，我不是一个真正的建筑专家。

于 2011-08-03T17:59:05.153 回答
2

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

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

于 2011-08-03T18:36:05.290 回答
2

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

于 2011-08-03T18:44:51.107 回答
0

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

于 2011-11-30T23:44:51.743 回答