5

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

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

找到一个插槽：最多匹配一个插槽。如果匹配的插槽不止一个，则说明您的全关联缓存方案有问题。在全关联缓存的任何插槽中，您永远不应拥有超过一个缓存行副本。很难维护多个副本，而且没有意义。这些插槽可用于其他高速缓存行。

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

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

4

1 回答 1

4

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

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

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

至于如何选择使哪一个无效，如果重复行之一是干净的，则优先使该重复行无效，而不是脏缓存行。如果超过缓存线是脏的并且他们不同意你有一个更大的错误要修复，但无论如何你的缓存不同步，你选择哪个可能并不重要。

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

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

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

我可能会实施一个搜索来检查每个正确的插槽。然后另一个块将从该列表中选择第一个并对其采取行动。

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

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

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

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

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

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

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

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

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

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

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

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

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

于 2010-12-01T20:19:03.110 回答