基于边覆盖队列的异构多处理器系统调度算法

摘要

异构多处理器系统是具有不同计算能力和存储能力并相互连接的一组处理器。在异构多处理器系统中，优秀的任务调度算法能够缩短任务完成时间，提升系统利用率和并行度。针对异构多处理器系统，基于有向无环图的边覆盖理论提出了一种新的任务调度算法——启发式边覆盖队列调度算法（HECSA）。该算法利用改进的启发式公式，在保证拓扑正确的前提下，生成有向无环图的边覆盖队列。再利用计算复杂度低的启发式方法将边覆盖队列按顺序分配到异构多处理器上执行。常见数字信号处理任务和科学工作流任务的仿真实验结果表明，提出的HECSA在较低的复杂度下能够得到更好的调度结果。

关键词

异构多处理器系统 / 有向无环图 / 边覆盖队列 / 快速傅里叶变换 / 高斯消元法 / 科学工作流