Load Balancing for Parallel Loops in Workstation Clusters
Abstract
Load imbalance is a serious impediment to achieving good performance in
parallel processing. Global load balancing schemes are not adequately
manage to balance parallel tasks generated from a single application.
Dynamic loop scheduling methods are known to be useful in balancing parallel
loops on shared-memory multiprocessor machines. However, their centralized
nature causes a bottleneck for the relatively small number of processors in
workstation clusters because of order-of-magnitude differences in
communications overheads. Moreover, improvements of basic loop scheduling
methods have not dealt effectively with irregularly distributed workloads in
parallel loops, which commonly occur in applications for workstation clusters.
In this paper, we present a new decentralized balancing method for parallel
loops on workstation clusters.
(Also cross-referenced as UMIACS-TR-96-6)