NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Performance tradeoffs in 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 sub-optimal, (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 other three strategies.
Document ID
19860014876
Document Type
Preprint (Draft being sent to journal)
Authors
Iqbal, M. A. (NASA Langley Research Center Hampton, VA, United States)
Saltz, J. H. (NASA Langley Research Center Hampton, VA, United States)
Bokhart, S. H. (NASA Langley Research Center Hampton, VA, United States)
Date Acquired
September 5, 2013
Publication Date
March 1, 1986
Subject Category
SYSTEMS ANALYSIS
Report/Patent Number
NASA-CR-178073
ICASE-86-13
NAS 1.26:178073
Funding Number(s)
CONTRACT_GRANT: NAS1-17070
CONTRACT_GRANT: NAS1-18107
PROJECT: RTOP 505-31-83-01
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 19860014876.pdf STI