# Amdahl's Law 阿姆達爾定律

> [name=K.Wei] [color=gray]

## 概述

阿姆達爾定律可以用來評估「改善系統」的效率。

## 先備知識

- 假設一部影片 10 分鐘。我用兩倍速觀看，只需5分鐘。
- 假設所需時間 T ，速度提升 S 倍。則提速後時間只需要 $\dfrac{T}{S}.$
- $\text{Rate} = \dfrac{ 1 }{ \text{Time} }$
- 一點點數學

## 原理

- 假設系統優化後提升 S 倍。

$$
\begin{array}{ll}
&\displaystyle{ \text{New Time} = \dfrac{ \text{Old Time} }{ \text{Speedup }S } }
\\\\
\Rightarrow & \displaystyle{ \text{Speedup }S = \dfrac{\text{Old Time}}{ \text{New Time} } = \dfrac{ \text{New Rate} }{ \text{Old Rate} } }
\end{array}
$$

## 推導（可以不用看）

- 假設系統由 $n$ 個部分組成，所需時間 $T_{overall}$。

$$
\begin{array}{ll}
\begin{array}{ll}
T_{overall} &= T_{1}+T_{2}+ \cdots + T_{a} + \cdots +T_{n},\; a \in (1,n)
\\\\
&\displaystyle{= \sum_{k=1}^{n}{ T_{k} } }
\end{array}
\\\\
\displaystyle{\Rightarrow \text{Ratio with } T_{overall }\; \text{ is }\; 1 }
\end{array}
$$

<br>

- 每 Part 對系統影響時間比 $R$

$$
\text{Ratio } R_{k} = \dfrac{ T_{k} }{ T_{overall} }
$$

<br>

- 假設 Part $a$ 優化後速度增加 $s$ 倍

$$
\begin{array}{ll}
\begin{array}{rl}
\text{New Time } t_{a} &= \dfrac{T_a}{s}
\\\\
\text{New Ratio } r_{a} &= \dfrac{ \frac{T_{a}}{s} }{ T_{overall} } = \dfrac{t_a}{T_{overall}}
\\\\
r_{overall} &\displaystyle{= \sum_{k=1}^{n}{r_{k}} }
\end{array}
\\\\
\begin{array}{ll}
\displaystyle{\Rightarrow T_{new} } &\displaystyle{= T_{1} + \cdots + \dfrac{T_{a}}{s} + \cdots + T_{n} }
\\\\
&\displaystyle{= \sum_{k=1}^{n} r_{k} \cdot T_{overall} \quad \boxed{ k \neq a \Rightarrow R_k = r_k } }
\\\\
&\displaystyle{= T_{overall} \times r_{overall} }
\end{array}
\end{array}
$$

<br>

- 系統速度提升

$$
\text{Speedup } S = \dfrac{ T_{overall} }{ T_{new} } = \dfrac{ T_{overall} }{ r_{overall} \cdot T_{overall} } = \dfrac{ 1 }{ r_{overall} } = \dfrac{1}{r_1+r_2+ \cdots + r_n}
$$

## 範例

### Case 1

假設你把系統某一部份提升了2倍速，
但這部分只佔系統的 20%，
意味著未改善的部分有 80%。

根據阿姆達爾定律：
$$
\text{Speedup} = \dfrac{1}{(1-0.2)+(\frac{0.2}{2}) } \approx 1.11
$$

意味這個優化只能提升系統速度 1.11 倍左右。
$$
\text{New Time} = \dfrac{\text{Old Time}}{1.11}
$$

---

### Case 2

接著假設你很厲害，
把系統的 20% 提升到無窮倍快。
$$
\text{Speedup} = \lim_{n \to \infty} \dfrac{1}{(1-0.2)+(\frac{0.2}{n})} = \dfrac{1}{0.8} = 1.25
$$

這時得到的就是這 20% 改善的極限。
你即使再怎麼厲害，
也只能把系統速度提升到 1.25 倍。

---

## 備註

覺得有問題的話歡迎來信指點！

---

###### tags: `Computer Organization`