国防科技大学学报
國防科技大學學報
국방과기대학학보
JOURNAL OF NATIONAL UNIVERSITY OF DEFENSE TECHNOLOGY
2014年
1期
172-177
,共6页
谢志强%韩英杰%齐永红%杨静
謝誌彊%韓英傑%齊永紅%楊靜
사지강%한영걸%제영홍%양정
单任务%任务复制%关键路径%产品加工树%多核
單任務%任務複製%關鍵路徑%產品加工樹%多覈
단임무%임무복제%관건로경%산품가공수%다핵
single-task%task duplication%critical path%processing flow chart%multi-core
针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响,导致任务完成总时间延迟的问题,提出了基于关键路径和任务复制(CPTD )的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树;再在生成的产品加工树中找到关键路径,并采取使关键路径上节点的紧前节点尽早调度的方式,使关键路径上节点尽早开始执行,进而使产品加工树中节点完成时间得以提前,达到缩短任务执行总时间的目的。理论分析表明,CPTD算法能够实现应用程序在多核上充分并行处理,并能缩短任务完成时间。
針對目前大多數多覈處理器任務分配優化算法沒有攷慮關鍵路徑上節點對任務完成時間的重要影響,導緻任務完成總時間延遲的問題,提齣瞭基于關鍵路徑和任務複製(CPTD )的單任務調度算法。CPTD算法通過複製任務圖中fork節點的方式將任務圖轉化為與之相對應的產品加工樹;再在生成的產品加工樹中找到關鍵路徑,併採取使關鍵路徑上節點的緊前節點儘早調度的方式,使關鍵路徑上節點儘早開始執行,進而使產品加工樹中節點完成時間得以提前,達到縮短任務執行總時間的目的。理論分析錶明,CPTD算法能夠實現應用程序在多覈上充分併行處理,併能縮短任務完成時間。
침대목전대다수다핵처리기임무분배우화산법몰유고필관건로경상절점대임무완성시간적중요영향,도치임무완성총시간연지적문제,제출료기우관건로경화임무복제(CPTD )적단임무조도산법。CPTD산법통과복제임무도중fork절점적방식장임무도전화위여지상대응적산품가공수;재재생성적산품가공수중조도관건로경,병채취사관건로경상절점적긴전절점진조조도적방식,사관건로경상절점진조개시집행,진이사산품가공수중절점완성시간득이제전,체도축단임무집행총시간적목적。이론분석표명,CPTD산법능구실현응용정서재다핵상충분병행처리,병능축단임무완성시간。
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.