...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Future generation computer systems >PCP-B~2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications
【24h】

PCP-B~2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications

机译：PCP-B〜2：用于科学工作流应用的部分关键路径预算均衡调度算法

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

摘要

Service-oriented computing becomes an attractive environment for executing scientific workflow applications. It enables these applications to use resources in a pay-as-you-go model. However, it also challenges traditional best-effort workflow scheduling strategies, that only focus on minimizing schedule length. One of the most challenging problem is to optimize workflow execution time under QpS constraint of budget. To solve this problem, we propose a heuristic algorithm of PCP-B~2. A PCP-wise budget distribution mechanism is proposed to balance budget among partial critical paths according to their sequential or parallel structure nature. The budget distribution mechanism is implemented using binary search method. Moreover, a partially rescheduling mechanism is designed to further tune budget distribution. Simulation experiments using five well-known scientific workflow applications show that PCP-B~2 algorithm is efficient in scheduling pipeline structured workflows, and performs better than other budget constrained scheduling algorithms on average. The time complexity of PCP-B~2 is O(log |RT | |T |~3), where |RT| denotes the number of resource type, and |T| denotes the total number of workflow task. This time complexity ensures that the proposed algorithm is able to schedule large scale workflows quickly.
机译：面向服务的计算成为执行科学工作流应用程序的诱人环境。它使这些应用程序可以按需付费模式使用资源。但是，它也挑战了传统的“尽力而为”工作流调度策略，该策略仅关注最小化调度时间。最具挑战性的问题之一是在QpS预算约束下优化工作流执行时间。为了解决这个问题，我们提出了一种启发式算法PCP-B〜2。提出了一种基于PCP的预算分配机制，以根据部分关键路径的顺序或并行结构性质在部分关键路径之间平衡预算。预算分配机制是使用二进制搜索方法实现的。此外，设计了部分重新计划机制以进一步调整预算分配。使用五个著名的科学工作流程应用程序进行的仿真实验表明，PCP-B〜2算法可高效地调度流水线结构化的工作流程，并且平均性能优于其他预算受限的调度算法。 PCP-B〜2的时间复杂度为O（log | RT | | T |〜3），其中| RT |表示资源类型的数量，| T |表示工作流程任务的总数。这种时间上的复杂性确保了所提出的算法能够快速调度大规模的工作流程。

著录项

  • 来源
    《Future generation computer systems》 |2016年第7期|22-34|共13页
  • 作者

    Fuhui Wu; Qingbo Wu; Yusong Tan; Rongzhen Li; Wei Wang;

  • 作者单位

    School of Computer Science, National University of Defense Technology, Changsha, 410073, China;

    School of Computer Science, National University of Defense Technology, Changsha, 410073, China;

    School of Computer Science, National University of Defense Technology, Changsha, 410073, China;

    School of Computer Science, National University of Defense Technology, Changsha, 410073, China;

    School of Computer Science, National University of Defense Technology, Changsha, 410073, China;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Service-oriented computing; Scientific workflow scheduling; Budget constrained scheduling;

    机译：面向服务的计算;科学的工作流程安排;预算受限的计划;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号