A scalable task duplication based scheduling algorithm for heterogeneous systems
- 8 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Optimal scheduling of tasks represented by a directed acyclic graph (DAG) onto a set of homogeneous processors is a strong NP-hard problem. In this paper, we introduce a scalable scheduling scheme called STDS for heterogeneous systems. This implies that tasks could potentially have different run times on different processors. The complexity of STDS is. (V 2) where v is the number of nodes in the task graph. Schedule length is primarily reduced by selected task duplication. Current task duplication based scheduling schemes are mostly done for homogeneous systems. Comparing the performance of STDS with BIL, another scheduling scheme for heterogeneous systems, it is observed that STDS obtained speed-ups of 6 to 40 generating shorter schedules when sufficient duplication can be carried out.Keywords
This publication has 13 references indexed in Scilit:
- A new heuristic algorithm based on GAs for multiprocessor scheduling with task duplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal task assignment in heterogeneous distributed computing systemsIEEE Concurrency, 1998
- Optimal scheduling algorithm for distributed-memory machinesIEEE Transactions on Parallel and Distributed Systems, 1998
- A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory SystemsJournal of Parallel and Distributed Computing, 1997
- A New Approach to Scheduling Parallel Programs Using Task DuplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- 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
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990