Efficient Two-Pass Dynamic Load Balancing for Computational Clusters

M.W. Akhtar and M.-T. Kechadi (Ireland)


Paralle Algortihms and Architectures, Heterogeneous Dis tributed Systems, Dynamic Load Balancing, Hypercube, Graph Embedding.


This paper presents and evaluates a new load balancing technique for computational clusters. The technique is dynamic, non-preemptive, adaptive, and fully distributed. The technique is a two step strategy; firstly, it maps the given cluster having an irregular topology into a hyper cube and then balances the load among the nodes using our PSLB algorithm. The technique collects the informa tion on the system in a distributed fashion. On the basis of this information, each node locally calculates the amount of workload that should be kept and/or received and the amount of work that should be sent. This technique is sim ple, efficient, and does not introduce a considerable over head as shown in the experimental results.

Important Links:

Go Back