caching - What Are Conflict Misses Exactly?

Question

I'm learning about basic cache concepts and the different types of cache misses. I understood the Compulsory types of misses but I'm having a hard time wrapping my head around the conflict and capacity types of misses! I still have to learn about replacement algorithms for the cache. I've read other questions on this site about this topic, but information on those other questions have been conflicting or vague regarding capacity and conflict misses. I'm hoping that on this one my question will be answered.

For example let's say that we have a 2 way associative cache with 4 sets. Let's talk about the first set that can store two cache lines/blocks(because it's a two way associative cache). I will now list the order of reads called from the processor. All of these addresses that are being read will just fall into the first set for simplicity sake.

-read address one (no cache line in set one for this address. This would be a compulsory cache miss. Data is copied from memory to the first cache line in this set).

-read address two (no cache line in set one for this address. This would also be a compulsory cache miss. Data is copied from memory to the second cache line in this set).

The first set of the cache is now "warmed up" meaning that the set is filled up to capacity with valid cache lines in them. Let's now try to access an address that would also fall into the first set.

-read address three (no cache line in set one for this address. Out of space in set one for anymore cache lines to be written.)

We run into the problem of trying to get a new cache line from memory into set number one but set one is fully occupied with two cache lines. In this situation you would have to use cache replacement policies. This problem is extremely prevalent in direct mapped cache. The way to mitigate this problem would be to increase the associativity of each set(meaning to increase the amount of cache lines that can be stored in one set).

My question is if this situation would be a compulsory or conflict miss? Or would a conflict miss affect all sets? What's the difference and how would each of them work in my example I wrote above? As said before, other questions on the site didn't really make sense to me so I'm hoping that I will figure this out soon.

标签： cachingcpu-architecturecpu-cache

Answer 1

首先，我将给出最初在Mark Donald Hill 的论文中介绍的这些术语的精确定义，然后给出更常见的松散定义。

考虑具有以下特征的缓存：

• 它不支持硬件预取。由于传入的请求，行只能填充到缓存中。
• 它是阻塞的，这意味着它不会在当前请求完全完成之前开始处理请求。
• 只有一个代理，即一个处理器，可以改变缓存的内容。系统中的任何其他单元都不会导致线路无效、替换或填充。
• 所有未命中的高速缓存访​​问都会导致目标高速缓存行被完全提取并填充到高速缓存中。
• 现有高速缓存行被驱逐或失效的唯一方法是为另一个要填充的空间腾出空间。否则，它将在缓存中始终处于有效状态。

令T为不跨越行边界的访问序列，并且所有这些访问都是按需访问（如果有的话，没有软件预取，也没有来自较低编号高速缓存级别的硬件预取）。每次访问都算作一次未命中或命中。令M(N, S)表示具有上述所有特征的高速缓存中发生的未命中数，其中N是路数，S是集合数。请注意，M(N, S)必须是非负整数，N和S必须是正整数。这是正在评估的缓存。可以基于它定义另外两种缓存模型。设M(N*S, 1)表示缓存中发生的未命中数，除了它有N*S路和一组之外，它在所有方面都相同。最后，让M(∞, 1)表示缓存中发生的未命中数，除了它有无限数量的路和一个集合（集合的数量在这里并不重要）之外，它在所有方面都是相同的。

现在想象一下，所有三个缓存模型都在使用相同的输入T并行模拟，并且所有缓存都是空的（即冷启动）。强制未命中是在具有无限多个高速缓存路的高速缓存中发生的高速缓存未命中。当且仅当它是T中对同一缓存行的第一次访问时，无限缓存中的访问未命中。如果在无限模型中发生强制未命中，那么其他两个模型中也必然会发生。强制未命中的数量是M(∞, 1)，它是非负数。

容量未命中是在完全关联模型中发生的缓存未命中，但在无限容量模型中不会发生。因此，容量未命中的数量为M(N*S, 1) - M(∞, 1)，这是非负数。当且仅当访问不是对高速缓存行的第一次访问并且替换策略已选择要由先前访问的行替换的行时，才会在完全关联模型中发生容量丢失。例如，如果替换策略是 LRU，当且仅当访问不是对缓存行的第一次访问并且到目前为止访问的唯一缓存行的总数超过缓存的容量时，才会发生容量丢失。

冲突未命中是在研究模型中发生的缓存未命中，但在完全关联模型和无限容量模型中均未发生。当且仅当它不是容量未命中且不是强制未命中时，未命中才是冲突未命中。如果正在研究的模型是完全关联的，则冲突未命中的数量为零。最初定义的冲突未命中数为M(N, S) - M(N*S, 1)。仅当在完全关联模型中丢失的所有访问在主模型中也丢失时，此数量才是非负的。虽然两个模型中的强制缺失是相同的，但并非所有在完全关联模型中缺失的其他访问也会在主模型中缺失，反之亦然。这取决于更换政策。参见，例如：完全关联的缓存能否比直接映射缓存具有更高的未命中率？. 因此，冲突未命中的数量可能为负数。但是，如果以任何其他方式计算冲突未命中的数量，则所有三种类型的未命中计数的总和可能大于未命中的总数。

有了开头提供的特性，没有其他类型的未命中。我想出了这个特征列表。论文中没有提到它们，因为当时大多数缓存设计都很简单，而且无论如何都有这些特点。但是在实际系统中使用的更现代的缓存更加复杂。

现在您应该能够根据您的示例中的访问“读取地址三”自行确定未命中的类型。

当人们使用“冲突缺失”和“容量缺失”这两个术语时，它们并不真正意味着这些精确的定义，而是在精神上指代这些定义，这种情况并不少见。可以通过更改正在访问的数据结构的布局来减少冲突未命中。可以通过减小工作集大小来减少容量缺失。当您想在真实处理器上测量这些指标时，您必须根据支持的性能监控功能来定义它们，而您无法像在模拟器中那样扩展这些功能。

在实验评估环境中使用这些术语时，准确定义这些术语很重要，因为它们没有标准定义。否则，它们将是模棱两可的，没有人能确定测量的是什么。如果在没有数字的讨论中使用，那么可以松散地使用，因为每个人都知道他们在精神上的意思。

我已经阅读了本网站上有关此主题的其他问题，但关于这些其他问题的信息在容量和冲突未命中方面一直存在冲突或含糊不清。

如果您提供这些帖子的链接，那就太好了。如果其他人发布了一个很好的答案并且可能只需要很小的改进，那么就没有必要从头开始写一个。否则，其中一些可以作为重复项关闭，以便像您这样试图获得答案的其他人可以直接指向正确的答案，而无需每个人都在混乱中费力。