A semi distributed load balancing scheme for large multicomputer systems

The authors propose a semi distributed approach for load balancing in large parallel and distributed systems. The proposed scheme is a two level hierarchical scheme which partitions the interconnection structure of a multiprocessor system into independent symmetric regions. Interconnection structures belonging to the classical infinite families of distance transitive graphs are considered. The proposed scheme uses the partitioning property of these graphs by employing Hadamard matrices. The performance of systems consisting of these interconnection structures with varying sizes is evaluated through simulation and compared with a fully distributed scheme. Simulation results indicate that the performance of the proposed scheme improves with the increase in system size