阿姆达尔与古斯塔夫森定律

两个公式描述了当你给并行程序增加处理器时的速度提升。它们对程序增长做出不同的假设，因此给出不同的极限。这篇笔记解释何时使用每一个，以及为什么这些假设很重要。

基本想法

每个程序的一部分以串行方式运行，一部分可以并行运行。串行部分是一个瓶颈：无论增加多少处理器，该串行部分总是花费相同的时间。如果代码的 10% 是串行的，无论有多少个核心，速度永远不会超过 10 倍。这是 Amdahl 定律背后的见解。

但实际程序随着增加核心时不会保持相同的规模。如果购买有 100 个核心而不是 10 个的机器，可能要解决更大的问题。现在有了容量，可能会并行化更多的部分。Gustafson 定律问的是：用更多核心在相同时间内能做多少工作？答案取决于如何扩展问题。

设 $p$ 是程序的串行部分比例，则 $1-p$ 是并行部分。在 $P$ 个处理器上：

S_p = \frac{1}{(1 - p) + p/P}

这是 Amdahl 定律。随着 $P$ 增长，加速比趋近于 $1/p$ 。如果 10% 是串行的，加速比上限为 10 倍。如果 1% 是串行的，上限是 100 倍。

Gustafson 定律说的是：假设在单处理器上，串行代码花费比例 $p$ 的时间，并行代码花费比例 $1-p$ 的时间。如果现在有 $P$ 个处理器并运行相同的串行代码，在相同时间内还能做多少额外的并行工作？

S_p = P - p(P - 1)

这与 $P$ 线性扩展。获得 $P - p(P-1)$ 倍加速比，远好于 Amdahl 的固定上限。串行部分花费成本相同，但并行部分扩展到填满额外的核心。

下面的工具展示两个定律。移动滑块，看两条曲线如何分化。Amdahl 达到极限；Gustafson 继续增长。两者之间的选择是关于你在问什么问题。

核心数: 16

串行比例: 10.0%

Amdahl

6.40x

Gustafson

14.50x

Amdahl: 1 / (0.100 + 0.0563)

Gustafson: 16 - 1.500

在 16 个核心，{serialFraction} 串行情况下，Amdahl: 6.40x，Gustafson: 14.50x

合成数据模拟，带随机种子，同样的设置每次结果都一样。可调整核心数和串行比例的滑块。