The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions
Loading...
Authors
Armstrong, Robert
Hensgen, Debra
Kidd, Taylor
Subjects
Advisors
Date of Issue
1998
Date
Publisher
IEEE
Language
Abstract
In this paper we study the performance of four mapping algorithms. The four algorithms include two naive ones: Opportunistic Load Balancing (OLB), and Limited Best Assignment (LBA), and two intelligent greedy algorithms: an O(nm) greedy algorithm, and an O(n 2 m) greedy algorithm. All of these algorithms, except OLB, use expected run-times to assign jobs to machines. As expected run-times are rarely deterministic in modern networked and server based systems, we first use experimentation to determine some plausible run-time distributions. Using these distributions, we next execute simulations to determine how the mapping algorithms perform. Performance comparisons show that the greedy algorithms produce schedules that, when executed, perform better than naive algorithms, even though the exact run-times are not available to the schedulers. We conclude that the use of intelligent mapping algorithms is beneficial, even when the expected time for completion of a job is not deterministic.
Type
Conference Paper
Description
In 7th IEEE Heterogeneous Computing Workshop (HCW ’98)
Series/Report No
Department
Identifiers
NPS Report Number
Sponsors
Funding
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.