IPPTS: An Efficient Algorithm for Scientific Workflow Scheduling in Heterogeneous Computing Systems

Efficient scheduling algorithms are key for attaining high performance in heterogeneous computing systems. In this article, we propose a new list scheduling algorithm for assigning task graphs to fully connected heterogeneous processors with an aim to minimize the scheduling length. The proposed alg...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2021-05, Vol.32 (5), p.1057-1071
Main Authors: Djigal, Hamza, Feng, Jun, Lu, Jiamin, Ge, Jidong
Format: Article
Language:English
Subjects:
Algorithms
Computation
Dynamic scheduling
Graphs
Heterogeneous networks
heterogeneous systems
Heuristic algorithms
list scheduling
Microprocessors
Prediction algorithms
Priority scheduling
Processors
Program processors
random graphs generator
Schedules
Scheduling
Scheduling algorithms
scientific workflows
Task analysis
Task scheduling
Workflow
Workflow scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Efficient scheduling algorithms are key for attaining high performance in heterogeneous computing systems. In this article, we propose a new list scheduling algorithm for assigning task graphs to fully connected heterogeneous processors with an aim to minimize the scheduling length. The proposed algorithm, called Improved Predict Priority Task Scheduling (IPPTS) algorithm has two phases: task prioritization phase, which gives priority to tasks, and processor selection phase, which selects a processor for a task. The IPPTS algorithm has a quadratic time complexity as the related algorithms for the same goal, that is O(t^{2} \times p) O(t2×p) , for t t tasks and p p processors. Our algorithm reduces the scheduling length significantly by looking ahead in both task prioritization phase and processor selection phase. In this way, the algorithm is looking ahead to schedule a task and its heaviest successor task to the optimistic processor, i.e., the processor that minimizes their computation and communication costs. The experiments based on both randomly generated graphs and graphs of real-world applications show that the IPPTS algorithm significantly outperforms previous list scheduling algorithms in terms of makespan, speedup, makespan standard deviation, efficiency, and frequency of best results.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2020.3041829