理解Amdahl定律

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

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

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

在這個(gè)公式中

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

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

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

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

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

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

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

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

圖 1-9

圖 1-10

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

考慮Gustafson定律

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

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

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

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

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

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

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

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

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

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

圖 1-11

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

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