（计算机软件与理论专业论文）树形网格任务调度方法研究.pdf

j ， 公髫g曩0。， ； at h e s i si nc o n l p u t e rs o n w a r ea n d t h e o r y t a s k s c h e d u l i n gr e s e a r c hb a s e d0 n t r e e - ba s e dg r i dlr e e - d a s e db r l d b yh u a n gj 硼听 s u p e i s o r ：p r o f e s s o rq i a oj i a n z h o n g n o r t h e a s t e r nu n i v e r s i 够 j u n e2 0 0 8 嘎： 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了 明确的说明并表示谢意。 学位论文作者签名：量j i 一 日期：厕6 心 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年口 学位论文作者签名：专 蚕 签字日期： 导师签名： 签字日期： 1 l a 东北大学硕士学位论文 摘要 树形网格任务调度方法研究 摘要 随着网格技术的深入研究与发展，地理上分布的异构资源可以通过网格工具整合成 一个完整的计算平台。高效的网格任务调度成为研究的热点和亟待解决的问题，其难点 在于综合考虑任务间数据依赖，网格环境的拓扑结构和异构性特征对于调度的影响。 有向无环图( d i r e c t e da c y c l i c 伊a p h ) 在并行计算任务调度领域中已有大量应用，它 使用结点来代表计算任务，并且使用有向边来表示任务间的数据依赖和任务之间的通信 量。关键路径是任务调度图中最长的执行路径，本文对传统的有向无环图模型进行了修 改，并在表调度技术中使用动态关键路径方法来有效降低整体任务图的调度长度。 本文首先提出了一种基于有向无环图模型的树形异构网格静态任务调度启发式算 法，该算法考虑了任务图中的数据依赖和网格的异构性，在每一个调度过程中，该算法 使用动态关键路径来选择任务结点，并且采取最早完成时间策略来完成处理机映射。在 总结了大量实验结果的基础上，针对任务间通信占用率较大的情况，本文提出了一种基 于任务预分配方式的新算法。 在实验中，本文对两种算法进行了实例分析和计算模拟，结果证明，两种算法都可 以得到预期的调度结果，在指定的条件下，新算法可以有效降低计算的复杂度。 最后本文对做出了工作总结，并对进一步的改进方向进行了简单讨论。 关键词：网格计算；异构；静态任务调度；动态关键路径；预分配； i i i ，i。，。 。 3产0 ，f ，0尹 1 查! ! 查堂塑主学位论文a b s n 粥t t i a s ks c h e d u l i n gr e s e a r c hb a s e do nt r e e b a s e dg r i d a l b s t r a c t w i t ht h en o 嘶s l l i l l go f 鲥dc o m p m i n gi nr e c e n ty e 躺，p e o p l eh 硒b e c l l 叫n gt 0 i n t e 黟a t et h eh e t e r o g e l l e o u sr e s o w c e sd i s 劬u t e d 躺l l i l dn l ew o r l d 缸oal l l l i f o 珊1 y c o m p u t i n gi n c t u r e f o ra 鲥dt 0 s u p p o r tav a r i e t yo fa 1 ) p l i c a t i o n sw i ml l i g l l p e r f 0 肌a n c e ，e 虢c t i v es c h e d u l i n go ft a s k si s 孤i m p o n a n ti s s u e ，锄db e c o m e so n eo fm e r e s e a r c hf o c u s e s c 0 n s i d 甜n gt 嬲kd a t ad 印e n d e n c e ，a n d l cl l l l c e r t a i l l t yo fm e 鲥d t o p o l o g y 嬲w e l la st h eh e t e r o g e i l e i 魄t a s ks c h e d u l i n gi n 鲥de n v i r o m e n tb e c o m e sm o r ed i 伍c u l tt h 锄 觚【d i t i o n a lp a r a l l e l t a s ks c h e d u l i n g t h ed i r e c t e da c y c l i cg r a p hm o d e l i sc o i i l 】m o n l yu s e di 1 1s t a t i cs c h e d u l i n go fa p a r a l l e l c o m p u t i n gp r o b l 锄，i l lw l l i c ht h en o d e sr 印r e s e n tm et a s k s 觚dm ed i r e c t e de d g e sr 印r e s 咖 t h ee x e c u t i o nd 印e i l d e n c i e sa sw e l l 嬲m e 锄o u mo fc o i i l 】m l l i l i c a t i o n t h ec r i t i c a lp a t hi sa l o n g e s tp a t hi nd a gw bm o d i f i e dm ed a gm o d e l ，u s e sl i s ts c h e d u l i n gt e c h l l i q u ew i t h d y l l 锄i c a l l yc r i t i c a lp a t ht or e d u c et h eo v e r a l lf i i l i s ht i m eo fap a r a l l e lp r 0 黟锄 t h i st h e s i sp r e s e n t sac o m p i l e - t i m es c h e d u l i n gh e 嘶s t i ca l g o r i t l 蚰i 1 1a 仃e e - b 弱e d 鲥d a r c h i t e c t u r e u s i n gt h ed a gm o d e lf i r s t ， w h i c ha c c o u n t s 矗md a t a d 印e n d e n c e粕d h c t e r o g e n e 时o fg i r do v e r h e a d ，t h i st e c h i l i q u eu s e sd y n 锄i c a l l y 嘶t i c a lp a t ht os e l e c tt a s k n o d e s ，a n de a r l i e s tf i n i s ht i m es t r a t e g yt om 印p i n gt a s k sw i mp r o c e s s o r sa te a c hs t 印b 勰e d o nt h i s ，w ed e v e l 叩e dan e wa l g o t l l i i lf o rt h eh i 曲c o m p u t i n gc o m m u i l i c a t i o nr a t es i t u a t i o n w i t ht a s kp r e c o l l o c a t em e m o d a r e rm es i m u l a t i o na 1 1 d a n a l y s i s ，w ef o u n dm a t ，t l l et 、oa l g o r i t l l l i l sc o u l dg e tt 1 1 e 觚t i c i p a t e ds c h e m ab o t h ，t h en e wa l g o r i t l l i i lc a nr e d u c et h ec o m p l e x 毋e 瓶c i e n t l yi np r o p e r e n v i r o n m e n t a tl 嬲t ，t h ed i s s e r t a t i o nc o n c l u d e sb y s u n l l n 撕z i n gt h er e s e a r c ha n di n d i c a t i n gi t s 觚u r e 蹄嚣 一v 人 东北大学硕士学位论文 丝型堕 _ _ - - _ _ - _ 一 k e y w o r d s ： 础dc o m p u t i n g ；h e t e r o g e n e o u s ；c o m p i l e t i m es c h e d u l i n g ；d y n 锄i cc r i t i c a l p a m ；p r e a 1 1 0 c a t e ； 骢j 1llj 东北大学硕士学位论文 目录 目录 独创性声明i ，摘要 a b s t r a c t v ， 第1 章绪论。1 1 1 课题背景和意义1 1 2 国内外的研究现状2 1 3 本文的主要工作3 1 4 本文的组织结构4 第2 章网格与任务调度5 2 1 网格计算5 2 1 2 网格的本质特征6 2 1 3 0 g s a 网格体系结构6 2 1 4 网格的五层结构7 2 1 2 网格发展现状9 2 2 网格调度问题1 0 2 3 两种任务调度技术1 3 2 3 1 表调度技术1 3 2 3 2 聚类技术1 5 2 4 网格计算中常见的任务调度算法1 6 第3 章树形网格任务调度模型研究1 9 3 1d a g 模型的引入19 3 2d a g 模型描述2 0 3 3 处理机描述2 4 3 3 1 处理机模型定义2 4 3 3 2 处理机拓扑结构2 4 v 东北大学硕士学位论文 目录 3 4 改进的d a g 模型3 0 第4 章树形网格任务调度算法3 3 4 1 关键问题分析3 3 4 2 一种基于动态关键路径的调度方法3 4 4 2 1 顺序选择d a g 图中的任务结点3 4 ； f 4 2 2 任务间消息在处理机之间路由与传递3 7l j 4 2 3 对所选择的任务结点进行处理机映射4 0 4 3 特定条件下对调度算法的改进4 4 第5 章实验及结果分析4 9 5 1 实验样例d a g 任务图模型和样例树形处理机结构4 9 5 2 算法4 5 调度实例5 0 5 3 算法4 6 调度实例5 6 5 4 两种调度算法实验总结5 8 第6 章结论6 1 参考文献6 3 致谢6 7 东北大学硕士学位论文 第l 章绪论 1 1 课题背景和意义 第1 章绪论 随着计算机通信带宽的不断增长，网络中接入的计算机数量日益增多。但h l t e n l e t 上有很多计算结点的使用效率并不高，大量计算机在多数时间内处于闲置或休眠状态， 或仅仅完成简单的文字处理工作。而另一方面，互联网上的内容每天都在飞速增长，不 可能有哪个单一的服务器或者搜索引擎能够掌握所有的资源，快捷、便利地为用户提供 所需的信息和计算服务。因此，需要一种新的技术来解决这些问题。网格就是这样的一 种技术，它是继h n 锄e t ，w 曲技术之后的第三次互联网技术浪潮。 网格计算【1 】作为当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的 研究课题，正越来越广泛的应用于科学、工程和工商业中。另一方面，高性能计算也已 经成为越来越多科学和工程和实践的关键技术，科学家们也越来越多地使用超级计算机 来研究复杂现象，例如可以用来预测复杂的非线性现象，或者是在做实验之前，就可探 索物理参数的变化规律，甚至还可以用来模拟现实世界中所发生的某些事件。然而，尽 管超级计算机的能力在不断地增长，仍然有许多应用无法实现。因为这些应用往往需要 处理能力强大的超级计算机的支持，但是超级计算机造价极高，通常只有一些国家级的 部门，如航天、气象等部门才有能力配置这样的设备；另一方面，某些应用对计算的要求 非常高，即使是现在最大的超级计算机也无法提供它们所需的资源，而网格计算为众多 闲置的计算资源提供了一种有效的共享方式，使得分布式资源给应用程序的使用者带来 了很多好处【2 】。网格系统部署涉及到不同种类的、地域上分散的、能够动态获取资源的 有效管理。 网格技术作为一种在更大范围的资源共享为目的的计算方式，它的实现需要计算机 网络和计算机技术的支撑。高性能计算技术和互联网技术迅猛发展和融合，实现了计算 机硬件和资源的连通，为网格的发展提供了技术支持。这样，当进行大数据量的计算或 对数据集进行大量重复分析操作时，就可以考虑利用网格技术共享互联网络上丰富的资 源【3 1 。 东北大学硕士学位论文第1 章绪论 在网格系统中，大量的上层应用共享着网格的各种资源。如何使得这些应用获得最 大的性能以及使得整个网格系统的效率达到最高，在很大程度上取决于它的调度者的有 效性和效率。良好的调度是实现高效使用共享资源的重要环节。通过调度，可以把应用 所需的计算隐藏于网格中，降低了上层应用的复杂性，使用户不必关心任务所需的计算 放在什么地方去执行从而把更多的精力投入到业务本身的开发中。对于一个调度系统，j 从应用的角度来说，用户关注的是它给应用带来的等待时间、执行时间等指标；而从系 i 一 统的角度来说，管理员关注的则是它导致的系统吞吐率、负载平衡等指标。这两方面的 指标有时候并不能达到完全一致，这就给网格调度带来了多种可能性。网格调度技术非 常复杂最主要的原因是网格具有一些独有的特征，例如，网格资源的动态变化性、资源 的类型异构性和多样性、调度器的分布和局部管理性等。在网格调度中，还需要考虑移 植性、扩展性、效率、可重复性以及网格调度和本地调度的结合等一系列问题【3 】。 传统的并行计算调度算法主要是调度一个应用程序的子任务到并行的计算机，主要 目的是减少计算时间；而对于网格环境，当前调度算法关心的主要问题是调度来自不同用 户的应用流到可用的计算资源上，从而最大限度地让网格系统得到最大的使用，它追求 的是调度的高吞吐率。另一方面，网格调度在本质上比局部调度复杂，因为网格调度要 面向跨管理域的大范围的资源，而且在网格这样的动态分布式计算环境资源可用性变化 常常出乎意料，所以网格环境中的调度很有难度。作为目前网格计算事实上的标准， g 1 0 b u s 并没有具体实现任务调度算法，针对具体的应用网格，必须在高层设计出高效的 任务调度算法。 1 2 国内外的研究现状 下面介绍几种在基于网格的资源管理和作业调度中广泛使用的调度系统 ( 1 ) c 0 n d o r l 4 1 。c o n d o r 是一个资源管理和作业调度系统，用来管理计算密集型的 任务的批处理队列。它是通过提供一个高吞吐量的计算( h t c ) 环境实现的。h t c 环境在 为这些任务提供高吞吐量的同时，可以有效且最好地利用所有的可用资源。它提供了传 统的队列和调度功能。在典型的使用情景中，用户将任务提交给c o n d o r ，它会对任务进 行排队并监视，然后在任务完成时将结果表示出来。c o n d o r 不仅在这种环境中工作得很 好，而且它也可以通过利用这些资源空闲时的空闲周期从而有效地管理非专用的资源， 一2 一z 东北大学硕士学位论文第1 章绪论 可以把这个称为时钟周期节余。 ( 2 ) l s f 【5 】。l s f 是一个资源管理和工作负载调度系统，由p l a t f o 吼c o n 州i n g c o r p o r a ：t i o n 开发。这个系统可以利用台式电脑、服务器和大型机等在内的计算资源，来 确保获取资源的优先权服务级。l s f v 6 支持一系列的计算机体系结构和操作系统，包括 h p ，m m ，i n t e l ，s u n 和n e c 等。一个l s f 集群有一个主主机和若干个执行主机。主主 机是整个集群的中心协调者。它负责作业的调度和分配，执行主机用来执行作业，一旦 主主机出现故障，集群中的另一个l s f 服务器将变成主主机。 ( 3 ) n i 眦o d 【6 】。由于网格的异构性，其资源可能被不同的个人或组织拥有，从而 具有不同的管理策略、访问成本以及动态变化的性能。n i n 啪d 系统的主要目标就是在 保证用户需求得到满足的条件下为用户提供最经济的计算模式。为了达到这个目的， n i m r o d 系统采用了d e a dl i n ea i l db u d g e tc o n s 仃a i n e d ( d b c ) s c h e d u l ea l g o r i t h m ，此算法根 据用户任务对于完成时间以及花费预算的要求对任务进行调度。 ( 4 ) a p p l e s 【7 1 。a p p l e s 是在网格中间件( 如g 1 0 b u s ) 之上开发的网格调度系统，每 一个提交给网格的应用都有自己的a p p l e s 。a p p l e s 的设计哲学是系统性能和利用的所 有方面都起源于使用系统对应用的一种预见。为了取得应用效果，a p p l e s 对特定资源 点上的应用性能进行度量，并利用这种信息来进行资源选择和调度安排，来实现它的将 任务以最有效的方式调度到资源上的目标。 1 3 本文的主要工作 本文研究了网格调度的原理、特点、组织结构和调度过程，对网格调度进行了详细 的分析和探讨，并提出自己的观点。具体内容如下： 首先对现有的调度算法进行了比较分析，引入了d a g 任务调度模型及动态关键路 径方法和最早完成策略。然后根据本文需要修改了网格调度过程中d a g 任务模型及动 态关键路径中的相关定义。 其次提出了一种新的异构树形网格下的调度方法，该算法考虑到了网格的异构性和 d a g 任务模型任务图中的数据依赖，利用基于动态关键路径的启发式策略，可以得到 较好的性能。 在对调度结果的分析后，提出了在某些特定条件下对算法的进一步改进，以全局规 3 东北大学硕士学位论文笫1 章绪论 划预分配的思想和降低计算复杂度的目的，在第一种算法的基础上进行了优化。算法的 每一个步骤都进行了深入的比较、分析和设计，力图使算法在找到近似最优解的同时能 获得更好的收敛速度。 最后采用两种算法对d a g 实例进行了实际调度和分析，结果表明，两种算法获得 了很好的效果，达到了预期的目标。 1 4 本文的组织结构 本文共分为六章。其中第三章，第四章，第五章为本文的研究重点。 第一章绪论介绍了课题背景和意义，阐述了网格计算的概念，并指出了国内外网格 计算的发展趋势，并指出了本文的组织结构。 第二章详细说明了网格计算的历史发展与本质特征，并介绍了o g s a 五层网格体系 结构，提出了任务调度在网格计算中的具体意义，并对常见网格任务调度算法进行了比 较。 第三章主要阐述网格任务调度中的d a g 任务模型和处理机模型。d a g 模型在并行 计算中已有广泛应用，文中给出了d a g 模型和非完全互连处理机模型的定义与描述， 并为使用结合动态关键路径的表调度技术对传统的d a g 模型做了修改。 第四章分析了树形网格任务中的关键问题，即如何顺序选择任务结点，消息在处理 机之间路由传递，如何进行处理机映射。文中对三个问题提出了解决方案，提出了一种 基于动态关键路径和最早完成时间策略的任务调度算法，经过总结与分析，在此基础上 提出了在计算通信比较低的情况下一种新的启发式算法。 第五章为算法的验证与实验部分，首先通过对实例的调度详细说明了两种算法的调 度步骤，然后并根据实验结果对两种算法进行了总结。 第六章为全文工作的总结部分，并对以后的工作方向做出了展望。 4 东北大学硕士学位论文第2 章网格与任务调度 2 1 网格计算 第2 章网格与任务调度 网格这一术语于2 0 世纪9 0 年代中期提出，用来表述一种适用于高端科学和工程的 ，分布式计算体系结构。当前在建设这种基础设施以及它的扩展和将其应用于商业计算方 面都取得了很大的进展。 网格计算技术产生的背景是计算应用对计算机资源和计算能力不断增长的需求。当 单台计算机系统不能满足应用的需求时，就需要使用其它计算机系统的资源。一方面， 由于超级计算机系统非常昂贵，不可能增加新的超级计算机作为这个应用的专用系统； 另一方面，即使可以使用其它超级计算机的资源，由于应用系统不具备通用性，因此不 可能直接利用这些计算资源。网格计算系统的出现为解决上述的问题提供了新的途径。 在计算机发展初期，人们就已经认识到了分布式计算的重要性，而且在计算机发展 过程中一直试图在系统各个层次上利用分布式计算。然而，由于技术条件和应用范围的 限制，分布式计算没能成为主流。近年来，人类的应用对计算机提出了越来越高的要求。 如在科学、工程及商业领域，还有许多问题，由于其规模和复杂性，这些计算密集和数 据密集的问题需要由多台计算机上的异构资源来协同解决。因此，分布式计算受到了特 别的关注。另外一方面，近十年来，由于更快的计算机硬件与更复杂的计算机软件的出 现，计算机和网络的性能得到了极大的提高，为分布式计算提供了技术和物质基础。 网格的概念来源于随时随地地提供电能的电力网格( e 1 e c t r i cp o w e r 嘶d ) ，它像计算 机和其他科技进步的产物一样，对人类的能力和社会有着巨大影响。提出网格的目的就 是能够使得人们在使用网格资源的时候，能够像使用电力资源一样，自由使用，网格也 希望给最终用户提供的是与地理位置无关，与具体的计算设施无关的通用的计算能力。 它的目标是实现网络虚拟环境上的高性能资源共享和协同工作，消除信息孤岛和资源孤 岛。网格的作用是将分散在网络上的信息及信息存储、处理能力以合理的方式“粘合” 起来，形成有机的整体，以提供比任何单台高性能计算机都强大得多的处理能力，实现 信息的高度融合和共享。 _ 5 东北大学硕士学位论文第2 章网格与任务调度 狭义网格中网络资源主要是指分布的计算机资源，因而狭义网格一般被称作为计算 网格，即主要用于解决科学与工程计算问题的网格。 网格的广义定义是一个集成的计算与资源环境，或者说是一个计算资源池。网格能 够充分吸纳各种计算资源，并将它们转化成一种随处可得的、可靠的、标准的同时还是 经济的计算能力。这里的资源除了各种类型的计算机，还包括网络通信能力、数据资料、 仪器设备、甚至是人等各种相关的资源。 d 网格研究的权威i 锄f o s t e r 把网格定义为“在动态变化的多个虚拟机构间共享资源 和协同解决问题 。大多数网格研究者认为这就是网格。在这里，网格的本质就是共享 与协同。所谓网格计算系统则是指通过高速网络连接，由地域分布的动态计算资源构成 的网络虚拟超级计算机系统【1 】。 2 1 2 网格的本质特征 网格的本质特征是： ( 1 ) 分布与资源共享：分布是网格最本源的特征，网格是通过集中分散的资源来 完成计算的，资源的共享是一种集中资源的手段 ( 2 ) 高度抽象：把计算力和所有的计算资源高度抽象成为用户可见的“电源接线 板”，其它的东西对用户透明。 ( 3 ) 自相似：在大尺度上和小尺度上有相同或者类似的规律 ( 4 ) 动态性和多样性：和电力网格一样，用户的需求是变化的，所以动态性是网 格需要考虑的一个基本问题 ( 5 ) 自治性与管理的多重性：网格结点内部的自治和外部的受控整合是网格的一 个特征，分层的资源需要层次化的管理，而分层来自于网格结点的归属问题和性能方面 的考虑。 2 1 3 0 g s a 网格体系结构 网格计算目前比较重要的体系结构是i a l lf o s t e r 等提出的5 层沙漏体系结构和结合 w 曲s e n ，i c e 的歼放网格体系结构o p e i l 嘶ds e r v i c e sa r c l l i t e c t i l r e 。w s r f 草案规范于 2 0 0 4 年年初推出，可以看作是o g s a 的进一步发展，但目前对其标准的讨论仍存在一 - 6 东北大学硕士学位论文第2 章网格与任务调度 些争议。5 层沙漏中强调以“协议 为中心，主要侧重于定性的描述，o g s a 以“服务” 为核心，定义了网格服务( 僦ds e i c e ) 的概念。w r e b 服务资源( w s r e s o u r c e ) 结构 是表示有状态资源和w 曲服务之间的关系的方法。后两种体系结构的基本思想都是将 网格中的各种计算资源抽象为虚拟组织，各个虚拟组织通过网格服务连接起来构成虚拟 的网格环境。近来，网格体系结构又出现了一个新的发展趋势：w s i 江( w 曲s e n ，i c e r e s o u r c ef r 撇e w o r k ，w 曲服务资源框架) 【8 】ow s i 心草案规范于2 0 0 4 年年初推出，可 以看作是o g s a 的进一步发展，但目前对其标准的讨论仍存在一些争议。虽然此规范出 现较晚，也还没有得到正式认同，但其中一些思想还是很值得我们借鉴。w 曲服务资源 ( w s r e s o u r c e ) 结构是表示有状态资源和w 曲服务之间的关系的方法。w 曲服务资源 框架是一组被提议的w 曲服务规范，它根据特定的消息交换和相关的讧l 定义来定义 w 曲服务资源方法的描述。这些规范使程序员可以声明和实现w 曲服务和一个或者多 个有状态的资源之间的关联。它们描述了定义资源状态的视图以及将它与w 曲服务描 述相关联来形成w 曲服务资源的总的类型定义的方法。它们也描述了如何通过w 曲服 务接口来访问w 曲服务资源的状态，并且定义了与w 曲服务资源分组和寻址相关的机 制。 综上所述，这两种体系结构的基本思想都是将网格中的各种计算资源抽象为虚拟组 织，各个虚拟组织通过网格服务连接起来构成虚拟的网格环境。与传统的分布式计算环 境相比，网格计算环境具备了更高的可管理性与自治性。 2 1 4 网格的五层结构 i a i l f o s t e r 于2 0 0 1 年提出了网格计算协议体系结构，认为网格建设的核心是标准化 的协议与服务，按照网格结构中各组成部分与共享资源的距离，将对共享资源进行操作、 管理和使用的功能分散在五个不同的层次。如图2 1 。 东北大学硕士学位论文 第2 章网格与任务调度 工具与应用应用层 诊昙篡 汇聚层 乡。资源与服务 旋源与 i 的安全访秘 l 连接层 程趴 构造层 图2 1 网格的五层体系结构 f i g 2 1f i v el a y e r sg r i d 觚h i t e c h 鹏 构造层( f a b r i c ) ：控制局部的资源。由物理或逻辑实体组成，目的是为上层提供共享 的资源。常用的物理资源包括计算资源、存储系统、目录、网络资源等。逻辑资源包括 分布式文件系统、分布计算池、计算机群等。构造层组件的功能受高层需求影响，基本 功能包括资源查询和资源管理的q o s 保证。 连接层( c o n n e c t i v i t y ) ：支持便利安全的通信。该层定义了网格中安全通信与认证授 权控制的核心协议。资源间的数据交换和授权认证、安全控制都在这一层控制实现。该 层组件提供单点登录、代理委托、同本地安全策略的整合和基于用户的信任策略等功能。 资源层( r e s o u r c e ) ：共享单一资源。该层建立在连接层的通信和认证协议之上，满 足安全会话、资源初始化、资源运行状况监测、资源使用状况统计等需求，通过调用构 造层函数来访问和控制局部资源。 汇集层( c o l l e c t i v e ) ：协调各种资源。该层将资源层提交的受控资源汇集在一起，供 虚拟组织的应用程序共享和调用。该层组件可以实现各种共享行为，包括目录服务、资 源协同、资源监测诊断、数据复制、负荷控制、账户管理等功能。 应用层( a p p l i c a t i o n ) ：为网格上用户的应用程序层。应用层是在虚拟组织环境中存 在的。应用程序通过各层的应用程序编程接口( a p i ) 调用相应的服务，再通过服务调 动网格上的资源来完成任务。为便于网格应用程序的开发，需要构建支持网格计算的大 型函数库。 东北大学硕士学位论文第2 章网格与任务调度 2 1 2 网格发展现状 目前国内外网格研究已经成了一个热点，具有代表性的研究项目和成果主要有 g 1 0 b u s ，l e 西o n ，n i n 啪d o ，n e t s o l v e 和c o n d o r 等。 g 1 0 b u s 是美国多家研究机构的合作项目，g 1 0 b u s 的核心是一个工具集，包括一组执 行基本服务的组件，如安全控制、资源获取、资源管理、资源预约、数据管理和通信等， 向用户应用提供分布异构资源的一个虚拟机。g 1 0 b u s 最初只支持计算网格，现在也支持 数据网格。g 1 0 b u s 提供了调度组件作为其工具集的一部分但没有提供具体的调度策略， 依赖高层调度器执行任务调度，很多调度器中间件如n i m r o d g 、a p p l e s 和c o n d o r 都 是基于g 1 0 b u s 服务开发的。 l e 百o n 是美国维吉尼亚大学研究的基于面向对象的网格操作系统，提供资源预约和 应用级的周期任务调度或批任务调度。l e 西o n 资源管理结构是分层结构的，支持分散的 调度策略，并支持通过资源代理进行调度策略的扩充，因此可以用n i i n r o d g 和a p p l e s 等应用级调度器代替l e 百o n 的默认调度策略。澳大利亚莫那西大学开发的计算和服务 网格n i i n r o d g ，利用网格系统如g 1 0 b u s 或l e g i o n 进行资源发现，通过网格资源代理 g r a c e ，利用微观经济模型对网络资源进行管理和调度，支持资源预约和基于微观经 济模型的q o s ，通过周期性重调度实现系统的负载平衡。 n e t s o l v e 是一种基于客户一代理一服务器结构的服务网格，由代理执行信息存储与维 护、资源发现和资源调度，客户端支持c ，f o r t i 乙埘，m a ：r l 蛆和网页应用程序。n e t s o l v e 的目标是提供简单易用的客户端，隐藏并行处理的复杂性，由服务器端支持各种科学计 算服务。 c 0 n d o r 是美国威斯康星大学开发的一个高吞吐量的计算环境，可管理分属于不同机 构的大量p c 机、工作站以及集群，以利用闲散c p u 周期著名，每个机器上运行的资源 代理周期性广播其可提供服务，客户代理广播其需求，匹配器执行任务到资源之间的调 度。 中科院计算所正在进行“织女星计划( v e g a 计划) 【9 1 ，其目标是具备以下几种能 力：大规模的数据处理能力、高性能计算能力，以及具备资源共享和提高资源利用率的 能力。与国内外其它网格研究项目相比，“织女星网格 的最大特点是“服务网格”( s e r v i c e 9 东北大学硕士学位论文第2 章网格与任务调度 例d ) 的概念。而服务网格有三个要点：第一，它是一种通用网格，不只是支持科学计 算，还支持其它服务，包括通信服务、数据服务、信息服务、计算服务、交易服务等等； 第二，服务是基本的应用模式，即客户端向网络发出服务请示，网格完成服务，并将结 果通知客户端；第三，网格的主要评价标准不单纯是计算速度等传统指标，而是类似“服 务等级协议( s e n ，i c el e v e la g r c e m e n t ) 这样的一套用户满意度或服务质量评价标准。 当前国内外重要网格应用研究项目包括：亚太地区网格a p g r i d 【1 0 】( 缸i ap a c i f i c g r i d ) ，美国n a s a 网格d g 【1 1 1 ( h l f o m a t i o np 0 w e r 嘶d ) ，欧洲数据网格d a t a 饲d 【1 2 】， 欧洲网格e u r 0 g r i d 【13 1 ，全球信息网格g i g 【1 4 】，美国n s f 网格t e r a g 衙d 【1 5 】，德国网格 d e u t s c h l a n d 嘶d d 一( 证d 【1 6 1 ，国家网格c n g r i d ( 科技部8 6 3 计划) ，中国教育科研网 格计划c h i n a 嘶d ，e s c i e n c e 网格研究计划( 国家基金委) ，中国空间信息网格，上海城 市信息网格，等等。可见，网格计算的应用已经引起了世界各国的高度重视。 2 2 网格调度问题 任务调度是网格计算中一个至关重要的问题，其算法将直接影响到网格环境中任务 执行的效率。用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照 某种策略把这些任务分配给合适的资源。高效的调度算法可以充分利用网格系统的处理 能力，从而提高应用程序的性能。由于网格计算是个新的研究领域，在网格环境里如何 有效地调度计算任务是影响网格计算是否成功的最重要因素之一。 如图2 2 ，分布式系统的问题求解过程大致分为四个步骤【l 8 】： ( 1 ) 任务分解：把一个大任务划分为可并行执行的相关的子任务的过程。 ( 2 ) 任务调度：将这些子任务分配到各个并行处理机上，并安排处理机上子任务 的执行次序的过程。 ( 3 ) 并行运算：子任务在被分配的处理机上进行并行通信与运算的过程。 ( 4 ) 解的合成：将子任务的运行结果结合成为整个大任务的运行结果。 其中，任务调度这一步骤对发挥系统的并行运算能力，提高系统吞吐量具有非常重 要的影响，良好的任务调度算法可以充分运用系统中每个处理机的计算能力。 一l o 东北大学硕士学位论文第2 章网格与任务调度 成 任务分解 i 任务调度 山 麓圜 # 行运笪 图2 2 分布式系统调度示意图 f i g 2 2t 勰ks c h e d u l i n gi i ld i s 仃i b u t e ds y s t e m s 一般情况下，多处理机系统的实际性能总是要小于其峰值性能，主要原因是【1 9 】： ( 1 ) 单处理机并不能总以其峰值性能运行。 ( 2 ) 处理机之间通信引起的开销。 ( 3 ) 不同处理机数据同步等待带来的开销。 ( 4 ) 负载不均衡使某些处理机处于空闲状态。 针对以上原因，对于某一个具体应用，为了充分发挥多处理机系统的性能需要解决 的问题有两个，一是如何对应用进行划分，使得程序的划分粒度与处理机系统的粒度相 匹配，该问题是程序划分和任务划分问题，二是任务调度问题，即如何将划分后形成的 子任务调度给合适的处理机去执行，以便使整个应用的执行时间最短。 程序划分问题一直是并行计算领域中待进一步解决的问题，目前，程序划分可以是 手工进行，也可以计算机自动完成，也可以人机交互进行划分，计算机自动进行程序划 分需借助编译手段来实现，用编译的方法划分程序基本上局限于循环的分割，人机交互 进行程序划分可能是今后主要的研究方向2 0 1 。程序划分问题不是本文讨论的重点，这里 仅作一般性介绍。 调度问题的分类如图2 3 ： b r 酾 东北大学硕士学位论文第2 章网格与任务调度 图2 3 网格调度分类 f i g 2 3c l a s s i f i c a t i o no ft a s ks c l l e d u l i n g 本地调度是处理机上运行的操作系统按照一定的规则将处理机的时间片分配给本 地的过程，本地调度仅针对一台处理机，而全局调度则是针对整个多处理机系统，按照 调度时机的不同，全局调度又分为动态调度和静态调度。 动态调度( d y l l 锄i cs c h e d u l i n g ) 是在运行时刻实现的。动态调度和核心是进程迁移 0 r o c e s sm i 酬i o n ) ，既应当有某种策略来保证如何将任务从负载比较重的处理机迁移到 负载比较轻的处理机【2 l 】，通常，典型的动态负载平衡算法包含三个策略： ( 1 ) 信息策略( h l f 0 1 1 n a t i o np o l i c ”在运行时，动态地收集每台处理机上的负载信息， 这些信息的获取对于传送策略与放置策略的实现是必须的，收集的负载信息可以集中到 一台处理机( 对应着集中式任务调度) 或分布到多台处理机上( 对应着分布式任务调度) 。 ( 2 ) 传送策略( t r 觚s f e rp o l i c y ) 针对每个处理机，确定负载上下阀值条件。当处理 机上的负载指数( 1 0 a di n d e x ) 超出上阀值时，该处理机处于过载状态，应将某个任务传送 给负载较轻的处理机；当处理机上的负载指数小于下阀值时，该处理机处于轻载状态，可 以接受来至其他处理机上的任务。注意，某个处理机所对应的上、下负载阀值应随着整 个系统负载的变化而做出相应的调整。 ( 3 ) 放置策略( p l a c e m e mp o l i c ”指明迁移的任务应放置到哪一台处理机上去。由于 动态调度本身引起的开销很大，这种调度方法主要用来提高整个系统的吞吐率。 本文将不再对动态调度做进一步的讨论，如不做声明，下文中的调度均指静态调度。 对于静态调度，任务分配给处理机是在程序执行之前完成的。有关任务的计算量、 1 2 t ， 一 东北大学硕士学位论文第2 章网格与任务调度 任务之间的依赖关系及通信情况，每个处理机的处理能力以及它们之间的互连拓扑在编 译时假定是己知的。一个任务一旦分配给某个处理机，便只能在该处理机上执行，即任 务的执行是非抢占式的在静态任务调度中，为了便于问题的研究，总是将具体的应用抽 象成有向无环任务图，同时将多处理机系统抽象成处理机模型。在有向无环任务图中， 结点表示任务，结点之间的有向边表示任务之间的数据流动。静态任务调度解决的问题 归结为：如何将任务调度给合适的处理机去执行。一般而言，静态调度的目标是最小化整 个应用的执行时间( m a l 【e s p a n ) 。 2 3 两种任务调度技术 任务调度中最常用的调度技术有两种，即表调度技术与聚类技术，目前，任务调度 中的绝大多数算法的设计都是基于这两种技术。 2 3 1 表调度技术 表调度技术是多处理机任务调度中最重要的调度技术，它总是按照任务图的拓扑顺 序，按照一定的优先级规则，从上至下的调度任务2 2 1 。 所谓表调度技术，就是在任务调度时，需要创建一个任务优先级表( t a s kp r i o r i t yl i s t ) 。 在该表中，前面结点的优先级高于后面结点的优先级，这种任务优先级列表既可以静态 地创建，也可以动态的创建。如果在调度之前，预先计算出每个任务结点的优先级，然 后根据每个结点的优先级大小将结点插入到列表中，这种任务优先级表