A list scheduling algorithm for heterogeneous systems based on a critical node cost table and pessimistic cost table
Authors:
- 9 September 2016
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 29 (5)
Abstract
Summary: This paper presents a novel list‐based scheduling algorithm called Improved Predict Earliest Finish Time for static task scheduling in a heterogeneous computing environment. The algorithm calculates the task priority with a pessimistic cost table, implements the feature prediction with a critical node cost table, and assigns the best processor for the node that has at least 1 immediate successor as the critical node, thereby effectively reducing the schedule makespan without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real‐world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness, and frequency of the best result. The results demonstrate that the Improved Predict Earliest Finish Time algorithm outperforms the Predict Earliest Finish Time and Heterogeneous Earliest Finish Time algorithms in terms of the schedule length ratio, frequency of the best result, and robustness while maintaining the same time complexity.Keywords
Funding Information
- National Natural Science Foundation of China (61402183, 61070015)
This publication has 19 references indexed in Scilit:
- A Synthesized Heuristic Task Scheduling AlgorithmThe Scientific World Journal, 2014
- List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost TableIEEE Transactions on Parallel and Distributed Systems, 2013
- A high performance algorithm for static task scheduling in heterogeneous distributed computing systemsJournal of Parallel and Distributed Computing, 2008
- Scheduling algorithm based on critical tasks in heterogeneous environmentsJournal of Systems Engineering and Electronics, 2008
- Improving scheduling of tasks in a heterogeneous environmentIEEE Transactions on Parallel and Distributed Systems, 2004
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- On exploiting task duplication in parallel program schedulingIEEE Transactions on Parallel and Distributed Systems, 1998
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessorsIEEE 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 taxonomy of scheduling in general-purpose distributed computing systemsIEEE Transactions on Software Engineering, 1988