《毕业设计论文一种基于并行遗传算法的机群负载分配调度策略的设计与实现》由会员分享，可在线阅读，更多相关《毕业设计论文一种基于并行遗传算法的机群负载分配调度策略的设计与实现（81页珍藏版）》请在金锄头文库上搜索。
1、一种基于并行遗传算法的机群负载分配调度策略的设计与实现 概述6 1.1并行处理技术的发展6 1.2集群技术概述6 1.3支持软件7 1.4任务分配负载均衡的重要意义8并行系统中的任务分配和负载平衡问题10 2.1任务分配问题的概述10 2.1.1 任务分配的一般描述及影响因素10 2.1.2任务分配问题描述11 2.2负载均衡问题的概述12 2.2.1概述12 2.2.2负载平衡问题描述13 2.3现有任务分配及负载均衡算法及其优缺点评述14 2.3.1基于图论的分配策略14 2.3.2 01程序设计策略16 2.3.3 “合一阈值”启发式分配算法17第三章一种新的基于并行遗传算法的策略提出及
2、可行性分析19 3.1遗传算法概述19 3.2遗传算法的结构20 3.3并行化的目的21 3.4并行性分析22 3.5并行算法与并行计算机系统23 3.6并行搜索与最优化25 3.7并行遗传算法形式化地定义29 3.8解决任务的分配与负载均衡问题的优势30算法建模与设计及针对机群应用环境的具体实现32 4.1和任务分配及调度相关的概念32 4.2算法的目标与设计原则34 4.2.1负载均衡算法的目标34 4.2.2负载平衡算法的组成34 4.3 算法的描述及数学模型35 网络应用及其特点39 4.6以PVM为支撑的PC机群环境的概述39 4.6.1 PVM系统概述39 4.7针对机群应用环境的
3、具体设计与实现46 4.7.1相关问题及解决46 4.7.2 虚拟服务器技术及其优缺点46 4.7.3一种新的网络服务并行计算模式的提出48 4.7.4PVM中连接重定向技术及其实现原理52 4.7.4PVM中连接重定向技术及其实现原理55 4.7.5在套接口上的实现59 4.4基本算法的设计62 4.5算法的分布并行设计70 4.5.1简单的主从模型：71 4.5.2网络并行模式:74 4.5.3 两级主从模型：74 4.5.3负载均衡策略设计76实验模拟与性能分析79 5.1性能评价与分析概述79 5.2实验环境与测试83结束语84参考文献85 摘要随着计算机和网络技术的迅速发展，用高速网
4、络连接一组工作站或PC机组成并行计算机系统或利用网络已有资源组成高性能计算环境，来解决许多中、大粒度、十分复杂的计算问题变得越来越普及。 采用这种思路建立起来的计算网络是一种可扩展、灵活的、高性价比的分布式并行处理系统，能否充分利用系统的冗余资源和最大限度发挥该系统的潜力，任务的分配和负载的动态调度是主要的影响因素之一，同时也是一个非常困难的问题。十几年间相继提出了许多解决方法，如：基于图论的分配方式及“阈值”合一法等，这些方法各有其有优缺点，但都不是完美的解决方案。 当今，计算机科学各个领域的发展几乎都显示出向并行计算的过渡趋势。人们开始从并行和分布式处理的角度重新探索计算机的各种理论和应用
5、。并行遗传算法的出现，无疑使我们在解决NPC之类问题方面有了新的转机和希望。 遗传算法是一种借鉴生物界自然选择和遗传机制得高度并行、随机、自适应得概率搜索算法，主要用于处理最优化问题和机器学习等方面。而并行遗传算法可以利用并行计算机的优势，将一个遗传算法的程序分配给几个处理机并行以提高程序执行速度，缩短算法执行所需的墙钟时间。 本文提出了一种基于并行遗传算法的任务分配策略，并且设计了自适应的负载均衡算法，针对PVM系统进行了模拟和实验，同时，还针对PVM在网络应用方面的弱点，采用了底层封装的方法，为PVM系统补充了一个调用库，使得算法能够根据不同的应用类型选择不同的调度方法来实现负载的平衡。并
6、且对算法进行性能分析和应用示例实际测试，达到预期的效果。 最后，对这方面的研究作了总结并为进一步的研究工作提出一些看法。关键字：分布式并行处理，并行遗传算法，机群，集群，并行虚拟机，任务分配，负载平衡 ABSTRACTWith the rapid progress of the network and computer technologies，it is becoming moreand more popular to combine a group of workstations or microcomputers into a distributed parallel Computati
7、on system with high speed network or build a high performance computing enviroment With the existing resource in order to resovle these media granularity complexity application Problems. This computing network is a kind of scalable,flexible and high performande via price ratiodistributed parallel pr
8、ocess system.That task allocation and workload dispatchment becomesthe key factor of whether the redundance resource and potentiality of the system can be made themost of or not.At the same time ,it is also a very ardous issue.Many solutions were proposed inthe past few years.for example,allocation
9、based on graphics theory and so on.But these methodsare not perfect. Recently, it indicates that all fields of computer science is being developed towards parallel computing .People begin to study these theory and application problems with distributed and parallel point of view.It is no doubt that t
10、 he parallel genetic algorithm brings a new opportunity to us on the NPC Problems. The genetic algorithm is a high parallel ,random ,adaptive theory that introduces natural selection and genetical mechanism from biological kingdom .It is used mainly in optimization and machine study and so on.And it
11、 can reach the best efficiency by running on the parallel system. In this paper, we propose a task placement based on the parallel genetic algorithm.And we designe an simple adaptive balance algorithm for PVM system.And we also enhancea library for network applications .It is proved feasible through
12、 our experiment .In addition,we summary what we have done and propose some advice for the more research .Keyword: distributed parallel computing,genetic algorithm,PVM,task,Workload,adaptive 概述 1.1并行处理技术的发展最近20多年，并行处理技术一直是计算机科学技术领域的重大研究课题之一，它对提高计算机的性能有着重大作用和广泛的应用前景。并行计算机并不是凭空产生的，而是反映了单处理机向高指标发展的自然趋势。
13、现代使用的单处理机结构是John Von Neumann式的，由单个程序计数器控制其执行顺序，在任一时刻，只有一条指令在执行。机器的串行性对于高速处理来说是一个严重障碍。单处理机运算速度的提高是有限的。现在实际中存在的许多大规模和超大规模问题用传统的单处理机是不能解决的。现在进行大规模信息处理采取的主要策略是克服Von Neumann模式的缺点和把工作分散到许多单处理机中，尽可能的高速度、高效率的进行并行处理，即发展并行处理技术。并行处理技术中的几个主要难题：（1） 任务的分配非常困难在处理机或节点机数目很多的情况下，要把任何一个问题分解成足够多的并行过程是非常困难的，并且着也不是所有的问题都
14、能做到这一点。在分布式计算机系统中，由于分布式算法具有分散的通信结构和相对独立的模块，在衡量一个算法好坏时，除了考虑时间复杂性、空间复杂性还要计算模块间的通信量IMC，因而一个分布式算法比其他算法更加复杂。在分布式计算中如何充分利用计算的局部性原理和寻找任务最优分配算法以减少过程之间的通信量和活获得高性能，是一个至今仍未很好解决的问题。（2） 很难摆脱串行处理方式的约束现有的软件产品绝大多数是按串行算法研制的。为了继承发扬人类的这笔财富，在原有的应用领域内研究并行处理技术时不得不考虑如何利用这笔财富，因此现有的并行算法绝大部分是从串行算法改造过来的。（3） 处理机之间的通信开销有可能使并行处理
15、技术得不偿失（4） 并行处理技术的主要难题是软件 对于含有大量处理机的并行处理结构，软件对系统的影响更大，其性能差距可几个数量级，软件的关键在于如何高效地进行存储管理和机间通信。软件中最难的是并行编译程序。 1.2集群技术概述 随着电子信息时代的来临，人们把越来越多的工作交给计算机完成。因特网为人类展示出更为宽广的分布式计算模式的天地，随着个人计算机性能的增强、存储设备容量的增加，似乎数据更多的分布在各个微机中。但是对于大型企业和网络提供商来说，他们无限增长的数据必须集中存储和处理，因此企业级的运算对计算机的处理能力提出了更高的要求，计算机系统供应商必须不断完善，改进现有的计算技术，使它们越来越强大。 集群技术是使用特定的连接方式，将相对于超级计算机便宜许多的计算机设备结合起来，提供与超级计算机性能
