BLOG

pipeline基础

🔹 基本 5 阶段流水线

🔹 涉及的核心硬件单元

1. PC + I-Cache
   • 提供下一条指令。
   • PC 递增或被分支单元修改。
2. Decoder + Control Unit
   • 翻译指令 → 控制信号。
   • 决定 ALU 操作类型、是否访存、是否写回。
3. Register File
   • 提供源操作数。
   • WB 阶段写回结果。
4. ALU
   • 负责算术/逻辑运算。
   • 分支判断、地址计算都由 ALU 或专用单元完成。
5. AGU (Address Generation Unit)
   • 生成内存地址（基址 + 偏移）。
   • 和 MEM 阶段的 D-Cache 交互。
6. Data Cache / Memory
   • 读写数据。
   • 如果 cache miss，需要和内存层次（L2/LLC/DRAM）交互。
7. Pipeline Registers (IF/ID, ID/EX, EX/MEM, MEM/WB)
   • 保持各阶段中间结果，维持流水线工作。

🔹 现代处理器的扩展

在乱序/多发射 (OoO / Superscalar) 核心里，基本 5 阶段被扩展成更复杂的流水线：

• 取指前端
  • 分支预测器 (Branch Predictor)
  • 指令队列 / 指令缓存 (I-Cache + uop Cache)
• 指令调度 / 乱序执行
  • Reorder Buffer (ROB)
  • Reservation Stations (RS)
  • Register Renaming (物理寄存器文件 PRF)
• 访存单元
  • Load Queue / Store Queue (LQ/SQ)
  • Write Buffer / Store Buffer
• 执行单元
  • 多个 ALU、FPU、SIMD 单元、AGU
• 访存层次
  • 多级 Cache (L1D, L2, LLC)，一致性协议 (MESI/MOESI)

program到cpu到memory model

Memory coherence 定义了写入地址X的内容最终会传播到其他处理器

Memory consistency 处理写入X的内容何时传播到其他处理器，相对于其他地址

Sequential consistency 所有处理器按程序顺序发出load和store操作，内存随机选择一个个处理器完成一个操作然后再选择另一个处理器

Total store ordering（TSO）

Processor consistency

Coherence protocol Basic

Consistency-agnostic coherence

Consistency-directed coherence

一致性不变量

• 单写多读（SWMR）不变量来定义缓存一致性。对于任何给定的内存位置，在任何给定的时间点，要么有一个单一的核心可以写入它（并且它也可能读取它）或一些核心可能读取它。
• 数据值不变式。一个时代开始时内存位置 A 的值与其最后一个读写时代结束时内存位置 A 的值相同。

有其他的”一致性定义”可以在更细或更粗的粒度上保持一致性

Core重排序内存访问

store-store重排：core有一个非FIFO写缓冲区（cache miss/写操作合并）

store-store重排：动态调度（指令流投机执行）

store-load/load-store重排：乱序执行（单个线程内不同地址的load/store重排序执行）

具有缓存一致性优化SC实现

Non-Binding Prefetching对内存一致性没有影响

在处理器访问内存时，延迟很高。为了减少等待，硬件或软件会提前把可能需要的数据从内存取到缓存里，这就是预取。

“非绑定”的含义

绑定预取（binding prefetch）：一旦发起预取，预取的数据会直接“绑定”到某个即将执行的 load 指令上，相当于替这个 load 提前取好数据。

非绑定预取（non-binding prefetch）：预取只是把数据放进缓存（或预取缓冲区），但是不和具体的 load 指令绑定。如果未来真的有指令访问这些数据，就能命中缓存；如果没有用到，则预取的数据会被丢弃，不影响程序正｜确性。

特点

• 降低耦合度：CPU 不必等待预取完成才能继续执行 load，指令语义不依赖预｜取结果。
• 提高灵活性：即使预取失败（预测错了），程序也能正常执行，只是没有性能｜收益。
• 不保证命中：相比绑定预取，非绑定预取的命中率和有效性更依赖预测算法。

Speculative Cores分支预测错误可以将load/store伪装成Non-Binding Prefetching而保证推测执行正确，分支预测之后的加载可以提交给 L1 缓存，其中它要么未命中（导致非绑定的 GetS 预取）要么命中然后返回一个值到寄存器。如果加载被取消，核心会丢弃寄存器更新，消除加载的任何功能影响——就像它从未发生一样。缓存不会撤销非绑定预取，因为这样做是不必要的，如果加载被重新执行，预取块可以有助于性能。对于存储，核心可能会提前发出非绑定的 GetM 预取，但它不会在存储保证提交之前将其提交给缓存。

Dynamically Scheduled Cores动态重新排序两个加载操作 L1 和 L2 的执行对其他核心是不可见的，这会违反 SC，需要核心验证预测是否正确。有两种执行此检查的技术：

• 只要块保持在缓存中，其值在加载执行和提交之间不可能发生变化。为了执行此检查，核心跟踪 L2 加载的地址，并将其与被驱逐的块和传入的保持一致请求进行比较。
• 第二种检查技术是在核心准备提交加载操作时回放每个推测性加载[2, 17]。如果在提交时加载的值不等于之前推测性加载的值，那么预测是错误的

Non-Binding Prefetching in Dynamically Scheduled Cores SC 只约束 load/store 的对外可见顺序，不约束核心内部或 coherence 协议层面发消息的顺序

SC规定了加载和存储应用一致性内存中的顺序，但并不规定一致性活动的顺序

为了进一步隐藏 store miss 延迟，有学者提出了 更激进的 SC 执行方式：

• 让 load 和 store 在 store miss 尚未完成的情况下，也能继续退休（retire）。
• 这意味着处理器会“投机”认为这些指令完成了，但实际上它们的结果可能还没完全提交到内存。

为了保持正确性，处理器必须 单独保存这些“投机退休”的指令状态，一旦发现投机错误，还能回滚。

• 细粒度（fine-grained）：逐条指令跟踪投机状态。
• 粗粒度（coarse-grained chunk）：按一大块指令为单位来跟踪

SC的原子指令

一般需要原子指令实现自旋锁或其他同步原语，实现原子指令：

锁定内存系统

即阻止其他核心发出内存访问请求，然后对其内存执行读取、修改和写入操作，代价太大，影响性能

通过cache corherence优化：

1. 核心先把目标 block 拉到自己缓存里，拿到 M (Modified) 状态。
   • 在 MESI 协议下，M 状态意味着“这个核心独占了这个缓存块，而且拥有最新值”。
   • 拿到 M 状态后，别的核心暂时不能访问这个块。
2. 在本地执行 load + store（即 RMW 操作），不需要额外 coherence 消息或总线锁。因为此时这个块在本核心是独占的，本地就能保证原子性。

   关键点：必须推迟处理外部 coherence 请求，直到 RMW 的 store 完成。

   • 举例：如果别的核心发来 “GetS/GetM” 请求，本核心要“等到自己完成 store 再响应”。
   • 这样保证了 RMW 操作在全局顺序里是一个原子步骤。

进一步优化：

允许 Load 部分先投机执行，同时异步去申请写权限；等到权限拿到后再完成 Store。

• 优点：
  • 减少等待时间：读操作可以马上用，不用等写权限到手。
  • 减少全局阻塞：不用锁总线，只是针对这个缓存行发 coherence 请求。
• 缺点：
  • 更复杂 → 需要硬件追踪缓存行状态，保证期间不被驱逐，否则要回滚。
  • 存在投机失败（需要重试）的可能

TSO（Total Store Order）

有写缓冲区硬件就不是SC，这使得写缓冲区在多核处理器中必须具有架构可见性。

对于写缓冲区可见性的一个应对方法是将其关闭，但供应商一直不愿这样做，因为可能影响性能。另一个选项是使用激进、推测性的 SC 实现，使写缓冲区再次不可见，但这会增加复杂性，并且可能浪费电力来检测违规和处理误推测。

Load → Load

Load → Write

Write → Write

Write → Load

TSO允许Write → Load中的Load先执行（所以不符合SC），从而导致核心可以看到未被写入的值，所以write和load之间需要插入fence指令来阻止这种优化。

实现

大多数当前的 TSO 实现似乎只采用 SC 实现并插入写缓冲区。

推测执行核心如何具体实现TSO：微架构可以将存储队列（未提交的存储）和写缓冲区（已提交的存储）在物理上合并，并且/或者将加载和存储队列在物理上分离。

多线程为 TSO 引入了一个微妙的写缓冲区问题。TSO 写缓冲区在逻辑上属于每个线程上下文（虚拟核心）。因此，在一个多线程核心上，一个线程上下文不应该绕过另一个线程上下文的写缓冲区。这种逻辑分离可以通过每个线程上下文的写缓冲区实现，或者更常见的是，通过使用带有线程上下文标识符标记的共享写缓冲区实现，只有当标记匹配时才允许绕过。

原子指令

由于读-改-写操作的加载部分不能在更早的存储操作排序完成（即退出写缓冲区）之前执行，因此原子读-改-写操作会先清空写缓冲区，然后才能执行读-改-写操作的加载部分。此外，为了确保存储部分能在加载部分之后立即排序，加载部分需要读写一致性权限，而不仅仅是普通加载所需的读权限。最后，为了保证读-改-写操作的原子性，缓存控制器不能在加载和存储之间释放一致性权限。

读-改-写操作有更优化的实现方式。例如，只要满足以下条件，写缓冲区就不需要清空：(a) 写缓冲区中所有已存在的条目在缓存中具有读写权限，并在读-改-写操作提交之前保持该权限；(b) 核心执行 MIPS R10000 风格的加载推测检查（第 3.8 节）。从逻辑上讲，所有更早的存储和加载操作将作为一个单元（有时称为“块”）在读-改-写操作之前立即提交。

由于 TSO 只允许一种类型的重排序，FENCE 指令并不常见，且 FENCE 指令的实现并不太关键。一个简单的实现：当执行 FENCE 时清空写缓冲区，并禁止后续加载操作直到更早的 FENCE 提交——这种方式可能提供可接受的性能。

XC & RC

XC

1. FENCE 指令可以用多种不同的方式实现（见第 5.3.2 节），但它们必须强制顺序。具体来说，无论地址如何，以下顺序都不能重排：
   1. Load → FENCE,
   2. Store → FENCE,
   3. FENCE → FENCE,
   4. FENCE → Load
   5. FENCE → Store
2. 对于相同地址，重排单元可能不会重排
   1. Load → Load, Load → Store, Store → Store
3. 重新排序单元必须确保加载操作能立即看到由自身存储操作引起的更新。

原子指令

XC 和 TSO 之间一个重要的区别在于它们如何使用原子 RMW 来实现同步。在 TSO 中，原子 RMW 用于尝试获取锁，而存储操作用于释放锁。在 XC 中，情况更为复杂。对于锁获取，XC 默认不限制 RMW 与临界区中的操作的重排序。为了避免这种情况，锁获取必须后跟一个 FENCE。类似地，锁释放默认也不限制其与临界区中该操作之前的操作的重排序。为了避免这种情况，锁释放必须前导一个 FENCE。

原子指令：保证单个操作不可中断（atomic）

fence：保证多个操作之间的顺序不被乱序执行（memory ordering）

二者配合：实现多核同步，例如锁 acquire/release

无数据竞争程序的数据一致性 TODO

RC（RELEASE CONSISTENCY）

RC 提供类似于 FENCE 的 ACQUIRE 和 RELEASE 操作，但它们只在一个方向上而不是像 FENCE 那样在两个方向上对内存访问进行排序。更一般地说，RC 只需要：

• ACQUIRE → Load, Store (but not Load, Store → ACQUIRE)
• Load, Store → RELEASE (but not RELEASE → Load, Store) and

SC ordering of ACQUIREs and RELEASEs:

• ACQUIRE → ACQUIRE
• ACQUIRE → RELEASE
• RELEASE → ACQUIRE, and
• RELEASE → RELEASE

因果关系和写原子性 TODO

RVWMO

RVWMO，可以理解为 Release Consistency (RC) 和 XC 的混合。类似于 XC，RVWMO 是基于全局内存顺序（所有内存操作的总顺序）定义的，并且有多种 FENCE 指令的变体。类似于 RC，加载和存储操作可以携带注释：加载指令可以携带 ACQUIRE 注释，存储指令可以携带 RELEASE 注释，而 RMW 指令可以被标记为 RELEASE、ACQUIRE 或两者兼有。

Acquire / Release

Acquire：用于 锁获取 / 原子操作前，保证临界区操作不会提前执行

• 两种类型：
  1. ACQUIRE-RCPC：保证本核读取顺序
  2. ACQUIRE-RCSC：保证跨核共享一致性

Release：用于 锁释放 / 原子操作后，保证临界区操作完成再释放锁

• 两种类型：
  1. RELEASE-RCPC → 本核顺序保证
  2. RELEASE-RCSC → 跨核共享顺序保证

Load / Store / RMW 的约束

• Load 指令：可以带 ACQUIRE-RCPC 或 ACQUIRE-RCSC
• Store 指令：可以带 RELEASE-RCPC 或 RELEASE-RCSC
• RMW 指令（原子读-改-写）：
  • 只能带 RCSC
  • 因为 RMW 既要读取又要写入，需要跨核共享一致性保证

顺序保证（Ordering）

1. Acquire 指令前的操作 → 不会被乱序到 acquire 指令之后
2. Release 指令后的操作 → 不会被乱序到 release 指令之前
3. RMW 指令 → 保证 atomic + release/acquire 顺序，跨核可见

原子指令

RISC-V 支持两种类型的 RMWs：原子内存操作（AMO）和加载保留/存储条件（LdR/StC）。其中 AMOs 来自单条指令（例如，获取并递增），而 LdR/StCs 实际上由两条独立的指令组成：LdR 指令用于获取值并保留到核心中，StC 指令只有在保留仍然有效时才执行。这两种类型 RMWs 的原子性语义存在细微差别。

类似于 XC RMW，如果加载和存储操作在全局内存顺序中连续出现，AMO 被认为具有原子性。LdR/StC 较弱。假设 LdR 读取了存储操作 s 产生的值；只要全局内存顺序中 s 和 StC 之间没有对相同地址的存储操作，LdR/StC 就被称为具有原子性。

1. AMO（Atomic Memory Operation）

• 定义：单条原子指令完成读-改-写操作
• 示例：fetch-and-increment, amoswap, amoadd
• 原子性：
  • 严格 atomic：load 与 store 在全局内存顺序中连续出现
  • 类似 XC RMW 的原子语义

1. LdR/StC（Load-Reserved / Store-Conditional）

• 定义：由两条指令组合实现原子操作
  1. LdR → 读取值，同时在 core 内部保留该地址的 reservation
  2. StC → 仅当 reservation 仍然有效时才写入，保证原子性
• 原子性语义：
  • 比 AMO 弱
  • 条件：
    • 假设 LdR 读取了由 store s 写入的值
    • 只要在 s 与 StC 之间 没有其他 store 写入同一地址，LdR/StC 才算原子
  • 可能失败（StC 失败 → reservation 被破坏）

总结

屏障指令保证单个core内指定某些load/store的顺序不被重排序，原子指令用来实现core间同步机制，SC相当于在每一条指令前后都插入屏障指令，TSO则是在Store→Load如果不想重排序则需要插入屏障指令，RVWMO需要在不想重排序的位置插入屏障指令，所有Memory Model都需要实现原子指令

Coherence Protocols

不变量：

• 单写多读（SWMR）不变量。对于任何内存位置 A，在任何给定（逻辑）时间，只有一个核心可以写入 A（也可以读取它），或者有一些核心只能读取 A。
• 数据值不变量。一个内存位置在一个纪元开始时的值与它在最后一个读写纪元结束时的值相同。

为了实现这些不变式，我们为每个存储结构——每个缓存和 LLC/内存——关联一个有限状态机，称为一致性控制器。这些一致性控制器的集合构成一个分布式系统，其中控制器之间交换消息以确保对于每个块，SWMR 和数据值不变式始终得到维护。这些有限状态机之间的交互由一致性协议指定。

缓存控制器：

缓存控制器必须响应两个来源的请求。在“核心侧”，缓存控制器与处理器核心接口。控制器接受来自核心的加载和存储操作，并将加载值返回给核心。当发生缓存未命中时，控制器会通过发出一致性请求（例如，请求只读权限）来启动一致性事务，该请求针对包含核心访问位置的数据块。此一致性请求通过互连网络发送到一个或多个一致性控制器。事务由一个请求以及为满足该请求而交换的其他消息组成（例如，从另一个一致性控制器发送给请求者的数据响应消息）。事务的类型以及作为每个事务一部分发送的消息取决于具体的一致性协议。

在缓存控制器的“网络侧”，缓存控制器通过互连网络与系统的其余部分接口。控制器接收需要处理的缓存一致性请求和缓存一致性响应。与核心侧类似，对传入的缓存一致性消息的处理取决于具体的缓存一致性协议。

内存控制器：

内存控制器与缓存控制器类似，但它通常只有网络侧。因此，它不会发出缓存一致性请求（代表加载或存储）或接收缓存一致性响应。其他代理，如 I/O 设备，可能根据其具体需求表现得像缓存控制器、内存控制器或两者兼具。

一致性协议不同体现在：

状态

事务

事件

转换集

一个协同步序的设计者必须为系统中每种类型的协同步序控制器选择状态、事务、事件和转换。

稳定状态的选择在很大程度上独立于协同步序的其他部分。例如，存在两种不同的协同步序类别，称为监听和目录，架构师可以使用相同的稳定状态集设计监听协议或目录协议。

同样，事务的选择也很大程度上独立于特定协议。

然而，与稳定状态和事务的选择不同，事件、转换和特定瞬态状态高度依赖于协同步序。

状态

我们希望将以下四个特性编码到缓存块的状态中：有效性、脏污性、独占性和所有权[10]。后两个特性是具有多个参与者系统的独特特性。

• 有效性：一个有效的块具有该块最新的值。该块可以被读取，但只有当它是独占的时才能被写入。
• 污染性：在一个单核处理器中，如果一个缓存块的值是最新的值，且这个值与 LLC/内存中的值不同，那么这个缓存块就是“脏”的。缓存控制器负责最终将这个新值更新到 LLC/内存中。“干净”一词通常用来表示“脏”的反义词。
• 独占性：如果一个缓存块是系统中该块的唯一私有缓存副本（即，该块除了可能在共享 LLC 中之外，其他地方都没有缓存），则该缓存块是独占的。
• 所有权：如果一个缓存控制器（或内存控制器）对该块负责响应该块的保持一致性请求，那么它是该块的所有者。在大多数协议中，任何给定块在任何时候都只有一个所有者。一个所有者拥有的块不能在没有将块的所有权交给另一个保持一致性控制器的情况下，为了给另一个块腾出空间而从缓存中移除——这可能是由于容量或冲突缺失。在某些协议中，非所有者块可以无声地（即，不发送任何消息）被移除。

MSI协议

• M(修改): 块有效、独占、拥有且可能已修改。该块可读或写。缓存拥有该块的唯一有效副本，缓存必须响应对该块的请求，而 LLC/内存中的块副本可能已过时。
• S共享：该块有效但非独占，非脏，非所属。缓存有该块的只读副本。其他缓存可能有该块的合法只读副本。
• I(nvalid)：该块无效。缓存可能不包含该块，或者包含一个可能过时的副本，它可能无法读取或写入。在本指南中，我们不对这两种情况做区分，尽管有时前一种情况可能表示为“不存在”状态。

MOESI协议

• O(拥有)：该块有效，被拥有，可能已修改，但不是独占的。缓存有该块的只读副本，必须响应对该块的请求。其他缓存可能有该块的只读副本，但它们不是拥有者。LLC/内存中的该块副本可能已过时。
• E(独占)：该块有效，独占且干净。缓存有该块的只读副本。没有其他缓存有该块的副本，LLC/内存中的该块副本是最新的。在本指南中，当块处于独占状态时，我们将其视为拥有者，尽管有些协议中独占状态不被视为拥有状态。当我们后面章节中介绍 MESI 监听和目录协议时，我们将讨论将独占块视为拥有者或不拥有者的问题。

在从一个稳定状态过渡到另一个稳定状态的过程中，可能存在瞬态状态。在第 6.3 节中，我们遇到了瞬态状态 IV（在 I 中，过渡到 V，等待 DataResp）。在更复杂的协议中，我们可能会遇到数十个瞬态状态。我们使用 XY 的符号来表示这些状态，表示块正在从稳定状态 X 过渡到稳定状态 Y，并且直到发生类型为 Z 的事件，过渡才会完成。例如，在后续章节中的一个协议中，我们使用 IM 来表示一个块之前处于 I 状态，一旦收到该块的 D（数据）消息，它将变为 M 状态。

我们迄今为止所讨论的状态——无论是稳定的还是瞬时的——都涉及存储在缓存中的块。LLC 和内存中的块也有与之相关的状态，命名 LLC 和内存中块状态的方法有两种。

• 以缓存为中心：在这种我们认为是最常见的做法中，LLC 和内存中一个块的状态是该块在缓存中状态的聚合。

  例如，如果一个块在 I 中的所有缓存中，那么这个块的 LLC/内存状态是 I。如果一个块在 S 中的一个或多个缓存中，那么 LLC/内存状态是 S。如果一个块在 M 的单个缓存中，那么 LLC/内存状态是 M。

• 以内存为中心：在这种方法中，LLC/内存中一个块的状态对应于内存控制器对此块权限（而不是缓存权限）。

  例如，如果一个块在 I 中的所有缓存中，那么此块在 LLC/内存中的状态是 O（而不是像缓存为中心方法中的 I），因为 LLC/内存表现得像一个块的所有者。如果一个块在 S 中的一个或多个缓存中，那么 LLC/内存的状态也是 O，原因相同。然而，如果一个块在 M 或 O 的单个缓存中，那么 LLC/内存的状态是 I，因为 LLC/内存有一个无效的块副本。

系统实现必须维护与缓存、LLC 和内存中块相关的状态。对于缓存和 LLC，这通常需要通过最多扩展每个块的缓存状态几位来实现，因为稳定状态的数量通常很少（例如，对于 MOESI 协议，5 个状态需要每个块 3 位）。一致性协议可能有更多瞬态状态，但只需要维护那些有挂起一致性事务的块的状态。实现通常通过向处理缺失状态寄存器（MSHRs）或用于跟踪这些挂起事务的类似结构中添加额外的位来维护这些瞬态状态[4]。

对于内存，可能看起来更大的总容量会带来重大挑战。然而，许多当前的多核系统维护一个包含式 LLC，这意味着 LLC 维护系统任何地方缓存的每个块的副本（即使是“独占”块）。在包含式 LLC 中，内存不需要显式表示一致性状态。如果一个块位于 LLC 中，其在内存中的状态与在 LLC 中的状态相同。如果一个块不在 LLC 中，其在内存中的状态隐式为无效，因为从包含式 LLC 的缺席意味着该块不在任何缓存中。

事务

常见事务

一些协议不需要一致性事务来驱逐共享块和/或独占块（即，PutS and/or PutE).

尽管大多数协议使用类似的事务集，但它们在一致性控制器如何交互以执行事务方面差异很大。正如我们将在下一节中看到的那样，在某些协议（例如，侦听协议）中，缓存控制器通过向系统中的所有一致性控制器广播 GetS 请求来启动 GetS 事务，并且当前拥有该块的控制器会向请求者发送包含所需数据的消息作为响应。相反，在其他协议（例如，目录协议）中，缓存控制器通过向目录发起请求来启动事务。

缓存控制器可以选择忽略来自核心的预取请求。

通过向一个特定的、预先定义的缓存一致性控制器发送单播 GetS 消息来发起 GetS 事务，该控制器可以直接响应或转发请求到另一个将响应请求者的缓存一致性控制器。

Snooping vs. Directory

• 侦听协议：缓存控制器通过向所有其他一致性控制器广播请求消息来启动对数据块的请求。一致性控制器集体“做正确的事”，例如，如果它们是响应另一个核心请求发送数据的所有者。侦听协议依赖于互连网络以一致顺序向所有核心传递广播消息。大多数侦听协议假设请求以总顺序到达，例如通过共享总线，但更高级的互连网络和放宽的顺序是可能的。
• 目录协议：缓存控制器通过向该块所属的内存控制器单播请求来启动对一个块的请求。内存控制器维护一个目录，其中包含 LLC/内存中每个块的状态信息，例如当前所有者的身份或当前共享者的身份。当一个块的请求到达其所属的内存控制器时，内存控制器会查找该块的目录状态。例如，如果请求是 GetS 请求，内存控制器会查找目录状态以确定所有者。如果 LLC/内存是所有者，内存控制器通过向请求者发送数据响应来完成事务。如果缓存控制器是所有者，内存控制器将请求转发给所有者缓存；当所有者缓存接收到转发的请求时，它通过向请求者发送数据响应来完成事务。

监听与目录的选择涉及权衡。监听协议在逻辑上简单，但它们无法扩展到大量核心，因为广播无法扩展。目录协议是可扩展的，因为它们采用单播，但许多事务需要更多时间，因为当主存不是所有者时，需要发送额外的消息。此外，协议的选择会影响互连网络（例如，经典监听协议要求请求消息具有总顺序）。

Invalidate vs. Update

在一致性协议中，另一个主要的设计决策是在核心写入一个块时决定要做什么。这个决策与协议是监听还是目录无关。有两种选择

• 作废协议：当一个核心想要写入一个块时，它会启动一个一致性事务来使所有其他缓存中的副本失效。一旦副本被作废，请求者就可以写入块，而不会有可能其他核心读取块旧值。如果另一个核心在它的副本被作废后想要读取该块，它必须启动一个新的完整性事务来获取块，并将从写入它的核心那里获得一个副本，从而保持一致性。
• 更新协议：当一个核心想要写入一个块时，它会启动一个一致性事务来更新所有其他缓存中的副本，以反映它写入块的新值。

再次强调，在做出这个决定时，涉及到权衡。更新协议减少了核心读取新写入块时的延迟，因为核心不需要启动并等待 GetS 事务完成。然而，更新协议通常消耗比无效化协议有更多的带宽，因为更新消息比无效化消息大（一个地址和一个新值，而不是仅仅一个地址）。此外，更新协议极大地复杂化了许多内存一致性模型的实现。例如，在多个缓存必须对多个块的多个副本应用多个更新时，保持写原子性（第 5.5 节）变得更加困难。由于更新协议的复杂性，它们很少被实现；在本指南中，我们重点关注更为常见的无效化协议。

Snooping Coherence Protocols

原子请求 原子事务

窥探协议基于一个想法：所有一致性控制器以相同的顺序观察（窥探）一致性请求，并集体“做正确的事”以保持一致性。通过要求给定块的请求按顺序到达，窥探系统使分布式一致性控制器能够正确更新代表缓存块状态的有限状态机。

传统的窥探协议将请求广播到所有一致性控制器，包括发起请求的控制器。一致性请求通常在有序广播网络上传输，如总线。有序广播确保每个一致性控制器以相同的顺序观察到相同的一致性请求系列，即存在一致性请求的完全顺序。由于完全顺序包含所有按块顺序，这个完全顺序保证了所有一致性控制器可以正确更新缓存块的状态。

总线促进了所有一致性控制器所监视的一致性请求的完全顺序。与上一章的例子一样，这个系统模型具有原子性属性，简化了一致性协议。具体来说，这个系统实现了两个我们定义为原子请求和原子事务的原子性属性。原子请求属性指出，一致性请求是在发出它的同一周期内排序的。这个属性消除了由于另一个核心的一致性请求而导致块状态在请求发出和排序之间发生变化的可能性。

原子事务属性表明一致性事务是原子的，即对同一块的后续请求不能在第一个事务完成之前出现在总线上（即，直到响应出现在总线上）。因为一致性涉及对单个块的运算，所以系统是否允许对其他块的后续请求不会影响该协议。

非原子请求 原子事务

基本侦听系统模型，我们在本章的其余部分大部分使用该模型，与简单侦听系统模型不同，它允许非原子请求。非原子请求源于多种实现优化，但最常见的是在缓存控制器和总线之间插入一个消息队列（甚至是一个单独的缓冲区）。通过将请求的发出时间与请求的排序时间分开，协议必须解决简单侦听系统中所不存在的一个漏洞窗口。基本侦听系统模型保留了原子事务属性，我们直到第 7.5 节才放宽这一属性。

我们将在表 7.8 和 7.9 中详细列出协议规范，包括所有瞬时状态。与第 7.2.2 节中简单侦听系统的协议相比，最显著的不同是瞬时状态的数量要多得多。放宽原子请求属性引入了许多情况，在这些情况下，缓存控制器在发出其一致性请求和在其总线上观察自己的一致性请求之间，会观察到另一个控制器在总线上发出的请求。

以 I 到 S 的转换为例，缓存控制器发出 GetS 请求，并将块的状态从 I 更改为 IS。在总线上观察到请求缓存控制器自身的 GetS 并进行序列化之前，块的状态实际上为 I。也就是说，请求者的块被视为处于 I 状态；无法执行加载和存储操作，并且必须忽略来自其他节点的保持一致性请求。一旦请求者观察到自己的 GetS，请求将被排序，块逻辑上处于 S 状态，但由于数据尚未到达，无法执行加载操作。缓存控制器将块的状态更改为 IS，并等待来自前拥有者的数据响应。由于原子事务属性，数据消息是下一个保持一致性消息（针对同一块）。一旦数据响应到达，事务完成，请求者将块的状态更改为稳定的 S 状态并执行加载操作。I 到 M 的转换过程与 I 到 S 的转换过程类似。

MESI

MOSI

非原子总线

基线 MSI 协议，以及 MESI 和 MOSI 变体，都依赖于原子事务假设。这种原子性极大地简化了协议的设计，但牺牲了性能。

实现原子事务最简单的方法是使用带有原子总线协议的共享总线；也就是说，所有总线事务都由一个不可分割的请求-响应对组成。拥有原子总线相当于拥有未流水线的处理器核心；无法重叠并行进行的活动。图 7.8 说明了原子总线的操作。由于一致性事务会占用总线直到响应完成，原子总线可以轻易地实现原子事务。然而，总线的吞吐量受请求和响应（包括请求和响应之间的任何等待周期，未显示）的延迟总和所限制。考虑到响应可能由片外内存提供，这种延迟瓶颈会限制总线性能。

图 7.9 展示了流水线非原子总线的操作。关键优势是不必等待响应就可以在总线上串行化后续请求，因此总线可以使用相同的一组共享线缆实现更高的带宽。然而，实现原子事务变得更为困难（但并非不可能）。原子事务属性限制了并发事务只能在同一块中，而不能在不同块中。SGI 挑战通过使用快速表查找来检查是否已有针对同一块的事务挂起，从而在流水线总线上强制执行原子事务。

对于非原子总线来说，一个主要的设计问题是它是否是流水线还是分割事务。如图 7.9 所示，流水线总线提供与请求相同的顺序的响应。

分事务总线相对于流水线总线的优势在于，低延迟响应无需等待先前请求的长延迟响应。例如，如果请求 1 是针对内存拥有的且不在 LLC 中的块，而请求 2 是针对片上缓存的块，那么像流水线总线那样强制响应 2 等待响应 1，将导致性能损失。

分事务总线提出的一个问题是匹配响应与请求。在原子总线上，一个响应对应于最近的请求是显而易见的。在流水线总线上，请求者必须跟踪未决请求的数量，以确定哪条消息是它请求的响应。在分事务总线上，响应必须携带请求或请求者的标识。

非原子系统模型

我们假设一个类似于图 7.11 所示的系统。请求总线与响应总线分开，独立运行。每个一致性控制器都与两个总线相连，但内存控制器没有连接来发起请求。我们绘制了 FIFO 队列以缓冲传入和传出的消息，因为在一致性协议中考虑它们很重要。值得注意的是，如果一致性控制器在处理请求总线上的传入请求时停滞，那么它后面的所有请求都将受到影响。

（在请求停滞之后序列化）将不会在该一致性控制器处理当前停滞的请求之前被处理。这些队列以严格的先进先出（FIFO）顺序处理，无论消息类型或地址。

总线互连网络优化

我们强调了嗅探系统提供广播一致性请求总顺序的必要性。表 7.2 中的示例展示了缺乏一致性请求总顺序如何导致不一致。然而，对一致性响应进行排序或广播并没有这样的需求。因此，一致性响应可以在一个不支持广播或排序的单独网络上传输。这类网络包括交叉开关、网格、环、蝴蝶等。

使用单独的非总线网络进行一致性响应有几个优点。

• 可行性：实现高速共享总线较为困难，尤其是对于总线上有多个控制器的系统。其他拓扑可以使用点对点连接。
• 吞吐量：总线一次只能提供一种响应。其他拓扑可以同时进行多个响应。
• 延迟：使用总线进行一致性响应需要每个响应都承担仲裁总线的延迟。其他拓扑可以允许立即发送响应而不需要仲裁。

侦听系统要求存在一个广播一致性请求的全序。对于一致性请求，共享总线是最直接实现这种广播全序的方法，但这并非唯一途径。有两种方法可以在没有物理总线的情况下实现与总线（即逻辑总线）相同的完全有序广播属性。

• 其他具有物理总序的拓扑：共享总线是实现广播总序的最明显拓扑，但还存在其他拓扑。一个值得注意的例子是树形拓扑，其中一致性控制器位于树的叶子上。如果所有一致性请求都单播到树的根，然后向下广播到树中，那么每个一致性控制器都会观察到相同的一致性广播总序。在这个拓扑中，序列化点是树的根。Sun Microsystems 在其 Starfire 多处理器[3]中使用了树形拓扑，我们将在第 7.7 节中详细讨论。
• 逻辑全序：即使没有提供这种顺序的网络拓扑，也可以获得广播的总序。关键在于按逻辑时间对请求进行排序。Martin 等人[6]设计了一种侦听协议，称为时间戳侦听，它可以在任何网络拓扑上运行。为了发出一致性请求，缓存控制器将其广播到每个一致性控制器，并在广播消息上标记应该排序的逻辑时间。该协议必须确保（a）每个广播都有一个独特的逻辑时间，（b）一致性控制器按逻辑时间顺序处理请求（即使它们在物理时间上以不同的顺序到达），以及（c）在逻辑时间 T 之后，不能有请求到达控制器。

Directory Coherence Protocols

传统的嗅探系统在完全有序的互连网络上广播所有请求，所有请求都由所有一致性控制器进行嗅探。相比之下，目录协议使用一种间接级别来避免有序广播网络以及每个缓存控制器处理每个请求。

目录协议的关键创新是建立一个目录，该目录维护每个块的相干状态的全局视图。目录跟踪哪些缓存持有每个块以及它们的状态。想要发出相干请求（例如，一个 GetS 请求）的缓存控制器直接将其发送到目录（即单播消息），然后目录查找块的状态以确定下一步采取什么行动。例如，目录状态可能表明请求的块由 C2 核心的缓存拥有，因此请求应该转发到 C2（例如，使用新的 Fwd-GetS 请求）以获取块的副本。当 C2 的缓存控制器接收到这个转发的请求时，它向请求的缓存控制器单播一个响应。

比较目录协议和侦听协议的基本操作很有启发。在目录协议中，目录维护每个块的状态，缓存控制器将所有请求发送到目录。目录要么响应请求，要么将请求转发给一个或多个其他一致性控制器，然后由这些控制器进行响应。一致性事务通常包含两个步骤（一个单播请求，然后是单播响应）或三个步骤（一个单播请求、K 个转发请求和 K 个响应，其中 K 是共享者的数量）。有些协议甚至有第四个步骤，这是因为响应是通过目录间接进行的，或者是因为请求者在事务完成时通知目录。相比之下，侦听协议会将块的状态分布到所有一致性控制器上。

由于这种分布式状态没有集中汇总，一致性请求必须广播到所有一致性控制器。因此，侦听一致性事务始终包含两个步骤（一个广播请求，然后是单播响应）。

因为不存在这个分布式状态的中央摘要，一致性请求必须广播到所有一致性控制器。因此，侦听一致性事务始终涉及两个步骤（先是一个广播请求，然后是一个单播响应）。

与窃听协议一样，目录协议需要定义一致性事务何时以及如何与其他事务排序。在大多数目录协议中，一致性事务在目录中进行排序。多个一致性控制器可能同时向目录发送一致性请求，事务的顺序由请求在目录中序列化的顺序决定。如果两个请求同时到达目录，互联网络实际上会选择目录先处理哪个请求。第二个到达的请求的命运取决于目录协议和竞争请求的类型。第二个请求可能（a）在第一个请求之后立即处理，（b）在目录中等待第一个请求完成，或者（c）被否定确认（NACK）。在后一种情况下，目录向请求者发送否定确认消息（NACK），请求者必须重新发出其请求。在本章中，我们不考虑使用 NACK 的协议，但我们在第 9.3.2 节讨论了 NACK 的可能用途以及它们如何导致活锁问题。

使用目录作为排序点代表了目录协议和监听协议之间的另一个关键区别。传统的监听协议通过在有序广播网络上序列化所有事务来创建一个总顺序。监听的总顺序不仅确保每个块的请求按块顺序处理，而且有助于实现内存一致性模型。回想一下，传统的监听协议使用完全有序的广播来序列化所有请求；因此，当请求者观察到自己的相干请求时，这作为其相干纪元可能开始的通知。特别是，当监听控制器看到自己的 GetM 请求时，它可以推断其他缓存将使它们的 S 块无效。我们在表 7.4 中证明了这种序列化通知足以支持强 SC 和 TSO 内存一致性模型。

相比之下，目录协议在目录中按顺序排列事务，以确保冲突请求按块顺序由所有节点处理。然而，由于缺乏全局顺序，目录协议中的请求者需要另一种策略来确定其请求何时被序列化，从而确定其一致性纪元何时可以安全开始。因为（大多数）目录协议不使用全局有序广播，所以没有全局序列化的概念。相反，必须针对（可能）拥有该块副本的所有缓存对请求进行单独序列化。需要显式消息来通知请求者其请求已被每个相关缓存序列化。具体而言，对于 GetM 请求，每个拥有共享 (S) 副本的缓存控制器在序列化失效消息后都必须发送显式确认 (Ack) 消息。

这种目录和监听协议之间的比较突出了它们之间的基本权衡。目录协议通过牺牲一定程度的间接性（即，某些事务需要三个步骤而不是两个步骤）来实现更大的可扩展性（即，因为它需要的带宽更少）。这种额外的间接性增加了某些一致性事务的延迟。