如何在缓存模拟器中查找冲突未命中数

Question

我正在尝试设计一个缓存模拟器。为了找到一个块的缓存命中/未命中，我将它的索引和偏移量与缓存中已经存在的块进行比较。在 n 关联缓存的情况下，我只检查该块可以去的那些缓存条目。

找到命中和冷未命中的数量是微不足道的。如果缓存已满（或者块可以进入的所有条目都已被占用），那么我们就会出现容量缺失。

有人可以告诉我如何找到冲突未命中的数量吗？冲突未命中的定义说：

Conflict misses are those misses that could have been avoided, 
had the cache not evicted an entry earlier

如何确定较早从缓存中删除的条目是否应该或不应该被删除？

Answer 1

从概念上讲，这是衡量未命中类型的方法：

测量以下缓存中相同代码的未命中数 (M)：

1. 无限容量、全关联缓存
2. 有限容量的全关联缓存
3. 有限容量的N路关联缓存

然后

• 强制失误次数 = M1
• 容量未命中次数 = M2-M1
• 冲突未命中数 = M3- 容量未命中数 - 强制未命中数 = M3 - M2

当在模拟器中实际实现这些测量时，您不需要运行三个不同的模拟。Leeor 描述的哈希映射的缺失为您提供了 M1。现在，如果您将哈希映射实现为列表（或一些更有效的数据结构），这样您就永远不会删除条目，但每当访问地址“x”时，请将“x”放在列表的前面。每当进行引用并且它命中列表中的第一个“S”位置（其中 S 是缓存的大小）时，就可以将其计为缓存编号 1 和 2 的命中。实际的缓存模拟（建模 N -way 缓存）给你 M3。因此，实际的缓存模型加上此列表数据结构可以在一次模拟运行中为您提供 M1、M2、M3。

Answer 2

您可以将所有历史地址存储在哈希图中，并在您错过时进行查找 - 如果您错过了缓存但命中了哈希 - 您在某个时刻驱逐了该行。

然而，它的大小可能会增长得相当快。但在大多数情况下，更有趣的是问“我可以将行缓存多一点时间并避免这种错过吗？”。为此，您可以扩展缓存模拟以拥有更多方式（直到您确定的保留行仍然现实的历史深度）。您像以前一样查找缓存，并维护与您使用的相同的 LRU 方法，但如果命中的方式超出了 LRU 年龄方面的“真实”方式计数 - 这是冲突未命中（即 - 该行在那里，但将 LRU 链推回到了应该被驱逐的点）。确保你的 LRU 机制可以这样工作 - 真正的 LRU 应该没问题，因为它保持严格的顺序，基于年龄值的也很好，但其他类型（如伪 LRU 树）可能会变得棘手。