一维高效动态负载平衡方法：多层均权法

提出了一个适合同构和异构并行计算环境的高效一维动态负载平衡方法；多层均权法，并成功地解决了多物质非定常流体力学Lagrange法并行数值模拟过程中的动态负载不平衡问题。文中给出了详细的理论分析以及两台并行机上结合某实际物理问题组织的并行数值实验。

High Efficient One Dimensional Dynamical Load Balancing Method: Multilevel Averaging Weight Method

A Multilevel Averaging Weight (MAW) dynamic load balancing method suitable for both synchronous and heterogeneous parallel computing environments is presented in this paper to solve the one-dimensional dynamic load imbalance problems arising from the parallel Lagrange numerical simulation of multiple matters non-steady fluid dynamics. At first, a one-dimensional load imbalance model is designed to simplify the theoretical analysis for the robustness of MAW method. For this model, the defined domain is uniformly differenced into grid cells, and every grid cells is assumed to be processed with different CPU time. Given P processors, it is required to find the efficient domain decomposition strategy which can keep the loads among different subdomains assigned to individual processors balanced. Secondly, we present a load balancing method, Averaging Weight (AW) method. The theoretical analysis shows that, while the number the processors is equal to 2, AW method is very efficient to adjust the system form a very imbalanced state to a very balanced state in 2—4 iterations. It is unfortunately that this conclusion can not be generalized to be suitable for larger number of processors. In further, inherited form the idea of the AW method, we designed another load balancing method, Multilevel Averaging Weight method. The similar theoretical analysis shows that this method can adjust the load to be balanced in ClogP iterations for any number of processors, where P is the number of processors and C is the iterations using AW method while P=2. This result is usually enough to efficiently track fluctuations in the load imbalance as the parallel numerical simulation progresses. Moreover, both AW and MAW method are all suitable for both homogeneous and heterogeneous parallel computing environments. Thirdly, we organize the numerical experiments for three types of load balancing models, and gain the same conclusions coincided with that of the theoretical analysis. At last, we apply the MAW method to the load balancing problems arising from the parallel Lagrange numerical simulation of multiple matters non-steady fluid dynamics, and improve the performance by 11%—17% for different grid scales and different number of processors of two parallel computers. One of the parallel computers is PC-Cluster with 9 Pentium-II 400MHz connected with 100Mbps switch, and another is some shared memory symmetric multiprocessors (SMP) with 12 CPUs.