Cache一致性 - 小鱼儿clouding的博客

一、从指令级并行到线程级并行

1.1 并行的层次回顾

前面已经覆盖了指令级并行（ILP, Instruction-Level Parallelism）和数据级并行（DLP, Data-Level Parallelism，如 SIMD 和 GPU），本节进入线程级并行（TLP, Thread-Level Parallelism）。

ILP：在单个 CPU 内部通过流水线、超标量、乱序执行等手段提升指令吞吐
DLP：一条指令操作多个数据（SIMD），GPU 是极端的 DLP 机器
TLP：多个处理器/核心同时运行不同的线程或程序

一个好汉三个帮。单个 CPU 再怎么搞——流水线再深、forwarding 再快、cache 再大——一个处理器能怎么样？想干大活，得多拉几个人。

1.2 为什么需要多处理器

回看单处理器的局限：

硬件资源（晶体管）不断增加，但单核性能提升遇到瓶颈
与其堆一个大而复杂的高频核心（功耗巨大），不如用多个简单核心并行工作
并行计算机是体系结构发展的必然方向

二、两种存储模型：共享存储 vs 消息传递

2.1 核心问题：多个 CPU 如何看待 Memory

有了多个 CPU，每个 CPU 有自己的 cache、甚至有自己的 memory，那么各 CPU 之间如何访问数据？这是多处理器系统设计的根本问题。

2.2 共享地址空间模型（Shared Address Space）

直觉类比：几个人住在一个寝室（或共用客厅），大家都能互相看到对方的物品，也能共享公共区域。

所有处理器共享同一个逻辑地址空间
物理上可以是统一的（集中式），也可以是分布的（分布式共享存储）
通信方式：load/store 指令直接访问，程序员只需写地址即可
编程模型简单：一个 memory copy 就完成数据传输

主打一个让程序员开心——你就 load/store，别的别管。

优势：编程简单，与单机编程模型兼容；通信量小时开销小，带宽利用好；Cache 可以减少远程访问频率；编译器设计简单。

劣势：通信量大时会占用总线（大家都访问同一片 memory 只有一条通路）；同一个地址对应的物理位置可能很近（在自己 cache 里，约 100 cycle），也可能很远（在别的 CPU 的 memory 上，>1000 cycle）；程序员无法预知访问延迟——同一个地址，有时候 100 cycle，有时候 1000 cycle，”没个准儿”。

你以为你能到达世界上的任何一个角落（逻辑地址 0x0000 到 0xFFFF 都是连续的），实际上有的角落就在你家（你自己的 memory），有的角落可能在很远的地方（别的 CPU 的 memory）。只能靠感受、猜测、摸索，没人告诉你哪片地址是快的、哪片是慢的。

2.3 消息传递模型（Message Passing）

直觉类比：像互联网一样，每人有自己的独立空间，通过发消息（message）进行通信。

每个处理器拥有完全独立的地址空间
通信是显式的：通过 send/receive 消息原语
程序员清楚知道什么时候在通信、通信代价有多大

优势：硬件简单，每个处理器只需要连接自己的 memory；程序员有明确的通信开销模型，可以做针对性优化；访问自己的一定快，通信的一定慢——但你知道慢多少；扩展性好：10 个 CPU 这样做，10000 个 CPU 也这样做，代码模型不变。

劣势：编程复杂，程序员和编译器必须显式管理通信；没有 cache 的自动缓冲效果；通信开销较大（需经过网络协议栈）。

2.4 两种模型的本质区别

维度	共享地址空间	消息传递
通信方式	隐式（load/store）	显式（send/receive）
程序员感知	不知道数据在哪	清楚通信代价
硬件复杂度	高（需保证 cache 一致性）	低
扩展性	有限（总线瓶颈）	好（无共享瓶颈）
编程难度	低	高
延迟可预测性	不可预测	可预测

三、SMP 与 DSM：共享存储的两种物理实现

3.1 集中式共享存储多处理机（SMP, Symmetric Multi-Processor）

结构：多个 CPU 各有自己的 L1/L2 cache，通过总线连接到一个统一的大 memory。

所有处理器到 memory 的访问延迟均匀（Uniform Memory Access, UMA）
也称为 UMA（Uniform Memory Access）架构
处理器规模较小（通常 < 16-32 核）时非常经济高效
这是当前消费级（C端）主流：手机里的多核 SoC、PC 的多核 CPU 都属此类

小的时候很经济——”经济”这个词就是说花不起钱的人也能用上多核。但服务器上就不是这个逻辑了，那是因为需要几十几百个核。

内存带宽瓶颈：memory 只有一个端口，所有核心都要通过总线访问。如果每人 1 GB/s 带宽，四个核合起来可能只有 2 GB/s 总线带宽，远低于每人独享的 1 GB/s x 4 = 4 GB/s。

3.2 分布式共享存储系统（DSM, Distributed Shared Memory）

结构：每个处理器带自己的本地 memory，通过网络互连。但逻辑上仍然是统一地址空间。

优点：访问本地 memory 很快，带宽可以横向扩展（每人都有独立的 memory 通道）
缺点：访问远程 memory 延迟很大（100-500 cycle，甚至微秒级）
软件开发模型不变（还是共享地址空间），但性能受物理拓扑影响

在单机上写的程序、软件模型不用变，来了直接跑。至于线程跑在哪个核上、数据落在哪个 memory 上，编译器帮你决定。但如果设计了一个认为”memory 都一样快”的算法，在这里可就不稳定了——有时候快，有时候慢。

3.3 SIMD、MIMD 与当前主流

SIMD（Single Instruction, Multiple Data）：GPU 的典型模式
MISD（Multiple Instruction, Single Data）：很少见
MIMD（Multiple Instruction, Multiple Data）：已经成为通用多处理机体系结构的选择

GPU 和这里讲的 MIMD 不一样——GPU 可以同时跑上万个线程，但这些线程的代码都一样（SIMT），而且线程之间几乎不通信。而这里讲的是”每个程序可能完全不同，有时候它们之间还要大量通信”的场景。

四、互连网络与远程访问延迟

4.1 不同互连架构的规模与延迟

互连类型	处理器规模	远程访问延迟
总线（共享存储）	< 20	~1 微秒
多层次环网（共享存储）	< 36	2-6 微秒
三维环网（共享存储）	32-2048	1-10 微秒
消息传递型	32-数万	10-100 微秒

同一芯片上的两个核通信：30-50 个 cycle
不同芯片上的两个核通信：100-500 个 cycle
数量级上差了 10 倍

挑个快的，规模就大不了；挑个规模大的，速度就高不了。这就是经典的工程权衡——又要马儿跑，又要马儿不吃草，不现实。

4.2 Amdahl 定律的警示

以 100 个处理器为例：如果程序的串行部分只占 0.25%（即可并行部分 99.75%），理论上 100 个处理器加速 80 倍。但 99.75% 的可并行比例在实际代码中极难达到。

这个例子放在这里就是提醒：以后想做并行，领导一拍板说”咱有钱了，装上 100 个 CPU”，想想代码的并行部分能做到 99.75% 吗？每次道理都懂，但数据出来的时候还是觉得”这也太离谱了”。

五、多处理器面临的三大挑战

5.1 挑战一：程序中的名义并行性有限

不是所有程序都适合并行化。GPU 之所以成功，是因为图形渲染和人工智能恰好具有极高的数据并行度、几乎没有数据依赖。

当年老黄（NVIDIA）做 GPU，就是打游戏这么一个”很小”的应用。因为在游戏渲染里，才找到了”并行度很高、没什么数据依赖”的场景。在人工智能兴起之前，GPU 就是一个打游戏的玩具，生意一直不怎么样。直到人工智能突然用了 GPU 这个方式——数据之间没有依赖，到处都并行——GPU 一下子就火了。但要找到一个能够有高并行性的场景本身就很难。

5.2 挑战二：相对较高的通信开销

远程通信的代价极大：

量化案例：处理器时钟频率 3.3 GHz，CPI = 0.5，所有 cache 访问命中（本地），仅 0.2%（2 permil） 的指令需要远程访问，远程访问延迟 200 纳秒。结果：性能下降 3.4 倍。

就 1000 条指令里只有 2 条做了远程访问，性能就直接差 3.4 倍！虽然那边的 CPU 能力很强，但来一次代价太高了，还不如本地干完算了。所以在设计编程模型时要注意：那边 CPU 很空闲、能力很强，但你要让它干，哪怕只干一点点小事，远程通信的开销就把性能直接搞崩了。

应对策略：

硬件层面：加 cache，减少远程访问频率
软件层面：数据结构设计尽量增加本地访问
多线程预取：提前把远程数据取到本地
数据多副本：在单核时代，一份数据 copy 就够了（多拷是傻子）；在多核时代，可能需要主动把数据做多份 copy 到本地，然后用 burst 方式批量传输，拷一”大份”（几十 KB），然后在本地哐哐算

5.3 挑战三：Cache 一致性问题

这是多处理器系统最头疼的问题。

六、Cache 一致性问题（Cache Coherence）

6.1 问题的提出

考虑两个处理器 A 和 B，共享同一个 memory 地址 X（初始值为 1）：

处理器 A 读 X → cache A 中有 X = 1
处理器 A 将 X 减 1 变为 0 → cache A 中 X = 0
处理器 B 读 X → cache B 中应该是什么？

问题取决于写策略：

如果是 write-through：A 写 X=0 时立即更新 memory，B 读 memory 得到 0
如果是 write-back：A 写完 X=0 先捂在 cache 里不写回 memory（等替换时再写），B 去读 memory 仍然得到 1——数据不一致了

当然应该是 0，问题是怎么确保它不是 1 呢？软件不可能——软件对 cache 是透明的，用户根本不知道 cache 里面有什么。所以只能靠硬件来解决。

6.2 Cache 一致性的定义

一个多处理器系统的 cache 是一致的（coherent），当且仅当满足以下条件：

程序序保持：处理器 P 对地址 X 写之后，P 再读 X，在没有其他处理器写 X 的情况下，P 读到的值一定是刚刚写入的值。
写传播：处理器 P 对地址 X 写之后，处理器 Q 读 X，只要写和读之间的间隔足够长（让硬件来得及传播）、且其间没有其他处理器写 X，Q 读到的值必须是 P 写入的值。
写串行化：所有处理器对同一地址的写操作，在所有处理器看来顺序是一致的。

听着要求不过分——自己写了读回来应该是一样的，别人读我写的也应该是我的值，所有写操作大家看到的顺序都一样。但实际上这个要求非常高！因为前面讲的所有东西——乱序执行、乱序提交、cache 的多级结构——都在默默不声不响地影响着这个一致性。

七、存储一致性模型（Memory Consistency）

7.1 Coherence vs Consistency

这是两个容易混淆的概念：

Coherence（连贯性/一致性）：保证同一地址在所有 cache 中的值一致（”这个数到底是多少”的问题）
Consistency（一致性/存储序）：保证不同地址的读写操作在所有处理器看来有明确的顺序（”你先写1再写2，别人看到的是先1后2还是先2后1”的问题）

这就是为什么要学技术英语——中文说起来都是”一致性”，但 Coherence 管的是”你的 cache 里 X 和我 memory 里 X 一样不一样”，Consistency 管的是”你写1再写2再写3，别人读的时候看到的是不是也是1、2、3按顺序来”。

7.2 顺序一致性（Sequential Consistency, SC）

最简单的存储一致性模型：程序的执行结果必须与某种将所有处理器的操作按程序序交错执行的结果相同。

每个处理器内部，指令按程序序执行（先 S1 再 L1）
全局来说，所有处理器的操作按某种交错顺序执行
不允许乱序

7.3 一个经典例子：两个线程四条指令

初始: X = 0, Y = 0

Thread 1:          Thread 2:
S1: X = 6          S2: Y = 6
L1: R1 = Y         L2: R2 = X

问：R1 和 R2 各是多少？

在顺序一致性下：

可能的执行顺序有多种
结果可以是：(R1=0, R2=6)、(R1=6, R2=0)、(R1=6, R2=6) ——但不会出现 (R1=0, R2=0)
因为在顺序一致性下，至少有一条 store 会先执行并被看到

如果允许乱序执行：

每个线程内部的 store 和 load 之间可能被重排
结果：4! = 24 种可能，包括 (R1=0, R2=0)
同样的代码每次运行可能出不同结果

两个程序、两行代码，执行出 24 种结果！调这样的代码非常痛苦。这就是为什么 OS 里要学锁机制（mutex）、原子指令——所有这些东西都是为了在底层乱序执行的情况下，把多线程代码的行为”管住”。

7.4 乱序执行的代价

乱序执行确实快——前面的指令被卡住（如 cache miss），后面无关的指令可以先执行。但乱序和多处理器 cache 一致性放在一起，复杂度爆炸式增长。

顺序执行就慢，想快就得乱序执行。但一乱序，两个 thread、两行代码就能出 24 种结果。那怎么办？加限制、加同步原语（fence 指令、原子操作、锁）——在上层看到的 lock/unlock、mutex、atomic，本质上都是在弥补底层乱序和 cache 不一致带来的不确定性。

八、实现 Cache 一致性的方法

8.1 写传播和写串行化

为了达到 cache 一致性，必须具备：

写传播（Write Propagation）：一个处理器的写操作必须被所有其他处理器感知。以前单核时代，写就是写给自己看；现在人多了，写完得”广播”。
写串行化（Write Serialization）：所有处理器看到同一地址上的写操作顺序必须一致。

8.2 共享数据的迁移和复制

数据迁移（Migration）：把共享数据移到正在访问它的处理器的 cache 中，减少后续远程访问延迟。

数据复制（Replication）：如果多个处理器同时读同一份数据，在每个处理器的 cache 中放一个副本，大家都可以本地访问。

好处是好处，但复制引入了一个新问题：数据改了，所有副本都得更新或作废。一个数据弄两个副本，得把它处理好。

8.3 两种硬件实现方案

小规模多处理器采用硬件（而非软件）实现 cache 一致性，以获得更快的性能。

方案一：目录协议（Directory-Based Protocol）

直觉：找个”小本本”记下来——谁访问了哪个地址、哪个 cache 里有哪个数据的副本。

在 memory 中维护一个目录（directory），记录每个 cache 块的状态和哪些处理器持有副本
当某个处理器写一个地址时，查目录，向持有该地址副本的处理器发送无效化（invalidate） 消息
问题是：目录放哪儿？memory 里很大、访问慢；放 cache 里又需要缓存一致性——”缓存又来了”。

每个 CPU 维护自己的目录还是大家共享一份？共享一份的话，跟 TLB 快表一样——内存里有一份完整的页表，cache 里有 TLB 快表，两个表还会不一致。目录也存在同样的问题。

方案二：监听协议（Snooping Protocol）

直觉：大家都”长点心”，自己不记小本本，而是在总线上做广播。

每个处理器监听（snoop）总线上的事务
当某个处理器写一个地址时，它在总线上广播
其他处理器听到广播后，检查自己 cache 里有没有这个地址
- 有：把自己那份标记为 dirty，作废掉
- 没有：不关我事，继续干活

大家都自己长点心——在总线上去听，看书上说谁写东西了，看自己有没有。没有？太好了。有？赶紧的，作废掉。

8.4 两种协议的比较

维度	目录协议	监听协议
记录方式	集中目录记录所有共享信息	各处理器自己监听总线
可扩展性	好（不依赖广播）	差（依赖总线广播，规模受限）
延迟	需查目录，额外开销	低（广播并行）
适用规模	大规模（数十到数万核）	小规模（总线互联，< 16-32 核）
硬件复杂度	目录存储开销大	每个 cache 需监听逻辑

目录办法也有，监听办法也有——如果要自己来设计，会怎么做？不容易，很不容易！现在画流水线很简单，等真设计的时候，有无数的坑要踩。

九、CPU 多核时代的功耗权衡

9.1 “四个 0.8GHz = 3.2GHz”的误区

手机芯片从单核走向多核的驱动力之一是功耗：

一个 3GHz 的高频复杂核心（如 x86 风格）功耗巨大
拆成四个 0.8GHz 的简单核心，总频率 4 x 0.8 = 3.2GHz，”听起来”还超过了 3GHz

这世界上技术宣传中常有误区，上技术课某种程度上就是培养辨别能力。搞了四个核，每个 0.8G，就说”我 4 x 0.8 = 3.2G”。代码以前跑在一个核上，现在跑在 0.8G 的核上，频率低了，想让旁边的核帮帮忙——一帮，按照前面那几倍的通信开销计算，性能直接就崩了。

9.2 真实的功耗收益

尽管有上述误区，多核在功耗控制上确实有实际收益：

低频核心功耗显著低于高频核心
手机续航从一天不到提升到一天半
前提是：程序不需要频繁的核间通信