Affordable Access

Publisher Website

Performance Bounds on Multiprocessor Scheduling Strategies for Chain Structured Programs

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
23
Issue
1
Identifiers
DOI: 10.1006/jpdc.1994.1125
Disciplines
  • Computer Science
  • Design
  • Mathematics

Abstract

Abstract In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is NP-hard to find an optimal schedule, and very little is known on how close the heuristic solutions get. In order to obtain nontrivial performance bounds, this study focuses on a restricted class of parallel programs, viz., chain structured programs. The major result is a theorem stating that if certain program parameters are known the execution time of the optimal schedule can be calculated within a factor of 2, even though the optimal schedule is unknown. Using a previously developed tool, one can extract the necessary parameters from a parallel program. This technique makes it possible to compare the execution time for different scheduling strategies with the optimal case. The technique used for calculating the performance bounds gives important hints on how to design efficient scheduling algorithms for chain structured programs.

There are no comments yet on this publication. Be the first to share your thoughts.