# 第四章(下)-并行计算定理

渐入佳境

# Amdahl’s law

Amdahl 定理中，计算负载 $W$ 保持固定，处理器的个数能够增加。假设 $W$ 由串行工作 $\alpha W$ 和 $n$ 个并行工作 $(1-\alpha)W$ ，其中 $\alpha \in (0,1)$ ，表示串行工作所占的比例。

T_n = {\alpha W} + \frac{(1-\alpha)W}{n}

S_n = \frac{T_1}{T_n} =\frac{W}{\alpha W + \frac{(1-\alpha)W}{n}} = \frac{n}{1+(n-1)\alpha} \tag{1}

上述公式 $(1)$ 就是 Amdahl 定理。

S_{\infty} = \frac{1}{\alpha} \tag{2}

由公式 $(2)$ 可得，一个固定负载的计算程序随着处理个数增加能够获得的加速比是有上限的,这个上限由无法并行的串行比例决定。或者说串行工作的比例是并行计算的瓶颈。

Gustafson 定理中，一个处理器的执行时间固定，不断的增加处理器，相同时间能够解决更大规模的问题。

S'_n = \frac{(\alpha W + (1-\alpha)nW)/1}{{\alpha W}/1 + {(1-\alpha)nW}/n} \tag{3}

S'_n = \alpha + (1-\alpha)n \tag{4}

由上述公式 $(4)$ 可得，随着处理器个数增加，加速比呈线性增长。该定理描述越大的并行系统，在相同的时间内就能解决越大的问题。

Sun-Ni 定理描述了内存限制模型（memory bound model）。该定理表明在n个处理器的系统上，问题规模受可用内存限制，加速比也受内存限制。

W^* = \alpha W + (1-\alpha)G(n)W

S^* = \frac{\alpha W + (1-\alpha)G(n)W}{{\alpha W}/1 + {(1-\alpha)G(n)W}/n} = \frac{\alpha + (1-\alpha)G(n)}{{\alpha} + {(1-\alpha)G(n)}/n}

根据 $G(n)$ ，有三种情况:

👉 Case 1: $G(n) = 1$ ，等价于 Amdahl 定理

S^* = \frac{\alpha + (1-\alpha)G(n)}{{\alpha} + {(1-\alpha)G(n)}/n} = \frac{1}{1 + (n-1)\alpha}

👉 Case 2: $G(n) = n$ ，等价于 Gustafson 定理

S^* = \frac{\alpha + (1-\alpha)G(n)}{{\alpha} + {(1-\alpha)G(n)}/n} = \alpha + (1-\alpha)n

👉 Case 3: $G(n) > n$

使 $G(n) = m, {where} \space m > n$ ，加速比是

S^* = \frac{\alpha + (1-\alpha)G(n)}{{\alpha} + {(1-\alpha)G(n)}/n} = \frac{\alpha + (1-\alpha)m}{m/n + (1-m/n)\alpha}

这种情况工作负载比内存增长更快。加速比相比于 Gustafson 定理的情况要稍快。

⭐️ Amdahl’s law 对应上一章的 strong scalability。

⭐️ Gustafson’s Law 对应上一章的 weak scalability。

这章的定理在描述并行计算时，只考虑并行计算的 computation 时间，而忽略 communication 的开销。在实际设计并行算法时，需要考虑计算和通信的平衡。