并行算法笔记（一）——性能测评

• 并行执行时间$T_{comput}$为计算时间，$T_{paro}$为并行开销时间，$T_{comm}$为通讯时间，则$T_n=T_{comput}+T_{paro}+T_{comm}$
• 通讯开销：通讯开销包括启动时间$t_0$（一般为建立连接所用时间）和传输时间，如果定义$r_{\infty }$为渐近带宽，则传输m比特信息的通讯开销为$T_{comm}(m)=t_0+m/r_{\infty }$
• S为加速比，E为效率

加速比性能定律

并行系统的加速比是指对于给定应用，并行算法的执行速度相对于最优串行算法的执行速度加快多少倍（$\geq$1）。

定义处理器数为P，问题规模（总计算量）为W，其中串行和并行计算量分别为$W_s,W_p,W=W_s+W_p$。为方便表示，定义串行分量的比例为$f=W_s/W$。

Amdahl定律

​ Amdahl定律假定计算负载是固定不变的，将计算任务分配到多个处理器上。则$S=\frac{W}{W_s+W_p/p}=\frac{W_s+W_p}{W_s+W_p/p}=\frac{p}{1+f(p-1)}$。

​ 当$p\to \infty ,S=1/f$，即串行分量为加速瓶颈。

​ 如果考虑额外串行开销$W_0$，则$S=\frac{W}{W_s+W_p/p+W_0}=\frac{p}{1+f(p-1)+W_{0}p/W}$

​ Amdahl是比较悲观的一种结论，认为即使使用再多的处理器也不会产生更好的结果。

Gustafson定律

​ 在一些高计算精度要求的任务中，计算时间是固定的，计算量和计算精度成正比，若在相同时间内提高计算精度只能通过增加处理器数量实现。

​ 此时Gustafson定律认为计算负载为$W_s+p{W}_p$，则$S=\frac{W}{W_s+W_p}=\frac{W_s+p{W}_p}{W_s+W_p}=f+p(1-f)=p-f(p-1)$

​ 当$p\to \infty$时，S可视为p的线性函数，不再存在串行瓶颈。

Sun和Ni定律

​ Sun和Ni定律考虑到了物理实现对并行效率的影响，即增大问题规模时读取储存的开销会发生变化。因此定义因子$G(p)$反应存储容量增加到p倍时并行工作负载的增加量，即扩大问题规模后的工作负载为$W^{\prime }=W_s+G(p)W_p=fW+(1-f)G(p)W$

​ 存储受限的加速公式为：$S=\frac{fW+(1-f)G(p)W}{fW+(1-f)G(p)W/p}=\frac{f+(1-f)G(p)}{f+(1-f)G(p)/p}$

• 当G§=1时，即增加处理器不会增加总计算负载，Sun和Ni定律变为Amdahl定律。
• 当G§=p时，即计算负载和处理器数成正比时，Sun和Ni定律变为Gustafson定律。
• 当G§>p时，即计算负载增加速度比储存开销增加的快时，Sun和Ni定律加速比要高于前两个定律。

可扩放性评测标准

​ 并行计算的可扩放性(Scalability)即计算系统性能随处理器增加提高的能力(可看作加速比的变化率)。目前没有公认的评判标准，下面列举一些常见的标准。

等效率度量标准

​ 定义加速效率$E=S/P=\frac{p}{1+T_0/T_e}\times \frac{1}{p}=\frac{1}{1+T_0/W}$，其中$T_0,T_e$分别为额外开销和计算开销。

​ 如果增加处理器数目，额外一定会增大(通讯开销)，因此为了维持效率不变需要增加计算负载。

​ 等效率度量标准即$f_E(p)$为维持相同效率E时问题规模W随p变化的函数。

• 优点：简单、可定量计算。
• 缺点：额外开销有时难以定量计算。

等速度度量标准

​ 速度即为最朴素的定义计算量/计算时间，等速度标准定义平均速度为并行速度/处理器数，即$\bar{V}=V/p=\frac{W}{pT}$ 。

​ 等速度度量中的可扩放性即当处理器数目增加时需要增加计算量保证平均速度不变的能力。用下式描述：
$$\Psi (p,p^{\prime })=\frac{W/p}{W^{\prime }/p^{\prime }}=\frac{p^{\prime }W}{p{W}^{\prime }}$$
即反应每个处理器分配的计算负载随处理器数的变化。当保持平均速度不变时，$\frac{W}{pT}=\frac{W^{\prime }}{p^{\prime }{T}^{\prime }}\Rightarrow \Psi =\frac{T}{T^{\prime }}$

​ 特别的，当p=1时，即串行计算，此时$\Psi (1,p^{\prime })=\frac{W}{W^{\prime }/p^{\prime }}$