并行执行时间方程式

对于一个并行算法，除了要确定计算步数外，还需要估计通信开销。在消息传递系统中，在求解问题的整个执行时间中必须考虑发送消息的时间。并行执行时间\(t_p\)是由两部分组成的：一个计算部分\(t_\text{comp}\)和一个通信部分\(t_\text{comm}\)；即有： \[ t_p = t_\text{comp} + t_\text{comm} \] ## 计算时间 计算时间可使用类似于顺序算法的方法通过计数计算步数加以推算。当有多个进程同时执行时， 只需计数最复杂进程的计算步数。通常所有进程都完成相同的操作，所以我们只需简单地计数一个进程的计算步数。在其他的情况中，我们将需要找出并发进程中的最大计算步数。一般而言，计算步数是\(n\)和\(p\)的函数。即有 \[ t_\text{comp} = f(n,p) \] \(t_p\)的时间单位与计算步的一样。

为方便起见，我们常将计算时间用消息传递分成各个部分，然后确定每个部分的计算时间。于是有 \[ t_\text{comp}=t_\text{comp1}+t_\text{comp2}+t_\text{comp3}+... \] 其中\(t_\text{comp1}\)、\(t_\text{comp2}\)、\(t_\text{comp3}\) ... 是各个部分的计算时间。

计算时间的分析通常假设所有处理器均相同且以相同速度运行。对特殊设计的计算机/多处理机来讲情况确实如此，但对机群来讲就不一定。机群的一个重要特征是计算机不必完全相同。在进行数学分析时，若考虑异构系统情况将有很大难度，因此我们的分析将假设所有计算机均是相同的。通过选择可用计算机间平衡计算负载的实现方法（负载平衡，load balancing）就可将不同类型的计算机考虑在内。 # 通信时间 通信时间与消息的数量、消息的大小、底层的互联结构以及传送方式有关。每个消息的通信时间与许多因素有关，包括网络结构和网络竞争。作为最初的近似，我们将使用下列公式表示消息1的通信时间： \[ t_\text{comm}=t_\text{startup} + wt_\text{data} \] 其中\(t_\text{startup}\)为启动时间，也称消息时延。实际上是发送不包含数据的消息所需的时间。它包括在源进程处将消息打包以及在目的进程处将消息解包所需的时间。

术语时延（latency） 用来描述完整的通信延时，所以这里用启动时间这一术语，且假设启动时间为一常数。

\(t_\text{data}\)这一项表示发送一个数据字所需的传送时间，也似它为一常数，\(w\)则表示数据字的数目。传送速率通常以位/秒（bits/second）为单位。当数据有\(b\)位时，就用\(b/t_\text{data}\)位/秒来表示。

下图对此方程做了说明。实际系统中，不可能得到如此完美的线性关系。许多因素会影响通信时间，包括对通信介质的争用。方程式忽略了在实际系统中的，源和目的可能不直接链接以致于消息传递必须经过中间结点这一事实。

此外，还假设由于在包中含有非数据的信息而导致的开销也是一个常数，且是\(t_\text{startup}\)的一部分。

最后的通信时间是一个进程中所有顺序消息的通信时间的累加和，于是有： \[ t_\text{comm} = t_\text{comm1} + t_\text{comm2} + t_\text{comm3} + ... \] 其中，\(t_\text{comm1}\)、\(t_\text{comm2}\)、\(t_\text{comm3}\) ... 是各消息的通信时间。通常所有进程的通信模式是相同的，并假设是一起发生的，因而只需考虑一个进程。

由于启动时间\(t_\text{startup}\)和数据传输时间\(t_\text{data}\)均以计算步单位衡量，这样我们就可将\(t_\text{comp}\)和\(t_\text{comm}\)加在一起来提到并行执行时间\(t_p\)。

基准测试程序系数

一旦我们获得了顺序执行时间\(t_s\)、计算时间\(t_\text{comp}\)和通信时间\(t_\text{comm}\)， 我们就可以为任何给定的算法/实现确定加速系数和计算/通信比，即： \[ 加速系数=\dfrac{t_s}{t_p}=\dfrac{t_s}{t_\text{comp}+t\text{comm}} \] \[ 计算/通信比=\dfrac{t_\text{comp}}{t_\text{comm}} \] 两个系数均是处理器数\(p\)和数据元素数\(n\)的函数，并将为增加处理器数和增大问题规模的并行求解给出可扩展性的指示。

时延隐藏

例. 假设一台计算机的最大运行速率为1 GFLOP（每秒10亿次浮点运算）并且启动时间为1 μs。则在消息启动时间内，计算机可执行1 000次浮点操作。

改善这种情况的一种方法是使通信与后续的计算重叠操作（overlap）；也就是在等待通信结束时，同时使处理器忙于有用的工作，这是所谓的时延隐藏。特别是非阻塞的发送例程提供了时延隐藏的可能性，但即使是（本地）阻塞发送例程也允许在等待目的进程接收消息时从事后续计算，且也许返回一个消息。

时延隐藏也可以通过将多个进程映射到一个处理器上，并使用分时机制来加以实现，当第一个进程因未完成消息传递或由于其他原因而停顿时，它就从一个进程转向另一个进程。有时称这些进程为虚拟处理机。在一个有\(p\)个处理器的计算机上实现\(m\)个进程（或虚拟机）算法被称为该计算机具有\(m/p\)并行不完善性（parallel slackness），这里\(p<m\)。使用并行不完善性隐藏时延方依赖于从一个进程切换到另一进程的有效的方法。线程能提供这种的有效的机制。

参考文献

Wilkinson, B., & Allen, C. M. (2005). Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers (2nd ed.). Pearson/Prentice Hall.