计算机体系结构 · 第29课

MESI协议与缓存行所有权:Invalidation、共享读与写权限转移

2026年11月17日|第5周第1节|预计18分钟(讲解与课后测评分开)

第4周已经学过Write-back、Dirty、Store Buffer、MSHR和Cache污染。从今天开始进入第5周:缓存一致性(Coherence)、内存模型(Consistency)与NUMA。本课只专注一个问题:两个核各有L1,如何保证对同一条物理Cache Line的读写不会让其中一个核悄悄读到被淘汰的旧副本?

本课结束后需要能够:画出MESI状态迁移、手算两核Trace、解释False Sharing,并证明为什么MESI并不自动意味着SC。

一、问题从哪里来?两个L1为何可能同时缓存X(约2分钟)

设共享地址X初始为0,Core 0和Core 1都有私有L1。二者都读取X,两个L1就可能各自保存一份副本。如果随后Core 0执行X=1,Core 1不能无限期地拿自己的旧副本0当作新鲜值使用。

flowchart LR
    C0["Core 0"] --> L0["L1_0: X的副本"]
    C1["Core 1"] --> L1["L1_1: X的副本"]
    L0 <-->|"相干消息 / 数据"| COH["Snoop或Directory"]
    L1 <-->|"相干消息 / 数据"| COH
    COH <--> MEM["共享下级Cache / 内存"]

最简单的思路是Write-update:某核修改X后通知其他副本更新。但常见的写失效(Write-invalidate)机制选择另一个办法:写入者获得这条Line的独占写权限,让其他核的旧副本变为Invalid,后续其他核再读时重新获取正确版本。

为何以Cache Line为单位而不是以C语言变量为单位?硬件Cache中的相干标记和所有权通常跟随整个Line。例如64B Line里有两个独立8B计数器,写任意一个都可能需要该整行的写所有权。这是后面False Sharing的根源。

二、符号、假设与两个关键不变量(约2分钟)

本课构造两核、64B Line、Write-back、写失效、无自发替换的教学MESI机器:每个核对指定物理Line X持有一个稳定状态M/E/S/I;相干事务在表格每一行结束时已经完成,暂不画总线竞争及暂态。若要精确模拟真实微架构,还需瞬态状态、请求队列、目录/总线仲裁、确认与重试。表格中的“W完成”指写操作真正获得相干写权限并更新缓存,不等于仅仅从ROB退休。

状态 含义 本地读 本地写
M — Modified 唯一可用副本,数据已修改,较旧下层副本可能过时 Hit 可继续写
E — Exclusive 唯一可用副本,干净 Hit 本地E→M,不必向其他核失效
S — Shared 一份干净、可读的副本,其他缓存可能也持有 Hit 先获得独占所有权,其他副本失效
I — Invalid 本级没有可用副本 必须获取 必须获取写所有权

MESI的核心不是记住四个名字,而是两个不变量:

单写者/多读者(Single Writer or Multiple Readers, SWMR):如果某核持有可写的M/E权限,那么其他核不能同时持有该行的有效共享副本;若多个核同时持有有效副本,则应处于允许共享读取的状态,而没有核在无协调情况下单独写入。

最新值不丢失(Data Value / Write Serialization):一个Line可以按协议建立相干的写入顺序,后续合法获取该Line的读者必须得到与其相干顺序相符的版本,不能在另一个缓存持有更新的M数据时,直接从旧DRAM返回过时值。

这两个条件关注同一物理Line,不负责直接规定不同地址X、Y之间所有CPU操作的跨核全序。更正式的Memory Consistency还要说明允许哪些Load/Store观察。MIT 6.004教学讲义明确将MESI用来维持共享副本与写失效的关系:https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c21/c21s1/ 。

三、三类关键相干事务:BusRd、BusUpgr、BusRdX(约3分钟)

这是用于推导的教学简化命名,真实CPU可能使用Directory请求、层级Snoop或不同事务编码。

  1. BusRd:共享/读请求。 当前本级I,Core需要读取X。如果没有其他副本,常可取得E;若其他核已有有效副本,则参与者变为S。若另一核持有M,最新数据应通过相干路径提供,并在本课程的简单MESI模型中将双方转为S。
  2. BusUpgr:本地已有S,但要写。 核已有最新的干净Line,却没有独占权限,需要通知其他共享者失效。获得确认后可以从S→M;不必再次下载一整条数据。
  3. BusRdX / RFO:本地I,但要写。 需要获取正确Line内容及独占所有权,可能同时触发其他副本失效。数据未必来自DRAM,也可能来自拥有者或LLC。
flowchart TD
    I["I:无有效副本"] -->|"本核读 / BusRd"| E["E:唯一干净副本"]
    I -->|"本核读且别核持有 / BusRd"| S["S:共享干净副本"]
    I -->|"本核写 / BusRdX-RFO"| M["M:唯一修改副本"]
    E -->|"本核写 / 无需失效消息"| M
    E -->|"别核读"| S
    S -->|"本核写 / BusUpgr + 其他核Invalidate"| M
    M -->|"别核读 / 提供最新数据"| S
    S -->|"别核取得写所有权"| I
    M -->|"别核取得写所有权 / 数据与权限交接"| I

图中省略了替换导致的回写、所有远端请求路径,以及同一时刻的瞬态。特别注意:本地E→M无需新的广播失效,因为E本来就意味着没有其他有效副本;但S→M通常必须协调。

当Core 1读取Core 0持有的M副本时,Core 0可通过相干系统交付最新数据。为了满足这里S为干净共享副本的简化MESI定义,协议还要使相应下层副本保持一致;这不等于软件必须等待数据写入最底层DRAM芯片后才能读。

四、完整两核Trace:状态是如何变化的?(约2分钟)

初始物理X=0,两核对X均为I,所有事务完成后再进行下一步。

操作 Core 0状态 Core 1状态 读取结果/关键事务
初始 I I X=0
Core 0读X E I 读0;BusRd,无其他副本
Core 1读X S S 读0;BusRd;Core 0降级
Core 0写X=7 M I BusUpgr;Core 1失效
Core 1读X S S 读7;Core 0的M副本提供最新数据
Core 1写X=9 I M BusUpgr;Core 0失效

这里没有任何一步要求Core 0写7后立刻把7刷回DRAM,Core 1才有可能拿到7。硬件相干请求能找到最新版本。MIT课程对“修改者提供数据、读者降级为S”有对应Trace:https://computationstructures.org/lectures/parallel/parallel.html 。

容易犯错的判断:“Core 1在Core 0持有M时读取X,会直接命中Core 1原来的共享副本。”不成立:Core 1在Core 0写入时已经被置为I。它必须重新获取有效数据。

五、数值案例:为什么False Sharing能拖垮多核吞吐?(约2分钟)

考虑对齐的64B物理Line:

字节位置: 0            8                             63
           +------------+------------+----------------+
Line L:   | counter_A  | counter_B  | 其余字段        |
           +------------+------------+----------------+
Core 0反复写counter_A;Core 1反复写counter_B

A与B是独立8B变量,但位于同一个64B相干单元。两个核反复交替写入时,Line的M写权限会在两核之间来回转移:

Core 0持有 M
   → Core 1请求写权限:Core 0失效,Core 1获得M
   → Core 0再次请求写权限:Core 1失效,Core 0获得M
   → ...

这就叫False Sharing(伪共享):不是两个核读写同一个变量,而是修改了不同字段却竞争同一Cache Line的所有权。

数值例题:假设已经完成第一次所有权获取,之后有500次真正发生的跨核所有权转移,每次转移在关键路径额外暴露60周期,并且这些开销完全不重叠,则:

[ \Delta C=500\times60=30{,}000\text{ cycles}. ]

把两个频繁写入的独立变量分别放进不同64B Line,能显著减少这类转移。但并非免费:Padding增加数据占用,可能增大Cache和TLB工作集,也可能损害其他访问的局部性。Linux内核官方文档也将不同字段共用相干Line造成的失效与HITM作为重要性能问题:https://www.kernel.org/doc/html/latest/kernel-hacking/false-sharing.html 。

六、Snooping与Directory:如何找到要失效的副本?(约2分钟)

Snooping(侦听式):在共享的广播或有序相干互连上,各缓存检查相关事务;对于小规模系统直观,但广播成本可能随核数上升。

Directory(目录式):维护该物理Line的拥有者与共享者信息,写入者只需向已知相关持有者发失效消息(具体编码可能使用Sharer Vector、稀疏目录等)。

flowchart LR
    A["Core 0想写Line X"] --> D["Directory:记录X的共享者"]
    D --> I1["Invalidate → Core 1"]
    D --> I2["Invalidate → Core 2"]
    I1 --> ACK["等待必要ACK"]
    I2 --> ACK
    ACK --> G["Core 0获得独占写权限"]

目录不会自动保证每种访问都比广播快:目录项占空间,热点Line可能需要多个确认,NoC拥塞与寻址延迟也会影响性能。但它可以避免对完全不相关的核心无条件广播。

性能关键是“消息开销与同步等待”,而不是单纯的有效Cache副本数量。下一周的NoC专题还会更深入分析互连成本。

七、最容易混淆的一点:MESI不等于SC或TSO(约3分钟)

7.1 Coherence只解决什么?

Coherence解决同一物理位置/Line的副本协调与写入序列化。例如Core 0写X=7,Core 1后来通过协议获得X时,不能把被淘汰的旧副本当成最新值。

但它不替你规定“Store X”和另一个地址“Load Y”是否必须遵循严格的跨核全局操作顺序。这是Memory Consistency Model的问题。

7.2 为什么SC禁止经典Store Buffering的(0,0)?

初始X=Y=0:

Core 0                      Core 1
Sx: STORE X=1               Sy: STORE Y=1
Ly: r0=LOAD Y               Lx: r1=LOAD X

SC(顺序一致性)要求存在一个保留每核程序顺序的全局串行交错:

[ S_x<L_y,\qquad S_y<L_x. ]

如果两次Load都读到初始0,还要求:

[ L_y<S_y,\qquad L_x<S_x. ]

联立得到:

[ \boxed{S_x<L_y<S_y<L_x<S_x} ]

出现严格顺序环,所以SC下不可能有 ((r_0,r_1)=(0,0))。

7.3 TSO为什么允许,MESI又为什么没有失效?

在允许Store→不同地址Load放松的TSO教学模型里,两核可以先将Store放入各自Store Buffer:

Core 0:X=1仍在本核Store Buffer;之后Load Y读取旧0
Core 1:Y=1仍在本核Store Buffer;之后Load X读取旧0
再往后,两份Store逐渐排出并通过MESI取得写权限

因而 ((0,0)) 可成为合法架构结果。当这些Store最终进入相干系统时,MESI仍然按规定维护各Line的写入所有权;一致性没有被破坏。

这是第5周必须掌握的三个不同时间点:

[ \boxed{\text{Store从ROB退休} \ne\text{相干写入已全局可见} \ne\text{脏数据已回写到DRAM}.} ]

更具体地说,本核Load可以从本核较老同址Store转发新数据,即使另一个核尚未观察到该Store;别的核只通过相干Cache/内存路径读到旧值,不代表它拥有违反MESI的新旧副本。

缓存一致性的MESI稳定状态并不直接描述Store Buffer中的所有在途写。把“Store已退休”直接等同于“对应Line已经M并可供其他核观察”,会在这一步推理出错。关于Coherence/Consistency区别,可参考上述MIT教材及并行体系结构讲义。

八、边界与反例:哪些说法不能直接推广?(约1分钟)

  • M状态不意味着DRAM已经更新。 最新版本可以保存在拥有者Cache中;别核读时由相干路径取得。
  • E→M通常不需额外失效,但S→M需要协调。 不要把两个Write Hit当成同样的外部流量。
  • MESI四状态是稳定状态教学模型。 真实CPU还可能使用MOESI、MESIF、目录、暂态和非包含式LLC,不能直接把图画成产品的逐周期实现。
  • False Sharing不是数据竞争(Data Race)的同义词。 两个线程即使通过正确同步分别更新自己的独立变量,也可能遭遇Line级乒乓。
  • 一致性正确不代表没有内存排序问题。 多地址的合法观察由ISA和编程语言的内存模型共同决定,必须正确使用同步原语。

九、本课总结与下一讲(约1分钟)

需要记住的核心不变量是:

[ \boxed{\text{Single Writer / Multiple Readers}} ]

[ \boxed{\text{获得写所有权之前,竞争副本必须被适当失效}} ]

[ \boxed{\text{相干副本正确}\not\Rightarrow\text{所有核的不同地址操作都是SC}} ]

下一讲:第30课(2026年11月18日,第5周第2节)《MESI状态机与协议竞态:Transient State、Invalidate ACK与Directory压力》。 下一讲将回答为什么两个核同时升级共享Line时,不可能只画一个理想的S→M箭头就万事大吉。

十、参考资料

  • MIT 6.004,Parallel Processing与MESI教学Trace:https://computationstructures.org/lectures/parallel/parallel.html
  • MIT OpenCourseWare,MESI与共享读/Invalidate:https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c21/c21s1/
  • Linux Kernel,False Sharing:https://www.kernel.org/doc/html/latest/kernel-hacking/false-sharing.html
  • Intel Performance Skills,False Sharing优化案例:https://github.com/intel/intel-performance-skills/blob/main/skills/performance-patterns/patterns/false-sharing.md

十一、四级分级测评(100分)

首次课堂不提供标准答案、解析或参考推导。 Lv1—Lv3客观判分;Lv4根据Rubric人工/自评,网站不应伪称开放题可以全自动证明。建议作答后按Lv1—Lv4顺序提交。

Lv1|Modified副本与跨核最新值(15分,单选,预计2分钟)

物理X初始为2。Core 0已通过相干协议完成对X的写入,使其L1持有X=7的Modified(M)副本;DRAM中的X仍可能是2。随后Core 1请求读取X。哪项判断最严谨?

A. Core 1必须从DRAM读取2,因为写回尚未发生。

B. Core 0已经是M,因此Core 1可以无须相干协议,直接读取自己的过时共享副本。

C. 相干系统必须使Core 1取得最新的有效数据版本,可由Modified持有者或相应相干路径提供,不要求程序先等待最终DRAM写回。

D. 只要Core 0的一条Store从ROB退休,就说明Core 1在同一周期必然能读到7。

可选提示(不泄露答案) 把“谁持有最新副本”“DRAM是否更新”和“Store是否仅退休”分成三个问题。

Lv2|MESI两核Trace中的Invalidate次数(20分,数值,预计4分钟)

两核教学MESI:同一物理Line X初始状态为(I,I),内存X=0;每一步相干事务在下一步之前完成,无自发替换。依次执行:(1) Core0读X;(2) Core1读X;(3) Core0写X=1;(4) Core1读X;(5) Core1写X=2;(6) Core0读X;(7) Core0写X=3。问:整个Trace里使另一个核原先有效的Line变为I的所有权升级/失效事务共发生几次?填写整数,不计初始I,也不把正常M→S读降级计为Invalidation。

作答单位:次;仅填写整数。

可选提示(不泄露答案) 每次写之前检查写入者是否持有S、E或M;只有别核持有有效副本而写入者需要独占所有权时才数一次。

Lv3|MESI、不变量、False Sharing与TSO(25分,多选,预计5分钟)

针对本课的普通可缓存内存与两核MESI稳定状态模型,选择所有正确说法。

A. 本核持有某Line的E副本时,若没有其他并发事务,本核写该Line可E→M,无须向别核额外发送Invalidate。

B. 本核对某Line只持有S副本时,要写入一般需要升级写权限并使其他有效共享副本失效。

C. 另一个核持有某Line的M副本时,读取者仍可通过相干协议获取最新数据,而不一定等到该Line最终从Cache逐出到DRAM。

D. 因为MESI保证同一Line相干,所以它自动禁止TSO经典Store Buffering的(0,0)架构结果。

E. 两个线程写不同变量,但变量位于同一64B Cache Line,仍可能不断争用该Line的写所有权。

F. 只要Store从ROB退休,该Store就必然已经对所有其他核心全局可见。

可选提示(不泄露答案) 分开判断单行写所有权、脏副本转发、同Line不同字段,以及不同地址的内存排序。

Lv4|MESI状态追踪、伪共享代价与SC/TSO证明(40分,开放,预计10—12分钟)

统一假设:两个核、64B Line、Write-invalidate教学MESI,所有事务按所列顺序完整结束;无自发驱逐、无其他共享者,所有写入实际取得权限后才记为完成。请完成A—D,写清状态、公式、边界。

A|MESI Trace与所有权(12分) 物理X初始0,双方均I。依次:(1) Core0读X;(2) Core1读X;(3) Core1写X=3;(4) Core0读X;(5) Core0写X=5。逐步列出(Core0,Core1) MESI状态和读出的X值;指出何时发生Invalidate、何时要由修改者提供最新数据。说明这里“M→S”的含义。

B|False Sharing与量化代价(10分) 同一个对齐64B Line里,Core0只写偏移0处的8B计数器a,Core1只写偏移8处的8B计数器b。两核交替共完成400次写,第一笔取得写所有权的成本不计,以后每次核间写所有权交换额外暴露70周期,成本互不重叠。求所有权交换次数和额外周期;把a、b拆到各自独立的Line后,说明在无其他共享者的理想条件下上述交换会如何变化,并讨论额外空间成本。

C|内存模型与单侧屏障(10分) 初始X=Y=0。Core0执行STORE X=1; FENCE; r0=LOAD Y;Core1执行STORE Y=1; r1=LOAD X。假设FENCE在TSO中保证本核较老Store在后继Load之前达到全局可见点,且没有其他写。判断只有Core0设置FENCE时(r0,r1)=(0,0)是否可能;再判断Core1也在Store与Load之间增加同类FENCE后是否可能。分别用可见顺序或时间线证明,并解释这与MESI及本核同址Store-to-Load Forwarding的关系。

D|实验设计与边界(8分) 为比较“同Line的两个独立计数器”与“分别Cache Line对齐”的实现设计公平实验:固定任务量,给出至少四项应收集的统计(如HITM、Invalidation、缓存Miss、端到端时间、IPC、P99、空间/Cache工作集等),并解释为什么不能只凭总Miss Rate或DRAM内容判断性能与正确性。

可选提示(不泄露答案) A依次追踪持有者和读值;B不要计入第一笔初始获取;C对比只有单侧Fence与双侧Fence时能否构造无环的跨核可见顺序;D检查相干流量和端到端时间。

十二、评分规则与下一讲

四题合计15+20+25+40=100分。≥80分按既定课号继续;60—79分补一例MESI状态追踪;低于60分重点复习第24课Write-back/Store Buffer、第28课SC/TSO,再做纠错练习。补练不改变第30课的日期和编号。

建议作答格式:

Lv1:
Lv2:
Lv3:(写所有选择字母)
Lv4:
A:
B:
C:
D: