基于关键路径和任务复制的多核调度算法

发布时间：2018-07-29 19:48

【摘要】：针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响,导致任务完成总时间延迟的问题,提出了基于关键路径和任务复制(CPTD)的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树;再在生成的产品加工树中找到关键路径,并采取使关键路径上节点的紧前节点尽早调度的方式,使关键路径上节点尽早开始执行,进而使产品加工树中节点完成时间得以提前,达到缩短任务执行总时间的目的。理论分析表明,CPTD算法能够实现应用程序在多核上充分并行处理,并能缩短任务完成时间。
[Abstract]:At present, most multi-core processor task allocation optimization algorithms do not consider the critical path node on the task completion time, resulting in the total task completion time delay problem. This paper proposes a single task scheduling algorithm based on critical path and task replication (CPTD). CPTD algorithm transforms the task graph into the corresponding product processing tree by copying the fork nodes in the task graph, and then finds the critical path in the generated product processing tree. In order to make the node in the critical path start to execute as early as possible, the completion time of the node in the product processing tree can be advanced and the total time of task execution can be shortened by making the node on the critical path be scheduled as early as possible. Theoretical analysis shows that the CPTD algorithm can achieve full parallel processing on multi-core applications and shorten the task completion time.
【作者单位】： 哈尔滨理工大学计算机学院;哈尔滨工程大学计算机学院;
【基金】：国家自然科学基金资助项目(60873019)
【分类号】：TP332

【参考文献】

相关期刊论文 前9条

1 孟宪福;闫玲玲;刘伟伟;;基于动态任务优先级的网格任务调度算法研究[J];大连理工大学学报;2012年02期

2 陈莉丽;姚益平;蔡潞;;多核环境下负载均衡的并行离散事件全局调度机制[J];国防科技大学学报;2012年04期

3 周双娥,袁由光,熊兵周,欧中红;基于任务复制的处理器预分配算法[J];计算机学报;2004年02期

4 邸楠,王韬,李晓明;LilyTask任务并行环境中基于任务关系的初始任务分配算法[J];计算机学报;2005年05期

5 谢志强;杨静;周勇;张大力;谭光宇;;基于工序集的动态关键路径多产品制造调度算法[J];计算机学报;2011年02期

6 谢志强;辛宇;杨静;;基于设备空闲事件驱动的综合调度算法[J];机械工程学报;2011年11期

7 徐成;赵林祥;杨志邦;;一种基于多处理器任务复制的分簇调度算法[J];计算机应用研究;2012年08期

8 陈芳园;张冬松;刘聪;王志英;;基于取指执行时序范畴的多核共享Cache干扰分析[J];计算机研究与发展;2013年01期

9 何琨;赵勇;陈阳;;分布式环境下多任务调度问题的分析与求解[J];系统工程理论与实践;2007年05期

【共引文献】

相关期刊论文 前10条

1 夏冰;李洁冰;;一种面向任务、可重构的主控中心设计方案[J];成组技术与生产现代化;2011年01期

2 黄漾;;分布式环境下任务调度探讨[J];电脑知识与技术;2011年19期

3 宋效东;窦万峰;汤国安;张刚;江岭;;并行累积可视性分析中的任务调度研究[J];地理与地理信息科学;2013年04期

4 何琨;黄文奇;;分布式内存机器中优化调度问题的数学模型[J];华中科技大学学报(自然科学版);2008年02期

5 赵明宇;张田文;;一种分布式计算环境下并行应用的调度算法[J];计算机研究与发展;2008年04期

6 李仁发;刘彦;徐成;;多处理器片上系统任务调度研究进展评述[J];计算机研究与发展;2008年09期

7 刘庆强;程亮;牟菡渝;;基于推荐机制的人机交互任务调度算法[J];佳木斯大学学报(自然科学版);2009年03期

8 夏冰;李金武;裴斐;郑秋生;;一种分布式安全评估通信与调度模型[J];计算机工程与应用;2011年12期

9 黎忠文;;嵌入式实时系统容错集成技术的研究[J];计算机科学;2006年05期

10 王小非;方明;;一种基于调度簇树的周期性分布实时任务调度算法[J];计算机科学;2007年03期

相关会议论文 前1条

1 夏冰;王志奇;郑秋生;李向东;;政务终端安全面临的问题与对策研究[A];第27次全国计算机安全学术交流会论文集[C];2012年

相关博士学位论文 前8条

1 官东;网格环境下的HLA仿真关键问题研究[D];中南大学;2011年

2 蒋建春;异构多核嵌入式软件关键问题研究[D];重庆大学;2011年

3 寇玮华;基于并行分层式链路分布式数据更新的协议及副本复制研究[D];西南交通大学;2004年

4 赵明宇;集群系统的调度算法研究[D];哈尔滨工业大学;2007年

5 兰舟;分布式系统中的调度算法研究[D];电子科技大学;2009年

6 张建军;基于Fork-Join任务图的调度算法研究[D];华中科技大学;2010年

7 刘彦;异构多核片上系统的任务调度及应用研究[D];湖南大学;2009年

8 王忠凯;动车组运用检修计划优化方法的研究[D];中国铁道科学研究院;2012年

相关硕士学位论文 前10条

1 闫思柱;可重构嵌入式系统软硬件划分及任务调度算法研究[D];哈尔滨理工大学;2010年

2 赵磊;适应多核处理器的任务调度研究[D];哈尔滨理工大学;2010年

3 李金武;分布式主机安全评估关键技术研究[D];中原工学院;2011年

4 曹立强;基于SWE的传感规划服务的研究与设计[D];西安工业大学;2011年

5 张建强;基于任务并行策略的多核程序优化研究[D];辽宁师范大学;2011年

6 徐钧磊;退火进化算法在网格任务调度中的应用和研究[D];南京信息工程大学;2011年

7 邵侠;存在延迟约束的综合柔性调度的研究[D];哈尔滨理工大学;2011年

8 常宁宁;基于设备工序紧凑的综合调度算法的研究[D];哈尔滨理工大学;2011年

9 仇文娟;云计算中依赖任务动态并行调度机制的研究[D];大连理工大学;2011年

10 于凤;考虑预期库存可用性的车间调度算法研究[D];大连理工大学;2011年

【二级参考文献】

相关期刊论文 前10条

1 何琨;赵勇;;网格环境下资源调度问题的统一建模与分析[J];华中科技大学学报(自然科学版);2006年03期

2 谢志强,刘胜辉,乔佩利;基于ACPM和BFSM的动态Job-Shop调度算法[J];计算机研究与发展;2003年07期

3 林剑柠;吴慧中;;一种基于动态决策路径的网格任务调度算法[J];计算机研究与发展;2008年05期

4 杨志义;杨刚;张海辉;;一种面向服务的事件驱动架构信息集成平台构造方法[J];计算机研究与发展;2008年10期

5 邵维忠,梅宏;统一建模语言UML述评[J];计算机研究与发展;1999年04期

6 谢志强,刘胜辉,乔佩利;电机产品加工的动态调度算法[J];计算机集成制造系统-CIMS;2003年06期

7 张德富,李新;求解作业车间调度问题的快速启发式算法[J];计算机集成制造系统;2005年02期

8 范路桥,常会友,朱旭东;一种改进的作业车间调度算法及其实现[J];计算机集成制造系统;2005年05期

9 梁峰;江志斌;陶俐言;赵大为;;基于事件驱动的制造资源冲突实时消解方法[J];计算机集成制造系统;2007年02期

10 刘振英,方滨兴,张毅;TSA-OT:一个调度Out-Tree任务图的算法[J];计算机学报;2001年04期

相关博士学位论文 前2条

1 谢志强;工件间有约束的复杂产品工序调度研究[D];哈尔滨理工大学;2009年

2 苏年乐;仿真模型可移植性规范的多核并行化研究[D];国防科学技术大学;2010年

【相似文献】

相关期刊论文 前10条

1 赵欢;江文;李学辉;;异构系统中的综合性启发式任务调度算法[J];计算机应用;2010年05期

2 兰舟;孙世新;;基于关键路径知识的任务调度遗传算法[J];计算机应用;2008年02期

3 连顺金;求AOE-网中关键路径的一种算法[J];黎明职业大学学报;2001年02期

4 曾党泉;;基于AOE网的工作流程主关键路径的研究[J];科技广场;2008年08期

5 徐凤生,黄倩;关键路径求解的新算法[J];计算机应用;2004年12期

6 王雪梅;杜凯;;基于AOE网的多源点多汇点关键路径研究[J];科技创新导报;2009年14期

7 徐敏;谭文安;;面向软件系统的指令时序建模与分析方法[J];计算机与数字工程;2010年11期

8 潘全科,朱剑英;一类解决Job shop问题的改进进化规划[J];山东农业大学学报(自然科学版);2005年02期

9 严晓浪,季爱明,沈海斌;性能优化的现场可编程门阵列快速编译方法[J];浙江大学学报(工学版);2005年10期

10 张芳;;前N条最短路径在网络中的应用[J];福建电脑;2008年05期

相关会议论文 前10条

1 徐上;;企业内部信息沟通关键路径的判定及其应用[A];推进铁路新跨越加快经济大发展——中国科协2004年学术年会铁道分会场论文集[C];2004年

2 张涛;杨卓;;单任务和双任务事件中脑电活动的信息流特征[A];第一届全国脑与认知科学学术研讨会论文集[C];2005年

3 刘瑞华;涂凍生;;生产加工网络的关键路径与扰动分析[A];1993中国控制与决策学术年会论文集[C];1993年

4 刘自宽;谭思彤;涂凍生;;随机串行生产线性能优化的非光滑分析方法[A];1998中国控制与决策学术年会论文集[C];1998年

5 李勇建;涂(?)生;;串行生产线存储单元的序优配置[A];2000中国控制与决策学术年会论文集[C];2000年

6 李勇建;涂奉生;;具有偏序结构的一般网络系统的关键路径与扰动分析问题[A];第十九届中国控制会议论文集（一）[C];2000年

7 李勇建;涂凍生;;串行生产线的关键路径计算与扰动分析[A];2001中国控制与决策学术年会论文集[C];2001年

8 赵建;;委托代理模型下国有煤矿经理激励机制设计[A];第一届全国安全科学理论研讨会论文集[C];2007年

9 李勇建;涂凍生;;应用关键路径串行再生系统的参数优化[A];2001中国控制与决策学术年会论文集[C];2001年

10 杨芳;;离散制造企业生产计划与控制管理系统研究[A];'06MIS/S&A学术交流会论文集[C];2006年

相关重要报纸文章 前10条

1 广文;三星半年多完成全年接单任务[N];中国船舶报;2011年

2 唐晓玉/译;关键路径公司 虚增收入遭起诉[N];中国财经报;2003年

3 通讯员 王小英;江阀厂提前4个月完成全年接单任务[N];中国船舶报;2008年

4 吉林 飘零雪;网页安全之简单任务[N];电脑报;2003年

5 记者　 陆旭升;我市已完成早稻订单任务[N];金华日报;2006年

6 ;明确“路标”强化执行[N];人民邮电;2003年

7 ;明确“路标” 强化执行[N];人民邮电;2003年

8 宁伦荣;当涂县：超额完成全年粮油订单任务[N];粮油市场报;2005年

9 记者 李建永;把城镇建设作为率先建设沿海强市的关键路径[N];秦皇岛日报;2007年

10 本报特派记者 卢建宁;产品走向世界的关键路径[N];广西日报;2010年

相关博士学位论文 前10条

1 兰舟;分布式系统中的调度算法研究[D];电子科技大学;2009年

2 崔万安;广义优先关系网络关键性分析[D];华中科技大学;2006年

3 高守玮;一类Flow shop生产调度问题及其优化方法之分析与研究[D];上海交通大学;2007年

4 何琨;多任务调度问题的研究与实现[D];华中科技大学;2006年

5 张建军;基于Fork-Join任务图的调度算法研究[D];华中科技大学;2010年

6 李勇;多Agent系统联盟及任务分配的研究[D];合肥工业大学;2008年

7 费蓉;动态规划研究及其在电力市场动态分区定价问题中的应用[D];西安理工大学;2009年

8 张涛;装备制造业突破性创新机制与建设路径研究[D];燕山大学;2012年

9 刘智全;企业R&D项目的过程控制与绩效评价研究[D];哈尔滨工业大学;2009年

10 褚春超;工程项目进度管理方法与应用研究[D];天津大学;2007年

相关硕士学位论文 前10条

1 梁红建;挣值分析法在项目进度费用管理的应用研究[D];吉林大学;2007年

2 丁世军;港口机械产品制造项目工期—费用优化研究[D];武汉理工大学;2010年

3 龙凯;关键链在Y公司项目管理中的应用研究[D];上海交通大学;2008年

4 吴逢庆;改进蚁群算法在车间调度中的应用研究[D];合肥工业大学;2009年

5 李振宏;随机环境下关键路径问题的研究[D];河北大学;2013年

6 王凯;基于关键路径的控制图式的项目时间管理[D];上海交通大学;2011年

7 刘莉;异构集群下并行任务的复制调度算法[D];武汉纺织大学;2013年

8 柴佳;关键路径下工程项目成本预警系统设计：一项实地研究[D];西南财经大学;2011年

9 赵林祥;基于多核处理器任务复制的分簇调度算法研究[D];湖南大学;2012年

10 钟志辉;JM ITV项目进度关键路径管理研究[D];华南理工大学;2011年

，

本文编号：2153799