caching - 组关联缓存的缓存命中率 : I don't understand this diagram

Question

标题可能不太好，但我找不到更好的标题。

我们有作业要做，但我没有交，因为我听不懂。现在因为结束了，我们得到了解决方案...现在我正在尝试使用解决方案来理解任务，因为尝试理解我们教授的复杂脚本对我来说是浪费时间。

<小时/>

任务:

We have a direct mapped cache with following access frequency on main memory blocks:

2 5 0 13 2 5 10 8 0 4 5 2

What's the hitting quote (aka hit rate) if the cache is a set-associative cache with set size 4 and FIFO?

来自my last question about direct-mapped caches ，我学会了如何计算点击引用，顺便说一句非常感谢。我唯一的问题是我不明白这些数字是如何放置在表格中的。

我想像编程一样:0-3是数组1，其他0-3是数组2。我们取出缓存的第一个数字 2 并将其放入 array1 中，因此它位于 array1[0] 中。然后我们对下一个数字执行相同的操作，取 5 并将其放入 array2[0] 中。现在取出下一个数字 0 并将其放入数组[1]中。

但是看起来模式是错误的，直到表的第 4 行为止都是正确的，但随后就错误了......

为什么表格中的数字是这样排列的？

解决方案:

Answer 1

您可能想知道为什么数字与地址不对齐，就像直接映射的情况一样。该图中发生的情况是，项目从左到右放入集合中，仅此而已，因为集合最初是空的。值 2、0、10 和 8 映射到最左边的集合。 2 首先出现，因此它位于最左边的列中。然后将 0 放置在下一个可用位置。 2 再次出现，即括号中所示的“命中”。然后 10 出现并进入第三位。 8 转到第四个位置，并且缓存 block 现在已满。 0 重复出现，并且命中，因为它仍在缓存中，位于第二个位置。现在出现了 4 个。缓存集已满:必须剔除某些内容。 2 被踢出(可能是由于最近最少使用 (LRU) 替换策略)并被 4 取代。这就是为什么 4 位于最左边的列；它已经取代了 2。现在 2 再次出现并且不再在缓存中，因为它刚刚被踢出。现在最近最少使用的缓存项是 0，因此它被踢出，2 现在位于第二位。

请注意，真正的四路组关联缓存并不总是使用完整的 block 范围 LRU 替换策略，因为需要进行一些进一步的简化来加速它们。

顺便说一句，地址按照简单模 4 分配到集合中。偶数地址分配到左侧集合，奇数地址分配到右侧集合，情况并非如此:

    set 0             set 1
0   1   2   3  |   0   1   2   3    <-   addr modulo 4
---------------+-----------------
0   1   2   3  |   4   5   6   7    <-   full addr
8   9  10  11  |  12  13  14  15  

可以看到，这与表中的内容是一致的；当然，除了地址与它们的模 4 位置不匹配之外:根据替换策略，它们在每组中被赋予任意位置。