期刊
IEEE TRANSACTIONS ON COMPUTERS
卷 64, 期 1, 页码 191-204出版社
IEEE COMPUTER SOC
DOI: 10.1109/TC.2013.205
关键词
Directed acyclic graph; heterogeneous cluster system; parallel processing; stochastic task scheduling
资金
- 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]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据