algorithm - 直接映射指令缓存 VS 使用 LRU 替换的全关联指令缓存

Question

对于小型缓存，直接映射指令缓存有时可以胜过使用 LRU 替换的完全关联指令缓存。

谁能用示例访问模式解释这是如何实现的？

Answer 1

这可能发生在小缓存中。让我们比较大小为 2 的缓存。

在我的示例中，直接映射的“DM”缓存将使用 A 行作为奇数地址，使用 B 行作为偶数地址。

LRU 缓存将使用最近最少使用的行来存储未命中的值。

我建议的访问模式是 13243142(重复任意多次)。

以下是错误缓存算法的行为细目:

H - hits
M - misses

----- time ------>>>>>

Accessed:    1 | 3 | 2 | 4 | 3 | 1 | 4 | 2
             \   \   \   \   \   \   \   \ 
LRU  A    ? | ? | 3 | 3 | 4 | 4 | 1 | 1 | 2 |
     B    ? | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
             M   M   M   M   M   M   M   M   

DM   A    ? | 1 | 3 | 3 | 3 | 3 | 1 | 1 | 1 |
     B    ? | ? | ? | 2 | 4 | 4 | 4 | 4 | 2 |
             M   M   M   M   H   M   H   M   

这为 LRU 提供了 8 个未命中，为直接映射提供了 6 个。让我们看看如果这种模式永远重复会发生什么:

----- time ------>>>>>

Accessed:    1 | 3 | 2 | 4 | 3 | 1 | 4 | 2
             \   \   \   \   \   \   \   \ 
LRU  A      | 2 | 3 | 3 | 4 | 4 | 1 | 1 | 2 |
     B      | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
             M   M   M   M   M   M   M   M   

DM   A      | 1 | 3 | 3 | 3 | 3 | 1 | 1 | 1 |
     B      | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 2 |
             H   M   H   M   H   M   H   M   

因此直接映射缓存将有 50% 的命中率，优于 LRU 的 0% 命中率。

之所以这样工作是因为:

• 在此模式中重复的任何地址在之前的 2 次访问中都没有被访问过(并且这两次访问都不同)，因此 LRU 缓存总是会丢失。
• DM 缓存有时会丢失，因为该模式的设计使其利用上次使用相应行时存储的内容。

因此，一旦可以为更大的缓存大小构建类似的模式，但缓存大小越大，这种模式就需要越长。这符合直觉，即对于较大的缓存，以这种方式利用它们会更加困难。