NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A comparative analysis of static and dynamic load balancing strategiesThe problem of uniformly distributing the load of a parallel program over a multiprocessor system was considered. A program was analyzed whose structure permits the computation of the optimal static solution. Then four strategies for load balancing were described and their performance compared. The strategies are: (1) the optimal static assignment algorithm which is guaranteed to yield the best static solution, (2) the static binary dissection method which is very fast but suboptimal, (3) the greedy algorithm, a static fully polynomial time approximation scheme, which estimates the optimal solution to arbitrary accuracy, and (4) the predictive dynamic load balancing heuristic which uses information on the precedence relationships within the program and outperforms any of the static methods. It is also shown that the overhead incurred by the dynamic heuristic is reduced considerably if it is started off with a static assignment provided by either of the three strategies.
Document ID
19870065368
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Iqbal, M. Ashraf
(NASA Langley Research Center Hampton, VA, United States)
Bokhari, Shahid H.
(NASA Langley Research Center; Institute for Computer Applications in Science and Engineering, Hampton, VA; University of Engineering and Technology, Lahorle, Pakistan)
Saltz, Joel H.
(NASA Langley Research Center; Institute for Computer Applications in Science and Engineering Hampton, VA, United States)
Date Acquired
August 13, 2013
Publication Date
January 1, 1986
Subject Category
Computer Programming And Software
Accession Number
87A52642
Funding Number(s)
CONTRACT_GRANT: NAS1-17070
CONTRACT_GRANT: NAS1-18107
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available