期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 27, 期 11, 页码 3158-3171出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2016.2528983
关键词
Stochastic scheduling; graph heuristic; PERT
Coping with uncertainties when scheduling task graphs on parallel machines requires to performnon-trivial evaluations. When considering that each computation and communication duration is a random variable, evaluating the distribution of the critical path length of such graphs involves computing maximums and sums of possibly dependent random variables. The discrete version of this evaluation problem is known to be #P-hard. Here, we propose two heuristics, CorLCA and Cordyn, to compute such lengths. They approximate the input random variables and the intermediate ones as normal random variables, and they precisely take into account correlations with two distinct mechanisms: through lowest common ancestor queries for CorLCA and with a dynamic programming approach for Cordyn. Moreover, we empirically compare some classical methods from the literature and confront them to our solutions. Simulations on a large set of cases indicate that CorLCA and Cordyn constitute each a new relevant trade-off in terms of rapidity and precision.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据