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

doi:10.7527/S1000-6893.2016.0230

流体力学与飞行力学

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

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

刘宏康, 阎超, 林博希, 赵雅甜

北京航空航天大学航空科学与工程学院, 北京 100083

收稿日期:2016-06-27 修回日期:2016-08-08 出版日期:2017-05-15 发布日期:2016-08-12
通讯作者: 阎超 E-mail:yanchao@buaa.edu.cn

Load balance strategy based on graph partition for multiblock structured grids

LIU Hongkang, YAN Chao, LIN Boxi, ZHAO Yatian

School of Aeronautic Science and Engineering, Beihang University, Beijing 100083, China

Received:2016-06-27 Revised:2016-08-08 Online:2017-05-15 Published:2016-08-12

摘要/Abstract

摘要：

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

关键词: 计算流体力学, 并行计算, 结构网格, 负载平衡, 图剖分

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

中图分类号:

V211.3

刘宏康, 阎超, 林博希, 赵雅甜. 基于图剖分的多块结构网格负载平衡方法[J]. 航空学报, 2017, 38(5): 120558-120558.

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.

参考文献

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

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

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

Load balance strategy based on graph partition for multiblock structured grids

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	乔建领, 韩忠华, 丁玉临, 宋文萍, 宋笔锋. 分层大气湍流场对远场声爆传播的影响[J]. 航空学报, 2023, 44(2): 626350-626350.
[2]	夏侯唐凡, 陈江涛, 邵志栋, 吴晓军, 刘宇. 随机和认知不确定性框架下的CFD模型确认度量综述[J]. 航空学报, 2022, 43(8): 25716-025716.
[3]	罗佳杰, 宋文滨. 层流机翼及其增升装置嵌套协同优化方法[J]. 航空学报, 2022, 43(8): 125377-125377.
[4]	陈广强, 豆国辉, 魏昊功, 邹昕, 李齐, 刘周, 周伟江. 火星探测器大气数据测量方法[J]. 航空学报, 2022, 43(3): 626619-626619.
[5]	杨鲤铭, 吴杰, 董昊, 杜银杰. 基于速度空间非结构网格和守恒修正的改进离散速度方法[J]. 航空学报, 2022, 43(12): 627033-627033.
[6]	杨体浩, 白俊强, 段卓毅, 史亚云, 邓一菊, 周铸. 喷气式客机层流翼气动设计综述[J]. 航空学报, 2022, 43(11): 527016-527016.
[7]	奕建苗, 邓枫, 覃宁, 刘学强. 快速预测跨声速流场的深度学习方法[J]. 航空学报, 2022, 43(11): 526747-526747.
[8]	王迪, 钱战森, 冷岩. 广义Burgers方程声爆传播模型高阶格式离散[J]. 航空学报, 2022, 43(1): 124916-124916.
[9]	鲍俊, 王瑜, 牛潜, 朱锡冬, 程建杰. 喷雾液滴撞击液膜影响参数及流动机理分析[J]. 航空学报, 2021, 42(S1): 726360-726360.
[10]	王子航, 吕宏强. 基于CFD高精度算法的雷电电磁场研究[J]. 航空学报, 2021, 42(S1): 726366-726366.
[11]	陈坚强, 吴晓军, 张健, 李彬, 贾洪印, 周乃春. FlowStar:国家数值风洞(NNW)工程非结构通用CFD软件[J]. 航空学报, 2021, 42(9): 625739-625739.
[12]	段焰辉, 周鑫, 高诗婕茜, 林锦星, 张怀宝, 王光学. 基于两步优化策略的结构网格负载平衡[J]. 航空学报, 2021, 42(9): 625751-625751.
[13]	任玉新, 王乾, 潘建华, 章雨思, 黄乾旻. 构建非结构网格高精度有限体积方法的新途径[J]. 航空学报, 2021, 42(9): 625783-625783.
[14]	刘君, 魏雁昕, 陈洁. 基于非结构网格有限差分法的扎染算法[J]. 航空学报, 2021, 42(7): 124557-124557.
[15]	李左飙, 温风波, 唐晓雷, 苏良俊, 王松涛. 基于深度学习的单排孔气膜冷却性能预测[J]. 航空学报, 2021, 42(4): 524331-524331.