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.
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
.
DOI: 10.7527/S1000-6893.2021.25751
[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