• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Resource-Constrained Replication Strategies for Hierarchical and Heterogeneous Tasks
【24h】

Resource-Constrained Replication Strategies for Hierarchical and Heterogeneous Tasks

机译：分层和异构任务的资源受限复制策略

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

摘要

In large-scale cloud computing systems, a task is often divided into multiple subtasks which can be executed in parallel in different machines. As a result, the task completion time is constrained by the completion time of the slowest subtask. To reduce the task completion time, the strategy of replicating the straggling subtasks has been employed in cloud computing frameworks such as MapReduce and Hadoop. Analyzing mathematically the performance of such replication strategies has recently received great attention. However, most of the analytical work focuses on the case where the completion times of the subtasks are identically distributed. This assumption may not hold in practice due to the modularization and encapsulation of the computation of a task, resulting in different service requirements for different subtasks. In this paper, we consider the case where the completion times of the subtasks of a task are drawn from heterogeneous/empirical distributions. Furthermore, we consider the case where jobs consist of hierarchical tasks that are required to be executed in a specific order described by a task precedence graph. We propose a novel framework to investigate how to allocate replication resources among the subtasks such that the overall task completion time is minimized. Specifically, we devise a Lagrange multiplier-based method and a water-filling-like algorithm for integer programs. We show via analysis and simulations the optimality and efficiency of our proposed algorithms, and explore the tradeoff between cost and latency from introducing replications in a task graph.
机译：在大规模云计算系统中，一个任务通常分为多个子任务，这些子任务可以在不同的机器中并行执行。结果，任务完成时间受最慢子任务的完成时间限制。为了减少任务完成时间，已经在诸如MapReduce和Hadoop的云计算框架中采用了复制散乱子任务的策略。数学上分析这种复制策略的性能近来受到了极大的关注。但是，大多数分析工作都集中在子任务的完成时间均匀分布的情况下。由于任务计算的模块化和封装性，该假设在实践中可能不成立，从而导致对不同子任务的不同服务需求。在本文中，我们考虑了一个任务的子任务的完成时间是从异构/经验分布中得出的情况。此外，我们考虑以下情况：作业由需要按照任务优先级图描述的特定顺序执行的分层任务组成。我们提出了一个新颖的框架来研究如何在子任务之间分配复制资源，从而使总体任务完成时间最小化。具体来说，我们为整数程序设计了一个基于Lagrange乘数的方法和一种类似注水的算法。通过分析和仿真，我们展示了所提出算法的最优性和效率，并通过在任务图中引入复制来探索成本与延迟之间的权衡。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号