基于图剖分的多块结构网格负载平衡方法
Load balance strategy based on graph partition for multiblock structured grids
Received date: 2016-06-27
Revised date: 2016-08-08
Online published: 2016-08-12
负载平衡是影响并行计算性能的重要因素。针对多块结构网格，给出了一种改进的多层次图剖分负载平衡方法。该方法设计了新的网格剖分算法，采用改进的子块分裂方法与图剖分算法的循环调用实现结构对接网格剖分，并通过建立不同物体重叠网格间的连接关系，实现了结构重叠网格的负载平衡。采用2个典型算例对方法进行了对比验证，数值结果表明，子块分裂方法对剖分结果具有重要影响，采用循环调用算法及改进的子块分裂方法能有效地实现计算负载均衡及通信量优化，同时显著减少了网格块数及因虚网格导致的内存需求，有利于提高并行效率。该负载平衡方法与网格拓扑无关，适用于多块结构对接网格及重叠网格，且整体型剖分方式对于多块结构重叠网格具有更好的剖分效果。
刘宏康 , 阎超 , 林博希 , 赵雅甜 . 基于图剖分的多块结构网格负载平衡方法[J]. 航空学报, 2017 , 38(5) : 120558 -120558 . DOI: 10.7527/S1000-6893.2016.0230
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.
[1] CHIEN Y P, CARPENTER F, ECER A, et al. Load-balancing for parallel computation of fluid dynamics problems[J]. Computer Methods in Applied Mechanics & Engineering, 1995, 120(1-2):119-130.
[2] RANTAKOKKO J. A framework for partitioning structured grids with inhomogeneous workload[J]. Parallel Algorithms and Applications, 1998, 13(2):135-151.
[3] MILLER G L, TENG S H, VAVASIS S A. A unified geometric approach to graph separators[C]//Proceedings of 32nd Annual Symposium of Foundations of Computer Science. Piscataway, NJ:IEEE Press, 1991:538-547.
[4] SIMON H. Partitioning unstructured problems for parallel processing[J]. Computing Systems in Engineering, 1991, 11(4):135-148.
[5] KARYPIS G, KUMAR V. METIS:Unstructured graph partitioning and sparse matrix ordering system, Technical Report[R]. Minneapolis:University of Minnesota, 1995.
[6] BOMAN E G, ÇATALYVREK U V, CHEVALIER C, et al. The Zoltan and Isorropia parallel toolkits for combinatorial scientific computing:Partitioning, ordering and coloring[J]. Scientific Programming, 2012, 20(2):129-150.
[7] YTTERSTRÖM A. A tool for partitioning structured multiblock meshes for parallel computational mechanics[J]. International Journal of High Performance Computing Applications, 1997, 11(4):336-343.
[8] RANTAKOKKO J. Partitioning strategies for structured multiblock grids[J]. Parallel Computing, 2000, 26(12):1661-1680.
[9] AHUSBORDE E, GLOCKNER S. A 2D block-structured mesh partitioner for accurate flow simulations on non-rectangular geometries[J]. Computers & Fluids, 2011, 43(1):2-13.
[10] DJOMEHRI M J, BISWAS R. Performance enhancement strategies for multi-block overset grid CFD applications[J]. Parallel Computing, 2003, 29(11-12):1791-1810.
[11] 司海青, 王同光. 多块并行计算中负载平衡策略及时间成本估算方法[J]. 航空学报, 2007, 28(S1):57-61. SI H Q, WANG T G. Load balancing strategy for parallel calculation and time cost estimation[J]. Acta Aeronautica et Astronautica Sinica, 2007, 28(S1):57-61 (in Chinese).
[12] 李桂波, 杨国伟. 基于多块结构网格的并行计算及负载平衡研究[J]. 宇航学报, 2011, 32(6):1224-1230. LI G B, YANG G W. Study on parallel computation and load balance strategy based on multiblock structured grid[J]. Journal of Astronautics, 2011, 32(6):1224-1230 (in Chinese).
[13] 许正, 李津, 朱自强. 网络连接机群上CFD计算的一种负载平衡方法[J]. 航空学报, 2005, 26(2):129-134. XU Z, LI J, ZHU Z Q. Load balancing strategy for parallel CFD calculation on cluster[J]. Acta Aeronautica et Astronautica Sinica, 2005, 26(2):129-134 (in Chinese).
[14] BARNARD S T, SIMON H D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[J]. Concurrency Practice & Experience, 1994, 6(6):101-117.
[15] KARYPIS G, KUMAR V. A fast and high quality multi-level scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 2006, 20(1):359-392.
[16] KIRICHENKO A V, MASON K, STRAUME M, et al. An efficient K-way graph partitioning algorithm for task allocation in parallel computing systems[C]//Proceedings of the First International Conference on Systems Integration. Piscataway, NJ:IEEE Press, 1990:748-751.
[17] GOURDAIN N, GICQUEL L, MONTAGNAC M, et al. High performance parallel computing of flows in complex geometries:I. Methods[J]. Computational Science & Discovery, 2009, 339(1):104-124.
[18] PELLEGRINI F. Graph partitioning based methods and tools for scientific computing[J]. Parallel Computing, 1997, 23(1-2):153-164.
[19] 刘巍, 张理论, 王勇献, 等. 计算空气动力学并行编程基础[M]. 北京:国防工业出版社, 2013:250-255. LIU W, ZHANG L L, WANG Y X, et al. Foundations of computational aerodynamics parallel programming[M]. Beijing:National Defense Industry Press, 2013:250-255 (in Chinese).
[20] DJOMEHRI M J, BISWAS R, LOPEZ-BENITEZ N. Load balancing strategies for multi-block overset grid applications[C]//Proceedings of the ISCA 18th International Conference Computers and Their Applications, 2003:63-71.
[21] COOK P, MCDONALD M, FIRMIN M. Airfoil REA2822 pressure distributions, and boundary layer and wake measurements, experimental data base for counter program assessment:AGARD Report AR 138[R]. Paris:AGARD, 1979.
[22] 2nd AIAA CFD Drag Prediction Workshop.[2016-06-27]. http://aaac.larc.nasa.gov/ts-ab/cfdlarc-dpw/June 2003.
/
| 〈 |
|
〉 |
CJA