DBEFT: A Dependency-Ratio Bundling Earliest Finish Time Algorithm for Heterogeneous Computing

Performance effective task scheduling algorithms are essential for taking advantage of the heterogeneous multi-processor in heterogeneous computing environments. In this paper, we present a task scheduling algorithm named as Dependency-ratio Bundling Earliest Finish Time (DBEFT). DBEFT is a list bas...

Full description

Saved in:
Bibliographic Details
Published in:IEEE access 2019, Vol.7, p.173884-173896
Main Authors: Li, Tao, Cao, Dingyuan, Lu, Ye, Huang, Tehui, Sun, Chengjun, Dong, Qiankun, Gong, Xiaoli
Format: Article
Language:English
Subjects:
Algorithms
Bundling
bundling scheduling
Critical path
Dependence
Heterogeneous networks
Heterogeneous system
Heuristic algorithms
Microprocessors
Scheduling
Scheduling algorithms
Task analysis
task dependency ratio
task duplication
Task scheduling
Time complexity
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:Performance effective task scheduling algorithms are essential for taking advantage of the heterogeneous multi-processor in heterogeneous computing environments. In this paper, we present a task scheduling algorithm named as Dependency-ratio Bundling Earliest Finish Time (DBEFT). DBEFT is a list based scheduling algorithm combined with task duplication, which can achieve high performance and low time complexity simultaneously. DBEFT selects the task from the perspective of extending parallelism between tasks instead of giving priorities to tasks on the critical path. Also, DBEFT reduces communication cost by adopting a bundling scheduling strategy. The experiments were conducted on both random graph set and real-world applications, and the results show that DBEFT obtained significant performance improvement, outperforming CEFT by 15%, PEFT by 30% and HEFT 33% in terms of SLR respectively.
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2019.2956759