阿姆达尔定律(Amdahl's Law)可用于计算通过并行运行一部分计算可加速的计算量。阿姆达尔定律以吉恩·阿姆达尔(Gene Amdahl)的名字命名，他在1967年提出了该定律。大多数使用并行或者并发系统工作的开发人员都对潜在的加速有着直观的感觉，即使不知道阿姆达尔定律也是如此。无论如何，了解阿姆达尔定律可能仍然有用。

我将首先以数学方式解释阿姆达尔定律，然后使用图表说明阿姆达尔定律。

定义了阿姆达尔定律

可以并行化的程序(或者算法)可以分为两部分：

• 不能并行化的部分
• 可以并行化的部分

想象一个程序处理磁盘上的文件。该程序的一小部分可能会扫描目录并在内存中内部创建文件列表。之后，每个文件将传递到单独的线程进行处理。扫描目录并创建文件列表的部分无法并行化，但可以处理文件。

串行(非并行)执行程序所花费的总时间称为T。时间T包括不可并行部分和可并行部分的时间。不可并行化的部分称为B。可并行化的部分称为TB。以下列表总结了这些定义：

• T =串行执行的总时间
• B =不可参数部分的总时间
• T-B =可并行化部分的总时间(串行执行时，不是并行执行时)

由此可见：

T = B + (T-B)

乍一看，程序的可并行化部分在方程式中没有自己的符号，可能看起来有些奇怪。但是，由于可以使用总时间T和B表示方程的可并行化部分(不可并行化的部分)，因此实际上从概念上简化了方程，这意味着该形式包含的变量较少。

可并行处理的部分是" TB"，可以通过并行执行来加速。它可以加速多少取决于我们申请执行它的线程数或者CPU数。线程或者CPU的数量称为N。因此，可并行化部分可以执行的最快速度是：

(T - B) / N

编写此内容的另一种方法是：

(1/N) * (T - B)

维基百科使用此版本，以防我们在此阅读有关阿姆达尔定律的信息。

根据阿姆达尔定律，使用N个线程或者CPU执行可并行化部分时，程序的总执行时间为：

T(N) = B + (T - B) / N

T(N)表示并行因子为N的全部执行。因此，T可以写为T(1)，意味着并行因子为1的总执行时间。使用T(1)代替T，阿姆达尔定律看起来像像这样：

T(N) = B + ( T(1) - B ) / N

它仍然意味着相同的意思。

计算实例

为了更好地理解阿姆达尔定律，我们来看一个计算示例。执行一个程序的总时间设置为1. 该程序的不可并行化部分为40％，这在总时间1中等于0.4. 因此，可并行化部分等于" 1 0.4 = 0.6"。

具有2的并行化因子的程序的执行时间(2个线程或者CPU执行可并行化部分，因此N为2)将为：

T(2) = 0.4 + ( 1 - 0.4 ) / 2
     = 0.4 + 0.6 / 2
     = 0.4 + 0.3
     = 0.7

使用5而不是2的并行化因子进行相同的计算将如下所示：

T(5) = 0.4 + ( 1 - 0.4 ) / 5
     = 0.4 + 0.6 / 5
     = 0.4 + 0.12
     = 0.52

图解的阿姆达尔定律

为了更好地理解阿姆达尔定律，我将尝试说明该定律是如何得出的。

首先，程序可以分解为不可并行化的部分B和可并行化的部分1-B，如下图所示：

顶部带有定界符的行是总时间T(1)。

在这里，我们可以看到并行化因子为2的执行时间：

在这里，我们可以看到并行度为3的执行时间：

优化算法

根据阿姆达尔定律，自然可以得出这样的结论：可并行化部分可以通过向其扔硬件来更快地执行。更多线程/ CPU。但是，不可并行化的部分只能通过优化代码来更快地执行。因此，我们可以通过优化不可并行化的部分来提高程序的速度和并行性。通常，我们甚至可以通过将一些工作移到可并行化部分中，来将算法更改为具有较小的不可并行化部分。

优化顺序部分

如果优化程序的顺序部分，还可以使用阿姆达尔定律计算优化后的程序执行时间。如果将不可并行化的部分B优化为因数O，则阿姆达尔定律如下所示：

T(O,N) = B / O + (1 - B / O) / N

请记住，程序的不可并行化部分现在需要B / O时间，因此，可并行化部分需要1 B / O时间。

如果B为0.4，O为2，N为5，则计算如下：

T(2,5) = 0.4 / 2 + (1 - 0.4 / 2) / 5
       = 0.2 + (1 - 0.4 / 2) / 5
       = 0.2 + (1 - 0.2) / 5
       = 0.2 + 0.8 / 5
       = 0.2 + 0.16
       = 0.36

执行时间与加速

到目前为止，我们仅使用阿姆达尔定律来计算优化或者并行化之后程序或者算法的执行时间。我们还可以使用阿姆达尔定律计算加速比，这意味着新算法或者程序比旧版本快多少。

如果程序或者算法的旧版本时间为T，则加速比为

Speedup = T / T(O,N)

我们通常将T设置为1只是为了计算执行时间和加速时间，是旧时间的一小部分。等式如下所示：

Speedup = 1 / T(O,N)

如果我们插入阿姆达尔定律计算而不是T(O，N)，则会得到以下公式：

Speedup = 1 / ( B / O + (1 - B / O) / N )

在B = 0.4，O = 2和N = 5的情况下，计算公式为：

Speedup = 1 / ( 0.4 / 2 + (1 - 0.4 / 2) / 5)
        = 1 / ( 0.2 + (1 - 0.4 / 2) / 5)
        = 1 / ( 0.2 + (1 - 0.2) / 5 )
        = 1 / ( 0.2 + 0.8 / 5 )
        = 1 / ( 0.2 + 0.16 )
        = 1 / 0.36
        = 2.77777 ...

这意味着，如果我们将不可并行化(顺序)部分优化为2倍，并将可并行化部分并行化为5倍，则该程序或者算法的新优化版本的运行速度最多将比2.77777倍旧版本。

测量，而不仅仅是计算

尽管阿姆达尔定律使我们能够计算算法并行化的理论速度，但不要过分依赖此类计算。实际上，当我们优化或者并行化算法时，许多其他因素也可能起作用。

内存，CPU高速缓存内存，磁盘，网卡等(如果使用磁盘或者网络)的速度也可能是限制因素。如果该算法的新版本被并行化，但导致更多的CPU高速缓存未命中，我们甚至可能无法获得使用x N个CPU所需的x N加速。如果最终使内存总线，磁盘或者网卡或者网络连接饱和，情况也是如此。