Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (1): 12-17.DOI: 10.11772/j.issn.1001-9081.2017.01.0012

Previous Articles     Next Articles

Heterogeneous scheduling algorithm with immediate successor finish time

WANG Guan1,2, WANG Yuxin3, CHEN Xin1, WANG Fei3, GUO He1   

  1. 1. School of Software Technology, Dalian University of Technology, Dalian Liaoning 116620, China;
    2. Department of Police Information, Liaoning Police College, Dalian Liaoning 116036, China;
    3. School of Computer Science and Technology, Dalian University of Technology, Dalian Liaoning 116024, China
  • Received:2016-08-20 Revised:2016-09-02 Online:2017-01-10 Published:2017-01-09
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of

    China (11372067, 61300016).

基于直接后继节点完成时间的异构调度算法

王冠1,2, 王宇新3, 陈鑫1, 王飞3, 郭禾1   

  1. 1. 大连理工大学 软件学院, 辽宁 大连 116620;
    2. 辽宁警察学院 公安信息系, 辽宁 大连 116036;
    3. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024
  • 通讯作者: 王宇新
  • 作者简介:王冠(1984-),男,辽宁大连人,讲师,博士研究生,CCF会员,主要研究方向:计算机系统结构、并行计算;王宇新(1973-),男,辽宁大连人,副教授,博士,CCF会员,主要研究方向:计算机系统结构、并行计算;陈鑫(1983-),男,辽宁锦州人,讲师,博士,主要研究方向:组合优化与调度;王飞(1993-),男,山东枣庄人,硕士研究生,主要研究方向:计算机系统结构、系统仿真;郭禾(1955-),男,辽宁大连人,教授,硕士,主要研究方向:计算机系统结构。
  • 基金资助:
    国家自然科学基金资助项目(11372067,61300016)。

Abstract: In the era of big data, data intensive computing always relies on distributed Heterogeneous Computing System (HCS), and an effective task scheduling method can improve the efficiency of a HCS. Based on a Directed Acyclic Graph (DAG) model, a task scheduling algorithm for heterogeneous computing named HSFT (Heterogeneous scheduling algorithm with immediate Successor Finish Time) was proposed. In the heterogeneous environment, especially when the computation cost and communication cost vary largely, the balance between them was considered and a more reasonable method was adopted, the product of the computation cost standard deviation and mean value was taken as the computation weight, and the ratio between the out degree communication cost weight and out degree was taken as the communication weight. Furthermore, based on the consideration of Earliest Finish Time (EFT), the immediate Successor Finish Time (SFT) was used for processor selection strategy. The experimental results on randomly generated DAGs show that the proposed algorithm performs better than HEFT (Heterogeneous Earliest Finish Time), SDBATS (Standard Deviation-Based Algorithm for Task Scheduling) and PEFT (Predict Earliest Finish Time) in terms of makespan, schedule length ratio, and efficiency without increasing time complexity.

Key words: Directed Acyclic Graph (DAG) scheduling, heterogeneous computing, task priority, immediate successor, static task scheduling

摘要: 分布式环境下的异构计算系统(HCS)是大数据时代进行数据密集型计算不可或缺的,一个有效的任务调度算法可以提高整个异构计算系统的效率。在对异构环境下的任务调度进行有向无环图(DAG)建模的基础上,提出基于直接后继节点完成时间的异构调度算法(HSFT)。在计算开销和通信开销差异度较大的异构环境中,考虑两者之间的平衡,采用更为合理的以计算均值与标准方差的乘积和通信权值与任务节点出度的比值作为优先权值计算方法,并在考虑最快完成时间(EFT)的基础上,将直接后继节点完成时间(SFT)用于处理器分配策略。实验结果表明,HSFT在不增加算法时间复杂度的情况下,比HEFT、SDBATS、PEFT等算法有更短的调度长度(makespan)、更优的调度长度比和效率。

关键词: 有向无环图调度, 异构计算, 任务优先级, 直接后继节点, 静态任务调度

CLC Number: