chapter3：内存为什么需要consistency和顺序 Consistency

本章深入研究内存 consistency 模型，这些模型为程序员和实现者定义了共享内存系统的行为。这些模型定义了行为正确性，以便程序员知道期望什么，实现者知道提供什么。

1、共享内存行为存在的问题

要了解为什么必须定义共享内存行为，考虑上表给出的执行情况。（这个例子和本章中的所有例子一样，假设所有变量的初始值都是零。）大多数程序员会期望core2 的寄存器 r2 应该得到值 NEW。然而，在当今的某些计算机系统中，r2 可以为 0。

对于单核来讲，core1的S1和S2操作访问不同的内存地址，并没有相关性，所以可以进行重排序。但这种重排序可能导致core1和core2的执行顺序变为S2、L1、L2、S1

这个执行结果满足coherence，并没有违反SWMR规则，所以得到错误结果的原因并不是incoherence。

对于表3.3，直觉上人们认为r1、r2可能存在三种情况

• (r1, r2) = (0, NEW) 用于执行 S1、L1、S2，然后是 L2
• (r1, r2) = (NEW, 0) 用于 S2、L2、S1 和 L1
• (r1, r2) = (NEW, NEW)，例如，对于 S1、S2、L1 和 L2

但对于x86系统，也允许(r1,r2)=(0,0)，因为内部采用了FIFO提高性能，同样满足coherence。所以这段程序可能存在四种结果，所以在定义共享内存行为时要进行充分考虑。

2、什么是内存consistence模型

consistence模型，是对使用共享内存执行多线程程序进行的行为规范。对于使用特定输入数据执行的多线程程序，它制定了动态加载可能返回的值及内存的最终状态。与单线程执行的区别在于，多线程执行可能存在多个正确的行为。

通常 memory consistency model（MC）将执行划分为遵守MC和不遵守MC。根据执行的划分，反过来可以将实现分为MC实现和非MC实现。MC实现是一个只允许MC执行的系统，而非MC实现有时允许非MC执行。

3、consistence和coherence对比

上一章定义了coherence的两条法则，看起来也是对共享内存行为的规范。但实际不是，原因有三：

• cache coherence的目标是使多核系统中的缓存像单核系统中一样不可见。既然不可见，就不需要从系统层面规范行为。
• coherence通常只对cache block进行处理，不参与多个block之间的通信。实际的完整程序会横跨多个block访问。
• 即使系统没有cache，没有coherence，也可能可以正常工作。

虽然coherence不是必须的，但多数共享内存系统都使用cache coherence来实现consistence model。consistence model在实线时可以将cache coherence当作黑盒。

4、sequential consistency（SC）基本思想

单核顺序处理器：the result of an execution is the same as if the operations had been executed in the order
specified by the program

多核顺序模型：the result of any execution is the same as if the operations of all processors (cores) were executed in some sequential order, and the operations of each individual processor (core) appear in this sequence in the order
specified by its program.

图 3.2 描述了执行表 3.1 中的示例程序。中间的垂直向下箭头表示内存顺序 (<m)，而每个核心的向下箭头表示其程序顺序 (<p)。我们使用运算符 <m 表示内存顺序，因此 op1 <m op2 意味着 op1 在内存顺序上先于 op2。类似地，我们使用运算符 <p 来表示给定核心的程序顺序，因此 op1 <p op2 意味着在该核心的程序顺序中 op1 在 op2 之前。在 SC 下，内存顺序尊重每个核心的程序顺序。 “尊重”意味着 op1 <p op2 意味着 op1 <m op2。注释 (/* ... */) 中的值给出了加载或存储的值。此执行以 r2 为 NEW 结束。更一般地，表 3.1 程序的所有执行都以 r2 作为 NEW 终止。唯一的不确定性——L1 在加载值 SET 一次之前加载 flag 为 0 的次数——并不重要。

图3.2说明了表3.3的四次执行，图 3.2c 仅描述了导致 (r1, r2) = (NEW, NEW); 的四种可能的 SC 执行中的一种。本次执行为{S1, S2, L1, L2}，其他为{S1, S2, L2, L1}, {S2, S1, L1, L2}, 和{S2, S1, L2, L1}。因此，在图 3.2a到c 中，有六次合法的 SC 执行。均满足，S1先于L1执行，S2先于L2执行。

图2d中给出了（0，0）的执行过程，如果结果为（0，0），那么执行顺序其中一种可能为（L1,L2,S1,S2）不符合顺序要求。

5、一点SC的形式化方法

在本节中，对SC进行更精确定义。采用 以下符号：L(a) 和 S(a) 分别表示加载和存储地址 a。符号 <p 和 <m 分别定义程序和全局内存顺序。程序顺序 <p 是每个核心的总顺序，它捕获每个核心在逻辑上（按顺序）执行内存操作的顺序。全局内存顺序 <m 是所有核心的内存操作的总顺序

SC 执行 (SC execution) 需要以下操作：

1、所有核心都按照程序顺序将它们的L和S插入到 <m 的排序中，无论它们是否是相同地址。

• If L(a) <p L(b) => L(a) <m L(b) /* Load -> Load */
• If L(a) <p S(b) => L(a) <m S(b) /* Load -> Store */
• If S(a) <p S(b) => S(a) <m S(b) /* Store -> Store */
• If S(a) <p L(b) => S(a) <m L(b) /* Store -> Load */

2、每次load都把最后一个store的值（按全局内存顺序）获取到同一地址：

表 3.4 中总结了 SC 的 ordering 要求。该表指定了 consistency 模型强制执行的程序顺序。例如，如果给定线程在程序顺序中在store之前有一个load（即，加载是“load 1”，store是表中的“操作 2”），那么这个交点处的表条目是“X ” 这表示这些操作必须按程序顺序执行。对于 SC，所有内存操作都必须按照程序顺序执行；在我们在接下来的两章中研究的其他 consistency 模型下，其中一些排序约束是放松的（即，它们的排序表中的一些条目不包含“X”）。

6、简单的 SC 实现

SC 允许两个简单的实现，这使得更容易理解 SC 允许哪些执行。

多任务单处理器 (The Multitasking Uniprocessor)

多任务单处理器 首先，可以通过在单个顺序核心（单处理器）上执行所有线程来为多线程用户级软件实现 SC。线程 T1 的指令在核心 C1 上执行，直到上下文切换到线程 T2 。在上下文切换时，必须在切换到新线程之前完成任何挂起的内存操作。检查表明所有 SC 规则均得到遵守

交换机 (The Switch)

其次，可以使用一组核心 C、单个交换机和内存来实现 SC，如图所示。假设每个核心按其程序顺序向交换机提交一次内存操作请求。每个核心都可以使用任何不影响它向交换机呈现内存操作的顺序优化。例如，可以使用带有分支预测的简单五级顺序流水线。

接下来假设交换机选择一个核心，让内存完全满足load或store，只要请求存在，就重复这个过程。交换机可以通过任何方法（例如，随机）选择核心，该方法不会因就绪请求而使核心挂死。此实现通过构造在操作上实现 SC

评估 (Assessment)

这些实现提供了操作模型，定义了 (1) 允许的 SC 执行和 (2) SC 实施“黄金标准”。 交换机实现还作为存在证明SC 可以在没有缓存或 coherence 的情况下实现。

当然，坏消息是，由于在第一种情况下使用单个核心和在第二种情况下使用单个交换机/内存的顺序瓶颈，这些实现的性能不会随着核心数量的增加而扩展。这些瓶颈导致一些人错误地认为 SC 排除了真正的并行执行。它没有，我们将在下面看到。

7、具有coherence的SC实现

cache coherence的存在有利于SC的实现，可以方便并行执行非冲突的load和store（如果两个操作针对同一个地址且其中至少一个操作为store，则发生冲突）。

在这里将 coherence 主要视为实现第 2 章的 SWMR 规则的黑盒。下面是一些属性：

• 使用状态修改 (M) 表示一个核心可以读写的 L1 block
• 使用状态共享 (S) 表示一个或多个核心只能读取的 L1 block
• GetM 和 GetS 分别表示在 M 和 S 中获得block的 coherence 请求。

图 3.4描绘了图 3.3 的模型，其中交换机和内存被一个coherent 缓存系统取代，表示为一个黑盒子。每个核心按其程序顺序向 coherent 缓存系统提供内存访问请求。在开始对同一核心的下一个请求之前，内存系统会完全满足每个请求。图b中加入L1 cache，这使得存储系统可以同时完成不冲突的访问请求，实现并行响应，并且这些请求可以按任何逻辑顺序放入<m。

图3.5中四个core的操作不冲突，可以由各自的L1 cache并发响应。图3.5b中的<m排序可以任意完成，都符合SC模型。

8、使用缓存 Coherence 优化 SC 实现

大多数真正的core实现consistence都比我们具有cache coherence 的基本 SC 实现更复杂。core采用预取、推测执行和多线程等功能来提高性能并容忍内存访问延迟，这些特性与内存接口交互，并对SC实现产生影响。值得记住的是，只要不影响最终结果，任何优化都是合法的。

Non-Binding Prefetching（https://zhuanlan.zhihu.com/p/373038275）

在一致性内存系统中，对块B的非绑定性预取会更改块B在缓存中的一致性状态。更一般地说，这种预取行为是由软件/处理器核部分硬件/缓存部分硬件通过发出一致性请求，来获得某个块在L1 缓存中的读写权限的行为。这种预取不会改变任何块B的数据或寄存器状态，因其对于SC模型的实现没有任何影响。非绑定预取操作仅限于图3.5的L1 cache中，对整个 consistency系统没有影响。

推测核心 (Speculative Cores)

考虑一个处理器核按照程序顺序执行load/store，同时允许分支预测，在分支预测错误后冲刷流水线。假设在分支指令后执行了load/store指令，如果分支预测错误，这些load/store会被冲刷，使得它们实际的效果像上述非绑定性预取那样，对SC的实现没有影响。

• 对于分支预测后的load而言，可能会产生L1 miss（发送GetS）；可能会产生hit并给寄存器返回值。如果load被冲刷了，处理器核心简单不执行寄存器的更新操作即可——就像load从未被操作一样。
• 对于分支预测后的store而言，处理器核可能会提前发送GetM进行预取，但直到消息被提交前store操作都不会被执行。这样避免了对SC模型的破坏。

Dynamically Scheduled Cores

现代处理器可能实现动态调度，以达到比顺序执行更高的性能。在多核处理器背景下，引入了新的内存一致性推测问题。考虑两笔load操作L1、L2，L2地址更先计算出来。多核处理器会先执行L2，并且可能对其他core不可见，这将违反SC。有两种技术来检查这种情况。

第一种方法是推测性地执行L2，但是提交L2之前，处理器检查推测访问的缓存块是否已经离开了缓存。只要缓存块仍然在缓存中，值就没有变化。为了执行这个检查，处理器跟踪L2 load的地址，并将evict的缓存块和传入的一致性请求进行对比，一个传入的GetM表明另一个处理器可以观察到L2的miss，而这个GetM表明推测性的load执行错误，需要冲刷推测路径。

第二种方法是在处理器准备提交load指令时replay每个推测性的load。如果提交时load的值不等于之前推测load的值，那么预测就不正确。

动态调度内核中的非绑定预取

一个动态调度的内核可能会遇到不按程序顺序load和store的情况，如程序顺序是load A，store B，store C，但可能不按照这个顺序进行非绑定预取，如GetM C，然后并行执行GetS A和GetM B，但这不会影响SC，SC只要求一个处理器的load和store从外界看上去按照程序顺序访问其L1缓存。简而言之，一致性模型决定了load/store（在其它核看上去）访问一致性内存的顺序，但不固定coherence 响应的顺序

多线程

SC模型同样允许多线程处理器核的实现，在这种情况下处理器核需要逻辑上被视为多个（虚拟）核，L1cache有switch来选择服务于哪个（虚拟）核。

9、SC的原子操作

在微架构中实现原子指令本身不难，但是过于简化的设计可能会导致性能不佳，例如实现原子指令的一个正确但简单的方法是让处理器锁定内存系统（即防止其他内核发出内存访问）并对内存进行读取、修改和写入操作。这种实现虽然正确而直观，但却牺牲了性能。

RMW更激进的实现是利用了SC可以保证所有请求按顺序发出。因此，一个原子RMW操作可以通过让一个核心在缓存中获得M状态的缓存块（此时其它core不能读也不能写）来实现，然后在缓存中进行load和store，不需要任何一致性消息或者总线锁定，只需要在此过程中阻塞其他处理器传来的一致性请求，并在store真正完成之后再响应其他处理器即可，这个过程不会有死锁的风险。

测验问题3：为了执行一个原子的read-modify-write（如test-and-set），一个核必须始终与其他核进行通信。
答：错误。

一个更加优化的实现可以在不违反原子性的情况下，允许在load和store之间有更多的时间。考虑这样的情况，一个缓存块当前处于S状态，RMW的load可以立即进行推测执行，与此同时缓存控制器发出一致性请求，将块的状态更新为M状态，更新完成后就可以执行store。这个过程不一定能保证原子性，因此为了检查原子性，处理器核必须检查load的缓存块是否在load和store之间从缓存中被evict，类似于前一节中检测错误的推测性load指令的过程。

10、实例MIPS R10000

R10000 是一款四路超标量 RISC 处理器内核，具有分支预测和乱序执行功能。该芯片支持 L1 指令和 L1 数据的write back cache，以及到（片外）统一 L2 缓存的专用接口。

在执行过程中，R10000处理器核按程序顺序向地址队列发出（推测性）load和store。load从上一个相同地址的store指令中获得推测性的值，如果没有，则从数据缓存中获得值。load和store按程序顺序提交，然后删除其地址队列条目。提交store时，缓存块必须在M状态下，并且缓存块必须原子地更新。

重要的是，如果发生了缓存块evict（可能是由于一致性请求或者仅仅是为其他的数据腾出空间），且evict的缓存块地址对应了地址队列中的某个load请求，那么这个load请求和后面所有的指令都要被冲刷，并重新执行。因此，当load最终提交时，load的缓存块在执行和提交之间一直在缓存中，因此这个期间load的值不会被改变。由于store在提交时实际写入缓存，R10000在逻辑上将load和store按程序顺序提交给内存系统，从而实现了SC。