基于两步优化策略的结构网格负载平衡

国家数值风洞（NNW）工程旨在发展完全自主知识产权的计算流体力学（CFD）软件，结构网格负载平衡问题研究是该工程中的一个重要组成部分。本文发展了两步优化策略以求解结构化网格的负载平衡问题。第1步优化采用传统的贪婪算法，完成对大块网格的剖分和以进程计算时间为指标的网格块分配；第2步采用遗传算法（GA），目标函数兼顾进程计算时间和通信时间，在第1步优化结果的基础上，对网格块在进程上的分配开展二次优化。为准确计算GA的目标函数，构建了一套计算时间和通信时间的建模方法，包括样本生成、模型建立和模型验证，整体方法具有一定的通用性。根据负载平衡问题以及两步优化策略的特点，对GA的编码、交叉、变异和种群初始化进行了研究，详细分析了交叉操作的递归问题及解决方法。算例验证说明建立的进程计算时间和通信时间模型具有较高的计算精度，能够用于GA的目标函数计算；两步优化策略能够在第1步优化的基础上进一步改善优化结果，从而减少CFD问题的整体计算时间，对于计算量巨大的工程问题具有较大的实用价值。

Two-step optimal strategy for load balancing of structured grid

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.