Abstract: In heterogeneous computing systems, efficient task scheduling algorithms are important to achieve high performance. List scheduling algorithm is a kind of classical static heuristic algorithm to solve the task scheduling problem. Due to the difference of the computation cost and communication cost of the task in heterogeneous system, the task scheduling problem is more complex than in homogeneous system. In this field, the research goals mainly focus on algorithms that shorten the scheduling length under lower time complexity. To solve these problems, a hybrid list scheduling algorithm DPLS based on task replication and pre-scheduling is proposed. This algorithm adopts task duplication strategy to selectively duplicate and schedule key predecessor tasks of the current task to the same processor, reducing the waiting time of the current task's dependent data communication on the key predecessor task, and then advancing the current task's completion time. The algorithm includes two stages: pre-scheduling and secondary scheduling. The pre-scheduling algorithm generates the basic scheduling scheme, and the secondary scheduling algorithm tries to generate a better scheduling scheme on this basis. Compared with the classical algorithm, DPLS has the same time complexity, that is, for tasks and processors. Simulation experiment results show that DPLS can generate schemes with shorter scheduling lengths and show better performance than other list scheduling algorithms. Compared with HEFT and PEFT, the performance of DPLS is improved by 12.563% and 7.786% respectively.

摘要： 在异构计算系统中，高效的任务调度算法是实现高性能的重要条件。列表调度算法是解决任务调度问题的一类经典的静态启发式算法，由于在异构环境下任务的计算成本以及通讯成本的差异，任务调度问题要比同构系统中更为复杂，该领域的研究目标主要集中在较低时间复杂度下缩短调度长度的算法上。针对这类问题，提出了一种基于任务复制和预调度的混合列表调度算法DPLS，该算法采用了任务复制策略，有选择性的将当前任务的关键前驱任务复制调度至相同的处理器上，减少当前任务对关键前驱任务依赖性数据通讯的等待时间，进而提前任务完成时间，算法包括预调度和二次调度两个阶段，预调度算法生成基础调度方案，二次调度算法在此基础上尝试生成更优的调度方案。与经典算法比较，DPLS有着相同的时间复杂度，即对于 个任务和 个处理器的时间复杂度为 ，仿真实验结果表明，DPLS能够生成调度长度更短的方案，表现出比其它列表调度算法更好的性能，相较于HEFT和PEFT分别实现了12.563%和7.786%的性能提升。