Stochastic DAG scheduling using a Monte Carlo approach

• A systematic approach to solve the stochastic DAG scheduling problem using a Monte Carlo method.
• Extensive simulation results assessing the Monte Carlo approach using four real-world DAGs.
• Significant performance improvement can be achieved at a reasonable execution time cost.

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.