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

doi:10.7527/S1000-6893.2016.0230

Abstract

Abstract:

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.

Key words: computational fluid dynamics, parallel computing, structured grids, load balance, graph partition

CLC Number:

V211.3

LIU Hongkang, YAN Chao, LIN Boxi, ZHAO Yatian. Load balance strategy based on graph partition for multiblock structured grids[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2017, 38(5): 120558-120558.

References

[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.

Load balance strategy based on graph partition for multiblock structured grids

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Jianling QIAO, Zhonghua HAN, Yulin DING, Wenping SONG, Bifeng SONG. Effects of stratified atmospheric turbulence on farfield sonic boom propagation [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(2): 626350-626350.
[2]	XIAHOU Tangfan, CHEN Jiangtao, SHAO Zhidong, WU Xiaojun, LIU Yu. Model validation metrics for CFD numerical simulation under aleatory and epistemic uncertainty [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 25716-025716.
[3]	WANG Yupeng, TIAN Wenpeng, SONG Pengfei, XIA Feng, FENG Jianmin. Research and verification of comprehensive acceleration technology for civil aircraft full-scale fatigue test [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 224919-224919.
[4]	CHEN Guangqiang, DOU Guohui, WEI Haogong, ZOU Xin, LI Qi, LIU Zhou, ZHOU Weijiang. Air data sensing technology of Mars probe [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 626619-626619.
[5]	YI Jianmiao, DENG Feng, QIN Ning, LIU Xueqiang. Fast prediction of transonic flow field using deep learning method [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(11): 526747-526747.
[6]	WANG Di, QIAN Zhansen, LENG Yan. High-order scheme discretization of sonic boom propagation model based on augmented Burgers equation [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(1): 124916-124916.
[7]	BAO Jun, WANG Yu, NIU Qian, ZHU Xidong, CHENG Jianjie. Influencing parameters and film flow mechanism of spray droplet impacting liquid film [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(S1): 726360-726360.
[8]	CHEN Jianqiang, WU Xiaojun, ZHANG Jian, LI Bin, JIA Hongyin, ZHOU Naichun. FlowStar: General unstructured-grid CFD software for National Numerical Windtunnel (NNW) Project [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(9): 625739-625739.
[9]	DUAN Yanhui, ZHOU Xin, GAO Shijiexi, LIN Jinxing, ZHANG Huaibao, WANG Guangxue. Two-step optimal strategy for load balancing of structured grid [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(9): 625751-625751.
[10]	LIU Jun, WEI Yanxin, CHEN Jie. Tie-dye algorithm based on finite difference method for unstructured grid [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(7): 124557-124557.
[11]	LI Zuobiao, WEN Fengbo, TANG Xiaolei, SU Liangjun, WANG Songtao. Prediction of single-row hole film cooling performance based on deep learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524331-524331.
[12]	YANG Xiaofeng, LI Qin, DU Yanxia, LIU Lei, GUI Yewei. Progress in numerical research on interface heterogeneous catalysis of hypersonic vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(12): 625908-625908.
[13]	CHANG Siyuan, BAI Xiaozheng, LIU Jun. A two-dimensional shock wave pattern recognition algorithm based on cluster analysis [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(8): 123626-123626.
[14]	HAN Zhonghua, XU Chenzhou, QIAO Jianling, LIU Fei, CHI Jiangbo, MENG Guanyu, ZHANG Keshi, SONG Wenping. Recent progress of efficient global aerodynamic shape optimization using surrogate-based approach [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 623344-623344.
[15]	CHANG Siyuan, BAI Xiaozheng, CUI Xiaoqiang, LIU Jun. An improved unsteady shock-fitting algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(2): 123498-123498.