（计算机应用技术专业论文）基于融合小生境遗传禁忌算法的多目标网格任务调度研究.pdf

工程硕：i ：学位论文 摘要 随着网格技术的发展与深入研究，地理上分散的异构资源可以通过 网格技术组织成一个虚拟的超级计算机。网格任务调度就是如何最有效 的管理和利用巨大的网格资源来的完成各种计算任务。任务调度是网格 计算中的一个重要组成部分，一直是国际和国内学术界的热点研究领域。 本文研究了一种融合小生境的遗传禁忌算法及其在多目标网格任务调度 中的应用研究。 分析网格任务调度的内容、意义及研究现状，并在此基础上分析了 网格任务调度目前存在的问题。提出一种融合小生境技术的遗传禁忌算 法( n g a t s ) 。基本思想是针对遗传算法在全局优化问题中容易出现早熟 和收敛速度慢，禁忌搜索强烈依赖于初始解等问题，本文根据遗传算法 和禁忌搜索算法自身的特点，分析两者的优势和不足，提出了一种融入 小生境技术的遗传禁忌算法( n g a t s ) 。该算法采用融入了小生境技术的 遗传算法作全局搜索，用禁忌搜索算法作局部搜索，可以加快收敛速度， 同时可以抑制早熟现象，避免过早收敛到局部最优。分析和实验结果表 明，该算法能很好的抑制早熟收敛，同时在计算速度和计算结果方面都 有改进，是一种快速有效的优化算法。 针对在动态、复杂的网格系统中，资源的失效非常频繁，影响网格 计算的服务质量和效率的问题，将上述算法n g a t s 应用于多目标网格任 务调度，形成一种新的融合小生境的遗传禁忌的多目标网格任务调度算 法( n g a t s m o g t s ) ，将任务生存性和任务完成时间( m a k e s p a n ) 结合起 来，给出一个可调节的多目标集成效用函数。 用g r i d s i m 模拟仿真软件对n g a t s m o g t s 进行仿真实验。模拟实 验结果表明，n g a t s m o g t s 能够有效的平衡任务生存性和m a k e s p a n 两 个目标，更适合开放复杂的网格计算环境。 关键词：网格；任务调度；多目标；遗传算法；禁忌算法：小生境；g r i d s i m a b s t r a c t w i t ht h e d e v e l 。p m e n to fg r i d t e c h n o l 。g y a n d i n d e p t hs t u d y ， g e o g r a p h i c a l l yd i s p e r s e da n dh e t e r o g e n e o u sr e s o u r c e sc a nb eo r g a n i z e di n t o av i r t u a lg r i ds u p e r c o m p u t e r g r i dt a s k s c h e d u l i n gi sh 。wt 。c a r r y 。u tt h e m o s te f f e c t i v e m a n a g e m e n ta n dh o wt o e f f e c t i v e l yc o m p l e t ea 1 1k i n d so f c o m p u t i n gt a s k sb yu s eo f g i a n t 1 m p o r t a n tp a r to fg r i dc o m p u t i n g i t g r i d s o u r c e s t a s k s c h e d u l i n g i sa n h a sa l w a y sb e e na na c t i v er e s e a r c ha r e a 1 ni n t e r n a t i o n a la n dd o m e s t i ca c a d e m i cc i r c l e s t h e t h e s i si st od e v e l o pa f u s i o nn i c h e g e n e t i ct a b us e a r c h a l g o r i t h m a n di t s a p p l i c a t i o ni n m u l t i o b j e c t i v eg r i dt a s ks c h e d u l i n ga p p l i c a t i o nr e s e a r c h t h e p r o b l e m so f g r i d t a s k s c h e d u l i n g a r e s u m m a r i z i n gr e s e a r c hc o n t e n ta n ds i g n i f i c a n c eo fg r i d r e s e a r c ha c t u a l i t y g e n e t i ca l g o r i t h ma n dt a b u s o l v et h ec o m p l i c a t e dl a r g e s c a l e a n a l y z e dt h r o u g h t a s ks c h e d u l i n ga n d s e a r c h a l g o r i t h ma r ep o w e r f u lt o o l st o o p t i m i z a t i o np r o b l e m s t od e a lw i t ht h e p r e m a t u r i t ya n dl o wc o n v e r g e n c es p e e dw h e nt h eg e n e t i c a l g o r i t h mb e i n g u s e df o rg l o b a lo p t i m i z a t i o na n dt a b us e a r c hd e p e n do n i t si n i t i a ls o l u t i o n s t r o n g l y t h r o u g hc o m p r e h e n s i v ec o n t r a s t a n de o m p a r is o nb e t w e e nt h e a b o v et w o a l g o r i t h m ，ah y b r i do p t i m i z a t i o na l g o r i t h mw a si n t r o d u c e dt o 1 m p r o v et h el a ls e a r c ha b i l i t yo fg e n e t i ca l g o r i t h m i nt h i s a i g o r i t h m i n o r d e rt os p e e du pc o n v e r g e n c es p e e da n dg e t s a t i s f i e dr e s u l t s ，t a b us e a r c h a l g o r l t h mw a su s e df o rl o c a l s e a r c h ，g e n e t i ca l g o r i t h mw a s a p p l i e df o r g j o b a ls e a r c h m e a n w h i l en i c h ew a si m p o r t e dt oc o n t r o lp r e m a t u r i t va n dt o a v o i d c o n v e r g i n g t ol o c a l o p t i m u m t h et e s tr e s u l t ss h o wt h a t b o t h c a l c u j a t l n gs p e e da n do u t p u ta r ei m p r o v e d ， s oi ti saf a s ta n de f f e c t i v e a l g o r i t h m k e s p o n s e1 nad y n a m i c ，c o m p l e xg r i ds y s t e m s ，r e s o u r c ef a i l u r ei s v e r v f r e q u e n t ， a f f e c t i n g s e r v i c e q u a l i t ya n d e f f i c i e n c y o f g r i dc o m p u t i n g p r o b l e m s ，t h ea b o v ea l g o r i t h m ( n g a t s ) i s a p p l i e dt om u l t i o b j e c t i v eg r i d a s k s c h e d u l l n g ，i n t e g r a t i o no ft h ef o r m a t i o no fan e wn i c h em u l t i o b j e c t i v e g e n e t l ct a b o og r i dt a s k s c h e d u l i n g a l g o r i t h m ( n g a t s m o g t s ) t h e s u r v i v a lo ft h et a s ka n dt a s kc o m p l e t i o nt i m e ( m a k e s p a n ) c o m b i n e dg i v e a n a d j u s t a b l em u l t i 。o b j e c t i v ei n t e g r a t i o no ft h eu t i l i t yf u n c t i o n t 程硕 ：学位论文 p e r f o r m i n ga ne x p e r i m e n tb a s e do ng r i d s i mt oe m u l a t i n gt h ea l g o r i t h m n g a t s m o g t s t h es i m u l a t i o nr e s u l t ss h o wt h a tt h es c h e d u l i n ga l g o r i t h m c a nt r a d eo f ft h e s et w oo b je c t i v e s s oi tc a nb ea p p l i e di nt h ec o m p l e xg r i d c o m p u t i n ge n v i r o n m e n tw e l l k e y w o r d ：g r i d ；t a s ks c h e d u l i n g ；m u l t i o b j e c t ；g e n e t i c a l g o r i t h m ； t a b us e a r c h ；n i c h e ；g r i d s i m 基于融合小生境遗传禁忌算法的多日标网格任务调度研究 插图索引 图1 1 五层沙漏结构4 图1 2 基于w e b 服务的o g s a 结构6 图1 3 论文的组织结构1 1 图3 1n g a t s 算法总体框架：2 0 图3 2 目标函数进化曲线图2 2 图4 1 任务依赖关系图2 6 图4 2 任务调度图2 7 图4 3 染色体结构2 8 图5 1g r i d s i m 体系结构3 5 图5 2 在线模式下，三中算法在不同任务数下的性能比较( 计算节点 数为1 0 ) 4 1 图5 3 在线模式下，三中算法在不同计算节点数下的性能比较( 任务 数为6 0 0 ) 4 2 图5 4 批模式下，三中算法在不同任务数下的性能比较( 计算节点数 为10 ) 4 3 图5 5 批模式下，三中算法在不同计算节点数下的性能比较( 任务数 为6 0 0 ) 4 4 v i t 程硕十学位论文 附表索引 表3 1 三种算法性能比较2 3 表3 2 对函数f 2 采用g a 、t s 和n g a t s 算法的计算结果比较2 4 v l i t 程硕 二学位论文 1 1 研究背景 第1 章绪论 2 0 世纪9 0 年代以来，i n t e r n e t 得到了迅速的发展，已经成为人们通 信和协同工作的基本工具。i n t e r n e t 将成千上万的计算资源、数据资源、 各种数字化设备和控制系统共同构成了生产、传播和使用知识的重要载 体。然而如此巨大的资源，并没有得到充分的利用，“信息孤岛”现象严 重，各种资源之间相互独立，没有得到有效的共享。面对这种需求，网 格计算应用而生。可以说，因特网在2 0 世纪8 0 年代的诞生，9 0 年代初 万维网技术的出现和迅速推广，2l 世纪初网格计算技术的提出，形成了 互联网发展史上的三大里程碑。 众所周知，高性能计算已经成为许多科学和工程实践的关键技术。 科学家们也越来越多地使用超级计算机来研究复杂现象，例如可以用来 预测复杂的非线性现象，或者是在做实验之前，就可探索物理参数的变 化规律，甚至还可以用来模拟现实世界中所发生的某些事件。然而，尽 管超级计算机的能力在不断增长，仍然有许多应用无法实现。因为这些 应用往往需要处理能力强大的超级计算机的支持，但是超级计算机造价 极高，通常只有一些国家级的部门，如航天、气象等部门才有能力配置 这样的设备；另一方面，某些应用对计算的要求非常高，即使是现在最 大的超级计算机也无法提供它们所需的资源，这时就需要将高性能计算 依托i n t e r n e t 或其他高速网络将遍布世界各个角落的能力千差万别的计 算资源联结在一起，形成大规模的几乎可以无限扩展的计算能力。因此， 对网格计算的研究具有很强的现实意义。 网格计算的目的是将地理分布、系统异构的各种高性能计算机、 数据库服务器、大型存储器和可视化、虚拟现实系统等资源，通过高速 互连网络连接起来，形成对用户相对透明的高性能虚拟计算环境，协同 解决大型应用的计算问题，实现计算资源、存储资源、数据资源、信息 资源、知识资源、专家资源等的全面共享，为用户提供优质的计算服务。 要实现如此强大的功能，如何最有效的管理和利用巨大的网格资源来完 成各种计算任务是一个重点。 任务调度是高性能计算中的一个重要组成部分，而随着网格的出现， 在任务调度中出现了很多新的特性，从而对传统的调度算法也提出了新 的挑战1 2 】。传统的并行计算调度算法主要是调度一个应用程序的子任务 到并行的计算机，主要目的是减少计算时间；而对于网格环境，调度算 基于融合小生境遗传禁忌算法的多目标网格任务调度研究 法关心的主要问题是调度来自不同用户的应用流到可用的计算资源上， 从而最大限度地让网格系统得到最大的使用，它追求的是调度的高吞吐 率。作为目前网格计算事实上的标准，g l o b u s 并没有具体实现任务调度 算法，针对具体的应用网格，必须在高层设计出高效的任务调度算法。 然而现有的一些调度算法如b a c k f i l l i n g 、f c f s ( f i r s tc o m ef i r s ts e r v e ) 等 并不能很好的适应网格资源的特性，如调度问题的n p 完全性，调度算法 的高效性，资源的异构性以及资源分配决策的并行性和分布性等。 1 1 1 网格简介 网格( g r i d ) 这个词来自于电力网格( p o w e r g r i d ) 。“网格”与“电力网格” 形神相似。一方面，计算机网纵横交错，很像电力网；另一方面，电力 网格用高压线路把分散在各地的发电站连接在一起，向用户提供源源不 断的电力。用户只需插上插头、打开开关就能用电，一点都不需要关心 电能是从哪个电站送来的，也不需要知道是水力电、火力电还是核能电。 建设网格的目的也是一样，其最终目的是希望它能够把分布在因特网上 数以亿计的计算机、存储器、贵重设备、数据库等结合起来，形成一个 虚拟的、空前强大的超级计算机，满足不断增长的计算、存储需求，并 使信息世界成为一个有机的整体，为各种相关应用提供底层技术支撑， 构造一个功能强大、无处不在的计算设施。 网格的创始人i a nf o s t e r 和c a r lk e s s e l m a n 曾给网格下过下过如下定 义：网格是一种新兴的基础设施，它将从根本上改变我们思考和使用计 算机的方式。网格这个词来源于可随时随地提供电能的电力网( e l e c t r i c p o w e rg r i d ) ，它像计算机和其它科技进步的产物一样，对人类的能力和 社会有着巨大的影响。人们相信通过使信息技术基础设施中的所有成分， 包括计算能力、数据库、传感器和人，灵活共享成为真正的协同工具， 网格将会有着类似的改造效果，导致新型应用的出现。 清华大学李三立院士将网格与信息高速公路做了比较，他认为【jj ：“将 先进计算基础设施( 网格) 与信息高速公路相比较，可以说信息高速公路是 信息传输和获取信息的基础设施；而先进计算基础设施则是信息处理的 基础设施。虽然，国内外都有不断扩充信息高速公路频带宽度、改进路 由器性能的计划；但是，国外专家认为：真正的下一代信息基础设施是 先进计算基础设施。它将使以计算机为主体的信息处理发生根本性的变 化。” 中科院计算所李国杰院士认为1 4j ：“网格不同于国外正在搞的 i n t e r n e t 2 或下一代i n t e r n e t ，网格可以称作是第三代i n t e r n e t ，其主要特 点是不仅仅包括计算机和网页，而且包括各种信息资源，例如数据库、 2 t 程硕十学位论文 软件及各种信息获取设备等，它们都连接成一个整体，整个网络如同一 台巨大无比的计算机，向每个用户提供一体化的服务。” 网格的应用领域十分广泛，人们将其称为第三代i n t e r n e t ，试图实现 互联网上所有资源的全面连通1 5j ，用g g g ( g r e a tg l o b a lg r i d ) 代替w w w 的地位，影响人类的尖端科研到商业应用乃至日常生活。 在计算科学与工程领域，计算科学家和工程师需要用网格进行大量 的科学计算和过程监控，分布在不同实验室的科学家可以使用不同的计 算机来协同解决同一问题，也可将远处的仪器、设备、传感器等与网格 建立连接，以便研究者进行三维可视化模拟，召开远程会议等。实验科 学家希望将远程仪器与超级计算机连接起来，通过高级用户界面来控制 仪器，实现远程沉浸、远程脑外科手术或者天文数据处理。网格具有天 然的增强协作的能力，为全球性的大公司和协会之间共享分布的信息与 资源提供了平台。在网格的支持下，通过建立交互式的可靠的大型数据 库，所有领域的研究者可以充分利用知识库集成的关于某些问题的科学 知识，协同研究和解决多学科性质的问题。 总之，网格可提供计算服务、数据服务、应用服务、信息服服务、 知识服务等，具有航空建模、高能物理、计算化学、光线追踪、数据挖 掘等广泛的应用领域。随着网格技术的不断完善和应用领域的不断扩展 可以在更多的领域得到应用，发挥更大的作用。 1 1 2 网格任务调度的重要地位 在网格系统中，任务调度系统是其重要的组成部分，它根据任务信 息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于 网格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于 资源的不同需求，使得任务调度变得极其复杂，不好的任务分配策略， 将会增加任务的执行时间、降低整个网格系统的吞吐量。因此，网格任 务调度的好坏，关系到网格系统的成败。 1 2 网格计算的研究进展 1 2 1 网格的体系结构 网格体系结构是关于如何构建网格的技术，包括对网格基本组成部 分和各部分功能的定义和描述，对网格各部分相互关系和集成方法的规 定，以及有效运行机制的刻画。显然，网格体系结构是网格中最核心的 技术，只有建立合理的网格体系结构，才能够设计和建造好网格，才能 使网格有效的发挥作用。网格体系结构主要有抽象层次结构、积木块结 基于融合小生境遗传禁忌算法的多目标嘲格任务调度研究 构、概念空间结构、混合结构和0 s g a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 结构5 中形式。目前比较重要且有影响的网格体系结构是五层沙漏结构 和开放网格服务结构o s g a 。 1 五层沙漏结构 五层沙漏结构是基于美国国家实验室的网格研发项目g l o b u s t6 】提出 来的，该结构的一个重要的思想就是以“协议”为中心，通过协议可以实 现一种机制，使得虚拟组织的用户和资源之间可以进行资源使用的协商， 建立共享关系，并且可以进一步管理和开发新的共享关系。五层沙漏结 构的重要特点是各部分协议的数量不同，形成一个沙漏形状，对于其核 心部分，要能够实现上层向核心的映射，同时实现核心协议向下层其它 各种协议的映射，核心协议在所有支持网格计算的地点都应该得到支持。 五层沙漏模型结构如图1 1 所示。 工具与应用 应用层 彦搿； 汇聚层 ) 资霎萎：詈的 ( 资源层 与连接层 飘 构造层 图1 1 五层沙漏结构 可以看出五层沙漏结构被分为五层，由下往上依次是构造层、连接 层、资源层、汇聚层和应用层。 ( 1 ) 构造层( f a b r i cl a y e r ) 网格构造层的基本功能是控制局部的资源，向上提供访问这些资源 的接口。构造层的资源是非常广泛的，可以是计算资源、存储资源、目 录、网络资源以及传感器等。构造层的网格组建实现对本地特定资源的 访问，向上提供访问这些资源的接口。构造层实现的基本功能包括查询 机制、控制服务质量的资源管理能力等。 ( 2 ) 连接层( c o n n e c t i v i t yl a y e r ) 4 t 程硕十学位论文 连接层的基本功能是保证构造层的资源实体间相互通信的便利和安 全。在这一层，网格定义了核心网络事务处理所需要的通信和认证协议。 通信协议允许在构造层资源之间互换数据，建立在通信服务上的认证协 议提供加密的安全机制，用于识别用户和资源。 ( 3 ) 资源层( r e s o u r c el a y e r ) 资源层的主要功能是实现对单个资源的共享。资源层建立在连接层 的通信和认证协议之上，定义的协议包括安全初始化、监视控制单个资 源的共享操作、审计、计费等。资源层的协议只考虑单个的局部资源， 忽略了全局状态和跨越分布式资源集合的原子操作，其协议实现调用构 造层的功能以访问和控制本地资源。资源层的重要的两个协议是信息协 议和管理协议，前者用于获得关于资源结构和状态的信息，后者用来协 商对共享资源的访问。 ( 4 ) 汇聚层( c o l l e c t i v el a y e r ) 汇聚层的作用是将资源层提交的受控资源汇集在一起，供虚拟组织 的应用程序共享、调用。为了对来自应用的共享进行管理和控制，汇聚 层提供目录服务、资源分配、日程安排、资源代理、资源监控诊断、网 格启动、负荷控制、账户管理等多种功能。 ( 5 ) 应用层( a p p l i c a t i o nl a y e r ) 应用层是网格上用户的应用程序。应用程序通过各层的a p i 调用相 应的服务，再通过服务调用网格上的资源来完成任务。应用程序的开发 设计大量的库函数。为了便于网格应用程序的开发，需要构建支持网格 计算的库函数。 2 开放网格服务结构o s g a 开放网格服务结构o s g a 是继五层沙漏结构之后最重要，也是目前 最新的一种网格体系结构，如图1 2 所示。 o g s a 的目的是将网格的一些功能融合到w e bs e r v i c e 框架中。o g s a 是面向服务的结构，计算资源、存储资源、网络、程序、数据等都是事 务，将所有事务都表示成一个服务，所有的服务都联系对应的接口，所 以，o g s a 被称为是以服务为中心的“服务结构”，通过标准的接口和协议 支持创建、终止、管理和开发透明的服务。结合目前的w e bs e r v i c e 技术， 支持透明安全的服务事例，o g s a 有效的拓展了w e bs e r v i c e 架构的功能， 它将网格从以科学与工程计算为中心的学术研究领域，扩展到更广泛的 以分布式系统服务集成为主要特征的社会经济活动领域，包括各种计算 资源、存储资源、网络、数据库等。o g s a 还提供了一种网格安全机制来 确保服务间所有的通信安全。o g s a 解决了两个重要的问题：标准服务接 口的定义和协议的识别。 基于融合小生境遗传禁忌算法的多日标网格任务调度研究 圈圆圈圜圜圈 图1 2 基于w e b 服务的o g s a 结构 o g s a 框架主要由四个层次构成，从下往上依次是资源层、w e b 服 务层、o g s a 体系结构服务层、网格应用层。 ( 1 ) 资源层 资源层是o g s a 以及通常意义上的网格计算的中心部分，包括物理 资源和逻辑资源。物理资源包括服务器、存储器和网络。逻辑资源通过 虚拟化和聚合物理层的资源来提供额外的功能。 ( 2 ) w e b 服务层 o g s a 中所以网格资源( 物理的和逻辑的) 都被理解成服务。o g s i 规范定义了网格服务并建立在标准w e b 服务技术之上。o g s i 利用诸如 x m l 和w e b 服务描述语言，为所有网格资源指定标准的接口、行为和交 互。o g s i 进一步扩展了w e b 服务的定义，提供了动态的、有状态的和可 管理的w e b 服务的能力，这对网格资源进行建模是必须的。 ( 3 ) 基于o g s a 架构的服务 w e b 服务层及其o g s i 扩展为下一层提供了基础设施一基于架构的 网格服务。g g f 目前正致力于在程序执行、数据服务和核心服务等领域 中定义基于网格架构的服务。随着这些新架构服务的出现，o g s a 将变成 更加强大的面向服务的架构。 ( 4 ) 网格应用层 随着时间的推移，一组丰富的基于网格架构的服务不断被开发出来， 利用一个或多个基于网格架构的服务的新网格应用程序亦将出现。这些 应用程序构成了o g s a 架构的第四个层次。 6 工程硕十学位论文 1 2 2 国内外网格计算的研究现状 网格计算的重要战略意义及其广阔应用前景，使其吸引了众多研究 人员和巨大资金投入。继学术界之后，各国政府和商业界分别启动了 一系列的研究项目。作为网格计算的基本组成部分，网格任务调度是这 些研究项目的重要研究对象。 19 9 2 年，美国开始实施高性能计算方面的计划h p c c ，并投入巨资 解决“巨大挑战问题”的环境、方法和技术。美国国防部的“全球信息网格 ( g l o b a li n f o r m a t i o ng r i d ) ”计划，预计在2 0 2 0 年完成。作为这个计划 的一部分，美国海军和海军陆战队已先期启动一个l6 0 亿美元的八年项 目，包括系统的研制、建设维护和升级。英国政府已决定投资一亿英镑， 用来建设“英国国家网格( u kn a t i o n a lg r i d ) ”。韩国政府也已正式宣布 建立第三代网络基础之国家网格基本计划，计划在五年内把分散的高性 能计算机通过往来连接起来并加以利用。 主要i t 厂商为获取该领域的控制权也展开了积极的竞争。2 0 0 2 年8 月，i b m 宣布投入四十亿美元，启动一个全公司的“网格计算创新计划”， 与g l o b u s 合作，把g l o b u s 标准与支持商用的万维网服务标准结合起来， 开发开放的网格计算标准o g s a ，将网格计算由学术界的科学计算应用扩 展到商业应用。其它公司也不甘示弱。s u n 也已启动了以g r i de n g i n e 分 布式资源管理软件为基础的开放源代码战略。m i c r o s o f t 的研究部门也积 极参与相关项目，包括容错远程文件系统f a r s i t e 和分布式系统m i l l e n i u m 的建设。 1 目前国际上有影响的几个网格计算研究项目如下【7j ： ( 1 ) gio b us o g s a g l o b u s 是美国阿岗国家实验室的研发项目，全美有12 所大学和研究 机构参与了该项目。g l o b u s 的主要研究目标有两个，一是网格技术的研 究，设计资源管理、安全、信息服务及数据管理等网格计算的关键理论； 二是相应软件的开发和标准的指定，具体成果是能在各种平台上运行的 网格计算工具软件( t o o l k i t ) ，开发适合大型系统运行的大型应用程序； ( 1 ) l e gi0 n l e g i o n i8 】是弗吉尼亚大学的研究项目，是面向对象技术在网格计算领 域应用的重要事例，支持透明的调度、数据管理、容错、站点自治和各 种安全选项。然而，面向对象方法也面临一些问题，例如很难支持与遗 留应用和服务的交互： 3 c o n d er 7 幕于融合小生境遗传禁忌算法的多目标嘲格任务调度研究 c o n d e r 9 l 项目开发、部署和评估支持在大规模分布资源集合上进行高 吞吐量计算的机制和策略。c o n d e r 环境采用分层体系。c o n d e r 中的资源 提议和请求通过其分类公共语言c l a s s a d 描述。c o n d e r 不支持服务质量； 4 nimro d - g n i m r o d g 【1 0 】是一个网格资源代理，由四个关键构件组成：作业管理 引擎、调度器、分派器和智能主体。n i m r o d g 支持资源的发现、选择、 调度与用户作业在远程资源中的透明运行。n i m r o d g 相关的研究成果还 包括g r i d s i m 工具集，提供复杂的设施以支持网格资源和应用调度的建 模模拟，可用于评估调度算法的性能； 5 a p p l e s 应用级调度项目a p p l e s t 】着重研究和开发在计算网格中调度单个 应用的智能主体。a p p l e s 智能主体嵌入到应用中以网格计算环境中进行 资源调度，因而对应用而言将作业映射到资源的调度是集中式的，但实 际运行应用的各个任务则由本地的资源调度器负责。a p p l e s 调度器的缺 点在于它不支持服务质量。目前，a p p l e s 的应用领域包括磁流体运动学、 基因序列比较、卫星雷达图像生成和x 射线断层摄影术等； 6 n e t s oip e n e t s o l v e 1 2 】是一个网格应用工具，提供基于远程过程调用的数值计 算编程环境。它由三个部分组成：服务的请求者、服务调度与维护者和 服务的提供者。n e t s o l v e 使得数值计算类型网格的编程工作变得十分简 单，而且容易跨平台； 7 d a ta grid 欧洲的d a t a g r i d 1 3 】项目是为建立大型强子对撞击l h c ( l a r g eh a d r o n c o l l i d e r ) 应用而生的，其基本思想是把生成的海量数据分散到全球的计 算机上进行处理，并由全球的物理学家共同进行分析。d a t a g r i d 的主要 功能包括负载调度、数据管理、系统监控、构造层管理、海量存储管理 在占 守。 8 s e ti h o m e 加州大学伯克利分校的s e t i h o m e 1 4 l 项目是对等计算的一个成功 典范。项目组称，在不到两年的时间里，这种计算方法已经完成了单台 计算机3 4 50 0 0 年的计算量，可见处理能力十分强大。 对于网格计算，我国政府给予了高度重视。我国已经开展了“中国国 家网格”、“教育科研网格”、“织女星网格 和“先进计算基础设施北京、上 海试点工程”等大型网格项目的研究。网格计算研究主要集中在中科院、 国防科大、清华大学等几家在高性能计算方面有较强实力的研究单位。 在国家高技术研究发展计划( 86 3 计划) 的支持下，我国的多项网格研究 已经取得了突破。国内主要网格项目有： 8 工程硕士学位论文 1 国家高性能计算环境 国家高性能计算环境( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n g e n v i r o n m e n t ，简称n h p c e ) 是国家高性能计算和信息服务的战略性基础 设施。该项目的目标是建立一个计算资源广域分布、支持异构特性的计 算网格示范系统，它把我国的8 个高性能计算中心通过i n t e r n e t 连接起来， 进行统一的资源管理、信息管理和用户管理，并在此基础上开发了多个 需要高性能计算能力的网格应用系统，已取得了一系列的科研成果。计 算所在国家高性能计算环境之后，推出了“服务网络”的概念，并把挽歌 研究所统称为“织女星网格( v e g ag r i d ) ”【l 引。其目标是使同一个平台同 时具备大规模的数据处理能力、高性能计算能力、资源共享和提高资源 利用率的能力。“织女星网格( v e g ag r i d ) ”主要研究了网格硬件层面、 网格系统软件层面、网格应用层面的内容； 2 中国教育科研网格 中国教育科研网格的目标是将广泛分布在中国教育科研网c e r n e t 和高校中的异构海量资源集成起来，实现c e r n e t 环境下资源的有效共 享，消除资源孤岛，提供有效服务，形成高水平低成本的服务平台，将 高性能计算送到教育和科研网用户的桌面上，成为国家科研教学服务的 大平台； 3 国家地质调查应用网格 国家地质调查应用网格基于网格技术，以“服务”为中心，提出并构 建了从信息获取、处理到应用的完整的7 层体系结构。同时结合行业应 用需求，着重研究资源管理、资源交易、服务等关键技术，提出了一种 新的服务链模型( 服务资源网) ，实现地质调查领域的资源共享和信息 服务； 4 中国气象应用网格 中国气象应用网格，其目标是以“十五”国家科技公关项目“中国气象 数值预报系统技术创新研究”的研究成果为基础，研制基于网格技术的数 值天气预报软件及其支持软件；利用中国气象局已有的卫星气象通讯网 络的高性能计算资源，深入研究数值预报工作流管理、服务网格构建、 防火墙突破等技术。 1 2 3 网格任务调度研究现状 在网格系统中，任务调度系统是其重要的组成部分，它根据任务信 息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于 网格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于 资源的不同需求，使得任务调度变得极其复杂，不好的任务分配策略， 9 幕于融合小生境遗传禁忌算法的多日标嘲格任务调度研究 将会增加任务的执行时间、降低整个网格系统的吞吐量。因此，网格任 务调度的好坏，关系到网格系统的成败。 1 3 本文的主要工作及组织结构 1 3 1 本文的主要工作 由于时间和水平有限，对于以上存在的问题，本文只对网格计算的 核心内容一一网格任务调度算法进行探索，以推进网格任务调度系统的研 究。本文的研究工作主要从以下几个方面展开： 一、对网格的发展及应用现状进行系统总结，详细分析现有各种网 格任务调度算法，分析现有网格任务调度算法的不足，为后文设计基于 遗传算法和禁忌搜索算法的网格任务调度策略提供参考； 二、研究遗传算法和禁忌搜索算法的机理，提出融合小生境技术的 遗传禁忌算法。深刻理解遗传算法和禁忌搜索算法的优缺点，以及两者 的内在联系，提出兼顾遗传算法和禁忌搜索算法优点的融合小生境技术 的遗传禁忌算法，并引入了几个常用的全局优化测试函数对算法的有效 性进行了验证； 三、研究网格系统的服务质量问题，根据网格任务调度特点，提出 基于融合遗传禁忌算法的多标网格任务调度策略。在动态网格环境中， 一个好的任务调度算法不但要考虑任务的m a k e s p a n ，使其尽量小，同样 要考虑整个系统的服务质量问题。本文研究了任务生存性概念，提出了 基于m a k e s p a n 和任务生存性的融合小生境遗传禁忌多目标网格任务调度 算法； 四、调度系统的仿真与分析。深入分析g r i d s i m 这一网格仿真软件， 用g r i d s i m 构建本文所提出的任务调度算法的模拟平台，并针对真实网 格环境的特点，给出自己设计的模拟程序，进而对本文所提出的任务调 度算法进行仿真与分析。 1 3 2 本文的组织结构 论文分为绪论( 第一章) 、主体( 第二章到第五章) 、结论( 第六章) 、参 考文献、致谢以及攻读硕士学位期间的主要研究成果等六个部分。 第一章为绪论。本章介绍了本课题的研究背景，综述了网格及其任 务调度技术的国内外研究现状，介绍了本课题的主要研究内容及本论文 的组织结构。 第二章主要研究网格环境中目前的网格任务调度算法。 第三章主要研究融合小生境技术的遗传禁忌算法。 1 0 工程硕l 二学位论文 第四章主要研究融合小生境遗传禁忌算法在多目标网格任务调度的 应用。 第五章主要研究基于g r i d s i m 的多目标网格任务调度算法的设计与 仿真。 最后对本论文进行总结，并提出了进一步的研究方向。 参考文献部分列出了本论文参考的主要论文和资料。附录部分给出 了攻读硕士学位期间的主要研究成果。最后的致谢部分对导师和各位师 友所提供的帮助表示衷心的感谢。 论文的组织结构如图1 3 所示。 网格任务调度的研究意义、研究 现状及本文的主要研究内容 上 融合小生境技术的遗传禁忌算法 融合小生境遗传禁忌多目标网格任务 调度研究 1r 基于gr i d s im 的多y l 标网格任务调度 仿真与实现 1r 本文的工作总结及进一步研究工作 图1 3 论文的组织结构 基于融合小生境遗传禁忌算泫的多目标网格任务调度研究 第2 章网格环境中的任务调度问题 网格是一个分布式的异构环境，主要由网格中间件系统与在i n t e r n e t 上的各个分布式共享资源组成。在网格系统中，任务调度系统是其重要 的组成部分，它根据任务信息采用适当的策略把不同的任务分配到相应 的资源节点上去运行。由于网格系统的异构性和动态性，以及运行于网 格系统之中的应用程序对于资源的不同需求，使得任务调度变得极其复 杂，不好的任务分配策略，将会增加任务的执行时间、降低整个网格系 统的吞吐量。因此，网格任务调度的好坏，关系到网格系统的成败i l 。 2 1 网格任务调度的特点 网格的任务调度是在传统高性能计算和分布式系统中的调度策略和 技术的基础上，结合网格的具体特征来设计的，因此网格调度十分复杂， 具体来说网格任务调度系统主要具有以下几个特点【l7 j ： 1 任务调度是面向异构平台的。由于网格系统是由分布在i n t e r n e t 上的各类资源组成的，包括各类主机、工作站甚至p c 机，它们是异构的， 可运行在u n i x ，w i n d o w sn t 等各种操作系统下，也可以是上述机型的 机群系统、大型存储设备、数据库或其他设备。因此网格系统中的任务 调度必须面向异构平台，并在这些平台上实现网格任务的调度； 2 任务调度是大规模的、非集中式的。由于网格系统是一个巨大的 整个i n t e r n c t 的分布式系统。要实现一种全局的统一集中的任务调度管理 是根本不可能的。因此，网格的任务调度必须以分布、并行方式进行任 务的管理与调度； 3 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网 格节点的内部调度策略是自治的，网格任务调度系统干预其内部的调度 策略是没有必要的，也是不可能的； 4 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随 着超级计算机系统的不断加入，系统的计算规模也必将随之扩大。因此， 在网格资源规模不断扩大、应用不断增长的情况下，网格系统的任务调 度必须具有可扩展性； 5 任务调度能够动态自适应。网格中的资源不但是异构的而且网格 的结构总是不停地改变：有的资源出现了故障，有的新资源要加入到网 格中，有些资源重新开始工作等。总之网格的动态性是明显的，所以任 务调度系统必须适应网格的这种动态性，从可利用的资源中选取最佳资 源为用户提供应用服务。 1 2 工程硕十学位论文 2 2 网格任务调度的主要目标 简单地说，网格计算任务调度的目标就是要对用户提交的任务实现 最优调度，并设法提高网格系统的总体吞吐率。具体的目标包括【l8 】：最 优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡 ( l o a db a l a n c i n g ) 、经济原则( e c o n o m i cp r i n c i p l e s ) 等。 ( 1 ) 最优跨度。跨a 度是一个最主要、最常见的目标，指的是调度的 长度，也就是从第一个任务开始运行到最后一个任务运行完毕所经历的 时间。跨度越短说明调度策略越好。当用户向网格系统提交任务后，最 大的愿望是网格系统尽快完成自己的任务。可见，实现最优跨度是用户 和网格系统的共同目标。 ( 2 ) 1 艮务质量q o s 。网格系统要为用户提供计算和存储服务时，用户 对资源需求情况是通过q o s 形式反映出来的。任务管理与调度系统在进 行分配调度任务时，保障网格应用的q o s 是完全应当的。 ( 3 ) 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键 问题。网格系统更进一步扩