1.2.1 使用阿姆達(dá)爾定律

接下來(lái)，我們介紹阿姆達(dá)爾定律。阿姆達(dá)爾定律實(shí)際上就是一個(gè)簡(jiǎn)單的數(shù)字公式，用于估計(jì)將串行程序的某些代碼放到多個(gè)處理器上并行執(zhí)行時(shí)可能帶來(lái)的潛在速度增益。為了便于理解，我們沿用建造房子的例子來(lái)介紹該定律。

在前面的例子中，整個(gè)工期僅與房子的實(shí)際物理建造過(guò)程有關(guān)，但現(xiàn)在，我們把設(shè)計(jì)房子的時(shí)間也考慮進(jìn)來(lái)。假設(shè)世界上只有一個(gè)人有能力設(shè)計(jì)你的房子——這個(gè)人就是你，并且設(shè)計(jì)房屋需要100小時(shí)。地球上沒(méi)有人能與你的設(shè)計(jì)才華相提并論，所以這部分任務(wù)根本不可能由其他建筑師來(lái)分擔(dān)——也就是說(shuō)，不管你有什么樣的資源，無(wú)論你能聘請(qǐng)多少人，設(shè)計(jì)這所房子都需要100小時(shí)。所以，如果你只聘請(qǐng)1個(gè)工人，建造這座房子所需要的全部時(shí)間就是200小時(shí)——你設(shè)計(jì)房子需要100小時(shí)，1個(gè)工人建造房子需要100小時(shí)。如果你聘請(qǐng)2個(gè)工人，則需要150小時(shí)——設(shè)計(jì)房子的時(shí)間仍然是100小時(shí)，而建造房子僅需要50小時(shí)。顯然，建造房子的總時(shí)間的計(jì)算公式為100+100/N，其中N是聘請(qǐng)的工人數(shù)量。

現(xiàn)在回過(guò)頭來(lái)想想，如果我們聘請(qǐng)1個(gè)工人，建造房子需要多長(zhǎng)時(shí)間——它最終決定了聘請(qǐng)更多工人時(shí)的加速比，也就是說(shuō)，這個(gè)過(guò)程變快了多少倍。如果我們聘請(qǐng) 1名工人，就會(huì)發(fā)現(xiàn)設(shè)計(jì)和建造房子所需的時(shí)間是相同的，即100小時(shí)。所以，我們可以說(shuō)，設(shè)計(jì)房子的時(shí)間占比是0.5（50%），建造房子的時(shí)間占比是0.5（50%）——當(dāng)然，這兩個(gè)部分加起來(lái)是1，也就是100%。當(dāng)增加工人時(shí)，我們希望對(duì)此進(jìn)行比較——如果我們有2個(gè)工人，建造房子時(shí)間將減少一半。所以，與初始串行版本相比，這將花費(fèi)原時(shí)間的0.5 + 0.5 / 2 = 0.75（75%），而0.75×200為150小時(shí)。我們可以看到，聘請(qǐng)更多工人的方法是行之有效的。此外，如果聘請(qǐng)N個(gè)工人，我們可以計(jì)算出N個(gè)工人并行施工所需時(shí)間占原時(shí)間的比例，具體計(jì)算公式為0.5 + 0.5/N。

現(xiàn)在，讓我們確定通過(guò)增加工人而獲得的加速比。如果我們有2個(gè)工人，建造一所房子需要原時(shí)間的75%，那么可以用0.75的倒數(shù)來(lái)確定并行化的加速比——也就是說(shuō)，加速比將是1/0.75，比只有1個(gè)工人時(shí)的速度約快1.33倍。在這種情況下，如果我們聘請(qǐng)N個(gè)工人，加速比將變?yōu)?/(0.5+0.5 /N)。

隨著聘請(qǐng)更多的工人（N更大），0.5/N將接近于0，所以當(dāng)并行化這個(gè)任務(wù)時(shí)，加速比是有一個(gè)上限的，即1/(0.5+0)=2。我們可以用估計(jì)的最大加速比除以原時(shí)間，來(lái)確定這個(gè)任務(wù)所需的絕對(duì)最小時(shí)間——200/2 = 100小時(shí)。

剛才用來(lái)確定并行編程中的加速比的原理叫作阿姆達(dá)爾定律。使用該定律時(shí)，只需要知道原始串行程序的執(zhí)行時(shí)間中，可并行化的代碼的執(zhí)行時(shí)間所占比例（稱為p），以及可用的處理器內(nèi)核數(shù)量N。

在這種情況下，無(wú)法并行化的代碼的執(zhí)行時(shí)間比例總是 1?p，所以我們只需要知道p。

現(xiàn)在，我們可以用阿姆達(dá)爾定律來(lái)計(jì)算加速比（Speedup，用S表示）了，具體公式如下所示：

綜上所述，阿姆達(dá)爾定律就是一個(gè)簡(jiǎn)單的公式，可以用于粗略地（非常粗略地）估計(jì)一個(gè)至少可以部分并行化的程序的潛在加速比。只要我們知道可以并行化的代碼的運(yùn)行時(shí)間占比（p）和運(yùn)行并行化的代碼的內(nèi)核數(shù)量（N），就可以大致推斷出是否值得為特定串行程序開發(fā)一個(gè)并行版本。