阿姆達(dá)爾定律可以用來(lái)計(jì)算處理器平行運(yùn)算之后效率提升的能力。阿姆達(dá)爾定律因 Gene Amdal 在 1967 年提出這個(gè)定律而得名。絕大多數(shù)使用并行或并發(fā)系統(tǒng)的開(kāi)發(fā)者有一種并發(fā)或并行可能會(huì)帶來(lái)提速的感覺(jué),甚至不知道阿姆達(dá)爾定律。不管怎樣,了解阿姆達(dá)爾定律還是有用的。
我會(huì)首先以算術(shù)的方式介紹阿姆達(dá)爾定律定律,然后再用圖表演示一下。
一個(gè)程序(或者一個(gè)算法)可以按照是否可以被并行化分為下面兩個(gè)部分:
假設(shè)一個(gè)程序處理磁盤(pán)上的文件。這個(gè)程序的一小部分用來(lái)掃描路徑和在內(nèi)存中創(chuàng)建文件目錄。做完這些后,每個(gè)文件交個(gè)一個(gè)單獨(dú)的線程去處理。掃描路徑和創(chuàng)建文件目錄的部分不可以被并行化,不過(guò)處理文件的過(guò)程可以。
程序串行(非并行)執(zhí)行的總時(shí)間我們記為 T。時(shí)間 T 包括不可以被并行和可以被并行部分的時(shí)間。不可以被并行的部分我們記為 B。那么可以被并行的部分就是 T-B。下面的列表總結(jié)了這些定義:
從上面可以得出:
T = B + (T – B)
首先,這個(gè)看起來(lái)可能有一點(diǎn)奇怪,程序的可并行部分在上面這個(gè)公式中并沒(méi)有自己的標(biāo)識(shí)。然而,由于這個(gè)公式中可并行可以用總時(shí)間 T 和 B(不可并行部分)表示出來(lái),這個(gè)公式實(shí)際上已經(jīng)從概念上得到了簡(jiǎn)化,也即是指以這種方式減少了變量的個(gè)數(shù)。
T- B 是可并行化的部分,以并行的方式執(zhí)行可以提高程序的運(yùn)行速度??梢蕴崴俣嗌偃Q于有多少線程或者多少個(gè) CPU 來(lái)執(zhí)行。線程或者 CPU 的個(gè)數(shù)我們記為 N??刹⑿谢糠直粓?zhí)行的最快時(shí)間可以通過(guò)下面的公式計(jì)算出來(lái):
(T – B ) / N
或者通過(guò)這種方式
(1 / N) * (T – B)
維基中使用的是第二種方式。
根據(jù)阿姆達(dá)爾定律,當(dāng)一個(gè)程序的可并行部分使用 N 個(gè)線程或 CPU 執(zhí)行時(shí),執(zhí)行的總時(shí)間為:
T(N) = B + ( T – B ) / N
T(N)指的是在并行因子為 N 時(shí)的總執(zhí)行時(shí)間。因此,T(1)就執(zhí)行在并行因子為 1 時(shí)程序的總執(zhí)行時(shí)間。使用 T(1)代替 T,阿姆達(dá)爾定律定律看起來(lái)像這樣:
T(N) = B + (T(1) – B) / N
表達(dá)的意思都是是一樣的。
為了更好的理解阿姆達(dá)爾定律,讓我們來(lái)看一個(gè)計(jì)算的例子。執(zhí)行一個(gè)程序的總時(shí)間設(shè)為 1。程序的不可并行化占 40%,按總時(shí)間 1 計(jì)算,就是 0.4,可并行部分就是 1–0.4=0.6.
在并行因子為 2 的情況下,程序的執(zhí)行時(shí)間將會(huì)是:
T(2) = 0.4 + ( 1 - 0.4 ) / 2
= 0.4 + 0.6 / 2
= 0.4 + 0.3
= 0.7
在并行因子為 5 的情況下,程序的執(zhí)行時(shí)間將會(huì)是:
T(5) = 0.4 + ( 1 - 0.4 ) / 5
= 0.4 + 0.6 / 6
= 0.4 + 0.12
= 0.52
阿姆達(dá)爾定律圖示
為了更好地理解阿姆達(dá)爾定律,我會(huì)嘗試演示這個(gè)定定律是如何誕生的。
首先,一個(gè)程序可以被分割為兩部分,一部分為不可并行部分 B,一部分為可并行部分 1–B。如下圖:
http://wiki.jikexueyuan.com/project/java-concurrent/images/24.png" alt="" />
在頂部被帶有分割線的那條直線代表總時(shí)間 T(1)。
下面你可以看到在并行因子為 2 的情況下的執(zhí)行時(shí)間:
http://wiki.jikexueyuan.com/project/java-concurrent/images/25.png" alt="" />
并行因子為 3 的情況:
http://wiki.jikexueyuan.com/project/java-concurrent/images/26.png" alt="" />
從阿姆達(dá)爾定律可以看出,程序的可并行化部分可以通過(guò)使用更多的硬件(更多的線程或 CPU)運(yùn)行更快。對(duì)于不可并行化的部分,只能通過(guò)優(yōu)化代碼來(lái)達(dá)到提速的目的。因此,你可以通過(guò)優(yōu)化不可并行化部分來(lái)提高你的程序的運(yùn)行速度和并行能力。你可以對(duì)不可并行化在算法上做一點(diǎn)改動(dòng),如果有可能,你也可以把一些移到可并行化放的部分。
如果你優(yōu)化一個(gè)程序的串行化部分,你也可以使用阿姆達(dá)爾定律來(lái)計(jì)算程序優(yōu)化后的執(zhí)行時(shí)間。如果不可并行部分通過(guò)一個(gè)因子 O 來(lái)優(yōu)化,那么阿姆達(dá)爾定律看起來(lái)就像這樣:
T(O, N) = B / O + (1 - B / O) / N
記住,現(xiàn)在程序的不可并行化部分占了 B / O 的時(shí)間,所以,可并行化部分就占了 1 - B / O 的時(shí)間。
如果 B 為 0.1,O 為 2,N 為 5,計(jì)算看起來(lái)就像這樣:
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
到目前為止,我們只用阿姆達(dá)爾定律計(jì)算了一個(gè)程序或算法在優(yōu)化后或者并行化后的執(zhí)行時(shí)間。我們也可以使用阿姆達(dá)爾定律計(jì)算加速比(speedup),也就是經(jīng)過(guò)優(yōu)化后或者串行化后的程序或算法比原來(lái)快了多少。
如果舊版本的程序或算法的執(zhí)行時(shí)間為 T,那么增速比就是:
Speedup = T / T(O , N);
為了計(jì)算執(zhí)行時(shí)間,我們常常把 T 設(shè)為 1,加速比為原來(lái)時(shí)間的一個(gè)分?jǐn)?shù)。公式大致像下面這樣:
Speedup = 1 / T(O,N)
如果我們使用阿姆達(dá)爾定律來(lái)代替 T(O,N),我們可以得到下面的公式:
Speedup = 1 / ( B / O + (1 - B / O) / N)
如果 B = 0.4, O = 2, N = 5, 計(jì)算變成下面這樣:
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 ...
上面的計(jì)算結(jié)果可以看出,如果你通過(guò)一個(gè)因子 2 來(lái)優(yōu)化不可并行化部分,一個(gè)因子 5 來(lái)并行化可并行化部分,這個(gè)程序或算法的最新優(yōu)化版本最多可以比原來(lái)的版本快 2.77777 倍。
雖然阿姆達(dá)爾定律允許你并行化一個(gè)算法的理論加速比,但是不要過(guò)度依賴這樣的計(jì)算。在實(shí)際場(chǎng)景中,當(dāng)你優(yōu)化或并行化一個(gè)算法時(shí),可以有很多的因子可以被考慮進(jìn)來(lái)。
內(nèi)存的速度,CPU 緩存,磁盤(pán),網(wǎng)卡等可能都是一個(gè)限制因子。如果一個(gè)算法的最新版本是并行化的,但是導(dǎo)致了大量的 CPU 緩存浪費(fèi),你可能不會(huì)再使用 xN 個(gè) CPU 來(lái)獲得 xN 的期望加速。如果你的內(nèi)存總線(memory bus),磁盤(pán),網(wǎng)卡或者網(wǎng)絡(luò)連接都處于高負(fù)載狀態(tài),也是一樣的情況。
我們的建議是,使用阿姆達(dá)爾定律定律來(lái)指導(dǎo)我們優(yōu)化程序,而不是用來(lái)測(cè)量?jī)?yōu)化帶來(lái)的實(shí)際加速比。記住,有時(shí)候一個(gè)高度串行化的算法勝過(guò)一個(gè)并行化的算法,因?yàn)榇谢姹静恍枰M(jìn)行協(xié)調(diào)管理(上下文切換),而且一個(gè)單個(gè)的 CPU 在底層硬件工作(CPU 管道、CPU 緩存等)上的一致性可能更好。