理解Amdahl定律

如果你想利用多核的優勢在盡可能少的時間運行盡可能多的指令，那么就需要以并行的序列分離代碼。然而，大多的算法需要運行一些串行代碼來調整并行執行。例如，并行執行很多代碼塊，最后收集他們執行的結果。那些分解并行執行工作復雜和收集執行結果的代碼是串行代碼，它是不能利用并行的優勢的。如果你的算法中有很多這樣的代碼片段，那么串行代碼所占的比例就會增加，并且能夠獲取到的性能收益就會減少。

Gene Amdahl是一個著名計算機架構師，當一個系統中僅有少量的計算機改善硬件的時候，那么能夠獲得最大的性能改善是多少呢？他做了大量與這方面有關的觀察研究。他使用這些觀察結果定義了Amdable’s Law，它是由一個預測使用多核處理器在理論上可以獲得最大性能改善的公式組成。它也使用于那些運行在多核處理器上的并發算法。

Maximum speedup（in times） = 1/((1-p) + p/n)

在這個公式中

P就是代碼中可以完全并行執行的部分。

n就是可用的執行單元的數目（處理器或者物理核心）。

根據這個公式，如果你有一個僅有50%（P = 0.5）的工作需要并行執行的算法，那么在雙核微處理器可以獲得的最大速度是1.33倍。圖1-8闡述了一個擁有1000個工作單元的算法分解成500個串行工作的單元和500個并行工作的單元。如果串行算法的執行完成需要1000秒，那么這個有部分并行代碼的新版本的執行時間不會少于750秒。

Maximum speedup (in times) = 1 / ((1 - 0.50) + (0.50 / 2)) = 1.33x

圖 1-8同樣的算法在八核微處理器上最大速度也不會超過1.77倍。因此，這些物理核心將使執行代碼的時間不會少于562.5秒。

Maximum speedup (in times) = 1 / ((1 - 0.50) + (0.50 / 8)) = 1.77x

圖 1-9 展示了同一算法在擁有不同數目（1-16）物理核心的微處理器上的最大速度。正如你所看到的，執行的速度并不是一條直線，隨著內核數目的增多會浪費一些處理能力。圖1-10展示了執行一個有90%代碼可以并行執行的相同算法的相同信息。事實上，90%的并行是一個大的優勢，但是帶有16個核心的微處理器僅僅提速6.4倍。

Maximum speedup (in times) = 1 / ((1 - 0.90) + (0.90 / 16)) = 6.40x

圖 1-9

圖 1-10

Amdabl定律考慮了物理核心數量的改變，但是并沒有考慮到你可以向現有應用程序添加潛在的新特性來利用額外的并發處理能力。例如，當你在多余三個核心的處理器上運行其他并不能大大改善性能的算法，你可以創建新的算法利用這些額外的內核。你可以創建考慮了不同并發場景的設計來減少Amdabl定律的影響。程序也必須考慮進像硬件所提供的的新的能力。

考慮Gustafson定律

John Gustafson注意到amdahl定律將算法視為固定不變的，但是考慮了運行他們的硬件。因此，他在1988年對這個定律進行了重新的定義。他認為速度的測量應該以相對處理器的數目的問題的規模計算，而不是任務問題是固定的大小。當硬件提供的并發處理能力增強時，問題的負載就會縮小變化。

Gustafson定律提供了一下的公式，它關注問題的大小來測量可以在固定時間內完成的工作單元的數目：

Total work (in units) = S + (N × P)

S代表串行順序執行的工作單元。

P代表可以完全并行執行的工作單元的數目。

N代表可用的處理器或者物理核心的數目。

你可以想象一個問題是有50個串行執行的工作單元組成。這個工作也可以調度每個可用核心并行執行50個工作單元。如果你有一個雙核的處理器，最大的工作單元的數目將是150個單元。

Total work (in units) = 50 + (2 × 50) = 150 units of work

圖1-11闡釋了一個擁有50個串行執行工作單元的算法和一個并行執行部分。并行部分的測量是根據物理核心的數目計算的。以這種方式，并行部分能夠處理并發的50個工作單元。并行部分的負載會隨著可用核心的數目增加。如果并行部分能夠提供額外的工作單元，這種算法就能夠在盡可能少的時間里產生更多的數據。相同的算法可以運行在一個帶有八個物理核心的微處理器上。在這種場景中，那么使用與前邊例子相同的時間能夠處理450個工作單元。

Total work (in units) = 50 + (8 × 50) = 450 units of work

圖 1-11

圖1-12展示了同一個算法的速度隨著物理核心（1-16）的數目的變化。這個速度是在增加核心數目的時候提供了足夠的并行執行的工作單元的。你可以看到，這個速度要不運用amdahl定律的結果要好的多。圖1-13展示了根據可用的物理核心的數目（1-32）需要的工作單元的總數。

圖1-14展示了很多算法組成了串行執行和并發執行部分的一些工作單元。并行部分已可用內核的增加作為標準計量。當并行部分執行更多工作單元時，此時串行執行部分的影響也會減小。在這種情況下，有必要計算并行和串行執行的總單元數目，然后將他們應用到給定的公式來計算在八核處理器中所有的工作任務。

Total sequential work (in units) = 25 + 150 + 100 + 150 = 425 units of work

Total parallel unit of work (in units) = 50 + 200 + 300 = 550 units of work

Total work (in units) = 425 + (8 × 550) = 4,825 units of work

圖 1-12

圖 1-13

圖 1-14

原文鏈接：http://www.cnblogs.com/wufengtinghai/archive/2012/06/04/2533551.html