分布式并行计算智能调度策略的研究与实现

发布时间：2020-05-16 06:57

【摘要】：多核计算、网格计算、云计算是近年来信息技术领域的研究热点,其技术的核心在于分布式并行计算的调度,而调度模型和调度算法是调度最重要的两个方面。因此,本文研究分布式并行计算的任务调度模型和任务调度算法,所做的主要工作如下:? 1)提出了一种更加实用的任务调度模型? 从计算模型、任务模型、性能模型三个方面对现有任务调度模型进行了分析和总结,并充分考虑到所要建立的模型能兼顾简单性和精确性。因为模型过于精确,则导致求解的复杂性或无法求解;如果模型过于简单,则难以描述实际系统。所以,必须在模型的实用性和准确性之间谋求折衷。? 2)设计了三种基于实用模型的调度算法? 基于提出的更加实用的任务调度模型,设计了求解该模型的三种调度算法。首先,研究模拟退火算法的基本思想并结合提出的任务调度模型,设计相应的调度算法,通过仿真研究该算法的性能。其次,为调度策略寻优,研究遗传算法,提出了一种自适应遗传算法,通过仿真表明该算法具有较好的性能及较高的解质量。最后,为简化调度算法及进一步提高性能,研究如何用蚁群算法求解该模型的任务调度问题,通过仿真表明该算法具有更好的性能和更高的解质量。? 3)实现了一个可高度扩展的分布式并行计算平台? 根据本文提出的任务调度模型,经过比较模拟退火算法、自适应遗传算法或优化的蚁群算法,选定蚁群算法。确定调度算法之后,本文主要从系统功能需求、架构设计、关键技术细节设计和系统评价四个方面讲述系统的实现。经过实验表明:该系统具有较强的通用性和扩展性,为高性能计算提供了一种较好的解决方案。?
【图文】：

理机的执行时间之和。如果目标函数值越大，表示解的质量越好，反之，，则解的质量较100]。 3.1.5 算法描述根据上面的分析，我们设计用模拟退火算法求解任务调度问题，关键问题是如何产生合法的新解，提出了如下操作过程： 1) 在 S 中随机地选取两个任务列表iL 和jL ，并且随机生成一个任意的数 n ( 0≤ n≤h由 n 确定交换点； 2) 把iL 和jL 两个任务列表中交换点以后列表互换，得到新解 S '。 定理 3.1 交换点选择满足下述条件：紧跟交换点前面的任务即前驱iT ， HTni( )≤；跟交换点后面的任务即后继jT ， HTnj( )≥，交换右部后仍然是一个合法的调度。

图 4.2 自适应算法中进化代数 l 与处理机数 m、任务数 n 的关系图 4.3 本章小结 分布式并行计算的任务分配与调度问题属于 NP 完全问题，传统的优化算法很难求得最优解，虽然已有人将遗传算法应用解决此问题，但结果并不能令人满意。本文提出的算法在性能和解的质量上要优于文[102]的传统算法及文[103]的改进算法，主要是采用了自适应的选择、交叉和变异操作。仿真实验结果表明，自适应遗传算法是可行和有效的，无论在精度上还是收敛速度上都较传统和改进的遗传算法有较大程度的提高。因此，自适应遗传算法显示出在任务分配与调度上所具有的优越性。
【学位授予单位】：湖北师范学院
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP338.6

【参考文献】

相关期刊论文 前10条

1 邹林刚;郝矿荣;丁永生;吴怡之;;并行分布式无线生理传感器网络的任务调度模型研究[J];传感技术学报;2009年02期

2 钟求喜,谢涛,陈火旺;基于遗传算法的任务分配与调度[J];计算机研究与发展;2000年10期

3 林剑柠,吴慧中;基于遗传算法的网格资源调度算法[J];计算机研究与发展;2004年12期

4 张勇;张曦煌;;改进型蚁群算法的多处理机任务调度研究[J];计算机工程与应用;2007年35期

5 崔明义;张新祥;苏白云;张瑞;;用蚁群算法实现地理信息系统空间曲线的描述[J];计算机工程与应用;2008年30期

6 陈佐瓒;徐胜超;;面向互联网计算资源共享的自适应调度模型[J];计算机工程与应用;2010年21期

7 毛国君,杨名生,宋广军;局域同构分布式系统的自适应任务分配算法[J];计算机工程与应用;1996年05期

8 钟求喜;谢涛;陈火旺;;任务分配与调度中的遗传算法:知识表示与遗传算子研究[J];计算机科学;2000年06期

9 王庆先;孙世新;尚明生;刘宴兵;;并行计算模型研究[J];计算机科学;2004年09期

10 尚明生;;网格计算中的任务调度模型研究[J];计算机工程;2006年02期

相关博士学位论文 前10条

1 张艳;分布并行算法设计、分析与实现[D];电子科技大学;2001年

2 张帆;过程系统优化的分布式并行计算[D];浙江大学;2002年

3 黄金贵;网络并行计算环境中基于多处理机任务的调度研究[D];中南大学;2003年

4 刘文捷;网格环境下主动式安全系统的通信机制研究[D];哈尔滨工程大学;2006年

5 卢国明;基于P2P的网格资源管理关键技术研究[D];电子科技大学;2006年

6 李建国;实时异构系统的集成动态调度模型与算法研究[D];中南大学;2006年

7 孔晓红;网络计算环境中基于智能算法的任务调度研究[D];江南大学;2007年

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

9 陈宝文;蚁群优化算法在车辆路径问题中的应用研究[D];哈尔滨工业大学;2009年

10 刘波;蚁群算法改进及应用研究[D];燕山大学;2010年

相关硕士学位论文 前10条

1 邱元杰;电网自动化分布并行操作系统中智能化任务调度的设计与实现[D];电子科技大学;2001年

2 张琦;校园网格系统中的资源管理和任务调度[D];华中科技大学;2004年

3 刘钊;演化计算在搜索与优化问题中的应用[D];中国地质大学;2004年

4 敖磊;求解TSP问题的改进蚁群算法[D];西安电子科技大学;2005年

5 侯锋;空间信息栅格中基于市场机制的任务调度模型研究[D];国防科学技术大学;2004年

6 唐觅;支持并行任务的多约束网格调度模型研究[D];吉林大学;2006年

7 韦苗苗;智能优化算法及应用的研究[D];山东大学;2006年

8 刘越屿;结合蚁群算法的GIS技术在多时间窗口车辆路径问题中的应用[D];汕头大学;2007年

9 翁佩纯;基于网格的CSCL资源管理与调度模型研究[D];华南师范大学;2007年

10 牛川川;计算网格中任务调度算法和策略的研究[D];南京理工大学;2007年

本文编号：2666353