| 引用本文: | 谢志强,韩英杰,齐永红,等.基于关键路径和任务复制的多核调度算法.[J].国防科技大学学报,2014,36(1):172-177.[点击复制] |
| XIE Zhiqiang,HAN Yingjie,QI Yonghong,et al.A scheduling algorithm for multi-core based on critical path and task duplication[J].Journal of National University of Defense Technology,2014,36(1):172-177[点击复制] |
|
| |
|
|
| 本文已被：浏览 8954次 下载 7057次 |
| 基于关键路径和任务复制的多核调度算法 |
| 谢志强1, 韩英杰1, 齐永红1, 杨静2 |
|
(1.哈尔滨理工大学 计算机学院， 黑龙江 哈尔滨 150080;2.哈尔滨工程大学 计算机学院，黑龙江 哈尔滨 150001)
|
| 摘要: |
| 针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响，导致任务完成总时间延迟的问题，提出了基于关键路径和任务复制(CPTD)的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树；再在生成的产品加工树中找到关键路径，并采取使关键路径上节点的紧前节点尽早调度的方式，使关键路径上节点尽早开始执行，进而使产品加工树中节点完成时间得以提前，达到缩短任务执行总时间的目的。理论分析表明，CPTD算法能够实现应用程序在多核上充分并行处理，并能缩短任务完成时间。 |
| 关键词: 单任务 任务复制 关键路径 产品加工树 多核 |
| DOI：10.11887/j.cn.201401030 |
| 投稿日期：2013-04-25 |
| 基金项目:国家自然科学基金资助项目（60873019） |
|
| A scheduling algorithm for multi-core based on critical path and task duplication |
| XIE Zhiqiang1, HAN Yingjie1, QI Yonghong1, YANG Jing2 |
|
(1. College of Computer，Harbin University of Science and Technology, Harbin 150080，China;2.College of Computer, Harbin Engineering University, Harbin 150001, China)
|
| Abstract: |
| Aiming at the problem of current scheduling algorithm for multi-core which fails to consider that the nodes on the critical path have a major impact on the ending time of tasks, leading to the delay of the task completion time; a scheduling algorithm based on critical path and task duplication (CPTD) is proposed. Firstly, the fork-nodes were duplicated to change the task graph into products processing tree, then the critical path in the processing tree were found, and the father nodes of the nodes on critical path were made to work at the earliest time. These operations can advance the start time of nodes on critical path. The purpose of the above operation is to shorten the implementation of the mandate of the total time. Theoretical analysis shows that the algorithm can achieve a single task fully parallel processing on multi-core, and also can shorten the completion time of the tasks. |
| Keywords: single-task task duplication critical path processing flow chart multi-core |
|
|
