# 第四章(上)-并行程序性能分析

渐入佳境

# 加速比 & 效率

加速比的定义为： $S(p) = \frac{T_s}{T_p}$

$T_s$ ：最优串行算法的执行时间

$T_p$ ：使用 p 个处理器的执行时间

Linear speedup: $S(p) = p$
- 理论上理想的加速比
Superlinear speedup: $S(p) > p$
- 偶尔在实践中发生
- 额外的硬件资源（例如：memory）
- 软件或硬件的优化（例如：caching）
Maximum Speedup
- 达到理想的最大加速比 $S(p) = p$ 很困难
  - 程序不是每个不都能并行化（导致处理器空闲）
  - 在并行计算中需要额外的计算量（例如：同步的开销）
  - 多个程序之间需要通信（通常是主要因素）
- 使 $f$ 表示程序中无法并行的部分
  - $S(p) = \frac{t_s}{ft_s + (1-f)t_s/p}$
  - 假如处理器的数量趋向于无限大： $S(p)_{p \to \infty} = \frac{p}{1+(p-1)f} = \frac{1}{f}$

System efficiency: $E(p) = \frac{T_s}{T_p \times p} = \frac{S(p)}{p} \times 100\%$

Strong scaling	Weak scaling
线性规模难以实现，因为随着问题规模增加，通信开销也会同比例增加	线性规模增加容易实现，因为不管使用多少进程，通信开销相对固定通信使用 nearest-neighbor communication patterns

本节的时间复杂度和代价优化不仅考虑了并行算法的设计，还考虑了并行部分的通信。

$T_p = T_{comp} + T_{comm}$
- $T_p$ : 并行算法的执行时间
- $T_{comp}$ : 计算部分的消耗
- $T_{comm}$ : 同步部分的消耗
$T_{comm} = q(T_{startup} + nT_{data})$
- $T_{startup}$ : 消息延迟（假设固定）
- $T_{data}$ : 一条数据的传输时间
- $n$ : 在一个消息中的数据的条数
- $q$ : 消息的数量

累加 $N$ 个数字的并行算法设计：

★ 算法1

用2个计算机来并行计算：

复杂度分析：

Computation: (step-2 和 step-4)
- $T_{comp} = n/2 + 1 = O(n)$
Communication: (step-1 和 step-3)
- $T_{comm} = (T_{startup} + n/2 \times T_{data}) + (T_{startup} + T_{data}) = 2T_{startup} + (n/2 + 1)T_{data} = O(n)$
总体的时间复杂度： $T_p = T_{comp} + T_{comm}=$ $O(n)$

★ 算法2

用m个处理器来并行计算：

（1）把 n 个数字平均的分给 m 个处理器
（2）m 个处理器同时相加 n/m 个数字
（3）把 m 个部分和返回到一个处理器，相加得到最终结果

并行处理流程：

由上述两个算法例子可知：
◇ 处理器个数少，通信开销少，计算的时间复杂度更高
◇ 处理器个数多，通信开销大，计算的时间复杂度更少

所以设计并行算法需要在 computation 和 communication 之间做权衡。

定义
- 解决问题的代价随着在单个处理器上的执行时间成正比例关系
- $O(T_p) \times N = O(T_s)$
  - $O(T_s)$ : 执行串行算法的时间复杂度
  - $O(T_p)$ : 执行并行算法的时间复杂度
例子
- Sequential algorithm: $O(N\log{N})$
- Parallel algorithm 1: uses $N$ processor with $O(\log{N})$
- Parallel algorithm 2: uses $N^2$ processor with $O(1)$