1.3  理解Amdahl法則

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

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

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

其中：

● P表示能夠完全并行運行的代碼比例。

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

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

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