Stochastic DAG scheduling using a Monte Carlo approach

    Research output: Contribution to journalArticlepeer-review


    In 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, 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 DAG scheduling heuristic and evaluated through extensive simulation. Empirical results show that a significant improvement of average application performance can be achieved by the proposed approach at a reasonable execution time cost. © 2013 Elsevier Inc. All rights reserved.
    Original languageEnglish
    Pages (from-to)1673-1689
    Number of pages16
    JournalJournal of Parallel and Distributed Computing
    Issue number12
    Publication statusPublished - 2013


    • DAG scheduling
    • Directed acyclic graphs
    • Heterogeneous computing
    • Monte Carlo methods


    Dive into the research topics of 'Stochastic DAG scheduling using a Monte Carlo approach'. Together they form a unique fingerprint.

    Cite this