毕业设计论文一种基于并行遗传算法的机群负载分配调度策略的设计与实现

《毕业设计论文一种基于并行遗传算法的机群负载分配调度策略的设计与实现》由会员分享，可在线阅读，更多相关《毕业设计论文一种基于并行遗传算法的机群负载分配调度策略的设计与实现（83页珍藏版）》请在装配图网上搜索。

1、 一种基于并行遗传算法的机群负载分配调度策略的设计与实现 第 83 页 共 83页 概述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系统概述3

3、9 4.7针对机群应用环境的具体设计与实现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 para

7、llel Computation 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 ratiodistribut

8、ed parallel process 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 examp

9、le,allocation 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 n

10、o doubt that t 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 an

11、d so on.And it 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 fe

12、asible through 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集群技术概述 随着电子信息时代的来临，人们把越来越多的工作交给计算机完成。因特网为人类展示出更为宽广的分布式计算模式的天地，随着个人计算机性能的增强、存储设备容量的增加，似乎数据更多的分布在各个微机中。但是对于大型企业和网络提供商来说，他们无限增长的数据必须集中存储和处理，因此企业级的运算对计算机的处理能力提出了更高的要求，计算机系统供应商必须不断完善，改

16、进现有的计算技术，使它们越来越强大。 集群技术是使用特定的连接方式，将相对于超级计算机便宜许多的计算机设备结合起来，提供与超级计算机性能相当的并行处理技术。早在七十年代就有人提出可以使用这种集群技术完成并行处理，但是由于受到当时网络交换技术的限制，集群系统在性能上与其他并行处理系统相距甚远，直到ATM技术、千兆位以太网技术逐渐成熟的今天，它才具备了与超级计算机相匹敌的能力。 目前最为流行的方式是用高速或超高速网络传输设备将几台服务器相连，实现并行处理，屏蔽单点失效。目前对集群技术需求最迫切、发展最快的领域主要有：www应用、数据库应用等商业计算领域。集群系统可以通过使用纯硬件的方式或使用软硬件

17、结合的方式来搭建。 在日常实践中，天气预报、海洋模型和环流、遗传工程、先进工业制造技术、能源工业、地震分析、化学工业、材料科学、生物科学、环境研究、结构分析、仿真、电子交易和军事等许多领域中都存在着大量的复杂计算问题，被称之为“巨大挑战问题”，解决这些问题无疑对人类有着重要的意义，这也就是高性能计算所要努力的目标。美国从1992年开始实施高性能计算方面的计划HPCC，并投入巨资研究解决“巨大挑战问题”的环境、方法和技术。 实现高性能计算的核心是并行技术的发展，尽管各类并行结构的超级计算机在高性能计算中发挥了重要作用，但随着网络技术的发展和普及，以网络为基础的分布式并行计算环境以其较高的性价比和

18、大范围、大数量异构机群并行成为新的高性能计算环境，其思想来源于并行结构随网络发展的自然延伸： 连接多个日益廉价的独立计算机，如工作站和PC机，形成类似MPP的性能； 利用网上日益庞大的空闲处理机资源，形成可扩展的高性能计算能力； 连接广域范围内的各种资源，形成巨大的协同计算环境，并使这些昂贵的资源能为尽可能多的用户共享。 专用机群一般由一组同构的处理机组成（有时也有异构情况），通常安装在一个机房内，或者将主板等安装在一个机柜的各机箱中（商业机群常用这种方式），或简单地把PC机堆砌在机架上（Piles of PC）。在这种机群中，每个处理机都是专用的、无属主的，由系统管理员统一管理，用户可通过前

19、端机进行访问，用户无需知道机群的详情，就像使用MPP机一样，易于配置和管理，不受外界干扰，通信可靠且延迟小，适合于面向加速比的并行任务和面向吞吐量批处理作业。专用机群具有相对结构和管理简单、易于扩展等特点，用途极广。1994年夏，美国的研究人员建成了第一个Beowulf机群，它由16个DX4处理机组成。1997年，又推出了16个基于P的机群，只需花费5万美元却具有每秒10亿次的浮点运算能力，而购买具有相同能力并行机的投资数却是它的10倍。 机群技术已经成了开发成本有效且可扩展的并行计算机的一大趋势。 1.3支持软件随着开放的分布式计算环境的普及，系统软件所扮演的角色日趋重要。为协调各节点机的工

20、作，系统应具备负载管理功能。1 工作负载管理在支持对完成企业商业目标十分重要的应用程序的同时，工作负载管理必须对所有类型的运行任务进行有效管理，同时最大限度地利用硬件与软件资源。从功能角度来说，工作负载管理软件调度，分析并监测企业应用工作负载的进程。工作负载管理在网络水平上来说具备许多传统操作系统的功能，它动态地通过调度用户作业以充分利用分布式异构计算资源。 虽然与数据管理和系统管理联系甚密，工作负载管理在几个主要方面同他们有显著的不同。数据管理为所有应用程序提供分布式数据平台，而工作负载管理提供“分布式计算平台”；系统管理侧重于硬，软件资源并由操作人员使用，而工作管理支持企业系统的计算工作负

21、载，并被可信任的最终用户直接或间接地使用。 工作负载管理弥补了系统管理的不足之处。系统管理确保了分布式计算资源发挥正确的功能，而工作负载管理确保了分布式计算资源有效地满足重要商业处理进程的要求。 以前，工作负载管理在系统软件市场中并不是主要的组成部分，由于转向异构式企业计算环境的强烈趋势，工作负载管理日趋重要。正是因为它能够在日益复杂的分布式环境中充分利用异构的硬/软件资源。在分布式计算环境中充分发挥虚拟主机的优势，将数据管理，系统管理和工作负载管理集成起来是十分重要的。 2 工作负载管理的功能与需求 : 从功能上角度来说，涉及到分布式应用工作负载的调度，分析，监测与操作。下面讨论这三个功能领

22、域。 l 工作负载调度 工作负载管理最重要，且是最基本的一个功能就是利用最合适的可用计算资源进行动态作业调度。根据作业要求，作业调度可以基于以下一或多个方面：l 资源可用性：一项作业可能要求一种特殊的系统平台，一定的内存或特殊的软件许可证，无须用户指定主机运行该作业，工作负载调度动态地用最佳可用计算资源满足作业要求。如果所需资源不可用，它可将作业延迟，等待下一次批处理来完成。 l 工作负载分析：尽管作业调度优化了工作执行程度并确保了可靠的作业处理，作业分析还支持作业数据综合分析以进入整个系统处理。 作业分析使用数据获得(1) 计算资源的下载与可用性 (2) 作业处理与资源利用 (3) 系统配置

23、； 1.4任务分配负载均衡的重要意义 为充分利用并行与分布式计算环境中，多处理机的并行处理能力，根据不同的数据约束关系和计算要求。一个任务往往被分解成多个子任务，任务分配与调度就是要将分解好的若干个子任务指派到处理机群中的各个处理机，并根据给定的子任务的数据约束关系合理安排好每个处理机的执行顺序。 遗传算法是于70年代的一种全局优化算法。它模拟和借鉴自然界生物进化的机理，具有简单、通用、稳健的特点。 并行遗传算法利用并行计算机的优势，将一个遗传算法的程序分配给几个处理机并行以提高程序执行速度。 计算机系统的性能，从静态来看，各个节点机的负载基本平衡是高性能的表现，从动态来看，任务的平均响应时间

24、是性能的尺度。能否做到合理的快速任务分配及负载的动态平衡是能否充分发挥系统资源优势，提高资源利用率的关键所在。也是防止软件并行性和硬件并行性之间失配的前提。 分布式并行系统中的任务分配和负载平衡问题 2.1任务分配问题的概述一个分布式并行系统由多个处理机或节点机组成，当有任务到达或产生时，要决定运行在哪个处理机或节点机上，这就是任务的分配和调度。静态分配策略是在系统运行的初始时刻，将用户提交的任务集一次性分配给系统中各处理机或节点机，以后直到这些任务执行完毕，各处理机上的任务一般不在变更。动态分配策略（负载平衡或负载共享）则是在运行过程中，将任务分配给各处理机，并对其上的任务数进行动态调整，尽

25、可能使系统中处理机上的负载达到基本平衡，减少系统平均响应时间。我们知道，一般情形下，在处理机或节点机的数目大于3的多机系统或分布式系统中的任务分配问题是一个NP完全问题，人们通常不会去寻求解决问题的最优解，但对于具体的分布式系统，在适当的假设条件下寻找不一定最优但实际可行且效果满意的方法，仍是目前十分热门的研究课题。然而，在实际的应用系统中，对任务动态调度的需求要多于对任务的静态分配，所以，动态任务分配算法（负载平衡或负载共享）、自适应分配算法及智能化任务分配算法将是进一步研究的方向。 2.1.1 任务分配的一般描述及影响因素1 任务分配的环境一般的分布式系统的结构示意图如下：MnnnM1M2

26、2SP1PNP2图2.1 分布式系统的结构图 其中，（M1，M2，Mi）是一组待处理的模块或子任务，（P1,P2,Pn）是系统的N个处理机或节点机，他们经过互连网络相互通信，分解机制S把m个模块或子任务合理的分配给n个处理机或节点机中某一些。通常mn, 位于不同处理机（节点机）上的模块彼此交换数据是通过他们所在处理机（节点机）彼此通信来实现的。任何一对模块的IMC（intermodule communication）的总量将随着模块对的不同而变化。所以，把这些模块分配给处理机（节点机）的方式，就可能影响整个系统的处理开销。例如，若模块Mi和Mj的IMC通信开销很大，通信也较频繁，而且他们又分配

27、在不同的处理机上，那么，相应的IPC（interprocess communication)开销会增大，如果把Mi和Mj分配到同一处理机上就可能减少系统的总处理开销，此外，若两个模块的 IMC 较小，且无优先制约关系把他们分配不同的处理机。显然，可能加速整个处理过程。2 影响系统性能的因素 在任务分配中，均衡负载分配策略是把模块比较均匀的分给系统的所有处理机或节点机使得这些处理机或节点机差不多是均匀负载的，这种策略可最大限度的提高系统的吞吐量。如果，只注重减少IPC而不考虑系统的均衡负载，那么可将待处理的模块全部分给同一节点机，任务的处理时间却成倍增加了。显然，均衡负载和减少IPC是相互矛盾的

28、两个因素，左右着任务分配的策略，影响着系统的性能，负载均衡可以提高系统的吞吐量，因为它试图将模块尽可能的均等的分配给各处理机，但由于IPC的开销又迫使分配策略不得不尽可能的把较多的模块分配给尽可能少的处理机或节点机。任务分配策略就是要设法折中这两个因素，将模块分配给处理机或节点机，使整个系统的性能提至最高。 2.1.2任务分配问题描述处理机间的通信开销是由于位于不同处理机（节点机）上的模块相互传递数据所引起，所以，IPC 是模块间的通信开销和模块分配的函数，显然如果两个模块同驻在一个处理机（节点机）上，则他们不会引起IPC。若干模块构成一个任务，一个任务是单一的处理实体，任务的分解和分配是用于

29、减少IPC的两个必要步骤。传统的任务分配策略其着眼点都在于设法减少系统中各处理机间的通信开销和运行模块所需的开销，以此来提高整个系统的性能。任务分配的目的是把一个提交任务划分成若干独立的。具有最小IMC的模块，并且我们假定任务分解已由软件设计者在设计阶段完成，提交给系统的任务已经分解成若干模块。任务分配是在并行处理系统中针对某个目标，按照一定的策略将规模为N的任务划分和映射P的处理机（节点机）上，则在并行处理系统中一个任务的执行时间T： T=F（tp,tc,te）其中：tp-子任务的最大执行时间； tc-完成任务所需的通信时间； te-其他开销 一个计算问题划分出的任务越多，tp 就越小，但t

30、c和te 会增大，而且增大的不仅可能抵消tp 减小的作用，甚至可能使并行处理的效益完全丧失。 任务分配问题也属于优化问题，即给定N个任务及其相互之间的关系和P个处理机，在各种可能的分配方案中选择最合理的一种，以达到某一最优目标。由于应用要求不同，认为分配的问题的最优目标条件有多种，如：最大吞吐量，最短完成时间，最大资源利用率，最小总费用（计算时间和通信时间总和）和最小通信开销等。 2.2负载均衡问题的概述 2.2.1概述负载平衡也称负载共享，是指对系统中的负载情况进行动态调整，以尽量消除或减少系统中各场点负载不均匀的现象。具体实现方法是将重载场点上的任务转移到其他轻载场点上，尽可能实现系统中各

31、场点的负载均衡，而且提高系统的吞吐量。负载共享有利于统筹管理分布式系统中的各种资源，便于利用共享信息及其服务机制扩大局部分布式系统的处理能力。动态负载共享策略是指把系统中各场点上已有的负载作为参考消息，在运行过程中，根据系统中各场点的负载状况，随时调整负载的分配，使各场点尽可能保持负载的均衡。负载：负载共享算法中的关键问题是如何确定负载？根据任务负载可以判断某一任务在特定场点的响应时间。确定在该场点上的执行性能。曾经被研究使用过的负载包括CPU队列长度、某段时间内的平均CPU队列长度、CPU利用率等。Kunz发现负载的选取对系统性能有着重要影响，而最有效的负载计算方式是CPU队列长度。动机：用

32、户将任务提交给系统处理，由于任务到达的随即性导致了某些处理机处于重载而某些处理机处于空闲或轻载状态。负载共享能够通过重载处理机上的任务迁移到轻灾处理机上执行来提高性能。在多处理机或节点机系统中，经常会出现某些处理机负载过重而另外一些处理机负载很轻甚至空闲的情况。为了提高处理机的利用率和系统并行计算的效率，人们试图把负载过重处理机上的一部分负载迁移到空闲或轻载处理机上，而导致了负载平衡问题的研究。负载平衡策略从总的来说，可以分为静态负载平衡和动态负载平衡。静态负载平衡在计算的初始阶段就作好负载的分配工作，由于它只作一次负载分配，不适合那些动态负载的情况，因此适用范围较小，而动态负载平衡根据计算过

33、程中数据项的变化情况动态地分配负载，根据起迁移负载的目的处理机的选择是否随机，可以分为确定型和随机型。确定型方法根据一些预先定义的规则进行，向哪些处理机迁移超额负载、迁移多少等都由这些规则的某些参数决定。典型的确定型方法有扩散方法、梯度方法等。而随机型方法则恰恰相反，负载的重分布是以随机方式进行的，由于没有一些预先定义的规则，因此随即型方法较确定型方法更简单，但更难于模型化和形式化分析。 2.2.2负载平衡问题描述假设系统由N台处理机组成，顺序标记为P0 ，P1， PN-1 ，处理机之间通过网络加以连接。为了评测系统的平衡性，用每台处理机所拥有的数据项来表示负载，记为wI 。整个系统的负载W=

34、W(i),0iN-1，系统的平均负载为W* =W/N。为了便于算法描述，引用了数据发送指令和数据接收指令。发送指令send(deskk,sizek)将大小为size的处理机上的负载发送到由desk标记的处理机上接收大小size的数据项。l 负载平衡算法分类负载平衡算法可分为动态算法和自适应算法二大类。1 动态算法根据系统状态，对可以接受任务的节点进行分析，如果处理机不空闲，可以将任务迁移到空闲节点，甚至可以将正在执行的任务迁移到其他空闲节点。但是，信息的收集、分析及作出决定要造成额外开销，不可小视。2 自适应算法通过动态改变参数甚至策略来调整自身的行为，以适应正在改变的系统状态，例如，某种负载

35、平衡算法在A情况小的性能优于其他算法，而另一种算法在B情况下更优，自适应算法能够根据系统状态的变化选择合适的算法。在无法通过任务迁移提高系统性能的情况下，自适应算法是很好的选择。另外，上述算法又可进一步分为抢占式和非抢占式两类。（1） 抢占式任务迁移是指可以转移一个已部分执行的任务。这个操作通常是非常昂贵的，因为收集任务的状态信息非常困难。任务状态包括虚拟内存的映像、进程控制块、I/O缓冲区、文件指针等。因此实现抢占式任务迁移开销很大。（2） 非抢占式任务迁移只包括未开始执行的任务，所以不涉及任务状态信息的迁移。 在这两种方式中，执行任务的一些环境信息将传送给远程节点，这些环境信息包括用户工作

36、目录和任务特权等。其中非强占式任务又称Task Placement。动态负载平衡算法可以根据集中的程度加以区分，分为集中、分散、组合三种。但集中式算法隐含着不稳定性，因为当中央控制节点出现故障是会导致系统瘫痪，一种解决方案是保持一个冗余节点，当中央控制节点出现故障是，冗余节点自动激活代行中央节点之责。集中式算法的另外一个缺点是易造成中央节点处的瓶颈。2.3现有主要算法及其优缺点评述 2.3.1基于图论的分配策略 基于图论的分配策略的基本思想是把待分配的一组模块作为图中的节点集，连接两个节点的有向连线上的权表示每对模块之间的IMC开销。IMC开销为0意指相应的两模块之间无通信发生，因此它们在图中

37、无连线；IMC开销为意指相应的两模块间通信量很大，必须分配给一个处理机。可见，图中节点间连线上的权表示分配在不同处理机上每对模块之间的通信开销。我们假定任何一对同驻模块的IPC开销为0。若把系统的总的开销定义为系统的处理开销和IPC开销之和，那么，这种分配策略的目的就是实现最小的总开销（C.C.Shen and W. H. Tsai 1985）。处理开销和IPC开销都是模块到处理机分配的函数，为了表示模块到处理机的分配，我们定义下面的分配矩阵X： x=而处理开销则由下面的Q矩阵给出： Q=q,I=1,2,m;k=1,1,.,n其中qi,k表示mi 在处理机Pk上的处理开销，它是该模块处理要求的

38、度量。qi,k=隐含模块mi不可能在处理机Pk上执行。令Ci,j表示模块mi 和mj之间的IMC开销。于是处理给定任务的总开销T表示为X的函数: T(X)=其中，第一项表示每个模块在它所分配的处理机上的处理开销，第二项则表示非同驻模块之间的IPC开销。最小开销分配则是在这种图上执行最小分割算法（F. Harary 1969）来获得。例如，考虑由两个处理机P1，P2构成的分布式系统，提交的任务由6个模块A，B，C，D，E，F组成。相关的IMC开销和处理开销分别给出在图中的（a）和(b)中。根据这些信息，利用上述方法可以构造一个模块通信图（见图2.2）。为了表示处理开销，我们再给图2.2添加两个节

39、点以表示两个可用的处理机P1和P2。在 P1上运行的某个模块的开销（即处理开销）标在该模块节点到节点P2 的连线上，在处理机P2上运行的某个模块的开销标在该模块节点P1的连线上，于是我们得到图2.2中双线所示，这就是在两个处理机上对给定模块的最小开销分配，容易看出，这种分配策略并没有实现处理机的负载均衡。ABCFED图2.2 模块通信图 模块A B C D E FABCD EF6 4 0 0 12 8 12 3 00 11 05 0 0（A）模块通信开销表模块P1开销 P2开销A BCDEF5 102 4 46 35 2 4（B）处理开销表 算法的优点：这种分配策略的最大优点是它的简明性。 主

40、要缺点：第一， 所用的最小分割算法是一种基本的最小分割算法，它只能用于实现两个或三个处理机间的最小开销分配。若将它扩充成处理任意个数的处理机，则需n维（n个处理机分配）的最小分割算法，该算法是极其复杂的。这就限制了这种任务分配策略的应用范围；第二， 这种方面既未提供表示有关存储空间或处理时间等方面的限制手段，也没有提供负载均衡方面的机制；第三， 它没有能力去观察排队延迟效果。当一个以上的模块分配给同一处理机是，就不可避免地出现延迟。因此，基于图论的任务分配策略不是任务分配问题的最好解决办法。 2.3.2 01程序设计策略 这种策略的主要思想是把任务分配问题概括成一种“优化问题”，然后利用数学程

41、序设计去解决它（J. A. Stankovic 1985）。 具体做法是：处理开销Q矩阵来表示，为了表示IPC开销，引进一个卷宗矩阵V和一个距离矩阵D，并用V与D之积替代的单个IMC开销矩阵C，利用卷宗矩阵： V=v,i=1,2,m;j=1,2,m来定义IMC，其中v表示从模块mi向模块mj发送的数据卷宗，若v=0。则表示模块mi 和mj 之间无数据交换。 以图2.1所示的分布式系统为例，在这组处理机上定义的距离矩阵D为： D=d k=1,2,n;h=1,2,n 其中，n为处理机的个数；距离d k，h 是处理机PK 和Ph 之间通信开销的一种度量。若P 和Ph 之间毫无关系，则令d k,，h

42、=。我们可用距离度量来表示网络中处理机的互连状况。如果允许d k ，h之值为非0，则可用它表示同驻模块之间的通信开销，假定每对处理机间的距离是知道的而且是固定的。这种分配策略的目标函数T现在可定义为： T（X）= 其中，第一项表示每个模块在它所分配的处理机上的处理开销；第二项则是对用于表示IPC开销的“卷宗-距离”元素之积求和；常量w用于调节处理开销和IPC开销，以补偿度量单位上的差异。负载均衡是通过施加若干限制来实现的。我们主要考虑储存容量、处理机速度以及处理时间的实时要求等方面的限制。由于处理机速度已反映在处理开销矩阵Q中，因此，我们只讨论其他两方面限制。A 存储容量方面的限制可表示为 其

43、中si表示模块mi所需要的存储容量，Rk 代表处理机Pk 的存储能力。 该式说明：分配给某个处理机的全部模块所需要的实际存储量的总和不能超过该处理机的存储能力。B 时实限制则由下式表示： 其中， ui表示模块mi所需要占用处理机的时间，RT代表位于处理机Pk上全部模块所需要的时间限制（对于给定任务而言）。 该式表明：处理分配给某一处理机上全部模块所需要的时间的总量不得超过该处理机所规定的实时限制。在条件A和B的限制下，通过对T（X）极小化，我们就可以对任何给定的系统执行任务分配。这可以作为一个非线性的01整数程序设计问题来求解。这种非线性的01方程式可以通过添加进一步的条件而线性化，从而简化整

44、个求解过程。当然，还可以采用其他求解方法，例如：采用近似求解法等。这种分配策略对任务分配环境提供了一种较好的表示方法，它也比较灵活，因为它所能适应地表示出某些限制条件。在基于图论的分配策略中实现这一点是不可能的。但它也存在以下缺点：第一， 它难以表示在实时条件限制下当前系统状态的作用；第二， 它也难以表示模块间数据流中优先关系的影响。因为这两种因素用一种复杂的方式将排队延迟引入了系统，所以对此需要进一步的研究。基于这方面的考虑，实时限制应变形为RT，k=1,2,3,n;I,j=1,2,.,m其中 p i，,j 表示模块mi 和mj 之间的优先关系，函数 fi则表示处理时间，包括在处理机 Pk上

45、处理模块mi 是的排队延迟。 2.3.3 “合一阈值”启发式分配算法假定所依赖的分布式系统由多个同构的处理机经互连网络连接而成，其中的每个处理机都具有同等的处理能力。位于不同处理机的模块相互交换信息是通过它们所在的处理机彼此通信实现的。为简化讨论，我们忽略模块间的优化关系。所谓“合一”是根据一定条件，将两个模块分配到同一处理机。这里的“ 阈值”是指处理机所能接收并处理的最大模块数。“合一 阈值”算法是一种分两阶段进行任务分配的算法。 第一阶段为“合一”阶段。即对用户提交的一组模块进行合一处理，具体过程为：先查找其中这样一对模块，即把它们合一后将消除最大的IMC开销，然后检查经过这种合一处理后，

46、相应的处理机是否满足实时和（或）存储方面的要求。若满足，则认为此次合一成功。否则，选择下一对具有最大IMC开销的模块，重复前面的过程，直至完成一次成功的何以。再将合一后的模块对全部分配完毕或剩下的模块不能按此方式分配为止。最后将剩下的模块分配到同一处理机上。第二阶段为“调整”阶段。它在第一阶段工作的基础上，根据各处理机上规定的阈值，对各处理机上的实际负载作必要的调整，即查看各处理机上的模块是否超越预定的阈值。若均未超过，则本阶段工作结束，该算法终止。否则，将那些超过阈值的处理机上的模块迁移到尚未超过阈值的处理机上。评价：下面仅从算法的时空复杂性及算法的输出与最优解的差距等方面来简单地分析该算法

47、。为此，假定有n个模块等待分配给m个同构的处理机。我们可用一个矩阵表示IMC开销，由对称行知，存储这方面的数据只需n（n-1）/2个单元。当完成了一次成功的合一后，修改相关模块的IMC开销后的信息用另一个矩阵存放，这也只需n (n - 1) /2个单元。不难看出，合一过程采用的是一种局部“贪心”策略，即每次查找一对这样的模块，它们经合一后不仅消除最大的IMC开销，而且相应的处理机应满足实时和（或）存储要求。若令T（n）为合一过程最坏情况下的时间复杂性，则不能得到下面的递推式：T（n）=查找具有最大IMC开销模块对的时间+修改其他模块对的IMC开销时间+T（n-1）显然T（n）O(n3)。若经合

48、一处理后剩下的模块数大于m，则认为合一失败（此时，不必进入“调整”阶段）。为此，可假定经合一处理后的模块数小于等于m。“调整”阶段是“合一”阶段的继续。在调整过程中，可用数组TV1.m存放各处理机的阈值，用load1.m存放各处理机上的实际负载。在合一过程中，很难知道分离出哪个模块（或模块族）可使得处理开销最小，故此采用“随机策略”。在此，不妨把调整过程进一步描述为：（1）计算各处理机的实际负载与其阈值之差Di，i=1，2，m；（2）按 Di的不增次序排序各处理机，并用j (1，2，m)指称经排序后位于序号j处的处理机；（3）对于j=1，2，m-1执行下面的操作：“向上迁移策略”若处理机j的D

49、i 大于0，则用随机方法从处理机j上选定一模块（或模块族）并把它迁移到处理机j+1上。重复此过程，直至处理机j的Dj 不大于0。必要是，可对模块族进行分裂。若处理机j的Dj 不大于0，则不做任何迁移工作。（4）处理机m的Dm不大于0,则报告“失败”，否则调整成功。以上分析可以看出，由于“合一”过程采用的是局部“贪心”策略，因此，不一定能实现最优分配。而“调整”过程采用随机方法选定迁移的模块，从而带有一定的盲目性。但是成功的合一处理可以减少系统中处理机见的通信开销，而成功的“调整”过程有尽可能的合一处理机的负载到达基本均衡，有利于提高系统的吞吐量，而且该算法具有较低的时空复杂性，实现过程也比较机

50、械、简单，因此，仍不失为一种可行的方法。第三章一种新的基于并行遗传算法的策略提出及可行性分析 3.1遗传算法概述遗传算法最早是由美国Michigan大学的Holland提出的，这种算法模拟达尔文的进化论创建的，它模拟生物遗传进化的过程，引入选择、复制、交叉重组和变异等方法，并将进化论中“物竞天择，适者生存”的概念，引入到算法中，是一种借鉴生物界自然选择和自然遗传机制的高度并行的、随机的、自适应搜索算法，是一种概率搜索算法，它利用某种编码技术作用于称为染色体的二进制串，其基本思想是模拟由这些串组成的群体的进化过程，遗传算法通过有组织地然而是随机的信息交换来重新结合那些适应性好的串，在每一代中，利

51、用上一代串的结构中适应性好的位和段来生成一个新的串的群体，作为额外添加，偶尔也要在串的结构中尝试用新的位和段来代替原来的部分。遗传算法是一种随机算法，但它不是简单的随机游走，它可以有效利用已有的信息来搜索那些有希望解质量的串。类似于自然进化，遗传算法是通过作用于染色体上的基因寻找好的染色体来寻求解问题，与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所 产生的每个染色体进行评价，并基于适应值来选择染色体，使适应值好的染色体比适应值差的染色体有更多的繁殖机会。 在生物界，一个生物群体中个体之间的差别是由包含在生物体内的染色体之间的差异来体现的，这种差别即反映在生物体自身的结构上

52、也反映在它们所处环境的行为上；反过来，结构与行为的不同又表现在它们生存与繁殖率的不同。在环境中，性能好的生物体（更适应的个体）具有更高的生存与繁殖率；反之，生存与繁殖率则较低。经历若干代之后,就整体而言，生物群体逐渐包含了更多的个体，其染色体的结构在环境中表现出更加优良的性能。这样，随着时间的推移，群体中个体的结构由于自然选择而发生变化。这种由于适应性导致的结构上的差异就是进化的结果。这就是达尔文在物种起源一书中描述的适者生存和自然选择的概念。关于进化理论的一般特性已广为人们所接受：（1） 进化过程发生在染色体上，而不是发生在它们所编码的生物体上（2） 自然选择把染色体以及由他们所译成的结构的

53、表现联系在一起，那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会。（3） 繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于他们的 父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生很大的差异。（4） 生物的进化没有记忆，有关产生个体的信息包含在个体所携带的染色体的集合以及染色体的编码的结构之中，这些个体会很好的适应它们的环境。 遗传算法是一种高度并行的数学算法，它使用以遗传操作为模式的数学操作将一组数学对象，通常是以染色体串为模式的定长字符串群体（每个串都具有一个适应度（Fitness），转换为新一代群体。通常，任何抽象的问题都可以认为是求解一个

54、问题，而问题求解又可看成对解空间的搜索。由于我们总是希望寻求“最佳”的解，因此可把求解过程当作一个优化过程。对于小空间，经典的穷举搜索方法足以解决问题；然而对较大空间，就需要采用自适应的、智能的搜索技术。遗传算法正是这种模拟自然界生物进化过程的自适应寻优技术，它的主要应用领域是复杂的非线性优化问题。尽管遗传算法可归类为概率算法，但它不同于随机算法，它把定向搜索与随机搜索有机地结合起来；正因如此，遗传算法也强于已有的定向搜索算法。遗传算法的另一个重要的特性是使用一个潜在解的群体来搜索解空间。其他方法，一般总是使用单点来搜索空间，这些算法非常依赖于起始点的选择，经常给出局部优化的点，与此相对照，遗

55、传算法保持一个潜在解的群体实现了多个方向上的搜索，同时，在搜索过程中鼓励不同方向上信息的结合和交流。群体经历了一个模拟进化过程：在每一代，较好的解“繁殖”，较差的解“消亡”。在这个过程中起关键作用的目标函数（适应函数）用于区别解的优劣。 3.2遗传算法的结构一般说来，解决一个具体问题的遗传算法由下述五个部分组成：(1) 制定问题的潜在解的遗传表示；(2) 创建潜在解的初始群体的方法；(3) 评估解的适应度的计值函数（适应函数）；(4) 改变子孙结构的遗传操作；(5) 算法适用的各种参数、变量及终止条件等。经典遗传算法的表示模式是将问题搜索空间中的每一个点表示为定长字符串，即字母表K上长度为L的

56、字符串，确定染色体串与空间点之间的映射关系有时是显而易见的，有时则非常困难，需要对问题有深刻的认识和正确的判断。适应度计算为群体（种群）中的每个定长字符串赋予一个适应度的值，赋值方式通常是问题所固有的；改变子孙结构的遗传操作主要有复制（Reproduction，也称繁殖）、交叉（Crossover，也称交配）和变异（Mutation），而控制遗传算法的参数包括群体的大小（种群规模），进化过程的最大代数以及控制各种遗传操作的概率等。经典遗传算法的执行步骤如下：(1) 开始(Start)随机创建由N个染色体组成的初始种群(2) 适应度(Fitness)为种群中的每一个染色体x计算适应度f(x)，其

57、中f(x)为适应函数(3) 产生新的种群(New population)循环进行下述各步，直到新的种群创建结束 选择（selection）根据适应度（适应度越好，被选中的概率就越大）选择两个父代染色体 交叉（Crossover）根据交叉率，对父代染色体进行交配，从而产生新的子代个体。如果不进行交配，那么子代即为父代的一个拷贝。 变异（Mutation）根据变异率，对新的子代个体进行变异操作 接收（Accepting）新的子代成为新的种群中的个体(4) 替换(Replace)新产生的子代种群成为下一次计算的父代(5) 测试(Test)如果满足终止条件，则停止，并返回当前种群中的最好个体(6) 循

58、环(Loop)转第(2)步上述遗传算法的组成与执行过程，表明了这是一种与问题领域无关的方法，它可以解决大量的不同方面的问题。我们应用遗传算法要考虑如下的问题。首先要考虑的问题是如何创建染色体，选择什么样的编码方式。它与交叉和变异两种遗传算法的基本操作密切相关。其次，是在进行交叉前如何选择父代染色体。这有许多方法，但主要的思想是选择较优的染色体（寄希望于好的父代产生好的子代）。但新的种群如果只由新的子代个体组成可能会导致在新的种群中失去最优的染色体。因此，经常用到精英理论（elitism）。这意味着，有少数（至少一个）当前的最优个体不加改变地被复制到下一代，这样使得最优个体能够存活到算法的运行结

59、束。 3.3并行化的目的 遗传算法的模仿自然界生物遗传和进化过程中的“物竞天择、适者生存”的原理而开发出的一种多参数、多个体同时优化方法。经过三十多年的开发研究和应用实践，遗传算法初步显示出了其解决复杂系统优化问题的良好能力，特别是对一些NP组合优化问题的求解，更表现出了优异的性能。 如今，遗传算法已经在旅行商问题的求解、生产调度、图形划分、函数优化、机器学习等众多领域中得到了成功的应用，并显示出良好的性能。标准的遗传算法以个体的集合为运算对象，对个体所进行的各种遗传操作都有一定的相互独立性，所以它具有一种天然的并行结构。 一方面，虽然遗传算法对一个个体编码串的搜索意味着它同时搜索了多个个体模

60、式，即对个体结构模式的处理具有并行的含义，但这个并行性是一个隐含的并行性，其运行过程及实现方法在本质上仍是串行的。这种串行的遗传算法在结局一些实际问题是，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度上的要求，因而遗传算法的并行计算问题就受到了较大的重现。 另一方面，由于遗传算法的天然并行性，人们认识到了对起进行并行处理的可能性，从而基于各种并行计算机或局域网，开发出了多种并行遗传算法（Parallel Genetic Algorithm,简称PGA）。开发并行遗传算法的主要目的是为了提高遗传算法的运行速度，开发和应用实践表明，各种并行遗传算法都能不同程度地达到这个要求。 3.4并行性分析Goldberg归纳出了基本遗传算法模型，它是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体（候选解），这个迭代过程直到满足某些结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化的要求，如图所示，可以从下面四种并行性方面着手对其进行改进和发展。 初始群体循环： 个体适应度评价循环： 个体选择运算