平行計算之兩三事

自從Moore's Law走到一個瓶頸之後，電腦發展的方向就開始往平行化發展，而談到平行計算，不能不說幾個基本概念。

Amdahl's Law: 

Gustafson's law:

這兩個都是很粗淺的公式，只能大致評估預期的效能比，實際跑起來比這複雜多了。
Amdahl's Law是把一件工作視為1，其中k的部份必須只能由一個Processor完成，其他(1-k)的部份，分別讓n顆Processsor處理，舉例來說，一份工作，能夠被平行化的程度只有0.4，然後放到一台雙核心的電腦上執行，預期可獲得的效率比為 ，如果同樣的工作，放在一台四核心CPU上面跑，預期的效率比會是 ，由此可見，同樣的演算法，在四核心的效能提昇比反而有限；從原先的數學公式來看，當k趨近於零 ，也就是盡量讓演算法平行化，將可以得到最多的效能比。

Gustafson's law，從另一個角度來論述性能比，n為處理器的數目，α為不能平行處理的部份，以上面的例子來看，雙核心的加速比應該是 ，而四核心的部份 ，跟上面Amadahl的結果對照起來，一個過於樂觀、另一個過於悲觀，不過相同的是，一旦α越小。