CPU 中的相关负载重新排序

2023-12-24

我一直在阅读内存屏障：软件黑客的硬件视图 http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf，保罗·E·麦肯尼 (Paul E. McKenney) 撰写的一篇非常受欢迎的文章。

该论文强调的一件事是，像 Alpha 这样的弱有序处理器可以重新排序相关负载，这似乎是分区缓存的副作用

论文摘录：

1 struct el *insert(long key, long data)
2 {
3     struct el *p;
4     p = kmalloc(sizeof(*p), GPF_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data; 
9     smp_wmb();
10    head.next = p;
11    spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {
16     struct el *p;
17     p = head.next;
18     while (p != &head) {
19         /* BUG ON ALPHA!!! */
20         if (p->key == key) {
21             return (p);
22         }
23         p = p->next;
24     };
25     return (NULL);
26 }

有 2 个处理器 CPU0 和 CPU1。
每个CPU有2个缓存体CB0（奇数地址），CB1（偶数地址）。
Head 位于 CB0，P 位于 CB1。
insert() 具有写屏障，可确保第 6-8 行首先在总线中失效，然后在第 10 行失效。
然而，执行搜索的另一个处理器可能会轻载CB0而重载CB1。
这意味着处理器领先于 head 的最新值，但 p 的旧值（因为 p 的失效请求尚未被 CB1 处理。）

问题：看起来所有架构都期望 Alpha 荣誉相关负载。例如：IA64 可以对以下内容进行重新排序，但相关负载重新排序除外。

加载后重新排序加载
存储后重新排序加载
商店重新排序后
加载后重新排序的商店
原子指令通过负载重新排序。
原子指令与商店重新订购。

这让我想知道需要什么硬件支持来防止相关负载重新排序。

一个可能的答案是所有其他体系结构（IA64）没有分区缓存，因此不会遇到此问题，并且不需要显式硬件支持。

有什么见解吗？

简短回答：

在乱序处理器中，加载存储队列用于跟踪和强制执行内存排序约束。 Alpha 21264 等处理器具有必要的硬件来防止相关负载重新排序，但强制执行这种相关性可能会增加处理器间通信的开销。

长答案：

依赖性跟踪的背景

这可能最好用一个例子来解释。假设您有以下指令序列（为了简单起见，使用伪代码指令）：

ST R1, A       // store value in register R1 to memory at address A
LD B, R2       // load value from memory at address B to register R2
ADD R2, 1, R2  // add immediate value 1 to R2 and save result in R2

在此示例中，之间存在依赖关系LD和ADD操作说明。这ADD读取值R2所以它不能执行，直到LD使该值可用。这种依赖性是通过寄存器实现的，并且处理器的发出逻辑可以跟踪它。

然而，两者之间也可能存在依赖关系。ST和LD，如果地址A and B我们是一样的。但与之间的依赖不同LD和ADD，之间可能的依赖关系ST和LD在发出指令（开始执行）时未知。

处理器不会在问题时尝试检测内存依赖性，而是使用称为加载-存储队列的结构来跟踪它们。该结构的作用是跟踪已发出但尚未退役的指令的挂起加载和存储的地址。如果存在内存顺序冲突，则可以检测到这一点，并且可以从发生冲突的点重新开始执行。

因此，回到伪代码示例，您可以想象这样一种情况：LD在之前执行ST（也许 R1 中所需的值由于某种原因尚未准备好）。但当ST执行它会看到该地址A and B是相同的。所以LD确实应该读取所产生的值ST，而不是缓存中已经存在的过时值。结果是LD需要重新执行，以及之后出现的任何指令LD。有多种优化方法可以减少部分开销，但基本思想是成立的。

正如我之前提到的，检测这种依赖性的逻辑存在于所有允许推测执行内存指令的乱序处理器（包括 Alpha 处理器）中。

内存排序规则

然而，内存排序规则不仅仅限制处理器从其自己的内存操作中看到结果的顺序。相反，内存排序规则限制了在一个处理器上执行的内存操作对其他处理器可见的操作的相对顺序。

阿尔法示例

在依赖负载重新排序的情况下，处理器必须跟踪此信息以供自己使用，但 Alpha ISA 不要求它确保其他处理器看到此排序。下面是如何发生这种情况的一个示例（我引用了这个链接 http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html)

Initially: p = & x, x = 1, y = 0

    Thread 1         Thread 2
--------------------------------
  y = 1         |    
  memoryBarrier |    i = *p
  p = & y       |
--------------------------------
Can result in: i = 0

目前，该异常行为仅可能出现在基于 21264 的计算机上系统。显然您必须使用我们的多处理器之一服务器。最后，你真正看到它的机会非常低，但这是可能的。

以下是要出现此行为所必须发生的情况。假设T1 在 P1 上运行，T2 在 P2 上运行。 P2 必须缓存位置 y，其值为 0。 P1 执行 y=1，这会导致向 P2 发送“无效 y”。这 invalidate进入P2的传入“探测队列”；随你便看，问题的出现是因为理论上这会无效坐在探测队列中，而不在 P2 上执行 MB。无效的是此时立即确认（即，您不必等待它在发送之前实际上使 P2 缓存中的副本无效致谢）。因此，P1可以通过它的MB。它继续写入 p.现在P2继续读取p。阅读 p 的回复允许在其传入路径上绕过 P2 上的探测队列（这允许回复/数据快速返回到 21264，无需等待之前的传入探测得到服务）。现在，P2可以取消引用 P 以读取位于其缓存中的 y 的旧值（P2 的探测队列中的无效 y 仍然存在）。

P2 上的 MB 如何解决这个问题？ 21264 刷新其输入探头每个 MB 都有队列（即，为其中的任何待处理消息提供服务）。因此，在读取 P 之后，您执行一个 MB，将 inval 拉入 y 一定。并且您无法再看到 y 的旧缓存值。

尽管上述情况在理论上是可能的，但可能性观察到的问题是极其微小的。原因是即使你正确设置缓存，P2 也可能有足够的为探测队列中的消息（即无效）提供服务的机会在收到“read p”的数据回复之前。尽管如此，如果你陷入这样一种情况：你在 P2 的探针中放置了很多东西队列在对 y 的无效之前，则有可能对 p 的回复返回并绕过此 inval。你会很难设置场景并实际观察异常情况。

上述内容解决了当前 Alpha 可能如何违反您的规定显示。由于其他优化，未来的 Alpha 可能会违反它。一有趣的优化是价值预测。

Summary

所有乱序处理器中都已经存在强制执行相关负载排序所需的基本硬件。但确保所有处理器都能看到这种内存排序会给处理缓存行失效增加额外的限制。它也可能在其他场景中增加额外的限制。然而，在实践中，对于硬件设计人员来说，弱 Alpha 内存模型的潜在优势似乎不值得以软件复杂性和需要更多内存屏障的额外开销为代价。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)