1.3  理解Amdahl法則

如果想要充分發(fā)揮多核的優(yōu)勢(shì)，在更短時(shí)間內(nèi)運(yùn)行更多的指令，那么就有必要將代碼分解為并行的序列。然而，大部分算法都要求運(yùn)行一些串行代碼來(lái)協(xié)調(diào)并行的執(zhí)行。例如，以并行方式啟動(dòng)很多塊計(jì)算，然后收集它們的計(jì)算結(jié)果。用于分解并行任務(wù)和收集結(jié)果的代碼可能是串行代碼，因而不能利用并行化的優(yōu)勢(shì)。如果將很多這類(lèi)算法組合起來(lái)，則整體的串行代碼的比例會(huì)增加，而性能優(yōu)勢(shì)可能會(huì)下降。

著名計(jì)算機(jī)架構(gòu)師Gene Amdahl對(duì)只有部分能夠改進(jìn)的計(jì)算機(jī)系統(tǒng)所能夠獲得的最大性能提升進(jìn)行了觀察。他通過(guò)這些觀察定義了Amdahl法則，通過(guò)以下公式預(yù)測(cè)多處理器系統(tǒng)的最大理論性能提升(即加速比，speedup)。這個(gè)公式也可以應(yīng)用于運(yùn)行在多核微處理器上的并行算法。

最大加速比(倍數(shù)) = 1 / ((1 - P) + (P/N)) 

其中：

● P表示能夠完全并行運(yùn)行的代碼比例。

● N表示可用的計(jì)算單元數(shù)(處理器或物理內(nèi)核數(shù))。

根據(jù)這個(gè)公式，如果一個(gè)算法中總?cè)蝿?wù)的50%(P=0.50)可以并行執(zhí)行，那么在具有兩個(gè)物理內(nèi)核的微處理器上的最大加速比為1.33x。圖1-8展示了一個(gè)帶有1000份任務(wù)的算法，其中500份串行任務(wù)，500份并行任務(wù)。如果串行版本需要耗費(fèi)1000秒的時(shí)間完成，那么帶有并行代碼的新版本至少需要750秒才能完成。

最大加速比(倍數(shù)) = 1 / ((1 - 0.50) + (0.50 / 2)) = 1.33x