Impact of task duplication on static-scheduling performance in multiprocessor systems with variable execution-time tasks
- 1 June 1990
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 18 (3b) , 439-446
- https://doi.org/10.1145/77726.255186
Abstract
The problem of scheduling a set of partially ordered tasks on a nonpreemptive multiprocessor system of identical processors assuming that the execution time of some tasks can vary within a set of known values is studied in an effort to construct a more realistic static schedule.A new heuristic algorithm (CP/MISF/TD) based on task duplication is proposed. The effectiveness of the algorithm is proved by comparing the results obtained for a wide variety of task graphs with the ones obtained by applying the classical list scheduling algorithms which consider fixed time tasks.Keywords: Static scheduling, List scheduling, Heuristic algorithms, Task duplication, Multiprocessor systems.Keywords
This publication has 6 references indexed in Scilit:
- Heuristic functions for static task allocationMicroprocessing and Microprogramming, 1989
- Determining average program execution times and their variancePublished by Association for Computing Machinery (ACM) ,1989
- Heuristic algorithms for task assignment in distributed systemsIEEE Transactions on Computers, 1988
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- Deterministic Processor SchedulingACM Computing Surveys, 1977
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961