A task duplication based bottom-up scheduling algorithm for heterogeneous environments
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 12 pp.-160
Abstract
We propose a new duplication-based DAG scheduling algorithm for heterogeneous computing environments. Contrary to the traditional approaches, proposed algorithm traverses the DAG in a bottom-up fashion while taking advantage of task duplication and task insertion. Experimental results on random DAGs and three different application DAGs show that the makespans generated by the proposed DBUS algorithm are much better than those generated by the existing algorithms, HEFT, HCPFD and HCNF.Keywords
This publication has 13 references indexed in Scilit:
- Improving scheduling of tasks in a heterogeneous environmentIEEE Transactions on Parallel and Distributed Systems, 2004
- A high performance,low complexity algorithm for compile-time task scheduling in heterogeneous systems2004
- Scheduling directed a-cyclic task graphs on heterogeneous network of workstations to minimize schedule length2004
- A task duplication based scheduling algorithm with optimality condition in heterogeneous systems2003
- Estimating execution time for parallel tasks in heterogeneous processing (HP) environment2002
- Triplet: A clustering scheduling algorithm for heterogeneous systems2002
- Fast and effective task scheduling in heterogeneous systems2002
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environmentIEEE Transactions on Computers, 1999
- On exploiting task duplication in parallel program schedulingIEEE Transactions on Parallel and Distributed Systems, 1998