Empirical comparison of heuristic load distribution in point-to-point multicomputer networks

Dirk C. Grunwald, Bobby A.A. Nazief, Daniel A. Reed

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

To benefit from parallel computers, programs must be partitioned into units that work in parallel. Once partitioned, these units, called processes, tasks or threads, must be assigned to specific processors for execution. On shared memory architectures, this is termed scheduling, while on multicomputer systems, it is called load distribution, distinguishing it from any local scheduling used on individual nodes. We compared several load placement algorithms using instrumented programs and synthetic program models. Salient characteristics of these program traces (total computation time, total number of messages sent and average message size) span two orders of magnitude. Load distribution algorithms determine the initial placement for processes, a precursor to the more general problem of load redistribution. We simulated a modern architecture with point-to-point communication; however, our findings should apply to wormhole networks as well. We found that information is usually better than inference for driving process placement. The strategies we examine use load or status information to select placement locations; this information is explicitly disseminated and also piggybacked on normal communication. We found that extant point-to-point networks reduce the rate of information dissemination because transiting messages are ignored by intermediate nodes. From these studies, we have concluded that desirable workload distribution strategies will place new processes globally, rather than locally, to spread processes rapidly, but that local information should be used to refine global placement.

Original languageEnglish
Title of host publicationArchitectures, Software Tools and Other General Issues
EditorsDavid W. Walker, Quentin F. Stout
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages984-993
Number of pages10
ISBN (Electronic)0818621133, 9780818621130
DOIs
Publication statusPublished - 1 Jan 1990
Event5th Distributed Memory Computing Conference, DMCC 1990 - Charleston, United States
Duration: 8 Apr 199012 Apr 1990

Publication series

NameProceedings of the 5th Distributed Memory Computing Conference, DMCC 1990
Volume2

Conference

Conference5th Distributed Memory Computing Conference, DMCC 1990
Country/TerritoryUnited States
CityCharleston
Period8/04/9012/04/90

Fingerprint

Dive into the research topics of 'Empirical comparison of heuristic load distribution in point-to-point multicomputer networks'. Together they form a unique fingerprint.

Cite this