(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf_第1页
(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf_第2页
(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf_第3页
(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf_第4页
(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf_第5页
已阅读5页,还剩119页未读, 继续免费阅读

(计算机应用技术专业论文)基于资源主动适应的网格依赖任务调度研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

东北大学博士学位论文摘要 基于资源主动适应的网格依赖任务调度研究 摘要 网格计算的出现,使得人们可以利用分布在各地的闲散计算资源处理较为复杂的计 算密集型的并行分布式应用。然而,如何将应用程序的任务调度到可用的资源上,是实 现高性能的关键因素之一。任务调度直接影响网格应用的性能,网格自身的自治性、异 构性、动态性、分布性等特性则对传统的任务调度方式及方法提出了新的挑战。 网格计算中一个大型的应用程序往往被分解为多个任务,由于应用程序分解的任务 之间往往存在依赖关系,因此对依赖任务调度问题的研究具有很高的实用价值。对于由 一组依赖任务构成的网格应用调度的首要目标是使得该应用程序在最短时间内完成,应 用的执行时间是由为每一个任务选取的资源以及任务的执行次序决定的,在异构、动态 的网格环境下,不仅资源的处理能力是不同的,资源间的网络带宽也是不同的,因而不 同的资源分配使得任务的执行时间以及任务间的数据传输时间或通信时间都将是不同 的,所以为了获得应用最短执行时间就需要针对整个依赖任务集合进行全局优化调度。 可见,为了使得应用的执行时间最短,首先需要解决的一个关键问题是针对整个任 务集合生成一个全局的优化调度方案,然而,网格自身的自治性、动态性使得资源的性 能是动态变化的,并且随时都可能有新的资源加入或已有的资源退出网格环境,针对整 个任务集合的全局优化调度方案是在确定的网格资源环境下生成的,在这样的情况下, 如何保证全局优化调度方案的可行性,即如何使得全局优化调度方案有效地适应网格资 源的动态变化就成为依赖任务调度的另外一个关键问题。显然,一个既能进行全局优化 调度又能够适应网格资源动态变化的调度方法是解决依赖任务调度问题的关键,针对该 问题,本文提出了一个新的任务调度机制一基于资源主动适应的网格依赖任务调度机 制,该机制可以描述为:首先根据任务的资源需求及任务间的依赖关系在当前可用资源 上进行全局优化调度,生成一个全局优化调度方案;然后,资源状态发生变化后主动触 发对其所影响的应用的调度计划的修正过程,从而使得已经生成的调度方案能够反映资 源的动态变化,达到适应资源动态变化的目的。 本文的主要贡献在于: 1 ) 提出了一个新的依赖任务调度机制一基于资源主动适应的网格依赖任务调度机 制,该机制的基本思想是首先通过全局优化方法获得依赖任务在当前可用资源集合上的 i i 东北大学博士学位论文摘要 全局优化调度计划,然后针对资源的状态变化调整已有的调度计划。该调度机制能够实 现针对应用进行全局优化调度的同时,还能适应网格资源的动态变化,同时由于对已有 调度计划的调整过程是由资源状态变化主动触发的,可作为后台程序执行,因此对调度 计划的调整过程不会增加整个应用的执行时间。 2 ) 针对上述调度机制中全局优化调度计划生成问题,本文提出了一个表示任务与 网格资源映射关系的方法:任务资源分配图( 1 b k r e 洲c e a s s i g n m c i l t g r a p kt - r a g ) , 该图将描述应用静态信息的任务图与动态的网格资源相结合,在t - r a g 的基础上将全 局优化调度计划生成问题转化为r a g 的优化选取问题。基于任务资源分配图优化选 取的全局优化调度模型兼顾了任务间的依赖关系、资源间的依赖关系及资源的异构性, 因而更适合网格中的依赖任务调度问题。基于该优化调度模型实现的算法与其它算法的 对比分析表明,该模型对于依赖任务的全局优化调度问题是有效的。 3 ) 为实现对全局优化调度计划的主动调整,将网格资源的变化抽象为有限的状态, 本文定义了资源状态变迁事件,构建了针对网格资源的有限状态机。资源状态发生变化 时,触发有限状态机根据预先制定的规则和算法对调度计划进行调整,从而使得在资源 状态变化时,调度计划依然能够反映资源的动态变化,从而达到适应资源动态变化的目 的。 4 ) 为了提高基于资源主动适应的网格依赖任务调度机制的效率,提出了面向应用 的网格资源表示及管理模型,面向应用需求的网格资源表示可以获得针对某个应用的资 源,提高了全局优化调度的效率;面向应用执行的网格资源表示对任务可用资源根据性 能建立了索引,可以提高调度计划的调整效率。 5 ) 应用本文提出的基于资源主动适应的网格依赖任务调度机制,设计并实现了一 个面向依赖任务的调度系统一d t o s s ( d 印e n d e n tt a s ko r i e n t e ds e h e d u l i n gs y s t e m , d t o s s ) ,验证了所提出机制的有效性。 关键词:网格计算;依赖任务调度;资源状态图;全局优化调度;任务资源分配图; 依赖任务调度系统; i i i 东北大学博士学位论文 a b s t r a c t a s t u d y o nr e s o u r c ea c t i v e a d a p t a t i o nb a s e dg r i dd e p e n d e n t t a s k ss c h e d u l i n g a b s t r a c t w i t ht h ee m e 玛e n c eo fg r i dc o m p u t i n g ,p e o p l ec a nu c o m p u t m gr e s o u r c e sd i s t r i b u t e d a c r o s st h ew o r l dt od e a lw i t hc o m p l e xp a r a l l e l d i s t r i b u t e da p p l i c a t i o n h o wt o s i g nt a s k so f t h ea p p l i c a t i o nw i ma v a i l a b l er e s o u r c e si sak e yi s s u et oi m p r o v et h ee f f e c t i v e n e s s t a s k s c h e d u l i n gd i r e c t l y a f f e c t st h ep e r f o r m a n c eo f 酣da p p l i c a t i o na n dt h e a u t o n o m y , h e t e r o g e n e i t y , d y n a m i ca n dd i s t r i b u t e dp r o p e r t yo f r e s o u r c e sp r o v i d e san e wc h a l l e n g et ot h e t r a d i t i o n a lt a s ks c h e d u l i n ga p p r o a c h i ng r i dc o m p u t i n gal a r g ea p p l i c a t i o ni s u s u a l l yd e c o m p o s e di n t om u l t i p l et a s k s b e c a u s et h e r ee x i s t sd e p e n d e n tr e l a t i o nb e t w e e ns u c ht a s k s ,r e s e a r c ho nd e p e n d e n tt a s k s c h e d u l i n gh a sh i 曲m e r i ti nt h ep r a c t i c e t h ei n i t i a lg o a lo fd e p e n d e n tt a s ks c h e d u l i n gi nt h e 鲥dc o m p m m gi st om a k et h ea p p l i c a t i o nf i n i s hw i t h i nt h es h o r t e s tt i m e t h ee x e c u t i o nt i m e o f t h ea p p l i c a t i o ni sd e t e r m i n e db yt h er e s o u r c e sa s s i g n e dt ot a s k sa n dt h ee x e c u t i o no r d e ro f t a s k s i nt h eh e t e r o g e n e o u sa n dd y n a m i c 鲥dc o m p m i n ge n v i r o n m e n t ,n o to n l yt h ec a p a c i t i e s o fr e s o u r c e s ,b u ta l s ot h eb a n d w i d t h sb e t w e e nr e s o u i v :e sa l ed i f f e r e n t t h u s ,t h es c h e d u l i n g m a k e st h ee x e c u t i o nt i m eo ft a s k sa n dd a t a t r a n s p o r t a t i o nt i m eb e t w e e n t a s k so r c o m m u n i c a t i o nt i m ea r ed i f f e r e n t i no r d e rt om a k et h ee x e c u t i o nt i m eo ft h ea p p l i c a t i o n s h o r t e s t , ag l o b a lo p t i m i z a t i o ns c h e d u l i n go f t h es e to f d e p e n d e n tt a s k si sn e e d e d i no r d e rt om a k et h es h o r t e s te x e c u t i o nt i m eo ft h ea p p l i c a t i o n , t h ef i r s tk e yp r o b l e m n e e d e dt os o l v ei st og e n e r a t eag l o b a lo p t i m i z a t i o ns c h e d u l i n gp l a nf o rt a s k ss e t h o w e v e r , f o rt h ea u t o n o m ya n dd y n a m i cp r o p e r t yo ft h eg r i d ,t h ep e r f o r m a n c eo fr e s o u r c e si sc h a n g e d d y n a m i c a l l ya n da ta n yt i m en e wr e s o u r e e sc a nj o i ni n t ot h eg r i de n v i r o n m e n ta n da v m l a b l e r e s o u r c e sc a l le x i tf r o mt h eg r i de n v i r o n m e n t i nt h i ss i t u a t i o n , h o wt oi n s u r et h ef e a s i b i l i t y a n do p t i m i z a t i o no ft h eg l o b a lo p t i m i z a t i o ns c h e d u l i n gp l a ni sa n o t h e rk e yp r o b l e mo ft h e d e p e n d e n tt a s ks c h e d u l i n g t h i sp r o b l e mi sn e e d e dt os o l v ei no r d e rt om a k et h eg l o b a l o p t i m i z a t i o ns c h e d u l i n gp l a na d a p tt ot h ed y n a m i cp r o p e r t yo ft h eg r i d r e s o u r c e s a s d i s c u s s e da b o v e ,as c h e d u l i n ga p p r o a c hw h i c hc a nm a k eg l o b a lo p t i m i z a t i o ns c h e d u l i n ga n d c a na d a p tt ot h e d y n a m i cp r o p e r t yo f 鲥dr e s o u r c e si s ak e yt os o l v et h ep r o b l e mo f d e p e n d e n tt a s ks c h e d u l i n g t os o l v et h i sp r o b l e m , t h i sd i s s e r t a t i o np r o p o s e san o v e lt a s k s c h e d u l i n gm e c h a n i s m , r e s o u r c ea c t i v e - a d a p t a t i o nb a s e dg r i dd e p e n d e mt a s ks c h e d u l i n g 东北大学博士学位论文 a b s t r a c t m e c h a n i s m t h i sm e c h a n i s mc a l lb ed e s c r i b e da sf o l l o w s :f i r s t l y , ag l o b a lo p t i m i z a t i o n s c h e d u l i n gp l a ni sg e n e r a t e da c c o r d i n gt o t h er e s o u r c e sr e q u i r e db yt h et a s k sa n dt h e d e p e n d e n tr e l a t i o n sb e t w e e nt a s k s ;t h e n , w h e nt h es t a t e so fr e s o u r c e sa r ec h a n g e d , t h e m o d i f y i n gp r o c e s sw i l lb ea c t i v a t e di no r d e rt om a k et h eg e n e r a t e ds c h e d u l i n gp l a na d a p t i v e t h ec h a n g eo f t h er e s o u r c e s t h ec o n t r i b u t i o no f t h i sd i s s e r t a t i o ni sp r e s e n t e da sf o l l o w s : 1 ) ad e p e n d e n tt a s ks c h e d u l i n gm e c h a n i s mi sp r o p o s e d ,r e s o u r c ea c t i v e - a d a p t a t i o n b a s e dg r i dd e p e n d e n tt a s ks c h e d u l i n gm e c h a n i s m t h eb a s i ci d e ao ft h i sp r o p o s e d m e c h a n i s mc a r lb ed e s c r i b e da sf o l l o w s :f i r s t l y , t h r o u g hg l o b a lo p t i m i z a t i o ns c h e d u l i n go nt h e a v a i l a b l ef e s o u r c e s ,ag l o b a lo p t i m i z a t i o ns c h e d u l i n gp l a ni sg e n e r a t e d ;t h e n , a c c o r d i n gt ot h e c h a n g eo fr e s o u r c e s ,t h ea v a i l a b l es c h e d u l i n gp l a nw i l lb em o d i f i e d b e c a u s et h em o d i f y i n g p r o c e s si si n v o k e db yr e s o u r c e sa c t i v e l yw h i c hc a l lb ee x e c u t e db a c k g r o u n d , t h i sp r o c e s s c a n n o ti n c r e a s et h ee x e c u t i o nt i m eo f t h ea p p l i c a t i o n 2 、t os o l v et h ep r o b l e mo fg e n e r a t i o no fg l o b a lo p t i m i z a t i o ns c h e d u l i n gp l a ni nt h e p r o p o s e dm e c h a n i s m ,t h i sd i s s e r t a t i o np r o p o s e sa na p p r o a c hw h i c h i sn a m e da s t a s k - r e s o u r c ea s s i g n m e n tg r a p h ( t - r a g ) t od e s c r i b et h em a p p i n gr e l a t i o nb e t w e e nt a s k s a n d 鲥dr e s o u r c e s t h et a s kg r a p hc a nd e s c r i b et h es t a t i ci n f o r m a t i o no ft h ea p p l i c a t i o na n d t h et - r a gc o m b i n e st h et a s kg r a p ha n dt h ed y n a m i c 鲥dr e s o u r c e st o g e t h e r b a s e do n t - r a c t h ep r o b l e mo fg e n e r a t i n gg l o b a lo p t i m i z a t i o ns c h e d u l i n gp l a nc a l lb et u r n e di n t oa p r o b l e mo fo p t i m i z e ds e l e c t i o no ff r a gg l o b a lo p t i m i z a t i o ns c h e d u l i n gm o d e lb a s e do n t - r a go p t i m i z a t i o ns e l e c t i o nc a nc o n s i d e rt h ed e p e n d e n tr e l a t i o n sb e t w e e nt a s k s , t h e d e p e n d e n tr e l a t i o n sb e t w e e nr e s o u r c e sa n dt h eh e t e r o g e n e i t i e so ft h er e s o u r c e s ,t h u si tc a l l a d a p tt ot h ep r o b l e mo ft a s ks c h e d u l i n gi n 鲥db e t t e r t h ea n a l y s i so fc o m p a r i s o no ft h e a l g o r i t h m sb a s e do nt h eg l o b a lo p t i m i z a t i o ns c h e d u l i n gm o d e la n do t h e ra l g o r i t h m ss h o w s t h a tt h em o d e li se f f e c t i v eo fs o l v i n gt h ep r o b l e mo fg l o b a lo p t i m i z a t i o ns c h e d u l i n go f d e p e n d e n tt a s k s 3 ) i no r d e rt oi m p l e m e n tt h ea c t i v em o d i f i c a t i o no ft h eg l o b a lo p t i m i z a t i o ns c h e d u l i n g , t h i sd i s s e r t a t i o na b s t r a c t st h ec h a n g eo fg r i dr e s o u r c e st of i n i t es t a t e sa n dd e f i n e st h ec h a n g i n g c o n d i t i o no ft h er e s o u r c es t a t e s t h i sd i s s e r t a t i o np r o p o s e sam o d i l y i n ga p p r o a c hw h i c hi s b a s e do nt h ef i n i t es t a t em a c h i n e w h e nt h er e s o u r c es t a t ei sc h a n g e d ,t h ef i n i t es t a t em a c h i n e w i l lb ei n v o k e da c c o r d i n gt ot h ep r e d e f i n e dr u l ea n da l g o r i t h mt oa f f e c tt h es c h e d u l i n gp l a ns o t h a tt h es c h e d u l i n gp l a nc a ns t i l lr e f l e c ta n dc o n s e q u e n t l ya d a p tt ot h ed y n a m i cc h a n g eo f t h e r e s o u r c e 4 、i no r d e rt oi m p r o v et h ee f f e c t i v e n e s so fr e s o u r c ea c t i v e a d a p t a t i o nb a s e dg r i d v 东北大学博士学位论文a b s t m c t d e p e n d e n tt a s ks c h e d u l i n gm e c h a n i s m ,t h i sd i s s e r t a t i o np r o p o s e sa 鲥da p p l i c a t i o no r i e n t e d r e s o u r c ed e s e r i p t i o n & m a n a g e m e n tm o d e l u s i n gt h ea p p l i c a t i o nr e q u i r e m e n to r i e n t e d l e s o u r c ed e s c r i p t i o n , r e s o u r c e sf o rc e r t a i n a p p l i c a t i o nw i l lb eo b t a i n e dt oi m p r o v et h e e f f e c t i v e n e s so fg l o b a l o p t i m i z a t i o ns c h e d u l i n g a c c o r d i n gt o t h ep e r f o r m a n c e ,t h e a p p l i c a t i o ne x e c u t i o no r i e n t e dr e s o u i ed e s c r i p t i o nb u i l d st h ei n d e xo fr e s o u r c e sf o rt a s k s w h i c hc 锄i m p r o v et h ee f f e c t i v e n e s so f m o d i f i c a t i o no f s c h e d u l i n gp l a n 5 1t h i sd i s s e r t a t i o nd e s i g n sa n di m p l e m e n t sad e p e n d e n tt a s ko r i e n t e ds c h e d u l i n g s y s t e m ( d t o s s ) b a s e d0 1 1t h ep r o p o s e dr e s o u r c ea c t i v e - a d a p t a t i o nb a s e dg r i dd e p e n d e n t t a s ks c h e d u l i n gm e c h a n i s m t h i ss y s t e mv e r i f i e st h ef e a s i b i l i t yo f t h ep r o p o s e dn l 。c h a n i s m k e y w o r d s :g r i dc o m p u t i n g ,d e p e n d e n tt a s ks c h e d u l i n g ,r e s o u r c es t a t ec h a r t ,g l o b a l o p t i m i z a t i o ns c h e d u l i n g ,t a s k - r e s o u r c ea s s i g n m e n tg r a p h , d t o s s v i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外,不包含其他人已经发表或撰写过的 研究成果,也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名:鸭螂 签字日期:为订3 ,o 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘,允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流,请在下方签名:否则视为不同意) 学位论文作者签名:傅葵砩导师签名:旅斌 签字 日期:叫弓,f 。签字日期:如呵? 、f f 东北大学博士学位论文 第一章绪论 第一章绪论 本章分析了本文的研究背景及研究意义,总结了国内外网格技术研究现状。对网格 技术中的任务调度问题进行了分析,针对网格应用的调度问题,勾画出本文研究的技术 路线,最后给出了本文的创新点及全文的组织结构。 1 。1 研究背景及意义 随着计算机性能的不断提高和网络通讯技术的迅猛发展,应用需求日益朝着高性 能、大规模、多样性、多功能的方向发展,要求将地理上分布的、异构的各种高性能计 算资源、存储资源、数据资源和其它特殊资源通过高速网络连接起来,实现商性能联合 计算,称为网格计算技术0 1 】【2 】【3 】。在网格计算环境中,资源分散在各个不同地域和管理 域中,由不同的组织拥有和操作,并且在使用策略和安全机制上各不相同,即不同站点 可能会使用不同的局部资源管理系统。同时,很多应用需要同时使用多个站点上的资源, 站点i + 1 治性和分配资源时可能出现的故障需要一种特殊机制来同时分配位于多个站点 上的资源。在过去的十几年中,网格计算在理论和应用两个方面都取得了长足的发展, 特别是在应用领域,这与其广阔的应用前景是紧密相关的。 随着社会的不断向前发展,现实生活中需要解决的问题越来越多,人们对资源的需 求也会越来越多,工作中的协同和合作也会不断加强。而网格的实质,就是共享与协作, 即在多个机构动态形成的虚拟组织中共享资源和协同解决问题。因此,网格计算在未来 的社会中将发挥着越来越重要的作用。 怎样合理的使用网格中的共享资源是决定网格系统效率的一个重要因素,调度则是 合理使用的关键所在,不合理的调度会使部分资源过载而其它的资源却处于空闲状态。 为了提高网格计算的效率,必须不断加强对调度的研究,从而达到高效利用共享资源这 个网格计算的根本目的,使网格计算在未来的社会中能够充分发挥其作用。 虽然现有的网格项i + 1 在体系结构和需要解决的问题类型等方面不尽相同,但它们的 本质内容都是资源共享与协作,基本上都需要一些共同的关键技术,例如网格调度技术。 在网格系统中,大量的上层应用共享着网格的各种资源。如何使得这些应用获得最大的 性能以及使得整个网格系统的效率达到最高( 例如最大吞吐率等) ,是网格调度所要解 决的问题。良好的调度是实现高效使用共享资源的重要环节。通过调度,可以把应用所 需的计算隐藏于网格中,降低了上层应用的复杂性,使用户不必关心任务所需的计算放 1 东北大学博士学位论文第一章绪论 在什么地方去执行从而把更多的精力投入到业务本身的开发中。 网格调度技术比传统高性能计算中的调度技术更复杂,这主要是因为网格具有一些 独有的特征,例如,网格资源的动态变化性、资源的类型异构性和多样性、调度器的分 布和局部管理性等。在网格调度中,还需要考虑移植性、扩展性、效率、可重复性以及 网格调度和本地调度的结合等一系列问题。 网格计算中一个大型的应用程序往往被分解为多个任务,由于应用程序分解的任务 之间往往存在依赖关系,因此对依赖任务调度问题的研究具有很高的实用价值。当前, 一些网格任务调度的研究针对元任务或者批任务开展【7 6 】i 彻,忽视了任务间的数据关联与 优先约束关系,因而不能反映网格任务的实际特征【4 1 ;另外一些针对依赖任务的调度研 究是基于表示为有向无环图d a g ( d i r e c ta c y c l i c 伊a p h ) 的任务图而进行的5 】【6 】【7 1 ,传统的 d a g 任务图只刻画了任务的计算量、通信量与优先关系,因此只能作为同构计算环境 的调度模型【s j ,所以真正适合于网格环境的依赖任务调度模型不仅需要考虑任务之间的 依赖关系,还要考虑调度环境的异构性、动态性带来的影响。 任务调度算法主要分为静态调度和动态调度两大类【9 】。静态调度假设任务图和处理 单元相关的信息在程序执行前可以精确获取,调度好的任务节点不能迁移,也称为编译 时间调度算法;反之,则称为动态调度算法,也称为实时调度算法。 静态任务调度的算法大致可分为;列表调度算法、基于任务复制的调度算法、基于 任务聚类的调度算法和基于随机搜索的调度算法。经典的列表调度算法是h u 首先提出 来的【1 0 1 ,列表调度的基本思想是:通过对节点分配优先级别来构造一个调度列表,然后 重复从调度列表中顺序取出第一个节点,将节点分配到使它的启动时间最早的处理器 上,直到任务图中所有节点被调度完毕。当前大多启发式调度算法都是基于这个思想提 出的,典型的算法有h l f e t ( h i g h e s tl e v e lf i r s tw i t he s t i m a t e dt m a e s ) 1 1 】,d l s ( d y n a m i e l e v e ls c h e d u l i n g ) 1 2 】,m o p ( m o d i f i e dc r i t i c a lp a t h ) t ”1 ,算法之间的区别在于如何计算任 务节点的权值以及相应的处理节点的选择【1 4 】。基于任务复制调度的基本思想主要是:在 一些处理器上冗余地映射任务图中的一些任务,以达到减少处理器之间通信开销的目 的,即它利用处理器的空闲时间复制前驱任务,可以避免某些前驱任务的通信数据的传 输,从而减少处理器等待的时间间隙。典型算法有d s h ( d u p l i c a f i o ns c h e d u l i n g h e u r i s t i c ) t ”1 ,b t d h ( b o t t o m - u pt o p d o w nd u p l i c a t i o nh e u r i s t i c ) t 1 5 】,c p f d ( c r i t i c a lp a t h f a s td u p l i c a t i o n ) ! 1 6 】等。基于任务聚类调度的基本思想是把给定任务图的所有任务映射到 数量不受限的集群上。如果两个任务分配到同一个聚类,则表示它们在同一个处理器上 一2 一 东北大学博士学位论文 第一章绪论 执行。除了执行聚类的步骤外,算法还必须对完成映射的聚类进行最后的调度,即对聚 类中的任务在每个处理器上进行时间先后排序。典型算法有d s c ( d o m i n a n ts e q u e n c e c l u s t e r i n g ) 1 刀和d c p ( d y n a m i cc r i t i c a lp a t h ) 1 8 1 算法。基于随机搜索技术的调度算法主要 是通过有导向的随机选择来搜索问题的解空间,这类技术组合前面搜索结果的知识和特 定的随机搜索特点来产生新的结果,其主要代表是基于遗传算法的调度算法【1 9 1 。 上述静态调度算法中表调度算法是在同构的系统中假定任务之间没有通信花费的 条件下提出的【2 0 】,在传统的并行计算系统中,由于可以保证经过一个很短的时间,各个 处理器必然返回结果,因此这种假设是成立的,但是对于网络资源和计算资源个体能力 都存在较大差异的网格系统中,资源能力的差异、任务间的数据传输花费等改变了传统 列表调度的基础,因此这些算法不能直接应用于网格环境中【2 l 】。基于任务复制的调度算 法和基于任务聚类的调度算法,将通信量大的任务尽可能分配到相同的资源上,以达到 减少处理器之间通信开销的目的,因此也不能彻底解决依赖任务调度问题。基于随机搜 索技术的调度算法比一般的启发式算法的调度结果要好,然而,它们往往有较高的时间 复杂度,而且需要适当地确定一些控制参数。此外,适用于一个任务图的最优控制参数 往往不适合另一任务图,很难找到对于大多数任务图都能产生较好的调度结果的控制参 数集。 动态调度算法采用在任务执行时刻根据任务和资源的实时状态进行资源分配的策 略,常见的动态调度算法有m e t ( m i n i m u me x e c u t i o nt t m e ) ,m c t ( m i n i m u mc o m p l e t i o n t n n e ) ,s a ( s w i t c h i n ga l g o r i t h m ) ,k p b ( k - p e r c e n tb e s t ) ,o l b ( o p p o r t u n i s t i el o a d b a l a n c i n g ) p 2 1 ,动态调度算法一般以负载均衡为目标是基于这样一个假设:若各个资源 节点的负载是均衡的则应用执行时间将是最短的嘲。 静态调度算法优化效果较好,但需要花费大量时间计算任务调度表,算法缺少灵活 性,随着资源的动态变化需要重新调度。相比之下,动态调度算法的环境适应性好,但 动态调度算法只考虑当前就绪队列中任务的特征进行调度,而不能顾及后续任务因而整 体优化效果较差。一个既能进行全局优化调度又能够适应网格资源动态变化的调度机制 是解决依赖任务调度问题的关键,针对该问题,本文提出了一个新的任务调度机制,该 机制的实现基于两个关键技术:全局优化调度和资源状态图模型。全局优化调度以整个 应用最短完成时间为优化目标,根据任务的资源需求及任务间的依赖关系生成一个当前 资源环境下最优的任务调度方案:资源状态图模型描述了资源变化的有限状态及各个状 态之间的转化规则。该机制可以描述为:首先根据任务的资源需求及任务间的依赖关系 一3 一 东北大学博士学位论文 第一章绪论 生成一个全局优化调度方案,然后以全局优化调度方案为蓝图,以资源状态变化为依据 动态修正调度方案。资源状态发生变化后主动触发对其所影响的应用的调度方案的修正 过程,因此将该过程称为资源主动适应过程,基于该过程的任务调度机制称为基于资源 主动适应的网格任务调度机制。 1 2 国内外研究现状 网格计算源于美国和欧洲( 英国、德国等) 的研究计划,作为一种新兴的技术,网 格正在快速发展,目前网格技术已经推广到各个大洲。网格技术的出现使得许多行业具 有挑战性的问题可以在新的计算平台上完成和实现。各国的科研机构和商业机构已经意 识到网格的重要性,在网格研究领域投入了大量的资金。全球网格论坛、地区和国家的 网格论坛正在迅速的发展,其学术交流活动也正在积极地展开。全球最大的网格联盟一 全球网格论坛( g l o b a lg r i df o r u m ,g g f ) 已经成为事实上的网格标准制定和发布机构。 下面介绍一下网格目前主要的研究现状及其应用。 1 2 1 美国的网格研究现状及应用 美国是网格技术的倡导者,也是目前网格技术的引领者。美国的网格发展也是从大 学和科研机构开始的,随后企业界的参与加快了网格技术的发展。先后开展了g l o b u s , l e g i o n ,c o n d o r 等比较有影响的网格项目的研究,并形成了具有一定规模和影响力的网 格应用及平台工具。 g l o b u s 2 4 1 是目前网格研究领域最具有影响力的项目之一,该项目的最初的目标是开 发一个面向科学计算的基本软件基础设施,利用该设备,把地理位置上分布的计算资源 和信息资源集成起来。其关键理论包括资源管理、网格安全、信息服务、数据管理等。 o l o b u s 联盟是网格计算的领导团队,以发展网格的基础技术为己任,先后推出了g t 2 ( g l o b u st o o l k i tv e r s i o n2 ) ,g t 3 和g t 4 ,g t 3 是第一个基于o g s a 体系结构的网格平 台,目前该工具集已经发展到基于w s r f ( w e bs e r v i c er e s o u r c ef r a m e w o r k ) 体系结构 的g t 4 。除了g l o b u s 之外,美国还有其它许多项目与网格研究和开发工作密切相关。 l e g i o n l 2 5 1 是弗吉尼亚大学的一个基于对象的元系统软件项目,该项目开始于1 9 9 3 年。该项目的目标是为用户提供单一、一致的虚拟计算模型。l e g i o n 是一个基于计算的 元系统,支持透明调度、数据管理、容错、站点自治和多种安全机制。在l e g i o n 内, 所有的实体都是对象,包括硬件实体和软件实体。每一个对象由它的类对象定义和管理, 一4 一 东北大学博士学位论文 第一章绪论 类对象的作用相当于管理者,它除了定义实例之外,还制定管理策略。 c o n d o 矧是一个专用的计算密集型负载管理系统,提供队列机制、调度策略、优先 级方案、资源监控、资源管理等功能。用户向c o n d o r 提交自己的作业,c o n d o r 把作业 放在队列中,根据一定的策略,在合适的时间在合适的资源上执行用户提交的作业。作 业运行过程中,它监控作业的运行过程;作业运行结束时,通过电子邮件等方式通知用 户。用户提交的作业可以是串行的,也可以是并行的。 p l 锄e t l a b l 2 _ 7 】【2 研是由民间研究团体发起的一个研究项目,旨在研究下一代互联网技 术。该研究计划希望克服现在互联网不够透明的缺点,提供透明的互联网服务,同时在 现有的互联网上增加一个o v e r l a y ,在p l a n e t l a b 中使用的是一种虚拟服务的计算方式, 计算能力通过虚拟机器来实现,每一个虚拟机成为一个s l i c e ,可以包含多个真实的计算 资源,也可以是一个真实计算资源的一部分。目前普林斯顿大学、华盛顿大学以及惠普 公司、i n t e l 公司等纷纷加入了这一研究计划,现在由普林斯顿大学、华盛顿大学和加州 伯克利大学共同管理该社团。p l a n e t l a b 目前在全球已经部署了上百个节点,我国在2 0 0 4 年底通过中国教育网也加入了这一研

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论