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

Hybrid List-Scheduling Algorithm Based on Task Duplication and Pre-Scheduling

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

In heterogeneous computing systems,efficient task-scheduling algorithms are crucial for achieving high performance.The list scheduling algorithm is a classical static heuristic algorithm employed to address task-scheduling issues.However,because of differences in the computational and communication costs for tasks in heterogeneous systems,the task scheduling problem is inherently more complex than in homogeneous systems.Current research primarily focuses on developing lower-time complexity algorithms that minimize the scheduling length.To address these challenges,a hybrid list-scheduling algorithm,referred to as Direct Partial Least Squares(DPLS),is proposed that incorporates task replication and pre-scheduling.This algorithm adopts a task duplication strategy to selectively duplicate and schedule key predecessor tasks on the same processor as the current task,thereby reducing the waiting time of the data-dependent communication on the key predecessor task and advancing the completion time of the current task.The DPLS algorithm consists of two stages:pre-and secondary scheduling.The pre-scheduling phase generates the basic scheduling scheme,and the secondary scheduling phase refines it.This improves the calculation method for task priority by considering the impact of task execution cost in the priority calculation process,leading to a more rational task prioritization.The experimental results indicate that DPLS has the same time complexity as classical algorithms.For a time complexity of O(n^(2)·p)for n tasks and p processors,DPLS can generate scheduling schemes with shorter lengths and outperform other list scheduling algorithms,achieving performance improvements of 12.563%and 7.786%compared to HEFT and PEFT,respectively.