（通信与信息系统专业论文）基于时间均衡的自适应网格任务调度机制研究.pdf

重庆邮电大学硕士论文 摘要 摘要 网格计算技术是当前国内外通信领域研究的热点之一。而网格任务调 度是其提高任务运行性能、实现网格资源共享的关键技术之一，它以一定 的优化目标为指导，通过合理的匹配网格资源和网格任务，将任务调度到 资源上运行。这是网格领域一直以来研究的核心和难点。 本文详细分析了计算网格模型尤其是网格资源及网格任务调度的特 征，并针对计算网格中大量独立或松耦合的任务( 称为任务放牧) 进行调 度的这一类应用，提出一种基于时间均衡的启发式调度方法，使任务分解 后在资源上期望完成时间点相同，以此来提高任务的完成速度，提高系统 吞吐率，同时使任务得到有效调度，资源得到有效利用。同时在此基础上， 综合考虑了资源的负载、本地任务和远程任务的区别、远程任务的优先级 以及调度但未执行的任务进行重新调度的优先级等因素，使本调度机制相 比于其他机制更接近于实际应用状况，将为日后进行大规模任务调度、信 息处理提供参考。 在本文最后进行了仿真实验，就任务完成时间、系统吞吐率、紧急任 务的优先调度等方面与m a x m i n 算法和m a x i n t 算法进行了比较。实验结 果证实了a t b b s 算法在缩短任务完成时间，提高系统吞吐率，给紧急任 务以优先调度等方面具有更好的优越性，是一种性能较好的任务调度算 法。 关键词；计算网格，任务调度，时间均衡，性能预测，自适应因子 重庆邮电大学硕士论文摘要 a b s t r a c t g r i dc o m p u t i n gt e c h n i q u ei sah o ts p o ti nc u r r e n td o m e s t i ca n df o r e i g n c o m m u n i c a t i o nr e s e a r c hf i e l d g r i ds c h e d u l i n gt a k e sc e r t a i no p t i m i z e dg o a la s t h ei n s t r u c t i o n g r i ds c h e d u l i n g ，i n s i d eo fi t ，i so n eo fi t sk e yt e c h n i q u e sw h o i m p r o v ei t sp e r f o r m a n c eo ft a s ke x e c u t i o na n dr e a l i z ei t st a r g e to fr e s o u r c e s h a r i n g g u i d e db ys o m eo p t i m a lt a r g e t s ，g r i ds c h e d u l i n gd e p l o y st a s k so n r e s o u r c e st h r o u g hr e a s o n a b l ya l l o c a t i n gr e s o u r c e sa n dt a s k s t h a ti st h ek e r n e l a n dd i f f i c u l t yo fr e s e a r c h e so ng r i d i nt h i sp a p e r ，c o m p u t i n gg r i dm o d e l se s p e c i a l l yf e a t u r e so fr e s o u r c e sa n d t a s ks c h e d u l i n gi nt h e s em o d e l sa r ea n a l y z e di n d e t a i l s ，a n dah e u r i s t i c s s c h e d u l i n ga l g o r i t h mb a s e do nt i m e b a l a n c e ，n a m e l ya d a p t i v et i m e b a l a n c e b a s e ds c h e d u l i n g ( a t b b s ) ，i sa d v a n c e dw h i c ha i m e da ts c h e d u l i n gal a r g e n u m b e ro fi n d e p e n d e n ta n dl o o s ec o u p l e dt a s k si nc o m p u t i n gg r i d t h e a l g o r i t h me q u a t e st h ee x p e c t e df i n i s ht i m eo fe a c ht a s kd e c o m p o s e d ，w h i c h s p e e d sa c c o m p l i s h m e n to ft a s k s ，i m p r o v e st h r o u g h p u to fs y s t e m ，s c h e d u l e s t a s k sa n du s e s r e s o u r c e sa f f e c t i v e l y m o r e o v e r ，f a c t o r ss u c ha sl o a do f r e s o u r c e ，d i f f e r e n c ei nl o c a lt a s k sa n dr e m o t et a s k s ，p r i o r i t yo fr e m o t et a s k s a n dr e - s c h e d u l i n gt a s k ss c h e d u l e db u tu n e x e c u t e d ，a r ec o n s i d e r e ds ot h a tt h e a l g o r i t h m i sc l o s e rt oa c t u a l a p p l i c a t i o n i t w i l lo f f e rar e f e r e n c ef o r s c h e d u l i n gt a s k sa n dd e a l i n gi n f o r m a t i o nc o s m i c a l l y t h r o u g hs i m u l a t i o n ，a t b b sa l g o r i t h mi sc o m p a r e dt o m a x - m i na n d m a x i n ti nf i n i s ht i m e ，s y s t e mt h r o u g h p u ta n dp r i o r i t yo fu r g e n tt a s k s t h e r e s u l tp r o v e st b b sa l g o r i t h mi ss u p e r i o ri nt h e s ea s p e c t s k e yw o r d s ：c o m p u t i n gg r i d ，t a s ks c h e d u l i n g ，t i m e - b a l a n c i n g ，c a p a b i l i t y f o r e c a s t ，a d a p t i v eg e n e i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞 邮直太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：凌缸签字日期：扣了年6 月g 日 学位论文版权使用授权书 本学位论文作者完全了解重废邮电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重废邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文 签字日期 三：m 名：闰彳 ：明年月吕日签字日期；明年厂二矿日 重庆邮电大学硕士论文第一章绪论 第一章绪论 网格计算资源具有多方面的异构性，非常适合具有多种内在并行性的 应用执行。计算网格主要目标之一就是为拥护高效的应用程序的执行环 境，并将应用程序调度到异构的计算节点上运行。获得最优或近优的性能 指标是应用调度模型研究的目标和方向。 本章简要地阐述了网格的基础知识、网格的起源和发展状况、网格任 务调度的基础知识及其研究状况，在此基础上提出了本文的基本思想，并 介绍了本文的主要工作与全文的组织结构。 1 1 研究背景 1 1 1 网格基础知识 网格( g r i d ) “耵技术起源于2 0 世纪9 0 年代初由美国政府资助 的分布式超级计算( d i s t r i b u t e ds u p e r c o m p u t i n g ) 项目i - w a y 。从1 9 9 3 年 开始，高性能计算技术和互联网技术进一步融合，酝酿产生了继因特网、 w e b 之后的第三大技术浪潮。“网格”这一术语的思想则起源于日常生活中 公共设施的应用，伊恩福期特出版的著作中最早将它称之为“网格”。 网格不仅支持旨在聚合计算资源的高性能科学计算，而且支持分布式 资源的协作与共享：不仅综合了对科学计算、并行计算以及工程计算等各 种业务的支持，即解决计算密集型的重大挑战性的问题，同时还构成事务 处理、信息交流、电子商务、远程医疗、数字图书馆等新型应用的基础， 因此网格技术成为当前计算机科学领域研究的一个热点。 目前，高性能计算已经成为许多科学和工程实践的关键技术，科学家 们也越来越多地使用巨型计算机来研究复杂现象。然而，巨型计算机的造 价极高，那些需要强大处理能力的应用仍然无法实现。另一方面，某些应 用对计算的要求非常高，即使是现在最大的巨型计算机也无法提供它们所 需的资源。 然而据估计，全球大型超级计算机系统在大量的时间内( 约6 0 ) 处 于闲置状态，u n i x 家族服务器也只有3 0 左右的时间在处理用户应用，而 个人桌面计算机则每天有一半以上的时间处于关机状态。另据一些专业媒 重庆邮电大学硕士论文第一章绪论 体披露，网络上的大量工作站和服务器的利用率也仅仅使用了其2 0 左右 的能力；就象科研院这样使用计算机频率高的单位，其计算机及其资源的 利用率也仅为2 5 左右。 要使大量闲置资源能够得到充分利用，这就需要将高性能计算依托 i n t e r n e t 或其他高速网络与遍布世界各个角落的能力千差万别的计算资源 联结在一起，形成大规模的几乎可以无限扩展的计算能力。网格计算就是 在巨型机与互联网技术的基础上推出的一项新的变革，将对全世界的i t 业产生巨大的震动和飞跃。 与传统的分布式并行计算不同，网格计算不再要求各种服务资源位于 单一组织拥有和管理的统一自治系统中，参加协作的各方共同构成一个虚 拟组织( v i r t u a l o r g a n i z a t i o n ，v o ) ，可以使用跨越多个自治系统的资源，协 同完成工作。网格研究的目标也越来越大，研究人员希望提供一种能够聚 集网络上的各种高性能计算机、服务器、p c 机、信息系统、海量数据存储 和处理系统、应用模拟系统、虚拟现实系统、仪器设备和信息获取设备以 及服务和研究人员等广泛分布的各种资源，作为进行大规模计算和海量数 据处理的通用基础支撑结构，为各种应用开发提供底层技术支持，将整个 i n t e r n e t 变为一个功能强大、无处不在的计算设施。 进入二十世纪九十年代，网格应用领域不断扩展。许多现代大型科学 研究和信息服务对高性能和大容量数据处理的能力需求增加，许多应用具 有高性能计算和海量数据存储、传输和分布处理相结合的特性。网格技术 研究范围迅速扩大，根据求解问题的特点，可以分为计算网格 ( c o m p u t a t i o n a lg r i d ) 、数据网格( d a t ag r i d ) ，信息网格( i n f o r m a t i o n g r i d ) 、 知识网格( k n o w l e d g e g r i d ) 、语义网格( s e m a n t i c g r i d ) 、访问网格( a c c e s s g r i d ) 等方向，其应用层面也大大扩展。 1 1 2 计算网格与任务调度 在网格技术当中，计算网格坤，成为目前网格计算技术研究最深和实践 最多的一种网格，甚至被认为是狭义的网格。它主要针对前沿科学研究和 大型行业应用，可共享和整合地理上分布的计算资源”1 。目标是发展遵循 开放标准，提供支持大规模分布合作计算和数据处理的基础计算设施。 计算网格是提供对高计算能力进行可靠、一致、深入并且廉价访问的 软、硬件基础”“。科学计算仍然是当前计算机的主要应用之一，但计算机 的能力并没有得到充分发挥。单台、孤立的计算机的求解能力是有限的， 2 重庆邮电大学硕士论文第一章绪论 通过搭建网格计算环境可以使多台计算机资源共享，协同进行问题求解， 从而为用户提供更高的计算能力，解决更复杂的问题，这就是计算网格追 求的目标。 作为一种为大型、复杂应用而设计的新兴技术，计算网格需要能够很 好地支持高性能需求和分布特性。为了更好地为网格用户提供高质量、安 全的计算服务，计算网格必须解决资源发现与管理“、任务调度“”“”、 安全“”、容错“”等一系列关键技术。 计算网格中，有大量的应用存在，这些应用又共享计算网格的各种资 源，如何才能够使这些应用获得较高的运行性能? 这就是网格任务调度需 要解决的问题。 用户通过任务管理系统向网格提交任务、为任务指定所需资源、删除 任务并监测任务的运行状态。将用户提交的任务按照任务的类型、所需资 源、可用资源等情况安排运行日程和策略，实现计算网格共享地理上分布 的资源协同完成某个任务的目标，是任务调度首要而基本的功能“。 网格计算环境的强大能力最终是通过网格上任务的运行性能来体现 的。为获得较高的运行性能，需要较优化的调度策略，以便在任务和资源 之间做出合理匹配，并可在运行过程中动态调整，既要达到对任务合理而 高效的调度和运行，也要充分、有效利用分布的资源。网格任务调度是一 个极其复杂的问题，因为网格中包含大量分布、异构的资源，而且资源的 状态是动态变化的，多个任务可能会引起资源竞争，如何充分、合理地利 用网格中的计算资源是调度的研究范畴。由于网格计算任务调度面临的是 一个n p 完全问题，它引起了众多学者的关注，成为目前网格计算研究领 域的一个焦点。“。”。 1 1 3 国内外网格计算项目简介 计算网格具有重要的战略意义及广阔的应用前景，许多国家、组织都 纷纷对其开展了深入研究。目前，网格的研究主要在美国和欧洲。英国政 府已投资l 亿英镑，用来研制“英国国家网格( u k n a t i o n a l g r i d ) ”。美 国政府用于网格技术基础研究经费则已达5 亿美元。美国军方正规划实施 一个宏大的网格计划，叫做“全球信息网格( g l o b a li n f o r m a t i o ng r i d ) ”， 预计在2 0 2 0 年完成。作为这个计划的一部分，美国海军和海军陆战队已 启动了一个耗资1 6 0 亿美元历时8 年的项目，包括系统的研制、建设、维 护和升级。随着网格研究在学术界的加速，信息产业界的大公司也相继公 3 重庆邮电大学硕士论文第一章绪论 布了与网格目标一致的研究开发计划。惠普、i b m 、微软、s u n 等公司最近 取得共识，支持x m l 、s o a p 、u d d i 等万维网标准，从而更有利于开发 新一代的网络应用，即万维网服务。其目的是将因特网上的资源和信息汇 聚在一起，组合成企业和消费者所需要的服务。惠普推出了e s p e a k 万维网 服务平台；i b m 用它的w e b s p h e r e 平台和一系列中间件实现万维网服务； 微软的路线是通过其n e t 计划和c # 语言实现万维网服务：s u n 则通过 o p e n n e t w o r ke n v i r o n m e n t ( s u no n e ) 计划和j a v a 平台来实现它。另外， i b m 最近宣布，将投资4 0 亿美元，启动一个全公司的“网格计算创新计 划”：s u n 则在2 0 0 0 年9 月公布了其网格引擎软件。 在我国，已经完成的网格研究项目主要有清华大学的先进计算基础设 施a c l ( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ) 和以中科院为主的国家高 性能计算环境n h p c e ( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n ge n v i r o n m e n t ) 。 在清华a c i 系统中，清华大学研制的高性能计算机”t h n p s c - 2 ”与上海大学 研制的高性能计算机”自强2 0 0 0 ”通过高速网络连接在一起，此外还连接了 4 个应用结点。这6 个地理位置不同的网格节点可以同时召开网络会议。 除此之外，还开发了相应的中间件，可以构成跨地区、跨学科的”虚拟实验 室”研究环境。清华a c i 系统具有一套健全的资源管理系统、任务管理系 统、用户管理系统及安全服务与监控系统。清华a c l 系统于2 0 0 1 年6 月 通过了鉴定。 从1 9 9 9 年底到2 0 0 1 年初，中科院计算所联合十几家科研单位，承 担了8 6 3 重点项目“国家高性能计算环境”的研发任务。该项目的目标是 建立一个分布式环境下支持异构平台的计算网格示范系统，它把我国的8 个高性能计算中心通过i n t e r n e t 连接起来，进行统一的资源管理、信息管 理和用户管理，并在此基础上开发了多个计算型的网格应用系统，取得了 一系列研究成果。 2 0 0 2 年4 月5 日至6 日，科技部召开了“网格战略研讨会”，确认 将网格的研究和应用列为“8 6 3 计划”的一个专项，随即成立了专项专家 组。8 6 3 网格专项投资高达3 个亿，主要任务是研制面向网格的万亿次 级高性能计算机、具有数万亿次聚合计算能力的高性能计算环境；开发具 有自主知识产权的网格软件；建设科学研究、经济建设、社会发展和国防 建设急需的重要应用网格；制定若干与网格相关的国家标准，参与制定国 际标准，使一批发明专利和软件获得受理和登记，形成自主知识产权。 2 0 0 5 年1 1 月2 2 日，国家8 6 3 计划“超级计算网格节点建设”项目顺 利通过验收，标志着中国国家网格北方主节点建设完成了其“十五”期间 4 重庆邮电大学硕士论文第一章绪论 的建设任务，所取得的重要阶段性成就为国家网格在“十一五”的持续发 展奠定了坚实的基础。 我国目前正在进行的网格研究项目主要有： 8 6 3 计划支持的“中国网格( c h i n ag r i d ) ”建设，有多家单位参加。 “上海教育科研网格”，多所上海的大学参加。 “仿真网格”的研究，由航天二院和清华大学共同开展。 “织女星网格”，由中科院计算所领衔开发。 另外，全国还有几十所大学和研究机构已经开展各种网格研究。 1 2 计算网格任务调度研究现状 如前所述，国内外针对计算网格的研究已如火如荼，不同的研究机构 根据自身需求提出了不同的任务调度算法及调度策略。又由于网格资源的 自治性、异构性、动态性及多管理域性等特点，目前的网格任务调度算法 大多为启发式的算法。启发式调度可以分为两类：在线模式( o n 1 i n e m o d e ) 调度和批( b a t c hm o d e ) 调度。当任务一到就立刻进行调度为在线模式， 而将到达的任务收集成任务集，满足一定条件才进行调度为批模式。 典型的在线模式调度算法包括o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g ) 算 法”“，m e t ( m i n i m u me x e c u t i o nt i m e ) 算法”“，m c t ( m i n i m u mc o m p l e t i o n t i m e ) 算法“”。在上述几类在线模式算法的基础上，研究者还提出了其他 一些在线模式算法，大多为上述几种算法的变形或组合。 批模式调度算法较在线式调度算法有更高的效率，实际网格系统中多 采用批调度算法，本文也只研究批模式调度。依据网格任务调度对象有两 种类型的优化问题：稳定的状态优化问题和标准的任务完成时间最小的优 化问题。本文的调度算法主要是实现总的任务完成时间最小，提高系统的 吞吐率。 m i n m i n 算法。2 1 是应用最为广泛的一种批模式调度算法，其思想是： 对于任务集中的每个任务，算法求得单个任务最小预期完成时间，然后把 所有任务中“最小预期完成时间”最小的任务分配给其相应的具有最小预 期完成时间的资源，并从任务集中删除；该过程重复进行直至所有的任务 调度完毕：m a x m i n 算法“”与m i n m i n 算法不同，它是将最小预期完成时 间最大的任务分配给对应的资源执行，当元任务中短任务远远多于长任务 时，该算法优于m i n - m i n 算法。s u f f e r a g e 算法皿盯计算任务在各个可用资源 上的预期完成时间，用次小的预期完成时间减去最小预期完成时间，得到 重庆邮电大学硕士论文第一章绪论 一个任务的s u f f e r 值，系统优先调度s u f f e r 值大的任务。m a x i n t l 2 4 】算法是支 持独立任务的优化调度算法，它吸取了m i n m i n 算法和m a x m i n 算法的优 点，除了利用历史信息之外，还利用预测信息来减少调度任务的时间。 m a x i n t 算法的基本思想是，最好的调度应该使得全部任务的完成时间最 小。如果一个任务在机器h 【s 】上具有最小完成时间，在h 【t 】上有次小完成 时间的话，指派任务给h s 是最好的且最常用的方法。m a x i n t 算法使用了 这一特性，但是，与m i n m i n 算法和m a x m i n 算法不同的是：多个任务进行 指派时，m a x i n t 算法需要考虑下一步的调度，使下一步调度期望最小，而 本次的调度则并非最佳。 上述算法在解决特定领域问题时具有一定的效果，但是还存在着一些 问题和缺陷，尤其对于大吞吐量任务调度应用效果不理想，此外，上述研 究也很少考虑网格中各个资源节点的性能度量以及任务本身的区别，更未 考虑到紧急任务的优先级问题，这些是本文要解决的核心问题。 1 3 本文研究内容 高吞吐率计算是计算网格中一类重要而广泛的应用，高吞吐率应用通 常转化为“任务放牧”问题陋“，即大量独立或松耦合的任务分散到网格虚 拟组织内不同的计算资源上运行。针对此类应用，本文对任务调度的研究 要解决以下几个方面问题： 1 、资源节点的性能度量 网格中资源类型多种多样，它们往往具有不同的体系结构，并且提供 资源的网格节点的通信带宽也不一样。调度服务将任务分配到具体资源节 点上执行，由于任务的完成时间为任务在相应资源上的等待时间和任务的 执行时间之和，放任务的完成时间和任务属性以及完成它的资源属性有密 切关系。由于各资源上的负载各不相同，某一任务在性能高的资源节点上 的完成时间不一定优于该任务在某个性能较低的资源节点上的完成时间。 因此，本文在设计任务调度算法时考虑到了资源的性能及其负载状况，根 据资源的性能及其负载状况对资源进行排序，以便任务选取合适的资源进 行调度。 资源节点的属性也即节点处理能力是任务调度的重要依据。影响处理 能力的主要因素有c p u 性能、i o 吞吐量、网络带宽等。对于“任务放牧” 此类应用的网格任务调度，相对于任务执行时间和通过网络传递的时间而 言，受i o 吞吐量影响的时间较少，因此本文研究的资源节点处理能力主 6 重庆邮电大学硕士论文第一章绪论 要指c p u 性能和网络带宽。 本文以c p u 性能、网络带宽以及资源负载为度量计算出每一任务分解 后的加权平均完成时间来指导任务调度。 2 、性能预测 网格资源的多样性、异构性、动态性以及多管理域性等特点要求我们 在做调度决定时需要建立随时间变化的性能预测模型，充分利用网格的动 态信息来表示网格性能的波动，根据资源状态的变化进行动态调度，以实 现优化调度。 本文构建一种可以在线预测的模型用来预测任务在各资源节点上的 完成时间，同时检测其网络带宽的负载变化，为调度策略的制定奠定基础。 3 、监测模块 由于网格资源具有分布性、异构性、动态性、自治性等特性，以及网 格中的任务又有本地任务和远程任务以及任务的优先级等区别，这导致网 格任务调度算法不能按照简单的某一调度算法进行调度，需考虑网格中的 实际应用情况。本文构建网格任务监测模块，用以监测网格上各任务的状 态，区分各任务的优先级以及由于网格资源的变化导致的已调度但未得到 执行的任务的重新调度的优先级。 通过对上述三方面的研究，本文提出了一种基于时间均衡的自适应网 格任务调度算法( a t b b s 算法) 。并与m a x m i n 算法及m a x i n t 算法进行 仿真比较，仿真实验验证了本算法能有效缩短任务完成时间、提高系统吞 吐率、紧急任务能得到更及时的响应，并且资源可以得到更充分的利用。 1 4 论文结构 全文共分五章，内容如下： 第一章为绪论，首先介绍了网格的起源和发展，以及计算网格和任务 调度问题的需求和意义，然后分析了己有的任务调度算法和国内外计算网 格项目中任务调度系统的研究开发现状，最后提出了本文的主要研究内 容。 第二章首先简要介绍网格的体系结构以及网格任务调度模型的基本概 念，然后介绍任务调度的研究现状以及面临的困难和挑战，对已有的几种 主要任务调度算法进行了比较研究，分析其优缺点。 第三章针对“任务放牧”这一类应用，运用数学方法分析网格资源及 任务的特性，建立时间预测模型，并把根据网格资源的性能和负载对资源 7 重庆邮电大学硕士论文第一章绪论 的排序做为任务选择资源的依据。根据网格监测模块的监测信息，给相应 需优先调度的任务附上自适应因子。最后提出基于时间均衡的自适应网格 任务调度算法。 第四章用仿真实验考察算法性能，得出本算法涉及的几个参数指标， 并运用仿真实验把本算法的性能与m a x m i n 算法和m a x i n t 算法进行了比 较。 第五章对己有的工作进行总结，提出需进一步深入研究的问题。 重庆邮电大学硕士论文第二章网格计算的概念 2 1网格基础 2 1 1 网格简介 第二章网格研究现状 网格技术起源于2 0 世纪9 0 年代初由美国政府资助的分布式超级计算 项目i - w a y 。从1 9 9 3 年开始，高性能计算技术和互联网技术进一步融合， 酝酿产生了继因特网、w e b 之后的第三大技术浪潮。“网格”这一术语的 思想则源于日常生活中公共设施的应用，i a nf o s t e r 出版的著作中最早将 它称之为“网格”。网格建立在i n t e r n e t 的可访问性基础之上，允许用户有 效地使用地理上分布的资源幢”。因此，网格也被看作下一代i n t e r n e t ”“。 网格是将分布在各地的计算机资源通过高速的互联网组成充分共享 的资源集成，这些机器的计算资源构成共享池。它彻底地改变了计算机和 数据的访问方式，将成为下一代分布式计算的体系结构标准，它提供从孤 立的系统到紧密结合的簇、企业范围内聚簇及地理上分散的计算机环境之 间联系的途径。用户无论在何时何地都能透明地访问计算和存储资源，并 保证一定的服务质量”。 网格作为一种新出现的重要的基础设施，与其它计算系统相比，具有 以下特性： 1 、分布与共享共存 分布性是网格的一个最主要的特点，首先网格涉及的资源是分布的， 它们一般类型多样，规模较大，跨越的地理范围较广；由于这个原因，基 于网格的计算也是分布式的，这就产生了资源与任务的分配和调度、安全 传输与通信等一系列需要解决的问题。 网格资源虽然是分布的，但又是充分共享的。共享是网格的目的，如 何解决分布资源的共享问题，是网格的核心内容。分布性是网格硬件在物 理上的特征，而共享是在网格软件支持下实现的逻辑上的特征，这两者在 网格系统中同时存在。 2 、相似性 网格的局部和整体之间存在着一定的自相似性，局部往往在许多地方 具有全局的某些特征，而全局的特征在局部也有一定的体现。 9 重庆邮电大学硕士论文第二章网格计算的概念 3 、动态性和多样性 对于网格来说，决不能假设它是一成不变的，原来拥有的资源或者功 能，在下一时刻可能会出现故障或者不可用；而原来没有的资源，可能随 着时间的推移会不断地加入进来。 网格资源是异构和多样的。在网格系统中可以有不同体系结构的计算 机系统和类别不同的资源，因此网格系统必须能够解决这些结构不同、类 别各异的资源之间的通信和互操作问题。 4 、自治性与管理的多重性 网格上的资源首先是属于某一个组织或者个人，因此网格资源的拥有 者对该资源有最高级别的管理权限，统一管理这些资源的同时，资源拥有 者也可自主管理其提供的资源。 因此网格的管理具有多重性，一方面允许网格资源的拥有者具有自主 性的管理，另一方面又要求网格资源必须接受网格的统一管理。 以上就是网格的一些特性，正是由于这些特性的存在，为任务调度算 法的设计提出了更大的挑战，只有解决好这一问题，才能使网格更好地发 挥优良的性能，为应用提供满意的服务。 2 1 2 网格的体系结构 网格体系结构是关于如何建造网格的技术，包括对网格基本组成部分 和各部分功能的定义及描述、网格各部分相互关系与集成方法的规定、网 格有效运行机制的刻画。i a nf o s t e r 将网格体系结构定义为“划分系统基 本组件，指定系统组件的目的与功能，说明组件之间如何相互作用”瞳“。 至今，主要的网格体系结构有两个：一个是i a n f o s t e r 等在早些时候提出 的五层沙漏结构：另一个是在考虑到w e b 技术的发展与影响后，f o s t e r 等 结合w e bs e r v i c e 提出的开放网格服务结构o g s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) 。 1 、五层沙漏结构”8 1 五层沙漏结构的基本思想是：共享需要互操作，而实现互操作需要定 义协议，五层沙漏结构中特别重视协议的定义。服务是由它使用的协议和 实现的行为定义的，标准协议还使得定义标准服务更加容易。标准服务的 定义( 如对计算的访问，存取数据，资源发现，协同调度，数据重复等) 可 以进一步提供增强的能力，使虚拟组织参加者得到更多的服务。 五层沙漏结构分为：构造层、连接层、资源层、汇聚层和应用层。如 1 0 重庆邮电大学硕士论文第二章网格计算的概念 图2 1 所示： 应用层 j 汇聚层 资源层 r 连接层 图2 1计算网格的五层沙漏体系结构模型 ( a ) 网格构造层的基本功能是控制局部的资源，向上提供访问这些 资源的接口； ( b ) 连接层的基本功能是实现相互的通信。它定义了核心的通信和 认证协议，用于网格的网络事务处理之中： ( c ) 资源层的重要功能就是实现单个资源的共享； ( d ) 汇聚层的主要功能就是协调“多种”资源的共享，即如何将下 面以单个资源形式表现出来的资源集中起来，协调解决多个资源之间的问 题： ( e ) 应用层关系的是有什么样的资源可以由下面提供给虚拟组织， 解决不同虚拟组织的具体问题。 可见，以资源共享协议和资源阃的通信协议为核心，网格环境实现了 广域范围内的资源共享和协同工作，将面向i n t e r n e t 的计算推进到了一个 新的阶段。 计算网格体系结构中的连接层、资源层和汇聚层的功能需要由架构在 资源层之上、应用层之下的网格中间件实现。 2 、开放网格服务体系结构 开放网格服务结构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 ) 。们是 g l o b a lg r i df o r u m4 的重要标准建议，是继五层沙漏结构之后最重要的一 种网格体系结构。它与五层沙漏结构最大区别在于，它不是象沙漏结构一 罱囤 重庆邮电大学硕士论文 第二章网格计算的概念 样以协议为中心，而是以服务为中心的。这里的服务是指具有特定功能的 网络化实体，包括各种计算资源、存储资源、网络、程序、数据库等等。 在o g s a 中，实现的不再是对资源的共享，而是对服务的共享。从资源到 服务，这种抽象将资源、信息、数据等统一起来，有利于灵活的、一致的、 动态的共享机制的实现。 2 2 网格应用现状和发展趋势 在计算网格中，应用都有其自身固有的特性，对这些特性进行分析是 进行任务调度的基础。 我国现代化建设中，许多大型行业应用都需要用到计算网格技术。在 天气预报、生命科学研究、地球环境保护、核试验仿真、教育科研等应用 领域中，人们对网格和计算网格技术的需求非常大。通过归纳我们可以把 网格应用大致分为以下几类”。 2 2 1 分布式超级计算 分布式超级计算是传统的集中式高性能计算向分布式的发展，将分布 在不同地域的超级计算机用高速网络连接起来，通过网格中间件“聚合”， 形成比单台超级计算机强大得多的计算平台。 这类应用有如下特点： 1 、通过网格将多个分散的计算资源聚合起来，用以解决单个资源无 法解决的问题，其规模大到可覆盖世界范围内的大部分超级计算机，小到 可能只是某公司内部的所有工作站。从集中计算到分布计算，是网格功能 的重要体现。 2 、面临如何实现协同调度计算资源、如何在异构系统问达到和保持 高性能的挑战。相应的协议和算法必须提供从几个到成百上千的计算资源 节点的可扩展性，并能容忍动态变化的网络延迟。 3 、通信会对系统性能造成较大的影响，调度过程中应该尽量使通信 和计算过程重叠，在计算精度和通信能力之间做出平衡，用冗余的计算减 少通信开销；增大计算的粒度，减少模块之间耦合度；并且在通信过程中 集结成组传输，采用压缩算法减少通信量。其应用领域包括大规模军事仿 真和天文学模拟。 1 2 重庆邮电大学硕士论文 第二章网格计算的概念 2 2 2 高吞吐率计算 高吞吐率计算是计算网格中一类重要而广泛的应用，如参数扫描分 析、蒙特片罗仿真、数字视频显示、复杂系统模拟、高性能生物信息计算、 药物设计、基因组学、蛋白质学等领域，均涉及大量样本空间的计算。这 些任务的性能往往不能以传统微观计算性能指标( 如每秒执行的浮点操作 数) 来度量，而要以端到端的工作量，如一周内执行的变换数、一月内显 示的视频帧数或一年内完成的模拟数目等来度量。 此类应用通过网格调度大量松耦合或相互独立的任务，充分利用空闲 的资源求解问题。集中可用的资源解决某个问题，这点与分布式超级计算 类型的应用相似，但任务问的相对独立性使得问题及问题求解大相径庭。 2 2 3 按需计算 按需计算虚拟化计算机、服务器以及整个数据中心等资源，提供资源 或服务满足业务需求。按需计算实现个人或组织的灵活性，使他们既可以 拥有自己的资源、基础设施，又可以向外部的服务提供商订购服务。这样， 对于那些关键的应用，个人或组织可以选择构建自己的网格基础设施，以 获得更高的效率：而对于一些更加通用的业务，可以选择求助于服务提供 商来满足对各种基础设施的需求。 按需计算类型的应用使用网格计算能力满足任务对资源的短期需求， 这些需求往往无法或不适合由本地资源完成。按需计算是实现效率更高、 复杂性更低和更加灵活业务的基础。 通常这类应用关心的是完成任务的性价比而并不强调完美的性能，它 们对资源的需求是动态的，用户群及可用资源集可能都很大，面临的挑战 包括资源定位、调度、容错、安全及付费机制等。随着开放网格和w e b 服 务协议的不断普及，越来越多的业务过程将会成为按需的应用。著名的 b u t t e r f l y 网格就是通过按需服务支持大规模多玩家的分布式可扩展游戏网 格。 2 2 4 数据密集型计算 数据密集型应用侧重于数据的存储、传输和处理，关键是如何综合来 自数据库、地理上分布的数据仓库、数字图书馆中的数据合成的新信息。 数据是科学和工程中所有分支学科的基础，在医药研究、诊断中扮演 重要角色，对商业和政府决策过程给予有力的支持。传感器、存储设备、 1 3 重庆邮电大学硕士论文第二章网格计算的概念 计算机、网络处理能力和容量的显著提高使创建海量数据文件成为可能。 科学和商业领域都存在着数据密集型应用，天文、生物、医药、环境、工 程和高能物理等研究领域很快会出现p b 数量级的文件，数据的飞速增长 使得数据分析成为一项挑战。这些海量数据的分析和研究将会促使在自然 物质、生命、环境或现实世界的其他方面产生意义深远的新见解。这些海 量数据的数据源分布在广泛的范围内，因此这类应用通常既是数据密集的 也是通信密集的。 解决该类应用问题的关键是如何在多层次上调度和配置复杂的大容 量数据流。应用领域包括很多高能物理实验、数字化天空扫描和气象预测 等。 2 2 5 协同计算 协同计算主要用于支持并加强人与人之间的交互，以克服地理位置、 交互能力和共享对象等诸多条件的限制。 随着广域协作范围与规模的增长，参与者需要进行异步交互操作。传 统上这种要求可以通过备忘录、录像带、录音磁带等机制来解决。但是这 些机制是单方面的，没有考虑人们相互影响带来的细微差别。协同计算可 支持位于不同地点的人员参加会议，在一个虚拟的共享空间中进行交互， 共同讨论问题。它是网格领域中新兴的一类重要应用，致力于支持广域、 实时和以计算机为媒介的通信。a r g o n n ef u t u r e s 实验室开发的a g ( a c c e s s g r i d ) 项目从1 9 9 4 年起致力于开发协作环境，是该类应用的典型例子。作 为一个网络、计算能力和交互资源的整体，a g 支持网格上群体与群体间的 人员交互，专注于高端工作空间中群体间的协作。当前的a g 系统包含大 量不同格式的多媒体内容的显示、演示和交互软件环境、网格中间件接口 和远程可视化环境。目前它已拥有数百个遍布世界各地的用户，实现他们 日常工作中的群体协作。协同计算面临的挑战是用户的感知能力带来的实 时要求和交互的多样性。 本文主要研究高吞吐率应用的任务调度问题。如前所述，高吞吐率计 算是计算网格的一类重要应用，它是通过网格调度大量松耦合或相互独立 的任务。由于网格具有大范围分布性、异构性和动态特性，松耦合的并行 应用相比紧耦合应用更适合在网格环境中执行。高吞吐率计算中的任务大 多转化为“任务放牧”心钉问题( 例如那些任务间完全独立的应用) 。此类 应用包括数据挖掘、大范围搜索、参数扫描应用、蒙特卡罗仿真、图像处 1 4 重庆邮电大学硕士论文 第二章网格计算的概念 理应用( 如x 光重建) 、药物设计、生物信息学等。 2 3 网格调度模型 传统上，应用程序在s m p ，m p p 或n o w 等同构或均一系统上运行， 因为计算资源的相对有限性，一个应用程序执行时，所有计算资源均作为 调度目标考虑。然而，网格计算资源具有多样性、异构性、广域分布性和 多管理域性，如果将全部网格资源作为一个应用程序的调度和执行目标， 可能因为通信延迟等问题，使得调度变得十分昂贵和困难，而且执行效率 也会下降。在网格计算系统下，应用程序调度模型需要考虑应用程序特性、 机器特性。为不同应用程序匹配不同的计算资源，可以提高计算资源的利 用率。图2 2 示出了网格计算系统下的应用程序调度模型的结构”“。 图2 2 网格系统下的应用程序调度模型 2 3 1 应用程序分析模块 应用程序分析模块有两大功能；应用类型分析和类度分析。通过对应 用程序的类型进行分析，可以确定应用程序的特点。初略地，可以将网格 环境下的应用程序分成三大类型，即计算密集型应用、通信密集型应用和 重庆邮电大学硕士论文第二章网格计算的概念 计算通信相对均衡型应用。通过对应用程序的类度进行分析，可以确定应 用程序中并行化任务的多少、并行化任务的特点。应用程序分析模块的结 果需要定时地发布到“应用特性描述表”中。 2 3 2 资源特性分析模块 资源特性分析模块主要通过典型应用分析机器对不同代码的执行效 率，得到机器对具有不同内在并行任务的运行效率。另外，还可以通过监 测和分析机器使用的处理器结构、存储器性能和高速缓存特性得到机器特 性信息，并把它作为资源特性的一部分。在网格系统中，由于资源具有多 方面的异构性，该模块的作用就更加重要。该模块首先分析网格资源的静 态信息，得到不同资源的c p u 体系结构、操作系统和应用接口等方面的异 同信息；然后，调用网格计算中间件的资源监测模块，监测计算资源的可 用性以及计算资源的动态特性，如计算资源的开启状态、节点可用内存大 小、负载情况和执行队列长度等。资源特性分析模块的执行结果需要定时 发布到“机器特性描述表”中。 2 3 3 应用程序分解模块 应用程序的自动分解一直是比较困难的工作，虽然在这方面已经做了 大量的研究，并取得了显著成果，但离实际应用还有较大距离。传统上， 应用程序的分解过程一般由编程人员控制。这在专业化机群系统上还是可 用行的。但在网格计算环境下，要实现应用的透明执行，应用程序分解就 变得非常重要。 在网格计算系统中，应用程序的分解涉及到任务并行粒度和应用特性 分析这两方面的结果。它是基于机器特性分析和程序代码分析而进行的。 首先，它利用“应用特性描述表”分解一个应用程序成很多任务，这些子 任务之间通常包含依赖或优先约束关系；然后，基于“机器特性描述表” 将分解的子任务构成适合不同机器特性的若干任务集合，目标是让任务能 够在适合自己运行的节点上运行。 由于网格系统是广域虚拟计算环境，有一定的传输延迟，因