阿姆達爾定律 Amdahl's Law

Amdahl's Law 是 1967 年 Amdahl 發表的論文提出的法則。

當時的命題是，在平行運算的研究領域中，一個程式可以分為可被平行運算與不能被平行運算兩個部分，當我們針對平行運算做效能提升的研究時，應該把時間跟經費做最有效率的投資，但究竟平行運算可以帶來多少效益？

$$T = 程式以序列運算的總時間 \\ B = 程式中，無法被平行化運算的部分的運算時間 \\ T-B = 可被平行化運算的總時間 \\ N = number of Threads/CPUs \\ T = B + (T-B) \\ (T-B) 部分可被平行化，變成耗費時間 (T-B)/N$$

假設 T 為 1

$$\text{if N=2} => T(N) = B + (T-B)/2 \\ \text{if N=3} => T(N) = B + (T-B)/3$$

可得到程式運算的總時間

$$T(N) = B + (T-B)/N$$

假設 T = 1, 只能序列運算的部分 B = 0.5, N = 2

$$T(2) = 0.5 + (1-0.5)/2 \\ = 0.5+0.5/2 \\ = 0.75$$

當 Thread/CPU 越多，就代表程式運算的總時間會減少。

---

另外有一個程式加速的指標參數

$$Speedup = \frac{Original Execution Time}{Execution Time After Enhancement} \\ = \frac{1}{B+(1-B)/N}$$

如果程式有一半的部分可被平行化加速

$$N=2, Speedup = \frac{1}{0.5+(1-0.5)/2} = 1.33 \\ N=4, Speedup = 1.6 \\ N=100, Speedup = 1.98 \\ N=1000, Speedup = 1.998 \\ N=10000, Speedup = 1.99998 \\ N=\infty, Speedup = 2$$

意思就是，就算平行化運算可以無限的加強效能，減少運算時間，程式的總運算時間，會被無法平行化運算加速的部分限制住。

如果有兩件事，我們不知道應該去做哪一項時，也可以利用這個法則決定，取效益比較高的那一個。例如：讀書時不知道要先讀數學還是英文，先假設數學是無法提升的部分，算出 Speedup，再用英文為B，算出 Speedup，兩個互相比較，就可以知道哪一個效益較高。

但真實世界也不是那麼簡單的事，因為我們無法預先知道，最佳化後的成果，是不是跟預先假設的成果效益一樣。另外以讀書為例，我們也不知道一直都看不懂的英文，要花多少時間，才能改進並得到效益，反而是比較熟悉的數學還有進步空間，因為看不懂的東西，再怎麼看也不懂，就算看懂以後的效益很高也沒有用。

References

OpenMP: Amdahl's Law - YouTube

阿姆達爾定律 - 維基百科，自由的百科全書

Day27：阿姆達爾定律（Amdahl's law）——資源配置的哲學 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

Amdahl's Law · 課程筆記

阿姆达尔定律(Amdahl’s Law) 计算51CTO博客amdahl 定律