synchronization - CPU 中的相关负载重新排序

Question

我一直在阅读Memory Barriers: A Hardware View For Software Hackers ，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 值(因为 CB1 还没有处理对 p 的失效请求。)

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

加载后重新排序加载

存储后重新排序加载

商店后重新订购的商店

加载后重新排序的商店

原子指令与负载重新排序。

与商店重新排序的原子指令。

这让我想知道需要什么硬件支持来防止依赖加载重新排序。

一个可能的答案是所有其他架构(IA64)都没有分区缓存，因此不会遇到这个问题，也不需要明确的硬件支持。

任何见解？

Answer 1

简短的回答:

在乱序处理器中，加载存储队列用于跟踪和强制执行内存排序约束。 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和 B我们是一样的。但不像 LD之间的依赖和 ADD ， ST之间可能存在的依赖关系和 LD在发出指令(开始执行)时未知。

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

因此，回到伪代码示例，您可以想象 LD 的情况。在 ST 之前执行(也许 R1 中所需的值由于某种原因没有准备好)。但是当 ST执行它看到地址 A和 B是相同的。所以 LD真的应该读取 ST 产生的值，而不是缓存中已经存在的陈旧值。结果 LD将需要重新执行，以及在 LD 之后出现的任何指令。 .有多种优化方法可以减少部分开销，但基本思想仍然成立。

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

内存排序规则

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

阿尔法示例

在依赖加载重新排序的情况下，处理器必须跟踪此信息以供自己使用，但 Alpha ISA 不要求它确保其他处理器看到此排序。下面是如何发生这种情况的一个示例(我引用自 this link )

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

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

The anomalous behavior is currently only possible on a 21264-based system. And obviously you have to be using one of our multiprocessor servers. Finally, the chances that you actually see it are very low, yet it is possible.

Here is what has to happen for this behavior to show up. Assume T1 runs on P1 and T2 on P2. P2 has to be caching location y with value 0. P1 does y=1 which causes an "invalidate y" to be sent to P2. This invalidate goes into the incoming "probe queue" of P2; as you will see, the problem arises because this invalidate could theoretically sit in the probe queue without doing an MB on P2. The invalidate is acknowledged right away at this point (i.e., you don't wait for it to actually invalidate the copy in P2's cache before sending the acknowledgment). Therefore, P1 can go through its MB. And it proceeds to do the write to p. Now P2 proceeds to read p. The reply for read p is allowed to bypass the probe queue on P2 on its incoming path (this allows replies/data to get back to the 21264 quickly without needing to wait for previous incoming probes to be serviced). Now, P2 can derefence P to read the old value of y that is sitting in its cache (the inval y in P2's probe queue is still sitting there).

How does an MB on P2 fix this? The 21264 flushes its incoming probe queue (i.e., services any pending messages in there) at every MB. Hence, after the read of P, you do an MB which pulls in the inval to y for sure. And you can no longer see the old cached value for y.

Even though the above scenario is theoretically possible, the chances of observing a problem due to it are extremely minute. The reason is that even if you setup the caching properly, P2 will likely have ample opportunity to service the messages (i.e., inval) in its probe queue before it receives the data reply for "read p". Nonetheless, if you get into a situation where you have placed many things in P2's probe queue ahead of the inval to y, then it is possible that the reply to p comes back and bypasses this inval. It would be difficult for you to set up the scenario though and actually observe the anomaly.

The above addresses how current Alpha's may violate what you have shown. Future Alpha's can violate it due to other optimizations. One interesting optimization is value prediction.

概括

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