A Monte-Carlo approach for full-ahead stochastic DAG scheduling

Wei Zheng; Rizos Sakellariou

doi:10.1109/IPDPSW.2012.8

A Monte-Carlo approach for full-ahead stochastic DAG scheduling

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

Abstract

In most heterogeneous computing systems, there is a need for solutions that can cope with the unavoidable uncertainty in individual task execution times, when scheduling DAGs. When such uncertainties occur, static DAG scheduling approaches may suffer, and some rescheduling may be necessary. Assuming that the uncertainty in task execution times is modelled in a stochastic manner, then we may be able to use this information to improve static DAG scheduling considerably. In this paper, a novel DAG scheduling approach is proposed to solve this stochastic scheduling problem, based on a Monte-Carlo method. The approach is built on the top of a classic static scheduling heuristic and evaluated through extensive simulation. Empirical results show that a significant improvement on average application performance can be achieved by the proposed approach at a reasonable execution time cost. © 2012 IEEE.

Original language	English
Title of host publication	Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012\|Proc. IEEE Int. Parallel Distrib. Process. Symp. Workshops, IPDPSW
Pages	99-112
Number of pages	13
DOIs	https://doi.org/10.1109/IPDPSW.2012.8
Publication status	Published - 2012
Event	2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012 - Shanghai Duration: 1 Jul 2012 → …

Conference

Conference	2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012
City	Shanghai
Period	1/07/12 → …

Keywords

DAG scheduling
Directed Acyclic Graph
full-ahead scheduling
monte-carlo methods

Access to Document

10.1109/IPDPSW.2012.8

Cite this

@inproceedings{063c21380233440e9b678ae055cc4f60,

title = "A Monte-Carlo approach for full-ahead stochastic DAG scheduling",

abstract = "In most heterogeneous computing systems, there is a need for solutions that can cope with the unavoidable uncertainty in individual task execution times, when scheduling DAGs. When such uncertainties occur, static DAG scheduling approaches may suffer, and some rescheduling may be necessary. Assuming that the uncertainty in task execution times is modelled in a stochastic manner, then we may be able to use this information to improve static DAG scheduling considerably. In this paper, a novel DAG scheduling approach is proposed to solve this stochastic scheduling problem, based on a Monte-Carlo method. The approach is built on the top of a classic static scheduling heuristic and evaluated through extensive simulation. Empirical results show that a significant improvement on average application performance can be achieved by the proposed approach at a reasonable execution time cost. {\textcopyright} 2012 IEEE.",

keywords = "DAG scheduling, Directed Acyclic Graph, full-ahead scheduling, monte-carlo methods",

author = "Wei Zheng and Rizos Sakellariou",

year = "2012",

doi = "10.1109/IPDPSW.2012.8",

language = "English",

isbn = "9780769546766",

pages = "99--112",

booktitle = "Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012|Proc. IEEE Int. Parallel Distrib. Process. Symp. Workshops, IPDPSW",

note = "2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012 ; Conference date: 01-07-2012",

}

Zheng, W & Sakellariou, R 2012, A Monte-Carlo approach for full-ahead stochastic DAG scheduling. in Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012|Proc. IEEE Int. Parallel Distrib. Process. Symp. Workshops, IPDPSW. pp. 99-112, 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012, Shanghai, 1/07/12. https://doi.org/10.1109/IPDPSW.2012.8

A Monte-Carlo approach for full-ahead stochastic DAG scheduling. / Zheng, Wei; Sakellariou, Rizos.
Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012|Proc. IEEE Int. Parallel Distrib. Process. Symp. Workshops, IPDPSW. 2012. p. 99-112.

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

TY - GEN

T1 - A Monte-Carlo approach for full-ahead stochastic DAG scheduling

AU - Zheng, Wei

AU - Sakellariou, Rizos

PY - 2012

Y1 - 2012

N2 - In most heterogeneous computing systems, there is a need for solutions that can cope with the unavoidable uncertainty in individual task execution times, when scheduling DAGs. When such uncertainties occur, static DAG scheduling approaches may suffer, and some rescheduling may be necessary. Assuming that the uncertainty in task execution times is modelled in a stochastic manner, then we may be able to use this information to improve static DAG scheduling considerably. In this paper, a novel DAG scheduling approach is proposed to solve this stochastic scheduling problem, based on a Monte-Carlo method. The approach is built on the top of a classic static scheduling heuristic and evaluated through extensive simulation. Empirical results show that a significant improvement on average application performance can be achieved by the proposed approach at a reasonable execution time cost. © 2012 IEEE.

AB - In most heterogeneous computing systems, there is a need for solutions that can cope with the unavoidable uncertainty in individual task execution times, when scheduling DAGs. When such uncertainties occur, static DAG scheduling approaches may suffer, and some rescheduling may be necessary. Assuming that the uncertainty in task execution times is modelled in a stochastic manner, then we may be able to use this information to improve static DAG scheduling considerably. In this paper, a novel DAG scheduling approach is proposed to solve this stochastic scheduling problem, based on a Monte-Carlo method. The approach is built on the top of a classic static scheduling heuristic and evaluated through extensive simulation. Empirical results show that a significant improvement on average application performance can be achieved by the proposed approach at a reasonable execution time cost. © 2012 IEEE.

KW - DAG scheduling

KW - Directed Acyclic Graph

KW - full-ahead scheduling

KW - monte-carlo methods

U2 - 10.1109/IPDPSW.2012.8

DO - 10.1109/IPDPSW.2012.8

M3 - Conference contribution

SN - 9780769546766

SP - 99

EP - 112

BT - Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012|Proc. IEEE Int. Parallel Distrib. Process. Symp. Workshops, IPDPSW

T2 - 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012

Y2 - 1 July 2012

ER -

A Monte-Carlo approach for full-ahead stochastic DAG scheduling

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this