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