Amdahl's law 是什么？
对 distributed training 意味着什么？

英文问法Explain Amdahl's law. · If 90% of the work is parallelizable, what's the max speedup on 8 GPUs? · How is it different from Gustafson's law? · Why doesn't adding GPUs give linear speedup?

考过面经：NVIDIA DevTech NG 2026（1p3a 1161658）；其他公司：PracHub 上标为 NVIDIA SWE 的题（"Explain Amdahl's law and GPU matmul optimization"）

先弄清楚：每个概念是什么

Speedup: 同一个任务，原来的时间 ÷ 现在的时间。
可并行比例 \(p\): 原来的运行时间里，能分给多个 worker（或被加速）的部分占多少，剩下的 \(1-p\) 是串行的。
Amdahl's law（strong scaling）: 问题规模固定，worker 加到 \(N\) 个，串行部分不变，speedup 上限是 \(1/(1-p)\)。
Gustafson's law（weak scaling）: 问题规模随 \(N\) 一起变大，串行部分不随规模增长，占比被稀释，speedup 接近线性。例：\(p = 0.9\)、\(N = 8\)：Amdahl 4.71×，Gustafson 7.3×。
Scaling efficiency: speedup ÷ \(N\)。例：\(p = 0.9\)、\(N = 8\) → 4.71/8 = 59%。

看图：串行部分为什么锁死 speedup

图 1：p = 0.9，单卡时间记为 1。每根条是 N 张卡时的时间 T(N)，左段（橙红）是串行部分 0.1，右段（蓝）是并行部分 0.9/N。卡再多 T 也小不过 0.1。

图 2：表里三种 p 的 speedup 曲线，两个轴都是对数刻度。水平虚线是上限 1/(1 − p)，曲线越往右越贴近它。斜着的点线是理想的 S = N，卡越多离它越远。

30 秒回答

If a fraction p of the runtime is parallelized over N workers, Amdahl's law gives a speedup of 1 / ((1 − p) + p / N), capped at 1 / (1 − p). With p = 0.9, eight workers give 4.7× and the cap is 10×, so first attack the serial part. That's strong scaling, a fixed problem size. Gustafson's law is weak scaling: if the problem grows with N, the serial share shrinks and speedup is nearly linear. In distributed training, exposed communication, the pipeline bubble, data loading and stragglers are the serial part, so we overlap communication and grow the global batch with the GPU count.

推导 / 关键公式

原来时间记为 1，并行部分被 \(N\) 个 worker 分掉：

\[ T(N) = (1-p) + \frac{p}{N} \] \[ S(N) = \frac{1}{(1-p) + p/N} \;\xrightarrow{N\to\infty}\; \frac{1}{1-p} \]

Gustafson 在 \(N\) 个 worker 上测，串行时间占比 \(1-p\)，同样的活一个 worker 要做 \(N\) 倍的并行部分：

\[ S = N + (1-p)(1-N) \]

手算例子

\(p = 0.9\)、\(N = 8\)：\(S = 1/(0.1 + 0.9/8) = 1/0.2125 = 4.71\)；\(N\to\infty\)：10。

\(p\)	\(N\) = 2	8	64	1024	上限
0.9	1.82	4.71	8.77	9.91	10
0.95	1.90	5.93	15.4	19.6	20
0.99	1.98	7.48	39.3	91.2	100

串行部分从 10% 压到 1%，64 卡的 speedup 从 8.8× 变成 39×。

放到 distributed training 里

"串行部分"是什么：没藏住的 communication（DP 的 all-reduce 通信量不随 \(N\) 变小）、pipeline bubble、data loading、等最慢的卡。
例：单卡一个 step 1.0 s 全是计算；\(N\) 卡时计算 \(1/N\) s，另有 0.1 s 没 overlap 的 all-reduce。8 卡 0.225 s，4.4×；64 卡 8.6×；再加卡也到不了 10×。

必答点

\(S = 1/((1-p) + p/N)\)，上限 \(1/(1-p)\)
\(p = 0.9\)：8 卡 4.71×，无穷多卡也只有 10×
先砍串行部分；\(N\) 大了以后加卡的边际收益很小
Gustafson：问题随 \(N\) 变大 → 接近线性（weak scaling）
训练里的串行部分：exposed communication、bubble、data loading、straggler → overlap、放大 global batch

追问

Amdahl 和 Gustafson 矛盾吗？

不矛盾。Amdahl 固定问题规模，问能快多少；Gustafson 固定运行时间，问能做多大的问题。Gustafson 在 1024 处理器上、串行占 0.4%–0.8% 的应用里测到 1016–1021 倍的 scaled speedup。

实际 speedup 为什么比 Amdahl 预测的还低？

Amdahl 假设并行部分完美均分、没有额外开销。实际上 communication 随 \(N\) 增加，TP 切得太细时 GEMM 变小，加卡甚至变慢（见 TP communication）。

怎么知道 \(p\) 是多少？

profile 一次看可并行部分占多少时间，或者用测到的 speedup 反推 \(p = (1 - 1/S)/(1 - 1/N)\)。例：8 卡测到 4.71× → \(p = 0.9\)。

和 GPU 加速有什么关系？

同一个公式，\(N\) 换成这部分被加速的倍数。matmul 搬到 GPU 快 50 倍但只占 80% 时间，整体 \(1/(0.2 + 0.8/50) = 4.6\times\)，瓶颈变成 CPU 预处理、host↔device 拷贝和 kernel launch。

大规模训练实际 scaling 怎么样？

Megatron-LM 把模型和 batch 随卡数一起放大（weak scaling），8.3B 模型在 512 张 GPU 上做到 76% scaling efficiency（相对单卡）。

来源CUDA C++ Best Practices Guide §4.1.3.1–4.1.3.3 · Gustafson 1988, Reevaluating Amdahl's Law（CACM 31(5)，作者主页全文；引 Amdahl 1967, AFIPS pp.483–485）· Rajbhandari et al. 2020, ZeRO §7.1（p.13）· Shoeybi et al. 2019, Megatron-LM abstract（p.1）、§5.1.1（p.6）

Amdahl's law 是什么？对 distributed training 意味着什么？