• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Sulaiman, Muhammad (Sulaiman, Muhammad.) | Halim, Zahid (Halim, Zahid.) | Waqas, Muhammad (Waqas, Muhammad.) | Aydin, Dogan (Aydin, Dogan.)

Indexed by:

EI Scopus SCIE

Abstract:

Efficient task scheduling is required to attain high performance in both homogeneous and heterogeneous computing systems. An application can be considered as a task grid represented using a Directed Acyclic Graph (DAG). Solving such DAG representing a scheduling problem is an NP-complete task. The primary concern in this problem domain is to reduce the schedule length with minimum complexity. This work presents a Hybrid List-based Task Scheduling using Duplication Scheme (HLTSD) algorithm for heterogeneous processors. The proposed HLTSD algorithm has the same time complexity as that of the recent state-of-the-art algorithms. However, it produces a minimum cost schedule in comparison with other related methods. This work also presents a mathematical formulation to find task priorities. The processor selection phase is improved by utilizing the techniques, like entry task duplication, insertion-based policy, duplication of parent task on other levels, and balancing the load on each processor. The current proposal minimizes the overall makespan of execution by reasonable levels. Performance of the proposed algorithm is evaluated using DAGs adopted from various state-of-the-art algorithms, real-world problems, like Gaussian elimination (GE) and fast Fourier transformation (FFT) task graph and randomly generated graphs with diverse characteristics. The proposed scheme is compared with four state-of-the-art list-based scheduling algorithms, namely Heterogeneous Earliest Finish Time (HEFT), Predict Earliest Finish Time (PEFT), Heterogeneous Scheduling with Improved task Priority (HSIP), and Task Scheduling for Heterogeneous Computing Systems (TSHCS). Based on the best quality schedule, the obtained results suggest that HLTSD has better results in 87% cases.

Keyword:

Heterogeneous systems DAG scheduling Task prioritization Hybrid scheduling Task scheduling

Author Community:

  • [ 1 ] [Sulaiman, Muhammad]Ghulam Ishaq Khan Inst Engn Sci & Technol, Fac Comp Sci & Engn, Machine Intelligence Res Grp MInG, Topi 23460, Pakistan
  • [ 2 ] [Halim, Zahid]Ghulam Ishaq Khan Inst Engn Sci & Technol, Fac Comp Sci & Engn, Machine Intelligence Res Grp MInG, Topi 23460, Pakistan
  • [ 3 ] [Sulaiman, Muhammad]Capital Univ Sci & Technol, Dept Comp Sci, Islamabad, Pakistan
  • [ 4 ] [Waqas, Muhammad]Beijing Univ Technol, Fac Informat Technol, Engn Res Ctr Intelligent Percept & Autonomous Con, Beijing 100124, Peoples R China
  • [ 5 ] [Waqas, Muhammad]Ghulam Ishaq Khan Inst Engn Sci & Technol, Fac Comp Sci & Engn, Topi 23460, Pakistan
  • [ 6 ] [Aydin, Dogan]Dumlupinar Univ, Dept Comp Engn, TR-43100 Kutahya, Turkey

Reprint Author's Address:

  • [Halim, Zahid]Ghulam Ishaq Khan Inst Engn Sci & Technol, Fac Comp Sci & Engn, Machine Intelligence Res Grp MInG, Topi 23460, Pakistan

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF SUPERCOMPUTING

ISSN: 0920-8542

Year: 2021

Issue: 9

Volume: 77

Page: 10252-10288

3 . 3 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:87

JCR Journal Grade:2

Cited Count:

WoS CC Cited Count: 22

SCOPUS Cited Count: 23

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

Online/Total:1470/10612488
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.