（计算机软件与理论专业论文）基于桌面网格的自调度算法的研究及应用.pdf

基于桌面网格的自调度算法的研究及应用中文摘要 基于桌面网格的自调度算法的研究及应用 中文摘要 桌面网格是一种由桌面p c 机组成的网格，具有结构更复杂、动态性更强等特点。 充分利用桌面网格的空闲计算能力可以为大规模计算提供一种廉价和便捷的解决方 案，其关键是如何把任务均衡地分配到各个节点上运行。而自调度技术则是解决这个 问题的关键技术之一。 自调度是一种动态、自适应的应用层分布式计算的调度模式，它把一个任务分解 成多个子任务，然后把每个子任务分配到各个计算节点上并行运行。本文根据桌面网 格动态性强、计算能力不稳定的特点，主要研究了如何利用和优化自调度技术，把任 务合理地分配到各个计算节点上均衡运行，最终获得较优的并行性能。 本文首先分析比较了现有自调度算法，指出现有算法应用在桌面网格环境中存在 的问题。其次，把自调度技术引入桌面网格，并根据生产者一消费者原理实现数据传 输和执行的并行，从而减少了计算节点的空等时间。然后，由于现有算法没有有效的 考虑计算节点的性能并要确定一些参数，而桌面网格具有更强的动态性和异构性导致 参数值难以确定，因此本文提出基于分块的混合型自调度算法c h s s ( c h u n kh y b r i d s e l f - s c h e d u l i n g ) ，该算法在整个调度过程中都根据计算节点的性能进行任务的动态分 配，大大缩短了任务的完成时间。最后，引入预测机制，提出一种基于分块的任务执 行时间的预测算法c t r p ( c h u n k b a s e dt a s kr u n t i m ep r e d i c t i o n ) ，该算法能精确地预测 计算节点上任务的执行时间，解决了执行过程中计算节点负载变化所导致的负载不平 衡问题。 本文在中文信息处理网格平台上进行了测试，结果表明，本文提出的c h s s 算法 和c t r p 算法在桌面网格环境中均能取得比现有算法更佳的性能。 关键词：桌面网格，自调度，负载平衡，预测，分块 作者：吉勤 指导老师：朱巧明 垒! ! 壁壁一一t h e r e s e a r c ha n da p p l i c a t i o no fs e l b s c h e d u l i n ga l g o r i t h m so nd e s kg r i de n v i r o n m e n t t h er e s e a r c ha n d a p p l i c a t i o no fs e l f _ s c h e d u l i n g a l g o r i t h m so nd e s kg r i de n v i r o n m e n t a b s t r a c t d e s kg r i di sm a i n l yc o m p o s e do fp e r s o n a lc o m p u t e r sa n di t sm o r ec o m p l e xa n d d y n a m i ct h a no t h e r s u s i n gv a c a n tc o m p u t a t i o na b i l i t i e si nd e s kg r i dc a np r o v i d ea n i n e x p e n s i v ea n dc o n v e n i e n ts o l u t i o nt os o l v el a r g es c a l ec o m p u t a t i o n a lp r o b l e m s ，s ot h a t h o wt oa l l o c a t et a s k st ot h e s en o d e sa n da c h i e v eb e t t e rl o a db a l a n c i n gi sa ni s s u ei nt h a t f i e l d s e l f - s c h e d u l i n gi so n eo fa c c e p t e ds o l u t i o n s s e l f - s c h e d u l i n gi sad y n a m i c ，a d a p t i v ea n dd i s t r i b u t e ds c h e d u l i n gm e t h o dw h i c h w o r k so na p p l i c a t i o nl a y e r i td i v i d e sat a s ki n t oas e to fs u b t a s k s ，a n dt h e na s s i g n st h e mt o c o m p u t i n gn o d e s t oe x e c u t ep a r a l l e l t h i sd i s s e r t a t i o nf o c u s e so nh o wt ou s ea n do p t i m i z e s e l f - s c h e d u l i n gt e c h n o l o g yt oa l l o c a t et a s k sr e a s o n a b l ea n da c h i e v eb e t t e rp a r a l l e l p e r f o r m a n c e f i r s t l y , t h i sd i s s e r t a t i o na n a l y z e sa n dc o m p a r e se x i s t i n gs e l f - s c h e d u l i n ga l g o r i t h m s ， a n dt h e np o i n t so u tt h e d i s a d v a n t a g e sw h e nu s i n gt h e s ea l g o r i t h m s i nd e s kg r i d e n v i r o n m e n t s s e c o n d l y , i ti n t r o d u c e sh o w t ou s es e l f - s c h e d u l i n gi nd e s k 鲥da n dp a r a l l e l d a t at r a n s f e ra n de x e c u t i o nb yu s i n gt h ep r o d u c e r - c o n s u m e rm o d e l t h a ta p p r o a c hc a n r e d u c et h ew a i t i n gt i m eo fe a c he x e c u t i o nn o d er a p i d l y t h i r d l y , a l m o s ta l l e x i s t i n g s e l f - s c h e d u l i n ga l g o r i t h m sd on o tc o n s i d e rt h en o d e s p e r f o r m a n c ee f f i c i e n t l ya n dn e e d s o m em a n u a lw o r kt od e c i d et h ev a l u eo fe a c hp a r a m e t e r u n f o r t u n a t e l yi ti sr e a l l yh a r d b e c a u s ee n v i r o n m e n to fd e s kg r i di sd y n a m i ca n dh e t e r o g e n e o u s s oi tp r o p o s e san o v e l c h u n kh y b r i ds e l f - s c h e d u l i n g ( c h s s ) a l g o r i t h mw h i c hd e t e r m i n e st h ev a l u eo fc h u n k a r t i f i c i a l l ya n da l l o c a t e st a s k sa c c o r d i n gt on o d e sp e r f o r m a n c ed y n a m i c a l l y l a s t l y , i t i n t r o d u c e st h ep r e d i c t i o na l g o r i t h m sa n dp r o p o s e san e wc h u n k b a s e dt a s kr u n t i m e p r e d i c t i o n ( c t r p ) a l g o r i t h ma c c o r d i n gt ot h ec h a r a c t e r so fs e l f 二s c h e d u l i n ga n dt h ed e f e c t s o fe x i s t i n ga l g o r i t h m s t h a ta l g o r i t h mc a np r e d i c tm o r ea c c u r a t e e x e c u t i n gt i m ea n d a c h i e v eb e t t e rl o a db a l a n c i n gt h a nt h a to fo t h e ro n e sw h e nm o s tn o d e s l o a di sc h a n g i n g h t h er e s e a r c ha n d a p p l i c a t i o no fs e l f - s c h e d u l i n ga l g o r i t h m so nd e s kg r i de n v i r o n m e n t a b s t r a c t f r e q u e n t l ya n dr u l e l e s s l y t h i sd i s s e r t a t i o nt a k e sc h i n e s ei n f o r m a t i o np r o c e s s i n gg r i da l st e s t b e d t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tc h s sa l g o r i t h ma n dc t r pa l g o r i t h mc a na c h i e v eb e t t e r p e r f o r m a n c e k e y w o r d s ：d e s k g r i d ，s e l f - s c h e d u l i n g ，l o a db a l a n c i n g ，p r e d i c t i o n ，c h u n k i i i w r i t t e nb yj iq i n s u p e r v i s e db yz h uq i a o m i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集 体已经发表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均己 在艾中以明确方式标明。本人承担本声明的法律责任。 研究生签名： 盔勃 日期： 皇鲤2 ：主 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、 中国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅 和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括 刊登) 授权苏州大学学位办办理。 研究生签名：盔蔓左日 期。 导师签名：三触期：卅 基于桌面网格的自调度算法的研究及应用 第l 章绪论 1 1 选题背景和意义 第l 章绪论 随着互联网技术的迅速发展，在网络上聚集了大量空闲的计算资源、存储资源和 信息资源，这些资源的闲置使得大范围地理分布的异构计算机系统和资源整合在一 起，形成一个大规模的计算平台成为日益迫切的要求。因此，网格( g r i d ) i m l 应运而生。 网格的概念最早于9 0 年代中期提出，用于表述在高端科学和工程分布式计算中 的一种基础构造形式。美国的资深科学家i a nf o s t e r 将网格描述为：网格是构筑在互 联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器和远 程设备等融为一体，为科技人员和普通用户提供更多的资源、功能和交互性。由于网 格能提供如此强大的功能，目前，包括中国在内，全世界很多国家都对网格投入巨大 的人力物力，产生了很多具有里程碑意义的研究成果。在网格的诸多研究方向之中， 对调度问题的研究无疑是最重要、最有挑战性的方向之一。 桌面网格是网格的一种，其中的计算资源主要是由一台台的桌面p c 机所组成， 这些资源是异构的，有自己的存储资源和软件资源。桌面网格的调度问题是根据各节 点的资源状态，把任务以合理的方式分配到相应的节点去执行。为了发挥出各节点的 潜在计算能力，一个主要的问题就是怎样把任务分配给各节点以使各节点的负载达到 平衡并使总的完成时间最小。 循环是科学计算领域中一个常见的、需要花费大量资源的问题【3 1 ，因此比较适合 于在网格环境下进行并行计算。如果一个循环的各次迭代之间没有任何关系，各次迭 代就可以看作是一个任务并可被独立的调度。传统模式上对这种并行循环的调度分为 静态调度和动态调度1 4 两种。静态调度是指在编译时进行任务的分配，因而在程序执 行前任务的大小已经是确定的，如o p e n m p 、m p i 等。当循环的各次迭代拥有相等的 工作量时静态调度可以发挥较高的性能，但是在处理以下几种情况时就会显示出不 足： ( 1 ) 循环的模式是不规则的； ( 2 ) 循环的工作量在编译时是不可知的； ( 3 ) 系统是异构的。 第1 章绪论基于桌面网格的自调度算法的研究及应用 动态调度则是为了解决以上问题而提出来的一种可在执行时调整具体任务的调 度方式。动态调度可以实现不同节点间的负载平衡，因此适合于迭代次数不定以及每 次迭代都花费不同时间的情况。 自- n 3 芝( s e l f - s c h e d u l i n g ) i s l 是一种动态、自适应的调度模式，比较适合于并行循环 的调度。它是一种在应用层的调度技术，指一个任务可以分解成多个子任务，然后每 个子任务分配到各个节点并行执行，从而减少完成时间的技术。在自调度中，各个执 行服务的节点根据自己的资源状况主动向调度节点索取任务，而不是被动地等待调度 节点分配任务。在有独立循环的计算中，如矩阵相乘、图像渲染等，自调度都取得了 比较理想的效果。而在桌面网格环境下，由于其系统的异构性和动态性，使得在这之 上的自调度变得复杂。总体来说，具有以下特点： ( 1 ) 自调度是基于异构环境的。由于桌面网格系统是由分布在网络上的各种p c 机组成，这些资源的结构、速度或操作系统是异构的，因此桌面网格环境下的自调度 必须面向异构环境； ( 2 ) 自调度不干涉网格节点内部的调度。自调度只是负责把任务以合理的方式、 合理的大小分配给网格节点执行，至于网格节点何时调度该任务及使用何种方式来调 度是由节点内部调度策略决定的； ( 3 ) 自调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总是不 停的改变：有新资源加入、有资源出现故障等，因此自调度必须适应网格的这种动态 性； ( 4 ) 自调度必须具有通用性。提交给网格的作业依据占用c p u 的时间及数据量的 大小可以分为计算密集型、数据密集型、计算和数据均密集型三种，因此桌面网格环 境下的自调度必须能满足这三种应用的要求。 桌面网格环境下自调度的目标就是以最优的方式分割任务，在最短的时间里完成 用户的请求。具体的目标包括负载平衡、完成时间短等。 ( 1 ) 完成时间短。完成时间指用户把任务提交给网格到网格把最终结果返回给用 户的这段时间。这是调度领域里一个最常见、虽普遍的目标，完成时间越短，说明调 度算法越好，用户的满意度也越高； ( 2 ) 负载平衡。由于桌面网格环境是异构的，各节点的性能不同，因此分配任务 时避免给一个性能比较差、负载比较重的节点分配过多的任务，否则会严重影响任务 2 基于桌面网格的自调度算法的研究及应用 第1 章绪论 总体的完成时间。 1 2 研究现状 早期的自调度算法都是基于集群系统的。文献 6 】中介绍的p s s ( p u r e s e l f - s c h e d u l i n g ) 算法每次分配一个单位的工作量给计算节点，而c s s ( c h u n k s e l f - s c h e d u l i n g ) 算法每次分配k 个单位的工作量给计算节点，这两种算法在整个程序 的执行过程中每次分配的任务量都是不变的。文献【3 】中的g s s ( g u i d e ds e l f - s c h e d u l i n g ) 算法、文献【7 】中的f s s ( f a c t o r i n gs e l f - s c h e d u l i n g ) 算法和文献【8 】中的t s s ( t r a p e z o i d s e l f - s c h e d u l i n g ) 算法是对c s s 和p s s 算法的改进，提出按照一定的规则进行任务量 的分配，这样每次分配的任务量都不同，减少了调度节点和计算节点间的通信。这些 算法虽然在集群上能取得好的性能，但是应用到桌面网格环境中还存在一些问题，譬 如：没有考虑计算节点的性能、负载不平衡等。因此，在这些研究的基础上，又提出 了一些网格环境中适用的自调度算法。 文献【9 】中的口s s ( as e l f s c h e d u l i n g ) 算法提出把调度分为两个阶段，第一阶段根 据计算节点的时钟速度分配，第二阶段使用c s s 和f s s 等算法分配。文献 1 0 】中的 e p l s s ( e f f i c i e mp a r a l l e ll o o ps e l f - s c h e d u l i n g ) 算法首先判断系统是异构还是同构，设 定不同的口值，然后按照口s s 算法分配任务。文献【1 1 】中的p p l s s ( p e r f o r m a n c e b a s e d p a r a l l e ll o o ps e l f - s c h e d u l i n g ) 算法首先在各计算节点上运行一个小程序，收集它们的 执行时间信息，根据公式计算出节点的性能值，第一阶段按照性能值进行任务的分配， 第二阶段使用c s s 和f s s 等算法分配。文献 1 2 】中的h p l s ( h y b r i dp a r a l l e ll o o p s c h e d u l i n g ) 算法在p p l s s 算法的计算性能值的基础上加了带宽的影响，其他的步骤 同p p l s s 算法。文献 1 3 】中提出的算法继p p l s s 和h p l s 算法之后在计算性能值时 加入了基于知识的工作量预测，使性能值更精确。文献 1 4 中的h s s ( h i s t o r y a w a r e s e l f - s c h e d u l i n g ) 算法提出把任务的分配分为两个步骤，第一步根据已有的算法计算块 大小，第二步根据每个节点上的历史执行情况来调整已分配的块大小，这样可以取得 比较好的负载平衡。文献 1 5 中的p s s ( p r o b a b l i s t i cs e l f - s c h e d u l i n g ) 算法针对网格动态 性的特点，提出在执行过程中动态的根据处理器数目的变化来分配任务。 通过分析可以看出，现有的自调度算法存在如下的一些问题： ( 1 ) 仅仅考虑任务的执行时间，忽略了任务的传输时间。由于自调度中是让计算 3 第l 章绪论基于桌面网格的自调度算法的研究及应用 节点主动的索取任务，执行模式为：请求任务一接收数据一执行一返回结果、请求下 次任务一等待一下次任务到达，但是数据的传输以及调度节点的处理都需要时间，因 此导致了计算节点在每个循环中都有空闲等待时间的存在； ( 2 ) 现有的自调度算法大多不能有效的考虑节点的性能。基于集群的自调度算法 没有考虑节点的性能差异，而异构系统上的自调度算法把任务的执行分为两个阶段， 按性能值分配任务只是在第一阶段，第二阶段依然没有考虑节点的性能，并且最优的 口值也很难确定； ( 3 ) 忽略了执行过程中节点负载的变化。桌面网格环境是动态的，不断有用户提 交任务，同时不断有用户的任务被完成，因此各节点的负载是不稳定的。如果不考虑 这种负载变化将会导致各节点负载的不平衡。 1 3 研究内容 本文针对上述问题，对网格环境下自调度算法做了详细和深入的探讨研究，提出 了自调度用在桌面网格环境中的一些改进的想法，主要目标是在动态的桌面网格环境 中，以最短的时间完成用户的任务并使计算节点的负载达到平衡。 本课题是在已有的中文信息处理网格平台z h h z g r i d r l 6 - 1 8 上进行研究的，该网格 专门为各类用户提供语言文字信息处理的基础服务，如分词服务、词性标注服务和实 体识别服务等。z h h z g r i d 除了具有一般服务网格的动态性、不确定性和面向服务等 特征外，还带有语言文字信息处理的特殊性，即以数据处理为主，并且其数据量大， 执行时间长。该网格的一个基本任务就是根据各个节点的资源状态，把任务以合理的 方式分配到相应的节点去完成，使它们的负载达到平衡，并使总的执行时间能趋近最 小，从而缩短任务的完成时间。 本文在研究过程中所做的工作包括： ( 1 ) 针对桌面网格中各计算节点在执行过程中由于任务的传输导致存在空闲等 待时间的问题，采用多线程机制并根据生产者一消费者原理保证各线程独立、正确地 工作，使数据的传输和执行并行，减少了计算节点的空等时间； ( 2 ) 结合c s s 和h p l s 两种算法，提出一种新的自调度算法，不用对调度的整个 过程分阶段，而是自始自终都根据计算节点的性能进行任务的分配，这种算法更加适 合桌面网格异构性的特点； 4 基于桌面网格的自调度算法的研究及应用第1 章绪论 ( 3 ) 针对执行过程中计算节点负载变化导致负载不平衡的问题提出引入预测机 制，并根据自调度的特点以及现有预测算法的不足，提出一种新的任务执行时间的预 测算法，该算法能精确地预测计算节点上任务的执行时间，使其负载趋向平衡。 1 4 论文的组织结构 本文以介绍桌面网格技术和网格自调度技术为起点，按照从理论到设想再到实验 验证的路线，根据桌面网格环境下自调度存在的不足，提出自己的设想，并在实际的 环境中进行验证，再把现有的算法同本文提出的算法进行比较，分析实验结果，验证 了算法的有效性。按照研究工作完成的顺序，本文的组织结构和章节安排如下： 第一章为绪论，介绍选题的背景、意义、研究现状和研究内容。 第二章为相关技术及研究基础，介绍了桌面网格技术和z h h z g r i d 的平台结构， 详细阐述了网格服务的包装、部署和访问，分析比较了已有的自调度算法，指出其应 用在桌面网格环境中存在的问题。 第三章为面向桌面网格的自调度算法的并行化，介绍了自调度算法在z h h z g r i d 中的实现，根据存在的问题，提出使用多线程机制以及生产者一消费者原理来对其并 行化，给出了相关的实验和结果。 第四章为基于分块的混合型自调度算法，详细介绍了算法的提出和描述，并在计 算密集型和数据、计算均密集型这两种类型的应用上进行验证，给出实验结果，进行 分析。 第五章为基于分块的任务执行时间的预测算法，介绍了现有的各种预测算法，针 对其不足和桌面网格环境的特点提出新的预测算法，详细描述了该算法以及最优预测 块大小的确定，给出了实验结果和分析。最后设计了综合实验，对本文提出的各种算 法进行比较以验证其有效性。 第六章为总结和展望，对本课题的研究成果进行了总结，指出了研究过程中存在 的不足和有待完善的方向。 第2 章相关技术及研究基础基于桌面网格的自调度算法的研究及应用 第2 章相关技术及研究基础 作为新一代网络计算与应用技术，网格的本质不是它的规模，而是充分利用网络 中现有的软硬件资源。它的目标是将地理上分布的、系统上异构的多种计算资源通过 高速网络连接起来，协同解决大型应用问题，进行网络上信息资源的共享，最终把整 个i n t e r n e t 整合成一台超级虚拟计算机。正因为网格提供了强大的计算能力，因此如 何对任务进行合理的调度是网格要解决的关键问题之一。自调度是一种应用层的调度 模式，比较适合于网格环境中可并行执行的任务的调度。本章着重介绍了自调度的相 关技术及网格服务技术，指出自调度应用在桌面网格环境中存在的问题。 2 1 桌面网格技术 网格是一个集成的计算与资源环境，或者说是一个计算资源池，它能够充分吸纳 各种计算资源，并将它们转化成一种随处可得的、可靠的和标准的计算能力。除了各 种类型的计算机，这里的计算资源还包括网络通信能力、数据资源等。桌面网格是网 格的一种，其计算资源主要是由桌面p c 机组成，它具有如下特点： ( 1 ) 资源具有分布性 桌面网格资源通常是跨管理域的资源，这些资源属于不同的组织，他们之间有些 建立了信任关系，有些没有，管理没有信任的桌面网格资源面临重大挑战。通过身份 认证等安全技术可以防止非法用户通过网络使用或获取网格的任何资源，保障数据的 安全性。 ( 2 ) 资源具有异构性 分布在广域网的不同管理域的资源具有异构性。桌面网格资源的异构性主要表现 在：每个系统可能有不同的处理器、不同的数据表示、不同的内存容量、不同的操作 系统以及不同的通信带宽等。通过将异构资源映射成统一管理的逻辑资源，实现资源 的动态收集、处理与调度是桌面网格资源管理系统的关键。 ( 3 ) 资源具有动态性 桌面网格的动态性包括资源的动态增加和动态减少。对于桌面网格资源动态减少 或者网格出现故障的情况，要求能及时实现作业的自动迁移，做到对高层用户透明或 6 基于桌面网格的自调度算法的研究及应用第2 章相关技术及研究基础 者尽量减少用户的损失。桌面网格资源的动态增加需要提高网格的扩展性，网格的扩 展性要求体现在规模、能力和兼容性几个方面。网格资源是异构的，在桌面网格环境 中可以有不同体系结构的计算机系统，因此网格系统必须能够解决这些不同资源之间 的通信和互操作问题。 ( 4 ) 自治性与管理的多重性 桌面网格资源的拥有者对该资源拥有最高级别的管理权限，网格应该允许资源拥 有者对他的资源有自主管理的能力，这称为自治性。但是桌面网格资源也必须接受网 格的统一管理，否则无法实现共享和互操作，因此桌面网格的管理具有多重性。 2 2 面向服务的中文信息处理网格平台 中文信息处理网格平台z h h z g r i d 是面向服务的平台，其中的各种应用都被包装 成服务，对外提供统一的接口供用户使用。 2 2 1 网格服务的概念 网格服务是在开放网格服务结构o g s 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 ) 1 9 - 2 0 1 中被 定义的。o g s a 是全球网格论坛g l o b a lg r i df o r u m 在计算网格五层沙漏结构的基 础上，结合w e b 服务技术提出来的，是目前最新的一种网格体系结构【2 2 1 。如果说五 层沙漏结构是以协议为中心的“协议结构 ，则o g s a 就是以服务为中心的“服务结 构 ，这里的服务是指具有特定功能的网络化实体，包括各种计算资源、存储资源和 程序等等，简而言之，一切都是服务。 网格服务是一种w 曲s e r v i c e l 2 3 1 ，它提供了一组接口，这些接口的定义明确并且 遵守特定的惯例，解决服务发现、动态服务创建和生命周期管理等问题。在o g s a 中，一切都看作网格服务，因此网格就是可扩展的网格服务的集合。图2 1 是对网格 服务的简单描述。 以网格服务为中心的模型具有如下好处【2 4 】： ( 1 ) 由于网格环境所有的组件都是虚拟的，因此，通过提供一组相对统一的核心 接口，所有的网格服务都基于这些接口实现，就可以很容易地构造出具有层次结构的、 更高级别的服务，这些服务可以跨越不同的抽象层次，以一种统一的方式来看待； ( 2 ) 虚拟化也可使得将多个逻辑资源实例映射到相同的物理资源上成为可能，在 7 第2 章相关技术及研究基础基于桌面网格的自调度算法的研究及应用 对服务进行组合时不必考虑具体的实现，可以以底层资源组成为基础，在虚拟组织中 进行资源管理。 服务数据访问 显式撤销 软状态生命周期 绑定属性 一可靠激活 一认证 g r i d s e r v i c e ( 必须的) 其他接口 ( 可选的) 2 2 2 网格服务的包装和部署 图2 1 网格服务示意图 标准接口： 一通知 一授权 一服务创建 一服务注册 一管理 一开发 应用相关接口 以j a v a 语言为例，网格服务的包装和部署流程如图2 2 所示。 i t n w t e s 妇d l e 一- n t j e a 触v a 卜 m p - 。n h 舳th 州叫 图2 2 网格服务包装和部署流程 以分词服务s e g s e r v i c e 为例，分词源程序使用的是斯坦福大学的 s t a n f o r d c h i n e s e s e g m e n t e r ，下面是包装的详细步骤： ( 1 ) 更新w s d l 文件。修改生成的s e g w s d l 文件，定义三处相关内容：第一是 服务可以接收的输入参数和返回值类型。分词服务接收的输入参数是要分词的文本， 而输出是分好词的文本，因此都可以定义为s t r i n g 类型：第二是消息；第三是接口。 代码如下： ! 一定义参数类銎- x s d ：e l e m e n tn a m e = a r g o ”t y p e = t x s d s t r i n g 泠 8 基于桌面网格的自调度算法的研究及应用第2 章相关技术及研究基础 p a r tn a m e = ? p a r a m e t e r s 。e l e m e n t = 、 t n s ：s e g “b ! 一定义输入消。g - p a r tn a m e = l p a r a m e t e r s 。e l e m e n t = t t n s ：s e g r e s p o n s e ”b ! - - s e g 为接口名称。 o u t p u tm e s s a g e = t n s ：s e g o u t p u t m e s s a g e 惨 ( 2 ) j a v a 代码实现。修改生成的s e g s e r v i c e j a v a 文件，按照分词的相关实现添加 代码。 ( 3 ) 编译。选用的是a n t 作为编译工具，首先修改b u i l d x m l 文件，增加生成的 g a r 文件的名称和一些相关信息，代码如下： ! 增加b u i m 文件夹及子文件夹所在位置o 9 第2 章相关技术及研究基础基于桌面网格的自调度算法的研究及应用 p r o p e r t yn a m e = b u i l d d i r ”l o c a t i o n = s e g s e r v i c e b u i l d 恰 p r o p e r t yn a m e = b u i l d d e s t l o c a t i o n = s e g s e r v i c e b u i l d c l a s s e s 惨 p r o p e r t y ? l a m e = b u i l d 1 i b d i r ”l o c a t i o n = s e g s e r v i c e b u i l d l i b 恰 p r o p e r t yn a m e = s t u b s d i r ”l o c a t i o n = s e g s e r v i c e b u i l d s t u b s 恰 p r o p e r t y 刀绷p = s t u b s s r c l o c a t i o n = s e g s e r v i c e b u i l d s t u b s s r c7 修 p r o p e r t yn a m e = s t u b s d e s t ”l o c a t i o n = s e g s e r v i c e b u i l d s t u b s c l a s s e s 诊 p r o p e r t yn a m e = e t c d i r ”v a l u e = s e g s e r v i c e e t c 诊 p r o p e r t yn a m e = s c h e m a 1 0 c a l ”l o c a t i o n = s e g s e r v i c e s c h e m a 惨 p r o p e r t yn a m e = s c h e m a p a t h ”v a l u e = g t 4 i d e s e g s e r v i c e 侈 ! 一增加弧讲文件夹相关信息关系飘3 钳是否正确生国乞- 1公式( 2 2 ) 在执行过程中k 固定不变，一般由事先指定。该算法主要的缺点是算法的有效性取决 于k 值的设定，当k 值太大时会导致负载的不平衡，太小又会导致过多次的数据传输 和调度。 1 4 基于桌面网格的自调度算法的研究及应用第2 章相关技术及研究基础 g u i d e ds e l f s c h e d u l i n g ( g s s ) 【3 3 0 。3 1 】：块大小的计算公式为： g = - 尼咖 公式( 2 3 ) g s s 算法这种块的大小越来越小的特性可以取得负载平衡和减少调度次数。而且，在 并行循环执行开始的时候分配比较大的块可以减少主节点和子节点之间的信息交流。 该算法主要的缺点是在最后的步骤里分配了很多比较小的块。 f a c t o r i n gs e l f - s c h e d u l i n g ( f s s ) 【7 , 3 0 - 3 1 ：块大小的计算公式为： c j = i 尼一1 ( a p ) i 公式( 2 4 ) 参数口是由计算得出或者通常选口= 2 。f s s 算法提出了分阶段分配的思想，在每一阶 段每个处理器所分配的任务量相等。该算法主要的缺点是很难确定最优的口值。 t r a p e z o i ds e l f - s c h e d u l i n g ( t s s ) 【8 , 3 0 - 3 1 】：块大小的计算公式为： c j = g 一1 一d ，d = l ( ，一三) ( n 1 ) l 公式( 2 5 ) 这里第一块大小，和最后一块大小可以由用户输入或者f = li 2 pi ，l = i 。该算法 主要的缺点是依然会发生很多的同步需求。 拿矩阵相乘来说，假设求：c = a 怊，a ，b 分别为1 0 0 0 1 0 0 0 的矩阵，循环如下： ，研( t = o ：i 10 0 0 ：i + + ) 如r o = o ：j ( 1 0 0 0 j + + ) 加r ( k = o ；k l o o o ；k + + ) c l i 】d 】+ = a i l l v b ( ；1 ： 这里，矩阵a 的每一行都要与b 的每一列相乘，得出c 的一行，因此，a 的行 与行之间是没有任何关系的，一行可以看作是一次迭代，可以使用自调度算法对矩阵 彳进行分配。彳有1 0 0 0 行，所以设总工作量i = 1 0 0 0 ，假设处理器的个数为一，则 按照p s s 、c s s 和g s s 等算法每次分配的块大小如表2 1 ，单位：行。 表2 1 工作量分配表 燃溅壤溪震：篓霪嚣，抉天擎震黧篡鬟纛缴i 震雾戮覆黧篓篡鬻麓囊耋：瀚 p s s11111 c s skkkkk g s s2 5 018 81 4 11 0 67 95 94 53 32 51 9 1 4ll864332l 1l 1 1 2 51 2 51 2 51 2 56 26 26 26 23 23 23 23 21 61 61 61 68888 f s s 444422221 l 1 1 t s s 1 2 51 1 71 0 91 0 l9 38 57 76 96 15 34 53 72 92 1 1 35 第2 章相关技术及研究基础基于桌面网格的自调度算法的研究及应用 ( 2 ) 异构系统上的自调度算法 以上所提出的几种算法虽说是自调度领域的经典算法，但是这些算法都是根据一 些简单的公式来分配任务，没有考虑到很多影响因素，它们存在以下的问题： 1 ) 分配任务时没有考虑到子节点的性能，譬如c p u 的速度、c p u 的负载等； 2 ) 这些算法都是在集群上提出的，如果应用到网格中，还必须考虑到网络带宽 的影响； 为了解决以上的问题，又提出了以下一些改进的自调度算法： 口s e l f - s c h e d u l i n g ( as s ) t 9 】：这个算法把调度分成两个阶段：第一阶段，把口的 工作量根据它们的c p u 时钟速度分配给各子节点；第二阶段，把剩下的( 1 0 0 口) 的 工作量依据c s s 、g s s 和t s s 等算法进行分配，这在一定程度上完成了从同构到异 构系统的算法的改进。主要缺点是口值是事先确定的并且在运行过程中一直不变，而 且如果系统的体系结构发生变化，以前设定的口值将可能不会满足新的结构的需求。 e f f i c i e n tp a r a l l e ll o o ps e l f - s c h e d u l i n g ( e p l s s ) 【1 0 】：这个算法与口s s 算法的不同在 于可动态确定、调整口值。首先收集各子节点的c p u 时钟速度，假设性能最好的为 最差的，倍，则算出h e t e r o g e n e o u sr a t i o ( h r ) - h r = 专 旦1 0 0 公式( 2 6 ) ，” 其中口，为口的临时值，如果口i h r ，则说明系统是相对同构的，并使口= 1 0 0 ，确定出口值后的步骤类似 于口s s 算法。该算法主要的缺点是仅仅考虑c p u 的时钟速度，而c p u 的负载以及 网络带宽等因素没有考虑。 p e r f o r m a n c e b a s e dp a r a l l e ll o o ps e l f - s c h e d u l i n g ( p p l s s ) t 1 1 】：这个算法要估计各节 点的性能( 尸d 。在开始调度之前，先写一个比较简单的应用程序在所有的子节点上运 行，记录下每个节点上的执行时间，再根据公式： 舾圳靠 公式( 2 7 ) j _ v n o d e l , s 算出各节点的性能，其中w 为权重，s 为所有节点的集合，乃为节点f 执行程序的时 间。然后根据胛把口的工作量分配给各节点，剩下的( 1 0 0 口) 的工作量根据c s s 、 g s s 和t s s 等算法分配。该算法主要的缺点是没有考虑到网络带宽的影响。 h y b r i dp a r a l l e ll o o ps c h e d u l i l l g ( h p l s ) 1 1 2 】：这个算法是p p l s s 算法的改进，在计 1 6 基于桌面网格的自调度算法的研究及应用 第2 章相关技术及研究基础 算性能阡的时候考虑了带宽的影响，公式如下： 所专忐 公加剐 v n “o d e , e sv n “o d e , e ss 其中，w ，为执行时间的权重，w 2 为带宽的权重，它们的和为l ，b ，为主节点和节点f 之间的带宽值。该算法可以比较准确的计算子节点的性能，对口值没有以前的算法敏 感，并且综合考虑了执行时间和网络带宽的影响。该算法主要的缺点是没有考虑到子 节点的负载在执行过程中可能会发生变化，计算出的性能值是非实时的，而且在第二 阶段也没有考虑子节点的性能。 p a r a l l e l l o o ps c h e d u l i n gu s i n gk n o w l e d g e - b a s e d w o r k l o a de s t i m a t i o n ( p l s k w e ) 1 1 3 】：该算法是继p p l s s 和h p l s 算法之后，由w e n c h u n gs h i h 等人提出 的，改