一种多核系统任务扰动迭代算法  

Task perturbation iteration algorithm on multicore systems

作　　者：张多利[1,2] 廖金月 罗乐 倪伟 宋宇鲲[1,2] Zhang Duoli;Liao Jinyue;Luo Le;Ni Wei;Song Yukun(Institute of VLSI Design,Hefei University of Technology,Hefei 230009,China;IC Design Web-cooperation Research Center of MOE,Hefei 230009,China)

机构地区：[1]合肥工业大学微电子设计研究所,合肥230009 [2]教育部IC设计网上合作研究中心,合肥230009

出　　处：《电子测量与仪器学报》2020年第9期133-139,共7页Journal of Electronic Measurement and Instrumentation

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

摘　　要：任务调度问题是多核处理器相关技术的一个重要组成部分。基于列表的调度算法因其低复杂度和高效率得到广泛关注,但确定任务优先级列表方法的单一性使得算法对解空间搜索不够,易陷入局部最优。为此,提出一种基于任务扰动的迭代型列表调度算法(task perturbation iteration algorithm, TPIA)。该算法通过选取任务扰动因子按照一定扰动策略进行调度列表迭代,对迭代后的列表进行贪心选择,生成更优的调度列表序列以得到更好的调度结果。通过实例和随机有向无环图(DAG)有限集对算法进行验证,结果表明算法能有效改善调度解,调度性能提升平均可达16.51%,适宜处理大规模、高出入度的复杂DAG图;针对TPIA算法在低任务总数高通讯开销情况下性能有所下降的问题,对平均任务节点数130以下的任务图进行分组测试,获得了对应的CCR上界值及其变化趋势。Task scheduling is an important part of multi-core processor technology.List-based scheduling algorithms are widely concerned because of their low complexity and high efficiency,but the singleness of the task priority list method makes the algorithm not enough to search the solution space,and it is easy to fall into the local optimal.Therefore,proposes an iterative list scheduling algorithm(TPIA)based on task perturbation.The algorithm selects the task disturbance factor to iterate the scheduling list according to a certain disturbance strategy,greedily selects the iterated list,and generates a better scheduling list sequence to obtain better scheduling results.The thesis validates the algorithm through examples and a limited set of random DAG graphs.The results show that the algorithm can effectively improve the scheduling solution,and the scheduling performance can be improved by an average of 16.51%.It is suitable for processing large-scale and high-entry complex DAG graphs.When the total number of tasks is low and the communication overhead is high,the performance is reduced.The task graphs with an average task node number of less than 130 are grouped and tested to obtain the corresponding upper CCR and its change trend.

关 键 词：静态任务 调度算法 扰动因子 扰动策略 搜索空间 

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