Improving scheduling of tasks in a heterogeneous environment
Top Cited Papers
- 28 June 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 15 (2), 107-118
- https://doi.org/10.1109/tpds.2004.1264795
Abstract
Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We introduce a task duplication-based scheduling algorithm for network of heterogeneous systems (TANH), with complexity O(V/sup 2/), which provides optimal results for applications represented by directed acyclic graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing "best imaginary level scheduling (BIL)" scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. We have shown to provide substantial improvement over existing work on the task duplication-based scheduling algorithm (TDS).This publication has 22 references indexed in Scilit:
- On supernode transformation with minimized total running timeIEEE Transactions on Parallel and Distributed Systems, 1998
- On exploiting task duplication in parallel program schedulingIEEE Transactions on Parallel and Distributed Systems, 1998
- Optimal scheduling algorithm for distributed-memory machinesIEEE Transactions on Parallel and Distributed Systems, 1998
- 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 Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- A taxonomy of scheduling in general-purpose distributed computing systemsIEEE Transactions on Software Engineering, 1988
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier BV ,1979