云平台上基于关键路径截取的有向无环图应用调度算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金资助项目(61572510);国家公益行业专项计划资助项目(GYHY201306003)


Directed acyclic graph application scheduling strategy based on critical path cut on cloud platform
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。

    Abstract:

    To address the problems that the resource is surplus, the resource utilization rate is low and the cost is unreasonably high for virtual machines in the scientific application of DAG(directed acyclic graph), a novel DAG scientific workflow scheduling algorithm based on CPC(critical path cut) was proposed. In the algorithm, the CPC technology was adopted to circularly find the unallocated task which is finished at last; the biggest connected subgraph was found from the graph constructed by the whole unallocated tasks; the critical path of this subgraph was calculated and the task set on the critical path was scheduled to the performance-matched virtual machine to execute. Meanwhile, the isolated tasks were used to fill in the idle slots of the virtual machines, such that the resource utilization could be improved. Experimental results demonstrate that, the proposed CPC algorithm can effectively reduce the execution cost of the scientific workflows while satisfying the deadline constraint in mean time. 

    参考文献
    相似文献
    引证文献
引用本文

刘少伟,任开军,邓科峰,等.云平台上基于关键路径截取的有向无环图应用调度算法[J].国防科技大学学报,2017,39(3):97-104.
LIU Shaowei, REN Kaijun, DENG Kefeng, et al. Directed acyclic graph application scheduling strategy based on critical path cut on cloud platform[J]. Journal of National University of Defense Technology,2017,39(3):97-104.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-02-14
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2017-07-09
  • 出版日期:
文章二维码