相关负载在CPU中重新排序

Question

我一直在阅读内存障碍:软件黑客的硬件视图,这是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 }

1. CPU0和CPU1有2个处理器.
2. 每个CPU具有2个高速缓存存储体CB0(奇数地址),CB1(偶数地址).
3. 头部在CB0中,而CB在CB1中.
4. insert()有一个写屏障,确保第6-8行的无效首先在总线中,然后在第10行无效.
5. 但是,执行搜索的其他处理器可以使CB0轻载并且CB1负载很重.
6. 这意味着处理器引导头的最新值但是p的旧值(因为对于p的无效请求尚未由CB1处理.)

问题: 看起来所有架构都期望Alpha荣誉依赖负载.例如:IA64可以重新排序以下除了依赖负载重新排序之外.

1. 加载后重新加载
2. 存储后加载重新排序
3. 商店在商店后重新订购
4. 商店在装载后重新订购
5. 原子指令与负载重新排序.
6. 原子指令与商店重新排序.

这让我想知道需要哪些硬件支持来防止依赖负载重新排序.

一个可能的答案是所有其他架构(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示例

在依赖负载重新排序的情况下,处理器必须跟踪此信息以供其自己使用,但Alpha ISA不要求它确保其他处理器看到此顺序.如何发生这种情况的一个例子如下(我引用了这个链接)

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上运行P1和T2.P2必须以值0缓存位置y.P1确实y = 1,这导致将"无效y"发送到P2.该无效进入P2的传入"探测队列"; 正如您将看到的那样,问题就出现了,因为这个无效理论上可以位于探测队列中,而不会在P2上执行MB.此时立即确认无效(即,在发送确认之前,您不等待它实际使P2的缓存中的副本无效).因此,P1可以通过它的MB.它继续写p.现在P2继续读取p.读取p的回复允许在其传入路径上绕过P2上的探测队列(这允许回复/数据快速返回到21264,而无需等待先前的传入探测被服务).现在,P2可以解除P以读取位于其缓存中的y的旧值(P2的探测队列中的inval y仍然位于那里).

P2上的MB如何修复此问题？21264在每个MB上刷新其传入的探测队列(即,为那里的任何未决消息提供服务).因此,在读取P之后,你会做一个MB,它肯定会将inval拉入y.并且您无法再看到y的旧缓存值.

即使上述情况在理论上是可能的,但由于它而观察问题的可能性非常小.原因是即使您正确设置了缓存,P2也可能有足够的机会在接收到"read p"的数据回复之前为其探测队列中的消息(即inval)提供服务.尽管如此,如果你遇到的情况是你在P2的探测队列中放置了许多东西,那么p的回复可能会回来并绕过这个值.虽然你很难设置场景并且实际观察到异常现象.

以上内容解决了当前Alpha可能违反您所显示的内容的方式.由于其他优化,未来Alpha可以违反它.一个有趣的优化是价值预测.

摘要

强制执行相关负载排序所需的基本硬件已经存在于所有无序处理器中.但是确保所有处理器都能看到这种内存排序会增加处理缓存行无效的额外限制.并且它可能在其他场景中添加额外的约束.然而,在实践中,似乎弱的Alpha存储器模型对于硬件设计者的潜在优势不值得花费软件复杂性并且增加了需要更多存储器障碍的开销.