Amdahl's law（阿姆達(dá)爾定律）公式推導(dǎo)與思考

原文地址：https://www.inlighting.org/archives/amdahls-law-and-its-proof

1. 介紹

Amdahl's law（阿姆達(dá)爾定律） 由計算機(jī)科學(xué)家 Gene Amdahl 在 1967 年提出，旨在用公式描述在并行計算中，多核處理器理論上能夠提高多少倍速度地梨，公式如下：
$S=\frac{1}{1-a+\frac{a}{n}}$
$S$ 為 speedup叉袍，代表全局加速倍速（原來總時間/ 加速后總時間）， $a$ 為并行計算所占比例（可以并行計算代碼量 / 總代碼量）， $n$ 為并行節(jié)點處理個數(shù)，可以理解為 CPU 的核心數(shù)，這里先簡要介紹下轧拄，后面會詳細(xì)說明并且推導(dǎo)。

2. 前置說明

2.1 Fraction enhanced

Fraction enhanced 顧名思義是部分提高讽膏。例如我的程序總共有 100 行代碼檩电，其中 50 行是可以通過并行計算的，那么這 50 行代碼就是 Fraction enhanced 府树。但是實際上 Fraction enhanced 是一個比例數(shù)值俐末，是并行計算代碼 / 總代碼量。
$Fraction\ enhanced=\frac{parallel\ code}{total\ code}$
例如上面的例子奄侠， $Fraction\ enhanced = 50/100=0.5$ 卓箫，由此我們可以發(fā)現(xiàn)，Fraction enhanced 的值永遠(yuǎn)小于 1垄潮。

2.2 Speedup enhanced

$Speedup\ enhanced=\frac{Old\ execution\ time}{New\ execution\ time}$

如上面公式所得烹卒，Speedup enhanced 等于 原有運行時間 / 并行計算加速后的時間 。例如系統(tǒng)原來串行計算需要 6 秒弯洗，加速后只需要 3 秒旅急，那么 $Speed\ enhanced=6/3=2$ 。由此可知 Speedup enhanced 的值永遠(yuǎn)大于 1牡整。

2.3 帶入 Amdahl's law

我們分別把 Fraction enhanced 和 Speedup enhanced 帶入 Amdahl's law藐吮。Fraction enhanced 對應(yīng)公式中的 $a$ ，即并行計算所占比例逃贝。Speedup enhanced 對應(yīng) $n$ 谣辞，即并行節(jié)點處理個數(shù)。

Speedup enhanced 為什么可以代替 $n$ 沐扳？

這里大家可能有一點疑問泥从，Speedup enhanced 明明是未加速前時間 / 加速后的時間，為什么就可以代表并行節(jié)點處理個數(shù)沪摄。在理論上躯嫉，單核處理器處理一個任務(wù)需要 100 秒，那么雙核處理它應(yīng)該需要 50 秒卓起。時間上它提速了 2 倍， cpu 個數(shù)上它也提升了 2 倍凹炸，故兩個可以替換戏阅。

$\begin{aligned} Speedup\ enhanced&=\frac{Old\ execution\ time}{New\ execution\ time} \\ &=\frac{100}{50}=2 \\ &=\frac{New\ cpu\ cores}{Old\ cpu\ cores} \\ &=\frac{2}{1}=2\\ \end{aligned}$

帶入后公示得：
$\begin{aligned} S&=\frac{Old\ total\ execution\ time}{New\ total\ execution\ time}\\ &=\frac{1}{{1-Fraction_{enhanced}}+Fraction_{enhanced}/Speedup_{enhanced}}\\ \end{aligned}$

3. 證明

$S$ 為我們所需要的結(jié)果，全局提速倍速
$Old\ total\ execution\ time$ （原來系統(tǒng)執(zhí)行總時間）為 $T$
$New\ total\ execution\ time$ （加速后系統(tǒng)執(zhí)行總時間）為 $T'$
系統(tǒng)中并行代碼塊（指能夠通過并行計算加速的代碼塊）原來執(zhí)行時間為 $t$
系統(tǒng)中并行代碼塊（指能夠通過并行計算加速的代碼塊）加速后執(zhí)行時間為 $t'$
系統(tǒng)中串行代碼塊（指不能通過并行計算加速的代碼塊）執(zhí)行時間為 $t_n$
$Fraction_{enhanced}$ 為 $f'$
$Speedup_{enhanced}$ 為 $s'$

$S=\frac{T}{T'}\\ T=t_n+t\\ T'=t_n+t'\\ f' = \frac{t}{T}=\frac{t}{t_n+t}\\ s'=\frac{t}{t'}\\ \frac{f'}{s'}=\frac{t}{t_n+t} \div \frac{t}{t'}=\frac{t'}{t_n+t}\\$

帶入公式得：
$\begin{aligned} S&=\frac{T}{T'}\\ &=\frac{t_n+t}{t_n+t'}\\ &=\frac{1}{(t_n+t')/(t_n+t)}\\ &=\frac{1}{1-\frac{t}{t_n+t}+\frac{t'}{t_n+t}}\\ &=\frac{1}{1-f'+\frac{f'}{s'}}\\ &=\frac{1}{{1-Fraction_{enhanced}}+Fraction_{enhanced}/Speedup_{enhanced}}\\ &=\frac{1}{1-a+\frac{a}{n}} \end{aligned}$
證明完畢啤它！

4. 總結(jié)

讓我們回到最初的公式
$S=\frac{1}{1-a+\frac{a}{n}}$
$a$ 為并行計算所占比例奕筐， $n$ 為并行節(jié)點處理個數(shù)舱痘。當(dāng) $a=0$ 時（即只有串行沒有并行），無論 $n$ 為多少离赫，加速比 $S$ 均為 1芭逝。當(dāng) $n \rightarrow +\infty$ ，當(dāng) cpu 核心數(shù)無限增多的時候渊胸，極限加速比 $S=1/(1-a)$ 旬盯。例如若并行代碼有 75%，極限加速比不能超出 4翎猛。

由此我們可知胖翰，在并行系統(tǒng)中一味的增加運算資源，并不能永遠(yuǎn)成倍的提升系統(tǒng)整體性能切厘。

5. 參考資料

阿姆達(dá)爾定律

Computer Organization | Amdahl’s law and its proof

理解性能提升By阿姆達(dá)爾定律(Amdahl's law)

最后編輯于：2020.03.08 18:35:45

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者