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

doi:10.1109/TPDS.2020.3041829

Return

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

2021-05-01

PRE

Hamza Djigal (Hamza Djigal) *

DOI：10.1109/TPDS.2020.3041829

Original

Original request for help

Save

Abstract

En 中文

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) x p), for t tasks and 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.

Keywords:

Workflow scheduling

list scheduling

random graphs generator

scientific workflows

heterogeneous systems

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.