前言

在上一篇文章《使用阿姆達爾定律來提升效率》中提到的阿姆達爾定律前提是假設問題的規模保持不變，并且給定一臺速度更快的機器，目標是更快地解決問題。然而，在大多數情況下，這并不完全正確。當有一臺更快的機器時，我們可能會希望增加解決問題的規模或提高解決方案的準確性。

古斯塔夫森定律（Gustafson's Law），又稱古斯塔夫森-巴西斯定律（Gustafson-Barsis's Law），是并行計算領域的一項原理，旨在解決并行系統的可擴展性問題。該定律由約翰·L·古斯塔夫森（John L. Gustafson）及其同事埃德溫·H·巴西斯（Edwin H. Barsis）于1988年提出，旨在回應阿姆達爾定律（Amdahl's Law）。阿姆達爾定律對并行處理所能實現的性能提升持較為悲觀的態度。

古斯塔夫森定律指出，通過增加問題規模可以顯著提高并行處理的速度。換句話說，該定律表明，隨著處理器數量的增加，總體計算工作量可以按比例增加，以保持恒定的效率。這與阿姆達爾定律形成了對比，后者側重于固定規模的問題，并強調計算順序部分的重要性，這限制了可實現的最大加速比。

在古斯塔弗森定律中，保持常數的不是問題的規模，而是我們等待結果的時間。古斯塔夫森觀察到，問題的并行部分會隨著問題規模的變化而變化，而順序部分則幾乎不會。

1. 古斯塔夫森定律

古斯塔夫森估計加速比S使用并行計算得到的公式如下：

S = s + p x N = s + (1-s) x N = N + (1-N) x s

其中，大寫S是并行化的理論加速比，N是處理器的數量，小寫s和p分別是在并行系統上執行程序的串行部分和并行部分所花費的時間比例，其中s+p=1。因此，S也可以用p表示為：

S = s + p x N = (1-p) + p x N = 1 + (N-1) x p

2. 古斯塔夫森定律的應用

假設我們有一個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

可見隨著處理器個數的增加，加速比得到明顯的提升。

如果我們使用阿姆達爾定律估計，速度的增加將從 2.7 增加到 3.3。

3. 古斯塔夫森定律的局限性

對于許多軟件程序來說，可以對串行執行的時間進行檢測和量化。這可以通過在程序的串行部分周圍放置計時器來估算s來實現。

基于此分數，可以使用阿姆達爾定律和古斯塔夫森定律來估算加速比。然而，這兩個定律都沒有考慮通信成本或中間級別的并行性。隨著處理器數量的增加，古斯塔夫森定律所實現的加速仍然有限，因為通信成本最終會變得如此之高，以至于抵消了增加工作負載所帶來的任何好處。

事實上，當應用于現代并行系統時，這兩條定律可能并不準確，因為通信成本對加速有很大的影響。

4. 總結

阿姆達爾定律是保持規模不變談加速比，古斯塔夫森定律是保持時間長度不變談加速比。阿姆達爾定律是悲觀的，而古斯塔夫森定律則是樂觀的。從阿姆達爾定律的角度來看待并行性可能會令人沮喪。古斯塔夫森證明，當我們增加并行部分的工作量時，順序部分造成的瓶頸會變得不那么嚴重。

古斯塔弗森定理強調了可拓展性在并行處理中的重要性，它關注并行部分以及如何擴展它以實現更好的性能，這一點與強調計算順序部分對性能影響的阿姆達爾定律不同。古斯塔夫森定律更適用于現實世界的問題，因為許多計算任務自然會隨著數據的大小或所解決問題的復雜性而擴展。