Static and Dynamic Processor Scheduling Disciplines in Heterogeneous Parallel Architectures

Most parallel jobs cannot be fully parallelized. In a homogeneous parallel machine-one in which all processors are identical-the serial fraction of the computation has to be executed at the speed of any of the identical processors, limiting the speedup that can be obtained due to parallelism. In a h...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 1995-07, Vol.28 (1), p.1-18
Main Authors: Menasce, D.A., Saha, D., Porto, S.C.D., Almeida, V.A.F., Tripathi, S.K.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Information retrieval. Graph
Software
Software engineering
Theoretical computing
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Most parallel jobs cannot be fully parallelized. In a homogeneous parallel machine-one in which all processors are identical-the serial fraction of the computation has to be executed at the speed of any of the identical processors, limiting the speedup that can be obtained due to parallelism. In a heterogeneous architecture, the sequential bottleneck can be greatly reduced by running the sequential part of the job or even the critical tasks in a faster processor. This paper uses Markov chain based models to analyze the performance of static and dynamic processor assignment policies for heterogeneous architectures. Parallel jobs are assumed to be described by acyclic directed task graphs. A new static processor assignment policy, called Largest Task First Minimum Finish Time (LTFMFT), is introduced. The analysis shows that this policy is very sensitive to the degree of heterogeneity of the architecture, and that it outperforms all other policies analyzed. Three dynamic assignment disciplines are compared and it is shown that, in heterogeneous environments, the disciplines that perform better are those that consider the structure of the task graph, and not only the service demands of the individual tasks. The performance of heterogeneous architectures is compared with cost-equivalent homogeneous ones taking into account different scheduling policies. Finally, static and dynamic processor assignment disciplines are compared in terms of performance.
ISSN:0743-7315
1096-0848
DOI:10.1006/jpdc.1995.1085