chapter2：coherence基础

在本章将充分介绍cache coherence，以了解一致性模型如何与缓存交互。2.1节开始介绍贯穿本书的系统模型。第2.2节解释了必须解决的缓存一致性问题以及不一致性的可能性是如何产生的。第2.3节精确地定义了缓存一致性

1、基准系统模型（Baseline System model）

基准系统模型定义为具有共享内存的多核处理器系统。也就是所有核心都可以对所有(物理)地址执行load、store操作，如图所示，多核处理器系统由多个单线程core组成，每个core有自己的私有数据缓存，以及一个由所有core共享的LLC。本书中cache指的是私有数据缓存，而不是LLC。每个core的数据缓存都是用物理地址访问，并采用write back方式(更新cacheline，cacheline撤出时更新内存)。cores与LLC通过互联网络相互通信。LLC在逻辑上属于内存测缓存（memory-side cache），因此不会引入另一个级别的coherence问题。LLC旨在减少内存访问的平均延迟，并增加内存的有效带宽，同时作为内存控制器。

此基准系统忽略了指令缓存、多级缓存、多核共享缓存、TLB、DMA等部分，这些暂时不需要讨论。

2、Incoherence是如何产生的

incoherence的出现仅源于一个基本问题：存在多个可以访问缓存和内存的master。在现代系统中，这些master可以是core、DMA和可以读取写入缓存和内存的外部设备。在本书中，可能更关心core，但其他master也需要考虑。

如图是一个incoherence的示例。最初，cache位置A在内存中的值为42，然后core2将此值同样加载到cache中。在time3时core1更改缓存中A的值从42变为43，此时core2的缓存中A的值过时，如果这时core2执行（while A==42）这句话，就会卡死。为了防止出现这种问题，系统必须规定一套cache coherence规则，使core1的操作对core2可见。

3、定义coherence

coherence首选的第一条定义是单写入多读取SWMR。对于任何给定的内存位置，在任何时刻，要么有一个core可以写它，要么有多个core可以读它。不可能存在一个core可以写入同时其他core可以写入或读取该位置。将一个内存位置的生命周期划分为上图所示的多个epoch，在某个节点中，要么单个core具有读写访问权限，要么多个core只有读权限。

除了SWMR外，coherence还要求给定内存位置的值被正确传播。在上图中，即使满足SWMR，如果core2和core5读到的值不同，那么系统是不一致的。同样如果第三个epoch时core1读到的值与第二个epoch时core3写入的不一样，系统也是不正确的。

SWMR需要结合数据invariant一起定义coherence。这里对于数据一致性的定义没看懂：This invariant states that the value of a memory location at the start of an epoch is the same as the value of the memory location at the end of its last read–write epoch.

3.1、保持coherence invariant

上一节中介绍的 coherence invariant提供了一些关于 coherence 协议如何工作的直观认识。绝大多数 coherence 协议，称为“invalidate protocol”，都是为了维护这些invariant而明确设计的。如果一个core想要读取一个内存位置，它会向其他core发送消息以获取该内存位置的当前值，并确保没有其他core缓存该内存位置处于读写状态的副本。这些消息可以结束任何其他core正在进行的读写epoch并开始一个只读epoch。如果一个core想要写入一个内存位置，并且还没有有效的只读缓存副本，它会向其他core发送消息以获取内存位置的当前值，并确保没有其他核心有只读或读写状态缓存内存位置的副本。这些消息可以结束任何其他core正在进行的读写或只读epoch，并开始一个新的读写epoch。这本入门读物关于缓存 coherence 的章节（第 6-9 章）极大地扩展了对invalidate protocol的抽象描述，但基本认识保持不变。

3.2、coherence粒度

core可以以各种粒度执行 load 和 store，通常范围为 1-64 字节。 理论上，可以以最精细的 load/store 粒度执行 coherence。 然而，在实践中，coherence 通常保持在cache block的粒度上。 也就是说，硬件在cache block的基础上强制执行 coherence。 在实践中，SWMR 不变量很可能是，对于任何内存块，要么有一个写入者，要么有一个或多个读取者。 在典型系统中，一个core不可能写入block的第一个字节，而另一个core正在写入该block中的另一个字节。 尽管cache block粒度很常见，而且我们在本入门书的其余部分都假设这一点，但应该知道有些协议在更细和更粗的粒度上保持 coherence。

侧边栏：coherence定义

我们首选的coherence定义是不同core对内存位置的访问权限和核之间传递数据的正确性。但还有一类侧重于load、store的定义，类似于内存一致性模型如何指定load、store在体系结构上可见的顺序。
指定 coherence 的一种 consistency-like 的方法与Sequencial consistency（SC） 的定义有关。SC 是我们在第 3 章中深入讨论的内存 consistency 模型，它指定系统必须按照每个线程的程序顺序的总顺序执行所有线程的加载和存储到所有内存位置。每次加载都会获取该总顺序中最近存储的值。与 SC 的定义类似的 coherence 的定义是，一个 coherent 系统必须看起来按照每个线程的程序顺序的总顺序执行所有线程的加载和存储到单个内存位置。这个定义强调了文献中 coherence 和 consistency 之间的一个重要区别：coherence 是在每个内存位置的基础上指定的，而 consistency 是针对所有内存位置指定的。值得注意的是，任何满足 SWMR 和数据值不变量的 coherence 协议也可以保证满足这种 consistency-like 的 coherence 定义。 （然而，反过来不一定是真的。）
Coherence 的另一个定义 [1, 2] 定义了具有两个invariant的coherence：（1）每个存储最终都对所有核心可见，（2）对相同内存位置的写入被序列化（即，所有核心以相同的顺序观察）。 IBM 在 Power 架构 [4] 中采取了类似的观点，部分原因是为了便于实现：其中一个核心的一系列存储可能已经到达某些核心（它们的值对这些核心的负载可见）但不包括其他核心。
Hennessy 和 Patterson [3] 规定的另一个 coherence 定义由三个invariant组成：(1) 核心加载到内存位置 A 会获得该核心先前存储到 A 的值，除非另一个核心中间已存储到 A； (2) 如果 S 和负载“在时间上充分分离”并且如果 S 和负载之间没有发生其他存储，则对 A 的加载获得另一个核心对 A 的存储 S 的值； (3) 存储到相同的内存位置被序列化（与前面定义中的不变量 2 相同）。与前面的定义一样，这组不变量同时捕获了安全性和活性。

3.3、coherence范围

无论我们选择哪种coherence定义都有一个特定的范围，架构师必须意识到它何时适用，何时不适用。 我们现在讨论两个重要问题：

• Coherence 适用于所有保存共享地址空间块的存储结构。 这些结构包括 L1 数据缓存、L2 缓存、共享最后一级缓存 (LLC) 和主存储器。 这些结构还包括 L1 指令高速缓存和转换后备缓冲区 (TLB)。（注2）

原书作者注 2：在某些架构中，TLB 可以保存不是共享内存中block的副本的映射。

• coherence不属于架构(也就是说，coherence在架构上是不可见的)。严格地说，如果遵循指定的内存一致性模型，系统可能是incoherence的，但仍然是正确的。虽然这个问题看起来有点奇怪(也就是说，很难想象一个实际的系统是consistence的，但incoherence的)，但它有一个非常重要的推论:内存一致性模型对coherence或用于实现coherence的协议没有明确的约束。尽管如此，正如第3章到第5章所讨论的，许多一致性模型的实现依赖于某些常见的coherence特点来保证正确性，这就是为什么我们在继续讨论一致性模型之前在本章介绍一致性