Abstract
Wegman (1991) introduced a load balancing algorithm for use in parallel computing when the execution times of individual node tasks are not known apriori. This algorithm divides each node task into two subtasks—one of which is assigned immediately to a node and the other used to fill in idle time. Inherent in this algorithm is the selection of a load balancing parameter representing the “fraction” of each task initially assigned to a node. This paper studies the selection of this parameter as a function of the distribution of task execution times and the number of available processing nodes. Several criteria are considered: minimization of the total execution time, maximization of the improvement over sequential processing, and maximization of the improvement over parallel processing without further load balancing.
Keywords:
1This research was supported by the Virginia Center for Innovative Technology and Geodynamics Corporation
1This research was supported by the Virginia Center for Innovative Technology and Geodynamics Corporation
Notes
1This research was supported by the Virginia Center for Innovative Technology and Geodynamics Corporation