国家数值风洞（NNW）工程旨在发展完全自主知识产权的计算流体力学（CFD）软件，结构网格负载平衡问题研究是该工程中的一个重要组成部分。本文发展了两步优化策略以求解结构化网格的负载平衡问题。第1步优化采用传统的贪婪算法，完成对大块网格的剖分和以进程计算时间为指标的网格块分配；第2步采用遗传算法（GA），目标函数兼顾进程计算时间和通信时间，在第1步优化结果的基础上，对网格块在进程上的分配开展二次优化。为准确计算GA的目标函数，构建了一套计算时间和通信时间的建模方法，包括样本生成、模型建立和模型验证，整体方法具有一定的通用性。根据负载平衡问题以及两步优化策略的特点，对GA的编码、交叉、变异和种群初始化进行了研究，详细分析了交叉操作的递归问题及解决方法。算例验证说明建立的进程计算时间和通信时间模型具有较高的计算精度，能够用于GA的目标函数计算；两步优化策略能够在第1步优化的基础上进一步改善优化结果，从而减少CFD问题的整体计算时间，对于计算量巨大的工程问题具有较大的实用价值。
Load balancing of structured grids composes an important part of the National Numerical Windtunnel (NNW) project which aims to design software of Computational Fluid Dynamics (CFD) with independent intellectual property right. This paper develops a two-step optimization strategy to solve the problems in load balancing of structured grids. The first step adopts the traditional greedy algorithm to split the large blocks of grids and assign the blocks based on computational time in each process. The second step adopts the Genetic Algorithm (GA). On the basis of the first step optimization solution, the second optimization can obtain better solution considering both the computational time and the communication time calculated by linear models. To improve the accuracy of the models, one of the key characteristics of the GA, a series of modeling methods are proposed for computational time and communication time, including the sample generation, model building and model validation. According to the characteristics of load balancing and the two-step optimization strategy, the paper studies the coding, crossover, mutation and population initialization of the GA, and analyzes the recursion problem of crossover operation. The verification shows that the models of computational time and communication time established in the paper can be used to compute the objective function of the GA with adequate accuracy. The cases of load balancing show that the two-step optimization strategy can further improve the optimization solutions in the first step, thereby reducing the overall computational time of certain CFD problems.
[1] 陈坚强. 国家数值风洞工程(NNW)关键技术研究进展[J/OL]. 中国科学:技术科学, (2021-04-28)[2021-05-08]. https://kns.cnki.net/kcms/detail/11.5844.TH.202104-28.0914.006.html. CHEN J Q. Advances in the key technologies of Chinese National Numerical Wind Tunnel Project[J/OL]. Scientia Sinica Technologica, (2021-04-28)[2021-05-08]. https://kns.cnki.net/kcms/detail/11.5844.TH.202104-28.0914.006.html (in Chinese).
[2] 赵钟, 张来平, 何磊, 等. 适用于任意网格的大规模并行CFD计算框架PHengLEI[J]. 计算机学报, 2019, 42(11):2368-2383. ZHAO Z, ZHANG L P, HE L, et al. PHengLEI:A large scale parallel CFD framework for arbitrary grids[J]. Chinese Journal of Computers, 2019, 42(11):2368-2383(in Chinese).
[3] 汤继飞, 李思, 张理论, 等. 面向并行负载平衡的数据剖分技术[J]. 计算机应用研究, 2010, 27(11):4015-4019. TANG J F, LI S, ZHANG L L, et al. Research of data partitioning technique for parallel load balancing[J]. Application Research of Computers, 2010, 27(11):4015-4019(in Chinese).
[4] BERGER M J, BOKHARI S H. A partitioning strategy for nonuniform problems on multiprocessors[J]. IEEE Transactions on Computers, 1987, C-36(5):570-580.
[5] FARHAT C, LESOINNE M. Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics[J]. International Journal for Numerical Methods in Engineering, 1993, 36(5):745-764.
[6] 刘胤田, 唐常杰, 曾涛, 等. 基于空间填充曲线的数据分发区域匹配[J]. 系统仿真学报, 2007, 19(4):780-783, 804. LIU Y T, TANG C J, ZENG T, et al. Implementation of data distribution region matching based on space-filling curve[J]. Journal of System Simulation, 2007, 19(4):780-783, 804(in Chinese).
[7] MEYERHENKE H, MONIEN B, SCHAMBERGER S. Graph partitioning and disturbed diffusion[J]. Parallel Computing, 2009, 35(10-11):544-569.
[8] BARNARD S T. PMRSB:Parallel multilevel recursive spectral bisection[C]//Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (CDROM). New York:ACM Press, 1995:267-276.
[9] LENG M. Multilevel-based graph partitioning and its application in VLSI design[D]. Shanghai:Shanghai University, 2008.
[10] CATALYUREK U V, BOMAN E G, DEVINE K D, et al. Hypergraph-based dynamic load balancing for adaptive scientific computations[C]//2007 IEEE International Parallel and Distributed Processing Symposium. Piscataway:IEEE Press, 2007:367-380.
[11] SCHLOEGEL K, KARYPIS G, KUMAR V. Multilevel diffusion schemes for repartitioning of adaptive meshes[J]. Journal of Parallel and Distributed Computing, 1997, 47(2):109-124.
[12] KARYPIS G, SCHLOEGEL K, KUMAR V. ParMETIS parallel graph partitioning and sparse matrix ordering library, Version 3.1[M]. Minneapolis:University of Minnesota Press, 2003.
[13] Sandia National Laboratories. Zoltan:Parallel partitioning, load balancing and data-management services[EB/OL]. (2010-11-04)[2021-05-08]. http://www.cs.sandia.gov/Zoltan.
[14] 刘宏康, 阎超, 林博希, 等. 基于图剖分的多块结构网格负载平衡方法[J]. 航空学报, 2017, 38(5):120558. LIU H K, YAN C, LIN B X, et al. Load balance strategy based on graph partition for multiblock structured grids[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(5):120558(in Chinese).
[15] 李桂波, 杨国伟. 基于多块结构网格的并行计算及负载平衡研究[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).
[16] 唐波. 大规模多区结构网格CFD并行计算中的负载平衡算法研究[D]. 长沙:国防科学技术大学, 2013. TANG B. Load balancing algorithm in the large-scale CFD applications with multi-zone structured grids[D]. Changsha:National University of Defense Technology, 2013(in Chinese).
[17] SCHLOEGEL K, KARYPIS G, KUMAR V. A new algorithm for multi-objective graph partitioning[C]//Euro-Par'99 Parallel Processing, 1999:322-323.
[18] KARYPIS G. Multi-constraint mesh partitioning for contact/impact computations[C]//Proceedings of the 2003 ACM/IEEE Conference on Supercomputing. New York:ACM Press, 2003:15-21.
[19] XIA W J, WU Z M. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J]. Computers & Industrial Engineering, 2005, 48(2):409-425.
[20] VICINI A, QUAGLIARELLA D. Airfoil and wing design through hybrid optimization strategies[J]. AIAA Journal, 1999, 37(5):634-641.
[21] DUAN Y H, CAI J S, LI Y Z. Gappy proper orthogonal decomposition-based two-step optimization for airfoil design[J]. AIAA Journal, 2012, 50(4):968-971.
[22] 茆诗松, 王静龙, 濮晓龙. 高等数理统计[M]. 北京:高等教育出版社, 2006:262-294. MAO S X, WANG J L, PU X L. Advanced mathematical statistics[M]. Beijing:Higher Education Press, 2006:262-294(in Chinese).
[23] LAFLIN K, BRODERSEN O, RAKOWITZ M, et al. Summary of data from the second AIAA CFD drag prediction workshop (invited)[C]//42nd AIAA Aerospace Sciences Meeting and Exhibit. Reston:AIAA, 2004.
[24] 王小平, 曹立明. 遗传算法——理论、应用与软件实现[M]. 西安:西安交通大学出版社, 2002:123-127. WANG X P, CAO L M. Genetic algorithm——Theory, application and software implementation[M]. Xi'an:Xi'an Jiaotong University Press, 2002:123-127(in Chinese).
CJA