关联缓存模拟 - 处理故障方案

Question

在模拟完全关联缓存(在MIPS程序集中)时,基于在线阅读的一些信息,我想到了一些问题.

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

查找插槽:最多一个插槽应匹配.如果有多个匹配的插槽,则您有一个错误的全关联缓存方案.在完全关联的缓存的任何槽中,您永远不应该有多个缓存行副本.维护多份副本很难,而且没有意义.这些插槽可用于其他缓存行.

这是否意味着我应该一直检查整个标签列表以检查第二次匹配？毕竟,如果我不这样做,我永远不会"意识到"缓存的错误,但是,每次检查似乎都是非常低效的.

在我检查的情况下,不知何故我设法找到第二个匹配,意味着错误的缓存方案,那我该怎么办？虽然最好的答案是修复我的实现,但我感兴趣的是如果出现这种情况,如何在执行期间处理它.

Answer 1

如果多个有效槽与一个地址匹配，则意味着当执行先前对同一地址的搜索时，未使用应与该地址匹配的有效槽（可能是因为一开始就没有检查）或者使用多个无效槽来存储根本不在高速缓存中的行。

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

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

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

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

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

• 该行已在缓存中，无需执行任何操作
• 该行不在缓存中，但有无效的可用槽：将新行放入可用槽之一
• 该行不在高速缓存中，但没有可用的无效插槽。必须驱逐另一条有效行并用新行取代它。
  
  • 选择驱逐候选人会对绩效产生影响。干净的缓存线可以被免费驱逐，但如果选择不当，可能会在不久的将来导致另一次缓存未命中。考虑是否除了一个缓存行之外的所有缓存行都脏了。如果仅驱逐干净的高速缓存行，则两个地址之间交替的许多顺序读取将导致每次读取时发生高速缓存未命中。缓存失效是 Comp Sci 中的两个难题之一（另一个是“命名事物”），并且超出了这个确切问题的范围。

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

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

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

• 如果该地址在缓存中，则尝试锁定该槽并返回该槽。如果插槽已被锁定，则停止直至其空闲。
• 如果该地址不在缓存中，则查找无效或有效但可驱逐的未锁定插槽。

在这种情况下，我们实际上可能会遇到两个插槽共享相同地址的情况。如果两个核心都尝试写入不在缓存中的地址，它们最终将获得不同的插槽，并且会出现重复行。首先让我们考虑一下可能发生什么：

• 这两行都是从主存储器读取的。它们的值相同并且都是干净的。驱逐是正确的。
• 这两行都被写入。两者都会很脏，但可能不相等。这是一个竞争条件，应用程序应该通过发出内存栅栏或其他一些内存排序指令来解决。我们无法猜测应该使用哪一个，如果没有缓存，竞争条件将持续存在 RAM 中。驱逐是正确的。
• 一行是读取，一行是写入。写是脏的，但读是干净的。如果没有中间缓存，这种竞争条件将再次保留在 RAM 中，但读者可能会看到不同的值。逐出干净的行是由 RAM 决定的，并且还具有始终支持先读后写顺序的副作用。

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

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

• 在两个并发读取的情况下，两条线是相同的、未锁定的并且可以互换。核心使用哪条线进行后续操作并不重要。
• 在并发写入的情况下，两条线不同步，但相互不可见。尽管这造成的竞争条件很不幸，但它仍然会导致合理的内存排序，就好像废弃行上发生的所有操作都发生在已清理行上的任何操作之前。
• 如果读取和写入同时发生，则脏行对于读取核心来说是不可见的。然而，干净的行对两个核心都是可见的，并且会导致写入者的内存排序被破坏。未来的写入甚至可能导致它锁定两者（因为两者都是脏的）。

最后一种情况很大程度上阻碍了脏线比干净线更受欢迎。这至少迫使一些额外的硬件首先查找脏线，只有在没有找到脏线的情况下才清洁线。现在我们有了一个新的并发缓存实现：

• 如果地址在缓存中并且是脏的并且由请求核心拥有，则使用该插槽
• 如果地址在缓存中但干净
  • 对于读取，只需使用该插槽
  • 对于写入，将插槽标记为脏并使用该插槽
• 如果地址不在缓存中并且存在无效槽，则使用无效槽
• 如果没有无效插槽，则逐出一行并使用该插槽。

我们已经很接近了，但实施中仍然存在漏洞。如果两个内核访问相同的地址但不同时怎么办？最简单的事情可能只是说脏线对于其他核心来说确实是不可见的。在缓存中但脏与根本不在缓存中相同。

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

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