（计算机应用技术专业论文）网格环境中任务dag调度算法研究.pdf

硕士学位论文摘要 摘要 网格作为一个集成的计算与资源环境，或者说是一个计算资源 池，它能够充分吸纳各种计算资源，并将它们转化成一种随处可得的、 可靠的、标准的同时还是经济的计算能力。除了各种类型的计算机， 这里的计算资源还包括网络通信能力、数据资料、仪器设备甚至是人 等各种相关的资源。网格要完成这一系列的工作必须通过一个好的调 度策略，因此，如何保证网格有效的资源调度分配已经成为重要的研 究课题。 本文通过建立网格环境中任务调度测评模型体系，结合了调度的 通信代价、处理器利用率和负载平衡提出了一种对调度策略优越性的 测评算法t a i ，并根据t a i 算法的测评思想，结合赫夫曼树，提出了 一个网格环境中d a 6 调度算法。本文的主要贡献包括以下几个方面： 1 分析目前调度算法普遍存在的问题，对存在的问题进行分析对 比，针对目前调度算法普遍存在的理想假设问题提出了可行的解决方 案。 2 针对目前的调度算法提出了一个评价调度算法优劣性的测评算 法t a i ，这个算法从通信代价、处理器满足性及负载平衡三方面有效 地对调度算法的优劣性进行测评。 3 基于上面提出的t a i 调度测评算法，并借鉴赫夫曼树的思想提 出了一个新的网格环境下的调度算法。这个算法所生成的调度方案经 过仿真实验均比其它调度算法产生的调度方案各方面性能均达到优 化。 本文提出的测评算法和调度算法，仅仅对于链路冲突进行了理想 假定，因此具有很好的适用性，将算法放到了普遍动态的网格环境中 来进行，有一定现实意义。 关键词：网格，任务调度，负载平衡，测评 硕士学位论文 a b s t r a c t a bs t r a c t g r i da sa ni n t e g r a t e dc o m p u t i n gr e s o u r c e sa n dt h ee n v i r o n m e n t ，o ri s ap o o lo fc o m p u t i n gr e s o u r c e s ，i tc a nf u l l ya b s o r ba l lk i n d so fc o m p u t i n g r e s o u r c e s a n dt om a k et h e mi n t oaw i d e l ya v a i l a b l ea n dr e l i a b l e ，o r e c o n o m i cs t a n d a r d so ft h ec o m p u t i n gp o w e r i na d d i t i o nt oa l lt y p e so f c o m p u t e r s ，c o m p u t i n gr e s o u r c e sh e r e i n c l u d en e t w o r kc o m m u n i c a t i o n s ， d a t a ，a p p a r a t u s ，e q u i p m e n ta n de v e np e o p l e ，a n do t h e rr e l a t e dr e s o u r c e s g r i dt oc o m p l e t et h ew o r ko ft h i ss e r i e sm u s tp a s sag o o ds c h e d u l i n g s t r a t e g y ，t h e r e f o r e ，h o wt oe n s u r et h a tt h eg r i ds c h e d u l i n ge f f e c t i v e a l l o c a t i o no fr e s o u r c e sh a sb e c o m ea ni m p o r t a n tr e s e a r c ht o p i c i nt h i sp a p e r t h r o u g ht h ee s t a b l i s h m e n to fag r i de n v i r o n m e n t e v a l u a t i o nt a s k s c h e d u l i n g m o d e l s y s t e m c o m b i n e s s c h e d u l i n g c o m m u n i c a t i o nc o s t p r o c e s s o ru t i l i z a t i o na n dl o a db a l a n c i n gt oa s c h e d u l i n gs t r a t e g yf o rt h es u p e r i o r i t yo ft h ea l g o r i t h mt a ia s s e s s m e n t ， a n di na c c o r d a n c ew i t ht h ee v a l u a t i o na l g o r i t h mt a it h i n k i n go f h u f f m a nt r e e ，p r o p o s e dag r i de n v i r o n m e n td a gs c h e d u l i n ga l g o r i t h m t h em a i nc o n t r i b u t i o no ft h i sp a p e ri n c l u d et h ef o l l o w i n g ： 1 a n a l y s i so ft h ec u r r e n ts c h e d u l i n ga l g o r i t h mw i d e s p r e a dp r o b l e m t h ep r o b l e m so fc o n t r a s t ，t h ep r e s e n ts c h e d u l i n ga l g o r i t h mp r e v a i l i n g i d e a lh y p o t h e t i c a lq u e s t i o np u tf o r w a r ds o l u t i o n s 2 i nv i e wo ft h ec u r r e n ts c h e d u l i n ga l g o r i t h mp r o p o s e das c h e d u l i n g a l g o r i t h mf o re v a l u a t i o no ft h em e r i t so ft a ie v a l u a t i o na l g o r i t h m t h e a l g o r i t h mf r o mt h ec o m m u n i c a t i o nc o s t ，p r o c e s s o ra n dl o a db a l a n c i n gt o m e e tt h r e eo ft h ee f f e c t i v es c h e d u l i n ga l g o r i t h mf o re v a l u a t i o no ft h ep r o s a n dc o n s 3 b a s e do nt h ea b o v ee v a l u a t i o nt a is c h e d u l i n ga l g o r i t h m a n d d r a w i n go nt h et h i n k i n go fh u f f m a nt r e et oa n e we n v i r o n m e n to ft h e g r i d s c h e d u l i n ga l g o r i t h m t h es c h e d u l i n ga l g o r i t h mg e n e r m e db ys i m u l a t i o n p r o g r a m m ea f t e rs c h e d u l i n ga l g o r i t h m st h a no t h e rp l a n sf o rm a n a g i n gt h e v a r i o u sa s p e c t sa r et oo p t i m i z ep e r f o r m a n c e t h i sp a p e rp r e s e n t st h ee v a l u a t i o na l g o r i t h ma n dt h es c h e d u l i n g a l g o r i t h m ，t h eo n l yi d e a la s s u m p t i o ni s c o n f l i c to fl i n k ，i th a sg o o d a p p l i c a b i l i t y , w i l lb eg e n e r a l l yd y n a m i ca l g o r i t h mh a sb e e np u to nt h e g r i df o rt h ee n v i r o n m e n t t oac e r t a i ne x t e n tp r a c t i c a ls i g n if i c a n c e k e yw o r d s ： g r i d ，t a s ks c h e d u l i n g ，l o a db a l a n c i n g ，e v a l u a t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 d 作者签名： 2 垒丝日期：丝堕年月日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 p 作者签名：盈墨奎导师签 硕士学位论文 第一章绪论 第一章绪论 网格环境下的调度问题是一类组合优化问题，在计算机及通信等许多领域有 着广泛的应用，在理论上又与算法设计、复杂性理论关系密切，因而引起了许多 学者的研究兴趣【l 卅。在网格计算中，任务管理、任务调度和资源管理是网格必 须具备的三个基本功能。用户通过任务管理系统向网格提交任务、为任务指定所 需资源、删除任务并监测任务的运行状态。用户提交的任务由任务调度系统按照 任务的类型、所需资源、可用资源等情况安排运行日程和策略。而资源管理系统 监测网格资源状况，收集任务运行时的资源占用数据等。由于网格计算任务调度 面临的是一个n p 完全问题【4 】，它引起了众多学者的关注，成为目前网格计算研 究领域的一个焦点。 同时，网格计算也提出了大量困难的课题，例如并行算法的设计、任务的划 分、通信的协调和同步、任务的调度。这些问题不解决，则不能从并行分布处理 中得到任何好处。 在这些问题中，调度和负载平衡是一个重要问题。它的根本问题是，当一个 并行程序实现一组任务后，就需要将它们合理或优化地分配到分布系统中的处理 单元。如果这个问题得不到解决，则有可能导致分布计算效率低下，更有甚者， 有可能造成其效率不如单机计算，乃至计算失败。因此，调度问题是网格计算的 瓶颈问题之一。 1 1 选题背景与意义 随着网格的日益发展，网格环境下的调度问题渐渐成为研究的热点，而网格 环境下的调度都是在传统的调度中发展出来的，传统的调度在计算机科学领域虽 说不是一个很新的课题，但它还一直是个远远没有得到很好解决的问题。 在并行处理领域中，针对以有向无环图d a g ( d i r e c t e da c y c l i cg r a p h ) 来表示 的并行任务在多处理机上进行处理的研究已经由来已久【5 - 7 】。这里带权值的d a g 主要定义了各个子任务间的前驱后继依赖关系和每个子任务的运行时间。但是在 早期的研究中，它并没有包含每个任务之间的通信时间f 引。而最近二十余年来， 随着网络硬件技术和处理器性能的迅速提高，并行处理领域进入了一个全新的阶 段，从而也给并行调度领域中的代表d a g 调度带来了新的问题。此时的并行调 硕士学位论文第一章绪论 度不仅要考虑任务之间的通信代价还要考虑以下因素：1 ) 新形式下的处理机网络 并非完全互连( f u l l y c o n n e c t e d ) ，而是采用任意形状的处理机网络( a r b i t r a r y p r o c e s s o rn e t w o r k ，简称a p n ) ，譬如超立方体等。2 ) 调度环境的异构性带来的影 响。目前绝大部分的d a g 调度算法都是假设处理机同构，也即处理机的处理能 力一致。 这些并行处理领域的新发展给传统的d a g 调度带来了巨大挑战。因为处理 机网络拓扑任意，所以连接处理机间的通信链路变为和处理机同等重要的可用资 源。此时我们不仅需要调度任务给处理机，而且还要把通信消息调度到通信链路 上从而最小化链路竞争。另外这里消息的调度策略还要考虑路由策略的影响，譬 如存储转发( s t o r ea n df o r w a r d ) 技术和虫孔路i 南( w o r m h o l e ) 技术的不同选择会对消 息调度策略产生重要的影响。此外因为处理机间的异构性，d a g 调度必须要考 虑不同处理机间的处理能力不同，而且处理机间的通信速率也可能不同。在这样 的情况下，原先d a g 图中的一些已经预测和估计的任务通信延迟和计算时间在 映射到物理处理机上执行时会有所变化。而现有的这些d a g 调度算法均没有合 理有效地考虑这些问题。 除此之外，传统的d a g 调度理论中还存在不少亟待解决的关键问题。在 d a g 聚簇中，众所周知，找到最优的聚簇调度是一个n p 完全问题，但是对于 线性聚簇，计算并行时间的问题是比较容易解决的，它具有多项式时间的复杂度。 那么什么时候使用线性聚簇策略和什么时候使用非线性聚簇策略? 我们在进行 d a g 调度时，必须选择一个合适的考虑d a g 粒度的调度算法，也就是要进行 d a g 粒度的有效划分，从而指导有效选择调度策略。另外在非线性聚簇条件下， 现有的调度算法都没有明确怎样有效调度那些独立任务。它们或者是优先调度那 些关键路径上的节点或者是优先调度那些具有最早执行时间的节点，但是这些策 略并不能完全使得整个d a g 任务的调度长短最短。而且现有的启发式d a g 调 度算法种类繁多，那么怎样验证各种启发式算法的近似比以及怎样结合实际综合 权衡d a g 调度算法的各种目标而设计出低复杂度高性能的可扩展d a g 调度算 法等问题也是急需解决的。 本文的开展就是要着力解决这些传统的d a g 调度在网格环境下应用的一些 关键技术，当然这两者并不是分割的目标，这些问题的解决将会促进两者融合发 展。传统的d a g 调度中一些关键技术的解决必将推动面向网格和异构环境下 d a g 调度的发展，因为面向异构系统的调度就包含了面向同构系统的调度，面 向网格的调度必然包含了面向完全互连网络的调度。反过来这些新形势下的调度 技术的解决必将丰富传统d a g 调度理论，而且必将大大推动d a g 调度理论应 用于实际系统。异构计算平台和网格是现今并行和分布式领域发展的必然趋势， 2 硕士学位论文第一章绪论 该项目的开展就是在这种新形势下提出d a g 调度领域中的新理论，新方法和新 技术，从而为组合优化领域中设计高效的启发式调度算法和网络并行计算环境中 的静态负载均衡以及并行程序编译提供理论和技术支持。 1 2 国内外研究现状 调度问题一直是计算机科学的一个热门的研究课题【9 1 。有许多专著和期刊 专题讨论调度问题，大量的论文在许多计算机科学方面的期刊上发表，如：i e e e t r a n s a c t i o n so ns y s t e mm a na n dc y b e r n e t i c ，i n f o r m a t i o na n dc o m p u t a t i o n ，i e e e t r a n s a c t i o n so np a r a l l e la n dd i s t r i b u t e ds y s t e m ，p a r a l l e la n dd i s t r i b u t e dc o m p u t i n g ， p a r a l l e lc o m p u t i n ga n dt r a n s p o r t e r s ，t h e o r e t i c a lc o m p u t e rs c i e n c e ，c o m p u t e r s & o p e r a t i o n sr e s e a r c h ，i n t e r n a t i o n a lj o u r n a lo f e l e c t r o n i c s 等等。与该研究方向相关 的国际会议有：t h ei n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m ，i n t e r n a t i o n a l c o n f e r e n c eo nh i g hp e r f o r m a n c ec o m p u t i n g ( a p c ) ，t h ei n t e r n a t i o n a lc o n f e r e n c eo n n e u r a l n e t w o r k s ， i n t e r n a t i o n a lc o n f e r e n c eo np r a c t i c eo fs o f t w a r e d e v e l o p m e n t ( t a p s o f t ) ，p r o c e e d i n g so ft h ec o n f e r e n c eo np a r a l l e lp r o b l e m s o l v i n gf r o mn a t u r e 等等。不仅如此，许多新兴的学科都把各自领域的研究成果 应用于解决调度问题，如基因算法的研究、人工神经网络的研究、人工智能和分 布式人工智能的研究都把解决调度问题作为其应用领域之一【l o 】。 在考虑任务间的通信时间方面，o r e g o ns t a t eu n i v e r s i t y 的b k r u a t r a c h u e 博 士在1 9 8 8 年就提出了包含计算通信延迟在内的新的d a g 并行任务调度模型【l ， 并且已经证明一般的d a g 调度是个n p 完全问题，也就是说它的最优解不能在 多项式时间内解决，除非p = n p 。目前也仅发现在以下三种情况下才有多项式的 最优解【4 】：1 、l 节点权值为单元时问，任务图为树型结构，调度到n 个处理机上； 2 ) 节点权值为单元时间，任务图形状任意，调度到2 个处理机上；3 ) 节点权值 为单元时间，任务图为“i n t e r v a l o r d e r ，调度到n 个处理机上。并且以上三种 情况均没有考虑通信延迟，即假设边权值为0 。那么在这种情况下，用启发式方 法来求解d a g 调度问题就成为一个首要选择。 几十年来，国内外的学者们已经对启发式d a g 调度进行了广泛而深入的不 懈研究，产生了很多的d a g 调度算法，但归纳起来，这些各个时期的算法可以 分成如下四种【1 2 】：其一是表调度算法( l i s ts c h e d u l i n g ) ，其二是聚簇调度算法 ( c l u s t e r i n g ) ，其三是基于任务复制的调度算法( t a s kd u p l i c a t i o n ) ，其四是随机化 搜索技术方法( r a n d o m i z e ds e a r c ht e c h n i q u e s ) 。 这里表调度算法有两个过程，其一是确定各任务的优先级阶段，其二是处理 机的选择阶段，从而选择合适处理机来运行当前优先级最高的就绪任务。表调度 硕士学位论文第一章绪论 算法主要是针对有限完全互连的处理机网络。现有各种各样的表调度算法的调度 结果显示，该类算法复杂度低而且性能较好，但是它是一种仅有一个步骤的调度 策略，不能适应a p n 网络，不过表调度算法思想在任务映射到物理处理机之后 来确定任务的执行次序时很有借鉴作用。另外表调度算法在某些情况下可能会产 生某些反常现象，譬如改变该算法中某些参数，如增加处理机数目，减少各任务 执行时间或者删除某些任务间的偏序关系时，整个并行任务的执行时间不但不会 减少反而还会增加r 。然而理论验证证明所有这些情况下，这些整个任务的执行 时间与最优算法相比存在一个比率小于2 的上界( u p p e rb o u n d ) 1 3 j 。目前基于表 调度的算法有，m c p , e t f , d l s ，l a s t ，h l f e t 以及i s h 1 4 - 1 8 】。基于聚簇的算法因为 是事先假定把各任务映射到无限数目处理机上，所以和一般算法比，它需要另外 一个合并步骤，即把由任务图划分的簇进行再合并，直到和当前可用的处理机数 目相同时为止。它的每一个簇只能映射到同一个处理机上，然后才在该处理机上 指定簇中各个任务的执行序列。聚簇算法可以分成两大类，线性聚簇和非线性聚 簇。如果至少有一个簇中含有两个互相独立的任务( 任务之间不存在依赖关系) ， 那么这便是一个非线性聚簇，反之便为线性聚簇。t a oy a n g 曾证明对于其所定义 的粗粒度d a g ，线性聚簇要优于非线性聚簇 1 9 1 。目前的聚簇算法有 m d ，d s c ，d c p , l c ，e z d c p , m p d 和c a s s ( c l u s t e r i n ga n ds c h e d u l i n gs y s t e m ) 等 瞄眦引。基于任务复制的调度算法主要是为了消除不同处理机间任务间通信时延而 设计。它的应用对象也主要为无限数目的同构处理机网络。因为这种算法不仅要 在其它处理机上复制任务，还要复制任务需要的数据，而且因为在复制任务时还 要向后搜索那些祖先节点( b a c k t r a c k i n g ) ，所以它比一般的算法需要大得多的空间 和时间复杂度，故一般仅局限于理论研究，较少应用于实际。基于任务复制的算 法有d s h ，c p f d ，b o t t o m u p - d o w nd u p l i c a t i o nh e u r i s t i c ，d u p l i c a t i o nf i r s ta n d r e d u c t i o nn e x t 和t c s d 等t 2 4 z 刀。随机化搜索技术方法近些年才流行起来，它主 要结合由前面的搜索结果所获取的知识和一些随机特征来产生新的调度结果。用 随机化搜索技术方法进行调度的结果比较好，但是它们的调度时间要比其它类的 算法高的多。另外譬如遗传算法( g e n e t i ca l g o r i t h m s ) t 2 8 】，它针对不同的d a g 图， 其最优控制参数也不相同，所以在实际调度过程中必须随时变更这些控制参数， 从而造成不便。随机化搜索技术方法包括遗传算法，模拟退火( s i m u l a t e d a n n e a l i n g ) 以及局部搜索技术( l o c a ls e a r c ht e c h n i q u e ) 2 9 3 0 】等。 国内对d a g 调度的研究起步比较晚，而且也都局限于国外研究的调度算法 所属范围之内，基本上还是处于跟踪发展阶段。譬如文 3 1 提出了一种名为b d c p 的调度算法，它也是一种基于动态关键路径技术的表调度算法；文【3 2 】针对在非 全互连工作站网络环境中通信之间不能并行执行的问题，提出了一个基于任务复 4 硕士学位论文第一章绪论 制的静态调度算法t s af j ；文 3 3 1 提出了基于d a g 的、优化的分代任务调度算 法o g s ，该算法综合考虑机器就绪时间和每个任务全部先导的完成时间，从而 减少全部参与调度节点的空闲时间，达到优化m a k es p a n 的目的；文 3 4 】是d a g 调度在网格计算中的应用，它提出了一种基于有向无环图的两层资源监测系统 ( d t g m s ) ；文 3 5 提出了一个基于d a g 图的指令调度优化算法；文 3 6 】针对人 们往往只注重找到一个调度路径最短的算法，却忽略了要节省处理器的问题，提 出了一个基于任务复制的算法t s a o t ；文【3 7 提出了在处理机网络为超立方体 时的基于l u 分解的任务图调度方法。这些方法都是从各个侧面提出了现有算法 的不足从而加以改进并应用到实际领域中去。 目前，网格调度方面的研究主要集中在3 个领域：计算资源的调度，数据 资源的调度和异构集群的调度系统。计算资源调度方面的研究工作考虑了网格系 统中节点动态变化问题，但是还集中在对分布在广域范围的高性能计算机进行共 享，没有考虑海量的数据资源参与问题。此外，大都还局限于m a s t e r s l a v e 的 调度模式，一些项目在体系结构设计方面还不尽如人意。这一方面的工作有代表 性的主要有a p p l e s 、n e t s o l v e 、p u n c h 、m o l 、m s h n 、n i m r o d g 等。数据 资源的调度方面，目前研究工作比较少，代表性的工作有g l o b u s 项目中数据管 理部分和欧洲数据网格。g l o b u s 初步解决了大规模数据传输机制和对数据复制 的管理等问题。欧洲数据网格提供了一个大规模处理数据机制。但是这两个项目 考虑的都是文件型数据资源，没有考虑对关系型数据库资源的共享和处理。此外， 目前的数据资源的调度机制还不成熟，没有和计算资源的调度机制整合起来。异 构集群的调度系统方面，研究工作相对较多，主要集中在对传统的调度算法进行 若干改进以适应异构的计算环境。目前研究工作的主要局限性在于：不考虑网络 传输的延迟，仅考虑计算资源；集中式的调度体系结构和m a s t e r s l a v e 的调度 模式；所考虑的网格系统中节点数目一般比较少，每当系统接收到一个任务或一 个元任务( 由多个互相独立的任务组成一个元任务) 时，使用网格系统的所有节 点为其服务；假设在调度过程中节点数是固定不变的。 在d a g 调度和规则网络的路由算法分析方面，我们课题组也长期从事了这 方面的研究，取得了一定的成果，在国内外核心期t u r n 著名国际会议上( 譬如计 算机学报，计算机科学与技术学报英文版，i p d p s ，p d p t a ，p d c a t 以及i - s p a n 等) 发表了多篇论文，研究成果得到了同行认可。在d a g 调度方面，我们也相 继发表了3 篇重要论文，并且被s c i ，e l 和i s t p 等收录。这三篇论文分别着眼 于设计低复杂度高性能的d a g 调度算法，非线性聚簇下独立任务的调度算法以 及任务的粒度分析，提出了基于动态关键路径和边消除的e z d c p 算法，基于最 大并行度的m p d 算法和一种系统性的d a g 粒度理论【3 8 枷l 。在m e s h 和其它规则 硕士学位论文 第一章绪论 网络的容错路由方面，我们利用概率分析方法也取得了不少可喜的成果h 7 】。 1 3 当前研究存在的问题 调度问题对绝大多数应用来说是n p 完全的，只有在少数高度简化的领域中 才不是n p 完全的【4 8 1 ，对于一般的调度问题来说，由于应用领域的假若设不同而 千变万化，使得调度问题在许多情况下非常难以处理，需要使用启发式方法才能 在合理时间内完成，但使用了这些启发式方法又不一定能够求得最优解，一般只 能求得满意解。 随着我们课题组在d a g 调度领域的研究不断深入，我们发现无论是国际还 是国内，所有的这些调度算法都没有解决以下问题：其一，这些算法都认为d a g 图的节点任务执行时间和任务之间的通信延迟在调度过程中不变，而实际上由于 计算平台的异构性或者处理机网络的松散易变性，任务的通信延迟或者计算代价 会有所变化；其二，现有算法都或多或少存在这样和那样的假定，譬如各处理机 同构并且完全互联，无链路竞争，任务可在任意处理机上运行以及处理机数目无 限等等，所有这些限制条件都大大限制了算法在实际领域中的应用1 6 - 7 , 4 8 ；其三， 我们知道，d a g 调度的实质就是一个在最大化任务的并行度和最小化任务间的 通信时间之间进行均衡问题，也即所谓的m a x m i n 问题【l ，而最能影响该均衡 点选取的就是d a g 图的粒度( g r a n u l a r i t y ) 选择，而关于怎样定义该粒度存在各种 各样的说法，它们从各个方面指导着调度算法的选取和调度结果的评估【4 9 o l ；其 四，目前各种聚簇算法中，对于同簇中没有依赖关系的各独立任务怎样调度到处 理机上没有一个明确的思想( 这里独立任务和般独立任务调度不同，因为这里 同簇中独立任务只能调度到同一个处理机上) ，而实际上这些独立任务调度的先 后关系会大大影响调度结果【1 3 1 ，这些不足都限制了d a g 调度算法的实用性。 从以上分析不难看出，许多调度问题远远还没有得到解决，调度算法的研究 仍然是一个长期而艰巨的任务。在本文中，我们试图采用启发式方法，均衡调度 的各平衡因子，寻求更有效的解决方法。 1 4 本论文的内容安排 本论文的工作得到国家自然科学基金的项目及博士点基金项目的资助，对网 格环境下d a g 调度进行了全面的分析与研究，全文共分为五章： 第一章绪论。主要介绍选题背景与意义，国内外研究现状。最后阐明了全 文的组织。 第二章详细介绍网格环境下的d a g 调度基础。 6 硕士学位论文 第一章绪论 第三章详细介绍网格、网格的特点及网格的调度模型。 第四章提出网格环境下d a g 调度的测评算法t a i 。 第五章提出基于t a i 测评算法的调度算法 最后是本文的工作总结以及研究展望。 7 硕士学位论文 第二章d a g 调度基础 第二章d a g 调度基础 网格计算资源具有多样性、异构性，非常适合具有多种内在并行性的应用执 行。计算网格主要目标之一就是为用户提供高效的应用程序的执行环境。将应用 程序调度到异构的计算节点上运行，获得最优或近优的性能指标是应用调节器度 模型研究的目标和方向。本章介绍网格环境下的应用程序调度方法，包括应用程 序网格调度模型、机器选择算法和任务映射与调度算法。 2 1 调度问题的概念和分类 多任务的调度问题在计算机科学领域虽说不是一个很新的课题，但它还一直 是个远远没有得到很好解决的问题。 2 1 1 调度问题的概念 在网格系统中，一个程序可以看成是一个任务集，这些任务可以并行或串行 地执行。任务之间一般是有优先次序约束的。调度问题的目标是要在满足一定的 性能指标和优先约束关系的前提下，将可并行执行的任务按适当分配策略确定一 种分派和执行顺序，合理分配到各处理机上有序地执行，以达到减少总的执行时 间的目的。性能和效率是评价调度系统的两个基本特征。我们应以任务分派( 调 度) 的质量和调度算法( 调度程序本身) 的效率为基础来评价调度系统。调度质 量以产生的优化调度的性能为基础来衡量；调度算法的效率以时间复杂性为基础 来衡量。例如，如果以优化一个程序的完成时间来衡量，显然完成时间越短越好。 如果两个调度算法产生相同的调度质量，则调度算法越简单越好【1 0 1 。 2 1 2 调度问题的分类 调度问题可以根据一个程序的任务是确定的还是非确定的来进行划分。确定 的调度是指被调度的任务和它们之间的相互关系在系统执行之前就可完全确定； 非确定的调度是指，只有部分初始任务是已知的，随着系统的执行，任务会动态 地增减。所以，一般将调度划分为两种形式的调度：静态调度和动态调度。 1 静态调度和动态调度 通常是在编译时已经确定了并行程序的特点和性质，如：任务的处理时间、 8 硕士学位论文 第二章d a g 调度基础 通信和同步要求、数据依赖等。也就是说，这些特点在程序执行前都是已知的， 因而一个并行程序可以表示成由加权边和加权节点组成的有向无环图( d i r e c t e d a c y c l i cg r a p h ，简称d a g ) ，图中节点的权表示任务的处理时间，边的权表示数 据依赖关系和任务间的通信时间。使用静态调度对许多科学计算是非常有效的。 例如，用图像处理方法进行物体识别和数值计算等任务都非常适合用静态调度的 方法进行处理。 在动态调度中，调度中的许多问题都是未知的。动态调度的目标不仅是减少 程序的完成时间，而且还要减少调度本身的开销，这种开销就是运行调度程序本 身所付出的代价。通常在分布系统中，动态调度算法采用所谓“偷取空闲周期” 的方法来均衡各处理器之间的负载。然而，当调度的目标是减少某些特定应用的 执行时间时，这种方法是不适用的。 从上述调度问题的分类可看出，调度策略分为静态或动态的，在某种程度上 主要取决于任务分派的时间，静态调度可被看作是预调度，在编译时就可确定哪 些任务在哪台处理机上执行。显然这种策略需要有的任务在执行前都是已知的， 执行调度程序的费用也可忽略不计。因为仅仅根据处理机编号和任务标识，处理 机就可以知道它应该执行哪些任务。如果任务的所有特征在编译时都可以确定， 静态调度就可通过某种有效的算法，合理地把任务分配到各处理机上。 2 b n p 和a p n 调度算法 当分布系统是松散耦合系统时，根据接受任务分配的计算机机群的数量的不 同，调度算法可分为两类：b n p ( b o u n d e dn u m b e rp r o c e s s o r s ) 和a p n ( a r b i t r a r y p r o c e s s o rn e t w o r k ) 。 ( 1 ) b n p 调度算法 这类算法适合于网络速度足够快、可以忽略通信延时的分布环境。在这样的 环境中，处理器之间具有充分而有效的连接。例如，相对紧耦合的网格可以使用 快速以太网、g i g a b i t 网和a m t 交换网。在这样的平台上，如果能对任务进行 优化分配，可以产生非常有效的调度。 ( 2 ) a p n 调度算法 a p n 调度算法需要计算任务中处理通信消息的代价。在这样的环境中，必 须考虑网络的拓扑结构。与b n p 调度算法相比较a p n 调度更加困难，调度程序 必须同时进行任务和信息的调度。实际上通信的耗费是衡量这种调度算法性能的 一个重要因素。当通信的耗费相对于计算的耗费是非常大的时候，通信的费用必 然是整个应用费用的主要部分。减少通信费用的技术之一是使用高带宽、低延时 网络，目前有几种典型的通信网络，如：a t m 、h p p i 、f d d i ，它们可以作为独 立处理节点之间的通信渠道，从而构成一个快速的并行分布计算系统。另一种减 9 硕士学位论文 第二章d a g 调度基础 少通信费用的技术是，使用不同的应用程序接口( a p i ) 来减少高层协议的费用， 这些协议的代价取决于特定网络硬件和软件接口的实施。 人们在将a p n 算法应用于实际问题时，提出和实现了很多软件工具，对应 用进行统计和分析，使用户可以得到应用的计算系列，并进一步将其划分为若干 相对独立的任务，然后将这些任务调度或映射到计算机集群中。然后，这些工具 再产生并行执行代码，代码中含有标准软件包和消息传递原语，如p v m 或m p i 原语等。 2 2 相关概念及理论 1 d a g 有向无环图( d i r e c t e dac y c l i n gg r a p h ) ：一个无环的有向图简称d a g 图。 有向无环图是描述一项工程进行过程的有效工具。主要进行拓扑排序和关键路径 的操作。 一个并行程序可以由d a g 模型来刻画。虽然一个程序中的循环不能由 d a g 模型直接表达出来，但可将在循环中的数据流的并行计算分解为更小的任 务，在局部加以刻画。绝大多数数值计算算法条件分支较少，这样d a g 就很 容易精确描述这些应用，特别是像高斯消去法和快速傅立叶变换等这样的数值计 算方法，循环的边界在编译时完全可以确定下来，这样的循环迭代就可以包含在 一个任务之中，也就是说可以用d a g 的一个节点表示。当然，在大多数情况 下，节点和边是靠估计出来的。一般根据特征信息，如数值运算、内存存取操作 和消息传递原语等进行估计。 我们经常通过d a g 图对要处理的任务进行描述，这样我们可以进清晰地得 到任务间的先后顺序关系和任务间的信息传递量，在d a g 描述中我们可以找出 一条或多条关键路径，通过对关键路径的分析，得出最短运行时间。在本文的算 法中就是采用d a g 图对任务进行描述的。 d a g 节点的入度和出度计算： d a g 节点的入度是节点的先导个数，通过求出节点的先导数，就知道节点 的入度；同样的道理，d a g 节点的出度就是该节点的后继数。计算节点先导数 的方法很简单：根据任务间关系矩阵，一个节点的先导数是该节点所对应的矩阵 行的元素“1 的个数。将该行的元素相加，即得这个节点的入度。d a g 节点 v u 的入度计算公式为 一1 i d k 】= 芝：t r k ，力 公式( 2 - 1 ) 1 0 硕士学位论文第二章d a g 调度基础 式中，k 是所求入度的d a g 节点的编号，f 是d a g 节点号，即任务号；t r 是任 务间依赖关系矩阵。 d a g 节点的后继数的计算方法也很简单：根据任务间关系矩阵，一个节点 的后继数是该节点对应的矩阵列的元素“l 的个数。将该列的元素相加，即得 这个节点的出度。d a g 节点讹1 7 的出度公式为 一l o d k 】= 乏：t r i ，朋 公式( 2 - 2 ) 2 并行性与通信时间 在任务之间的通信时间可以忽略的情况下，就绪任务可同时分配到当前可利 用的处理机上，这样可以减少总的执行开销。这种情况可能出现在共享内存的环 境下。在该环境下，通信可以在存储器的刷新周期内完成。实际上，这种环境是 许多不考虑通信时间的启发式调度方法的基础。 另一方面，当通信时间不可忽略的时候，启发式调度方法必须在分配任务时 考虑通信时间问题。有时可能要考虑将具有较长通信时间的任务，与发送消息给 它的任务分配到同一个处理机上。这正是我们在第四章和第五章所实现的网格调 度方法的基本策略之一。 在本文所提出的算法中，我们的通信时间是不可忽略的，我们通过对任务间 的信息传递量进行评估，从而得出任务间的通信时间，而根据这个通信时间去确 定任务的分组与处理器分配，在第四章的网格环境下d a g 调度的测评算法和第 五章的基于t a i 测评算法的调度算法均采用了这一方法。 3 粒度 性粒度大小是启发式方法必须考虑的又一个问题，同时它也与并行性和通信 时间密切相关。它在程序分片时就必须解决。这个问题的难度是如何确定一个程 序的任务图中每个节点的最佳粒度大小。 粒度定义为若干连续的指令结合在一起形成的模块的大小，这个模块能够在 每个处理机上独立执行。改变粒度大小可以通过增加或减少模块的指令数。粒度 可以d , n 只有一条指令，大到包含整个程序。如果粒度太大，则并行性减弱，因 为潜在的并发任务被合并到一个任务中，并且只能在一个处理机上顺序执行。另 一方面，当粒度太小时，系统要把大量时间花在上下文切换、调度和通信上，从 而增加了执行的总成本。 由于各种分布系统的产生，将程序进行划分并将各个分片程序所使用的数据 尽可能放到局部处理单元变得越来越重要，其出发点是减少各处理单元所运行的 任务之间的数据移动。因为，即使分布系统使用高数据传输率通道，其延时还是 远远大于局部存储器的延时。另一方面，如果仅考虑将并行程序放到一个处理机 硕士学位论文 第二章d a g 调度基础 执行来增加数据局部化，将会牺牲程序的并行性。所以，在启发式调度中要权衡 最大局部化和最大并行化之间的矛盾。好的调度能使得最大局部化和最大并行性 都能够得以实现。 不同的并行程序设计环境往往形成一种“自然”粒度，在我们的解决方案中， 采用一种自然的粒度划分方法，也就是任务的形式，因此，在第四章和第五章并 没有过多地去涉及任务粒度的划分，我们认为一个任务就是一个粒度。 4 任务分配 任务可以不受优先关系的约束而相互作用或进行通信，这类任务的调度问题 称为任务分配，它是属于略微简化了一点的调度问题。任务分配问题的背景是不 需要强调任务在分布系统上的执行次序。在一个由多个处理机组成的分布系统 中，相互作用的任务必须分配到多个处理机上，以充分利用系统资源。 在任务分配到处理机的过程中，有两种类型的成本：任务在某个处理机上的 执行成本和处理机之间的通信成本。为了改进网格系统的性能，这两个目标必须 满足，即：处理机之间的通信成本要降到最低；在不同处理机上的任务的执行成 本需要平衡。这两者似乎有些冲突。任务分配技术就是要找到某种分配策略，使 得处理机之间通信成本和任务的执行时间都尽可能最小化。 我们从前面的讨论中已经知道，一般情况下( 处理机个数大于3 ) 的任务分 配问题是n p 完全的，网格环境中当然会大于3 ，所以人们不会盲