Premium
A list scheduling algorithm for heterogeneous systems based on a critical node cost table and pessimistic cost table
Author(s) -
Zhou Naqin,
Qi Deyu,
Wang Xinyang,
Zheng Zhishuo,
Lin Weiwei
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3944
Subject(s) - computer science , robustness (evolution) , critical path method , scheduling (production processes) , schedule , dynamic priority scheduling , least slack time scheduling , job shop scheduling , earliest deadline first scheduling , rate monotonic scheduling , distributed computing , parallel computing , algorithm , mathematical optimization , mathematics , engineering , biochemistry , chemistry , systems engineering , gene , operating system
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.