DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm

Luiz F. Bittencourt; Rizos Sakellariou; Edmundo R M Madeira

doi:10.1109/PDP.2010.56

DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm

Luiz F. Bittencourt, Rizos Sakellariou, Edmundo R M Madeira

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

Abstract

Among the numerous DAG scheduling heuristics suitable for heterogeneous systems, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time. In this paper, we propose an improvement of HEFT, where the locally optimal decisions made by the heuristic do not rely on estimates of a single task only, but also look ahead in the schedule and take into account information about the impact of this decision to the children of the task being allocated. Preliminary simulation results indicate that the lookahead variation of HEFT can effectively reduce the makespan of the schedule in most cases without making the algorithm's execution time prohibitively high. © 2010 IEEE.

Original language	English
Title of host publication	Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010\|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP
Publisher	IEEE Computer Society
Pages	27-34
Number of pages	7
ISBN (Print)	9780769539393
DOIs	https://doi.org/10.1109/PDP.2010.56
Publication status	Published - 2010
Event	18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010 - Pisa Duration: 1 Jul 2010 → …

Conference

Conference	18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010
City	Pisa
Period	1/07/10 → …

Access to Document

10.1109/PDP.2010.56

Cite this

Bittencourt, L. F., Sakellariou, R., & Madeira, E. R. M. (2010). DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP (pp. 27-34). IEEE Computer Society . https://doi.org/10.1109/PDP.2010.56

Bittencourt, Luiz F. ; Sakellariou, Rizos ; Madeira, Edmundo R M. / DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP. IEEE Computer Society , 2010. pp. 27-34

@inproceedings{84728f3c78ce41a6972eb9a9cba9034d,

title = "DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm",

abstract = "Among the numerous DAG scheduling heuristics suitable for heterogeneous systems, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time. In this paper, we propose an improvement of HEFT, where the locally optimal decisions made by the heuristic do not rely on estimates of a single task only, but also look ahead in the schedule and take into account information about the impact of this decision to the children of the task being allocated. Preliminary simulation results indicate that the lookahead variation of HEFT can effectively reduce the makespan of the schedule in most cases without making the algorithm's execution time prohibitively high. {\textcopyright} 2010 IEEE.",

author = "Bittencourt, {Luiz F.} and Rizos Sakellariou and Madeira, {Edmundo R M}",

year = "2010",

doi = "10.1109/PDP.2010.56",

language = "English",

isbn = "9780769539393",

pages = "27--34",

booktitle = "Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP",

publisher = "IEEE Computer Society ",

address = "United States",

note = "18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010 ; Conference date: 01-07-2010",

}

Bittencourt, LF, Sakellariou, R & Madeira, ERM 2010, DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. in Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP. IEEE Computer Society , pp. 27-34, 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010, Pisa, 1/07/10. https://doi.org/10.1109/PDP.2010.56

DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. / Bittencourt, Luiz F.; Sakellariou, Rizos; Madeira, Edmundo R M.
Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP. IEEE Computer Society , 2010. p. 27-34.

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

TY - GEN

T1 - DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm

AU - Bittencourt, Luiz F.

AU - Sakellariou, Rizos

AU - Madeira, Edmundo R M

PY - 2010

Y1 - 2010

N2 - Among the numerous DAG scheduling heuristics suitable for heterogeneous systems, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time. In this paper, we propose an improvement of HEFT, where the locally optimal decisions made by the heuristic do not rely on estimates of a single task only, but also look ahead in the schedule and take into account information about the impact of this decision to the children of the task being allocated. Preliminary simulation results indicate that the lookahead variation of HEFT can effectively reduce the makespan of the schedule in most cases without making the algorithm's execution time prohibitively high. © 2010 IEEE.

AB - Among the numerous DAG scheduling heuristics suitable for heterogeneous systems, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time. In this paper, we propose an improvement of HEFT, where the locally optimal decisions made by the heuristic do not rely on estimates of a single task only, but also look ahead in the schedule and take into account information about the impact of this decision to the children of the task being allocated. Preliminary simulation results indicate that the lookahead variation of HEFT can effectively reduce the makespan of the schedule in most cases without making the algorithm's execution time prohibitively high. © 2010 IEEE.

U2 - 10.1109/PDP.2010.56

DO - 10.1109/PDP.2010.56

M3 - Conference contribution

SN - 9780769539393

SP - 27

EP - 34

BT - Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP

PB - IEEE Computer Society

T2 - 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010

Y2 - 1 July 2010

ER -

Bittencourt LF, Sakellariou R, Madeira ERM. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP 2010|Proc. Euromicro Conf. Parallel, Distrib. Netw.-Based Process., PDP. IEEE Computer Society . 2010. p. 27-34 doi: 10.1109/PDP.2010.56

DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm

Abstract

Conference

Access to Document

Fingerprint

Cite this