计算机工程 ›› 2018, Vol. 44 ›› Issue (8): 43-47.doi: 10.19678/j.issn.1000-3428.0048099

• 先进计算与数据处理 • 上一篇    下一篇

异构分布式计算环境下一种新型表调度算法

李云洋 1,周川 1,王琦 2   

  1. 1.南京理工大学 自动化学院,南京 210094; 2.中航工业西安飞行自动控制研究所,西安 710065
  • 收稿日期:2017-07-25 出版日期:2018-08-15 发布日期:2018-08-15
  • 作者简介:李云洋(1992—),男,硕士研究生,主研方向为分布式计算、可靠性分析;周川(通信作者),教授;王琦,高级工程师。
  • 基金项目:

    国家重点研发计划项目(2017YFB1001801);江苏省重点研发计划项目(BE2017161);江苏省“六大人才高峰”项目(XNYQC-CXTD-001)。

A New List Scheduling Algorithm in Heterogeneous Distributed Computing Environment

LI Yunyang 1,ZHOU Chuan 1,WANG Qi 2   

  1. 1.School of Automation,Nanjing University of Science and Technology,Nanjing 210094,China; 2.AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710065,China
  • Received:2017-07-25 Online:2018-08-15 Published:2018-08-15

摘要:

针对异构分布式环境下并行计算的静态任务调度问题,在HEFT算法的基础上,提出一种新型表调度算法IFEFT。以最小化有向无环图(DAG)的执行跨度为目的,在任务处理器分配阶段改变HEFT算法中的处理器分配策略,计算任务最早完成时间与其出口任务之间的最大通信开销, 并依据两者乘积的最小值进行分配,兼顾任务对其直接后驱任务和直接前驱任务完成时间的影响,以优化处理器分配结果。通过随机生成的DAG图进行仿真,与HEFT、DLS和CPOP算法的比较结果表明,IFEFT算法具有更高的调度效率。

关键词: 异构分布式计算, 有向无环图, 静态任务, 表调度, 调度长度

Abstract:

A new list scheduling algorithm called IFEFT is proposed based on HEFT algorithm for minimizing makespan which can be modelled as a Directed Acyclic Graph(DAG) for static task scheduling problems in heterogeneous distributed computing environment.In the phase of processor selection,a better processor selected by changing the policy of HEFT processor is allocated based on the product of earliest finish time and link distance which makes value smaller to assign the processor for considering the impact of the task on its immediate predecessor and immediate successor tasks finish time.Finally,based on randomly generated graphs,the comparison studies demonstrate that IFEFT algorithm has an advantage over the HEFT,DLS and CPOP in terms of scheduling efficiency.

Key words: heterogeneous distributed computing, Directed Acyclic Graph(DAG), static task, list scheduling, scheduling length

中图分类号: