Research And Design On An Efficient Load Balancing Algorithm

Distributed parallel computing can provide relatively cheap and powerful processing capacity which has recently gained extensive attention in the field of both research and application. The load balancing is one of the important factors influencing the performance of distributed parallel computing. And, the efficiency of load balancing strategy is directly related to the implementation effect of distributed parallel system.As a key technology to improve the performance of distributed parallel computing, load balancing is a NP problem. So the distributed parallel system can only get the approximate solution, but cannot obtain the optimum load balancing. The characteristics of the distributed parallel system also further increase the difficulty of load balancing:firstly, the heterogeneity of nodes and tasks in the distributed parallel computing system increases the difficulty of the load balancing strategy; secondly, the heterogeneity of network also poses challenges to the load balancing strategy; thirdly, the expanding of distributed parallel system demands load balancing strategy with good scalability; finally, the load balancing strategy needs to adapt to the distributed parallel system dynamic. All above lead to some problems of the existed research on load balancing in task scheduling model, complexity, information acquisition, data transmission costs and the strategy of dynamic adjustment.According to the above problems, the task scheduling model is designed on the basis of existing research, and a simple and efficient load balancing algorithm is presented based on this model.(1) Task scheduling model is designed according to the characteristics of the distributed parallel environment. First of all, task model which contains tasks needing to process data and pure computing tasks is abstracted. Secondly, the more actual system structure is abstracted; processor model with the consideration of the dynamic and heterogeneity of node is designed based on the influence of the historical value; standard network distance is proposed with the purpose of dealing with network dynamic and calculating communication overhead better, and the communication model, including LAN and WAN, is designed based on this concept. Finally, task organization form, migration pattern, and the problems which need to be solved by the load balancing algorithm in this thesis are given according to the designed model.(2) An efficient load balancing algorithm is presented based on the designed task scheduling model. The load balancing process is divided into the process of Assignment and Redistribution. Simple and high accuracy task scheduling algorithm (SHAS) and dynamic load adjustment algorithm based on performance gains factor (DLAPGF) are proposed respectively aiming at the process of Assignment and Redistribution. SHAS combines the on-demand and periodic way of information collection, and uses the way of piggybacking information in order to further improve the accuracy of the information. Based on this and considering communication overload and data transmission cost, the last completion time (LCT) of task is more accurately calculated, and then the Min-Min algorithm is used to schedule new tasks under the guidance of the presented principle of the task scheduling. DLAPGF obtains the goal of load balancing by analysis. Partner nodes are determined based on standard network distance, of which information is obtained by the improved mutual information feedback method. Eventually, the concept of performance gains factor is presented based on node last completion time (NLCT), and then based on this concept the exchange and transfer operation are used for dynamic task adjustment process. Simultaneously, SHAS and DLAPGF deal with system dynamic to a certain extent.(3) Based on the four performance indicators including completion time of the system, system balance, data transmission costs and message overhead, the respectively experimental results of SHAS and DLAPGF show the effectiveness of the proposed algorithm. Meanwhile, the influence of parameter and system dynamic on the efficiency of algorithm is verified.