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

负载平衡是影响并行计算性能的重要因素。针对多块结构网格,给出了一种改进的多层次图剖分负载平衡方法。该方法设计了新的网格剖分算法,采用改进的子块分裂方法与图剖分算法的循环调用实现结构对接网格剖分,并通过建立不同物体重叠网格间的连接关系,实现了结构重叠网格的负载平衡。采用2个典型算例对方法进行了对比验证,数值结果表明,子块分裂方法对剖分结果具有重要影响,采用循环调用算法及改进的子块分裂方法能有效地实现计算负载均衡及通信量优化,同时显著减少了网格块数及因虚网格导致的内存需求,有利于提高并行效率。该负载平衡方法与网格拓扑无关,适用于多块结构对接网格及重叠网格,且整体型剖分方式对于多块结构重叠网格具有更好的剖分效果。

Load balance strategy based on graph partition for multiblock structured grids

Load balance is of significance to the performance of parallel computing.Aiming at a good load balance with as less blocks as possible in parallel computing,an enhanced partitioning strategy based on multilevel graph partition is proposed for multiblock structured grids,including a recursive partition algorithm and an improved subgrid-splitting method,and then extended to the overlapping multiblock grids by establishing the connection between subgrids of different bodies hereafter.Two typical applications,covering the 1 to 1 coincident grid and the overlapping grid,are implemented to compare the behaviors of various partition strategies,as regards load balance,edge-cut and block numbers.Results demonstrate that the subgrid-splitting method is critical to structured grids,and partitioning over-lapping grid integrally is obviously a better alternative.Specifically,the new partitioning strategy shows a good performance in load balance and communication overheads,and meanwhile decreases the amount of blocks enormously as well as the memory requirement caused by the ghost cell of edge-cuts,leading to a better parallel efficiency.The enhanced partition strategy is applicable to both the 1 to 1 coincident grids and overlapping grids.