• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Correlation-Aware Heuristics for Evaluating the Distribution of the Longest Path Length of a DAG with Random Weights
【24h】

Correlation-Aware Heuristics for Evaluating the Distribution of the Longest Path Length of a DAG with Random Weights

机译：用于评估具有随机权重的DAG的最长路径长度的分布的相关感知启发法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Coping with uncertainties when scheduling task graphs on parallel machines requires to perform non-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.
机译：在并行计算机上调度任务图时，应对不确定性需要执行非平凡的评估。当考虑到每个计算和通信持续时间都是随机变量时，评估此类图的关键路径长度的分布涉及计算可能相关的随机变量的最大值和总和。已知此评估问题的离散版本为＃P-hard。在这里，我们提出了两种启发式算法，CorLCA和Cordyn，来计算这种长度。它们将输入的随机变量和中间的变量近似为正常随机变量，并且精确地考虑了两种不同机制之间的相关性：通过针对CorLCA的最低共同祖先查询和针对Cordyn的动态编程方法。此外，我们从经验上比较文献中的一些经典方法，并将其与我们的解决方案相对。对大量案例的仿真表明，CorLCA和Cordyn在速度和精度方面均构成了一个新的相关权衡。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号