目录与缺失

一、MSI 协议回顾与问题分析

1.1 MSI 的基本框架

前文介绍的 MSI 协议是 cache 一致性的基础协议。在多处理器系统中，每个 CPU 有自己的 cache，共享同一块 memory。MSI 定义了三种 cache block 状态：

1.2 数据共享与修改的核心逻辑

在这个框架中，有几种典型的场景：

• 所有缓存都共享（shared）：多个 cache 持有同一块，数据一致，各方都可以读
• 某个缓存修改了（modified）：某个 CPU 从 memory 读进数据后做了修改，但还没写回 memory
  • 这个数据变成了”独一无二”的一份——因为它被改过了，所以叫 modified
  • 其他 cache 中的这块数据被标记为 invalid
  • 只有持有 modified 块的那个 cache 拥有最新、最可用的数据

数据 share 的时候各方都一样，各方都可以用。但一旦有人修改了，那这块数据就是独一无二的了——因为被他改过了，所以才叫 modified。

1.3 数据传递的标准流程

当一个 cache 的数据是 modified，另一个 cache 想要读这个数据时，流程是：

1. 持有 modified 块的 cache 先写回 memory（write-back / flush）
2. 请求方再从 memory 读上来

小时候看到一道奥数题——已知烧开水的方法：拿壶装水、放炉上、开火烧。问题是”壶里已经有水，怎么烧开水？”答案是把水倒掉——这样就回到了原样的问题，直接调用原来的解法。这个智慧的思路是：与其写新代码，不如把问题转化成已有代码能处理的样子。

在这个场景中：写 memory 的代码本来就有，从 memory 读的代码本来就有，不需要写新代码。将数据先 flush 到 memory，然后对方从 memory 读——两个已有的代码段组合起来就解决了问题。

1.4 伊利诺伊大学研究者的发现

伊利诺伊大学的研究人员做了一个实验——实际去观察总线上发生了多少次通信，每次通信是不是必要的。他们发现了一个问题：

通过实际测量总线事务，可以发现协议中哪些通信是必要的、哪些通信可以被优化。MESI 正是从 MSI 的冗余总线事务中抽象出新的状态。

二、MESI 协议——从 MSI 到 MESI

2.1 动机：S 到 M 的不必要总线事务

在 MSI 协议中有一个问题：当某个 cache 要从 shared 状态进入 modified 状态时（即读进并修改一个 block），按照协议需要先通知所有其他持有者，将它们的数据失效。这会产生一个总线事务（bus transaction）。

但考虑一个常见场景：实际上只有一个 cache 持有这个块（即 shared 的 count = 1）。在这种情况下：

• 该 cache 不需要通知其他 cache，因为没有其他共享者
• 广播失效会浪费一次总线事务

某个 cache 读入并修改一个 block，会产生两个总线事务：第一个是 bus read 把数据读进来进入 S 状态，第二个是把其他副本 invalid 然后进入 M 状态。但如果没有其他共享者，第二个事务并不必要。

2.2 解决方案：添加 Exclusive（E）状态

MESI 的改进方式是在 MSI 的状态集合中增加一个更精确的状态，用来区分“只有一个 cache 持有且未修改”和“多个 cache 共享”这两种情况。

思路是：当 shared 的 count = 1（只有一个 cache 持有者，而且数据没有被修改过、与 memory 一致），这个状态就不再叫 shared，而是单独起一个名字——Exclusive（独占）。

2.3 Exclusive 状态的关键特性

Exclusive 状态的核心意义：表示”当前 cache 独有该块，且该块是干净的（clean），未被修改过”。

关键特性：

• 区分了”一个人的 shared”和”多个人的 shared”
• 处于 Exclusive 状态的块做更新时，不需要广播——因为只有当前 cache 持有，没有别人需要通知
• 可以直接从 E 状态变为 M 状态，省掉了一次总线事务

Exclusive 就出现在”读进来还没写”的时候。某个 cache 读入来只要不写，就一直读，数据跟 memory 一样。但没有人跟我 share——所以不能叫 shared；也没被修改过——所以不能叫 modified。这就是 Exclusive。

2.4 E 状态与 M 状态的区别

在 Exclusive 状态下这两个数据是一致的（cache 和 memory），这一点非常重要。因为我回头要更新数据的时候，我得知道 memory 的数据能不能用。Modified 的话我就知道 memory 不能用了。Share 状态呢？Share 状态就是因为 cache 和 memory 数据一样，所以我是可以用 memory 的。

2.5 硬件实现：Wired-OR 信号

为了判断一个块是否只有当前 cache 持有，需要在总线上增加一条 shared signal 线：

• 使用 wired-OR（线或）实现——只要有一个 cache 的 shared 信号为高，总线就被拉高
• Wired-OR 不需要经过门电路延迟，直接把金属线连在一起，速度极快
• 当读取一个块时，如果 shared 信号线没有被拉高（说明没有其他 cache 持有），则该块进入 E 状态；如果被拉高（有人也有），则进入 S 状态

不需要经过门电路做逻辑，就是把线连在一起——只要有一个为 1，其他都能拉上去。这就叫 wired-OR。这是极简的实现方式，速度更快。

2.6 MESI 状态迁移图

MESI 有四个状态，每个状态之间的转换取决于两个事件源：

• Processor 的操作（来自自己的 CPU）：读（read）或写（write）
• Bus 上的操作（来自其他 CPU/设备）：bus read、bus write 等

MESI 的状态迁移可以从事件来源推导：如果多个 cache 都在读同一块，则保持 Shared；如果只有本地 processor 读且总线上没有其他读请求，则可以保持 Exclusive；如果只有本地 cache 持有最新副本并发生写操作，则进入或保持 Modified。

理解每个状态的所有权、是否脏以及是否存在其他共享者，比机械记忆状态图更重要。

三、Cache 到 Cache 数据传输与 MOESI 协议

3.1 动机：能不能直接从 cache 传数据？

在 MESI 协议中，当 P0 的数据是 modified，P1 想读这块数据时，流程是：

1. P0 先把数据 flush 到 memory（一次写）
2. P1 再从 memory read（一次读）

这就涉及两次 memory 访问，而 memory 很慢。

直觉想法：能不能让 P0 直接把数据传给 P1？cache 之间传数据快得多——在同一个芯片内部，cache 的速度远快于 memory。

3.2 cache-to-cache 传输的问题

这个想法在只有两个 CPU 时没问题（伊利诺伊大学就用的两个核）。但当 CPU 多了以后就出问题了：

• P1、P2、P3、P4 都 share 着数据
• P5 想从 cache 里拷一份——从谁的 cache 拷？
• 谁离得近？谁不太忙？
• 需要一个 selection 机制来决定由谁来提供数据

选择过程很复杂。离得近的那个现在可能特别忙，因为有任务一直在跑；不太忙的可能离得远。到底按远近来选还是按忙碌程度来选？还得设计协议和机制。

当多个 cache 共享时，有个 selection 过程。而且总线上的通信量——之前两个核还好，挂四个核时总线上已经很繁忙了。你在用他在用，平白无故要从 cache 往那边拷数据，还要握手确认，这给总线增加了很大压力。最终发现这种实现代价可能高于直接从 memory 获取数据。

3.3 时代变化带来的瓶颈

时代的一粒沙，落到他头上就把他给压垮了。伊利诺伊大学做的时候只有两个核——不是问题。等多了以后就是问题了。

总线挂四个核、八个核、十六个核，总线越来越繁忙：

• cache-to-cache 传输需要占用总线带宽
• 需要握手确认、需要 selection
• 总线成了瓶颈

3.4 MOESI 协议：添加 Owner 状态

面对”不想通过 memory 传输”和”不知道从谁那拷贝”的矛盾，一个新的思路产生了：

指定一个 owner——当数据在多个 cache 之间 share 时，指定其中一个作为”拥有者”（owner），由他来负责：

• 将数据传给其他需要的 cache（cache-to-cache）
• 最终将数据写回 memory（在数据不再需要时）

这就是 MOESI 协议中新增的 Owner (O) 状态：

Owner 状态的特征：

• 多个 cache share 同数据，但 memory 的数据是旧的（cache 和 memory 不一致）
• 在 share 的这群 cache 中，只有一个被指定为 owner
• owner 负责：给其他 cache 传递数据 + 最终写回 memory
• 当数据不再被任何人需要时，owner 负责把 memory 更新

Owner 状态允许多个 cache 共享同一份最新数据，同时暂时不更新 memory。只要在共享者中指定一个 owner 负责后续数据转发和最终写回，就可以减少不必要的 memory 访问。

MOESI 的设计延续了 MESI 的思路：发现协议中仍有可优化的通信模式，就通过增加状态表达更精确的数据所有权关系。

四、监听协议的可扩展性问题与目录协议

4.1 总线监听的根本限制

监听协议的核心瓶颈是总线。所有一致性消息都依赖同一条总线传播，处理器数量增加后，总线带宽和广播开销都会成为限制。

监听协议在 CPU 数量很少时（2-4 个）工作得很好，但随着 CPU 数量增加：

• 总线带宽有限，挂的 CPU 越多，冲突越多
• 广播式通信效率越来越低
• 协议状态越来越复杂（MSI → MESI → MOESI → …），但治标不治本

当系统扩展到数十乃至上百个核心时，继续在监听协议上增加状态无法根本解决总线瓶颈。

4.2 从集中式到分布式：两种共享存储架构

教材中展示了两种共享存储架构：

集中式共享存储（Symmetric Shared Memory）：

• 所有 CPU 通过一条总线连接到一个共享 memory
• 每个 CPU 有自己的 cache
• 这就是之前一直讨论的基于总线的监听协议架构
• 适合 CPU 数量少的场景

分布式共享存储（Distributed Shared Memory）：

• 每个处理器有自己的 memory
• 通过互联网络（interconnection network）连接
• 数据通过消息传递来共享
• 可以扩展支持更多处理器

对称式（Symmetric）的变体：

• 外部有较大的共享 cache（类似 L2/L3 cache）
• 每个 CPU 有自己的私有 cache
• 外部 shared cache 分成多个 bank（bank 0, bank 1, bank 2…）
• 访问不同 bank 不会冲突——提高了带宽

将共享 cache 分成多个 bank，可以让不同访问落在不同 bank 上并行进行，从而提高总带宽并减少冲突。

4.3 目录协议的基本思想

如果所有处理器都挂在同一条总线上，总线会很快成为瓶颈。分布式共享存储转而使用互联网络进行点对点通信。

在分布式共享存储架构中，改用目录协议（Directory Protocol）：

• 维护一个目录，记录哪个 cache 持有哪个数据块的副本
• 不需要广播——根据目录找到具体持有者，点对点通信
• 避免了总线广播的瓶颈
• 但目录本身需要存储空间（相当于之前讲过的”代价”）

4.4 研究者为什么要做分布式

分布式方案并不是集中式方案失效后才被想到的，而是早期核心数量较少时没有立即体现工程必要性。随着核心数增加，分布式目录协议的价值才变得明确。

前瞻性研究的价值在于提前建立可扩展架构：当核心数从少量扩展到更多时，集中式总线会成为瓶颈，而分布式目录协议可以继续扩展。

目录协议体现了体系结构研究中的一个典型模式：在当前规模下看似复杂的方案，可能在未来规模扩大后成为必要的基础机制。

五、多核环境下的 Cache 一致性与缺失分类

5.1 写入缺失与写入更新的非原子性问题

在监听协议中，写入缺失（write miss）和写入更新（write update）都不是原子操作：

写入缺失（Write Miss）：

• 先发现 cache miss
• 做一次 bus read 把数据读进来
• 然后做一次 write
• 这中间可能被其他操作打断

写入更新（Write Update）：

• 写数据 → 更新到 memory → 同时广播让其他 cache 失效或更新
• 这些步骤中间也有可能被打断

在单个多核心芯片中，可以通过占用总线（bus locking）来实现原子性：某个核心执行原子操作时暂时独占总线，其他核心等待。但随着核心数量增加，这种方式会严重限制并行性。

5.2 在没有总线的系统中

在分布式架构（没有总线）中，确保读写操作不被冲突就需要更复杂的机制——保持严格的读写顺序（ordering），这就是 memory consistency（内存一致性模型）问题。

5.3 总线流量的两个来源

总线上通信的流量主要来自两个方面：

1. 单处理器 cache 缺失造成的流量：发生 cache miss 时，需要访问 memory 并占用总线
2. 一致性协议造成的流量：MSI/MESI/MOESI 这些协议本身的通信信号导致的总线流量（invalidation、read 请求、write-back 等）

六、Cache 缺失的四种分类（4 C’s）

6.1 传统的 3C 模型

6.2 新增第四类：通信缺失（Coherence/Communication Miss）

在多核系统中，处理器之间通信也会导致 cache miss——这就是通信缺失（Communication Miss）。

通信缺失又分为两类：

真共享缺失（True Sharing Miss）

两个处理器确实在访问同一个变量。例如 P1 和 P2 都访问 X1：

• P1 把 X1 改成 modified → P2 的 X1 被 invalid
• P2 再访问 X1 → miss，需要把最新数据拿回来
• 这个缺失是真的由数据共享导致的——数据本身就两个人在用

假共享缺失（False Sharing Miss）

两个处理器访问的是不同的变量，但这些变量恰好落在同一个 cache block 里：

1
2
3
一个 cache block 里放了四个数据：X0, X1, Y0, Y1
P1 在用 X0, X1
P2 在用 Y0, Y1

• P1 更新了 X0/X1 → P2 的整个 block 被 invalid（包括 Y0, Y1）
• P2 正在算 Y0、Y1，突然发现自己的数据失效了
• P2 重新读回来——发现 Y0、Y1 根本没变！只是因为它们在同一个 block 里被”连累”了
• 过了一会儿 P2 更新 Y0/Y1 → P1 的 X0/X1 也被 invalid

假共享会导致 cache block 在多个处理器之间反复失效。虽然两个处理器访问的变量在逻辑上无关，但它们位于同一个 block 中，因此任一变量被写入都会使整个 block 失效。

如果 cache block 只有一个字，假共享可以避免；但实际系统为了利用内存带宽和空间局部性，通常一次读取多个字节。只要 block 大于单个变量，不相关变量落入同一 block 的情况就可能发生，假共享也就无法完全避免。

6.3 真共享 vs 假共享的区分

七、例题分析

7.1 题目

P1 和 P2 的 cache 中，X 和 Y 处于不同 cache block 中，且均为 Shared 状态。分析以下一系列访问操作，判断每次 cache 访问的结果是：命中（hit）、真共享缺失（true sharing miss）、假共享缺失（false sharing miss）、还是强制缺失（compulsory）。

（具体操作序列：P1 write X → P2 read Y → P1 read X → P2 write X → P1 write Y → P2 read Y → …）

7.2 关键分析

• P1 write X（两人都 shared）→ P1 进入 Modified，P2 的 X 被 invalid → 这是命中（P1 自己 cache 里有 X，从 S 变 M）
• P2 read Y：Y 本来在 P2 的 cache 里是 shared。但 P1 写 X 时——如果 X 和 Y 在同一个 block 里——P2 的整个 block 都失效了。所以 P2 read Y 时发生 miss。数据 Y 本身没被改，是被”连累”的 → 假共享缺失
• P2 read X：P2 的 X 被 invalid 了（因为 P1 写了 X），数据确实被 P1 改了 → 真共享缺失
• 后续每次 P1 写都导致 P2 的整个 block invalid，反之亦然

第一次写 X 是命中（自己 cache 里有）。其他某些操作是命中，某些是 true sharing miss（数据真的被对方改了），某些是 false sharing miss（数据没改，只是同在一个块里被 invalid 了）。关键要看：被 invalid 的时候，自己的数据到底有没有被人真的修改过。

八、多核 Cache 性能数据

8.1 OLTP 基准测试

通过 OLTP 基准测试（一种偏重数据库的测试基准），观察随着核数增加，各类缺失的变化：

• True sharing miss：随着核数增长而增加——多线程间确实会访问共享数据
• False sharing miss：也在稳步增长——核越多，不同变量落在同一 block 的概率越大
• Conflict miss、Capacity miss、Compulsory miss：变化不大，基本稳定
• Code miss（指令缺失）：随核数略有增加，因为总 cache 量增加导致更多的冷启动

8.2 Block Size 对缺失率的影响

• 总体上说，block 越大，miss per 1000 instructions 下降——空间局部性被更好地利用
• 但 false sharing miss 随 block 增大而增加——block 越大，无关变量被”连累”的概率越高
• 其他类型缺失率随 block 增大基本下降

8.3 工程权衡

• Processor 数量增加 → 外出访问时间变长
• Block size 增大 → 空间局部性好但 false sharing 增加
• 到底怎么调参数？根据实际情况——没有统一的答案

这体现了体系结构设计中的 trade-off：增加 processor 数量、增大 block size、降低缺失率或降低通信开销之间并不存在无代价的统一最优解，参数选择必须依赖目标负载和实现约束。

• Previous
  唯一分解
• Next
  不确定性与进化