Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jpdc.2005.01.002
Title: Iterative list scheduling for heterogeneous computing
Authors: Liu, G.Q.
Poh, K.L. 
Xie, M. 
Keywords: Heterogeneous computing systems
List scheduling
Randomly generated DAGs
Task scheduling
Issue Date: May-2005
Citation: Liu, G.Q., Poh, K.L., Xie, M. (2005-05). Iterative list scheduling for heterogeneous computing. Journal of Parallel and Distributed Computing 65 (5) : 654-664. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jpdc.2005.01.002
Abstract: Optimal scheduling of parallel applications on distributed computing systems represented by directed acyclic graph (DAG) is NP-complete in the general case. List scheduling is a very popular heuristic method for DAG-based scheduling. However, it is more suited to homogenous distributed computing systems. This paper presents an iterative list scheduling algorithm to deal with scheduling on heterogeneous computing systems. The main idea in this iterative scheduling algorithm is to improve the quality of the schedule in an iterative manner using results from previous iterations. The algorithm first uses the heterogeneous earliest-finish-time (HEFT) algorithm to find an initial schedule and iteratively improves it. Hence the algorithm can potentially produce shorter schedule length. The simulation results show that in the majority of the cases, there is significant improvement to the initial schedule. The algorithm is also found to perform best when the tasks to processors ratio is large. © 2005 Elsevier Inc. All rights reserved.
Source Title: Journal of Parallel and Distributed Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/87055
ISSN: 07437315
DOI: 10.1016/j.jpdc.2005.01.002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

59
checked on Jun 25, 2018

WEB OF SCIENCETM
Citations

43
checked on May 30, 2018

Page view(s)

16
checked on Mar 12, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.