一种使用改进预测成本矩阵任务优先排序的异构计算系统列表调度算法  

A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing

作　　者：姚宇 宋宇鲲 杨国伟 黄英 张多利 YAO Yu;SONG Yukun;YANG Guowei;HUANG Ying;ZHANG Duoli(School of Microelectronics,Hefei University of Technology,Hefei 230601,China)

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

出　　处：《电子与信息学报》2023年第1期125-133,共9页Journal of Electronics & Information Technology

基　　金：安徽高校协同创新项目(GXXT-2019-030)。

摘　　要：异构计算系统执行应用效率的提高高度依赖有效的调度算法。该文提出一种新的列表调度算法,称为改进的预测优先任务和乐观处理器选择调度(IPPOSS)。通过在任务优先级排序阶段引入任务的后向预测成本,来减少调度长度。与现有工作相比,该文使用改进预测成本矩阵(IPCM),更合理地进行了任务优先级排序,从而在处理器选择阶段获得了更好的解,并保持2次时间复杂度。IPCM考虑了任务优先级排序阶段的各种计算、通信因素,比预测优先任务调度(PPTS)提出的预测成本矩阵(PCM)更容易获得合理的优先级列表。随机生成应用的有向无环图(DAG)和真实世界应用的DAG的实验结果分析表明,IPPOSS的性能优于相关算法。The improvement of application efficiency of heterogeneous computing systems is highly dependent on effective scheduling algorithms. A new list scheduling algorithm called Improved Predict Priority and Optimistic processor Selection Scheduling(IPPOSS) is proposed by this paper. By introducing the backward prediction cost of tasks in task prioritizing phase, the scheduling length is reduced. Compared with the existing work, an Improved Predict Cost Matrix(IPCM) is adopted to prioritize tasks more reasonably and a better solution in processor selection phase when keeping quadratic time complexity is obtain. IPCM, which considers various calculation and communication factors in the task prioritization stage, is easier to obtain a reasonable priority list than Predict Cost Matrix(PCM) proposed by Predict Priority Task Scheduling(PPTS). That the performance of IPPOSS is better than related algorithms is shown by the analysis of the experimental results of randomly generated application Directed Acyclic Graphs(DAGs) and real-world application DAGs.

关 键 词：异构系统 并行计算 列表调度 静态调度 

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