复杂形状飞行器CFD并行计算的静态负载平衡问题的研究_图文

1、复杂形状飞行器CFD并行计算的静态负载平衡问题的研究木 刘鑫。陆林生江南计算技术研究所.无锡214083Iiuxin倒摘要:本文主要讨论复杂形状飞行器CFD并行计算的静态负载平衡问题.首先,本文从图论的角度讨论了静态负载平衡问题,给出三个优化目标,即点集等分.最短通路和通信量最小.对于以边缘通信为特征的一般数值计算问题。本文论述了二维问题正方形划分总通信量最小、并行效率最高,三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点,本文提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法,实验结果证明,该方法实现简单,能够处理不同规模复杂外形的CFD

2、实际课题,且能达到较优的负载平衡和较高的通信效率,明显提高并行程序的整体效率.关键词:CFD;并行计算;静态负载平衡;规则划分;自动重分计算流体力学(CFD是一门利用计算机对流体的复杂流动进行数值模拟的学科。流体的运动规 律可由欧拉方程、NS(Navier-Stokes方程等数学方程组来描述,CFD则采用数值计算方法求解这些 方程,研究流体运动特性,得出流体的时空流动规律。在CFD中,首先要把计算区域离散化为网格。 流场的状态由网格的各种流动特征量来表述,如速度、密度、压力、温度等。CFD程序主要是对特 征量进行大量迭代,由于计算量非常大,需要在高性能并行计算机或集群并行计算机系统上进行大 规

3、模并行计算。复杂形状飞行器的一个重要特征是计算区域由多个大小不等的物理块组成,这给负载平衡带 来很大的挑战。如何进行任务划分与处理器分配是获得较高的并行效率的关键.当前大部分的CFD 并行计算课题的任务划分采用人工划分方式,或者只能实现计算区域较简单情形的自动任务划分, 这些方法己不能满足复杂形状飞行器CFD的大规模并行计算的需要。本文结合实际应用课题。从理 论探讨和工程应用出发在解决复杂形状飞行器CFD并行计算的静态负载平衡问题上做了一些尝试。木本课题得到国家863高科技发展计划(编号:2003AA723050,国家自然科学基金资助项目(编号:10072077 资助刘鑫,博I:生,主要研究领

4、域为并行算法与并行识别;陆林生,教授,博:I:生导师.主要研究领域为并行算法与并行识别.61本文先从图论的角度讨论了静态负载平衡问题。给出静态负载平衡问题的二二个优化目标。即 点集等分。最短通路和通信量最小。对于分布存储的并行计算机,当处理器同构时.负载,f,衡问题 等价于一个线图的分割问题.其对应的约束条件,一是要求各处理器上的任务尽可能柏等,二是处 理器之间的最大通信量为极小。同时,对于以边缘通信为特征的一般数值计算问题。本文论述了二:维问题正方形划分总通信量最小、并行效率最高,三维问题立方体划分总通信量最小、并行效率最 高的结论.并给出实际分块过程中应遵循的准则:使尽可能多的处理器处理规

5、模较大的数据子集。 基于以上结论和本应用课题的特点。本文提出两种负载平衡算法:一维优先的规则分块算法和基于 自动重分块的不规则分块算法,分别处理中小规模和大规模并行的问题。实际使用时,采用两种算 法相结合的方法,当处理器数少于或接近物理块数时.使用基于自动重分块的不规则分块算法,该 算法更灵活,在处理器很少的情况下也可以获得较好的负载平衡,弥补额外带来的通信开销;当处 理器数大于物理块数时,采用一维分解优先的规则分块算法,这种算法在大规模并行时优势更明显。 实验结果证明,两种负载平衡算法相结合的方法实现简单,能够处理不同规模复杂外形的CFD实际 课题,且能达到较优的负载平衡和较高的通信效率,明

6、显提高并行程序的整体效率。2静态负载平衡问题的图论表示用平面图上的一个点集U=“l,“2,甜口表示p个处理器,用这些点的可能连线 F=Z,厶,六u×u表示节点间的通信线路。如果是同构网络,则可以略去节点的权重 也不必考虑边的方向性。则处理器的相互关系可以用无向图H=川,F表示。一个并行应用程序 我们使用赋权图G=(V,E,p,仃来描述, 其中节点V=,I,2,。, 边 E=巳,P2,P,V×V.节点权重户:V专R,边的权重盯:E专R。对于本文的cFD 问题,节点代表各处理器上的数据子集,边代表数据通信.该图的拓扑可由图的邻接矩阵A表示:彳=(%。,其中。1f,/刀,=l表示

7、节点M、有通信,%=O表示节点U、一无 通信。G的端容量矩阵T为一实对称矩阵.用来表示节点之间的通信量:T=(ff,。,。其中 lf,疗.当f=,时。令f,=0,即忽略节点与自身的通信开销。G的顶点容量代表节点的 数据处理的计算量,用实列向量C表示,则C=cI,乞,巳7=p(H,p(v2,户(%负载平衡问题可以看成是一个图的嵌入问题.对于一般的数值分析问题.认为力>>p,即图 G的节点远大于图H的节点。负载平衡的任务就是找到一个好的方法,将图G=(V,E,p,伊映 射到图H=(u,F上,设这个映射为加Vu.映射关系由矩阵B=(6。,确定,且. f l G中,节点分配于H中的f节点呵

8、 Io G中,节点不分配于H中的,节点另有列向量X=(jcl,x2,童。7表示每个处理器的运算开销,则有X=BC.为了使并行系统达到较好的负载平衡状态,首先必须控制单个处理器承受的最大负载load(万=max 芝:户(V,=巴登(x, (1 -暑U I ssPpJ EV.石(”,l62设G巾的某个边为e=VI,V2E,咖=甜IU,咖2夕=“2U。设w。为“I到“。的 路径,则图G中某一边在H中需要的最长通信链路10ng(万-。器EM (2 此外。通信线路.兀上最大通信流量为加=盯(eo?(1.”2eE,E-.为了达到较好的负载平衡,应控制晟大通信量.所以负载平衡的第三个指标为:n。w(万2,o

9、譬。F加2厂嚣譬。扣(荟eE盯(e (3 _,。Ew。以上(1、(2、(3式给出了负载平衡问题的三个优化目标。即点集的等分,图的最短通路问题, 网络流问题。由于当前MPP的通信速度很快。图H可以看成是完全连接的,此时1w。I暑l。这样, 图G向图H的映射问题可以退化成图G的分割问题。设有p个处理器节点,则负载平衡问题转 化成求图G的p个子集,且满足cut(石=:盯(e (4 瓢嚣龋为极小。上式的意义是要求对图G进行切割时。被切断的边上的通信总量为最小。综上所述,当 处理器同构时,负载平衡问题等价于一个图的分割问题,其对应的约束条件。一是要求各处理器上 的任务尽可能相等,二是处理器之间的最大通信

10、量为极小.3预备知识图的分割可以采用几何方法,简单的几何方法是将图的节点在某一轴投影,再沿轴向进行划 分,这个轴可以是坐标轴或者是图的最小惯性轴。因为本文所用CFD例题使用结构化网格,所以我 们采用沿各个计算坐标轴向进行划分的方法。下面我们分别就不同分块算法的通信优化问题和并行 效率问题进行讨论。3.1不同分块算法的通信优化问题通信优化问题较为复杂,这里我们假设只有二排边缘通信的简单情况。先考虑二维问题任葸 划分的情况,每块大小为t,只,f=1,2,p,二维区域大小为×,则总的通信量 。=2(羔(z,+J,一2,问题归结为求(+儿一2在一y。=2/p条件下的最 f=I ,_l小值。又

11、艺(x,+”一2羔2i万一2=2(厄一1,当且仅当=儿时,等号成 ;I f=I:芷,即j:维向I题任意划分时,正方形划分总通信量晟小。63同样地,三维问题的任意划分情况归结为求(x,y。+少,乙+x.z,一32在 ,=I工.J,z,=3/p条件下的最小值。一 2(毛J,。+y,z。+工,zf一322艺3(工,J,z,了一3J2=32(p一I当且仅当=y,=z,时,等号成立,即三维问题任意划分时,立方体划分总通信量最小。3.2不同分块算法的并行效率问题以八点平滑为例:曰(f,_,七=(彳(,一l,_,一I,七一I+彳(,/一I,七一1+彳(f一1,.,七一1+彳(,/,七一1+彳(fl,/一l,

12、七+彳(f,/一l,七+彳(,一l,/,七+彳(f,一|f,七/8其中工七=l'2,.'。设一维分解的加速比为口l二维分解的加速比为口2.三维分解的加速比为口,.处理器个数 为p t每点的通信时间为f二维分解时每个处理器的数据子集为,.c,三维分解时每个处 理器的数据子集为,.cJl,假设>>1,则N 3%2矿石而33口,=了一:_二_:一 /p+f2(彤十洲+脚 3/肘+f幸22(p一+2p州2当且仅当,.=c=/万时等号成立。33%2矿石鬲丽百;再而矿石看丽甲。/p+f2(阳+cJl,+砌 3/口+r62D一273当且仅当厂=f=厅=J7、r/Vp时等号成立。易

13、得当p>33时,max(口3>口I:当p>o时。max(口3>ma(口2;当p>(2+12时,max他2>口I综上所述-当且仅当,%取得最大值3/(3/p+r62p一273; 若p>5,则max(口3>max(口2>口I。3.3实际分块过程中应遵循的准则设有Jp个处理器并行处理由个数据构成的数据集S,分配给每个处理器的数据子集S;包 含%个数据(f=1,2,pt且有当,/, /=1,2,ps,n s,=o U S=s I(吩一动/司<占其中万=/p是平均分配给各处理器的数据数,占是给定的误差。设有册(mp个处理器中包 含的数据个数相等

14、.且最大,则m越大.并行效率越高。证明:设有聊个处理器中包含的数据个数为门帐万,先证明历越大,l(刀吣一万/矧越小。 不失一般性,令f=1,2,肌个处理器各包含"。,个数据.则有尘生坚二!:生坚一1:堡坚:旦 +1. =:一.1. ,l。+乙惕 f=朋+I所以,当朋越大,l(,l删一万/叫越小. 再证并行效率盯: 显然所.门嘣+羔伟<(肌+1.玎哪+兰%t,+l ,=朋+2显然。当I(疗一一万/万l越小,效率J7越高。综上所述,实际分块过程中应遵循使尽可能多的处理器处理规模较大的数据子集的准则,避 免出现某一个处理器的负载过大的情况。4静态负载平衡算法实现及实验结果4.1一维分

15、解优先的规则分块算法由前面的结论:p>5时,maX(口,>maX(口,>口,所以对于一般的边缘数据通信问题。 采用三维分解优先的处理器分布方式。又三维问题任意划分时,立方体划分通信量最小,所以在进 行三维分解时,应按照三个方向网格点数的比例来分配处理器数。二维分解时也同样按照两个方向 网格点数的比例来分配处理器。由于本例题需要二维流水线并行,所以处理器分布方式最好采用一 维分解优先,再考虑二维和三维分解的方式。在实际的分块过程中需要考虑到下面两个问题:(1每 个处理器包含的各方向的网格点数要有门槛值,各方向的网格点数至少要大于10,这样才能保证并 行粒度相对于通信量足够大.不

16、会影响到并行程序的整体效率;(2根据3.3的结论.我们应使尽可 能多的处理器处理规模较大的数据子集.避免出现某一个处理器的负载比平均负载大很多的情况, 所以在分块完成后,要有定量的检查,划分给每个处理器数的负载与平均负载之差要有限制。即: I, . . .、,. .IlUD啤一,D口%w/,D口l<占。如果有处理器不能满足要求.则将给定的处理器总数递减,再重新 分块(这里取F0.1。一维分解优先的规则分块算法具体步骤如下:I把物理块按从小到大的顺序排列,先处理较小的物理块,如果它们的数据子集之和小于等于 平均负载,则把它们组合在一个处理器中:II其余物理块从负载平衡的角度出发,按网格数比

17、例分配处理器数,每个物理块分配的处理 器数如果不是整数,需要取整,处理器数小的向上取整,处理器数多的向下取整:为保持总数不变,修改最大块的处理器数:IV试探一维分解.如果划分后该方向网格点数>规定的最小网格点数,则一维分解; V如果该物理块分配奇数个处理器且一维分解不成功.将处理器数调整为偶数:VI试探:二维分解,如果划分后该方向网格点数>=规定的最大网格点数,则:二维分解; VII一维、二:维分解不成功的,则三维分解。如前所述,若某物理块分配奇数个处理器,则将处理器数调整为偶数再进行-j维分解或二=三维 分解。由3.1和3.2的结论,:维分解或三维分解应按照对应方向网格点数的比例

18、来分配处理器,如65果遇到不能整除的情况，则根据该物理块网格数大小将分配的处理器数进行递增或递减，然厉再重 新进行二维分解或三维分解。因为这样的整除问题的存在，分块后的处理器总数肯可能小丁给定的 处理器数。 基于自动重分的不规则分块算法 当处理器数小于物理块数时我们发现一维分解优先的规则分块算法效果不理想，如果物理 块大小相差很大而处理器数很少。规则分块算法就不能满足负载平衡的要求了。下面本文提出一种 新的基于自动重分的不规则分块算法，这种分块算法适用面很广，可以用在同构机群上和异构机群 上。该算法的基本原理是将超出平均负载的最大块进行重新分割以满足负载平衡的要求，因而更为 灵活，在处理器数少

19、于物理块数时也可以达到较优的负载平衡。这种不规则分块算法在通信效率上 可能略逊于上一种方法，但是当处理器数少的时候通信开销相对于计算量来说比较小，较优的负载 平衡可以弥补带来的额外通信开销，所以这种算法是可行的。基于自动重分的不规则分块算法的具 体步骤如下： 初始化： 计算平均处理时间： ，矿 乙。 ，曲 嗽 粕一弱 其中：为每块的网格数：为每个网格的运算量（用浮点操作数表示）；只眦为每个处理 器每秒的浮点操作数。 假设所有处理器都分配一个非常小的小块计算得到初始的雕： ；宰形 胖 主循环： ，（尸，） 眦 其中，（，）表示分配给该处理器的所有小块的集合。 如果有小块未分配，则将最大的未分配的

20、小块分配给最先完成计算的处理器； 如果（，腓乙（唧），则沿最长边按比例分裂此块以满足雕乙，将剩下的部分 小块划分为未分配小块，将该小块划分给该处理器。 在实际的处理过程中。我们采用两种分块算法相结合的方式。如果给定的处理器数少于或接 近物理块数，则采用基于自动重分的不规则分块算法，如果给定的处理器数大于物理块数则采用 一维分解优先的规则分块算法。另外，在基于自动重分的不规则分块算法的具体实现中，也应考虑 到上面提到的两个问题：（）每个处理器包含的各方向的网格点数要有门槛值，但沿最长边方向按 比例分裂小块时。可能难以满足各方向的网格点数至少要大于的条件所以这种情况下将小块沿 最长边方向和次长边方

21、向按比例进行二维分裂将剩下的三个部分小块划分为未分配小块，将分裂 后的小块划分给该处理器。（）划分给每个处理器的负载与平均负载之差要有限制。如果有一个处 理器彳能满足要求。则修改哪的值调用主循环重新分块直至满足负载，衡要求。 实验结果 本例题主要模拟某超燃冲压发动机的流场情况，控制方程是考虑化学非衡反应的非定常二三 维方程： 望望塑丝坠塑堕 二一一一一二 缸 叙 包 砂 砂 式中：，办，声，卢，）是守恒变量；、是无粘通量向量； 、，、，是粘通量向量：是化学反应源项。 计算方法采用隐式有限体积法，具有二排边缘通信和二元递归计算特点。本题的计算规模比 较大计算区域划分为个区，对应块不同类型的网格。网格具体情况见表、分 别表示三个方向的最大网格点数。 表 物理块号 计算区域的具体情况 物理块号 一 引 引 钾 “ 定义衡量负载平衡的标准矽型铲，其中是处理器数，。为每个处理器分得的 网格数，（）。采用上面提出的