【文件属性】：
文件名称：Scheduling Precedence Constrained Stochastic Tasks
文件大小：2.73MB
文件格式：PDF
更新时间：2021-04-27 11:35:33
调试；异构
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
minimizeaparallelapplication’sexpectedcompletiontimeisanimportantbutverydifficultprobleminparallelanddistributedcomputing.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
makespanofschedulingstochastictasksisgreaterthanorequaltothemakespanofschedulingdeterministictasks,whereallprocessing
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.