带资源约束的异构多核任务复制调度算法  

Task-duplication scheduling algorithm with resource constraints for heterogeneous multi-core processor

作　　者：王月恒 倪伟 汪敏 WANG Yueheng;NI Wei;WANG Min(School of Microelectronics,Hefei University of Technology,Hefei 230601,China)

机构地区：[1]合肥工业大学微电子学院,安徽合肥230601

出　　处：《合肥工业大学学报（自然科学版）》2022年第11期1497-1504,共8页Journal of Hefei University of Technology：Natural Science

基　　金：国家重点研发计划资助项目(2018YFB2202604)。

摘　　要：关键路径的确定与优化在异构多核系统的任务调度算法中占据重要地位。为解决异构多核系统调度算法常因估算关键路径时的参数选择存在局限而导致的估算结果偏差过大,调度结果不佳的问题,文章提出一种在参数计算时考虑资源约束的异构多核任务复制调度算法(task-duplication scheduling algorithm with resource constraints,TDSA-RC)。该算法通过改进布局优化方式,扩大其适用范围;同时通过筛除冗余任务,减少任务复制过程中产生的不必要的计算。通过随机生成的任务图和3种实际应用的任务图调度对比实验表明,该算法能有效缩短并行任务的调度长度,与TDCA(task-duplication based clustering algorithm)算法相比,平均性能可提升12.08%,适合处理规模大、层级少且join节点占比多的并行任务。The determination and optimization of the critical path is the key point to solving the task scheduling problem for heterogeneous multi-core processor.In order to solve the poor scheduling result caused by the large deviation between the estimated path and the actual one due to the limitation of parameters selection when estimating critical path in the scheduling algorithm for heterogeneous multi-core processor,a task-duplication scheduling algorithm with resource constraints(TDSA-RC)for heterogeneous multi-core processor is proposed.The algorithm also improves the layout optimization method to expand its scope of application,and filters and deletes redundant tasks to reduce unnecessary calculations in task duplication phase.The comparison experiments of scheduling randomly generated task graphs and three practical task graphs show that the proposed algorithm could effectively shorten the scheduling length of parallel tasks.Compared with the task-duplication based clustering algorithm(TDCA),the average performance of the TDSA-RC could be improved by 12.08%.TDSA-RC is suitable for processing parallel tasks featuring large scale,fewer levels and a large proportion of join nodes.

关 键 词：异构多核 静态任务调度 资源约束 任务复制 

分 类 号：TN401[电子电信—微电子学与固体电子学]