Research On Load Balancing For Peta-scale Distributed Systems

With half a century of efforts designed,computer hardware has been incredibly improved and tends to be low cost and high performance.For example,IBM has revealed an ambitious program to expand the horizons of supercomputing with the goal of creating a system called Blue Gene P targeting lpetaflops of peak performance with processing nodes to achieve 256K.So it will make the world's top computer useless without a reasonable task of scheduling strategy in such peta-scale distributed systems.Under the auspices of National Natural Science Foundation,the works in the paper focus on load balancing for peta-scale distributed systems.Its main tasks are as follows:At first,the paper analyses the limitations of centralized and distributed strategies. Centralized strategies include GreedyLB,RefineLB,OrbLB and GreedyCommlLB. Distributed strategies include Neighborhood Averaging and Work-Stealing.Experimental results prove that the centralized strategies above have difficulties in memory cost and overhead of load balancing,but distributed strategies have problems in low CPU utilization.Secondly,the paper analyses the communication cost and overhead of load balancing of the strategies for peta-scale distributed system which includes hierarchical strategy and hybrid strategy.But all the strategies above are predicated on the assumption that delays are deterministic. In actuality,delays are random in such communication media,especially in the case of peta-scale distributed system.This is attributable to uncertainties associated with the amount of traffic,congestion,and other unpredictable factors within the network.But the existent strategies perform poorly to predict the communication delay.During the reasons above,according to the feature of the random delay,the paper proposes randomness based hierarchical load balancing framework in conclusion.The framework has three features:(Ⅰ) Proposing hierarchical framework to decrease the overhead of load balancing.(Ⅱ) Considering the heterogeneity in the processing rates of the nodes as well as the randomness in the delays imposed by the communication medium.(Ⅲ) Proposing the generalized neural network(GNN) policy based on intelligent neurons for delay forecast in distributed system,this method provides a solution for the communication based load balancing strategies.Our simulation results prove that this framework is fit for peta-scale distributed system compared with the centralized framework as well as the distributed framework.