阿姆达尔定律

1. 推导
2. 举例
3. 和边际收益递减规律的关系
4. 串行程序的优化
5. 局限性

阿姆达尔定律给出了任务在固定负载的情况下，随着系统资源的提升，执行速度的理论上限。以计算机科学家Gene Amdahl命名。

$S_{latency}(s) = \frac{1}{(1-p)+\frac{p}{s}}$

其中 $S_{latency}$ : 整个任务的提速比。 s: 部分任务得益于系统资源升级带来的提速比。 p: 这部分任务执行时间占整个任务执行时间的百分比（系统资源提升前）。

从上可以得到： $\begin{cases} S_{latency}(s) \le\frac{1}{1-p} \\ \lim \limits_{s \to 0}S_{latency}(s)=\frac{1}{1-p} \end{cases}$

以上公式说明了通过资源升级来给任务加速的加速比上限，而且和提速的幅度无关，理论加速比总是受限于不能加速的任务的比例。

阿姆达尔的定律常用于并行计算中，用来估计多处理器情况下的理论加速比。例如，如果有个程序在单核下需要执行20个小时，并且不能被并行处理的部分占1个小时的执行时间，剩余的19个小时(p=0,95)的任务可以并行化，那么不管有多少核心来并行处理这个程序，最小执行时间不可能小于一个小时。由此得到，理论加速比的上限是20倍（1/(1-p) = 20）。因此，并行计算只和少数的核心和极度可并行化的程序相关。

1. 推导

把一个任务放在资源可提升的系统中执行和在原生系统中执行做比较，可以把这个任务分为两个部分：

不能从系统资源提升收益的部分
能通过资源提升加速的部分

例如，有这样一个程序，它负责处理磁盘文件。这个程序的一部分扫描磁盘上的目录然后在内存中创建文件列表。完成以后，程序的另一部分把每一个文件传给各个线程去处理。那么，扫描目录并且创建文件列表的部分并不能在并行计算机上获得加速，但是处理文件的部分可以通过并行计算加速。

在系统资源提升以前，整个任务的执行时间用$T$表示。它$T$包含上面介绍的两部分执行时间。能够获益于系统资源的部分执行时间占比用$p$表示。不能获益的程序比例就是$1-p$，那么 $T=(1-p)T+pT.$

获得加速后的部分执行时间变为 ${\frac {p}{s}}T.$

因此，加速后总的执行时间为 $T(s)=(1-p)T+{\frac {p}{s}}T.$

假定负载是W，那么阿姆达尔定律给出了负载W下的时间加速比，得到 $S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.$

2. 举例

例一

如果30%的执行时间是可以加速的，那么p=0.3，如果加速比是2, 即s=2，那么由阿姆达尔定律得到全局加速比为 $S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac {0.3}{2}}}}=1.18.$

例二

有一个串行任务，可以分成连续执行的四个部分，这四个部分的执行时间占分别为p1=0.11, p2=0.18, p3=0.23, p4=0.48。假设第一部分不能加速，即s1=1，第二部分s2=5，第三部分s3=20，第四部分s4=1.6。通过阿姆达尔定律可知，全局加速比为

$S_{\text{latency}}={\frac {1}{ {\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}{s4}}}}={\frac {1}{ {\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}}}=2.19.$

注意第二部分和第三部分的20倍提速和5倍提速是如何被第四部分（48%占比）的1.6倍加速给拉下来的。

3. 和边际收益递减规律的关系

阿姆达尔定律经常和边际收益递减规律混为一谈，尽管只有在特定的情形下应用阿姆达尔定律才展现出边际递减率。如果选择了最佳的部分来提速，那么我们会看到随着资源的进一步提升，获得的加速是单调递减的。如果选择的不是最优，那么继续提升最关键部分还是能看到明显的提高。注意实际情况中，这种通过改善非最优部件来提升系统性能的事情是合理的，因为提升关键部分常常会更加困难，或者花费更多时间。

如果你是在运行一个固定计算量的程，而且正在考虑随着机器处理核心数量的增加伴随而来的收益，那么阿姆达尔定律确实展现了边际递减。每个新增加的处理器带来的性能比前一个处理器带来的要小。每次处理核心数加倍，加速比减小，最终趋向于1/(1-p)。

这样的分析忽略了其他潜在的瓶颈，例如内存带宽和I/O带宽，如果它们不随这核心数目提升，那么把这些瓶颈考虑进去更加显现了纯粹通过增加处理器所具有的边际递减规律。

4. 串行程序的优化

For example, with a serial program in two parts A and B for which TA = 3 s and TB = 1 s,

假如有个串行程序，可以分为两个部分A和B， TA = 3s，TB = 1s。

如果B提速5倍，即s=5，p = TB/(TA + TB) = 0.25，那么 $S_{\text{latency}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;$
如果A提速两倍，即s=2, p = TA/(TA + TB) = 0.75，那么 $S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.$

因此，把A加速两倍优于把B加速5倍。速度的提升比例可以这么计算 ${\text{percentage improvement}}=100\left(1-{\frac {1}{S_{\text{latency}}}}\right).$

由此

A提速两倍带来37.5%的整体加速。
B提速5倍只能带来整体20%的提速。

5. 局限性

阿姆达尔定律只能用在固定范围的问题上面。在实际中，随着可用的计算资源越来越多，这些资源倾向于用于更大的问题上面（更大的数据集），而且并行部分上的时间开销通常比串行工作增长要快。在这样的情况下，(Gustafson’s law)古斯塔夫森定律给出了更佳的接近实际的针对并行计算性能的评估[1]。

[1] Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. p. 61.