直接映射指令缓存与使用 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次未命中，为直接映射的LRU提供了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%命中率。

这样做是因为：

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

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