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

Heterogeneous scheduling algorithm with immediate successor finish time

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

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 Acyclie 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 resuhs 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.