芯耀
343
前言
在上一篇文章《受用一生的定理：阿姆達(dá)爾定律》中提到的阿姆達(dá)爾定律前提是假設(shè)問題的規(guī)模保持不變，并且給定一臺(tái)速度更快的機(jī)器，目標(biāo)是更快地解決問題。然而，在大多數(shù)情況下，這并不完全正確。當(dāng)有一臺(tái)更快的機(jī)器時(shí)，我們可能會(huì)希望增加解決問題的規(guī)?；蛱岣呓鉀Q方案的準(zhǔn)確性。
古斯塔夫森定律（Gustafson's Law），又稱古斯塔夫森-巴西斯定律（Gustafson-Barsis's Law），是并行計(jì)算領(lǐng)域的一項(xiàng)原理，旨在解決并行系統(tǒng)的可擴(kuò)展性問題。該定律由約翰·L·古斯塔夫森（John L. Gustafson）及其同事埃德溫·H·巴西斯（Edwin H. Barsis）于1988年提出，旨在回應(yīng)阿姆達(dá)爾定律（Amdahl's Law）。阿姆達(dá)爾定律對(duì)并行處理所能實(shí)現(xiàn)的性能提升持較為悲觀的態(tài)度。
古斯塔夫森定律指出，通過增加問題規(guī)?？梢燥@著提高并行處理的速度。換句話說，該定律表明，隨著處理器數(shù)量的增加，總體計(jì)算工作量可以按比例增加，以保持恒定的效率。這與阿姆達(dá)爾定律形成了對(duì)比，后者側(cè)重于固定規(guī)模的問題，并強(qiáng)調(diào)計(jì)算順序部分的重要性，這限制了可實(shí)現(xiàn)的最大加速比。
在古斯塔弗森定律中，保持常數(shù)的不是問題的規(guī)模，而是我們等待結(jié)果的時(shí)間。古斯塔夫森觀察到，問題的并行部分會(huì)隨著問題規(guī)模的變化而變化，而順序部分則幾乎不會(huì)。
1. 古斯塔夫森定律
古斯塔夫森估計(jì)加速比S使用并行計(jì)算得到的公式如下：
S = s + p x N = s + (1-s) x N = N + (1-N) x s
其中，大寫S是并行化的理論加速比，N是處理器的數(shù)量，小寫s和p分別是在并行系統(tǒng)上執(zhí)行程序的串行部分和并行部分所花費(fèi)的時(shí)間比例，其中s+p=1。因此，S也可以用p表示為：
S = s + p x N = (1-p) + p x N = 1 + (N-1) x p
2. 古斯塔夫森定律的應(yīng)用
假設(shè)我們有一個(gè)70% 并行、30% 順序的程序，并且我們有10 個(gè)處理器，那么按古斯塔弗森定理得到的加速比為：
S = N + (1 - N) x s = 10 + (1 – 10) x 0.3 = 7.3
那假如上面程序有1000個(gè)處理器呢？
S = N + (1 - N) x s = 1000 + (1 – 1000) x 0.3 = 700.3
可見隨著處理器個(gè)數(shù)的增加，加速比得到明顯的提升。
如果我們使用阿姆達(dá)爾定律估計(jì)，速度的增加將從 2.7 增加到 3.3。
3. 古斯塔夫森定律的局限性
對(duì)于許多軟件程序來說，可以對(duì)串行執(zhí)行的時(shí)間進(jìn)行檢測和量化。這可以通過在程序的串行部分周圍放置計(jì)時(shí)器來估算s來實(shí)現(xiàn)。
基于此分?jǐn)?shù)，可以使用阿姆達(dá)爾定律和古斯塔夫森定律來估算加速比。然而，這兩個(gè)定律都沒有考慮通信成本或中間級(jí)別的并行性。隨著處理器數(shù)量的增加，古斯塔夫森定律所實(shí)現(xiàn)的加速仍然有限，因?yàn)橥ㄐ懦杀咀罱K會(huì)變得如此之高，以至于抵消了增加工作負(fù)載所帶來的任何好處。
事實(shí)上，當(dāng)應(yīng)用于現(xiàn)代并行系統(tǒng)時(shí)，這兩條定律可能并不準(zhǔn)確，因?yàn)橥ㄐ懦杀緦?duì)加速有很大的影響。
4. 總結(jié)
阿姆達(dá)爾定律是保持規(guī)模不變談加速比，古斯塔夫森定律是保持時(shí)間長度不變談加速比。阿姆達(dá)爾定律是悲觀的，而古斯塔夫森定律則是樂觀的。從阿姆達(dá)爾定律的角度來看待并行性可能會(huì)令人沮喪。古斯塔夫森證明，當(dāng)我們增加并行部分的工作量時(shí)，順序部分造成的瓶頸會(huì)變得不那么嚴(yán)重。
古斯塔弗森定理強(qiáng)調(diào)了可拓展性在并行處理中的重要性，它關(guān)注并行部分以及如何擴(kuò)展它以實(shí)現(xiàn)更好的性能，這一點(diǎn)與強(qiáng)調(diào)計(jì)算順序部分對(duì)性能影響的阿姆達(dá)爾定律不同。古斯塔夫森定律更適用于現(xiàn)實(shí)世界的問題，因?yàn)樵S多計(jì)算任務(wù)自然會(huì)隨著數(shù)據(jù)的大小或所解決問題的復(fù)雜性而擴(kuò)展。
