language-agnostic - 关联缓存模拟 - 处理错误方案

Question

在模拟完全关联的缓存(在 MIPS 程序集中)时，根据在线阅读的一些信息，想到了几个问题；

根据马里兰大学的一些笔记

Finding a slot: At most, one slot should match. If there is more than one slot that matches, then you have a faulty fully-associative cache scheme. You should never have more than one copy of the cache line in any slot of a fully-associative cache. It's hard to maintain multiple copies, and doesn't make sense. The slots could be used for other cache lines.

这是否意味着我应该一直检查整个标签列表以检查第二个匹配项？ 毕竟，如果我不这样做，我将永远不会“意识到”缓存的错误，但是，每次检查似乎效率很低。

如果我确实进行了检查，并且以某种方式设法找到了第二个匹配项，这意味着缓存方案有问题，那么我该怎么办？ 虽然最好的答案是修复我的实现，但如果出现这种情况，我对如何在执行期间处理它很感兴趣。

Answer 1

如果多个有效槽与地址匹配，则意味着在执行先前对同一地址的搜索时，未使用本应与地址匹配的有效槽(可能是因为它没有首先检查)或者使用了多个无效槽来存储根本不在缓存中的行。

毫无疑问，这应该被视为一个错误。

但是，如果我们刚刚决定不修复该错误(也许我们宁愿不将那么多硬件用于更好的实现)，那么最明显的选择是选择一个使插槽失效的插槽。然后它将可用于其他缓存行。

至于如何选择使哪一个无效，如果其中一个重复行是干净的，则优先于脏缓存行使该行无效。如果超过缓存行是脏的并且他们不同意，那么您需要修复更大的错误，但无论如何您的缓存不同步，您选择哪个可能无关紧要。

编辑:这是我如何实现硬件来做到这一点:

首先，从重复假设开始并没有多大意义，而是我们稍后会在适当的时候解决这个问题。缓存新行时必须发生的事情有几种可能性。

该行已在缓存中，无需任何操作

该行不在缓存中，但有可用的无效插槽:将新行放入可用插槽之一

该行不在缓存中，但没有可用的无效插槽。另一条有效线路必须被驱逐，新线路取而代之。

选择驱逐候选人会影响绩效。干净的缓存行可以被免费驱逐，但如果选择不当，可能会在不久的将来导致另一个缓存未命中。考虑是否除了一个缓存线之外的所有缓存线都是脏的。如果只有干净的缓存行被逐出，那么在两个地址之间交替进行的许多顺序读取将导致每次读取时缓存未命中。缓存失效是 Comp Sci 中的两个难题之一(另一个是“命名事物”)，并且超出了这个确切问题的范围。

我可能会执行一个搜索来检查正确的插槽以对其中的每一个进行操作。然后另一个块将从该列表中选择第一个并对其进行操作。

现在，回到问题。重复项可能进入缓存的条件是什么。如果内存访问是严格有序的，并且实现(如上)是正确的，我认为根本不可能重复。因此无需检查它们。

现在让我们考虑一个更难以置信的情况，其中一个缓存在两个 CPU 内核之间共享。我们将只做可以工作的最简单的事情，并为每个内核复制除缓存本身之外的所有内容。因此，不共享时隙搜索硬件。为了支持这一点，每个插槽有一个额外的位用作互斥锁。搜索硬件不能使用被另一个内核锁定的插槽。具体来说，

如果地址在缓存中，尝试锁定插槽并返回该插槽。如果插槽已被锁定，则停止直到它空闲为止。

如果地址不在缓存中，则查找无效或有效但可驱逐的未锁定插槽。

在这种情况下，我们实际上最终会处于两个插槽共享相同地址的位置。如果两个内核都尝试写入不在缓存中的地址，它们最终将获得不同的插槽，并且会出现重复的行。首先让我们想想可能发生的事情:

这两行都是从主内存中读取的。它们将具有相同的值，并且它们都将是干净的。驱逐也是正确的。

两行都是写。两者都会脏，但可能不相等。这是一个竞争条件，应该由应用程序通过发出内存栅栏或其他一些内存排序指令来解决。我们无法猜测应该使用哪一个，如果没有缓存，竞争条件将持续到 RAM 中。驱逐也是正确的。

一行是读，一行是写。写是脏的，但读是干净的。如果没有中间缓存，这种竞争条件将再次存在于 RAM 中，但读者可能会看到不同的值。逐出干净的行是 RAM 的正确做法，并且还具有总是有利于读取然后写入顺序的副作用。

所以现在我们知道该怎么做，但是这个逻辑属于哪里。首先让我们想想如果我们什么都不做会发生什么。对任一核上相同地址的后续缓存访问都可以返回任一行。即使两个核心都没有发出写入，读取也可能会不断出现不同，在两个值之间交替。这打破了所有关于内存排序的想法。

一种解决方案可能只是说脏线仅属于一个核心，该线不是脏线，而是脏线并由另一个核心拥有。

在两个并发读取的情况下，两行是相同的、未锁定且可互换的。核心为后续操作获取哪条线并不重要。

在并发写入的情况下，两条线不同步，但相互不可见。尽管这造成的竞争条件令人遗憾，但它仍会导致合理的内存排序，就好像在丢弃的行上发生的所有操作都发生在已清理行上的任何操作之前一样。

如果读取和写入同时发生，则脏线对读取核心不可见。但是，干净的线条对两个内核都是可见的，并且会导致编写器的内存排序中断。 future 的写入甚至可能导致它同时锁定两者(因为两者都是脏的)。

最后一种情况几乎阻碍了脏线比干净线更受欢迎。这迫使至少一些额外的硬件首先寻找脏线，只有在没有发现脏线时才清洁线。所以现在我们有了一个新的并发缓存实现:

如果地址在缓存中并且是脏的并且由请求核心拥有，请使用该插槽

如果地址在缓存中但干净

对于读取，只需使用该插槽

对于写入，将插槽标记为脏并使用该插槽

如果地址不在缓存中并且存在无效槽位，则使用无效槽位

如果没有无效插槽，则驱逐一行并使用该插槽。

我们越来越近了，实现中仍然存在漏洞。如果两个内核访问相同的地址但不是同时访问会怎样。最简单的可能就是说脏线对其他核心来说真的是不可见的。在缓存中但脏与根本不在缓存中相同。

现在我们要考虑的实际上是为应用程序提供同步工具。我可能会做一个工具，如果它很脏，它只会明确地刷新一条线。这只会调用在驱逐期间使用的相同硬件，但将该行标记为干净而不是无效。

简而言之，我们的想法是处理重复项不是通过删除它们，而是通过确保它们不会导致进一步的内存排序问题，并将重复数据删除工作留给应用程序或最终驱逐。