Browse Prior Art Database

Dynamic Load Balancing

IP.com Disclosure Number: IPCOM000114013D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 89K

Publishing Venue

IBM

Related People

Altevogt, P: AUTHOR [+2]

Abstract

Described is an algorithm for dynamic loadbalancing of a class of geometric parallel synchronous algorithms on (heterogeneous) Multiple Instruction stream, Multiple Data stream (MIMD) systems. The algorithm is based on a dynamic partitioning of the domain of the algorithm, taking into account the actual processor resources of the various processors of the MIMD system.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Dynamic Load Balancing

      Described is an algorithm for dynamic loadbalancing of a class
of geometric parallel synchronous algorithms on (heterogeneous)
Multiple Instruction stream, Multiple Data stream (MIMD) systems.
The algorithm is based on a dynamic partitioning of the domain of the
algorithm, taking into account the actual processor resources of the
various processors of the MIMD system.

      Implementing a synchronous parallel algorithm on a
heterogeneous MIMD system (e.g., on a cluster of different
workstations), a loadbalancing between the processors of the system
(taking into account the actual resources being available on each
node of the system) turns out to be crucial, because the processor
with the least resources determines the speed of the complete
algorithm.

      The heterogenity of the MIMD system may not only result because
of heterogeneous hardware resources, but also due to a heterogeneous
use of homogeneous hardware resources (e.g., on a workstation
cluster, there may exist several serial tasks running on some of the
workstations of the cluster for some time in addition to the parallel
application; this results in a temporary heterogenity of the cluster,
even if the workstations of the cluster are identical).  This kind of
heterogenity can in general only be detected during the runtime of
the parallel algorithm.

      Therefore, the usual approach of geometric parallelization to
parallelize algorithms by a static decomposition of a domain into
subdomains and associating...