Performance Comparison of Dynamic Load-Balancing Strategies for Distributed Computing

A. Cortés, A. Ripoll, M.A. Senar and E. Luque

Abstract. Dynamic load balancing is essential for the efficient use of highly parallel systems when solving problems with unpredictable load estimates. We present a new fully distributed dynamic load-balancing algorithm for load balancing among the processors of an arbitrary interconnected network of processors. This algorithm called DASUD (Diffusion Algorithm Searching Unbalanced Domains) belongs to the nearest-neighbours class and operates in a diffusion scheme where a processor balances its load with all its neighbours. DASUD has been developed to solve the problems related to handle indivisible tasks and reduce load thrashing between neighbouring processors involved in the nearest-neighbour algorithms based on the diffusion approach. DASUD detects unbalanced domains and performs local exchange of load between processors to achieve global balancing. A set of experiments has been carried out to assess the effectiveness of DASUD in balancing the load in parallel systems. It has been evaluated by comparison with another well-known strategy from the literature, namely, the SID (Sender Initiated Diffusion) algorithm. The comparison was carried out by considering a large set of load distributions that exhibit different degrees of initial workload unbalancing as well as different shapes of workload unbalancing. These distributions were applied to ring, torus and hypercube topologies, and the number of processors ranged from 8 to 128. From these experiments we have observed that DASUD outperforms the other strategy used in the comparison as it provides the best trade-off between the balance degree obtained at the final state and the number of iterations required to reach such state. DASUD is able to coerce any initial load distribution into a highly balanced global state and also exhibits good scalability properties.

Key words. load balancing, nearest-neighbours algorithms.

Registration: PIRDI-7/98, October 1998.


Retrieve compressed postScript document (pirdi7.zip: 282558 bytes)
Copyright © 1998 by Computer Science Department. UAB