Lecture 14: Cache Coherence（缓存一致性）（日期：2025-11-11, Tuesday）
Lecture 14: Cache Coherence（缓存一致性）（日期：2025-11-11, Tuesday）
概述：本讲讨论共享内存多处理器上的缓存一致性问题（cache coherence problem）：现代处理器为了性能在各自的私有缓存中复制内存内容，导致不同处理器可能对同一内存位置观察到不同值。本讲先给出”coherence”的严格定义与两条不变量（SWMR、Data-Value），然后重点讲解基于失效（invalidation）的写回一致性协议 MSI 及其改进版 MESI（状态转换图、总线事务 BusRd/BusRdX/BusWB、总线嗅探 snooping），再简要介绍可扩展的目录式一致性（directory-based coherence），最后从程序员视角讨论伪共享（false sharing）等由一致性协议引起的”伪通信”开销。
注意：本讲与 Assignment 2（多核 CPU 上的任务图调度）直接相关——你在作业中使用的共享变量、互斥锁与屏障背后的正确性保证，正是本讲的一致性协议提供的；理解 coherence 也能帮你解释作业中”看似无关的线程互相拖慢”这类性能现象（通常是伪共享）。
一、核心概念与定义
1. Cache Coherence Problem（缓存一致性问题）
- 定义：现代处理器把内存内容复制到本地缓存中以获得性能。问题在于：不同处理器的缓存可能持有同一内存位置的不同值，使得”读 X 应返回最近写入 X 的值”这一直观预期被破坏。
- 现实类比：同一份合同原件（内存）被复印成多份放在不同办公室（各核缓存）。A 办公室在自己的复印件上改了数字（store），B 办公室看自己的旧复印件（load），两边看到的”合同”不一致。
- 图示（写回缓存下的乱象，来自 slide 11-12）：
P1 $ P2 $ P3 $ P4 $ mem[X] Action 0 0 0 0 0 初始 foo=0 1 0 0 0 0 P1 store X 1 0 0 0 2 P1 load Y（迫使 X 从 P1 缓存被换出） 0 1 0 0 0 P3 load X → miss，从内存拿到旧值 0！ 0 1 0 0 2 P3 store X … （各处理器看到不同值 = 不一致）
2. Coherence（一致性）的严格定义
- 定义（slide 16）：一个内存系统是 coherent 的，当且仅当：对每个内存位置，所有处理器对该位置的全部操作存在一个假设的串行顺序（hypothetical serial order），且该顺序与执行结果一致，并且满足：
- 任一处理器发出的操作，在该顺序中保持其程序内发出顺序（program order）；
- 每次读返回的值 = 该串行顺序中最后一次写到该位置的值。
- 现实类比：多位老师批改同一份作业（同一地址）时，必须约定一个”批改先后顺序”，且每位老师看到的批改结果符合这个顺序；顺序由”谁先交”（程序序）决定，而不是”谁手快”（时间）决定。
- 关键点：coherence 只约束同一个地址上的操作顺序。
3. SWMR Invariant（单写多读不变量）
- 定义（slide 17）：对任意地址 x，在任意时间段（epoch）内：
- Read-Write epoch：只有一个处理器可以写 x（同时也可以读）；
- Read-Only epoch：可以有任意多个处理器只读 x。
- 现实类比：接力棒（单写权）只有一个人握着；其余人只能围观（读），等接力棒传到自己手上才能写。
- 图示：
地址 x 的时间线： Read-Write Read-Only Read-Write Read-Only （只有 P0） （P0,P1,P2） （只有 P1） （P0,P1） |─────────────|─────────────|─────────────|─────────────|→ time
4. Data-Value Invariant（数据值不变量 / 写串行化）
- 定义（slide 17）：一个 epoch 开始时地址 x 的值，等于其上一个 Read-Write epoch 结束时的值。换句话说，写必须被”串行化”——每次写的结果成为后续所有读看到的值。
- 现实类比：黑板上的值每被擦掉重写一次（写 epoch），所有学生下一节课看到的都是最新值；不允许”某个学生还看到上一版”。
5. Write-Through vs Write-Back Cache（写直达 vs 写回缓存）
- 定义：
- Write-through：每次写都穿透到内存，内存始终是最新值；实现一致性简单，但每个写操作都占用内存带宽，带宽需求极高（slide 23）。
- Write-back：写只改缓存行并置 dirty bit，行被换出时才写回内存；吸收了大量写流量，但dirty 状态现在意味着”独占所有权”，需要更复杂的一致性协议。
- 现实类比：写-through 像”每写一个字立刻传真给总部存档”（安全但费钱费线）；写-back 像”先在本地草稿本上改，定稿后才把整页寄回总部”（省事，但总部可能不知道本地改了）。
- 缓存行结构（slide 6/27）：
[ Tag \| Line state \| Dirty bit \| Data (现代 Intel 为 64 字节) ]。
6. Snooping（总线嗅探）
- 定义（slide 21）：基于广播的一致性方案。所有与一致性相关的活动都广播到系统中所有处理器（更准确地说，广播到各处理器的缓存控制器）；每个缓存控制器”嗅探”（snoop）总线上的内存操作，并按一致性协议作出响应。
- 现实类比：公司群里喊话——任何改动都在大群里@所有人，每个人看到消息后检查自己手上有没有相关文件并处理。
- 要点：缓存控制器现在要响应两个方向的事件：(1) 本地 CPU 的 LD/ST 请求；(2) 芯片互连上广播的一致性活动。
7. MSI 协议（Invalidation-Based Write-Back Protocol）
- 定义（slide 28-30）：基于失效的写回一致性协议。每个缓存行有三种状态：
- I（Invalid）：本缓存无有效副本；
- S（Shared）：行在一个或多个缓存中有效，内存副本是最新的；
- M（Modified）：行只在恰好一个缓存中有效（即 dirty / exclusive），该缓存必须负责在别人读时提供数据。
- 两种处理器操作：PrRd（处理器读）、PrWr（处理器写）；三种总线事务：BusRd（读一份副本，无意修改）、BusRdX（取独占副本，打算修改）、BusWB（把 dirty 行写回内存）。
- 现实类比：图书馆借书规则——M 状态 = 你借了唯一一本并在上面批注（别人要看你必须把批注版给他）；S 状态 = 多人都借了同一本书且内容与馆藏一致；I 状态 = 你没借这本书。
- 状态转换图（slide 29）：
PrRd / -- ┌───────────┐ ▼ │ ┌───┐ PrWr / BusRdX ┌───┐ │ M │◄─────────────────│ S │ └───┘ └───┘ │ ▲ PrRd / -- │ ▲ BusRdX/│ │ │ │ PrWr / BusRdX BusWB │ │ PrWr / BusRdX │ │ PrRd / BusRd ▼ │ ▼ │ ┌─────────┐ BusRd / -- ┌─────────┐ │ I │◄──────────────│ (同 I) │ └─────────┘ └─────────┘ （图例：A / B 表示"观察到动作 A 时，采取动作 B"；实线 = 处理器发起，虚线 = 总线发起）
8. MESI 协议（Exclusive Clean 状态）
- 定义（slide 34-35）：MSI 的改进——即使程序完全没有共享，MSI 也要为”读后写”付两次总线事务（I→S 的 BusRd，S→M 的 BusRdX）。MESI 增加 E（Exclusive Clean） 状态：行未修改、但只有本缓存有副本（内存副本仍有效）。于是 E→M 升级不需要任何总线事务（本地直接改）。”MESI，不是 Messi！”
- 现实类比：MSI 像”买书必须先在登记簿上登记再借（每次都要跑柜台）”；MESI 像”发现这本书只有我借了，我直接在书上批注，不用再跑柜台报备”。
- 四种状态：I / S / M / E；读请求若发现没有其他缓存断言 shared，则进入 E 而非 S。
9. False Sharing（伪共享）
- 定义（slide 43）：两个处理器写入不同的地址，但这些地址映射到同一条缓存行。缓存行在两个写处理器的缓存之间”乒乓”（ping-pong）传递，产生大量由一致性协议驱动的通信——这些通信是完全人为的（artifactual），因为程序本身在这些地址之间没有任何数据依赖（没有真实共享）。
- 现实类比：两个学生坐在同一张长桌两端各自写自己的作业（不同地址），但桌子（缓存行）只有一个，谁一低头写字，对方就得把桌面的东西收走再放回来（缓存行被整行迁移）。
- 图示：
缓存行（64 B） ┌──────────────────────────────────────────────┐ │ [P1 的 int] [P2 的 int] │ │ 地址 A 地址 B（同一条缓存行！） │ └──────────────────────────────────────────────┘ P1 写 A → 行被迁到 P1 缓存（P2 的行失效） P2 写 B → 行被迁到 P2 缓存（P1 的行失效） → 乒乓，无谓的 coherence 通信
10. Directory-Based Coherence（目录式一致性）
- 定义（slide 36-37）：嗅探方案需要广播才能得知其他缓存中行的状态，扩展性差。目录式方案把每行的状态信息集中存放在一个目录（directory）中：目录条目记录该行在所有缓存中的状态，缓存按需查目录，通过点对点（point-to-point）”按需告知”消息维护一致性，而不是广播。仍须维持 SWMR 与写串行化两条不变量。
- 现实类比：图书馆总台账（目录）记录”这本书在谁手上”；别人借书时只需问总台账，而不必向全楼喊话。
- 实例（Intel Core i7）：L3 充当集中目录（L3 是 inclusive cache，L2 里的行必在 L3 中，因此 L3 知道每行在哪些 L2 中）；一致性消息只发给包含该行的 L2，而不是广播给所有 L2（i7 互连是 ring，不是 bus）。目录规模：P=4（核数）× M（L3 行数）。
11. 3Cs Cache Miss Model（三类缺失）与 AMAT
- 定义：缺失分为 Cold（冷缺失）、Capacity（容量缺失）、Conflict（冲突缺失）。多处理器下还要额外考虑 True Sharing（真共享）/ False Sharing（伪共享） 与 Upgrade（升级） 造成的缺失（slide 44 按缓存行大小拆解各类缺失率）。平均访存时间 AMAT = Σ frequency × latency，且 AMAT_Multiprocessor > AMAT_Uniprocessor（slide 39）。
- 现实类比：AMAT 像”通勤平均时间”——既取决于坐哪趟车（访问频率），也取决于每趟车多慢（各级延迟）；多核下多了”找别人要数据”的绕路，平均通勤变长。
- 延迟表（Core i7 Xeon 5500，约值）：L1 命中 ~4 cycles；L2 命中 ~10 cycles；L3 命中（行未共享）~40 cycles；L3 命中（行在别的核共享）~65 cycles；L3 命中（行在别的核且 modified）~75 cycles；本地 DRAM ~30 ns（~120 cycles）；远端 DRAM ~100 ns（~400 cycles）。
二、代码示例与详细解说（本讲重点）
示例 1：伪共享（False Sharing）演示——相邻 int 计数器互相拖慢
代码（C++11，std::thread 版）（对应 slide 42 的 pthread 演示，改写为现代 C++）：
#include <atomic>
#include <chrono>
#include <cstring>
#include <iostream>
#include <thread>
#include <vector>
constexpr int NUM_THREADS = 8;
constexpr int MANY_ITERATIONS = 100'000'000; // 每个线程累加次数
constexpr int CACHE_LINE_SIZE = 64; // 现代 x86 缓存行大小
// 版本 1：朴素版——每个线程一个相邻的 int（伪共享！）
void worker_plain(int* counter) {
for (int i = 0; i < MANY_ITERATIONS; i++)
(*counter)++; // 写自己的计数器
}
// 版本 2：填充版——每个计数器独占一条缓存行
struct PaddedCounter {
int counter;
char padding[CACHE_LINE_SIZE - sizeof(int)];
};
void worker_padded(PaddedCounter* pc) {
for (int i = 0; i < MANY_ITERATIONS; i++)
pc->counter++;
}
template <typename Worker, typename Arg>
double run(Worker worker, Arg* array) {
std::vector<std::thread> threads;
auto t0 = std::chrono::steady_clock::now();
for (int i = 0; i < NUM_THREADS; i++)
threads.emplace_back(worker, &array[i]);
for (auto& t : threads) t.join();
auto t1 = std::chrono::steady_clock::now();
return std::chrono::duration<double>(t1 - t0).count();
}
int main() {
// 版本 1：int counter[NUM_THREADS]，相邻元素共享缓存行
int* plain = new int[NUM_THREADS]();
double t1 = run(worker_plain, plain);
// 版本 2：PaddedCounter counter[NUM_THREADS]，每个元素独占缓存行
PaddedCounter* padded = new PaddedCounter[NUM_THREADS]();
double t2 = run(worker_padded, padded);
std::cout << "plain (false sharing): " << t1 << " s\n";
std::cout << "padded (no sharing) : " << t2 << " s\n";
delete[] plain;
delete[] padded;
return 0;
}
【代码做了什么？】
- 8 个线程各自重复累加自己的计数器
counter[i]——线程之间没有任何真实的数据共享：没有锁、没有跨线程读写同一变量，程序逻辑上完全正确。 - 版本 1 把 8 个
int放在连续数组里：相邻元素（如counter[0]与counter[1]）落在同一条 64 字节缓存行内。 - 版本 2 用
struct PaddedCounter让每个计数器独占一条缓存行（int 后填充到 64 字节对齐）。 - 幻灯片上的实测（8 线程、4 核系统）：版本 1 耗时 14.2 秒，版本 2 仅 4.7 秒——快了约 3 倍，而两者的”算法”完全相同。
【并行机制解说】
- 为什么逻辑上独立却慢 3 倍？因为缓存一致性的粒度是缓存行而不是单个 int。线程 1 写
counter[0]时，缓存控制器必须先获得该行的独占权（写回协议下即 M 状态），于是广播 BusRdX，使持有同行的其他缓存（线程 2 的）将该行失效；线程 2 再写counter[1]时又要重新把行抢回来。两个线程交替写同一条行 → 缓存行在两个核之间乒乓，每一次乒乓都是一轮总线事务 + 失效传播（几十到上百 cycle 的延迟），且随线程数增加而恶化。 - 这对应本讲的 false sharing 概念：通信完全由一致性协议驱动、与程序语义无关（”No inherent communication, this is entirely artifactual communication (cache lines > 4B)”）。修复方式就是填充 padding / 对齐，让不同线程写的数据落在不同缓存行。
- 关键点：即使没有
std::atomic、没有任何同步，单靠volatile int级别的”看似独立”的写，也会因为缓存行粒度而产生性能耦合——这是 cache-coherent 架构编程中必须警惕的隐藏通信。
示例 2：MSI 协议的缓存控制器状态机（模拟器）
代码（C++，模拟 MSI 协议的缓存控制器）（对应 slide 28-30 的协议逻辑）：
#include <cstdio>
enum State { I, S, M };
enum Event { PrRd, PrWr, BusRd, BusRdX, BusWB };
// 模拟"一个缓存控制器"对事件 A 的响应：更新自身状态，并决定是否发出总线事务
// 返回值 = 该控制器需要在总线上发出的事务（0 表示无）
struct Controller {
State st = I;
int onEvent(Event e) {
int tx = 0; // 0 = 无总线事务
switch (e) {
case PrRd: // 本地处理器读
if (st == I) { st = S; tx = /*BusRd*/ 1; } // 从 I 读：发 BusRd 拿共享副本
else { /* S 或 M 命中，直接读 */ }
break;
case PrWr: // 本地处理器写
if (st == M) { /* 已独占，直接写（不通知别人） */ }
else if (st == S) { st = M; tx = /*BusRdX*/ 2; } // 升级：必须 BusRdX 让别人失效
else { st = M; tx = /*BusRdX*/ 2; } // 从 I 写：BusRdX 取独占
break;
case BusRd: // 嗅探到别人要读
if (st == M) { st = S; tx = /*BusWB*/ 3; } // 我是唯一持有者：写回内存供其读取
break; // I/S 状态无需动作
case BusRdX: // 嗅探到别人要独占写
if (st == M) { st = I; tx = /*BusWB*/ 3; } // 必须失效；若 dirty 先写回
else if (st == S) { st = I; } // 必须失效（否则不"唯一"了）
break;
case BusWB: // 嗅探到写回，无本地动作
break;
}
return tx;
}
};
int main() {
Controller c;
// 场景（对应 slide 31 的例子）：P1 读 x → P3 读 x → P3 写 x → P1 读 x
printf("PrRd -> state=%d tx=%d\n", c.st, c.onEvent(PrRd)); // S
printf("PrRd -> state=%d tx=%d\n", c.st, c.onEvent(PrRd)); // S（S 中读仍命中）
printf("PrWr -> state=%d tx=%d\n", c.st, c.onEvent(PrWr)); // M，tx=BusRdX
printf("BusRdX(from P2) -> state=%d tx=%d\n", c.st, c.onEvent(BusRdX)); // I
return 0;
}
【代码做了什么？】
- 实现一个缓存控制器的状态机逻辑：根据本地事件（PrRd/PrWr）与总线嗅探事件（BusRd/BusRdX/BusWB）更新行状态，并决定是否发出总线事务。
- 关键分支：本地写只有在 M 状态才能”静默”进行；S 或 I 状态写都必须发 BusRdX（即使行在本地缓存中有效，只要它是 S 状态，也必须广播 BusRdX 让别人失效——因为”多个缓存同时持有同一行”时，本地无法独占）。
- 嗅探到别人发 BusRdX 时，本控制器必须把行失效（M 状态还需先写回，即发 BusWB），否则别人拿不到独占权。
- 模拟了 slide 31 的场景：P1 读 x（S）→ P3 读 x（S）→ P3 写 x（P1 被 BusRdX 失效为 I，P3 进入 M）→ P1 再读 x 会 miss，数据来自持有 M 的 P3（而非内存）。
【并行机制解说】
- 并行如何实现：所有缓存控制器独立地运行同一套协议逻辑（slide 30：”all caches are carrying out this logic independently to maintain coherence”），通过总线上的广播消息”协作”维持两条不变量：
- SWMR：只有 M 状态的行可以被写，而 M 意味着”其他所有缓存都收到了失效消息”——于是任意时刻只有一个写者；
- Data-Value（写串行化）：当某缓存需要数据而另一个缓存处于 M 时，数据由 M 缓存通过 BusWB 提供（而不是内存里的旧值）；总线本身串行化了所有事务，从而给所有操作一个一致的全局顺序。
- 同步点在哪：每一次 BusRdX 都是一次”隐性同步”——它宣告”我要独占写入”，所有相关缓存必须在此之前处理完自己手上的副本（失效或写回）。
- 对应概念：MSI 协议、invalidation、snooping、SWMR/Data-Value 不变量。注意本例展示的是”单个地址”的协议行为——这正是 coherence（同地址排序）要保证的；不同地址之间的排序问题留给 Lecture 15 的 consistency。
示例 3：MSI vs MESI——”读后写”需要几次总线事务？
代码（C++，事务计数对比）（对应 slide 34 的论点：MESI 消除”无共享也要付两次事务”的低效）：
#include <cstdio>
// 统计"读取地址 X，然后写入地址 X"这一最常见模式所需的总线事务数
int main() {
// ---- MSI：读 → 进入 S；写 → 必须 BusRdX 升级 ----
// 事务 1: BusRd（I → S）
// 事务 2: BusRdX（S → M，向所有其他缓存广播失效）
int msi_transactions = 2;
printf("MSI : read-then-write needs %d bus transactions\n", msi_transactions);
// ---- MESI：读时若没有其他缓存断言 shared，进入 E（独占、干净）----
// 事务 1: BusRd（I → E，其他缓存无人持有 → 进入 E 而非 S）
// 事务 2: 无！E → M 是本地升级，不需要任何总线事务
int mesi_transactions = 1;
printf("MESI: read-then-write needs %d bus transaction\n", mesi_transactions);
// 关键前提：MESI 的 E 状态必须"确认没有别人也持有该行"。
// 总线协议用"共享信号"（shared line）实现：读事务在总线上发出时，
// 若有其他缓存持有该行，它会"断言 shared"，本缓存就进入 S 而非 E。
bool another_cache_asserts_shared = false; // 典型单线程/无共享场景
if (another_cache_asserts_shared) {
// 有其他缓存持有 → 进入 S，写时仍要 BusRdX 升级
printf("MESI: line is shared -> write needs BusRdX upgrade (like MSI)\n");
} else {
// 无其他缓存持有 → 进入 E，写是"静默升级"
printf("MESI: line is exclusive-clean -> silent E->M upgrade, 0 extra tx\n");
}
return 0;
}
【代码做了什么？】
- 对比同一场景（先读后写同一地址）在两种协议下的总线事务数。MSI 必须付两次：BusRd（I→S）+ BusRdX（S→M，广播失效）。
- MESI 引入 E 状态：读请求若没有其他缓存断言 shared，则进入 E；此时本地写只是 E→M 的静默升级，无需任何总线事务——即使程序完全没有共享，也省掉一次广播（slide 34：”This inefficiency exists even if application has no sharing at all”）。
- 代码同时说明 E 与 S 的判定机制：总线上的”共享信号”（shared line）——读事务广播时，其他持有该行的缓存会断言 shared，本缓存据此选择进入 S 还是 E。
【并行机制解说】
- 这是协议级优化的典型例子：一致性协议设计需要权衡”每次操作付多少通信成本”。MESI 的洞察是把”独占”（exclusivity）与”所有权/脏”（dirty/ownership）解耦：E 状态的行”只有我有，但内存副本仍有效”——所以它既不违反 SWMR（只有我持有，我可以独占写），又不需要像 M 那样承担”必须把最新数据写回/提供给他人”的责任。
- 对程序员的意义：即便你的程序从不共享数据（每个核只碰自己的数据），缓存一致性机制依然在后台产生通信；MESI 把”私有数据的常见访问模式”（读一次然后反复写）的通信降到最低。这提醒我们：性能不仅取决于程序逻辑，还取决于硬件协议为你的访问模式付出的通信代价。
- 对应概念：MESI、BusRd/BusRdX、E 状态、协议开销。注意 MESI 仍保留 MSI 的失效语义——只要有人真正共享（进入 S），写就仍需 BusRdX 广播失效，保证 SWMR。
示例 4：目录式一致性（Directory-Based Coherence）草图
代码（伪代码/C++ 风格）（对应 slide 36-37 的目录思想）：
// 目录条目：记录一行在哪些缓存中、以及当前所有权状态
struct DirEntry {
enum State { UNCACHED, SHARED, MODIFIED } state;
int owner; // MODIFIED 时的唯一持有者（缓存编号）
std::vector<int> sharers; // SHARED 时的读者列表
};
// 集中式目录（例如 Intel Core i7 的 L3 扮演的角色）
class Directory {
std::unordered_map<uint64_t, DirEntry> entries;
public:
// 请求者 c 想读地址 addr：只通知"需要知道"的缓存，而不是广播
void handleReadRequest(int c, uint64_t addr) {
auto& e = entries[addr];
if (e.state == MODIFIED) {
// 数据在 owner 手里：让 owner 把最新数据转发给 c（并写回内存）
sendMessage(e.owner, "forward data", addr);
e.owner = -1; // 转为共享
e.sharers = {c};
e.state = SHARED;
} else {
// 内存有最新副本：直接回数据，把 c 加入 sharers
e.sharers.push_back(c);
}
}
// 请求者 c 想写地址 addr：逐一点对点地让所有 sharers 失效（无广播）
void handleWriteRequest(int c, uint64_t addr) {
auto& e = entries[addr];
if (e.state == SHARED) {
for (int s : e.sharers)
if (s != c) sendMessage(s, "invalidate", addr); // 只通知持有者！
e.sharers.clear();
} else if (e.state == MODIFIED && e.owner != c) {
sendMessage(e.owner, "invalidate + writeback", addr);
}
e.owner = c; // 目录记住新 owner
e.state = MODIFIED;
}
};
【代码做了什么？】
- 目录为每条缓存行维护：状态（UNCACHED / SHARED / MODIFIED）、MODIFIED 时的 owner、SHARED 时的 sharers 列表。
- 读请求：若行在别的缓存处于 MODIFIED，目录让 owner 转发数据（并写回内存），再记录读者；否则直接从内存回数据。
- 写请求：目录只向 sharers 列表里的缓存发送 invalidation 消息（point-to-point），而不是广播给所有缓存；随后把 owner 记为请求者。消息只在”需要知道”的缓存间传递（”need to know” basis）。
- 对应 slide 37 的 Intel Core i7 实现：L3 是 inclusive cache（L2 中的行必在 L3），因此 L3 能当集中目录；目录维护”哪些 L2 含有该行”的列表，一致性消息只发给这些 L2（i7 互连是 ring 而非 bus）。
【并行机制解说】
- 并行如何实现：一致性串行化的”裁判”从总线换成目录——目录成为串行化点（serialization point），所有状态转换决策由目录做出，因此依然满足 SWMR 与写串行化两条不变量，但通信方式从”广播给所有人”变成”点对点通知相关者”，可扩展性大大提高（广播成本随处理器数量增长，目录只随共享关系增长）。
- 同步点：目录集中了”谁是当前 owner / 谁在共享”的信息，写请求的失效确认（invalidation acknowledgement）通过目录汇聚，形成全局一致的写顺序。
- 代价：目录本身是存储开销（条目数 = 缓存行数 × 每条目信息），且所有请求都要经过目录（多一跳延迟）——这是”可扩展性”与”单点延迟”的权衡。
- 对应概念：directory-based coherence、点对点消息、序列化点。这是对 snooping 广播方案（”scalability limited by ability to broadcast”）的直接回应。
示例 5：用 VTune / 系统工具观察一致性开销（命令示例）
代码（命令行）（对应 slide 40 “Use VTune to learn about memory system performance”）：
# 1. 用 VTune 的 memory-access 分析收集缓存与内存指标
vtune -collect memory-access -knob sampling-interval=1 -result-dir=vtune_out ./my_program
# 2. 查看关键指标：缓存缺失、带宽、以及 NUMA/远程访问
vtune -report summary -result-dir=vtune_out
# 关注指标：
# - L1/L2/L3 命中率与缺失率（对比单线程基线，评估 coherence 带来的额外缺失）
# - DRAM 带宽利用率（写回、伪共享都会抬高带宽）
# - NUMA 远程内存访问占比（NUMA 系统中一致性/访存延迟更高）
# 3. Linux perf 快速查看缓存行为
perf stat -e cache-misses,cache-references,LLC-load-misses,LLC-store-misses ./my_program
【代码做了什么？】
- 给出用硬件性能计数器观察缓存/一致性开销的标准流程：VTune 的 memory-access 分析 +
perf stat的 cache 事件。 - 关键判断依据：对比单线程基线的缓存缺失率增量——多处理器下增加的缺失往往来自一致性协议（true sharing、false sharing、upgrade），而 NUMA 系统还可能出现”本地内存也 miss”的远程访问延迟（slide 39 的 AMAT 分析）。
【并行机制解说】
- 这是”从程序员视角理解 coherence 开销”的实操：coherence 使通信时间成为并行开销的一部分——它表现为更高的缓存缺失率、更高的内存访问延迟（如 L3 命中但行在其他核：~65 cycles；行在其他核且 modified：~75 cycles；远端 DRAM：~100 ns）。AMAT = Σ frequency × latency，多核下两者都可能变差。
- 只有百分之零点几的额外缺失（”Only a fraction of a % of these can be significant!”）就可能显著影响性能，所以需要用工具量化，而不是凭感觉。
- 对应概念：communication overhead、AMAT、false sharing 的量化。如果发现缺失率异常升高，下一步通常就是检查是否伪共享（示例 1 的 padding 修复）。
三、关键要点
- 缓存一致性问题是”复制”带来的：共享地址空间这个抽象并不是由单一存储单元实现的——数据既在内存中又被复制到各处理器私有缓存中，因此”读 X 应返回最近写 X 的值”需要协议来保证；这不是互斥问题，加锁无法修复（slide 12：”Is this a mutual exclusion problem? Can you fix the problem by adding locks? NO!”）。
- coherence 有精确的定义：对每个地址存在一个与所有观察一致的串行顺序；每处理器按程序序执行；读返回串行顺序中最后一次写。实现层面由两条不变量落地：SWMR（单写多读） 与 Data-Value（写串行化）。
- 基于失效的写回协议（MSI/MESI）是核心机制：只有 M（或 E）状态的缓存能本地静默写；想写必须先通过 BusRdX 获得独占权（广播失效他人副本）；嗅探到别人要独占时自己必须失效（dirty 先写回）。MESI 的 E 状态让”无共享”场景免掉一次总线事务。
- 一致性通信是程序员要付的隐性开销：伪共享（不同地址同缓存行）会产生完全人为的乒乓通信——同一逻辑程序的性能可差 3 倍（14.2s vs 4.7s）；padding/对齐是标准修复。
- 广播不扩展，目录可扩展：snooping 的可扩展性受”能否广播给所有缓存”限制；目录式一致性（如 i7 的 L3 目录）用点对点消息把通信限制在”需要知道”的缓存之间。
四、常见陷阱与注意事项
- 以为一致性问题是锁能解决的：把共享变量”用锁保护”并不能修复缓存不一致——协议层面的一致性错误（读旧值）发生在内存系统，而不是临界区；锁只解决”多写者互斥”的语义问题（而 coherence 本就不允许并发写者在协议层面同时写）。
- 忽视伪共享：为每个线程分配”独立的”相邻变量（如
int counter[NUM_THREADS]）看似无共享，实则同缓存行乒乓。写高性能代码时，线程私有数据要 padding 到缓存行边界（或用alignas(64)），并意识到volatile/普通写都可能触发。 - 误解 dirty bit 的含义：写回缓存中 dirty 不只是”内存过期”，它意味着独占所有权（M 状态）——持有 M 行的缓存必须负责在别人读时提供数据（写回），否则别人会从内存拿到旧值。
- 忽略通信延迟的层级差异：同样一次”L3 命中”，行未共享 ~40 cycles、行在别的核共享 ~65 cycles、行在别的核且 modified ~75 cycles、远端 DRAM 数百 cycles——设计共享数据结构时应尽量让高频访问的数据独享缓存行并减少跨核写共享。
- 对缓存行大小/协议做硬编码假设：缓存行是 64B（现代 Intel）但不同架构不同（slide 44 显示缺失率随行大小显著变化，且分解为 cold/capacity/true sharing/false sharing/upgrade）；协议可能是 MSI/MESI/目录式的混合（如 i7 的 L3 目录 + L1/L2 嗅探式行为）。可移植代码应使用
std::hardware_destructive_interference_size（C++17）或对齐宏，而不是写死 64。
五、思考题（带答案）
Q1：为什么在 MSI 中，即使行已经在本地缓存且处于 S 状态，写它仍然必须发出 BusRdX 事务？ A1：因为 S 状态意味着其他缓存可能也持有该行的副本。若本地直接从 S 改为 M 而不广播失效，别的缓存仍保留旧副本，之后它们读到的将是旧值——违反 SWMR 不变量（同一时刻只能有一个写者，且写后其他缓存不得再持有有效副本）。BusRdX 的作用就是”宣告我要独占写入”，迫使所有持有者失效（若它们处于 M，还须先写回）。这正是 slide 33 强调的：”Read-exclusive transaction is required even if line is valid (but not exclusive… it’s in the S state)”。
Q2：伪共享和真共享（true sharing）有什么区别？为什么伪共享是”人为的”（artifactual）通信？ A2：真共享指多个处理器访问同一地址（比如同一把锁、同一个累加器），通信是程序语义必需的；伪共享指多个处理器访问不同地址（如 counter[0] 和 counter[1]），仅因这些地址落在同一条缓存行而被迫以整行为粒度通信——程序本身在这些地址间没有任何数据依赖，因此这种通信完全是缓存行粒度（64B）大于数据粒度（4B int）的产物。修复方法：padding/对齐使每个线程的数据独占缓存行，或重新布局数据结构。
Q3：为什么说”总线”对 MSI 协议的正确性如此重要？如果把总线换成非广播的互连（如 ring），MSI 还会正确工作吗？ A3：MSI 依赖两点总线特性：一是广播（BusRd/BusRdX 能到达所有缓存，保证”所有持有者都被通知失效”）；二是顺序性/原子性（总线在同一时刻只处理一个事务，天然为所有一致性操作提供一个全局串行顺序，从而满足 Data-Value 不变量中的写串行化）。若换成 ring 之类的非广播互连，MSI 的失效消息无法到达所有缓存、也没有天然的总序——所以 Intel Core i7 改用目录式一致性：L3 作集中目录、按需点对点通知，由目录充当新的串行化点（slide 37）。这解释了”广播不可扩展 → 目录方案”的演进逻辑。
本讲笔记基于 Stanford CS149 Fall 2025 Lecture 14 幻灯片（raw/cachecoherence.txt）撰写；性能数据（14.2s vs 4.7s、各层级延迟）均引自幻灯片原文。