Amdahl’s law（阿姆达尔定律）公式推导与思考

介绍

Amdahl’s law（阿姆达尔定律） 由计算机科学家 Gene Amdahl 在 1967 年提出，旨在用公式描述在并行计算中，多核处理器理论上能够提高多少倍速度，公式如下：
$$S=\frac{1}{1-a+\frac{a}{n}}$$
$S$ 为 speedup，代表全局加速倍速（原来总时间/ 加速后总时间），$a$ 为并行计算所占比例（可以并行计算代码量 / 总代码量），$n$ 为并行节点处理个数，可以理解为 CPU 的核心数，这里先简要介绍下，后面会详细说明并且推导。

前置说明

Fraction enhanced

Fraction enhanced 顾名思义是部分提高。例如我的程序总共有 100 行代码，其中 50 行是可以通过并行计算的，那么这 50 行代码就是 Fraction enhanced 。但是实际上 Fraction enhanced 是一个比例数值，是并行计算代码 / 总代码量。
$$Fractionenhanced=\frac{parallelcode}{totalcode}$$
例如上面的例子，$Fractionenhanced=50/100=0.5$ ，由此我们可以发现，Fraction enhanced 的值永远小于 1。

Speedup enhanced

$$Speedupenhanced=\frac{Oldexecutiontime}{Newexecutiontime}$$

如上面公式所得，Speedup enhanced 等于 原有运行时间 / 并行计算加速后的时间 。例如系统原来串行计算需要 6 秒，加速后只需要 3 秒，那么 $Speedenhanced=6/3=2$ 。由此可知 Speedup enhanced 的值永远大于 1。

带入 Amdahl’s law

我们分别把 Fraction enhanced 和 Speedup enhanced 带入 Amdahl’s law。Fraction enhanced 对应公式中的 $a$ ，即并行计算所占比例。Speedup enhanced 对应 $n$ ，即并行节点处理个数。

Speedup enhanced 为什么可以代替 $n$ ？

这里大家可能有一点疑问，Speedup enhanced 明明是 未加速前时间 / 加速后的时间，为什么就可以代表并行节点处理个数。在理论上，单核处理器处理一个任务需要 100 秒，那么双核处理它应该需要 50 秒。时间上它提速了 2 倍， cpu 个数上它也提升了 2 倍，故两个可以替换。 $$\begin{array}{rl}Speedupenhanced& =\frac{Oldexecutiontime}{Newexecutiontime}\\ & =\frac{100}{50}=2\\ & =\frac{Newcpucores}{Oldcpucores}\\ & =\frac{2}{1}=2\end{array}$$

带入后公示得： $$\begin{array}{rl}S& =\frac{Oldtotalexecutiontime}{Newtotalexecutiontime}\\ & =\frac{1}{1-Fractio{n}_{enhanced}+Fractio{n}_{enhanced}/Speedu{p}_{enhanced}}\end{array}$$

证明

• $S$ 为我们所需要的结果，全局提速倍速
• $Oldtotalexecutiontime$ （原来系统执行总时间）为 $T$
• $Newtotalexecutiontime$ （加速后系统执行总时间）为 $T^{\prime }$
• 系统中并行代码块（指能够通过并行计算加速的代码块）原来执行时间为 $t$
• 系统中并行代码块（指能够通过并行计算加速的代码块）加速后执行时间为 $t^{\prime }$
• 系统中串行代码块（指不能通过并行计算加速的代码块）执行时间为 $t_n$
• $Fractio{n}_{enhanced}$ 为 $f^{\prime }$
• $Speedu{p}_{enhanced}$ 为 $s^{\prime }$

$$\begin{array}{c}S=\frac{T}{T^{\prime }}\\ T=t_n+t\\ T^{\prime }=t_n+t^{\prime }\\ f^{\prime }=\frac{t}{T}=\frac{t}{t_n+t}\\ s^{\prime }=\frac{t}{t^{\prime }}\\ \frac{f^{\prime }}{s^{\prime }}=\frac{t}{t_n+t}÷\frac{t}{t^{\prime }}=\frac{t^{\prime }}{t_n+t}\end{array}$$

带入公式得： $$\begin{array}{rl}S& =\frac{T}{T^{\prime }}\\ & =\frac{t_n+t}{t_n+t^{\prime }}\\ & =\frac{1}{(t_n+t^{\prime })/(t_n+t)}\\ & =\frac{1}{1-\frac{t}{t_n+t}+\frac{t^{\prime }}{t_n+t}}\\ & =\frac{1}{1-f^{\prime }+\frac{f^{\prime }}{s^{\prime }}}\\ & =\frac{1}{1-Fractio{n}_{enhanced}+Fractio{n}_{enhanced}/Speedu{p}_{enhanced}}\\ & =\frac{1}{1-a+\frac{a}{n}}\end{array}$$

证明完毕！

总结

让我们回到最初的公式
$$S=\frac{1}{1-a+\frac{a}{n}}$$
$a$ 为并行计算所占比例，$n$ 为并行节点处理个数。当 $a=0$ 时（即只有串行没有并行），无论 $n$ 为多少，加速比 $S$ 均为 1。当 $n\to +\mathrm{\infty }$ ，当 cpu 核心数无限增多的时候，极限加速比 $S=1/(1-a)$ 。例如若并行代码有 75%，极限加速比不能超出 4。

由此我们可知，在并行系统中一味的增加运算资源，并不能永远成倍的提升系统整体性能。

参考资料

阿姆达尔定律

Computer Organization | Amdahl’s law and its proof

理解性能提升By阿姆达尔定律(Amdahl’s law)