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

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

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

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 工作负载管理的功能与需求 : 从功能上角度来说，涉及到分布式应用工作负载的调度，分析，监测与操作。下面讨论这三个功能领域。 l 工作负载调度 工作

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

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

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

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

26、布式系统的结构图 其中，（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。若干模块构成一个任务，一个任务是单一的处理实体，任务的分解和分配是用于减少IPC的两个必要步骤。传

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

30、不仅可能抵消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=W(i),0iN-1，系统的

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

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

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

37、的两模块间通信量很大，必须分配给一个处理机。可见，图中节点间连线上的权表示分配在不同处理机上每对模块之间的通信开销。我们假定任何一对同驻模块的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上的处理开销，它是该模块处理要求的度量。qi,k=隐含模块mi

38、不可能在处理机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添加两个节点以表示两个可用的处理机P1

39、和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程序设计策略 这种策略的主要思想是把任务分配问题概括成一种“优化问题”，然后利用数学程序设计去解决它（J. A.

41、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 存储容量方面的限制可表示为 其中si表示模块mi所需要的存

43、储容量，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上处理模块mi 是的排队延迟。

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