异构计算环境下任务调度算法的研究

发布时间：2020-06-04 06:55

【摘要】： 随着计算机技术的发展,计算机应用范围不断扩大,异构计算系统在并行处理中得到了广泛运用。任务调度是并行处理中的关键问题,异构计算环境下的调度问题则更加复杂,是研究中亟待解决的一个难题。 调度的目标是在满足一定性能指标和有限约束关系的前提下减少总的执行时间。绝大部分情况下的任务调度问题已经被证明为NP完全问题,这使得启发式方法在调度中得到了普遍运用。本文针对异构计算系统的任务调度展开研究,在经典的任务模型上提出了两个新的算法： 针对基于优先驱动的表调度算法常出现优先级相同的问题,提出了一种综合性启发式算法(Heterogeneous Critical Path First Synthetic, HCPFS)。该算法在任务选择阶段按照是否关键路径节点、ranku值递减、后继数递减的优先级顺序选择任务,在任务分配阶段根据任务的最早完成时间进行处理器选择,并采用了任务复制和插入策略,以达到充分利用处理器资源,减少任务通信开销的目的。 在采用复制方法的调度算法中,是以当前任务的开始时间、完成时间和执行时间等作为任务分配的依据,往往会产生不必要的任务复制。本文提出了一种基于后继任务最早完成的调度方法(Heterogeneous Successor Finish Earliest, HSFE),根据下一调度任务与当前调度任务的关系来进行任务分配,在当前调度任务与下一调度任务存在前驱后继关系时,以下一任务的最早完成作为当前处理器分配的依据,从而有效抑制了任务的不必要复制,增加了任务调度空间,提高了调度效率。 本文从多个角度对算法进行了测试,通过对调度长度下界比、加速比的比较可知,本文提出的多优先级策略和基于后继就绪任务调度的方法有效地缩短了调度长度,通过对任务平均复制比和平均执行时间下界比的比较可知,.算法根据后继调度任务选择处理器分配,有效地抑制了任务的多余复制,节约了处理器资源,复制方法体现了更好的灵活性。
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：TP338.6

【相似文献】

相关期刊论文 前10条

1 袁志祥;王小平;;基于广义随机Petri网的网格调度模型[J];计算机工程;2010年02期

2 黄海于;何大可;;一种基于负载均衡性的网格任务调度算法[J];计算机工程;2010年02期

3 蒋瀚洋;王樱;;网格计算中Min-Min算法及改进算法的研究[J];计算机时代;2010年01期

4 苏翊;;网格任务调度算法Min-min的GridSim模拟实现[J];电脑知识与技术;2010年05期

5 邓定兰;于炯;谭亚丽;吕良干;;网格工作流的动态贪心调度算法[J];计算机工程;2010年03期

6 易侃;王汝传;;一种基于SOA的网格任务调度框架[J];计算机技术与发展;2010年04期

7 张建生;;基于人工鱼群算法的网格任务调度策略[J];电脑编程技巧与维护;2010年10期

8 孟宪福;刘伟伟;;基于选择性复制前驱任务的DAG调度算法[J];计算机辅助设计与图形学学报;2010年06期

9 谭亚丽;于炯;邓定兰;吕良干;田国忠;;基于多维QoS约束的网格任务调度算法[J];计算机工程;2010年12期

10 叶春晓;陆杰;;基于改进遗传算法的网格任务调度研究[J];计算机科学;2010年07期

相关会议论文 前4条

1 李英楠;余华山;;一种基于任务复杂度评估的网格任务调度算法[A];2010国际信息技术与应用论坛论文集[C];2010年

2 吕默威;韩世杰;张晓彤;何杰;余美强;;一种兼有语音通信功能的实时定位系统的设计与实现[A];第六届和谐人机环境联合学术会议（HHME2010)、第19届全国多媒体学术会议（NCMT2010）、第6届全国人机交互学术会议（CHCI2010）、第5届全国普适计算学术会议（PCC2010）论文集[C];2010年

3 陈平;王柏;徐六通;吴斌;王艳辉;;电信社群网络中介度的网格并行算法及调度算法[A];2006年全国通信软件学术会议论文集[C];2006年

4 王益;邢春晓;周立柱;;海量信息系统中服务器机群和客户机结合的分布式虚拟现实计算[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

相关博士学位论文 前4条

1 巴巍;实时系统动态优先级任务调度算法的研究[D];大连理工大学;2010年

2 钟锋;基于网格的煤炭企业信息化关键技术研究[D];中国矿业大学（北京）;2009年

3 贺小川;单芯片系统（SoC）中的实时任务调度算法研究[D];国防科学技术大学;2009年

4 马丹;任务间相互依赖的并行作业调度算法研究[D];华中科技大学;2007年

相关硕士学位论文 前10条

1 王向慧;网格计算中任务调度算法的改进[D];大连交通大学;2010年

2 许玉杰;基于信任模型的数据网格任务调度算法研究[D];大连海事大学;2010年

3 秦涛;基于最早完成时间的网格任务调度算法[D];大连海事大学;2010年

4 任鹏;嵌入式多任务调度算法及CAN总线通信技术研究[D];西安电子科技大学;2010年

5 肖晓锋;基于多QoS约束的网格计算任务调度算法研究[D];西南交通大学;2010年

6 刘定一;基于SOA的海量遥感数据并行处理的研究与应用[D];河南大学;2010年

7 罗飞;片上多处理器芯片上的SPX性能优化研究[D];上海交通大学;2010年

8 钟英姿;QoS约束下的网格任务调度算法研究[D];中南大学;2010年

9 王晓宇;实时任务在集群计算中的自适应容错调度研究[D];复旦大学;2010年

10 范国昌;网格计算的Online-Min-Min任务调度算法研究[D];北京邮电大学;2010年

，

本文编号：2696040