一种多核系统改进型列表调度算法  

A Multicore System Improved List Scheduling Algorithm

作　　者：罗乐[1] 王春华[1] 张多利[1] 宋宇鲲[1] LUO Le;WANG Chunhua;ZHANG Duoli;SONG Yukun(School of Electronic Science & Applied Physics,Hefei University of Technology,Hefei 230009,China)

机构地区：[1]合肥工业大学电子科学与应用物理学院,安徽合肥230009

出　　处：《电子科技》2020年第6期52-57,共6页Electronic Science and Technology

基　　金：国家自然科学基金(61874156)。

摘　　要：在任务调度领域,基于列表的任务调度算法被广泛应用。经典列表调度算法在节点排序阶段会对权值一致的任务节点进行随机排序,但这种节点排序方式过于粗糙,难以取得较好效果。针对这一缺陷,文中提出了一种改进型列表调度算法,通过特殊列表片段将权值一致的任务整合到一起,并对特殊列表片段的调度解空间进行遍历,以迭代产生更优的调度列表获得更好的调度效果。随机DAG图测试结果表明,提出的算法调度效果优异,算法平均增强比最高可达15.3%,不仅适用于多种任务图规模,且在CCR和平均出入度较高的情况下有更好的调度性能。The list-based task scheduling algorithm has been widely used in the field of task scheduling.The classic list scheduling algorithm randomly sorts the task nodes with the same weight in the node sorting stage.But the sorting method is rough and difficult to achieve better results.In view of this defect,this study proposed an improved list scheduling algorithm.This algorithm integrated tasks with consistent weights through special list fragments,and traversed the scheduling solution space of special list fragments to iteratively generate better scheduling lists to obtain a better scheduling results.The results of random DAG graph test showed that the proposed algorithm had excellent scheduling effect,and the average algorithm enhancement ratio was up to 15.3%,indicating the proposed method was not only suitable for multiple task map scales,but also had better scheduling performance under the condition of higher CCR and higher average access.

关 键 词：调度算法 节点排序 任务权值 权值一致排序困境 特殊列表片段 调度空间 

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