一区二区日嗨,老司机一区二,亚州激情久久久久

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

1. 介紹

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

2. 前置說明

2.1 Fraction enhanced

Fraction enhanced 顧名思義是部分提高。例如我的程序總共有 100 行代碼，其中 50 行是可以通過并行計(jì)算的，那么這 50 行代碼就是 Fraction enhanced 。但是實(shí)際上 Fraction enhanced 是一個(gè)比例數(shù)值，是并行計(jì)算代碼 / 總代碼量。
$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 等于 原有運(yùn)行時(shí)間 / 并行計(jì)算加速后的時(shí)間 。例如系統(tǒng)原來串行計(jì)算需要 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$ ，即并行計(jì)算所占比例。Speedup enhanced 對應(yīng) $n$ ，即并行節(jié)點(diǎn)處理個(gè)數(shù)。

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

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

$\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í)行總時(shí)間）為 $T$
$New\ total\ execution\ time$ （加速后系統(tǒng)執(zhí)行總時(shí)間）為 $T'$
系統(tǒng)中并行代碼塊（指能夠通過并行計(jì)算加速的代碼塊）原來執(zhí)行時(shí)間為 $t$
系統(tǒng)中并行代碼塊（指能夠通過并行計(jì)算加速的代碼塊）加速后執(zhí)行時(shí)間為 $t'$
系統(tǒng)中串行代碼塊（指不能通過并行計(jì)算加速的代碼塊）執(zhí)行時(shí)間為 $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$ 為并行計(jì)算所占比例， $n$ 為并行節(jié)點(diǎn)處理個(gè)數(shù)。當(dāng) $a=0$ 時(shí)（即只有串行沒有并行），無論 $n$ 為多少，加速比 $S$ 均為 1。當(dāng) $n \rightarrow +\infty$ ，當(dāng) cpu 核心數(shù)無限增多的時(shí)候，極限加速比 $S=1/(1-a)$ 。例如若并行代碼有 75%，極限加速比不能超出 4。