扉页
1995 年 9 月
WRL 研究报告 95/7
共享内存 一致性模型： 教程 Sarita V. Adve Kourosh Gharachorloo
摘要
支持共享内存抽象的并行系统正在计算领域的许多方面得到广泛认可。为这类系统编写正确且高效的程序需要对内存语义进行形式化规约，即内存一致性模型。最直观的模型——顺序一致性——极大地限制了单处理器硬件和编译器设计者常用的许多性能优化的使用，从而降低了使用多处理器带来的好处。为缓解这一问题，许多当前的多处理器支持更宽松的内存一致性模型。不幸的是，各种系统支持的模型在微妙但重要的方面彼此不同。此外，精确地定义每个模型的语义往往会导致复杂的规约，这对于计算机系统的普通用户和构建者来说难以理解。 本教程论文的目的是以一种大多数计算机专业人员都能理解的方式描述与内存一致性模型相关的问题。我们关注为基于硬件的共享内存系统提出的一致性模型。许多这些模型最初在规约时强调它们所允许的系统优化。我们保留这种以系统为中心的强调，但使用统一且简单的术语来描述不同的模型。我们还简要讨论了一种替代的以程序员为中心的视角，该视角根据程序行为而非特定的系统优化来描述模型。
1 引言
共享内存或单一地址空间抽象相比消息传递（或私有内存）抽象具有若干优势，它提供了从单处理器更自然的过渡，并简化了数据划分和动态负载分配等困难的编程任务。因此，支持共享内存的并行系统正在技术和商业计算领域获得广泛认可。 为了编写正确且高效的共享内存程序，程序员需要精确了解多个处理器的读和写操作下内存如何表现。例如，考虑图 1 中的共享内存程序片段，它代表了 SPLASH 应用套件中 LocusRoute 程序的一个片段。该图显示了处理器 P1 反复分配任务记录、更新记录中的数据字段，并将记录插入任务队列。当没有更多任务时，处理器 P1 更新指针 Head，使其指向任务队列中的第一个记录。与此同时，其他处理器等待 Head 具有非空值，在临界区内将 Head 指向的任务出队，最后访问出队记录中的数据字段。程序员对内存系统有何期望以确保该程序片段的正确执行？一个重要的要求是，从出队记录中的数据字段读出的值应与 P1 在该记录中写入的值相同。然而，在许多商业共享内存系统中，处理器有可能观察到数据字段的旧值（即 P1 写入该字段之前的值），从而导致与程序员预期不同的行为。
Initially all pointers = null, all integers = 0.
P1 P2, P3, ..., Pn
while (there are more tasks) f while (MyTask == null) f
Task = GetFromFreeList(); Begin Critical Section
Task ! Data = ...; if (Head != null) f
insert Task in task queue MyTask = Head;
g Head = Head ! Next;
Head = head of task queue; g
End Critical Section
g
... = MyTask ! Data;
图 1：读操作可以返回什么值？
共享内存多处理器的内存一致性模型提供了内存系统如何向程序员呈现的正式规约，消除了程序员期望的行为与系统实际支持的行为之间的差距。实际上，一致性模型限制了共享内存程序执行中读操作可以返回的值。直观上，读操作应返回对同一内存位置“最后”一次写入的值。在单处理器中，“最后”由程序顺序精确定义，即内存操作在程序中出现的顺序。在多处理器中则不然。例如，在图 1 中，记录中 Data 字段的写和读不按程序顺序相关，因为它们位于两个不同的处理器上。尽管如此，单处理器模型的直观扩展可以应用于多处理器情况。这个模型称为顺序一致性。非正式地说，顺序一致性要求所有内存操作看起来一次执行一个，并且单个处理器的操作看起来按照该处理器的程序顺序执行。回到图 1 中的程序，该模型确保从出队记录中的数据字段读操作将返回处理器 P1 写入的新值。 顺序一致性提供了一个简单且直观的编程模型。然而，它通过强制共享内存操作之间的严格顺序，禁止了许多单处理器中可能的硬件和编译器优化。因此，人们提出了许多更宽松的内存一致性模型，包括一些商业可用架构所支持的模型，如 Digital Alpha、SPARC V8 和 V9 以及 IBM PowerPC。不幸的是，文献中提出了大量彼此在微妙但重要的方面不同的宽松一致性模型。此外，用于描述这些模型的复杂且不统一的术语使得理解和比较它们变得困难。这种多样性和复杂性还常常导致对宽松内存一致性模型的误解，其中一些误解在图 2 中有所描述。 本教程文章的目标是以大多数计算机专业人员都能理解的方式描述顺序一致性以及其他更宽松的内存一致性模型。如果系统设计人员正在引入的性能增强功能要被程序员正确且广泛地使用，那么这种理解就很重要。为了实现这一目标，我们使用简单且统一的术语来描述不同模型的语义。我们关注为基于硬件的共享内存系统提出的一致性模型。大多数这些模型的原始规约都强调这些模型所允许的系统优化。我们在描述中保留这种以系统为中心的强调，以便捕捉模型的原始语义。我们还简要描述了宽松一致性模型的一种替代视角，即以程序员为中心的视角。这种视角根据程序行为而非硬件或编译器优化来描述模型。有兴趣进一步深入研究以系统为中心和以程序员为中心两种视角的更形式化处理的读者，可以参考我们之前的工作 [1, 6, 8]。 本文的其余部分组织如下。我们首先简要说明谁应该关注系统的内存一致性模型。接下来我们描述顺序一致性提供的编程模型，以及顺序一致性对硬件和编译器实现的影响。然后我们使用简单且统一的术语描述几种宽松的内存一致性模型。文章最后一部分描述以程序员为中心的宽松内存一致性模型视角。
2 内存一致性模型——谁应该关心？
作为程序员与系统之间的接口，内存一致性模型的影响在共享内存系统中无处不在。该模型影响可编程性，因为程序员必须使用它来推理程序的正确性。该模型影响系统性能，因为它决定了硬件和系统软件可以利用的优化类型。最后，由于缺乏对单一模型的共识，当软件在不同模型之间迁移时，可移植性可能会受到影响。 在每个定义了程序员与系统之间接口的层次上，都需要内存一致性模型规约。在机器代码接口层面，内存模型规约影响机器硬件设计人员以及编写或推理机器代码的程序员。在高级语言接口层面，规约影响使用高级语言的程序员，以及将高级语言代码转换为机器代码的软件和执行该代码的硬件的设计人员。因此，可编程性、性能和可移植性问题可能存在于多个不同的层次。 总之，从程序员的角度来看，内存模型影响并行程序的编写；从系统设计人员的角度来看，它影响并行系统几乎所有方面的设计（包括处理器、内存系统、互连网络、编译器和编程语言）。
3 单处理器系统中的内存语义
大多数高级单处理器语言为内存操作提供简单的顺序语义。这些语义允许程序员假设所有内存操作将按照程序指定的顺序（即程序顺序）一次一个地发生。因此，程序员期望读操作将返回在顺序程序顺序中同一位置之前最后一次写入的值。幸运的是，顺序性的假象可以被高效地支持。例如，只需维护单处理器数据依赖和控制依赖就足够了，也就是说，当两个操作针对同一位置或一个操作控制另一个操作的执行时，按程序顺序执行这两个操作。只要尊重这些单处理器数据依赖和控制依赖，编译器和硬件就可以自由地重排针对不同位置的操作。这使得编译器优化（如寄存器分配、代码移动和循环变换）以及硬件优化（如流水线、多发射、写缓冲旁路和转发以及无锁缓存）成为可能，所有这些都会导致内存操作的重叠和重排。总体而言，单处理器的顺序语义为程序员提供了一个简单且直观的模型，同时允许广泛的高效系统设计。
| 误解 | 现实 |
|---|---|
| 内存一致性模型仅适用于允许多个共享数据副本的系统；例如，通过缓存。 | 图 5 给出了几个反例。 |
| 大多数当前系统都是顺序一致的。 | 图 9 提到了几个非顺序一致的商业系统。 |
| 内存一致性模型只影响硬件设计。 | 本文描述了内存一致性模型如何影响系统设计的许多方面，包括编译器中允许的优化。 |
| 缓存一致性协议与内存一致性模型的关系：（i）缓存一致性协议本身支持顺序一致性，（ii）内存一致性模型取决于系统支持基于失效还是基于更新的缓存一致性协议。 | 本文讨论了缓存一致性协议只是内存一致性模型的一部分。其他方面包括处理器向内存系统发出内存操作的顺序，以及写操作是否原子执行。本文还讨论了给定的内存一致性模型如何同时允许失效或更新一致性协议。 |
| 系统的内存模型可以通过仅指定处理器（或内存系统）的行为来定义。 | 本文描述了内存一致性模型如何受到处理器和内存系统行为的影响。 |
| 宽松内存一致性模型不能用于隐藏读延迟。 | 本文描述的许多模型允许隐藏读和写延迟。 |
| 宽松一致性模型需要使用额外的同步。 | 本文讨论的大多数宽松模型不需要程序中的额外同步。特别是，以程序员为中心的框架只要求正确区分或标记操作。其他模型提供安全网，允许程序员强制执行正确性所需的约束。 |
| 宽松内存一致性模型不允许混沌（或异步）算法。 | 本文讨论的模型允许混沌（或异步）算法。对于以系统为中心的模型，程序员可以通过考虑模型所启用的优化来推理此类算法的正确性。以程序员为中心的方法只要求程序员显式识别参与竞争的操作。对于许多混沌算法，前者可能提供更高的性能，因为此类算法不依赖顺序一致性来保证正确性。 |
图 2：关于内存一致性模型的一些误解。
图 3：顺序一致性的程序员视角。
4 理解顺序一致性
共享内存多处理器最常假设的内存一致性模型是顺序一致性，Lamport 形式化定义如下 [16]。
定义： [多处理器系统是顺序一致的，当且仅当] 任何执行的结果都等同于所有处理器的操作按某种顺序执行的结果，并且每个单独处理器的操作在此序列中按其程序指定的顺序出现。
顺序一致性有两个方面：（1）维护来自单个处理器的操作之间的程序顺序，（2）维护来自所有处理器的操作之间的单一顺序。后者使得内存操作看起来相对于其他内存操作是原子或瞬时执行的。 顺序一致性为程序员提供了一个简单的系统视图，如图 3 所示。概念上，存在一个单一的全局内存和一个开关，在任何时间步将任意处理器连接到内存。每个处理器按程序顺序发出内存操作，开关提供所有内存操作之间的全局串行化。 图 4 提供了两个示例来说明顺序一致性的语义。图 4(a) 说明了来自单个处理器的操作之间程序顺序的重要性。该代码段描述了用于临界区的 Dekker 算法实现，涉及两个处理器（P1 和 P2）和两个初始化为 0 的 flag 变量（Flag1 和 Flag2）。当 P1 尝试进入临界区时，它将 Flag1 更新为 1，并检查 Flag2 的值。Flag2 的值为 0 表示 P2 尚未尝试进入临界区；因此，P1 可以安全进入。该算法依赖于这样一个假设：P1 的读返回值为 0 意味着 P1 的写发生在 P2 的写和读操作之前。因此，P2 对 flag 的读将返回值 1，阻止 P2 也进入临界区。顺序一致性通过要求维护 P1 和 P2 的内存操作之间的程序顺序来确保上述行为，从而排除两个处理器都读到值 0 并进入临界区的可能性。 图 4(b) 说明了内存操作原子执行的重要性。该图显示了三个处理器共享变量 A 和 B，两者均初始化为 0。假设处理器 P2 对其 A 的读返回值 1（由 P1 写入），写入变量 B，然后处理器 P3 对 B 的读返回值 1（由 P2 写入）。顺序一致性的原子性方面使我们能够假设 P1 的写的效果同时被整个系统看到。因此，在上述执行中，P3 保证能看到 P1 的写的效果，并且其对 A 的读必须返回值 1（因为 P3 在看到 P2 对 B 的写之后看到 P2 对 A 的写的效果）。
Initially Flag1 = Flag2 = 0 Initially A = B = 0
P1 P2 P1 P2 P3
Flag1 = 1 Flag2 = 1 A=1
if (Flag2 == 0) if (Flag1 == 0) if (A ==1)
critical section critical section B=1
if (B==1)
register1 = A
(a) (b)
图 4：顺序一致性示例。
5 实现顺序一致性
本节描述如何在实际系统中实现图 3 所示的顺序一致性直观抽象。我们将看到，与单处理器不同，仅在每个位置的基础上保留操作顺序不足以在多处理器中维护顺序一致性。 我们首先考虑顺序一致性与常见硬件优化的交互。为了区分程序顺序和原子性问题，我们首先描述无缓存架构中顺序一致性的实现，然后考虑缓存共享数据的影响。本节后半部分描述顺序一致性与常见编译器优化的交互。
5.1 无缓存架构
我们选择三种典型的硬件优化作为示例，说明在没有数据缓存的情况下实现顺序一致性时出现的典型交互。许多其他常见硬件优化可能导致与我们典型示例类似的交互。正如将要看到的，在无缓存环境中正确支持顺序一致性的关键问题在于维护来自每个处理器的操作之间的程序顺序。图 5 说明了下面讨论的各种交互。术语 t1、t2、t3、… 表示相应内存操作在内存处执行的顺序。
5.1.1 具有旁路能力的写缓冲
我们考虑的第一个优化说明了维护写操作与其后读操作之间程序顺序的重要性。图 5(a) 显示了一个无缓存的基于总线的共享内存系统示例。假设一个简单的处理器按程序顺序一次一个地发出内存操作。与图 3 的抽象相比，我们考虑的唯一优化是使用具有旁路能力的写缓冲。在写操作时，处理器只需将写操作插入写缓冲并继续，无需等待写操作完成。后续读操作被允许旁路写缓冲中任何先前的写操作以更快完成。只要读地址与任何缓冲写的地址不匹配，就允许这种旁路。这构成了单处理器中用于有效隐藏写操作延迟的常见硬件优化。 为了理解写缓冲的使用如何违反顺序一致性，考虑图 5(a) 中的程序。该程序描述了前面图 4(a) 中也展示过的 Dekker 算法。如前所述，顺序一致系统必须禁止两个 flag 的读都返回值 0 的结果。然而，这个结果可能出现在我们的示例系统中。每个处理器可以缓冲其写操作，并允许后续读旁路其写缓冲中的写操作。因此，在两个写操作被服务之前，两个读操作可能都被内存系统服务，从而允许两个读都返回值 0。 上述优化在传统单处理器中是安全的，因为旁路（针对不同位置的操作之间）不会导致单处理器数据依赖的违反。然而，如我们的示例所示，这种重排很容易在多处理器环境中违反顺序一致性的语义。
P1 P2
Read Read P1 P2
Flag2 Flag1
Write Flag1 t3 Write Flag2 t4
t1 t2 Flag1 = 1 Flag2 = 1
Shared Bus if (Flag2 == 0) if (Flag1 == 0)
critical section critical section
Flag1: 0
Memory
Flag2: 0
(a) write buffer
P1 P2
Read Data t3
General Interconnect Read Head t2
P1 P2
Write Head Write Data
t1 t4 Data = 2000 while (Head == 0) {;}
Head = 1 ... = Data
Head: 0 Data: 0
Memory
(b) overlapped writes
P1 P2
Write Head t3
Write Data t2 General Interconnect
Read Head P1 P2
t4 Read Data
t1 Data = 2000 while (Head == 0) {;}
Head = 1 ... = Data
Head: 0 Data: 0
Memory
(c) non−blocking reads
图 5：可能违反顺序一致性的典型优化。
5.1.2 重叠写操作
第二个优化说明了维护两个写操作之间程序顺序的重要性。图 5(b) 显示了一个具有通用（非总线）互连网络和多个内存模块的示例系统。通用互连网络缓解了基于总线设计的串行化瓶颈，多个内存模块提供了同时服务多个操作的能力。我们仍然假设处理器按程序顺序发出内存操作，并在不等待先前写操作完成的情况下继续后续操作。与上一个示例相比，关键区别在于同一处理器发出的多个写操作可能由不同内存模块同时服务。 图 5(b) 中的示例程序片段说明了上述优化如何违反顺序一致性；该示例是图 1 所示代码的简化版本。顺序一致系统保证 P2 对 Data 的读将返回 P1 写入的值。然而，允许图 5(b) 所示系统中 P1 上的写操作重叠很容易违反这一保证。假设 Data 和 Head 变量位于不同的内存模块中，如图所示。由于对 Head 的写可能在到达 Data 的内存模块之前就被注入网络，这两个写可能按程序顺序之外完成。因此，另一个处理器可能观察到 Head 的新值，却仍获得 Data 的旧值。其他常见优化，如在写缓冲中合并同一缓存行的写操作（如 Digital Alpha 处理器中所做的），也可能导致写操作的类似重排。 同样，虽然允许对不同位置的写操作重排对单处理器程序是安全的，但上述示例表明这种重排很容易违反顺序一致性的语义。解决这个问题的一种方法是等待写操作到达其内存模块后，才允许同一处理器的下一个写操作被注入网络。强制执行上述顺序通常需要写操作的确认响应，以通知发出写操作的处理器该写操作已到达其目标。确认响应在具有通用互连网络的系统中对于维护从写到后续读操作的程序顺序也很有用。
5.1.3 非阻塞读操作
第三个优化说明了维护读操作与其后读或写操作之间程序顺序的重要性。我们考虑在图 5(b) 所示系统（在图 5(c) 中重复）中支持非阻塞读。虽然大多数早期 RISC 处理器会等待读操作的返回值（即阻塞读），但许多当前和下一代处理器具有通过使用非阻塞（无锁）缓存、推测执行和动态调度等技术在读操作之后继续执行的能力。 图 5(c) 显示了来自同一处理器的读操作重叠如何违反顺序一致性的示例。该程序与前一个优化使用的程序相同。假设 P1 确保其写操作按程序顺序到达各自的内存模块。然而，如果允许 P2 以重叠方式发出其读操作，则可能出现 Data 的读在 P1 的写之前到达其内存模块，而 Head 的读在 P1 的写之后到达其内存模块的情况，从而导致非顺序一致的结果。将读操作与其后的写操作重叠也可能导致类似上述的问题；然而，后一种优化在当前处理器中并不常见。
5.2 带缓存的架构
上一节描述了在没有缓存的情况下实现顺序一致性模型时由于内存操作重排而产生的复杂性。共享数据的缓存（或复制）可能呈现类似的违反顺序一致性的重排行为。例如，一级写直达缓存可能导致类似于具有旁路能力的写缓冲所允许的重排，因为按程序顺序跟随在写之后的读可能在写完成之前由缓存服务。因此，带缓存的实现也必须采取预防措施来维护来自每个处理器的操作按程序顺序执行的假象。最值得注意的是，即使处理器的读命中其缓存，该处理器通常也不能读取缓存值，直到按程序顺序其先前的操作完成为止。 共享数据的复制引入了三个额外的问题。首先，存在多个副本需要一种机制（通常称为缓存一致性协议）将新写入的值传播到被修改位置的所有缓存副本。其次，检测写操作何时完成（以保留从写到其后续操作的程序顺序）在存在复制时需要更多事务。第三，将变更传播到多个副本本质上是原子的，这使得保留写操作相对于其他操作的原子性假象更具挑战性。我们在下面更详细地讨论这三个问题。
5.2.1 缓存一致性与顺序一致性
文献中存在几种缓存一致性（也称为缓存一致性）的定义。最强的定义几乎将缓存一致性视为顺序一致性的同义词。其他定义则施加了极其宽松的排序保证。具体而言，通常与缓存一致性协议相关的一组条件是：（1）写操作最终对所有处理器可见，（2）对同一位置的写操作似乎被所有处理器以相同顺序看到（也称为对同一位置写的串行化）[13]。上述条件显然不足以满足顺序一致性，因为后者要求对所有位置（而不仅仅是同一位置）的写操作被所有处理器以相同顺序看到，并且还明确要求单个处理器的操作按程序顺序执行。 我们不使用缓存一致性这一术语来定义任何一致性模型。相反，我们仅将缓存一致性协议视为将新写入的值传播到被修改位置的缓存副本的机制。值的传播通常通过使副本失效（或消除）或将副本更新为新写入的值来实现。基于对缓存一致性协议的这种看法，内存一致性模型可以被解释为确定新值何时可以传播到任何给定处理器的策略，即对新值传播设置早期和晚期边界。
5.2.2 检测写操作的完成
如上一节所述，维护从写到后续操作的程序顺序通常需要确认响应来通知写操作的完成。在无缓存系统中，确认响应可以在写操作到达其目标内存模块时生成。然而，在带缓存的设计中，上述方式可能不够。考虑图 5(b) 中的代码，以及同一图中所示但为每个处理器增加了写直达缓存的系统。假设处理器 P2 最初在其缓存中有 Data。假设 P1 在其对 Data 的前一个写到达目标内存后、但其值通过失效或更新消息传播到 P2 之前，继续执行对 Head 的写。现在 P2 可能读到 Head 的新值，却仍然从其缓存返回 Data 的旧值，这违反了顺序一致性。如果 P1 等待 P2 对 Data 的缓存副本被更新或失效后再继续执行对 Head 的写，就可以避免这个问题。 因此，当写操作到达一个在其他处理器缓存中被复制的行时，系统通常需要一种机制来确认目标缓存已收到失效或更新消息。此外，确认消息需要被收集（在内存处或在发出写操作的处理器处），并且发出写操作的处理器必须被通知这些确认已完成。只有在上述通知之后，处理器才能认为写操作已完成。一种常见优化是在收到失效或更新消息后立即在处理节点确认该消息，并可能在实际缓存副本受影响之前确认；只要对传入缓存的消息处理遵守某些排序约束，这种设计仍然可以满足顺序一致性 [6]。
5.2.3 维护写操作的原子性假象
虽然顺序一致性要求内存操作看起来是原子的或瞬时的，但将变更传播到多个缓存副本本质上是原子的。我们激励并描述两个条件，这两个条件一起可以确保在数据复制存在的情况下呈现原子性的假象。由于原子性导致的问题更容易用基于更新的协议来说明；因此，以下示例假设使用这种协议。 为了激励第一个条件，考虑图 6 中的程序。假设所有处理器都按程序顺序一次一个地执行其内存操作。如果处理器 P1 和 P2 对 A 的写的更新以不同顺序到达处理器 P3 和 P4，则可能违反顺序一致性。因此，处理器 P3
Initially A = B = C = 0
P1 P2 P3 P4
A=1 A=2 while (B != 1) f;g while (B != 1) f;g
B=1 C=1 while (C != 1) f;g while (C != 1) f;g
register1 = A register2 = A
图 6：写串行化示例。
和 P4 可能对 A 的读返回不同的值（例如，register1 和 register2 可能分别被赋值为 1 和 2），使得对 A 的写看起来是非原子的。上述违反顺序一致性的情况可能发生在使用通用互连网络的系统中（例如，图 5(b)），其中消息沿网络中的不同路径传输，且对交付顺序不提供任何保证。可以通过施加对同一位置的写进行串行化的条件来避免这种违反；也就是说，所有处理器以相同顺序看到对同一位置的写。如果某个位置的所有更新或失效都源自一个单点（例如，目录），并且网络保留了这些消息在给定源和目的地之间的顺序，则可以实现这种串行化。另一种替代方法是延迟发送更新或失效，直到代表同一位置先前写操作发出的任何更新或失效被确认收到后再发送。 为了激励第二个条件，再次考虑图 4(b) 中的程序片段，同样使用更新协议。假设所有变量最初都被所有处理器缓存。此外，假设所有处理器都按程序顺序一次一个地执行其内存操作（等待如上所述的确认），并且对同一位置的写被串行化。在具有通用网络的系统上仍然可能违反顺序一致性，如果（1）处理器 P2 在 A 的更新到达处理器 P3 之前读取了 A 的新值，（2）P2 对 B 的更新在 A 的更新之前到达 P3，以及（3）P3 读取了 B 的新值，然后继续从其自己的缓存读取 A 的值（在收到 P1 对 A 的更新之前）。因此，P2 和 P3 似乎在不同时间看到对 A 的写，使得该写看起来是非原子的。在基于失效的方案中也可能出现类似情况。 上述违反顺序一致性的情况发生的原因是，允许 P2 在 P3 看到该写生成的更新之前返回对 A 的写的值。防止这种违反的一种可能限制是，禁止读操作在所有缓存副本确认收到该写生成的失效或更新消息之前返回新写入的值。对于基于失效的协议，这个条件很容易确保。基于更新的协议更具挑战性，因为与失效不同，更新直接向其他处理器提供新值。一种解决方案是采用两阶段更新方案。第一阶段涉及向处理器缓存发送更新并接收这些更新的确认。在这个阶段，不允许任何处理器读取已更新位置的值。在第二阶段，向已更新的处理器缓存发送确认消息，以确认已收到所有确认。处理器一旦收到第二阶段的确认消息，就可以从其缓存中使用更新后的值。然而，发出写的处理器可以在第一阶段结束时认为其写操作已完成。
5.3 编译器
顺序一致性的程序顺序方面与编译器的交互类似于其与硬件的交互。具体而言，对于到目前为止讨论的所有程序片段，编译器生成的共享内存操作重排将导致与硬件生成的重排类似的顺序一致性违反。因此，在缺乏更复杂分析的情况下，编译器的一个关键要求是保留共享内存操作之间的程序顺序。这一要求直接限制了任何可能导致内存操作重排的单处理器编译器优化。这些优化包括简单的优化，如代码移动、寄存器分配和公共子表达式消除，以及更复杂的优化，如循环分块或软件流水线。
除了重排效应外，寄存器分配等优化还会导致某些共享内存操作的消除，这反过来可能违反顺序一致性。考虑图 5(b) 中的代码。如果编译器在 P2 上将 Head 位置分配到寄存器中（通过将 Head 的一次读操作读入寄存器，然后在寄存器内读取该值），则 P2 上的循环在某些执行中可能永远不会终止（如果 P2 上的单次读返回 Head 的旧值）。然而，在该代码的每个顺序一致执行中，循环都保证会终止。问题的根源在于，在 P2 上将 Head 分配到寄存器中阻止了 P2 观察到 P1 写入的新值。 总之，如果顺序一致性要被保持，共享内存并行程序的编译器不能直接应用许多单处理器编译器中常用的优化。上述评论适用于显式并行程序的编译器；并行化顺序代码的编译器自然对其生成的结果并行程序有足够的信息来确定何时可以安全地应用优化。
5.4 顺序一致性总结
从上述讨论可以清楚地看出，顺序一致性限制了许多常见的硬件和编译器优化。顺序一致性的简单硬件实现通常需要满足以下两个要求。首先，处理器必须确保其先前的内存操作完成后，才能按程序顺序继续执行下一个内存操作。我们称这一要求为程序顺序要求。确定写的完成通常需要来自内存的显式确认消息。此外，在基于缓存的系统中，写必须为所有缓存副本生成失效或更新消息，并且只有当生成的失效和更新被目标缓存确认后，写才能被视为完成。第二个要求仅适用于基于缓存的系统，涉及写原子性。它要求对同一位置的写进行串行化（即，使所有处理器以相同顺序看到对同一位置的写），并且在读操作返回写的值之前，该写生成的所有失效或更新必须已被确认（即，直到该写对所有处理器可见）。我们称这一要求为写原子性要求。对于编译器，简单实现中也适用程序顺序要求的类似要求。此外，通过寄存器分配等优化消除内存操作也可能违反顺序一致性。 人们提出了许多技术，以允许硬件和编译器使用某些优化而不违反顺序一致性；下面讨论那些有潜力大幅提升性能的技术。 我们首先讨论两种适用于具有缓存一致性硬件支持的顺序一致系统的硬件技术 [10]。第一种技术自动为因程序顺序要求而延迟的任何写操作预取所有权（例如，通过为写缓冲中延迟的任何写发出预取独占请求），从而将延迟写的部分服务与程序顺序中位于其前面的操作重叠。这种技术仅适用于使用基于失效协议的缓存系统。第二种技术推测性地服务因程序顺序要求而延迟的读操作；在读行被失效或更新之前，简单地回滚并重新发出读操作和后续操作，即可保证顺序一致性，而这种情况在更简单的实现中读本可以被发出时是不频繁的。后一种技术适合动态调度处理器，因为大部分回滚机制已经存在以处理分支预测错误。上述两种技术将被若干下一代微处理器支持（例如，MIPS R10000、Intel P6），从而实现更高效的顺序一致性硬件实现。 其他隐藏延迟的技术，如非绑定软件预取或对多上下文的硬件支持，已被证明可以增强顺序一致性硬件的性能。然而，上述技术与宽松内存一致性结合使用时也有益。 最后，Shasha 和 Snir 开发了一种编译器算法，用于检测何时可以在不违反顺序一致性的情况下重排内存操作 [18]。这种分析可用于实现硬件和编译器优化，仅重排那些被编译器分析为安全的操作对。Shasha 和 Snir 的算法具有指数复杂度 [15]；最近，有人提出了一种针对 SPMD 程序的多项式复杂度新算法 [15]。然而，这两种算法都需要全局依赖分析来确定来自不同处理器的两个操作是否可能冲突（类似于别名分析）；这种分析很困难，往往导致保守信息，从而降低算法的有效性。 上述硬件和编译器技术是否能接近更宽松一致性模型的性能还有待观察。本文的其余部分重点讨论放宽内存一致性模型，以实现顺序一致性所限制的许多优化。
6 宽松内存模型
作为顺序一致性的替代方案，学术界和商业界提出了若干宽松内存一致性模型。大多数这些模型的原始描述基于差异很大的规约方法论和形式化程度。本节的目标是使用简单且统一的术语描述这些模型。这些模型的原始规约强调模型所允许的系统优化；我们在本节描述中保留这种以系统为中心的强调。我们关注为硬件共享内存系统提出的模型；为软件支持的共享内存系统提出的宽松模型描述起来更复杂，超出了本文的范围。描述硬件和软件模型的更形式化且统一的以系统为中心的框架，以及该框架内几个模型的形式化描述，出现在我们之前的工作 [8, 6] 中。 我们首先描述用于表征各种模型的简单方法论，然后使用该方法论描述每个模型。
6.1 表征不同的内存一致性模型
我们根据两个关键特征对宽松内存一致性模型进行分类：（1）它们如何放宽程序顺序要求，（2）它们如何放宽写原子性要求。 关于程序顺序放宽，我们根据模型是否放宽从写到后续读、两个写之间以及从读到后续读或写的顺序来区分模型。在所有情况下，放宽仅适用于针对不同地址的操作对。这些放宽与第 5.1 节讨论的优化并行。 关于写原子性要求，我们根据模型是否允许读操作在访问位置的所有缓存副本收到该写生成的失效或更新消息之前（即，在该写对所有其他处理器可见之前）返回另一个处理器的写的值来区分模型。这种放宽在第 5.2 节中描述，仅适用于基于缓存的系统。 最后，我们考虑一个与程序顺序和写原子性都相关的放宽，即允许处理器在写对其他处理器可见之前读取其自己先前写的值。在基于缓存的系统中，这种放宽允许读在写相对于其他对同一位置的写被串行化之前、以及在写的失效/更新到达任何其他处理器之前返回该写的值。这种放宽所允许的常见优化示例是在写缓冲中将写的值转发给同一处理器的后续读。对于基于缓存的系统，另一个常见示例是处理器写入写直达缓存，然后在写完成之前从缓存中读取该值。我们单独考虑这种放宽，因为即使本节讨论的若干模型未在其原始定义中明确说明这种优化，它也可以被安全地应用于许多模型而不违反模型语义。例如，只要维护了所有其他程序顺序和原子性要求，顺序一致性就允许这种放宽 [8]，这就是为什么我们在上一节没有讨论它。此外，本节讨论的所有模型中除一个外，都可以安全地应用这种放宽。 图 7 总结了上述放宽。宽松模型通常还为程序员提供覆盖这些放宽的机制。例如，可能提供显式栅栏指令来覆盖程序顺序放宽。我们通称这些机制为模型的安全网，并将讨论每个模型提供的安全网类型。每个模型可能提供更微妙的方式来强制执行特定的排序约束；为简单起见，我们只讨论更直接的安全网。 图 8 概述了本节剩余部分描述的模型。该图显示了相应模型的简单实现是否能有效利用上述程序顺序或写原子性放宽。
内存模型所允许的放宽包括：
- 放宽从写到读的程序顺序
- 放宽从写到写的程序顺序
- 放宽从读到读以及从读到写的程序顺序
- 提前读取其他处理器的写
- 提前读取自己的写
图 7：内存模型所允许的放宽。前三种（程序顺序）放宽仅适用于访问不同位置的操作对。
| 放宽类型 | 写→读 顺序 | 写→写 顺序 | 读→读/写 顺序 | 提前读其他处理器的写 | 提前读自己的写 | 安全网 |
|---|---|---|---|---|---|---|
| 顺序一致性 SC [16] | ||||||
| IBM 370 [14] | ✓ | ✓ | 串行化指令 | |||
| 全存储排序 TSO [20] | ✓ | ✓ | ✓ | 读-改-写 | ||
| 处理器一致性 PC [13, 12] | ✓ | ✓ | ✓ | 读-改-写 | ||
| 部分存储排序 PSO [20] | ✓ | ✓ | ✓ | ✓ | 读-改-写、STBAR | |
| 弱序 WO [5] | ✓ | ✓ | ✓ | ✓ | ✓ | 同步操作 |
| 释放一致性 RCsc [13, 12] | ✓ | ✓ | ✓ | ✓ | ✓ | release、acquire、nsync … |
| 释放一致性 RCpc [13, 12] | ✓ | ✓ | ✓ | ✓ | ✓ | 读-改-写、release、acquire、nsync … |
| Alpha [19] | ✓ | ✓ | ✓ | ✓ | MB、WMB | |
| RMO [21] | ✓ | ✓ | ✓ | ✓ | 各种 MEMBAR | |
| PowerPC [17, 4] | ✓ | ✓ | ✓ | ✓ | ✓ | SYNC |
图 8：宽松模型的简单分类。勾号表示相应放宽被对应模型的简单实现所允许，也表示程序员可以通过程序结果检测到该放宽，但以下情况例外：在 SC、WO、Alpha 和 PowerPC 模型中，“提前读自己的写”不可检测；在 RCsc 的复杂实现中，“提前读其他处理器的写”是可能且可检测的。
| 放宽类型 | 提供该放宽的商业系统示例 |
|---|---|
| 写→读 顺序 | AlphaServer 8200/8400、Cray T3D、Sequent Balance、SparcCenter1000/2000 |
| 写→写 顺序 | AlphaServer 8200/8400、Cray T3D |
| 读→读/写 顺序 | AlphaServer 8200/8400、Cray T3D |
| 提前读其他处理器的写 | Cray T3D |
| 提前读自己的写 | AlphaServer 8200/8400、Cray T3D、SparcCenter1000/2000 |
图 9：若干放宽顺序一致性的商业系统。
放宽，并提及每个模型提供的安全网。该图还指示程序员何时可以检测到上述放宽；即，何时它们可以影响程序结果。图 9 给出了允许上述放宽的商业系统示例。为简单起见，我们不试图描述模型在诸如指令获取或多粒度操作（例如，字节和字操作）等问题上的语义，即使其中一些模型定义了此类语义。 以下各节更详细地描述每个模型，并讨论每个模型对硬件和编译器实现的影响。在整个讨论中，我们隐式假设满足以下约束。首先，我们假设所有模型都要求写最终对所有处理器可见，并且对同一位置的写被串行化。如果共享数据未被缓存，这些要求自然满足；如果共享数据被缓存，通常由硬件缓存一致性协议满足。其次，我们假设所有模型都强制执行单处理器数据依赖和控制依赖。最后，放宽从读到后续写操作的程序顺序的模型还必须维护一种微妙的多处理器数据依赖和控制依赖形式 [8, 1]；后一种约束为我们所知的所有处理器设计固有地维护，并且也可以很容易地被编译器维护。
6.2 放宽从写到读的程序顺序
我们讨论的第一组模型放宽了写到不同位置后续读的情况下的程序顺序约束。这些模型包括 IBM 370 模型、SPARC V8 全存储排序模型（TSO）和处理器一致性模型（PC）（这与 Goodman 定义的处理器一致性模型不同）。 这些模型所允许的关键程序顺序优化是允许读相对于同一处理器的先前写被重排。作为这种重排的结果，图 5(a) 中的程序等可能无法提供顺序一致的结果。然而，由于剩余程序顺序约束的执行，图 5(b) 和图 5(c) 所示的顺序一致性违反不可能发生。 三个模型在读何时可以返回写的值方面有所不同。IBM 370 模型最严格，因为它禁止读在写对所有处理器可见之前返回该写的值。因此，即使处理器对与其自身先前待处理写相同地址发出读，读也必须延迟到写对所有处理器可见为止。TSO 模型部分放宽了上述要求，允许读在写相对于其他对同一位置的写被串行化之前返回其自身处理器的写的值。然而，与顺序一致性一样，读不允许在写对所有其他处理器可见之前返回另一个处理器的写的值。最后，PC 模型放宽了这两个约束，使得读可以在写被串行化或对任何其他处理器可见之前返回任何写的值。图 10 显示了说明上述三个模型之间差异的示例程序。 我们接下来考虑上述三个模型的安全网功能。为了强制执行从写到后续读的程序顺序约束，IBM 370 模型提供了特殊的串行化指令，可以放在两个操作之间。一些串行化指令是用于同步的特殊内存指令（例如，compare&swap），另一些是非内存指令，如分支。回到图 5(a) 中的示例程序，在每个处理器上的写之后放置一条串行化指令，即使程序在 IBM 370 模型上执行，也能提供顺序一致的结果。 与 IBM 370 相反，TSO 和 PC 模型不提供显式安全网。然而，程序员可以使用读-改-写操作来提供程序顺序在写和后续读之间被维护的假象。对于 TSO，如果写或读已经是读-改-写的一部分，或被替换为读-改-写，则程序顺序似乎被维护。为了用读-改-写替换读，读-改-写中的写必须是“虚拟”写，即将读出的值写回。类似地，用读-改-写替换写需要无论读返回什么值都将期望的值写回。因此，上述技术仅适用于为读-改-写指令提供这种灵活性的设计。对于 PC，如果读被替换为或已经是读-改-写的一部分，则写和后续读之间的程序顺序似乎被维护。与 TSO 相反，在 PC 中替换写为读-改-写不足以施加这种顺序。差异产生的原因是 TSO 对读-改-写的行为施加了更严格的约束；具体而言，TSO 要求在任何位置的其他写似乎都不出现在读-改-写的读和写之间，而 PC 仅要求对同一位置的写满足此条件。
Initially A = Flag1 = Flag2 = 0 Initially A = B = 0
P1 P2 P1 P2 P3
Flag1 = 1 Flag2 = 1 A=1
A=1 A=2 if (A == 1)
register1 = A register3 = A B=1
register2 = Flag2 register4 = Flag1 if (B == 1)
register1 = A
Result: register1 = 1, register3 = 2, Result: B = 1, register1 = 0
register2 = register4 = 0
(a) (b)
图 10：370、TSO 和 PC 之间的差异。部分 (a) 中程序的结果在 TSO 和 PC 中是可能的，因为这两个模型都允许 flag 的读发生在每个处理器上 flag 的写之前。IBM 370 中不可能出现该结果，因为每个处理器上对 A 的读直到该处理器上对 A 的写完成后才会发出。因此，每个处理器上对 flag 的读直到该处理器上对 flag 的写完成后才会发出。部分 (b) 中的程序与图 4(b) 相同。所示结果在 PC 中是可能的，因为它允许 P2 在 P1 的写对 P3 可见之前返回该写的值。IBM 370 或 TSO 中不可能出现该结果。
我们接下来考虑用于强制执行写原子性要求的安全网。IBM 370 不需要安全网，因为它不放宽原子性。对于 TSO，仅当同一处理器中同一位置后续读之前的写才需要写原子性安全网；可以通过使用上述读-改-写确保从写到读的程序顺序来实现原子性。对于 PC，如果可能返回该写的值的每个读都是读-改-写的一部分或被替换为读-改-写，则写保证看起来是原子的。 读-改-写操作如何在上述模型中确保所需程序顺序或原子性的推理超出了本文范围 [7]。在 TSO 和 PC 等模型中依赖读-改-写作为安全网存在一些缺点。首先，系统可能未实现可用于适当替换任何读或写的通用读-改-写。其次，将读替换为读-改-写会带来执行写的额外开销（例如，使该行的其他副本失效）。当然，如果这些特定的读或写操作已经是读-改-写操作的一部分，则这些安全网不会增加任何开销。此外，大多数程序的正确性并不频繁依赖从写到读的程序顺序或写原子性。 放宽从写到后续读的程序顺序可以通过有效隐藏写操作的延迟在硬件层面大幅提升性能 [9]。然而，对于编译器优化而言，这种单独的放宽在实践中并不有益。原因是程序中的读和写通常是细密交错的；因此，大多数重排优化实际上会导致相对于读和写两者的重排。因此，大多数编译器优化需要重排程序顺序中任意两个操作的完全灵活性；仅允许重排写相对于后续读的灵活性不够充分。
6.3 放宽从写到读和从写到写的程序顺序
第二组模型通过消除对不同位置写之间的排序约束，进一步放宽了程序顺序要求。我们在此描述的这种模型的唯一示例是 SPARC V8 部分存储排序模型（PSO）。相对于前一组模型，PSO 所允许的关键额外硬件优化是，来自同一处理器对不同位置的写可以流水线化或重叠，并且允许按程序顺序之外到达内存或其他缓存副本。关于原子性要求，PSO 与 TSO 相同，允许处理器提前读取自己的写的值，并禁止处理器在写对所有其他处理器可见之前读取另一个处理器的写的值。回到图 5(a) 和 (b) 中的程序，PSO 允许非顺序一致的结果。 PSO 提供的用于施加从写到读的程序顺序以及强制执行写原子性的安全网与 TSO 相同。PSO 提供显式的 STBAR 指令来施加两个写之间的程序顺序。在使用 FIFO 写缓冲的实现中支持 STBAR 的一种方法是将 STBAR 插入写缓冲，并延迟在 STBAR 之后缓冲的写的退役，直到 STBAR 之前缓冲的写已退役并完成。可以使用计数器来确定 STBAR 之前的所有写何时完成——发送到内存系统的写使计数器递增，写确认使计数器递减，计数器值为 0 表示所有先前的写都已完成。回到图 5(b) 中的程序，在两个写之间插入 STBAR 可确保 PSO 产生顺序一致的结果。 与前几组模型一样，PSO 允许的优化对编译器来说不够灵活，没有用处。
6.4 放宽所有程序顺序
我们考虑的最后一组模型放宽了不同位置所有操作之间的程序顺序。因此，读或写操作可能相对于后续对不同位置的读或写被重排。我们讨论弱序（WO）模型、释放一致性模型（RCsc/RCpc）的两种变体，以及为商业架构提出的三个模型：Digital Alpha、SPARC V9 宽松内存顺序（RMO）和 IBM PowerPC 模型。除 Alpha 外，上述模型还允许对同一位置两个读的重新排序。回到图 5，上述模型违反了该图所示所有代码示例的顺序一致性。 相对于先前模型所允许的额外关键程序顺序优化是，读操作之后的内存操作可以相对于读操作重叠或重排。在硬件中，这种灵活性提供了通过实现真正的非阻塞读来隐藏读操作延迟的可能性，无论是在静态（按序）还是动态（乱序）调度处理器的上下文中，都由非阻塞（无锁）缓存和推测执行等技术支持 [11]。 该组中的所有模型都允许处理器提前读取自己的写。然而，RCpc 和 PowerPC 是唯一其简单实现允许读返回另一个处理器提前写的值的模型。WO、RCsc、Alpha 和 RMO 的更复杂实现也可能实现上述行为。然而，从程序员的角度来看，WO、Alpha 和 RMO 的所有实现都必须保留写原子性的假象。RCsc 在这方面是一个独特的模型；程序员不能依赖原子性，因为 RCsc 的复杂实现可能以可能影响程序结果的方式违反原子性。 上述模型可以根据提供的安全网类型分为两类。WO、RCsc 和 RCpc 模型根据操作类型区分内存操作，并为某些类型的操作提供更严格的排序约束。另一方面，Alpha、RMO 和 PowerPC 模型提供显式栅栏指令，用于在各种内存操作之间施加程序顺序。下文更详细地描述这些模型中的每一个，重点介绍它们的安全网。本节末尾讨论该组模型对编译器实现的影响。
6.4.1 弱序（WO）
弱序模型将内存操作分为两类：数据操作和同步操作。为了在两个操作之间强制执行程序顺序，程序员需要至少将其中一个操作标识为同步操作。该模型基于这样的直觉：同步操作之间数据区域中内存操作的重排通常不会影响程序的正确性。 被标识为同步的操作有效地提供了强制执行程序顺序的安全网。我们简要描述在硬件中支持适当功能的一种简单方法。每个处理器可以提供一个计数器来跟踪其未完成的操作。当处理器发出操作时该计数器递增，当先前的操作完成时递减。每个处理器必须确保同步操作直到所有先前操作完成（由计数器值为零表示）后才发出。¹ 此外，在先前同步操作完成之前不会发出任何操作。请注意，两个同步操作之间的内存操作仍然可以相对于彼此重排和重叠。 ¹ 对于弱序，如果程序顺序中读 R 后跟写 W，且两者由多处理器数据依赖或控制依赖相关（在第 6.1 节中提到），我们假设写 W 被延迟，直到读 R 完成且被 R 读取的写也完成。 弱序模型确保写对程序员总是看起来是原子的；因此，不需要写原子性的安全网。
6.4.2 释放一致性（RCsc/RCpc）
与弱序相比，释放一致性对内存操作提供了进一步的区分。图 11 以图形方式描述了这种内存操作分类。操作首先被区分为普通操作或特殊操作。这两个类别大致对应于 WO 中的数据操作和同步操作。特殊操作进一步被区分为 sync 或 nsync 操作。Sync 直观上对应于同步操作，而 nsync 对应于异步数据操作或不用于同步的特殊操作。最后，sync 操作进一步被区分为获取或释放操作。直观上，获取是为了获得对一组共享位置的访问权而执行的读内存操作（例如，锁操作或自旋等待 flag 被设置）。释放是为了授予访问一组共享位置的权限而执行的写操作（例如，解锁操作或设置 flag）。 释放一致性有两种变体，它们根据在特殊操作之间维护的程序顺序而有所不同。第一种变体在特殊操作之间维护顺序一致性（RCsc），而第二种变体在这些操作之间维护处理器一致性（RCpc）。下面，我们描绘了这两种模型针对不同位置操作的程序顺序约束。在我们的符号中，A ! B 意味着如果操作类型 A 在程序顺序中先于操作类型 B，则两个操作之间强制执行程序顺序。对于 RCsc，约束如下：
- acquire ! all，all ! release，以及 special ! special。
对于 RCpc，消除了特殊操作之间从写到读的程序顺序：
- acquire ! all，all ! release，以及 special ! special，但特殊写之后跟特殊读除外。
因此，通过在两个操作之间区分或标记适当的操作，可以实现程序顺序的强制执行。对于 RCpc，施加从写到读操作的程序顺序需要使用类似于 PC 模型的读-改-写操作。此外，如果要排序的写是普通操作，则读-改-写中的写需要是释放；否则，读-改-写中的写可以是任何特殊写。类似地，为了使写在 RCpc 下看起来是原子的，可以使用读-改-写操作来替换适当的操作，类似于 PC 模型。如前所述，RCsc 的更复杂实现中写也可能看起来是非原子的。通过将足够的操作标记为特殊可以保持写的原子性；然而，在本文提出的简单框架内精确解释如何做到这一点是困难的。我们应该注意，RCsc 模型还伴随着一种更高级别的抽象（在第 7 节中描述），它使程序员无需直接对大量程序使用低级规约进行推理 [13]。
shared
special ordinary
sync nsync
acquire release
图 11：为释放一致性区分操作。
6.4.3 Alpha、RMO 和 PowerPC
Alpha、RMO 和 PowerPC 模型都提供显式栅栏指令作为其安全网。 Alpha 模型提供两种不同的栅栏指令，即内存屏障（MB）和写内存屏障（WMB）。MB 指令可用于维护 MB 之前任何内存操作与 MB 之后任何内存操作之间的程序顺序。WMB 指令仅在写操作之间提供这种保证。Alpha 模型不需要写原子性的安全网。 SPARC V9 RMO 模型提供更多种类的栅栏指令。实际上，MEMBAR 指令可以定制为将先前读和写操作的某种组合相对于未来读和写操作排序；使用四位编码来指定读-读、读-写、写-读和写-写排序的任意组合。MEMBAR 可用于将写相对于后续读排序这一事实，缓解了在 SPARC V8 TSO 或 PSO 模型中为达到这种顺序而使用读-改-写的需要。与 TSO 和 PSO 类似，RMO 模型不需要写原子性的安全网。 PowerPC 模型提供单一栅栏指令，称为 SYNC 指令。对于施加程序顺序，SYNC 指令的行为类似于 Alpha 模型的 MB 指令，但有一个例外。该例外是，即使 SYNC 放在对同一位置两个读之间，第二个读仍有可能返回比第一个读更旧的写的值；也就是说，读似乎按程序顺序之外发生。这可能造成程序中微妙的正确性问题，可能需要使用读-改-写操作（类似于 PC 和 RCpc 中的使用）来强制执行对同一位置两个读之间的程序顺序。PowerPC 在原子性方面也与 Alpha 和 RMO 不同，因为它允许写被另一个处理器的读提前看到；因此，类似于 PC 和 RCpc，可能需要使用读-改-写操作来使写看起来是原子的。
6.4.4 编译器优化
与前几节中的模型不同，放宽所有程序顺序的模型提供了足够的灵活性，允许对共享内存操作进行常见的编译器优化。在 WO、RCsc 和 RCpc 等模型中，编译器可以在两个连续同步或特殊操作之间重排内存操作。类似地，在 Alpha、RMO 和 PowerPC 模型中，编译器在连续栅栏指令之间的操作具有完全的重排灵活性。由于大多数程序不频繁使用这些操作或指令，编译器获得了大段代码区域，在这些区域中几乎可以安全地应用所有用于单处理器程序的优化。
7 宽松内存模型的替代抽象
上一节描述的宽松内存模型所提供的灵活性使得广泛的性能优化成为可能，这些优化已被证明能显著提升性能 [9, 11, 6]。然而，更高的性能伴随着程序员更高的复杂性。此外，不同系统支持的广泛模型要求程序员处理在微妙方式上不同的各种语义，并使程序在这些系统之间移植的任务复杂化。编程复杂性源于宽松内存模型通常提供的以系统为中心的规约。这种规约直接将程序员暴露于模型所允许的重排和原子性优化，并要求程序员考虑在这种优化存在下程序的行为，以推理其正确性。这激励人们为程序员设计一种更高级别的抽象，它提供更简单的系统视图，同时允许系统设计人员利用相同类型的优化。 对于我们描述的宽松模型，程序员可以通过使用足够的安全网（例如，栅栏指令、更保守的操作类型或读-改-写操作）来施加适当的排序和原子性要求，从而确保程序的正确性。困难的问题在于识别正确性所必需的排序约束。例如，考虑图 1 中的程序在弱序（WO）等模型上执行。在这个例子中，为正确性只需维护以下顺序：（1）在 P1 上，维护对 Head 的写与对 Head 写之前的操作之间的程序顺序，（2）在其他处理器上，维护从对 Head 的读到后续操作之间的程序顺序。对 Head 的写和读实际上表现为同步操作，通过这样标识它们，像 WO 这样的模型将自动维护适当的程序顺序。认识到这个问题，许多模型如 WO 都附有关于程序员必须做什么以确保“正确”行为的非正式条件。例如，弱序要求程序员应识别所有同步操作。然而，这些条件的非正式性质使它们在应用于广泛程序时变得模糊（例如，哪些操作应真正被标识为同步）。因此，在很多情况下，程序员仍然不得不诉诸于低级别重排优化来进行推理，以确定是否强制执行了足够的顺序。 与以系统为中心的规约将性能增强优化直接暴露给程序员不同，以程序员为中心的规约要求程序员提供有关程序的某些信息。然后系统使用这些信息来确定是否可以应用某种优化而不违反程序的正确性。为了提供形式化的以程序员为中心的规约，我们首先需要定义程序“正确性”的概念。一个明显的选择是顺序一致性，因为它是单处理器正确性概念的自然扩展，也是多处理器中最常假设的正确性概念。其次，必须从程序员那里获得的信息必须被精确定义。 总之，采用以程序员为中心的方法，内存一致性模型是根据程序员必须提供的程序级信息来描述的。基于该模型的系统利用这些信息执行优化，而不违反顺序一致性。我们之前的工作探索了各种以程序员为中心的方法。例如，data-race-free-0（DRF0）方法探索了允许类似弱序所启用优化所需的信息 [2]。properly-labeled（PL）方法随释放一致性（RCsc）的定义一起提供，作为推理 RCsc 所利用优化类型的更简单方式 [13]。利用更激进优化的以程序员为中心的方法在我们其他工作中描述 [7, 3, 1, 6]；还开发了一个用于设计以程序员为中心的模型的统一框架，并用于探索此类模型的设计空间 [1]。 为了更具体地说明以程序员为中心的方法，下一节描述了程序员可能提供的程序级信息类型，以启用类似弱序模型所利用的优化。然后我们描述程序员如何实际将此类信息传达给系统。
7.1 以程序员为中心的框架示例
回想一下，弱序基于这样的直觉：内存操作可以被分类为数据和同步，数据操作可以比同步操作更激进地执行。以程序员为中心方法的一个关键目标是形式化应被区分为同步的操作。 如果一个操作在任何顺序一致执行中与另一个操作形成竞争，则该操作必须被定义为同步操作；其他操作可以被定义为数据。给定一个顺序一致执行，如果一个操作与另一个操作访问同一位置、至少其中一个操作是写，并且两个被考虑的操作之间没有其他介入操作，则该操作与另一个操作形成竞争。考虑图 12 中的示例（与图 5(b) 中的示例相同）。在该程序的每个顺序一致执行中，对 Data 的写和读总是由对 Head 的写和读的介入操作分隔开。因此，对 Data 的操作是数据操作。然而，对 Head 的操作并不总是被其他操作分隔开；因此，它们是同步操作。请注意，程序员只对程序的顺序一致执行进行推理，为了提供上述信息，不需要处理任何重排优化。 从系统设计角度来看，被区分为同步的操作需要被保守地执行，而被区分为数据的操作可以被激进地执行。特别是，弱序模型所启用的优化可以被安全地应用。此外，该信息还启用了比弱序所利用的更激进的优化 [2, 13, 1]。 如图 13 所示，以程序员为中心的框架要求程序员识别所有可能参与竞争的操作作为同步操作。其他操作可以被区分为数据
Initially all locations = 0
P1 P2
Data = 2000 while (Head == 0) f;g
Head = 1 ... = Data
图 12：提供关于内存操作的信息。
START
don’t know or
yes never don’t care
distinguish as
races?
data
no
distinguish as
synchronization
图 13：决定如何区分内存操作。
或同步。因此，如果程序员不确定特定操作是否参与竞争，可以保守地将其区分为同步操作。这种“不知道”选项很重要，原因如下。程序员可以通过将所有操作保守地区分为同步来简单地确保正确性；当然，这放弃了任何性能收益，但可能允许更快地获得初始可工作的程序。“不知道”选项的另一个潜在好处是，它允许程序员通过为部分内存操作（在程序的性能关键区域）提供准确信息，并简单地为剩余操作提供保守信息，来逐步调整性能。当然，如果程序员错误地将竞争操作区分为数据，则不保证正确性。 向系统提供适当信息需要在编程语言层面有一种机制来区分内存操作，还需要某种机制以某种形式将这些信息传递到硬件层面。我们在下一节描述此类机制。
7.2 区分内存操作的机制
本节描述几种可能的机制，用于传达上一节所述以程序员为中心的框架所需的信息。
7.2.1 在编程语言层面传达信息
我们考虑具有显式并行构造的编程语言。语言提供的并行编程支持范围可能从高级并行构造（如 doall 循环）到低级使用内存操作实现同步。因此，传达内存操作信息的机制取决于语言提供的并行支持。
许多语言指定了并行任务和同步的高级范式，并限制程序员使用这些范式。例如，考虑一种仅允许通过 doall 循环表达并行的语言。正确使用 doall 循环意味着，如果至少其中一次访问是写，则循环的两个并行迭代不应访问同一位置。因此，内存操作信息被隐式传达，因为高级程序中的任何操作都不参与竞争。 在稍低的层次上，语言可能提供常见同步例程的库，程序员被限制通过调用此类例程来实现同步。在这种情况下，程序员必须使用足够的此类同步调用来消除程序中其他操作之间的任何竞争。因此，类似于 doall 循环的情况，所有对程序员可见的内存操作信息（即，同步例程内部使用的操作除外）被隐式传达。当然，编译器或库例程的编写者仍然必须确保为实现 doall 循环或其他同步例程等构造而引入的额外操作的操作类型（即同步或数据）被传达给硬件等较低层次。 最后，程序员可能被允许直接使用程序层面可见的内存操作来实现同步（例如，使用内存位置作为 flag 变量）。在这种情况下，程序员必须显式传达操作类型信息。一种方法是将此信息与程序层面的静态指令相关联。例如，语言可以提供构造，将特定的静态代码区域标识为同步（或数据）；那么从该代码区域生成的所有动态操作都被隐式标识为同步（或数据）。另一种选择是将数据或同步属性与共享变量或地址相关联。例如，语言可能提供额外的类型声明，允许程序员识别用于同步目的的变量。 编程语言提供的机制类型和通用性影响传达所需信息的易用性。例如，在使用类型声明来指示操作类型的方法中，默认将所有操作视为数据（除非另有说明）可能是有益的，因为数据操作更频繁。另一方面，将同步类型作为默认值可以使初始可工作程序更简单，并可能通过要求程序员显式声明更激进的数据操作来减少错误。
7.2.2 向硬件传达信息
在编程语言层面传达的信息最终必须提供给底层硬件。因此，编译器通常负责将较高级别的信息适当地转换为硬件支持的形式。 类似于编程语言层面使用的机制，内存操作信息可以与特定地址范围相关联，也可以与操作对应的内存指令相关联。将信息与特定地址范围相关联的一种方法是将特定页面的操作视为数据或同步操作。将信息与特定内存指令相关联可以通过两种方式完成。第一种选择是提供多种内存指令（例如，通过提供额外的操作码）来区分内存操作。第二种选择是使用虚拟内存地址的任何未使用高位来实现这一点（即地址阴影）。最后，某些内存指令，如 compare-and-swap 或 load-locked/store-conditional，可能默认被视为同步。 大多数商业系统不提供上述功能来直接向硬件传达内存操作信息。相反，这些信息必须被转换为硬件层面支持的显式栅栏指令，以施加足够的排序约束。例如，为了在支持类 Alpha 内存屏障的硬件上提供弱序同步操作的语义，编译器可以在每个同步操作之前和之后都加上内存屏障。
8 讨论
有强有力的证据表明，通过启用多种硬件优化，宽松内存一致性模型比顺序一致性提供更好的性能 [9, 11, 6]。处理器速度相对于内存和通信速度的增长只会增加这些模型的潜在收益。除了在硬件层面提供性能收益外，宽松内存一致性模型在启用重要编译器优化方面也发挥着关键作用。上述原因导致许多商业架构，如 Digital Alpha、Sun SPARC 和 IBM PowerPC，支持宽松内存模型。此外，几乎所有其他架构也支持某种形式的显式栅栏指令，表明未来承诺支持宽松内存模型。不幸的是，关于内存一致性模型的现有文献浩瀚而复杂，其中大部分针对该领域的研究人员，而非典型的计算机系统用户或构建者。本文使用统一且直观的术语涵盖了与当今工业界代表性内存一致性模型相关的几个问题，旨在触及更广泛的计算机专业人员群体。 宽松内存一致性模型的一个缺点是编程复杂性的增加。这种复杂性很大程度上是因为文献中提出的许多规约将模型所启用的低级别性能优化直接暴露给程序员。我们之前的工作通过定义更高级别的抽象解决了这个问题；只要程序员提供关于内存操作的正确程序级信息，这种抽象就提供顺序一致性的假象。与此同时，High Performance Fortran 等语言标准化工作导致了与顺序一致性不同的高级内存模型。例如，High Performance Fortran 的 forall 语句指定了一组数组索引的计算，具有 copy-in/copy-out 语义，其中一个索引的计算不受其他索引计算产生的值的影响。总体而言，最佳内存一致性模型的选择远未解决，将受益于语言和硬件设计人员之间更积极的合作。
9 致谢
这项工作的大部分是作为我们学位论文研究的一部分完成的。我们非常感谢各自的导师 Mark Hill 以及 Anoop Gupta 和 John Hennessy，感谢他们在整个学位论文工作中的指导。我们特别感谢 Mark Hill 建议撰写这篇论文并鼓励我们写作。我们感谢 Sandhya Dwarkadas、Anoop Gupta、John Hennessy、Mark Hill、Yuan Yu 和 Willy Zwaenepoel 对本文早期版本提出的宝贵意见。我们还感谢 Andreas Nowatzyk、Steve Scott 和 Wolf-Dietrich Weber 分别提供有关 Sun Microsystems、Cray Research 和 HaL Computer Systems 开发产品的信息。
参考文献
[1] Sarita V. Adve. Designing Memory Consistency Models for Shared-Memory Multiprocessors. PhD thesis, Computer Sciences Department, University of Wisconsin-Madison, December 1993. Available as Technical Report #1198. [2] Sarita V. Adve and Mark D. Hill. Weak ordering - A new definition. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 2–14, May 1990. [3] Sarita V. Adve and Mark D. Hill. A unified formalization of four shared-memory models. IEEE Transactions on Parallel and Distributed Systems, 4(6):613–624, June 1993. [4] Francisco Corella, Janice M. Stone, and Charles M. Barton. A formal specification of the PowerPC shared memory architecture. Technical Report Computer Science Technical Report RC 18638(81566), IBM Research Division, T.J. Watson Research Center, January 1993. [5] Michel Dubois, Christoph Scheurich, and Fayé Briggs. Memory access buffering in multiprocessors. In Proceedings of the 13th Annual International Symposium on Computer Architecture, pages 434–442, June 1986. [6] Kourosh Gharachorloo. Memory Consistency Models for Shared-Memory Multiprocessors. PhD thesis, Stanford Univer- sity, 1995. [7] Kourosh Gharachorloo, Sarita V. Adve, Anoop Gupta, John L. Hennessy, and Mark D. Hill. Programming for different memory consistency models. Journal of Parallel and Distributed Computing, 15(4):399–407, August 1992. [8] Kourosh Gharachorloo,Sarita V. Adve, Anoop Gupta, John L. Hennessy,and Mark D. Hill. Specifying system requirements for memory consistency models. Technical Report CSL-TR-93-594, Stanford University, December 1993. Also available as Computer Sciences Technical Report #1199, University of Wisconsin - Madison. [9] Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Performance evaluation of memory consistency models for shared-memory multiprocessors. In Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 245–257, April 1991.
[10] Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Two techniques to enhance the performance of memory consistency models. In Proceedings of the 1991 International Conference on Parallel Processing, pages I:355–364, August 1991. [11] Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Hiding memory latency using dynamic scheduling in shared- memory multiprocessors. In Proceeding of the 19th Annual International Symposium on Computer Architecture, pages 22–33, May 1992. [12] Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Revision to “Memory consistency and event ordering in scalable shared-memory multiprocessors”. Technical Report CSL-TR-93-568, Stanford University, April 1993. [13] Kourosh Gharachorloo, Dan Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy. Memory con- sistency and event ordering in scalable shared-memory multiprocessors. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 15–26, May 1990. [14] IBM System/370 Principles of Operation. IBM, May 1983. Publication Number GA22-7000-9, File Number S370-01. [15] Arvind Krishnamurthy and Katherine Yelick. Optimizing parallel SPMD programs. In Languages and Compilers for Parallel Computing, 1994. [16] Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs.IEEE Transactions on Computers, C-28(9):690–691, September 1979. [17] Cathy May, Ed Silha, Rick Simpson, and Hank Warren, editors. The PowerPC Architecture: A Specification for a New Family of RISC Processors. Morgan Kaufmann Publishers, Inc., 1994. [18] Dennis Shasha and Marc Snir. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems, 10(2):282–312, April 1988. [19] Richard L. Sites, editor. Alpha Architecture Reference Manual. Digital Press, 1992. [20] The SPARC Architecture Manual. Sun Microsystems Inc., January 1991. No. 800-199-12, Version 8. [21] David L. Weaver and Tom Germond, editors. The SPARC Architecture Manual. Prentice Hall, 1994. SPARC International, Version 9.
本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。