Strategies for dynamic load balancing on highly parallel computers

Author

Willebeek-LeMair, Marc H. ; Reeves, Anthony P.

Author_Institution

IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA

Volume

4

Issue

9

fYear

1993

fDate

9/1/1993 12:00:00 AM

Firstpage

979

Lastpage

993

Abstract

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge - the accuracy of each balancing decision, and 2) overhead - the amount of added processing and communication incurred by the balancing process. All five strategies have been implemented on an Inter iPSC/2 hypercube

Keywords

parallel processing; performance evaluation; resource allocation; synchronisation; Inter iPSC/2 hypercube; dynamic load balancing; highly parallel computers; load balancing communication overhead; multicomputer systems; Application software; Concurrent computing; Costs; Distributed control; Hypercubes; Load management; Load modeling; Local area networks; Multiprocessing systems; Scholarships;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.243526

Filename

243526