Research On Load Balancing Algorithms Based On Graph Partitioning And Graph Layout

With the rapid development of high performance computer systems, parallel computing has become a basic supporting technology for scientific and engineering computing. How to solve the load balancing problem efficiently is one of the most fundamental issues in the research of parallel computing. When the scale of parallel simulations goes up to hundreds of processors, the load balancing problem becomes the critical factor that influences the performance of parallel computing.The load balancing problem has been widely studied in recent years. However, as a result of the development of high performance computer systems and the increasing need from real-world applications, new issues about load balancing problems appear in the world of parallel computing and challenge those existing algorithms. First, new parallel algorithms introduce new computational structures, which demand new load balancing algorithms. What's more, many important applications (such as weapon physics, weather forecast, hydrodynamics and inertial confinement fusion) require simulations on thousands of processors, and such massive computations often lead to severe load imbalance. Many existing load balancing algorithms fail to cope with this grand challenge. Hence, designing highly-efficient load balancing algorithms which can scale up to thousands of processors is an important and challenging task in the study of parallel computing.The performance of parallel computing strongly depends on the load distribution of parallel algorithms. Therefore, it is proper to divide parallel algorithms into categories. According to their load distribution, parallel algorithms can be categorized as and modeled by static load model, dynamic load model, multi-constraint model and other models. Based on different models, efficient load balancing algorithms can be constructed respectively. This dissertation has conducted a systematic research on the designing of load balancing algorithms which can scale up to thousands of processors. The main contributions are as follows:1. A load balancing algorithm, based on minimum linear arrangement, is designed for static load model. Comparing to other algorithms, our algorithm is fast and efficient. Numerical results on 1024 processors show that our algorithm is one of the best load balancing algorithms.2. Aiming at the dynamic load imbalance problem which often exists in complex numerical simulation, we propose a new graph layout model based on dynamic load model. Furthermore, we design a new load balancing algorithm based on our model. This algorithm overcomes the limitation that algorithms based on graph layout cannot control migration cost explicitly. We experimentally evaluate the effectiveness of our model and our algorithms on a variety of synthetically generated problems.3. Applications modeled by multi-constraint load model include parallel solution of multi-physics and multi-phase computations, which underlie many existing and emerging large-scale scientific simulations. We propose an iterative one-dimensional multi-constraint load balancing algorithm, of which convergence theorem is established. Numerical results on 1024 processors show the effectiveness of our algorithm. By combining with graph layout algorithm, our algorithm can handle general multi-constraint load models, which extends the range of use for load balancing algorithm based on graph layout.4. Structured Adaptive Mesh Refinement (SAMR) methods are playing an increasing role in tackling difficult scientific applications. Because of the multi-scale nature of the algorithm, the load balancing problem of SAMR is even more difficult. We present a model that characterizes the computational structure of parallel SAMR programs. Based on this model, we construct a new load balancing algorithm: MGP-LMCR Experiments on synthetically generated problems show our algorithm can reduce communication cost between levels and migration cost between time steps.