时间戳

首页 > 解决方案 > 完全关联的缓存能否比直接映射缓存具有更高的未命中率？

caching - 完全关联的缓存能否比直接映射缓存具有更高的未命中率？

问题描述

以下是一个面试问题：

为什么完全关联缓存的未命中率可能高于直接映射缓存？

我认为这根本不可能。任何人都可以分享一些对此的见解吗？

标签： cachingcpu-architecturecpu-cache

解决方案

你应该假设它们的大小相同吗？如果不是，那么如果大多数未命中是“容量”未命中，而不是冲突未命中，则较小的完全关联高速缓存仍然会丢失更多。

如果它们的大小相同，那么可能性就会小很多，因此您必须开始考虑病理病例。替换政策的不幸案例可能会导致不相关的失误驱逐一条以后有用的线路。完全关联缓存中的未命中可以驱逐任何当前行，并且必须选择一个。（并且具有高关联性，LRU 会占用很多位，所以它可能不是真正的 LRU。即使是真正的 LRU，你当然可以构造一个仍然驱逐更多行的序列。）

考虑以下事件序列：

  • 未命中将一行带入缓存。将来会有用，当然硬件还不能知道，因为它看不到未来。
  • 许多其他强制未命中其他行（因此没有缓存可以帮助它们），地址（对于直接映射或集合关联缓存）没有别名相同的集合，即具有不同的索引。因此，它们不可能扰乱直接映射的未来价值线，但它们可以用于完全关联：一切都在一个大集合中。如果这只是在一个大数组上循环也可以工作（除了将别名具有未来值的那一行）。
  • 这里也可能有一些命中，但如果没有命中则更容易验证正确性。只要没有一条线相互别名，所以我们
  • 对第一行的另一个访问。 直接映射肯定仍然有缓存，因为以前的访问没有这个索引。Associative 将驱逐它，除非替换策略以某种方式预测或猜测未来并且从未驱逐它，尽管其他线路的所有来来往往。

可能有更合理的例子，平均命中率不是那么低。例如，简单地循环一个数组，从而在顺序读取每个字节或字时从缓存中受益。

关联缓存有更多空间供其他访问别名同一集合，因为集合较少。通常，替换策略会为您的工作负载做出有用的选择，因此这种行为只有在击败它的情况下才有可能。

相关：https ://en.wikipedia.org/wiki/Adaptive_replacement_cache https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/ - 当缓存爆破循环时，自适应替换可以帮助保留一些行在一个巨大的阵列上运行。

自适应替换策略可以使关联缓存更能抵抗这种直接映射缓存可以击败它的最坏情况。当然，遍历一个巨大的数组通常会完全清除直接映射的缓存。这里的特别之处在于，我们避免了任何会为将要命中的线产生别名的东西。因此，对于涉及很多行但碰巧跳过一行的访问序列，循环遍历链表更合理。

还相关：LRU 的病态最坏情况：Bélády 的虚拟内存页面替换异常，其中可以构建 LRU 因更多页帧而变得更糟但 FIFO 没有的情况。CPU 缓存的类似情况会随着每组更多的方式而变得更糟，对于对一组的相同访问序列。

当然，没有人说全关联缓存是真正的 LRU，正如我之前所说，这在实践中不太可能。

推荐阅读