Amdahl's law

关于Amdahl’s law。

Amdahl’s law，又叫做阿姆达尔定律，其意义在于表示了计算机并行计算处理任务的加速的极限。

简略证明

解释如下，假设一个任务需要时间$T$来完成，而其中可以被并行处理加速的部分比例为$p$，那么不能被并行计算加速的部分就为$1-p$，比如从磁盘上读取程序段就不能并行加速，而读取完成到内存中就可以开多个进程或者利用分布式的方法并行处理来加速。

$$
T = (1-p)T + pT
$$

开启加速后，可以加速的部分时间减少至原来的 $\frac {p} {s}$

$$
T’ = (1-p)T + \frac p s T
$$

则加速比就为

$$
S_{\text{latency}}(s) = \frac {T} {T’} = \frac{1}{1 - p + \frac p s}
$$

意义

Amdahl’s law揭示了不管如何的进行并行计算，只要任务包含无法被并行加速的部分，那么加速比是有上限的，因为

$$
\lim_{s \rightarrow \infty} S_{\text{latency}}(s) = \frac {T} {T’} = \frac{1}{1 - p}
$$

例如如下图中的例子，如果任务的95%可以并行，那么加速的极限约为20倍。