引言

并行处理可以分为功能并行和数据并行两种方式，大规模数据并行是大规模科学计算的一种最常见并行处理方式。例如在求解流体力学方程时，往往将求解空间数据分割成不同的区域，用多个处理机进行处理实现并行计算。并行处理的目的在于加快处理速度，以往的性能分析侧重于对加速比的讨论^[1]，指出增加课题计算规模可以提高加速比。在满足时间要求的前提下，对于某些用户，对计算机进行升级的主要目的是减少计算时间；但对于很多用户，在计算时间能够满足要求的前提下，扩大计算机规模是为了提高计算精度，他们需要在规定的时间内得到精度尽可能高的计算结果。这部分用户的课题规模随并行机规模而增大，并行效率成为用户关心的主要问题，他们希望在扩大计算机规模的同时，大课题运行时间和并行效率基本不变。Gustafson分析了计算机规模与求解问题规模同时扩大n倍时的加速比情况，提出了固定时间加速比的概念，即Gustafson定律^[2]。但是它没有包括对计算机通信性能、I/O性能的分析。

本文以流体力学初值问题为背景，建立了一个大规模数据并行的性能分析模型，提出时间不变，并行效率不变，并进一步假定计算、延迟、通信、I/O时间都不变，在此条件下，分析了并行计算机处理机速度、处理机数量和通信延迟、通信速率以及输入输出速率之间的关系。

1 数据并行计算模型

初值问题是已知某空间在初值时刻的状态，求解经过时间T以后的状态。假定求解空间为边长为L的正立方体 (图 1)，用间距为d的三维网格进行离散化，构成格点数为 (L/d)³的三维网格。处理机数量为P=n ×n，对区域进行二维水平分割，每个区域是格点数量为的柱形，在水平边缘有宽度为e个格距的重叠区域，在进行计算时需要用到该区域的数据，在区域中心有区域，它计算的数据已经在该区域内。其时间分辨率为Δt，经过T/Δt步计算，得到T时刻的状态进行输出。

设每个网格点的计算时间相同，为t_ca。每次通信的延迟时间为t_la，每个格点数据的输入输出时间为t_io，每个格点数据的通信时间为t_co，各通信链路之间无冲突，则计算时间为延迟时间为通信时间为输入输出时间为时间分辨率Δt由计算稳定性确定，正比于空间分辨率，设Δt=αd，e由采用的计算方法确定。总时间为:

(1)

2 可扩展性与运行时间的关系

Nussbaum和Ag arw al提出了并行计算机的可扩展性定义^[3]，在理想情况下，可扩展性与并行效率的定义是一致的^[4]。本文建立的计算模型属于理想情况，因此，在以下分析中，可扩展性与并行效率相同。

定义1 :对于给定算法κ，P-处理机系统的加速比S_peedup(κ，P) 和效率E_ffecient(κ，P) 分别为:

其中，T_ime(κ，P) 是在P-处理机系统的并行执行时间。

算法规模可以定义为该算法的计算量，在单处理机条件下，算法规模增加m倍，记为mκ，则计算时间增加m倍。即

定理:在算法规模增加m倍的同时增加处理机数量m倍，若计算时间不变，则并行效率不变。

证:

证毕。

所以，可扩展性不变与计算时间不变等价。

3 处理机计算速度和数量与通信、I/O性能的关系

在式 (1) 中假定计算时间Tca不变，并设处理机计算速度有:

(2)

可得:

(3)

假定延迟时间不变有:

(4)

代入式 (3)

(5)

假定通信时间不变，并设通信速度为Sco=1t co有:

(6)

代入式 (3) 可得:

(7)

假定总I/O时间不变，并设可得:

(8)

代入式 (3) 得

(9)

由此可见，系统处理机的计算速度和数量与通信延迟时间和通信速率，I/O速率之间存在相应的比例关系:通信速度延迟时间I/O速度S_co。

4 计算与通信重叠的影响

如果每个处理机都由一个独立的通信管理硬件，可以实现通信与计算的操作重叠，这时，要求非边缘区域的计算时间大于等于通信时间，若延迟时间远远小于通信时间，边缘区域远远小于非边缘区域，即L>>2edn，有:

带入式 (3) 得

(10)

其中S′_co=1/ t_co为通信与计算重叠时的通信速度，由式 (7) 和 (10) 有

(11)

对于多数应用课题，通信时间远远小于计算时间，即在通信与计算操作可以重叠的计算机上，只要通信时间不大于计算时间，即可将通信时间完全隐藏。所以对通信速度的最低要求是:

(12)

与没有此项功能的计算机相比，对通信速度的要求可以适当降低。

5 试验结果与分析

我们以在数值预报模式中抽取的二阶扩散方程为例，在IBM sp2计算机上，对上述分析结果进行验证。取L=130 km，T=13 s，分别用P₁=9个与P₂=16个处理机进行试验。并假定，增加处理机数量的目的是增加机算精度，在处理机数量为P₁=9时，分辨率d₁=1 km，根据式 (2)，有P₁ d₁⁴=P₂ d₂⁴可得d₂=0.866，测量了计算、通信、I/O时间。忽略延迟时间。由于在同一台计算机上，计算、通信、I/O速度不变，根据前面的分析，我们通过测量P₁=9时的通信时间，分别用式 (6) 和 (8) 推算增加分辨率后相应的通信、I/O时间并与实测数据进行比较 (见表 1)。可以看出二者是比较吻合的。证明分析是正确的。

6 结论

本文通过建立初值问题的计算模型，分析了并行计算机系统的处理机速度，处理机数量与通信延迟时间、通信速度、I/O速度之间的关系。指出对于解决该类问题的并行计算机有以下要求:

(1) 并行处理机的处理机数量、处理机速度、通信延迟、通信速度以及I/O速度形成有机的整体，提高处理机计算速度S_ca或增加处理机节点数量P的同时必须以的比例增加并行机的通信速度，以的比例降低延迟时间，以的比例提高I/O速度。否则会降低系统的可扩展性。

(2) 计算与通信操作重叠，不仅可以提高并行效率，同时还有利于降低通信速度对系统可扩展性的影响。