Amdahl-Law

Amdahl Law（Amdahl 定律）

Problem（解决什么问题）

Amdahl 定律要解决的是：当系统中只有一部分可以被优化时，局部优化最多能给整体系统带来多少加速。

它关心的是：

• 优化的是总运行时间中的哪一部分
• 这一部分被加速了多少倍
• 没有被优化的部分如何限制整体收益
• 为什么局部性能提升不能直接等于整体性能提升

---

Basic Idea（核心思想）

Amdahl 定律的核心思想是：

整体运行时间由不可加速部分和可加速部分共同决定；局部加速越强，不可加速部分越成为整体性能上限。

设原始总时间为 $T_{old}$：

• $\alpha$：可以被加速的部分占原始总时间的比例
• $1-\alpha$：不能被加速的部分占原始总时间的比例
• $k$：可加速部分的加速倍数
• $S$：整体加速比（speedup）

那么新时间占原始时间的比例是：

$$(1-\alpha )+\frac{\alpha }{k}$$

整体加速比是：

$$S=\frac{1}{(1-\alpha )+\frac{\alpha }{k}}$$

所以新运行时间是：

$$T_{new}=\frac{T_{old}}{S}$$

也就是：

$$T_{new}=T_{old}\left((1-\alpha )+\frac{\alpha }{k}\right)$$

---

Working Process（工作流程）

1. 拆分原始运行时间

把原始运行时间拆成两部分：

原始总时间 = 不可加速部分 + 可加速部分

如果把 $T_{old}$ 归一化为 1，那么：

不可加速部分 = 1 - alpha
可加速部分 = alpha

---

2. 只压缩可加速部分

如果可加速部分被加速 $k$ 倍，那么它的新时间比例变成：

$$\frac{\alpha }{k}$$

不可加速部分保持不变：

$$1-\alpha$$

---

3. 合成新的整体运行时间

新时间比例是：

$$(1-\alpha )+\frac{\alpha }{k}$$

因此：

$$T_{new}=T_{old}\left((1-\alpha )+\frac{\alpha }{k}\right)$$

flowchart TD
    Old["T_old"] --> Split["拆分运行时间"]
    Split --> Fixed["不可加速部分: 1 - alpha"]
    Split --> Improved["可加速部分: alpha"]
    Improved --> Faster["加速 k 倍: alpha / k"]
    Fixed --> New["T_new 比例"]
    Faster --> New

---

4. 由时间比例得到整体加速比

整体加速比定义为：

$$S=\frac{T_{old}}{T_{new}}$$

因为：

$$\frac{T_{new}}{T_{old}}=(1-\alpha )+\frac{\alpha }{k}$$

所以：

$$S=\frac{1}{(1-\alpha )+\frac{\alpha }{k}}$$

---

5. 当局部加速趋近无穷

如果可加速部分的加速倍数 $k$ 趋近无穷：

$$k\to \infty$$

那么：

$$\frac{\alpha }{k}\to 0$$

整体加速比的上限变成：

$$S_{max}=\frac{1}{1-\alpha }$$

这说明：

即使可加速部分几乎不再花时间，整体加速比也不会超过 1 / (1 - alpha)。

从运行时间角度看：

$$T_{new}\to T_{old}(1-\alpha )$$

所以时间减少的上限就是原始总时间中的 $\alpha$ 部分；剩下的 $1-\alpha$ 部分无法通过优化这一个局部继续减少。

---

Example（具体例子）

假设：

• $\alpha =0.8$：原始运行时间中 80% 可以被优化
• $k=4$：这 80% 被加速 4 倍

新时间比例是：

$$(1-0.8)+\frac{0.8}{4}=0.2+0.2=0.4$$

整体加速比是：

$$S=\frac{1}{0.4}=2.5$$

含义：

局部加速 4 倍，不代表整体加速 4 倍。

整体只加速了 2.5 倍，新运行时间是原来的 40%：

$$T_{new}=0.4T_{old}$$

---

Common Pitfall（常见误区）

如果 $S$ 表示整体加速比，那么：

$$T_{new}=\frac{T_{old}}{S}$$

不能写成：

$$T_{new}=T_{old}\cdot S$$

原因是：

• $S>1$ 表示程序变快
• 程序变快时，运行时间应该变小
• 所以新时间应当除以加速比

---

Trade-off（设计权衡）

优点：

• 可以估算某个局部优化对整体性能的理论上限
• 能帮助判断优化热点是否值得投入
• 能解释为什么不可并行或不可优化部分会限制整体收益

缺点：

• 依赖对 $\alpha$ 的估计，实际系统中这个比例可能会变化
• 假设可加速部分和不可加速部分边界清晰
• 只描述上限，不直接告诉我们如何实现优化

适用场景：

• 性能优化收益估算
• 并行化收益分析
• 判断系统瓶颈是否值得继续优化
• 理解 CSAPP 中局部改进与整体性能之间的关系

---

Summary

Amdahl 定律说明：

局部优化的整体收益，受它在原始总时间中所占比例限制。

当 $k\to \infty$ 时，整体加速比上限是：

$$S_{max}=\frac{1}{1-\alpha }$$

核心公式：

$$S=\frac{1}{(1-\alpha )+\frac{\alpha }{k}}$$

新时间：

$$T_{new}=\frac{T_{old}}{S}$$

---

Related Concepts（关联概念）

• Information Is Bits + Context：CSAPP 章节学习中的体系结构理解记录