Research On Load Balancing Algorithms Of The Structured Multi-block Grid

In recent years,the field of high performance computing is developing rapidly.Existing supercomputers have more processor cores and larger internal cluster communication bandwidth,resulting in more powerful computing power and faster communication speed.Numerical simulation in scientific and engineering computing is a critical type of application in the field of high performance computing.Among them,the load balancing efficiency and communication overhead determine the qualit y of the numerical simulation program and the execution speed of the program.In order to achieve better numerical simulation quality and speed up the execution of numerical simulation programs,all processor cores in high performance computing systems should be as load balanced as possible.This means that in the application type of the structured multi-block grid,the computational load in the structured multi-block grid can be mapped as evenly as possible across all processor cores for parallel computing.At the same time,the communication overhead among all processor cores should be as small as possible.In the load balancing problem of the structured multi-block grid,the load value among different grid blocks,the quantitative relationship between the grid block and the processor core,and the mapping strategy from the grid block to the processor core are the main factors that affect the load balancing efficiency and the communication overhead.Since most of the existing algorithms do not fully consider these three factors,Most of them have problems such as excessive communication overhead.For the first two factors,this paper proposes a structured multi-block grid block segmentation algorithm.The algorithm first introduces two evaluation criteria,the grid block optimal computation load interval and the grid block computation load lower bound,to evaluate the co mputational load of each grid block.Secondly,an improved rectangular partitioning algorithm is implemented in the algorithm.According to results of the two evaluation criteria,the above structured multi-block grid block segmentation algorithm adopts the improved rectangular partitioning algorithm as the main segmentation algorithm and the classical recursive edge bisection algorithm as the auxiliary segmentation algorithm to optimize the original structured multi-block grid,so as to solve the problems caused by the first two factors.For the challenge of the third factor,and considering the irregular data dependence between different grid blocks,this paper utilizes the data structure of the graph to model the structured multi-block grid,and then adopts the graph partitioning algorithm to map all grid blocks to processors.Combining the above-mentioned structured multi-block grid block segmentation algorithm with graph segmentation algorithm,this paper proposes a load balancing algorithm for structured multi-block grid numerical simulation application.Compared with the existing algorithms,the load balancing algorithm proposed in this paper not only pays attention to load balancing efficiency,but also further optimizes communication overhea d,which can achieve relatively good load balancing efficiency and relatively low communication overhead.Experiments show that for structured multi-block grid numerical simulation applications,the structured multi-block grid load balancing algorithm pro posed in this paper can achieve ideal load balancing efficiency and relatively low communication overhead among processor cores in high performance computing systems,thus has great practical value.