Dynamic Load Balancing on Irregular Networks Embedded in Hypercubes

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


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


In this study a dynamic load balancing technique for het erogenous distributed systems is presented.This is a two phase technique. Firstly the system is modeled as a hy percube.This is done only once, unless there is a change in the topology. In the second phase load balancing is per formed using Positional Scan Load Balancing algorithm. The PSLB algorithm is a decenterlised and fully distributed load balancing algorithm which uses the scan operator (also known as parallel prefix), as means for obtaining necessary information for each system node. Based on this informa tion each node calculates its future load. A novel aspect of this technique is that, in the case of load migration, each node knows exactly where to send its extra workload. The communication involved is only among neighbours. Both phases were analysed theoretically and experimentally.The experimental results show the effectiveness of the tech nique. In addition, the cross over point where load bal ancing becomes effective is also determined.

Important Links:

Go Back