基于图剖分的多块结构网格负载平衡方法

《基于图剖分的多块结构网格负载平衡方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、航空学报ActaAerOnauticaetAstrOnauticaSinicaMay252017Vol38No．5SSN1000．6893CN11-1929／Vhttp：Hhkxb．buaaeducahkxb@buaa．edu．cn基于图剖分的多块结构网格负载平衡方法刘宏康，阎超“，林博希，赵雅甜北京航空航天大学航空科学与工程学院，北京100083摘要：负载平衡是影响并行计算性能的重要因素。针对多块结构网格，给出了一种改进的多层次图剖分负载平衡方法。该方法设计了新的网格剖分算法，采用改进的子块分裂方法与图剖分算法的循环调用实现结构对

2、接网格剖分，并通过建立不同物体重叠网格间的连接关系，实现了结构重叠网格的负载平衡。采用2个典型算例对方法进行了对比验证，数值结果表明，子块分裂方法对剖分结果具有重要影响，采用循环调用算法及改进的子块分裂方法能有效地实现计算负载均衡及通信量优化，同时显著减少了网格块数及因虚网格导致的内存需求，有利于提高并行效率。该负载平衡方法与网格拓扑无关，适用于多块结构对接网格及重叠网格，且整体型剖分方式对于多块结构重叠网格具有更好的剖分效果。关键词：计算流体力学；并行计算；结构网格；负载平衡；图剖分中图分类号：V211．3文献标识码：A文章编号：

3、i000—6893(2017)05—120558—10计算流体力学(ComputationalFluidDynam—ics，CFD)中通常需要将物理流场离散化为计算网格，其中，多块结构网格(单块为结构网格但各块间的连接关系可以为一一对应或重叠)技术扮演着重要角色，在航空航天、气象预测等领域应用广泛。随着T程问题日益复杂化，高精度的数值模拟需求对计算格式及网格分辨率提出了更高要求，进而导致计算量急剧增加。受限于串行程序的计算效率，并行计算是解决上述问题的重要手段，而影响并行性能的关键因素之一是计算负载平衡的实现。当前的CFD并行计算普

4、遍采用“单程序多数据”模式，需要将计算网格映射到分布式存储系统的各个进程上。在复杂实际问题中，计算区域一般由多个大小不等的子块组成，且存在相互间流场信息传递的复杂问题，同时伴随着并行规模的增加，这给结构网格的负载平衡带来了困难。因此，发展适用于复杂实际问题的结构网格负载平衡方法，对实现计算负载均衡及进程间通信成本优化具有重要意义。现阶段国内外对负载平衡方法的研究较为丰富，提出了一系列启发性算法，如贪婪算法[1]、谱方法[，]、几何剖分方法[33及图剖分方法E4]等，并已集成至通用软件包，如文献[5—6]等。上述算法对非结构网格具有天

5、然适用性，但无法直接适用于结构网格，且在该方面的研究也相对有限。国外方面，YtterstrOmL7j最早提出了递归边对分(Re—cursiveEdgeBisection，REB)方法进行网格细分以实现负载平衡，而Rantakokko【83进一步发展了多层次剖分的负载平衡方法，在一定程度上减少了网格块数。Ahusborde和Glockner[91重点研究了非规则矩形流场的子块分割算法并进行了流场求解，Djomehri和Biswas[1叩则采用REB方法进行了重叠网格的子块分割，并基于Overflow求解器开展求解，对比不同算法并行效果

6、。国内方面，收稿日期：2016—06—27；退修日期：2016—07—25；录用日期：2016—08—08；网络出版时间：2016．08．1210：59网络出版地址：WWWcnki．net／kcms／detail／111929．V201608121059．004html*通讯作者．E-mail：yanchao@buaaedu．CR现角榕武：朝宏康．阗超。林博希。等．基f函劫分的多块结构两格负载平衡方法!J]．航空学报，2017，38(5)：120558．L

7、UHK．YANc，LINBx，eta1．Loadbalancestrateg

8、ybasedongraphpartitionformultiblockstructuredgridsEJJActaAeronauticaetAstro．nauticaSinica，2017，38(5)j120558120558．1航空学报司海青和王同光[1妇提出了一种无子块分割的负载剖分算法，李桂波和杨国伟口21则采用遗传优化算法研究了负载与通信的并行影响，许正等n朝采用负载再分配策略来实现动态负载平衡，并提出近似均分子块分割方法。上述研究往往以对接结构网格为主，难以适用于多块结构重叠网格，并且由于对网格块数的关注不足，存在子块分割

9、过多或剖分效果受网格拓扑、进程数影响较大的缺陷。本文针对负载平衡方法进行了研究，提出了一种改进的结构网格负载平衡方法。该方法采用网格子块分割及图剖分的循环调用思路，同时改进了子块分裂方法，并通过建立重叠边界关联，将其拓展至多块结构重叠