A productive duplication-based scheduling algorithm for heterogeneous computing systems

Young Choon Lee*, Albert Y. Zomaya

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

8 Citations (Scopus)

Abstract

The scheduling problem has been shown to be NP-complete in general cases, and as a consequence many heuristic algorithms account for a myriad of previously proposed scheduling algorithms. Most of these algorithms are designed for homogeneous computing systems. This paper presents a novel scheduling algorithm for heterogeneous computing systems. The proposed method is known as the Productive Duplication-based Heterogeneous Earliest-Finish-Time (PDHEFT) algorithm. The PDHEFT algorithm is based on a recently proposed list-scheduling heuristic known as the Heterogeneous Earliest-Finish-Time (HEFT) algorithm which is proven to perform well with a low time complexity. However, the major performance gain of the PDHEFT algorithm is achieved through its distinctive duplication policy. The duplication policy is unique in that it takes into account the communication to computation ratio (CCR) of each task and the potential load of processors. The PDHEFT algorithm performs very competitively in terms of both resulting schedules and time complexity. In evaluating the PDHEFT algorithm a comparison is made with another two algorithms that have performed relatively well, namely, the HEFT and LDBS algorithms. It is shown that the proposed algorithm outperforms both of them with a low time complexity.

Original languageEnglish
Title of host publicationHigh Performance Computing and Communcations
Subtitle of host publicationFirst International Conference, HPCC 2005, Sorrento, Italy, September 21-23, 2005. Proceedings
EditorsLaurence T. Yang, Omer F. Rana, Beniamino Di Martino, Jack Dongarra
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages203-212
Number of pages10
Volume3726 LNCS
ISBN (Electronic)9783540320791
ISBN (Print)3540290311, 9783540290315
DOIs
Publication statusPublished - Sep 2005
Externally publishedYes
Event1st International Conference on High Performance Computing and Communcations, HPCC - 2005 - Sorrento, Italy
Duration: 21 Sep 200523 Sep 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3726 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other1st International Conference on High Performance Computing and Communcations, HPCC - 2005
CountryItaly
CitySorrento
Period21/09/0523/09/05

Fingerprint Dive into the research topics of 'A productive duplication-based scheduling algorithm for heterogeneous computing systems'. Together they form a unique fingerprint.

Cite this