Research About Dynamic Load Balancing Algorithm Based On Hierarchical Strategy

With the development of computer and network technology, large-scale parallel distributed processing system has been extensively applied. For one distributed system, how to dynamically assign and schedule the tasks among the nodes, that is, dynamic load balancing, has much influence to the performance of system. Load balancing has a lot of research value in theory and application. People have noticed it for a long while. In recent years many researcher of some countries have engaged in it and put forward series of dynamic load balancing algorithms. Because those algorithms didn't solve the existing problems completely so we must do the research for dynamic load balancing of distributed system more extensively. Many aspects about load balancing are particularly discussed, including concept, classification, characteristic, algorithm mechanism, driven strategy, difficulty, approach, etc. Research actuality for load balancing is summarized and many existing static and dynamic load balancing algorithms are compared. Those algorithms are pointed their advantages and disadvantages. On this base, from the network architecture, that is, topology, some logic alteration is done in common mesh, hypercube and net topology. By certain principle physical topology is partitioned into many regions and one information central node is selected for every region. Those information central nodes form the second logic regions and information central node is selected again if necessary, and so on. Finally logic hierarchical structure is come into being on physical topology finally. By reasoning and computing to approve that communication on network can spread from local region to total topology by the way of partition and many basic communication costs are reduced.On the base of hierarchical way, a new dynamic load balancing algorithm is proposed. The algorithm can solve some disadvantages such as lack of stability, lack of agility, lack of general in existing algorithms. On this base, one algorithm mechanism base of prediction is proposed. The mechanism can be applied in load balancing algorithm to make the load information on node known exactly and betimes. The mechanism also provides better basis for the transfer among the nodes. Then one dynamic load balancing model basing prediction and using hierarchical way is built. The main thinking of algorithm is by local regions'optimization to achieve whole system's near optimization. The relationship between tasks and the difference of nodes in system are considered. The algorithm improves the traditional driven strategy and use new schedule rules among tasks. On base of reducing basic communication costs, the algorithm reduces much additional costs of system and enhances the efficiency of itself. The main characteristics of the algorithm are:(1) Self-adaptive and parameter variational. The algorithm uses not single driven strategy but adjust loading threshold and parameters dynamically in the process of system running. Users can select the value of parameters according to the demand for system then obtain excellent performance.(2) System stable and no thrash. The use of local region in algorithm make the transfer for tasks among the nodes occurs in local regions firstly and transfer between the regions occurs if necessary. Besides the algorithm improve the former driven strategy to make the transfer must from over loading nodes to light loading nodes. This method's purpose is strong. It avoids some transfer of low efficiency and unnecessary disturbance to nodes.(3) Simple and practical. The algorithm adopts not schedule method with many costs such as AI theory but the thinking of from local optimization to whole optimization and one extreme schedule method with pertinence. The algorithm only increases some space costs and the costs of communication route for tasks transfer. The additional costs are few.(4) General. The algorithm can be applied on isomorphic and isomerous distributed systems composed of most common mesh and hypercube. It can be applied on general net topology.Some experiments for comparison and instances for analysis are done to validate the exactness and availability of hierarchical strategy load balancing algorithm. Since the hierarchical strategy load balancing algorithm can indeed solve the problem of load balancing for distributed systems available and flexible. The algorithm makes up some defects in existing algorithms.