A Task Duplication Based Optimal Scheduling Algorithm for Variable Execution Time Tasks
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 52-56
- https://doi.org/10.1109/icpp.1994.47
Abstract
Efficient scheduling algorithm is one of the key factors in determining the performance of distributed memory machines. This paper presents an enhanced Search and Du plication Based Scheduling (SDBS) algorithm which car schedule Directed Acyclic Graphs (DA Gs) with variable execution time tasks. Since the DAGs are based on data dependencies of the tasks, the control dependencies are clustered within each node. If the node encapsulates a loop or an if-then-else kind of statement, then assuming the execution times to be fixed would not be appropriate. It is assumed in this paper that the execution time varies between two time estimates. The complexity of this scheduling algorithm is in 0(V 4- E), where V is the number of node,- and E is the number of edges in the task graph. This algo rithm is based on some realistic assumptions and generates an optimal time schedule. If the assumptions cannot be completely satisfied then the algorithm provides a schedule which is close to optimal. The performance in these cases has been obtained using extensive simulation work which indicate the closeness of the results.Keywords
This publication has 9 references indexed in Scilit:
- SDBS: a task duplication based optimal scheduling algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Threshold Scheduling Strategy for Sisal on Distributed-Memory MachinesJournal of Parallel and Distributed Computing, 1994
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- C.P.M. Scheduling with Small Communication Delays and Task DuplicationOperations Research, 1991
- Impact of task duplication on static-scheduling performance in multiprocessor systems with variable execution-time tasksPublished by Association for Computing Machinery (ACM) ,1990
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Multiprocessor scheduling with interprocessor communication delaysOperations Research Letters, 1988