Abstract: 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.

Key words: load-balancing, greedy algorithm, genetic algorithm, structured grids, National Numerical Windtunnel (NNW) Project