（计算机软件与理论专业论文）面向分布式仿真系统的网格元任务调度算法的研究.pdf

上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 摘要 将网格技术有效地应用到复杂分布式仿真应用系统中，可以有效地降低仿 真应用系统的开发费用和开发周期。为了能充分利用网格中的各种资源，为基 于网格技术的分布式仿真系统设计一个高效的资源调度算法是十分重要和迫切 的。 本文引入了适合基于网格技术的分布式仿真系统特征的元任务模型，提出 了一种基于元任务模型的资源调度算法。该调度算法从全局出发，不是以单个 任务的计算量、单种资源的利用率为唯一的标准，而是兼收了静态任务调度算 法和动态任务调度算法的优点，因此能有效的利用网格资源，发挥各种资源的 优势。该调度算法还实现了任务调度中的资源预约机制。 论文还在l i n u x 下使用s i m g r i d 模拟器实现了本文提出的调度算法和几个 常用的调度算法。在确立了任务与资源间关系的模型的基础上，对这些算法进 行了实验和分析。实验结果表明，当任务与资源之间存在某种联系时，本文提 出的调度算法能够有效的利用这种联系，从而更好地提高算法的性能。 关键字：先进分布式仿真网格元任务任务调度资源分配 t 海大学硕上学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y a b s t r a c t ae o m p l i c a t e d ，d i s t r i b u t e ds i m u l a t i o ns y s t e mc a nb ed e v e l o p e da t l o w e rc o s tw i t ht h ea p p l i c a t i o no fg r i dt e c h n o l o g y i tc a l l sf o ra n e f f i c i e n ta n dp r a c t i c a lr e s o u r c ea l l o c a t i o na l g o r i t h mf o rd i s t r i b u t e d s i m u l a t i o ns y s t e m st om a k et h eb e s to fa l ts o r t so fg r i dr e s o u r c e s i nt h i sp a p e r am e t a - t a s km o d e lt h a tc a nc h a r a c t e r i z et h eg r i d b a s e d ， d i s t r i b u t e ds i m u l a t i o ns y s t e mi si n t r o d u c e d ，a n dar e s o u r c ea l l o c a t i o n a l g o r i t h mb a s e do nt h i sm o d e li sp r e s e n t e d t h i sa l g o r i t h md r a w st h e s t r e n g t ho fb o t hs t a t i c r e s o u r c ea l l o c a t i o na l g o r i t h m sa n dd y n a m i c r e s o u r c ea l l o c a t i o na l g e r i t h m sw i t h o u tl a y i n gp a r t i c u l a rs t r e s s o na c e r t a i nt a s ko rac e r t a i nk i n do fr e s o u r c e s ，s ot h a tg r i ds y s t e mr e s o u r c e s c a nb eu t i l i z e de f f i c i e n t l y t h i sa l l o c a t i o na l g o r i t h ma l s op r o v i d e sa m e c h a n is i l lt or e s e r v er e s o u c e si nt h e i ra l l o c a t i o n t h ea l l o c a t i o na l g o r i t h ma n ds o m eo t h e ra l i o c a t i o na l g o r i t h m si n c o m m o nu s ea r ei m p l e m e n t e du n d e rl i n u xb yu s i n gt h es i m g r i de m u l a t o r ， a n dc o m p a r e di nf o u rr e p r e s e n t a t i v er e s p e c t so ft h er e l a t i o nb e t w e e n t a s k sa n dr e s o u r c e s t h er e s u l ts h o w st h a tt h ea l l o c a t i o na l g o r i t b m p r e s e n t e di nt h i sp a p e r h a sb e t t e rp e r f o r m a n c ed u et ot a k i n gt h e a d v a n t a g eo ft h er e l a t i o nb e t w e e nt a s k sa n dr e s o u r c e s k e y w o r d s ：a d v a n c e dd i s t r i b u t e ds i m u l a t i o n ，g r i d ，m e t a t a s k ， t a s ks c b e d u lin g ，r e s o u r c ea ll o c a tio n 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 期逊! ! ! ! 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：垒矽3 5 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v er s i t y 1 1 课题背景 第一章绪论 虚拟现实( v r ：v i r t u a lr e a l i t y ) 是计算机模拟的三维环境。用户可以走 进这个环境并操纵系统中的对象( 如运动方向、速度等) ，同时系统也向用户反馈 信息。虚拟现实带来了人机交互的新概念，带给用户强烈的真实感和临场感的 体验，这种沉浸式交互环境的实现主要依托实物虚化、虚物实化和高性能的计算 处理技术。分布式交互仿真系统( d i s ：d i s t r i b u t e di n t e r a c t i v es i m u l a t i o n s y s t e m ) 。3 可以看作是基于网络的虚拟现实系统，是可供多用户同时异地参与的 分布式虚拟环境( d v e ：d i s t r i b u t e dv i r t u a lr e a l i t ye n v i r o n m e n t ) ”1 ，处于 不同地理位置的用户如同进入到同一个真实环境中，通过姿势、声音或文字等 “在一起”进行交流、学习、训练、娱乐，甚至协同完成同一件复杂产品的设 计或进行同一任务的演练。 近年来，随着分布式仿真技术的迅速发展，节点数量的增多和分布范围的 扩大，计算日趋复杂，多单位协作日益频繁，大型分布式交互仿真系统的组织 与实施都面临着众多人员、大量异构计算资源、多信息系统之间的协作与交互。 针对复杂的分布式交互仿真系统的特点，为了有效地应用并管理众多的分布异 构资源，消除信息孤岛，基于网格技术的分布式仿真系统得到了越来越多分布 式仿真系统领域的科研工作人员的青睐。通俗地讲，网格就是一种分布的高性 能计算与数据处理的底层支持框架，能够管理众多地理上、组织上分布的异构 资源，包括计算资源、存储资源、通信资源、软件资源、知识资源、各种设备 资源，甚至合作者等。通过提供访问远程资源的可扩展的，安全的，高性能的 机制以及相应的协议、服务和软件开发工具，网格技术能使地理上分散的工作 团体充分共享资源，协同工作。 在基于网格技术的分布式仿真系统中，为了能充分利用网格中的各种资源， 设计一个高效的资源调度算法就显得十分的重要和迫切。网格是一个计算环境， 现有的资源，诸如网络、超级计算机、服务器、操作系统、数据库、文件系统 等都是网格计算的底层设施，应用程序通过网格共享这些资源来完成任务。由 于网格底层设备的分布和异构性，所以对并行任务的任务管理、任务调度和资 源管理是网格计算中的基本功能也是研究的难点和重点。现有的国内外对此环 境下的任务分配和调度算法的研究，还有待深入。 上海人学硕十学位论文 t h ep o s t g r a d u a t et h e s iso fs h a n g h a iu n i v e r s i t y 1 i2 分布式交互仿真系统的现状及发展趋势 分布式交互仿真的研究开发工作可追溯到2 0 世纪8 0 年代初。最有代表性 的当属2 0 世纪8 0 年代中期美国国防部提出的先进分布仿真( a d v a n c e d d i s t r i b u t e ds i m u l a t i o n ，a d s ) 技术的概念。1 ，a d s 是仿真技术发展的一个里程 碑。a d s 系统将分布在不同地点的、自治的单一仿真系统，通过计算机网络联 结成一个集数学仿真、半实物仿真和人在回路仿真为一体的分布交互式仿真系 统，通过采用协调一致的协议、标准、结构，实现各类仿真系统之间的互操作， 并对仿真过程进行动态管理。近年来，仿真应用系统的规模不断扩展，仿真应 用系统越来越复杂，不仅表现在仿真时域的扩展，也表现在仿真地域的扩大， 以及仿真组成的复杂上，例如涉及多技术领域，涉及多粒度仿真模型，涉及多 种时间管理机制等。同时，这种基于网络的分布式仿真系统也面临着一些问题， 主要体现在以下几个方面”1 。 ( 1 ) 缺乏仿真数据统一的描述形式 仿真应用系统都是通过数据的交互达到互操作的。可以说，数据的正确及 时交互是互操作的前提和重要内容。时间一致性和空间一致性都是保证数据正 确的条件，从而也保证了仿真过程与仿真结果的正确。数据在仿真演练开始前、 仿真演练过程中和仿真演练结束后都会在仿真应用之间传输。影响仿真数据不 一致的原因很多，主要是：1 ) 概念的不一致性，对一个事物定义的内涵和外延 不一致；2 ) 数据表现的不一致，如对f 1 6 战斗机可以用代号、也可以用名称来 唯一标识这架战斗机；3 ) 数据格式的不一致，是指表示数据的代码不一致。这 种不一致直接导致了系统交互的困难。 ( 2 ) 资源的静态分配 当前所进行的分布式仿真一般是基于局域网、为单一仿真任务服务的，仿 真资源的分配是静态的，也就是说在仿真运行前，各仿真子任务已经和资源绑 定了，这种绑定在仿真运行过程中很难再进行更改。这在客观上就要求各仿真 资源在任务运行过程中必须能够正常运行而且在每个仿真资源中必须有足够的 冗余来支持仿真任务。 ( 3 ) 缺乏对大型的并行仿真应用的支持 现有的仿真系统中的仿真应用通常采用串行的程序处理方式。但某些仿真 应用的计算量非常巨大，采用串行的程序处理方式往往不能够适应。这时，通 常采用简化仿真模型的方式来减少工作量。但这样做将相应地降低仿真的精度 上海人学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v er s i t y 和可信度。如果使用并行的程序处理方式，将不可避免使用大型的计算机来提 供计算资源。通常，在分布仿真系统中，大型计算机的计算资源提供给多个仿 真应用共享使用是困难的。 ( 4 ) 仿真资源的异地资源的调用及仿真结果的分析比较困难 大规模的分布仿真中经常会出现异地资源的调用。但是当前的网络技术不 能对这种异地资源调用提供非常好的支持；此外，基于网络的分布式仿真的结 果一般都分散存放在仿真任务运行的机器上，要进行结果分析就必须对这些数 据进行收集，提交的数据格式不规范，且效率低下容易出错。 随着网格技术。1 的出现，给分布式仿真系统提供了一个新的平台。网格技 术所具有的资源共享、协同工作、基于统一的开放技术标准等优点，正是一个 开放、通用的先进分布仿真协同工作环境所需求的。网格的主要功能是提供网 格用户一个透明的、分布的、共享的、安全的和容错的使用环境，在此环境中 用户能够共享各种资源，网格中间件为用户屏蔽复杂的底层操作。把网格技术 有效地应用到复杂分布仿真应用系统中，可以有效地降低仿真应用系统开发费 用，缩短仿真应用系统开发时间，解决上述列举的分布仿真存在的问题。 1 3 论文主要研究内容 本文研究的主要内容是面向分布式仿真系统的网格中元任务调度算法。基 于网格技术的分布式仿真系统的主要目标是通过网络互连实现网格内资源共 享，并通过有效的资源管理和资源分配策略达到提高资源利用率和仿真系统模 拟结果的实时性和精确性。在研究网格环境下的分布式仿真系统时，不仅要考 虑为分布式仿真系统提供的数据的正确性，还要保证仿真系统中各个节点的模 拟结果在时间和空间的一致性。因此研究高效的资源管理和任务调度算法是基 于网格技术的分布式仿真系统软件开发的关键问题。本文从下面几个方面对网 格中元任务调度算法进行研究、设计和分析。 ( 1 ) 通过分析分布式仿真应用系统和网格的特点，引进元任务模型，并把 元任务作为基于网格技术的分布式仿真系统中资源调度的最小单位。 ( 2 ) 通过对一些常用的任务调度算法的研究、分析和比较，并根据任务和 资源的特性，提出了一种基于网格元任务模型的调度策略。该调度策略从全局 出发，不是以单个任务的计算量、单种资源的利用率为唯一的标准，而是兼顾 静态任务调度算法和动态任务调度算法的优点。它的基本思想是：首先用静态 算法搜寻一个近似最优解，把任务预先分配给对应的资源；再根据运行时的具 【：海大学硕士学位论文 t h ep os t g r a d u a t et h e s iso fs h a n g h a iu a i v c rs l t y 体情况，对预先分配的任务进行调整，从而减少元任务的完成时问。 ( 3 ) 利用网格任务调度模拟器s i m g r i d 在l i n u x 系统下实现以上( 2 ) 的 元任务调度策略。 ( 4 ) 将以上( 2 ) 的元任务调度策略与几种常用的调度算法进行对比实验。 首先确立了用于测试的四个任务与资源间关系的模型，接着根据任务与资源间 的关系模型对这些调度算法进行实验和分析，给出本文提出的算法的优缺点和 最佳适用范围。 1 4 论文组织结构 第一章是绪论。介绍了本文的立题背景和意义，点明了本文的主要研究内 容简单介绍了基于网络的分布式仿真系统及其面临的问题。 第二章首先介绍了一些网格技术的基础知识，再介绍基于网格的分稚式仿 真系统的优势和体系结构，根据分布式仿真系统和网格的特点引入元任务模型。 第三章介绍了调度算法的基础知识，通过对一些常用的任务调度算法的研 究、分析和比较，作者根据分布式仿真系统和网格的特点。提出了一种基于元 任务模型的调度算法。 第四章首先介绍元任务调度算法的系统模型和优化目标，然后介绍本文提 出的算法的设计过程。 第五章首先介绍了s i m g r i d 模拟器的一些基础知识及算法实现中要使用到 的数据类型和a p i ，然后介绍算法的数据结构和实现的关键部分。 第六章首先介绍五种用于对比的常用算法，然后作者提出四种任务与资源 的关系模型用于对比实验，最后通过在这四种关系模型上的实验结果分析本文 提出的算法的优缺点和适用范围。 第七章是结束语，介绍了本文当前已经完成的工作，并指明了进一步工作 第七章是结束语，介绍了本文当前已经完成的工作，并指明了进一步工作 的方向。 4 【海大学硕士学位论文 t h ep o s t g r a d u a t et h e s iso fs h a n g h a iu n i v e r s i t y 第二章基于网格技术的分布式仿真环境 2 1 网格 随着互联网技术的迅猛发展，科学研究和相关应用借助网络环境获得了极大 的进步，同时在互联网上形成了大量以计算机系统为主导的计算资源、存储资源、 数据资源、信息资源、知识资源和仪器设备资源等。1 “。网格正逐步成为一种新 的技术和基础设施，可以充分利用集成的资源，形成一个大规模的计算池。利用 网格的这种超级处理能力，能够解决以前一台高性能计算机无法解决或者不容易 解决的大规模科学计算；利用网格中的共享资源，可以处理需要多种资源、多个 系统和多门学科的参与的重大应用研究问题：网格不但有助于解决物理、天文、 生物、工程和模拟等领域的科学计算问题，同时在商业领域、社会生活和国民经 济的各行各业方面具有潜在的重大影响“。 2 2 1 网格概念 网格是借鉴电力网的概念提出来的，网格的最终目的是希望用户在使用网格 计算能力时，就如同现在使用电力一样方便，为网格用户提供与地理位置无关、 与具体计算设施无关的通用计算能力。由于网格研究现在处于发展阶段，对于网 格概念还没有达成一致，下面是一些有代表性的定义和观点： i a nf o s t e r 和i c a r lk e s s e l m a n 于1 9 9 8 年在网格的第一本专著网格：一 种新的计算基础设施蓝图1 中定义如下：计算网格是一个包含硬件和 软件的基础设施，它能对高端计算能力提供可靠的、一致的、普遍的和 不昂贵的接入。 l a nf o s s t e r 等人在2 0 0 1 年认为“”：网格关心的是在动态的、多机构的 虚拟组织中协调资源共享和协同解决问题，核心思想是在一组参与节点 ( 资源提供者和消费者) 中协商资源共享管理的能力，利用协商得到的 资源池共同解决一些问题。 i a nf o s t e r 给出了判断网格的三原则“：( 1 ) 协调非集中控制资源。网 格整合各种资源，协调各种使用者，这些资源和使用者在不同控制域中， 网格还要解决在这种分布式环境中出现的安全、策略、成员权限等问题。 否则，只能算本地管理系统而非网格。( 2 ) 使用标准、开放、通用的协 议和界面a 网格建在多功能的协议和界面之上，这些协议和界面解决认 上海大学硕 j 学位论文 t h ep o s t g r a d u a t et h c s i so fs h a n g h a iu n iv e r s i t y 证、授权、资源发现和资源存取等基本问题。否则，只算一个具体应用 系统而非网格。( 3 ) 得到非平凡的服务质量。网格允许它的资源被协调 使用，以得到多种服务质量，满足不同使用者需求，如系统响应时间、 流通量、有效性、安全性及资源重定位，使得联合系统的功效比各部分 的功效总和要大得多。 中国科学院计算所所长李国杰院士认为：网格是继传统因特网、w e b 之 后的第三次互联网浪潮，可以称之为第三代因特网应用。传统因特网实 现了计算机硬件的连通，w e b 实现了网页的连通，而网格则试图实现互 联网上所有资源的全面连通，其中包括计算资源、存储资源、通信资源、 软件资源、信息资源、知识资源等。 企业界的网格相关研究开发工作中，最重要的就是w e b 服务。一些研究 机构和业界联盟己经就几个底层标准协议达成了共识，包括x m l 、s o a 、 w s d l 、u d d i 等。当前w e b h 艮务服务和网格研究正在走向融合，两个领域 的研究在很多方面已达成一致，w e b 服务资源框架w s r f ( w s - - r e s o u r c e f r a m e w o r k ) 是这种融合的一个见证，同时也是网格研究中一个重要的 新起点。w s r f 是一组被提议的w e b 服务规范，根据特定的消息交换和相 关的x m l 说明来定义w e b 服务资源方法的描述。这些规范可以声明和实现 w e b 服务和一个或者多个有状态的资源之间的关联，描述了定义资源状 态的视图以及将它与w e b 服务说明相关联从而形成w e b 服务资源类型定 义的方法，也描述了如何通过w e b 服务接口来访问w e b 服务资源的状态， 并且定义了与w e b f l 臣务资源分组和寻址相关的机制。 研究者从不同的角度和侧重点，对于网格多方面的特点和功能进行了说明， 同时由于网格是面向问题领域，不同问题的要求和解决方法不一样，因此呈现出 各种各样的定义和观点，同时网格还处于发展阶段，有关的概念也在不断变化和 发展之中的，但是从网格的起源和目的看，网格的本质是“资源共享与协同工作”。 2 2 2 网格的特点 虽然网格系统具有分布式的一些特征，但是作为种新的计算基础设施，网 格具有一些重要的特点“，这些特点对于网格构建、网格研究和网格应用有重要 的影响。 ( 1 ) 分布性。组成网格的资源在地理位置上是分布的，这些资源可能是计 算资源、存储资源、数据资源、仪器资源等等，分布在地理位置不同的许多地方， 而不是集中在一起。在这种分布环境下，需要解决网格资源针对任务的分配和调 6 上海大学硕士学位论文 t h ep o s t g r a d u a l et h e s i so fs h a n g h a iu n i v e r s i t y 度问题、传输和通信问题，人与系统以及人与人之间的交互和协同问题，网格应 用在分布环境中自动执行和协作问题。 ( 2 ) 异构性。网格可以包含多种异构资源，包括跨越地理分布的多个管理域。 构成网格计算系统的超级计算机有多种类型，不同类型的超级计算机在体系结 构、操作系统及应用软件等多个层次上可能具有不同的结构。因此网格要具有利 用资源的异构特点进行处理的能力，同时也要具有提供一致资源管理的能力。 ( 3 ) 可扩展性。早期计算系统初期的规模较小，随着超级计算机系统的不断加 入，系统的规模随之扩大。网格可以从最初包含少数的资源发展到具有成千上万 资源的大网格。由此可能带来的一个问题是随着网格资源的增加而引起的性能下 降以及网格延迟，网格必须能适应规模的变化。 ( 4 ) 自治性。网格上的资源首先是属于某一本地的个人或者组织，网格资源 的拥有者对资源具有最高级别的管理权限，网格应该允许资源拥有者对其资源有 自主的管理能力，因此具有自治性。同时这些资源根据一定的约束和规则接受网 格的统一管理，实现资源的共享和互操作，这使得网格管理比一般的分布式系统 更为复杂，具有管理的多重性。 ( 5 ) 动态型。由于网格中的资源具有自治性，因此网格资源可能动态的加入 或者退出网格，也可能出现故障导致不能用，另外资源的性能情况也可能发生较 大的变化，使得供网格使用的资源也会发生相应的变化。由于网格没有集中控制 能力，因此对于这种动态性需要有一种机制来保障网格应用的运行不会遭受比较 大的影响。与一般的局域网系统和单机的结构不同，网格计算系统由于地域分布 和系统的复杂使其整体结构经常发生变化，网格计算系统的应用必须能适应这种 不可预测的结构。 ( 6 ) 自相似性。网格的局部和整体之间存在着一定的相似性，局部在许多地 方具有全局的某些特征，而全局的特征在局部也有一定的体现，网格的构建通过 小的局部网格可以形成更大的网格，其构成方式具有相似性。 2 2 3 网格计算 在过去的十年中，科学计算正从主机集中转移到分布方式。近年来，这一趋 势更向着网格计算“3 1 延伸。网格是以资源共享为目的，支持对可计算资源的远程 和并发的访问，用高速网络连接的地理上分布的可计算资源所组成的一个具有单 一系统映像的高性能计算和信息服务环境。若干j 下在进行的研究项目，如 g l o b u s “”f 致力于建立地理分布资源的无缝连接和主观一体化。 f ：海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v c r s i t y 网格资源主要包括计算资源、通信资源和存储资源。如何使用这些资源，高 效地完成计算任务是网格系统的研究重点之一。这里首先要明确网格的使用模 式，即用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照 某种策略把这些任务分配给合适的资源。 以完成时间为优化目标的任务一资源映射是n p 完全问题，所以需要辅助的启 发算法。一般情况下，人们总是去寻找不一定是最优，但比较可行的方法。粗略地 分，可把它们分为两大类：即静态分配策略和动态分配策略。静态分配策略是在系 统运行的初始时刻。将用户提交的任务一次性地，尽量均衡地分配给系统中各处 理机，在运行过程中，各处理机各自处理自己的任务，直到这些任务运行完，一般 不再做变更。其特点是实现简单，但效果有限，很容易造成负载不均衡。有的处理 机出现闲置，有的却一直超载。它的优点是实现简单。而动态分配策略是指在运 行过程中将任务分配给多个处理机，并对其上的任务数进行动态调整，尽可能使 系统中的各处理机上的负载达到平衡。一般也称为动态负载平衡。其优点是能充 分发挥各个处理机的功能，提高整个系统的吞吐量它的缺点是实现起来复杂程 度高，还容易给各处理器带来额外负载。 网格计算目前广泛采用的系统框架为5 层沙漏结构1 ，如图2 - l 所示。 、 、c 具与应用反朋屡 、， 目录代理。磷 懈调度与监控， 汇聚燃 i 单个资潦 l 管理 资潦艨 ，资源与暇务 ，的窭垒济问、 连接屡 计算搬、 存储介鹰、网络 匈造燃 博感器等各种资瀛接口 图2 15 层沙漏结构 最底层为构造层，基本功能是控制局部资源，提供一套对各种资源控制的工 具和接口，由运行不同操作系统、数据库管理系统或资源管理系统的p c 机、工 作站、集群或大型机组成，也可以是存储系统、网络资源或传感器等。 连接层的基本功能是实现相互通信，定义核心通信与认证协议。 资源层主要实现对单个资源的共享，监控单个资源的共享操作、审计及付费 等资源层与连接层形成了沙漏模型的瓶颈部分，因此，这部分协议集合应尽量 小，且尽量标准化。 汇聚层主要负责协调多种资源的共享，提供多个资源的联合调度和预约， 1 - _ 海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 可通过裁减满足特定用户社团、虚拟组织或应用领域的需求。 应用层向网格用户提供各种应用工具和接口。 下一代网格计算系统框架为o g s a ( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ) 。1 。 g s a 基于x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 标准，以网格技术和w e bs e r v i c e s 技术为支撑，将资源、信息和数据统一起来，利于灵活、一致、动态的共享机 制的实现，使分布式系统管理有了标准的接口和行为，支持临时服务，可形成异 构与跨地域的虚拟运行环境。 2 2 基于网格技术的分布式仿真系统的优势 网格技术所具有的资源共享、协同工作、基于统一的开放技术标准等优点， 正是一个开放、通用的先进分布仿真协同工作环境所需求的。网格的主要功能 是提供网格用户一个透明的、分布的、共享的、安全的和容错的使用环境，在 此环境中用户能够共享各种资源，网格中间件为用户屏蔽复杂的底层操作。把 网格技术有效地应用到复杂分布仿真应用系统中，可以有效地降低仿真应用系 统开发费用，缩短仿真应用系统开发时间，解决基于网络的分布仿真存在的问 题。 1 、网格采用的是统一的标准。标准化意味着网格可以使接入设备像电话一 样易用。标准化对各个仿真领域的信息进行抽象，建立仿真数据的元信息，使 所有仿真数据都采用或支持网格所支持的数据描述形式，会有效地增进数据的 互操作特性。 2 、先进分布仿真协同环境是一个仿真开发环境和仿真运行环境并重的综合 性仿真环境，利用网格技术实现开发环境所开发的各种资源的共享，利用网格 的“广域缓存”技术把用户最需要的信息放在离用户最近的服务器上，根据仿 真任务对可获取的各种资源进行动态配置，实现负载的动态平衡。提高仿真系 统的容错能力。 3 、采用网格技术超强的计算能力能提供对大规模并行仿真的支持；许多高 性能的仿真资源( 硬、软件工具、仿真器、数据库、模型库等) 可以提供更多的 用户共享与重用。 4 、提供的数据管理机制可支持文件的异地调用和仿真结果的综合分析、评 估。 9 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu 1 1 i v er s i t y 2 3 基于网格技术的层次化体系结构分析 为了适应大规模异构模型协同仿真，设计体系结构时应考虑到体系结构的 互操作性、可扩展性、层次性和兼容性。针对分布仿真协同环境的研究内容与 网格技术的特点，图2 2 是基于网格技术的先进分布仿真协同环境体系结构。 i 壁竺! 坚三圣竺兰：竺亟三三三二 一一 图图囤囤图圉， 蝴躺件 困图圈囤圈圉 隅 l o t 海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 2 4 基于网格技术的先进分布仿真协同环境 在分布式协同建模环境中，不同的分系统可能分布在不同的地域。为了进 行协同建模，需要共享资源、协调进程，进行模型交互与集成等。而且在运用 可视化技术进行产品的设计与组装时，会受到计算能力的限制。特别是当在分 布式协同建模环境中要进行零件级装配操作，对模型组件的设计涉及到组件的 几何特性时，需要从图形中抽取特征作为组件索引以及数据库分类的标准，使 得模型组件在分布式协同建模环境中注册后能被模型库管理系统索引和管理。 同时要为客户端用户提供模型查询显示的功能，根据用户提供的信息进行模式 匹配，对模型库进行基于内容的检索。在客户端用户完成模型的组装后，需要 在建模环境中进行运行验证，如果组合模型比较复杂，在客户端环境下就无法 在规定的仿真步长里完成计算。协同建模、资源共享、模型特征的抽取、模型 查询中的模式匹配过程以及建模环境中组装模型的验证都需要较大的计算量， 可以采用网格技术对计算能力的进行支撑。采用三层功能结构将网格技术、可 视化技术融合到分布式协同建模环境中。 ( 1 ) 第一层为仿真应用系统层，提供给建模人员可视化的建模图形界面， 用户以图形化方式浏览模型组件，对模型进行可视化的查询、修改与组装，并 对组装好了的模型在仿真环境中进行验证。在这里用户感觉不到网格操作的存 在，网格服务对用户而言是透明的。 ( 2 ) 第二层是基于网格的支撑环境。在这个支撑环境中封装了网格服务， 能够进行模型组件封装，网格资源与安全管理，提交模式匹配计算与仿真应用 系统模型运行任务( 图2 - 3 ) 。首先仿真应用系统向动态更新请求在线协同分配 图2 - 3 枉网格环境下仿真应用系统作业提交 器( d y n a m i c a l l y u p d a t e dr e q u e s to n l i n ec o a l l o c a t e r ，d u r o c ) 发出资源申 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 请，g r a m 向m d s 动态报告资源状况并更新m d s 中的当前可用资源情况。d u r o c 查 询m d s 后得到当前资源信息，并向g r a m 申请资源，网格服务程序执行管理 ( e x e c u t i o nm a n a g e m e n t ，e m ) 将文件( 仿真环境，程序代码与初始化数据) 传送到服务器。服务器把根据调度算法使用网格资源，调度算法根据各个的仿 真实体和网格中可用资源情况，动态地把各个仿真实体方分配给相应的网格资 源节点。网格资源节点把结果返回给服务器，保存在g a s s ( g l o b a la c c e s st o s e c o n d a r ys t o r a g e ) 中。当全部仿真实体都完成后，服务器把各个独立的仿真 实体集成起来，最后向仿真应用系统返回结果。 ( 3 ) 第三层是分布式数据库，模型字典、模型特征和性能数据的存储都放 置在数据库中，为客户端的查询和访问提供服务。 2 5 网格技术与先进分布仿真技术的互补与融合 经过几十年的发展，在不断扩大的社会需求和不断进步的信息技术的推动 下，仿真技术得到了飞速的发展，在体系结构、通信协议等方面相继制定了一 系列国际标准。如基于i e e e l 2 7 8 标准的分布交互仿真，基于i e e e l 5 1 6 标准的 高层体系结构( h l a ) o ”等。并在大规模应用系统中得到了应用和验证。 网格技术和这些先进分布仿真技术在某些方面是相互融合的，网格技术可 以在以下方面对现有先进分布仿真技术进行完善。 ( 1 ) 仿真演练的动态配置 前面已经分析过，当前所进行的分布式仿真大多是为单一仿真任务服务的， 仿真资源的分配是静态的，各仿真子任务在仿真开始前就已经和资源绑定了。 通过网格技术，以一种灵活的资源分配机制来增强仿真系统的灵活性和鲁棒性。 ( 2 ) 仿真结果的自动收集、分析与评估 仿真结束后，可以通过规范的网格提交服务，自动收集分布在异地节点上 的仿真结果，统一进行综合分析，并形成分析报告，对仿真结果进行评估。例 如，我们已经通过g a s s 服务将仿真结果在仿真结束后，自动传到仿真评估点。 2 6 面向分布式仿真环境的网格元任务模型 在网格环境下仿真应用系统作业提交的整个过程( 图2 3 ) 中任务调度算 法是提高整个系统性能的关键。良好的调度算法可以充分利用网格中可用资源 为分布式仿真应用系统服务，调度算法决定了整个网格资源的利用率，尤其是 l 海大学硕士学位论文 t h ep o s t g r a d u a t et h e s l so fs h a n g h a iu n i v e r s i t y 当仿真应用系是一个大型的并行仿真系统时，一个良好的调度算法可以在不降 低仿真精度和可信度的前提下，很好保证仿真系统中各个节点上仿真结果在时 间和空问上的一致性，从而提高仿真应用系统的真实感。为了提高算法的效率， 作者通过分析分布式仿真应用系统和网格的特点引进元任务模型如图2 - 4 所示。 根据目前网格系统的使用模式和基于网格技术的先进分布仿真协同环境体系结 构，元任务可作为网格调度的最小单位。因为在分布仿真协同环境中，可以分 图2 - 4 元任务的组成结构 解为许多互不相关的仿真实体，每个仿真实体都得通过按顺序读取数据、获得 实体的模型、进行计算、显示模型和数据的传输等等，在完成每个实体的过程 中对计算资源，存储资源，网络资源，工具资源和模型资源的使用是有一定的 依赖关系的。元任务的结构如图2 - 4 所示，元任务由若干个任务组成，每个任 务又分成存储子任务、传输子任务、计算子任务和建模子任务等子任务。一个 任务内部的各个子任务之间存在数据依赖关系，但各个任务之间不存在相互依 赖关系。基于元任务模型的调度算法关键是选择最适合的任务，选择最适合的 任务运行可以很好的利用网格资源，提高资源的利用率和网格系统吞吐率，使 元任务的完成时间尽可能短，同时保证仿真应用系统的真实感。 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 第三章调度算法综述 3 1 静态调度算法 3 1 1 静态最优解算法 静态算法中的最优解算法有四种：图论法、数学法、解空间计数搜索法和 队列法。其中图论法是有代表意义的。以下简单说明图论法的常用算法。在图 论法中，两种模型分别用来表示系统和任务，即系统图和任务图，见图3 1 。 系统图中的结点表示处理机，结点旁的数字表示其计算能力，结点间的连 线表示网络的物理连接。我们可以看到，系统图所表示的是一种简化的异构系 统模型。它可以提供影响系统性能的主要参数信息。任务图中的结点表示任务， 横线上的数字为任务编号，横线下的数字表示任务粒度。连线表示执行时的偏 序关系( 即a b 表示a 执行后b 才可执行) ，连线上的数字表示通讯量。 系统图任务图 圈3 - - 1 系统图与任务图 o a n t t 表格可以用来表示任务在处理机上的分配与运行。图3 2 是一个 g a n t t 示例图。其中并行任务t l 、t 4 和t 2 、t 3 分别在处理器p l 和p 2 上执行。 图中空白部分表示c p u 空闲时间。这种空闲可能是任务问的通信或同步造成的。 处理罂 p l p 2 圈3 2g a n t t 示例图 时闯 调度问题是n p - - c o m p l e t e 问题。要想使任务的完成时间最短，任务在处理 机上的分配算法是指数复杂度型。当忽略通信开销时，只有满足以下三个条件 r 海大学硕 学位论文 t h ep o s 培r a d u a t et h e s i so fs h a n g h a iu n i v g r s i t y 中的一个，才可得到多项式时间复杂度算法： ( 1 ) 树型任务图； ( 2 ) 只有两个处理机； ( 3 ) 间隔顺序任务图。 从以上介绍可以看出，最优算法实际上只能解决几类特殊情况的问题，因 此，其用途主要是作为理论工具，而很少能用于实际系统。 3 1 2 静态次优解算法 静态启发式方法 这类方法可以快速、有效地得到次优调度。针对预先知道的信息( 包括任 务粒度，任务间通讯量，任务执行偏序关系以及系统限制) ，采用非解析的、近 似的、逐步逼近的试探方法寻找近似最优解，是此类方法的共同特点。w u 和 s w e e t i n g 提出的静态启发式任务分配算法3 ，比较有代表性，适用于大粒度并 行任务和基于消息传递的系统。 - 静态遗传算法 遗传算法的基本过程是。“： ( 1 ) 初始化：将问题的解定义为基因串，随机产生第一代基因。 ( 2 ) 计算适应函数值。 ( 3 ) 遗传操作：根据适应函数值使用遗传算子产生下一代基因。 ( 4 ) 重复( 2 ) 和( 3 ) 直到算法收敛。 总的来看，虽然静态调度算法没有考虑系统的不可确定因素，但由于在编 译时可以完成调度，对于大型应用程序的性能提高起着重要作用。在实际应用 中，如果能与动态算法结合使用，则可能取得更好的效果。 3 2 动态调度算法 3 2 1 集中式控制与分布式控制算法 集中式控制算法”1 控制一般通过m a s t e r s l a v e 的方式来实现，最典型的 上海大学硕士学位论文 t h ep os t gr a d u a t et h c s i so fs h a n g h a iu n i v e r s i t y 是任务池( p o o lo ft a s k s ) 方法由m a s t e r 创建和维护任务池( 一般组织成队 列形式) ，并向空闲的s l a v e 处理机分派任务。如果每个任务粒度不同，则粒度 较大的任务一般处于队列头部。m a s t e r 以贪心分配的原则管理各s l a v e 。p v m 环境下的应用程序很多采用此类负载平衡方法是换维平衡法，该方法是种全 局控制的、完全同步的策略。它首先将n 个处理机组织成m 维，然后每次在某 一维的处理机集合中进行负载平衡。通过更换不同的维的处理机集合，利用维 与维之间处理机的重叠特性，达到全局负载平衡的效果。集中式控制算法在并 行处理系统规模较大时可能会出现瓶颈现象。 3 2 2 分层负载平衡方法 分层负载平衡方法是一种异步控制的、全局性的方法。它将系统组织成一 个层次式的控制结构，负载平衡由最底层的处理机发起，逐渐向高层传递。每 一层的负载实行集中控制，最高层控制全局的负载平衡。 3 2 3 梯度模型 梯度模型。7 1 的基本思想是首先由轻载处理机向其它处理机报告它们的负载 状态，重载处理机根据系统维护的负载梯度表。向离它最近的轻载处理机派送 部分负载。 3 3 常用的任务调度算法 目前，在任务调度中常用的调度算法由以下几种： ( 1 ) 先进先出算法( f i r s ti nf i r s to u t ) f i f o 调度算法是一种基本的调度方式，严格的f i f o 完全以任务进入队列 的时间为顺序，实行“先到先服务”的策略，只要先到的任务得不到运行或没 有完成，后面的作业也不能运行。也可以不按严格的先进先出的顺序运行任务， 而是按一定的原则搜索可运行的任务。如图3 3 所示，具有优先级的5 个作业 a e ，f i f o 调度在优先级队列中从前到后进行搜索以找出一个后若干具有最高 优先级的任务运行。选出来运行的这个任务这时可以一直运行到退出为止。从 + 三三哑围船e 丑 图3 3 先讲先m 上海大学硕士学位论文 t h ep os t g r a d u a t et h e s i so fs h a n g h a iu n i