什么是冲突未命中？
What Are Conflict Misses Exactly?
我正在学习基本的缓存概念和不同类型的缓存未命中。我了解强制性类型的未命中，但我很难理解冲突和容量类型的未命中！我仍然需要了解缓存的替换算法。我已经在本网站上阅读了有关此主题的其他问题，但有关这些其他问题的信息在容量和冲突未命中方面一直存在冲突或含糊不清。我希望在这个问题上我的问题能得到解答。
例如，假设我们有一个包含 4 个集合的 2 路关联缓存。先说第一个可以存储两个缓存lines/blocks的集合（因为是双路相联缓存）。我现在将列出从处理器调用的读取顺序。为简单起见，所有这些正在读取的地址都将落入第一组。
-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).
第一组缓存现在已“预热”，这意味着该组已填满其中包含有效缓存行的容量。现在让我们尝试访问一个也属于第一组的地址。
-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.)
我们 运行 尝试从内存中获取新缓存行到第一个集合中，但第一个集合已被两个缓存行完全占用。在这种情况下，您将不得不使用 缓存替换策略 。这个问题在直接映射缓存中非常普遍。缓解这个问题的方法是增加每个集合的关联性（意味着增加可以存储在一个集合中的缓存行的数量）。
我的问题是这种情况是强制错过还是冲突错过？或者冲突未命中会影响所有集合吗？在我上面写的示例中，它们有什么区别以及如何工作？如前所述，网站上的其他问题对我来说并没有真正意义，所以我希望我能尽快解决这个问题。
首先，我将给出最初在 Mark Donald Hill's dissertation 中介绍的这些术语的精确定义，然后我将给出更为常见的宽松定义。
考虑具有以下特征的缓存：
- 不支持硬件预取。由于传入请求，行只能填充到缓存中。
- 它是阻塞的，这意味着它不会在当前请求完全完成之前开始处理请求。
- 只有一个代理，即处理器，可以更改缓存的内容。系统中没有任何其他单元可以导致行失效、替换或填充。
- 所有未命中的缓存访问都会导致目标缓存行被完全提取并填充到缓存中。
- 现有缓存行被逐出或失效的唯一方法是使 space 填充另一个缓存行。否则，它将在缓存中始终处于有效状态。
设 T 是不跨越线边界的访问序列，并且所有这些都是按需访问（没有软件预取，也没有来自较低编号缓存的硬件预取水平，如果有的话）。每次访问都将计为一次未命中或命中。令 M(N, S) 表示具有上述所有特征的缓存中发生的未命中数，其中 N 是路数S是组数。请注意 M(N, S) 必须是非负整数并且 N 和 S 必须是正数整数。这是正在评估的缓存。可以基于它定义另外两个缓存模型。令 M(N*S, 1) 表示缓存中发生的未命中数，除了具有 N*S 方式和一套。最后，让 M(∞, 1) 表示缓存中发生的未命中数，除了它有无限多种方式和一组（数量集合在这里并不重要）。
现在想象一下，所有三个缓存模型都使用相同的输入 T 并行模拟，并且所有缓存都为空（即冷启动）。 强制未命中是在具有无限多个缓存路的缓存中发生的缓存未命中。当且仅当它是 T 中对同一缓存行的第一次访问时，无限缓存中的访问未命中。如果无限模型中发生强制未命中，则其他两个模型中也必然会发生。强制未命中数为M(∞, 1)，非负数
capacity miss是cache miss，发生在全关联模型，无限容量模型不会。因此，容量未命中的次数为M(N*S, 1) - M(∞, 1)，为非负数。当且仅当访问不是对高速缓存行的第一个访问并且替换策略已选择要由先前访问的行替换的行时，才会在完全关联模型中发生容量未命中。例如，如果替换策略是LRU，当且仅当访问不是第一个访问缓存行并且到目前为止访问的唯一缓存行的总数超过缓存的容量时，才会发生容量未命中。
A 冲突未命中 是缓存未命中，它发生在正在研究的模型中，但不会出现在全关联模型中，也不会出现在无限容量模型中。未命中是冲突未命中当且仅当它不是容量未命中也不是强制性未命中。如果所研究的模型是完全关联的，则冲突未命中数为零。最初定义的冲突未命中数为 M(N, S) - M(N*S, 1)。仅当全关联模型中未命中的所有访问在主模型中也未命中时，此数量才为非负数。虽然强制未命中在两个模型中是相同的，但并非全关联模型中所有其他未命中的访问也会在主模型中丢失，反之亦然。这取决于更换政策。参见，例如：Can a fully associative cache have a higher miss rate than a direct mapped 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.
如果您能提供这些帖子的链接就好了。如果其他人发布了一个很好的答案并且可能只需要稍作改进，那么就没有必要从头开始写一个。否则，其中一些可以作为重复项关闭，以便其他像您一样试图获得答案的人可以直接指向正确答案，而无需每个人都在混乱中费力。
我正在学习基本的缓存概念和不同类型的缓存未命中。我了解强制性类型的未命中，但我很难理解冲突和容量类型的未命中！我仍然需要了解缓存的替换算法。我已经在本网站上阅读了有关此主题的其他问题，但有关这些其他问题的信息在容量和冲突未命中方面一直存在冲突或含糊不清。我希望在这个问题上我的问题能得到解答。
例如，假设我们有一个包含 4 个集合的 2 路关联缓存。先说第一个可以存储两个缓存lines/blocks的集合（因为是双路相联缓存）。我现在将列出从处理器调用的读取顺序。为简单起见，所有这些正在读取的地址都将落入第一组。
-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).
第一组缓存现在已“预热”，这意味着该组已填满其中包含有效缓存行的容量。现在让我们尝试访问一个也属于第一组的地址。
-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.)
我们 运行 尝试从内存中获取新缓存行到第一个集合中，但第一个集合已被两个缓存行完全占用。在这种情况下，您将不得不使用 缓存替换策略 。这个问题在直接映射缓存中非常普遍。缓解这个问题的方法是增加每个集合的关联性（意味着增加可以存储在一个集合中的缓存行的数量）。
我的问题是这种情况是强制错过还是冲突错过？或者冲突未命中会影响所有集合吗？在我上面写的示例中，它们有什么区别以及如何工作？如前所述，网站上的其他问题对我来说并没有真正意义，所以我希望我能尽快解决这个问题。
首先，我将给出最初在 Mark Donald Hill's dissertation 中介绍的这些术语的精确定义，然后我将给出更为常见的宽松定义。
考虑具有以下特征的缓存：
- 不支持硬件预取。由于传入请求，行只能填充到缓存中。
- 它是阻塞的，这意味着它不会在当前请求完全完成之前开始处理请求。
- 只有一个代理，即处理器，可以更改缓存的内容。系统中没有任何其他单元可以导致行失效、替换或填充。
- 所有未命中的缓存访问都会导致目标缓存行被完全提取并填充到缓存中。
- 现有缓存行被逐出或失效的唯一方法是使 space 填充另一个缓存行。否则，它将在缓存中始终处于有效状态。
设 T 是不跨越线边界的访问序列，并且所有这些都是按需访问（没有软件预取，也没有来自较低编号缓存的硬件预取水平，如果有的话）。每次访问都将计为一次未命中或命中。令 M(N, S) 表示具有上述所有特征的缓存中发生的未命中数，其中 N 是路数S是组数。请注意 M(N, S) 必须是非负整数并且 N 和 S 必须是正数整数。这是正在评估的缓存。可以基于它定义另外两个缓存模型。令 M(N*S, 1) 表示缓存中发生的未命中数，除了具有 N*S 方式和一套。最后，让 M(∞, 1) 表示缓存中发生的未命中数，除了它有无限多种方式和一组（数量集合在这里并不重要）。
现在想象一下，所有三个缓存模型都使用相同的输入 T 并行模拟，并且所有缓存都为空（即冷启动）。 强制未命中是在具有无限多个缓存路的缓存中发生的缓存未命中。当且仅当它是 T 中对同一缓存行的第一次访问时，无限缓存中的访问未命中。如果无限模型中发生强制未命中，则其他两个模型中也必然会发生。强制未命中数为M(∞, 1)，非负数
capacity miss是cache miss，发生在全关联模型，无限容量模型不会。因此，容量未命中的次数为M(N*S, 1) - M(∞, 1)，为非负数。当且仅当访问不是对高速缓存行的第一个访问并且替换策略已选择要由先前访问的行替换的行时，才会在完全关联模型中发生容量未命中。例如，如果替换策略是LRU，当且仅当访问不是第一个访问缓存行并且到目前为止访问的唯一缓存行的总数超过缓存的容量时，才会发生容量未命中。
A 冲突未命中 是缓存未命中，它发生在正在研究的模型中，但不会出现在全关联模型中，也不会出现在无限容量模型中。未命中是冲突未命中当且仅当它不是容量未命中也不是强制性未命中。如果所研究的模型是完全关联的，则冲突未命中数为零。最初定义的冲突未命中数为 M(N, S) - M(N*S, 1)。仅当全关联模型中未命中的所有访问在主模型中也未命中时，此数量才为非负数。虽然强制未命中在两个模型中是相同的，但并非全关联模型中所有其他未命中的访问也会在主模型中丢失，反之亦然。这取决于更换政策。参见，例如：Can a fully associative cache have a higher miss rate than a direct mapped 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.
如果您能提供这些帖子的链接就好了。如果其他人发布了一个很好的答案并且可能只需要稍作改进，那么就没有必要从头开始写一个。否则，其中一些可以作为重复项关闭，以便其他像您一样试图获得答案的人可以直接指向正确答案，而无需每个人都在混乱中费力。