Consistency (A.K.A., Memory Consistency, Memory Consistency Model, or Memory Model)

定义:
在共享内存上执行的多线程程序所被允许的访存行为的规范。

对程序员可见

共享内存行为

问题:

乱序 CPU 可能对访存顺序重新排序，这样的重排对于单核本身而言执行结果是正确的，但在多核中可能与其他核的访存顺序在并发执行时存在矛盾
并发执行的结果存在不确定性

这些不确定的执行结果可能是非预期的，但均没有违反 coherence 定义的 SWMR 不变性。

共享内存行为应当定义所有线程的所有执行。

内存一致性模型

Consistency Model	Feature	Implement	Case
Sequential Consistency (SC)	最严格，最符合直觉	严格定序	MIPS R10K
Total Store Order (TSO)	性能有提升	使用 FIFO 保证写顺序	x86 and historical SPARC systems
relaxed/weak memory consistency models (XC)	性能更高，实现更简单	FENCE 指令实现同步	IBM Power

TSO 在执行模型和实现上均是 SC 的子集，因此 TSO 比 SC 更松散 (relaxed/weaker)

与 Coherence 的区别

Consistency 规定程序访存行为
Coherence 提供内存抽象 (black box)

Good Memory Consistency Model (3P + 1P)

Programmability 可编程性：应当使多线程编程更容易
Performance 性能：在合理的功耗面积的约束下可以达到高性能
Portability 可移植性：可以被广泛采用，具有后向兼容性，可以翻译为其他模型
Precision 精确性：足够精确的定义（数学语言）

Coherence (A.K.A., Cache Coherence)

Cache 一致性，硬件用于实现 Memory Consistency 的手段，对程序员不可见

定义

实现视角的定义:
满足 SWMR Invariant 和 Data-Value Invarient

程序员视角的定义:

类似 Sequential consistency (SC) 的定义: 以每个执行线程的程序顺序为准在单个内存地址上执行多个线程的访存
两个不变性的定义:
- liveness invariant: 每个 store 最终对所有的核可见
- safety invariant: 对同一内存地址的写入必须串行化
Hennessy and Patterson 定义, 三个不变性:
- 对地址 A 的 load 访问获取该核先前对 A 的 store, 除非有其他核在这之间有对 A store
- 对地址 A 的 load 访问获取其他核对 A 的 store, 要求该 store 和该 load 之间间隔的时间足够长，且二者之间没有发生过其他 store
- 对同一地址的 store 必须串行化

问题场景:
多个线程对同一内存地址(存在多个副本)的访问中至少有一个是写

目的:
使 cache 在共享内存中的行为同在单核系统中一致。具体而言，实现的一致性协议需要使一个线程对某个 cache 的写可以被其他线程看到（广播到所有 cache ）

不同的 Cache 一致性协议实现对于广播的时机不同:

consistency-agnostic coherence
- 同步广播：写请求在返回给 core 之前对其他所有 core 可见
Consistency-directed coherence
- 异步广播: 写请求可以在对其他所有 core 可见之前返回（其他 core 可以观察到写之前的值）
- 由 Consistency 管理写请求的顺序以保证正确性
- 主要用于 GPGPU 中并取得较高的性能提升

Consistency-Agnostic Coherence

其行为类似对原子存储的访问 (without cache)

最常见的一致性协议： MOESI
一致性协议的硬件实现
Snooping 一致性协议
- 硬件实现简单： cache 控制器争夺共享总线并广播请求
- 可扩展性差，现代总线过多导致比较复杂
- cases: Sun UltraEnterprise E10000, IBM Power5
Directory 一致性协议
- 可扩展性更高
- 每个 cache 存储一部分地址空间的内容，没有副本, cache 之间通过数据包通信（只有一个目的 cache ）
- cases: SGI Origin 2000, AMD HyperTransport, HyperTransport Assist, and Intel QuickPath Interconnect (QPI)

Token Coherence
- 每个内存地址拥有一定的 token (token 数等于核心数), 当一个核拥有所有的 token 时才可以对该内存地址进行写访问，拥有一个或多个 token 才可以进行读访问

Coherence Invariants 需要满足的不变性要求：(二者共同保证了同步传播)

Single-Writer, Multiple-Reader (SWMR) Invariant: 在任意时间对同一内存地址的访问中最多有一个写，且在写访问时不允许其他的读访问
Data-Value Invariant: 对于一个内存地址的访问，该值从任意时间段开始到下一次写之间的时间段内保持不变

维持 Coherence Invariants: Coherence Protocols -> invalidate protocols

如果一个核试图读一个内存地址
- 向其他核发送信息获取该内存的当前值
- 确保其他核的该内存的副本没有处于写状态
如果一个核试图写一个内存地址
- 如果该核还没有该内存有效的只读 cache 副本，则向其他核发送信息获取该内存的当前值
- 确保其他核该内存的副本没有处于写访问或读访问

实现

Coherence Protocols 实现的粒度:
一般而言以 cache block 为基本粒度，但是理论上可以有更细(硬件代价更高昂)或者更粗(性能更差)的粒度

cache protocol 需要实现的结构:: (coherence controller)
组成一个分布式系统，互相交换信息 (for each cache block) 。每一个控制器本质上是一个有限状态机的集合，每个状态机管理一个 cache block 的状态，并且接受和处理事件。

在 cache 端，为 cache controller
在 LLC/memory 端，为 memory_controller

cache controller

core side: 接受来自核的访存请求，返回数据值
network side: 发送和接受一致性请求(通过互联网络与系统其他的控制器交互)

memory controller

只有 network 端
不会发送一致性请求和接受一致性响应

xixi's blog

Memory Consistency And Cache Coherence