Journal
IEEE TRANSACTIONS ON COMPUTERS
Volume 64, Issue 1, Pages 191-204Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TC.2013.205
Keywords
Directed acyclic graph; heterogeneous cluster system; parallel processing; stochastic task scheduling
Funding
- National Natural Science Foundation of China [61133005]
- National Science Foundation of China [61070057, 61370098, 61370095]
- PhD Programs Foundation of Ministry of Education of China [20100161110019]
- Scientific Research Fund of Hunan Provincial Education Department [12A062]
Ask authors/readers for more resources
Generally, a parallel application consists of precedence constrained stochastic tasks, where task processing times and intertask communication times are random variables following certain probability distributions. Scheduling such precedence constrained stochastic tasks with communication times on a heterogeneous cluster system with processors of different computing capabilities to minimize a parallel application's expected completion time is an important but very difficult problem in parallel and distributed computing. In this paper, we present a model of scheduling stochastic parallel applications on heterogeneous cluster systems. We discuss stochastic scheduling attributes and methods to deal with various random variables in scheduling stochastic tasks. We prove that the expected makespan of scheduling stochastic tasks is greater than or equal to the makespan of scheduling deterministic tasks, where all processing times and communication times are replaced by their expected values. To solve the problem of scheduling precedence constrained stochastic tasks efficiently and effectively, we propose a stochastic dynamic level scheduling (SDLS) algorithm, which is based on stochastic bottom levels and stochastic dynamic levels. Our rigorous performance evaluation results clearly demonstrate that the proposed stochastic task scheduling algorithm significantly outperforms existing algorithms in terms of makespan, speedup, and makespan standard deviation.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available