Heuristic methods for dynamic load balancing in a message-passing supercomputer

Author

Xu, Jian ; Hwang, Kai

Author_Institution

IBM Corp., San Jose, CA, USA

fYear

1990

fDate

12-16 Nov 1990

Firstpage

888

Lastpage

897

Abstract

The scheme is based on using easy-to-implement heuristics and a variable threshold in migrating processes among the multicomputer nodes. It uses a distributed control over all processor nodes as coordinated by a host processor. Four heuristic methods for process migration are presented, which are distinguished by choosing different policies for process migration and threshold update. A parallel simulator (PSIM) with distributed load balancers is developed on an iPSC/2 hypercube system. The load balancing scheme is evaluated to determine the effects of various system utilizations, load imbalances, communication and migration overheads, and multicomputer sizes. The relative merits of the four methods are revealed under various multicomputer conditions

Keywords

distributed processing; parallel processing; performance evaluation; resource allocation; scheduling; virtual machines; PSIM; distributed control; distributed load balancers; dynamic load balancing; iPSC/2 hypercube; load imbalances; message passing multicomputer; message-passing supercomputer; migration overheads; parallel event drives simulator; parallel simulator; process migration; system utilizations; threshold update; variable threshold; Costs; Degradation; Delay; Distributed computing; Distributed control; Hypercubes; Load management; Load modeling; Message passing; Supercomputers;

fLanguage

English

Publisher

ieee

Conference_Titel

Supercomputing '90., Proceedings of

Conference_Location

New York, NY

Print_ISBN

0-8186-2056-0

Type

conf

DOI

10.1109/SUPERC.1990.130115

Filename

130115