李云洋, ,

(1.南京理工大学 自动化学院,南京 210094; 2.中航工业西安飞行自动控制研究所,西安 710065)

0 概述

随着网络技术的飞速发展和在实际工程系统中的广泛应用,越来越多不同处理能力的单个处理器通过网络互联而组成了异构分布式计算环境,如网络化嵌入式系统[1]。在处理大规模任务时,分布式计算系统通常将任务分解为若干相互依赖的子任务并进行处理,而任务调度是实现高效异构分布式计算的关键技术。由于大规模复杂多约束任务调度问题是NP-hard问题[2],往往难以获得最优解,尤其在分布式异构计算环境中,由于各任务在异构处理器上执行特性不同,对复杂任务调度问题提出了挑战,因此研究并设计低复杂度、高性能的任务调度算法具有重要的理论意义和工程应用前景。

静态任务调度算法主要包括基于启发式和基于随机搜索的算法,其中启发式调度主要有表调度算法、基于分簇的调度算法和基于复制的调度算法[3-4]。表调度由于简单易行,并且具有较高的调度效率和较低的时间复杂度,因此受到广泛关注,其主要代表性算法有DLS[5]、HEFT[6]、CPOP[6]等。文献[6]提出2种低复杂度的表调度算法HEFT和CPOP,但HEFT算法在处理器分配阶段仅根据本任务完成时间最短的策略分配处理器,而未考虑对后继任务完成时间的影响。文献[7-8]提出2种基于复制策略的调度算法,减少了任务完成时间,但算法执行时间复杂度较高且容易造成处理器资源浪费。文献[9-10]分别提出2种基于分簇策略的调度算法,基于分簇的算法能够有效利用处理器资源而提高任务并行计算执行效率,但在减少通信开销上不如基于任务复制的算法,并且时间复杂度也高于表调度算法。……