An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems
- 20 June 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 14 (6), 533-544
- https://doi.org/10.1109/tpds.2003.1206502
Abstract
Scheduling precedence constrained task graphs, with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication heuristics are more effective, in general, for fine grain task graphs and for networks with high communication latencies. However, most of the available duplication algorithms are designed under the assumption of unbounded availability of fully connected processors, and lie in a high complexity range. Low complexity optimal duplication algorithms work under restricted cost and/or shape parameters for the task graphs. Further, the required number of processors grows in proportion to the task-graph size significantly. An improved duplication strategy is proposed that works for arbitrary task graphs, with a limited number of interconnection-constrained processors. Unlike most other algorithms that replicate all possible parents/ancestors of a given task, the proposed algorithm tends to avoid redundant duplications and duplicates the nodes selectively, only if it helps in improving the performance. This results in lower duplications and also lower time and space complexity. Simulation results are presented for clique and an interconnection-constrained network topology with random and regular benchmark task graph suites, representing a variety of parallel numerical applications. Performance, in terms of normalized schedule length and efficiency, is compared with some of the well-known and recently proposed algorithms. The suggested algorithm turns out to be most efficient, as it generates better or comparable schedules with remarkably less processor consumption.Keywords
This publication has 28 references indexed in Scilit:
- An optimal scheduling algorithm based on task duplicationIEEE Transactions on Computers, 2002
- Efficient local search far DAG schedulingIEEE Transactions on Parallel and Distributed Systems, 2001
- Optimal scheduling algorithm for distributed-memory machinesIEEE Transactions on Parallel and Distributed Systems, 1998
- Using duplication for scheduling unitary tasks on m processors with unit communication delaysTheoretical Computer Science, 1997
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1996
- Task clustering and scheduling for distributed memory parallel architecturesIEEE Transactions on Parallel and Distributed Systems, 1996
- DSC: scheduling parallel tasks on an unbounded number of processorsIEEE Transactions on Parallel and Distributed Systems, 1994
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- Hypertool: a programming aid for message-passing systemsIEEE Transactions on Parallel and Distributed Systems, 1990
- A taxonomy of scheduling in general-purpose distributed computing systemsIEEE Transactions on Software Engineering, 1988