电子测量与仪器学报

张多利,廖金月,罗乐,倪伟,宋宇鲲.一种多核系统任务扰动迭代算法[J].电子测量与仪器学报,2020,34(9):133-139

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

Task perturbation iteration algorithm on multicore systems

DOI：

英文关键词:static task scheduling turmoil element perturbation strategy search space

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

作者	单位
张多利	1. 合肥工业大学微电子设计研究所，2. 教育部 IC 设计网上合作研究中心
廖金月	1. 合肥工业大学微电子设计研究所，2. 教育部 IC 设计网上合作研究中心
罗乐	1. 合肥工业大学微电子设计研究所，2. 教育部 IC 设计网上合作研究中心
倪伟	1. 合肥工业大学微电子设计研究所，2. 教育部 IC 设计网上合作研究中心
宋宇鲲	1. 合肥工业大学微电子设计研究所，2. 教育部 IC 设计网上合作研究中心

Author	Institution
Zhang Duoli	1. Institute of VLSI Design, Hefei University of Technology,2. IC Design Web-cooperation Research Center of MOE
Liao Jinyue	1. Institute of VLSI Design, Hefei University of Technology,2. IC Design Web-cooperation Research Center of MOE
Luo Le	1. Institute of VLSI Design, Hefei University of Technology,2. IC Design Web-cooperation Research Center of MOE
Ni Wei	1. Institute of VLSI Design, Hefei University of Technology,2. IC Design Web-cooperation Research Center of MOE
Song Yukun	1. Institute of VLSI Design, Hefei University of Technology,2. IC Design Web-cooperation Research Center of MOE

摘要点击次数: 422

全文下载次数: 745

中文摘要:

任务调度问题是多核处理器相关技术的一个重要组成部分。基于列表的调度算法因其低复杂度和高效率得到广泛关注,但确定任务优先级列表方法的单一性使得算法对解空间搜索不够,易陷入局部最优。为此,提出一种基于任务扰动的迭代型列表调度算法(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.

查看全文查看/发表评论下载PDF阅读器