A hybrid heuristic for DAG scheduling on heterogeneous systems

Rizos Sakellariou; Henan Zhao

doi:10.1109/IPDPS.2004.1303065

A hybrid heuristic for DAG scheduling on heterogeneous systems

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

This paper is motivated by the observation that different methods to compute the weights of nodes and edges when scheduling DAGs onto heterogeneous machines may lead to significant variations in the generated schedule. To minimize such variations, the paper presents a novel heuristic for DAG scheduling, which is based upon solving a series of independent task scheduling problems. A novel heuristic for the latter problem is also included in the paper. Both heuristics compare favourably with other related heuristics.

Original language	English
Title of host publication	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)\|Proc. Int. Parall. Distrib. Process. Symp. IPDPS 2004
Pages	1571-1583
Number of pages	12
Volume	18
DOIs	https://doi.org/10.1109/IPDPS.2004.1303065
Publication status	Published - 2004
Event	Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) - Santa Fe, NM Duration: 1 Jul 2004 → … http://dblp.uni-trier.de/db/conf/ipps/ipdps2004-w10.html#CooperDKKMMMMBCCDLOSXJLPRDMSYD04http://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04

Conference

Conference	Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
City	Santa Fe, NM
Period	1/07/04 → …
Internet address	http://dblp.uni-trier.de/db/conf/ipps/ipdps2004-w10.html#CooperDKKMMMMBCCDLOSXJLPRDMSYD04http://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04

Access to Document

10.1109/IPDPS.2004.1303065

Cite this

@inproceedings{828ea6b534ea4b66a962c4938bc1e573,

title = "A hybrid heuristic for DAG scheduling on heterogeneous systems",

abstract = "This paper is motivated by the observation that different methods to compute the weights of nodes and edges when scheduling DAGs onto heterogeneous machines may lead to significant variations in the generated schedule. To minimize such variations, the paper presents a novel heuristic for DAG scheduling, which is based upon solving a series of independent task scheduling problems. A novel heuristic for the latter problem is also included in the paper. Both heuristics compare favourably with other related heuristics.",

author = "Rizos Sakellariou and Henan Zhao",

year = "2004",

doi = "10.1109/IPDPS.2004.1303065",

language = "English",

isbn = "0769521320",

volume = "18",

pages = "1571--1583",

booktitle = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)|Proc. Int. Parall. Distrib. Process. Symp. IPDPS 2004",

note = "Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) ; Conference date: 01-07-2004",

url = "http://dblp.uni-trier.de/db/conf/ipps/ipdps2004-w10.html#CooperDKKMMMMBCCDLOSXJLPRDMSYD04http://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/ipps/CooperDKKMMMMBCCDLOSXJLPRDMSYD04",

}

Sakellariou, R & Zhao, H 2004, A hybrid heuristic for DAG scheduling on heterogeneous systems. in Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)|Proc. Int. Parall. Distrib. Process. Symp. IPDPS 2004. vol. 18, pp. 1571-1583, Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM), Santa Fe, NM, 1/07/04. https://doi.org/10.1109/IPDPS.2004.1303065

A hybrid heuristic for DAG scheduling on heterogeneous systems. / Sakellariou, Rizos; Zhao, Henan.
Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)|Proc. Int. Parall. Distrib. Process. Symp. IPDPS 2004. Vol. 18 2004. p. 1571-1583.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A hybrid heuristic for DAG scheduling on heterogeneous systems

AU - Sakellariou, Rizos

AU - Zhao, Henan

PY - 2004

Y1 - 2004

N2 - This paper is motivated by the observation that different methods to compute the weights of nodes and edges when scheduling DAGs onto heterogeneous machines may lead to significant variations in the generated schedule. To minimize such variations, the paper presents a novel heuristic for DAG scheduling, which is based upon solving a series of independent task scheduling problems. A novel heuristic for the latter problem is also included in the paper. Both heuristics compare favourably with other related heuristics.

AB - This paper is motivated by the observation that different methods to compute the weights of nodes and edges when scheduling DAGs onto heterogeneous machines may lead to significant variations in the generated schedule. To minimize such variations, the paper presents a novel heuristic for DAG scheduling, which is based upon solving a series of independent task scheduling problems. A novel heuristic for the latter problem is also included in the paper. Both heuristics compare favourably with other related heuristics.

U2 - 10.1109/IPDPS.2004.1303065

DO - 10.1109/IPDPS.2004.1303065

M3 - Conference contribution

SN - 0769521320

SN - 9780769521329

VL - 18

SP - 1571

EP - 1583

BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)|Proc. Int. Parall. Distrib. Process. Symp. IPDPS 2004

T2 - Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)

Y2 - 1 July 2004

ER -

A hybrid heuristic for DAG scheduling on heterogeneous systems

Abstract

Conference

Access to Document

Fingerprint

Cite this