基于任务复制与预调度的混合列表调度算法

在异构计算系统中,高效的任务调度算法是实现高性能的重要条件。列表调度算法是一类经典静态启发式算法,用于解决任务调度问题。在异构环境下由于任务的计算成本以及通信成本存在差异,因此任务调度问题比同构系统中更为复杂。该领域的研究目标主要集中在较低时间复杂度下缩短调度长度。为此,提出一种基于任务复制和预调度的混合列表调度算法DPLS。采用任务复制策略,有选择性地将当前任务的关键前驱任务复制调度至相同的处理器上,减少当前任务对关键前驱任务依赖性数据通信的等待时间,进而缩短任务完成时间。DPLS算法包括预调度和二次调度2个阶段,预调度算法生成基础调度方案,二次调度算法在此基础上尝试生成更优的调度方案,改进任务优先级的计算方式,将任务自身执行成本的影响考虑到优先级计算过程中,使得任务优先级更加合理。实验结果表明,DPLS与经典算法具有相同的时间复杂度,对于n个任务和p个处理器的时间复杂度为O(n^(2)·p),能够生成调度长度更短的方案,相较于HEFT和PEFT分别实现了12.563%和7.786%的性能提升。