Dynamic Load Balancing In Parallel Computing On Heterogeneous System

Load balancing(LB) is an important technique for parallel computing. However, it is an insidious factor that could greatly impact the performance of a parallel algorithm. Actually, it is not a prerequisite component for a parallel application, and load imbalance is seldom detected in small test. As the explosive growth of data amount for sophisticated parallel application, the severe effects of load imbalance on parallel algorithms gradually emerge. The load balancing techniques have been extensively studied for e?cient utilization of computational resource in parallel and distributed system. Due to the design of parallel algorithm and the autonomy of parallel computing system, part of the computational units would be over-loaded while others are light-loaded. The aim of load balancing is to redistribute the workload among each computational unit, in order to accomplish the tasks over roughly the same time, which could significantly improve the entire performance.For the sake of higher performance, new cluster of machines would be added, merging with the former system to constitute a heterogeneous system. Indeed, different computational ability could appear in the same cluster, therefore, LB technique becomes particularly essential while running a parallel application on such a heterogeneous system.As the initial imbalance caused by the heterogeneous architecture, static load balancing(SLB) methods can no longer tackle this problem. Applying dynamic load balancing(DLB) algorithms is an alternative solution. In this paper, we proposed a stochastic method for load balancing in heterogeneous parallel computing, which could predict the status of computing system by learning the performance characteristics of the computational units, then make a decision on task transfer.Firstly, we define the DLB problem using stochastic process theory, transforming it into an optimization problem with appropriate constrain, which is given in the formal method. For the purpose of achieving the optimal solution, we introduce the probatilistic graphical model(PGM). By mapping the original problem to PGM, the optimization problem could be converted into a subproblem in PGM- parameter learning. In addition, the decision made for task transfer could be obtained by inference algorithms with respect to PGM.Secondly, based on the effective optimization model, we implemented a parallel version of this online learning algorithm to boost the performance without weakening the optimizing effect. Moreover, a stochastic diffusion protocol is adopted for messaging, in order to reduce the cost of feedback in online learning algorithm.Finally, several experiments on the proposed DLB algorithm were conducted using simulation. The effectiveness and efficiency of the model could be verified by analysing the experimental data.