本页目录
并行 I · 并行模型与缓存一致性
对标：CMU 15-418 / Berkeley CS267 ｜ 前置：perf-01（Amdahl）、os-02（并发）、csapp-02（缓存） perf 线在单核上榨性能，到了极限就得用多核。但并行不是"加核就快"——它有自己的定律（Amdahl/Gustafson）、自己的硬件现实（缓存一致性）、自己的编程模型。这一页建立并行的世界观：并行的加速上限在哪、多核共享内存底下的缓存一致性怎么运作、以及数据并行 vs 任务并行的划分。这是走向 GPU（gpu 线）和 MLSys（mlsys 线）的地基。
学习层：8 个核为什么可能只换来 4.7 倍？
具体谜题：并行循环与共享计数器
一个程序 90% 的工作可并行，10% 必须串行；8 核下 Amdahl 上限是多少？现在让四个线程各自更新相邻数组槽位：逻辑上没有共享变量，为什么仍可能在 MESI 总线上互相失效？先分别预测“算法上限”和“缓存一致性代价”。
\n+\n+
先下注，再看时间线
\n+
预测：① \(S_8=1/(0.1+0.9/8)\approx4.71\)，加核不会突破串行尾巴；② 相邻计数器落在同一缓存行时，写入会产生乒乓，padding 到独立缓存行可减少失效；③ 数据并行适合独立像素，任务并行适合不同阶段，二者不能只按线程数比较。
\n+最小心智模型：工作分解 + 共享协议
并行性能同时受两个系统约束：任务图中不可切开的关键路径，以及多个核心对同一缓存行的所有权竞争。线程数只是资源请求；真正的可扩展性来自减少关键路径、分离写集合并保持工作均衡。
\n+
形式机制与不变量
固定问题规模的 Amdahl 定律为 \(S(N)=1/(s+(1-s)/N)\)，其中 \(s\) 是串行比例；若问题规模随核数扩展，可用 Gustafson 近似 \(S_G(N)=N-s(N-1)\)。MESI 不变量是：同一缓存行在某一时刻至多有一个 Modified 所有者；另一个核心写入该行必须使旧副本失效。于是不同字段若共享一行，也会付出一致性通信。
反例与失效边界
- Amdahl 假设比例稳定；输入规模、I/O、调度和同步随 \(N\) 变化时，曲线只是基线。
- padding 能缓解伪共享，却会增加内存占用、降低局部性；只读共享和真正共享写入的代价不同。
- 缓存一致性不等于语言内存模型的同步正确性；看见最新值、原子性和 happens-before 是不同命题。
迁移任务：为一个循环选择并行模型
把 L07 的向量循环、图像 gamma 校正和一个网页请求管线分别标为数据并行或任务并行，画出关键路径和写集合。再用 Amdahl 估算收益，用伪共享 trace 找出需要私有累加器或对齐的位置，并说明什么时候应改用工作窃取或 MPI。
无 JavaScript 时的静态读法：串行比例 \(s=0.1\) 时，1、2、4、8 核 Amdahl 加速约为 1、1.82、3.08、4.71。若四个线程写入同一条 64-byte 缓存行，虽然槽位不同，MESI 仍需在每次写时转移行的 Modified 所有权；把每个槽位隔 64 bytes 后，逻辑结果不变但失效事件显著减少。交互版先预测，再切换核心数、串行比例与 packed/padded 布局查看加速和一致性事件。
| 核心数 | Amdahl \(s=.1\) | 写布局 | 一致性风险 |
|---|---|---|---|
| 1 | 1.00× | packed | 无跨核写 |
| 4 | 3.08× | packed | 高，缓存行乒乓 |
| 8 | 4.71× | padded | 低，仍受串行段限制 |
1. 并行的加速上限：Amdahl vs Gustafson
Amdahl 定律（perf-01 的并行版）：程序中串行部分占比 \(s\)，用 \(N\) 核，加速比 \(\le \frac{1}{s + (1-s)/N}\)。残酷推论：只要有 5% 串行部分，无论多少核，加速比不超过 20×。串行瓶颈是并行的天花板——这解释了为什么"加核收益递减"。
Gustafson 定律（乐观的另一面）：实践中问题规模常随核数增长（更多核就处理更大数据）——此时可并行部分随规模扩大、串行占比相对缩小，加速接近线性。"固定问题看 Amdahl（悲观），扩展问题看 Gustafson（乐观）"——两者不矛盾，是看问题规模是否固定。ML 训练就是 Gustafson 的胜利：更多 GPU → 训更大模型/更大 batch。
关键认知：并行前先问"串行部分是什么、能否消除"——同步点、共享资源争用（os-02 锁）、不可并行的数据依赖，都是串行瓶颈。减少串行比增加核数更重要。
2. 缓存一致性：多核共享内存的底层魔法
多核各有自己的 L1/L2 缓存（csapp-02），却共享同一主存——如果核 A 改了变量 x（在它的缓存里），核 B 缓存里的旧 x 怎么办？ 这就是缓存一致性（cache coherence）问题，由硬件协议（MESI）解决：
- MESI 协议：每个缓存行有四态——Modified（我改过，独占）/ Exclusive（只我有，没改）/ Shared（多核共享只读）/ Invalid（失效）。核要写一个行，先让其他核的该行失效（invalidate），取得独占后再改。
- 代价——一致性流量：多核频繁读写同一缓存行 → 大量失效消息在核间飞 → 性能暴跌。这正是 os-02/csapp-02 说的伪共享的硬件根源：两个线程改同一行的不同字节，硬件不知道它们无关，照样来回失效。
- 内存序（memory ordering）（os-02 埋的坑）：为性能，CPU 允许一定的重排——一个核的写，别的核看到的顺序可能不同。这就是为什么无锁编程要内存屏障精确控制可见性（par-02 细讲）。
读法：共享内存并行的"共享"是有硬件成本的幻觉——理解 MESI，你就懂了"为什么线程私有数据要对齐到缓存行""为什么争用同一个原子计数器不 scale"。多核性能的很多坑都在这条缓存一致性总线上。
3. 并行的两种分解
把工作拆给多核，两种基本模式：
- 数据并行：同样的操作作用于大量数据的不同部分（数组每段一个线程、矩阵每块一个核）——规整、易扩展、GPU 的天下（gpu 线）。SIMD（perf-01）是数据并行的指令级版，GPU 是它的大规模版。
- 任务并行：不同的任务并行做（一个线程解码、一个渲染、一个 I/O）——不规整、靠任务调度。
分治天然并行（🔗 algo-01）：归并排序左右两半可并行、MapReduce（dist-03）是数据并行的分布式版。识别"哪部分是数据并行"是并行化的第一步——数据并行好扩展，优先找它。
4. 共享内存并行编程模型
在多核上写并行代码的几种抽象：
- 线程 + 锁（os-02）：最底层、最灵活、最易错（竞态、死锁）。
- OpenMP：
#pragma omp parallel for一行把循环并行化——声明式、适合数据并行的规整循环，科学计算常用。 - 任务并行库（TBB、Cilk、Rust rayon）：你描述任务和依赖，运行时用工作窃取（work-stealing）调度器自动负载均衡——空闲线程从忙线程"偷"任务，优雅解决负载不均。
- 消息传递（MPI）：不共享内存，进程间显式发消息——多机集群的模型（HPC 超算、跨节点，与 dist 线相通）。
选择：规整数据并行用 OpenMP/GPU、不规则任务用工作窃取、跨机器用 MPI。"共享内存 vs 消息传递"是并行编程的两大哲学——前者方便但受限于单机 + 一致性成本，后者可扩展到千万核但要显式通信。
5. 练习与要点
例 1（Amdahl 算天花板） 程序 90% 可并行，无限核的加速上限？（\(1/0.1 = 10×\)）——"10% 串行就锁死在 10× 以内"，理解为什么要死磕串行部分。
例 2（伪共享复现） 4 线程各累加一个数组的相邻 4 元素（同缓存行）vs 各隔 64 字节——后者快数倍。用 perf 看缓存一致性流量。MESI 的代价亲手可测（也是 os-02 例 3 的硬件解释）。
例 3（找数据并行） 给"图像每像素做 gamma 校正""快排""网页服务器处理请求"分类到数据并行/任务并行——培养"这活儿怎么拆给多核"的直觉，并行化的第一判断。\(\blacksquare\)
下一页：并行 II——同步原语与无锁结构：原子操作、内存序，以及不用锁也能正确并发的深水区。