多核系统静态任务调度的启发式算法  

Heuristic algorithm for static tasks scheduling of multicore system

作　　者：宋宇鲲[1] 韦龙龙 张多利[1] 

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

出　　处：《电子测量与仪器学报》2018年第5期134-141,共8页Journal of Electronic Measurement and Instrumentation

基　　金：国家自然科学基金(61106020)资助项目

摘　　要：在任务调度研究领域,列表类调度算法的优化研究始终备受关注,针对经典列表调度算法难以获得理想调度解的缺陷,提出一种迭代型列表调度算法。该算法采用遍历宏块拓扑序列技术,扩大任务图拓扑序列搜索空间以得到更小的任务图调度长度。理论分析表明,对于任意的任务图,该算法得到的调度长度必不大于经典列表调度算法。以4种常见类型和随机类型的任务图样本证实,迭代型列表调度算法能够有效改善调度解,尤其在平均通信计算时间比超过1的情况下,调度性能的平均提升超过14.6%,最大提升达到102.8%。In the area of task scheduling research,the technology of list scheduling constantly gets much attention from the research community. Aiming at the defect of the simple list scheduling( SLS) algorithm cannot get desirable schedule solution,the iterative list scheduling( ILS) algorithm is proposed in this paper. To get smaller schedule length,the proposed algorithm enlarges the task graph topological order search space by traversing the macroblock topological orders. According to theoretical analysis,the schedule length of the ILS algorithm is less than or equal to that of the SLS algorithm for any task graph. The experimental results point out that the ILS algorithm can effectively improve the scheduling solution,the average accelerate ratio exceeds 14. 6% and the maximal accelerate ratio reaches 102. 8% when communication to computation ratio exceeds 1.

关 键 词：静态任务 调度算法 宏块 拓扑序列 搜索空间 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]