LOAD BALANCING ALGORITHMS FOR AN EXTENDED HYPERCUBE

Reduction of the execution time of a job through equitable distributio n of work load among the processors in a distributed system is the goa l of load balancing. In the paper, performance of static and dynamic l oad balancing algorithms for the extended hypercube, is discussed. Thr eshold algorithms are very well-known algorithms for dynamic load bala ncing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hie rarchical interconnection network of the extended hypercube is suitabl e for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the al gorithm for an extended hypercube is compared with those for mesh and binary hypercube networks.