面向计算密集型批处理的任务调度策略

发布时间：2020-03-30 21:04

【摘要】：在计算密集型批处理任务中,有一种任务运行时间很长、且要占用大量CPU和内存资源,例如基因测序任务。对于该种类型的任务调度策略来讲,任务完成时间是衡量调度策略好坏的一个重要指标。在任务大小和数量一定时,任务完成时间越小,系统服务质量越高。设计了一种面向计算密集型批处理任务的调度系统。该系统采用一种混合改进遗传模拟退火算法(Improved Genetic Simulated Annealing,IGSA)来进行任务调度。该算法综合了遗传算法(Genetic Algorithm,GA)多点寻优和模拟退火算法(Simulated Annealing,SA)局部搜索能力强的优势,其基本思想是对遗传算法的初始化方法、选择算子、交叉算子、交叉概率、变异概率和算法的终止条件做出一定的改进,其中初始化方法采用在多个随机解中选出一部分最优秀解作为部分初始解的方法,选择算子采用最优个体直接保留到下一代的方法,交叉算子采用一种双精英保留策略,交叉概率和变异概率采用自适应概率的方法,算法终止条件采用种群最优解连续几代都没有发生改变则终止算法的方法。然后将改进遗传算法(Improved Genetic Algorithm,IGA)产生的多个解作为模拟退火算法的输入,同时对多个解进行模拟退火并将结果中最优秀的解作为算法的最终解。实验结果表明,相比于RoundRobin(RR)算法、改进的遗传算法、模拟退火算法的任务调度,混合改进遗传模拟退火算法更能缩短任务的完成时间,同时更能保障系统的负载均衡性。
【图文】：

图 2-6 Min-Min 算法示例2.2.3 启发式调度算法分布式计算系统中任务调度是一个多对多的组合优化问题，也是一个 NP-Hard问题。群智能算法相比传统算法而言在组合优化问题上表现出了明显的优势，，它们往往通过模拟自然界动物群体的一些习性来表达生物的智慧。例如，遗传算法用一个个体表示一个任务调度方案，通过种群不断的选择、交叉、变异而得到最优的调度方案[34]。粒子群算法通过模拟鸟类觅食的行为使多个解之间相互交换信息从而找到最优解[34]。蚁群算法通过模拟蚂蚁寻找食物的过程中通过信息素与其它伙伴相互交流的过程而找到最佳调度方案[34]。

图 2-7 Max-Min 算法示例2.3 本章小结数据一致性的保证、系统故障的处理、资源的有效利用、集群扩展性的保障、调度策略的灵活配置等一系列问题都是调度系统设计的难点，而不同的集群调度架构在这些问题的处理上各有千秋。调度系统中任务调度策略对系统的性能至关重要，本章在介绍了主流的集群调度架构后，阐述了独立任务的调度模型以及常用调度算法。
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 车明康;;性能比8096强一倍的80C 196 16位单片机[J];微电子学与计算机;1988年12期

2 杨志豪;赵太银;姚兴苗;李磊;;一种适应数据与计算密集型任务的私有云系统实现研究[J];计算机应用研究;2011年02期

3 赵吉志;;5600系列处理器浅析[J];科技浪潮;2010年04期

4 ;成品油零售求变 安腾2在计算密集型应用方案[J];信息系统工程;2004年03期

5 ;AlphaServer DS20强化64位计算[J];每周电脑报;1999年06期

6 江先阳;刘新春;张佩珩;孙凝晖;徐志伟;;计算密集型体系集成DDR SDRAM控制器设计[J];计算机工程与科学;2006年03期

7 史红周,李锦涛,郭俊波,黄晁,叶剑;图形终端应用协议中计算密集型操作的分布技术[J];计算机辅助设计与图形学学报;2005年04期

8 朱敏;刘雷波;尹首一;杨晨;王文杰;魏少军;;H.264计算密集型任务在可重构处理器上的映射[J];电路与系统学报;2013年02期

9 王尚万家;;教你打造终极游戏机[J];当代职校生;2004年11期

10 殷开爽;骆丽;;基于SOPC的MPEG-4视频播放器[J];单片机与嵌入式系统应用;2006年05期

相关会议论文 前4条

1 张盛;张明华;刘雅杰;;云平台SaaS模式下位场数据处理软件设计与实现[A];2017中国地球科学联合学术年会论文集（四十二）——专题81：应用地球物理学前沿、专题82：工程结构性态化设计与地震韧性、专题83：地球重力场及其地学应用[C];2017年

2 唐思宇;朱振宇;许冬燕;;面向多终端协同的多域融合边缘控制系统[A];物联网与无线通信-2018年全国物联网技术与应用大会论文集[C];2018年

3 刘滨;石峰;;基三分层互连网络中负载平衡的研究与仿真[A];中国系统仿真学会第五次全国会员代表大会暨2006年全国学术年会论文集[C];2006年

4 宋贤鑫;张一帆;秦晓琦;冯志勇;;车联网中基于边缘计算的感知决策技术[A];第十四届中国智能交通年会论文集（2）[C];2019年

相关重要报纸文章 前10条

1 赛迪评测计算机整机实验室;图形/计算密集型应用用户的选择[N];中国计算机报;2003年

2 ;计算场为PC带来力量[N];网络世界;2001年

3 ;IBM启动高性能计算计划[N];计算机世界;2007年

4 本报记者 逄丹;高性能计算和云计算是否可以调和？[N];通信产业报;2011年

5 云中子;解析新时代下的高性能计算[N];中国信息化周报;2015年

6 计算机世界评测实验室 于泽;小身材 大内涵[N];计算机世界;2012年

7 安琳 赛迪智库软件与信息服务业研究所;移动云计算发展亟须突破四大瓶颈[N];通信产业报;2014年

8 ;IBM TotalStorage DS4800[N];中国电子报;2005年

9 ;Linux更快 更强 更企业[N];网络世界;2004年

10 刘洪宇;IDF2009预示快速创新与整合风向[N];中国计算机报;2009年

相关博士学位论文 前1条

1 管茂林;面向计算密集型嵌入式应用的VLIW编译优化技术研究[D];国防科学技术大学;2012年

相关硕士学位论文 前10条

1 何昕迪;移动微云中的任务分配框架及算法的研究[D];上海交通大学;2017年

2 胡江峰;面向计算密集型批处理的任务调度策略[D];华中科技大学;2019年

3 刘锐;基于移动边缘计算的任务卸载策略研究[D];东华大学;2019年

4 左超;移动边缘计算中的端到端任务分配算法[D];广东工业大学;2019年

5 刘国强;基于移动边缘计算的任务卸载策略研究[D];哈尔滨工业大学;2018年

6 肖骞;移动边缘计算网络联合计算迁移决策与资源分配算法研究[D];重庆大学;2018年

7 盛冲冲;计算密集型应用在新型众核处理机环境下的实现及性能[D];复旦大学;2014年

8 郭俊武;移动云环境下的计算密集型任务迁移技术[D];哈尔滨工业大学;2015年

9 高哲;基于能耗的云迁移方法研究[D];西安理工大学;2016年

10 王福友;计算密集型应用下嵌入式双机容错系统研究与实现[D];西南交通大学;2014年

本文编号：2608063