张多利,廖金月,罗 乐,倪 伟,宋宇鲲.一种多核系统任务扰动迭代算法[J].电子测量与仪器学报,2020,34(9):133-139 |
一种多核系统任务扰动迭代算法 |
Task perturbation iteration algorithm on multicore systems |
|
DOI: |
中文关键词: 静态任务 调度算法 扰动因子 扰动策略 搜索空间 |
英文关键词:static task scheduling turmoil element perturbation strategy search space |
基金项目:国家自然科学基金(61874156)资助项目 |
|
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 |
|
摘要点击次数: 323 |
全文下载次数: 572 |
中文摘要: |
任务调度问题是多核处理器相关技术的一个重要组成部分。 基于列表的调度算法因其低复杂度和高效率得到广泛关
注,但确定任务优先级列表方法的单一性使得算法对解空间搜索不够,易陷入局部最优。 为此,提出一种基于任务扰动的迭代
型列表调度算法(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阅读器 |
|
|
|