阿姆達爾定律

阿姆達爾定律可以用來計算處理器平行運算之后效率提升的能力。阿姆達爾定律因Gene Amdal 在1967年提出這個定律而得名。絕大多數使用并行或并發系統的開發者有一種并發或并行可能會帶來提速的感覺，甚至不知道阿姆達爾定律。不管怎樣，了解阿姆達爾定律還是有用的。

我會首先以算術的方式介紹阿姆達爾定律定律，然后再用圖表演示一下。

阿姆達爾定律定義

一個程序（或者一個算法）可以按照是否可以被并行化分為下面兩個部分：

可以被并行化的部分

不可以被并行化的部分

假設一個程序處理磁盤上的文件。這個程序的一小部分用來掃描路徑和在內存中創建文件目錄。做完這些后，每個文件交個一個單獨的線程去處理。掃描路徑和創建文件目錄的部分不可以被并行化，不過處理文件的過程可以。

程序串行（非并行）執行的總時間我們記為T。時間T包括不可以被并行和可以被并行部分的時間。不可以被并行的部分我們記為B。那么可以被并行的部分就是T-B。下面的列表總結了這些定義：

T = 串行執行的總時間

B = 不可以并行的總時間

T- B = 并行部分的總時間

從上面可以得出：

T = B + (T – B)

首先，這個看起來可能有一點奇怪，程序的可并行部分在上面這個公式中并沒有自己的標識。然而，由于這個公式中可并行可以用總時間T 和 B（不可并行部分）表示出來，這個公式實際上已經從概念上得到了簡化，也即是指以這種方式減少了變量的個數。

T- B 是可并行化的部分，以并行的方式執行可以提高程序的運行速度。可以提速多少取決于有多少線程或者多少個CPU來執行。線程或者CPU的個數我們記為N。可并行化部分被執行的最快時間可以通過下面的公式計算出來：

(T – B ) / N

或者通過這種方式

(1 / N) * (T – B)

維基中使用的是第二種方式。

根據阿姆達爾定律，當一個程序的可并行部分使用N個線程或CPU執行時，執行的總時間為：

T(N) = B + ( T – B ) / N

T(N)指的是在并行因子為N時的總執行時間。因此，T(1)就執行在并行因子為1時程序的總執行時間。使用T(1)代替T，阿姆達爾定律定律看起來像這樣：

T(N) = B + (T(1) – B) / N

表達的意思都是是一樣的。

一個計算例子

為了更好的理解阿姆達爾定律，讓我們來看一個計算的例子。執行一個程序的總時間設為1.程序的不可并行化占40%，按總時間1計算，就是0.4.可并行部分就是1 – 0.4 = 0.6.

在并行因子為2的情況下，程序的執行時間將會是：

T(2) = 0.4 + ( 1 - 0.4 ) / 2 = 0.4 + 0.6 / 2 = 0.4 + 0.3 = 0.7

在并行因子為5的情況下，程序的執行時間將會是：

T(5) = 0.4 + ( 1 - 0.4 ) / 5 = 0.4 + 0.6 / 6 = 0.4 + 0.12 = 0.52

優化算法

從阿姆達爾定律可以看出，程序的可并行化部分可以通過使用更多的硬件（更多的線程或CPU）運行更快。對于不可并行化的部分，只能通過優化代碼來達到提速的目的。因此，你可以通過優化不可并行化部分來提高你的程序的運行速度和并行能力。你可以對不可并行化在算法上做一點改動，如果有可能，你也可以把一些移到可并行化放的部分。

如果你優化一個程序的串行化部分，你也可以使用阿姆達爾定律來計算程序優化后的執行時間。如果不可并行部分通過一個因子O來優化，那么阿姆達爾定律看起來就像這樣：

T(O, N) = B / O + (1 - B / O) / N

記住，現在程序的不可并行化部分占了B / O的時間，所以，可并行化部分就占了1 - B / O的時間.

如果B為0.1，O為2，N為5，計算看起來就像這樣：

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

運行時間 vs. 加速

到目前為止，我們只用阿姆達爾定律計算了一個程序或算法在優化后或者并行化后的執行時間。我們也可以使用阿姆達爾定律計算加速比（speedup），也就是經過優化后或者串行化后的程序或算法比原來快了多少。

如果舊版本的程序或算法的執行時間為T，那么增速比就是：

Speedup = T / T(O , N);

為了計算執行時間，我們常常把T設為1，加速比為原來時間的一個分數。公式大致像下面這樣：

Speedup = 1 / T（O,N)

如果我們使用阿姆達爾定律來代替T(O,N)，我們可以得到下面的公式：

Speedup = 1 / ( B / O + (1 - B / O) / N)

如果B = 0.4， O = 2， N = 5， 計算變成下面這樣：

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 ...

上面的計算結果可以看出，如果你通過一個因子2來優化不可并行化部分，一個因子5來并行化可并行化部分，這個程序或算法的最新優化版本最多可以比原來的版本快2.77777倍。

測量，不要僅是計算

雖然阿姆達爾定律允許你并行化一個算法的理論加速比，但是不要過度依賴這樣的計算。在實際場景中，當你優化或并行化一個算法時，可以有很多的因子可以被考慮進來。

內存的速度，CPU緩存，磁盤，網卡等可能都是一個限制因子。如果一個算法的最新版本是并行化的，但是導致了大量的CPU緩存浪費，你可能不會再使用x N個CPU來獲得x N的期望加速。如果你的內存總線（memory bus），磁盤，網卡或者網絡連接都處于高負載狀態，也是一樣的情況。

我們的建議是，使用阿姆達爾定律定律來指導我們優化程序，而不是用來測量優化帶來的實際加速比。記住，有時候一個高度串行化的算法勝過一個并行化的算法，因為串行化版本不需要進行協調管理（上下文切換），而且一個單個的CPU在底層硬件工作（CPU管道、CPU緩存等）上的一致性可能更好。

任務調度

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。