Performance Comparison of Dynamic Load-Balancing Strategies for Distributed
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:
Copyright © 1998 by Computer Science Department. UAB