5

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

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

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

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

如何确定之前从缓存中删除的条目是否应该被删除？

4

2 回答 2

5

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

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

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

然后

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

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

于 2014-02-25T14:22:09.020 回答
3

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

然而，这可以在规模上相当迅速地增长。但在大多数情况下，更有趣的是问“我可以将行缓存稍长一点并避免这种错过吗？”。为此，您可以扩展您的缓存模拟以拥有更多方法（直到您确定的历史深度仍然可以保持线条）。您像以前一样查找缓存，并维护您将使用的相同 LRU 方法，但如果被击中的方式超出了 LRU 年龄方面的“真实”方式计数 - 这是一个冲突未命中（即 - 行在那里，但将 LRU 链推回了应该被驱逐的程度）。确保你的 LRU 机制可以这样工作——真正的 LRU 应该没问题，因为它保持严格的顺序，基于年龄值的也可以，

于 2013-08-19T19:25:18.783 回答