基于HEFT和CPOP的相关任务表调度算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61772205);广东省科技计划项目(2014B010110004,2016A010106007,2016B090927010);广东第二师范学院网络工程重点学科(ZD2017004);广东第二师范学院计算机实验教学示范中心(SY2016014)


List Scheduling Algorithm of Dependent Tasks Based on HEFT and CPOP
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

    DAG任务调度是当前研究的热点,DAG任务模型中任务的调度顺序一方面会影响用户服务满意质量,另一方面也会影响云服务资源的利用率,高效的任务调度算法能够使多核处理器的资源分配和并行计算能力更强.表调度算法HEFT算法以及CPOP算法在相关任务调度中存在效率较低等问题.本文基于HEFT算法和CPOP算法,提出了一种相关任务调度模型和相关任务调度算法IHEFT算法,对任务排序和任务调度两个方面进行改进.任务排序阶段,以任务的方差以及平均通信代价作为排序的依据;任务调度阶段,对满足任务复制条件的结点进行任务复制.实验证明,IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack值方面均优于HEFT算法和CPOP算法.

    Abstract:

    DAG task scheduling is the current hot topic. In task model of DAG, the order of task scheduling affect the service satisfaction of users on one hand, and also affect utilization rate of cloud service resources on the other hand. High efficient task scheduling algorithm may strengthen the resources distribution of the multi-core and the parallel computing ability. HEFT algorithm and CPOP algorithm are of lower efficiency in related task scheduling. Based on HEFT algorithm and CPOP algorithm, a dependent task scheduling model and task scheduling algorithm IHEFT (Improvement Heterogeneous Earliest Finish Time) algorithm are proposed in this study. The IHEFT algorithm mainly optimizes two aspects:task ordering and task scheduling. The variance of task scheduling cost on every processor core and the average communication overhead are the basis of task ordering. In the stage of task scheduling, task duplication of some nodes in DAG with some conditions can make full use of heterogeneous processor resources and shorten the completion time of task set. Experiment results show that the IHEFT algorithm performs more performance than the HEFT algorithm and the CPOP algorithm in terms of the task scheduling Makespan, the average waiting time and the average value of Slack.

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

刘林东,邬依林.基于HEFT和CPOP的相关任务表调度算法.计算机系统应用,2019,28(3):118-125

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-09-12
  • 最后修改日期:2018-10-08
  • 录用日期:
  • 在线发布日期: 2019-02-22
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号