Synchronous load balancing in hypercube multicomputers with faulty nodes

This paper presents a new dynamic load-balancing algorithm for hypercube multicomputers with faulty nodes. The emphasis in our method is on obtaining global load information and performing task migration using "short paths" in a synchronous manner so that a minimal amount of communication overhead is required. To accomplish this, we present an algorithm for constructing a new logical topology from a hypercube topology with faulty nodes. This new topology is used to obtain the global load information and to perform task migration. Simulation results are used to evaluate the performance of our dynamic load balancing method when compared with previous methods. (C) 1999 Academic Press.