计算机工程

作者：严长宇, 张磊

单位：首都师范大学信息工程学院, 北京 100048

关键词：任务调度,异构计算系统,任务复制,预调度,列表调度

基金：科技创新2030—重大项目(2020AAA0109700)

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

来源：2024年第12期

《计算机工程》期刊编辑部

查看计算机工程杂志2024年第12期