Task scheduling in multiprocessing systems
- 1 December 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Computer
- Vol. 28 (12) , 27-37
- https://doi.org/10.1109/2.476197
Abstract
The complex problem of assigning tasks to processing elements in order to optimize a performance measure has resulted in numerous heuristics aimed at approximating an optimal solution. This article addresses the task scheduling problem in many of its variations and surveys the major solutions. The scheduling techniques we discuss might be used by a compiler writer to optimize the code that comes out of a parallelizing compiler. The compiler would produce grains of sequential code, and the optimizer would schedule these grains such that the program runs in the shortest time.Keywords
This publication has 10 references indexed in Scilit:
- An Optimal Algorithm for Scheduling Interval Ordered Tasks with Communication on N ProcessorsJournal of Computer and System Sciences, 1995
- Parallax: a tool for parallel program schedulingIEEE Parallel & Distributed Technology: Systems & Applications, 1993
- A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- PYRROSPublished by Association for Computing Machinery (ACM) ,1992
- Hypertool: a programming aid for message-passing systemsIEEE Transactions on Parallel and Distributed Systems, 1990
- An Almost-Linear Algorithm for Two-Processor SchedulingJournal of the ACM, 1982
- Scheduling Interval-Ordered TasksSIAM Journal on Computing, 1979
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- Optimal Sequencing of Two Equivalent ProcessorsSIAM Journal on Applied Mathematics, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961