基于直接后继节点完成时间的异构调度算法
来源：计算机应用杂志2017年第1期北京时间：
作者：王冠, 王宇新, 陈鑫, 王飞, 郭禾
单位：1. 大连理工大学 软件学院, 辽宁 大连 116620;2. 辽宁警察学院 公安信息系, 辽宁 大连 116036;3. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024
摘要：分布式环境下的异构计算系统（HCS）是大数据时代进行数据密集型计算不可或缺的，一个有效的任务调度算法可以提高整个异构计算系统的效率。在对异构环境下的任务调度进行有向无环图（DAG）建模的基础上，提出基于直接后继节点完成时间的异构调度算法（HSFT）。在计算开销和通信开销差异度较大的异构环境中，考虑两者之间的平衡，采用更为合理的以计算均值与标准方差的乘积和通信权值与任务节点出度的比值作为优先权值计算方法，并在考虑最快完成时间（EFT）的基础上，将直接后继节点完成时间（SFT）用于处理器分配策略。实验结果表明，HSFT在不增加算法时间复杂度的情况下，比HEFT、SDBATS、PEFT等算法有更短的调度长度（makespan）、更优的调度长度比和效率。
关键词：有向无环图调度,异构计算,任务优先级,直接后继节点,静态任务调度
基金资助：国家自然科学基金资助项目（11372067，61300016）。
