阿姆達爾定律與古斯塔夫森定律的差異:前提、公式、擴展性、範例比較

兩者都是估算增加處理器時能加速多少的定律,但前提不同。阿姆達爾定律固定問題規模,考慮如何更快完成相同的工作,因此無法平行化的部分決定了加速的上限。古斯塔夫森定律固定執行時間,考慮隨著處理器增加而解更大的問題,因此加速幾乎與處理器數量成正比地增加。兩者並不矛盾,而是在回答不同的問題。

項目阿姆達爾定律古斯塔夫森定律
固定的項目問題規模(總工作量)執行時間(每個處理器的工作量)
問題相同的問題能解得多快在相同的時間內能解多大的問題
公式(N 為處理器數)S = 1 / ((1 − p) + p / N)S = s + (1 − s) × N = N − s × (N − 1)
比例的量測方式p 是在 1 個處理器上執行時,可平行化部分所佔的時間比例s 是在 N 個處理器上平行執行時,循序部分所佔的時間比例
增加 N 時在 1 / (1 − p) 達到上限幾乎與 N 成正比地持續增加
計算範例若 p = 0.95,N = 100 時約 17 倍,即使 N 為無限大,上限也是 20 倍若 s = 0.05,N = 100 時約 95 倍
對應的擴展方式強擴展(strong scaling)弱擴展(weak scaling)
呈現的觀點悲觀。少量的循序部分決定上限樂觀。只要擴大問題,平行化就有回報
適用的例子想快速處理固定大小的輸入時。例如處理 1 張影像、互動式回應等網格更細的模擬,或想在相同時間內處理更大的資料或模型時
兩者都未納入的因素通訊與同步的額外負擔、負載不均、記憶體頻寬不足通訊與同步的額外負擔、負載不均、記憶體頻寬不足

數值為具代表性的大致參考值,會因世代或產品而異。

適用於什麼情況

阿姆達爾定律
問題規模固定,想縮短回應時間時。用來估算平行化的上限,並判斷是否應減少循序部分。
古斯塔夫森定律
能隨處理器增加而擴大問題時。用來估算在大規模模擬或資料處理中,解得更細、更大的價值。
評估結果的呈現
報告平行效能時,應註明是以強擴展還是弱擴展量測。條件不同時,即使是同一個程式,加速比也會有很大差異。

常見問題

這兩個定律不矛盾嗎?

不矛盾。阿姆達爾定律固定問題規模,古斯塔夫森定律固定執行時間,因此回答的是不同的問題。此外,循序部分的比例在阿姆達爾定律中以 1 個處理器執行時的時間量測,在古斯塔夫森定律中則以 N 個處理器執行時的時間量測,因此不能代入相同的數值來比較。

明明有 90% 可以平行化,為什麼最多只能加速 10 倍?

因為剩下的 10% 無論增加多少處理器都不會縮短。即使平行部分的時間趨近於零,整體時間也不會短於原本的 10%,因此加速在 1 / 0.1 = 10 倍達到上限。

為什麼實際的加速比這些定律的預測小?

因為兩個定律都沒有納入處理器之間的通訊與同步、負載不均、共用記憶體頻寬不足等因素。處理器越多,這些影響越大,平行效率隨之下降。

我的程式應該套用哪一個定律?

如果輸入大小固定,想更快得到結果,就是阿姆達爾定律。如果處理器增加後想處理更細的網格或更大的資料,就是古斯塔夫森定律。即使是同一個程式,適用的定律也會因使用方式而改變。

理解度檢測

對於整體處理中有 90% 可以平行化的程式,在無限增加處理器數量來執行時,理論上的最大加速比為何?

  1. A10 倍
  2. B90 倍
  3. C無限大
查看答案與解析

正確答案:A. 10 倍

依據阿姆達爾定律(Amdahl's law),設可平行化的比例為 p、處理器數為 N,加速比為 1/((1 − p) + p/N)。當 p = 0.9 時,即使 N 趨近無限大,上限也是 1/0.1 = 10 倍,N = 10 時也只有約 5.3 倍。即使無法平行化的部分再小也會決定上限,因此減少循序部分很重要。而擴大問題規模以增加平行部分的想法,則是古斯塔夫森定律(Gustafson's law)。

從阿姆達爾定律可得到的、關於效能改善作法的啟示,下列何者最適當?

  1. A優先加速花費大量時間的部分(常見情況)
  2. B先加速很少被執行的部分
  3. C無論加速哪個部分,對整體的效果都相同
查看答案與解析

正確答案:A. 優先加速花費大量時間的部分(常見情況)

即使把只占整體1%的部分加速到無限快,整體也只會變快約1%。相對地,若將占80%的部分加快2倍,整體約為1.7倍。因此基本作法是先用剖析器(profiler)等找出花費大量時間的部分,再從那裡開始改善。「加速常見情況」是電腦設計中也反覆使用的原則。

  1. 古斯塔夫森定律(Gustafson's law)所表達的想法,下列何者正確?
  2. 在平行計算的評估中,所謂「強擴展(strong scaling)」與「弱擴展(weak scaling)」的差異,下列何者正確?
  3. 表示效能改善程度的「加速比(speedup)」,其求法下列何者正確?

前往效能評估與效能剖析的練習題

相關名詞的解說

阿姆達爾定律
只將程式的一部分平行化時,整體的加速受限於無法平行化的部分的定律。例如即使將 90% 平行化,最多也只能加速到 10 倍。
古斯塔夫森定律(Gustafson's law)
增加處理器數量時,若所處理的問題也隨之變大,可平行化部分的比例就會增加,而得到與處理器數量大致成正比的效果的想法。
強擴展性(Strong scaling)
固定問題大小並增加處理器,觀察時間能縮短多少的平行效能評估。
弱擴展性(Weak scaling)
固定每個處理器的問題大小並擴大整體,觀察時間是否維持固定的平行效能評估。
平行效率(Parallel efficiency)
以處理器數量除平行化所得加速比所得的值。表示核心被有效使用的程度。

相關的比較