理解Amdahl定律

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

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

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

在這個公式中

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

n就是可用的執(zhí)行單元的數(shù)目（處理器或者物理核心）。

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

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

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

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

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

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

圖 1-9

圖 1-10

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

考慮Gustafson定律

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

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

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

S代表串行順序執(zhí)行的工作單元。

P代表可以完全并行執(zhí)行的工作單元的數(shù)目。

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

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

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

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

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

圖 1-11

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

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

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