（计算机应用技术专业论文）天文图像合成网格服务的负载平衡研究.pdf

摘要 网格计算在动态多机构的虚拟组织中协调资源共享和协同求解问题。负载平 衡均衡所有结点上的负载，提高系统的资源利用率，减少任务平均响应时间。可 分负载理论是进行并行分布式任务调度实现负载平衡的一个模型，有易于处理、 可操作性强、扩展性好、适用于多数网络拓扑结构、易于与实际结合等优点，因 此在数据密集型网格计算中进行可分负载理论的研究和应用深受研究人员的青 睐。本文应用并行传输，计算通信可重叠的可分负载理论求解天文图像合成网格 服务的任务分配和再分配问题，取得了一些成果。 本文首先设计了天文图像合成网格服务的系统结构，分析总结了该网格服务 四个主要工作流程，设计了该网格服务的服务流程。 然后讨论了天文图像合成网格服务的任务分配问题。通过对基于蚂蚁算法的 网格任务调度方法进行分析和改造，提出了基于蚂蚁算法的性能预测方法以进行 简单高效的性能预测，为负载平衡提供支持。针对该网格服务四个工作流程建立 了根结点提交二次叠加、根结点提交一次叠加、根结点处理二次叠加和根结点处 理一次叠加四个可分负载模型。为了更好的处理存储限制问题，提出了一种比增 量平衡策略算法更快适用范围更广的快速存储限制分配算法。基于已有求取次优 解的整数逼近算法，提出了增一堆排序整数逼近算法以求取可分粒度问题的最优 解。基于以上的模型和算法，设计了该网格服务的任务分配总体流程。通过仿真 实验分析选取了基于蚂蚁算法的性能预测方法的算法参数。 最后讨论的是天文图像合成网格服务的任务再分配问题。选取c p u 就绪队 列长度、磁盘请求队列长度和任务进度三个负载参数衡量资源性能，提出了基于 连通分图的负载聚类方法以决定是否需要任务迁移及迁移任务的发送者和接收 者。通过分析任务迁移后总完成时间变化规律建立了该网格服务任务再分配的可 分负载模型。提出了该网格服务的任务再分配算法。 本文对天文图像合成网格服务的任务分配和再分配模型和算法进行了深入 的研究和设计，给出了多项式时间求取该网格服务负载平衡最优解的完整方案， 提高网格系统性能。 关键词：网格服务，性能预测，负载平衡，可分负载理论，天文图像合成，蚂蚁 算法 a b s t r a c t g r i dc o m p u t i n gi m p l e m e n t sr e s o u r c es h a r i n ga n dc o o r d i n a t e dp r o b l e ms o l v i n g i nd v n a m i c ，m u i t i i n s t i t u t i o n a lv i r t u a lo 唱a n i z a t i o n s l o a db a l a n c et r i e st ob a l a n c et h e l o a do fe v e r yc o m p u t e rn o d e d i v i s i b l el o a dt h e o 巧( d l di sam e t h o d o l o g yt h a t i m p l e m e n t sl o a db a l a n c ei nd a t a i n t e n s ep a r a l l e l a n dd i s t r i b u t e ds y s t e ms c h e d u l i n g t h ep a p e ru s e st h ed l tt os o l v et h et a s ka l l o c a t i o na n dr e a l l o c a t i o np r o b l e mo f a s t r o n o m i c a l i m a g em o s a i c k i n gg r i ds e r v i c e f i r s t l y ，t h es y s t e ma r c h i t e c t u r eo ft h e 矿i ds e r v i c ei sd e s i g n e d f o u rw o r k n o w s a r ea n a l y s e da n ds u m m a r i z e d t h es e r v i c ef l o wo ft h e 伊i ds e r v i c ei sp u tf o n v a r d s e c o n d l y ，t h et a s ka l l o c a t i o no ft h e 铲i ds e r v i c ei sd i s c u s s e d b ym a k i n gad e e p r e s e a r c hi n t ot h eg r i dt a s ks c h e d u l e rb a s e do nt h ea n ta l g o r i t h 瑚，t h ea u t h o rb r i n g s f o r w a r das i m p l ea n de f f e c t i v ep e 而肿a n c ep r e d i c t i o nm e t h o db a s e do nt h ea n t a l g o r i t h mt os u p p o nt h el o a db a l a n c e r o o ts u b m i t t i n g 觚i c ea d d i n g ，r o o ts u b m i t t i n g o n c ea d d i n g ，r o o tc o m p u t i n gt w i c ea d d i n ga n dr o o tc o m p u t i n go n c ea d d i n gd i v i s i b l e t a s km o d e l sa r ep r o p o s e d t bt a c k l et h es t o r a g ec o n s 仃a i n ta n dd i v i s i b l eg r a n u l a r i 哆 p r o b l e m s ，af a s t e ra n dw i d e ru s e ds t o r a g ec o n s t r a i n ta ll o c a t i o na l g o r i t h mt h a ni b sa n d i n c r e a s i n go n eh e 印s o r to p t i m u mi n t e g e r 印p r o x i m a t i o na j g o “t h m b a s e do na s u b o p t i m u mi n t e g e r 印p r o x i m a t i o na l g o r 砒l l na r ed e s i g n e d t h et a s ka l l o c a t i o nf l o w b a s e df o r e n a m e dm o d e l sa n da l g o r i t h m si sf o u n d as i m u l a t o nf o rc h o o s i n gt h e p a r a m e t e r so ft h ep e 墒r m a n c ep r e d i c t i o nm e t h o db a s e do nt h ea n ta l g o r i t i sd o n e f i n a l l y ，t h et a s kr e a lj o c a t i o no ft h eg r i ds e r v i c ei sd i s c u s s e d c p uq u e u el e n 或h ， d i s kr e q u e s tq u e u el e n g t ha n dt a s kp r o g r e s sr a t ea r ec h o s e nt ow e j g ht h er e s o u r c e p e i r f o r n l a n c e al o a dc l u s t e rm e t h o db a s e do nc o n n e c t e ds u b g r a p hi sp r o p o s e dt o d e c i d ew h e t h e rt a s km i g r a t i o ni sn e e d e da n dt h es e n d e ra n dr e c e i v e r so fi t b y a n a l y s i n gt h ec h a n g eo f t h ec o m p i e t et i m ea r e rt h et a s km i g r a t i o n ，t h ea u t h o rd e r i v e s at a s kr e a l i o c a t i o nd i v i s i b l et a s km o d e l at a s kr e a l l o c a t i o na l g o r i t h mo ft h eg r i d s e r v i c ei sd e s i g n e d t h et a s ka l l o c a t j o na n dr e a l l o c a t i o nm o d e l sa n da l g o r i t h m so fa s t r o n o m i c a l i m a g em o s a i c k i n g 矿i ds e r v i c ea r er e s e a r c h e da n dd e s i g n e d ai n t e g r a t e ds o l u t i o nt h a t c a ng e tt h eo p t i m u ma l l o c a t j o no f t h el o a db a l a n c eo ft h eg r i ds e r v i c ei np o l y n o m i a l t i m ei sp r e s e n t e dt oi m p r o v et h eg r i ds y s t e mp e 南r m a n c e 1 a e yw o i t d s ： 旷i ds e r v i c e ，p e m n n a n c ep r e d i c t i o n ，l o a db a l a n c e ，d i v i s i b l e l o a d t h e o 巧，a s t r o n o m i c a l m a g em o s a i c k i n g ，a n ta l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导爆指导下进行的研究工作和取缛的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 娶碍谁 签字| b 袈： z 口。年 6 月歹日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 熊科嚷 导师签名： 签字日期：。6 年6 月箩日 签字日期： 钟 口汴b 其9 第一章绪论 1 1 课题背景 第一章绪论 网格研究 1 】 2 】 4 7 】起源于2 0 世纪9 0 时代初由美国政府资助的分布式超级计 算项目i w a y 。从1 9 9 3 年开始，高性能计算技术和互联网技术进一步融合，产 生了新一次的技术浪潮网格计算。网格计算是在动态的、多机构的虚拟组织 中协调资源共享和协同解决问题。网格系统除了具有分布式的一般特征外，它还 拥有在分布环境中自动执行和协作、对异构资源进行一致管理、允许资源自主管 理、允许资源动态加入或退出、局部和整体之间存在一定的相似性等特点。目前 国内外学者对网格安全、网格信息管理、网格资源分配和管理、数据管理、协同 分配和管理、工作流管理、网格监控和用户门户等诸多方面【6 】都进行了广泛和 深入的探讨和研究，并推出了很多网格中间件和开发网格应用的工具包及框架。 网格技术在分布式超级计算、分布式仪器系统、数据密集型计算、远程沉浸、天 文气象、高能物理、生物信息、组合化学及商业等领域都有着广泛的应用。 虚拟天文台【4 6 】利用最先进的信息技术、网格技术将各种天文研究资源，包 括天文数据、天文文献、各种天文分析工具、计算资源、存储资源以及天文望远 镜等观测设备，以统一的服务模式透明地汇集到系统中。虚拟天文台一经提出就 得到了全世界各国的广泛响应和积极投入，被公认为未来天文学家研究的一个重 要发展方向和工作环境。美国虚拟天文台在数据的统一注册归档、统一访问、分 析处理方面取得了很多进展。法国在虚拟天文台的数据融合方面取得了很不错的 成绩，它开放的一些工具已经集成到了世界各国虚拟天文台项目中，得到了广泛 的应用。英国国家虚拟天文台a s t r o g r i d 是目前世界上第一个结构比较完整的虚 拟天文台，集成了大量数据查询、数据访问、数据处理等应用和服务并提供了统 一的配置访问环境和工作流管理的可视化建模、执行和监视环境。还有很多国家 的虚拟天文台也取得了可观的研究成果。我国自行研发的虚拟天文台 4 5 】实用工 具比如v o d a s 、v o f i i t e r 、f i t h a s 、s k v m o u s e 等相继出现，可以访问的数据 集也在逐渐扩大，处在虚拟天文台的发展阶段。 天文图像合成网格服务来源于虚拟天文台一个典型和重要的应用。它利用最 新的网格技术为用户和应用程序提供一个优质高效的天文图像合成基础服务，为 天文数据的后续分析处理奠定基础。美国n a s a 资助的蒙太奇m o n t a g e 工程完 第一章绪论 成了天文图像合成各处理模块的研究和开发，并提供一个以t e r a g r i d 中集群系统 和并行文件系统为计算环境的主流天文数据集的天文图像合成在线服务。 网格负载平衡是提高网格性能和服务质量的关键问题。n i m r o d g 、a p p l e s 和c o n d o 卜g 等都是目前应用较广泛的网格任务调度器。但这些调度器都是普适 型的调度器，适用一定范围的所有计算密集性任务调度。需要适用于特定的数据 密集性应用的任务调度器的出现。目前已经有很多很好的调度算法，一些新的研 究方向如神经网络、遗传算法、蚂蚁算法等，由于它们是模拟某一自然现象或过 程而发展起来的，并且具有适于高度并行与自组织、自适应、自学习等特征，引 起了人们的极大兴趣。数据密集型问题处理和调度中出现的可分负载理论对数据 密集型问题进行了很好的建模，得出了些很好的结论，并很容易扩展到实际应 用环境中，成为数据计算领域的一个研究热点。可分负载理论作为一种任务调度 算法，能够更好更快的求解任务分配的最优解。 本文运用可分负载理论研究天文图像合成网格服务的负载平衡问题，包括该 网格服务的任务分配和再分配，从而有效地提高系统的资源利用率，减少天文图 像合成的任务平均响应时间。 1 2 研究意义 天文图像合成网格服务负载平衡研究是该网格服务的研究重点，好的负载平 衡算法能够充分利用网格资源，提高天文图像合成的运算速度和网格系统的资源 利用率和负载平衡度。应用网格环境中负载平衡技术解决实际问题是网格计算研 究成败的关键，也是网格环境中负载平衡的直接目标和意义所在。天文图像合成 网格服务的研究结合具体天文学实例，研究特定网格中任务分配和再分配等核心 网格计算负载平衡问题，丰富网格计算技术和应用的内容。天文图像合成网格服 务的研究为网格计算等先进信息技术研究提供优良的实验场，推动国内信息技术 的发展。 虚拟天文台研究目前主要集中在海量天文数据的共享和访问问题上，少量的 分析处理服务也以超级计算机，集群系统，并行文件系统等为计算环境。因此， 结合天文海量数据处理的自身特点，利用全分布的工作站和分布式文件系统进行 网格系统负载平衡技术和应用的研究，对虚拟天文台、对中国的网格技术发展有 很大意义。天文图像合成网格服务进行天文海量数据的处理和计算，充分利用网 络上分布的工作站提高计算的速度和效率，为虚拟天文台其他网格服务的发展提 供一个实例参考。同时天文图像合成服务可访问虚拟天文台中已经做好的数据共 享和访问系统查询天文图像数据，经过一系列流程处理，生成的合成图像又可以 第一章绪论 被虚拟天文台其他服务运用。虚拟天文台的其它服务也可以直接访问天文图像合 成服务便于自身的处理。因此天文图像合成服务可以与其他服务整合在一起对外 提供天文学的计算和访问。 天文图像合成本身为天文学家后续的研究和分析提供大量优质的合成图像， 是天文学上一个十分重要和必要的基础处理过程，该网格服务为后续天文数据处 理和研究提供平台支持和数据支持，是虚拟天文台的有力支撑。天文图像合成网 格系统可被全球各种各样的群体访问，包括那些没有经济能力建造和运行大型观 测设备的群体，能大大促进发展中国家和不发达国家的天文研究。 1 3 研究内容和创新 针对网格环境的动态性和复杂性特征，结合天文海量数据处理的自身特点， 本文进行了天文图像合成网格服务的总体设计，在天文图像合成网格服务的任务 分配和再分配方面做了一定的理论研究和试验，取得了一些成果。具体的研究内 容和创新点如下： ( 1 ) 根据网格环境特点和天文海量数据处理的自身特点，设计了天文图像合成 网格服务的系统结构，提出了天文图像合成网格服务任务分配、复制管理、 任务执行、任务监控和任务再分配的网格服务流程。 ( 2 ) 对传统蚂蚁算法和基于蚂蚁算法的网格任务调度方法进行分析和改进，结 合网格环境的实际属性和系统参数，结合天文图像合成的工作流程，提出 了基于蚂蚁算法的性能预测方法。 ( 3 ) 结合天文图像合成的工作流程和网格服务的特点，建立了天文图像合成网 格服务的根结点提交二次叠加、根结点提交一次叠加、根结点处理二次叠 加和根结点处理一次叠加四个可分负载模型。并给出了资源选择策略。 ( 4 ) 通过对已有的平衡增量策略算法进行分析，提出了一种更快适用范围更广 的快速存储容量限制可分负载分配算法，并分析了该算法的性能和复杂 度。 ( 5 ) 对已有只能求取次优解的可分负载整数逼近算法进行分析和研究，本文在 已有整数逼近算法的基础上提出了可求取最优解的整数逼近算法增 一堆排序整数逼近算法，并分析了该算法的性能和复杂度。 ( 6 ) 结合天文图像合成网格服务的特点，设计了模拟网格环境，模拟天文图像 合成，模拟任务产生、任务分配、任务执行的仿真试验，并对仿真结果数 据进行分析，选取了基于蚂蚁算法的性能预测的算法参数。 ( 7 ) 根据网格环境和天文图像合成计算的特点，选取任务完成进度、c p u 队 第一章绪论 列长度和磁盘队列长度作为资源负载参数，提出了基于连通分图的资源负 载聚类算法，用于决定任务迁移是否要迁移及选择任务迁移的发送资源和 接收资源。 ( 8 ) 根据天文图像合成网格计算特点，分析了任务迁移后总完成时间的变化， 提出了任务再分配的可分负载模型和任务再分配算法。 1 4 论文结构 文章进行了天文图像合成网格服务的总体设计，研究了任务分配和再分配问 题。本文分六章，论文结构如下： 第一章为绪论，介绍了本文的课题背景、研究意义、研究内容和创新点。 第二章为全文的理论基础，详细给出了网格计算，性能预测和负载平衡的相 关理论和知识。 第三章为天文图像合成网格服务的总体设计，提出了该网格服务的系统结 构，介绍了天文图像合成的功能模块及并行优化和天文图像合成工作流程，提出 了天文图像合成网格服务流程。 第四章为天文图像合成网格服务的任务分配，提出了基于蚂蚁算法的性能预 测方法，建立了该网格服务的根结点提交二次叠加、根结点提交一次叠加、根结 点处理二次叠加和根结点处理一次叠加四个可分负载模型，提出了一种快速存储 容量限制可分负载分配算法，提出了可求取最优解的整数逼近算法一增一堆排 序整数逼近算法，进行了仿真实验并对实验结果进行分析选取了基于蚂蚁算法的 性能预测方法的算法参数。 第五章为天文图像合成网格服务的任务再分配，提出了基于连通分图的负载 聚类方法，建立了该网格服务任务再分配的可分负载模型，提出了该网格服务任 务再分配算法。 第六章为全文的总结和研究工作展望。 4 第二章网格计算和负载平衡 第二章网格计算和负载平衡 天文图像合成网格服务的负载平衡研究是在网格计算环境中进行天文图像 合成任务分配和再分配研究，而性能预测为高效的负载平衡提供支持，是一项重 要的研究内容。因此本章介绍网格计算、性能预测和负载平衡的相关理论和现状， 重点介绍网格计算、性能预测和负载平衡的意义、特点、分类和常用方法。 2 1 网格计算 2 1 1 网格概述 随着计算机应用领域的不断拓展和计算机应用研究的不断深入，需要计算机 解决的问题越来越复杂，规模也越来越大，解决这些问题所需要的计算能力和存 储能力等在大幅度提高。对这些计算密集、海量信息存储的问题求解需要超大规 模的计算和数据分析能力，而目前只有少数科研机构拥有能满足这样的信息存储 和处理能力的单个计算资源或局部计算资源，无法满足人们数据处理需求的增 长。网格这种以打破地域的限制来实现更大粒度和更大范围的资源共享方法在此 背景下应运而生。 网格一词来源于电力网，研究的目标是将地理上分散的属于不同机构管理的 运行不同软件的异构的各种高性能计算机、服务器、p c 、信息系统、海量数据 存储和处理系统、应用模拟系统、虚拟现实系统、仪器设备和信息获取设备( 例 如传感器) 等各种存储资源、服务资源和计算资源用i n t e m e t 连接，通过合理的 组织充分利用起来，并提供给用户一个高可靠、高性能的无处不在的可透明访问 的统一虚拟超级计算机环境。网格是一个集成的计算与资源环境，或者说是 一个计算资源池，这里的计算资源除了包括各种类型的计算机，还包括网络通信 能力、数据资料、仪器设备、甚至是人等各种相关的资源。网格能够充分吸纳各 种计算资源。 网格概念的提出从根本上改变了人们对计算的看法，它突破了以往强加在计 算资源上的种种限制。首先是计算能力大小的限制，网格所提供的计算能力理论 上近乎无限，在这种计算能力的支持下，人们可以做许多以前无法想像和无法完 成的工作。其次是地理位置的限制，网格通过网络将处在不同地理位置的资源连 接起来，并通过一套管理系统加以管理，可以使本地用户方便的使用异地资源， 第二章网格计算和负载平衡 而不需要到异地资源所在地去。另外，网格还打破了传统的共享和协作方面的限 制，可以在动态跨组织域的虚拟组织内实现协同的资源共享和问题求解 2 】。以 前对资源的共享往往停留在数据文件传输的层次，而网格资源的共享允许直接控 制其他资源，而且共享资源的各方在协作时可以以多种方式更广泛地交流信息， 充分利用网格提供的各种功能。 2 1 2 网格特点 网格计算属于分布计算研究领域，但与传统分布计算相比，它还具有一些重 要的特点，这些特点对于网格构建、网格研究和网格应用有着重要的影响。网格 主要包括以下四个特点【3 】： ( 1 ) 资源分布共享 网格资源是分布的，它们分布在地理位置不同的许多地方，跨越地理范围较 广，涉及的资源规模较大。在这种分布环境下，网格计算需要解决网格资源针对 任务的分配和调度问题、传输和通信问题、人与系统以及人与人之间的交互和协 同问题、网格应用在分布环境中自动执行和协作问题。同时资源共享是网格建设 的目的，即网格上的任何资源都可以提供给网格上的任何使用者。解决分布式的 共享问题，是网格的核心内容。分布式是网格硬件在物理上的特征，而共享是在 网格软件支持下实现的逻辑上的特征，这两者对于网格来说都是十分重要的。 ( 2 ) 资源自治统一管理 网格上的资源首先属于某一本地的个人或者组织，网格资源的拥有者对资源 具有最高级别的管理权限，网格允许资源拥有者对其资源有自主的管理能力，这 就是网格资源的自治性。同时，这些资源根据一定的约束和规则接受网格的统一 管理，实现资源的共享和互操作，这使得网格管理更为复杂，具有管理的多重性。 ( 3 ) 资源异构 网格资源是异构的，并且类型复杂，对于计算资源，有不同类型的计算机， 不同的计算方式，不同的计算接口，不同的系统架构；同样，对于存储资源及其 他设备和资源也面临着同样的问题。因此，网格既要具有利用资源的异构特点进 行处理的能力，也要具有提供一致资源管理的能力。 ( 4 ) 资源动态性强 。网格的动态性包括动态增加和动态减少两方面的含义。由于网格资源分布自 治，决不能假设网格环境是一成不变的。某一时刻拥有的资源或者功能，在下一 时刻可能就会出现故障或者不可用：而原来没有的资源，可能随时会不断加入进 来。网格资源的动态变化特点要求网格管理必须充分考虑并解决好这一问题，对 于网格资源的动态减少或出现故障，需采取措施，实现任务的自动迁移，对用户 第二章网格计算和负载平衡 透明或尽可能减少用户的损失。资源的动态增加要求网格具有可扩展性，新加资 源自然加入网格，和原有资源融合在一起，共同发挥作用。 2 1 3 网格体系结构 网格体系结构给出了网格的基本组成与功能，描述了网格各组成部分的关 系，体现了网格的整体架构和实现机制。 网格最早提出的时候，采用了五层沙漏结构 2 】。五层沙漏结构的主要特点 就是以协议为中心，十分强调服务与编程接口和软件开发包，强调对物理资源和 这些资源所支持的服务的共享。 五层沙漏结构根据该结构中各组成部分与共享资源的距离，将对共享资源进 行操作、管理和使用的功能分散在五个不同的层次，由下至上分别为构造层、连 接层、资源层、汇聚层和应用层。在五层结构中，资源层和连接层共同组成了瓶 颈部分，使得该结构呈沙漏形状。g 1 0 b u st o o l k i t2 是基于五层沙漏结构的。 f o s t e r 等结合w 曲s e r v i c e s 技术提出了开放网格服务结构o g s a 4 】。o g s a 最基本的思想就是以“服务”为中心。在o g s a 框架中，将一切抽象为服务， 包括各种计算资源、存储资源、网络、程序、数据库等等，简而言之，一切都是 服务。这种观念，有利于通过统一的标准接口来管理和使用网格。在o g s a 中， 将一切都看作网格服务，因此网格就是可扩展的网格服务的集合。网格服务可以 以不同的方式聚集起来满足虚拟组织的需要，虚拟组织自身也可以部分地根据他 们操作和共享的服务来定义。g l o b u st o o l k i t3 完全基于o g s a 架构。 o g s a 希望能最终与w e bs en r i c e s 技术完全融合，但是其所基于的技术规范 o g s i 却存在一些缺点，使得两者融合起来相当困难。所以新的架构w s r f 5 】被 制定了出来，以便克服o g s i 的缺点。 w s i 心采用了与网格服务完全不同的定义：资源是有状态的，服务是无状态 的。定义出一个通用且开放的架构，利用w 曲服务对具有状态属性的资源进行 存取，并包含描述状态属性的机制，另外也包含如何将机制延伸至w e b 服务中 的方法。最新的g l o b u st o o l k i t4 是基于w s r f 的。 2 1 4 网格调度和资源管理 资源管理和任务调度是网格计算的关键技术，资源管理要解决资源的描述、 组织和管理等关键问题。网格调度是将网格作业映射到多管理域的资源上的过 程。根据当前系统的负载情况，并考虑满足使用者和应用的需求，调度器对系统 内的任务进行动态调度，提高系统的运行效率。 网格环境中的资源是分布的、异构的、由不同的组织和个人所拥有，每个拥 第二章网格计算和负载平衡 有者都有各自的资源管理策略和不同的访问代价模型，因此管理网格资源是很复 杂的。网格的用户主要是同资源访问代理交互，从而不需了解资源计算的复杂性。 资源访问代理通过网格信息服务器发现用户能够访问的资源，使用中间件服务同 资源代理协商，将任务分配到资源上，协调应用和数据处理的执行过程，并收集 计算结果。资源访问代理还负责监控资源的执行过程，负责管理网格结构的变化 及资源故障。 网格调度分为集中式调度，分布式调度和分层式调度【6 】。在集中式调度环 境中，一个中央节点扮演着资源管理者的角色，它将作业调度到环境周围的其他 节点。分布式调度中没有中央调度者负责管理所有的作业，涉及多个本地调度者， 其任务是彼此交互以分配作业给参与的节点。在具体进行任务调度的时候，各个 网格环境可以根据不同的情况采用不同的调度策略。 网格调度包括资源发现、资源选择、调度产生和作业执行四个主要阶段 6 】。 资源发现的目的是识别已认证的可利用资源的动态信息列表，这些资源可用于作 业提交。资源选择是选择资源，在最大程度上满足使用者的要求和条件。调度产 生包括：从待执行的作业队列中挑选出一个作业和为执行作业选择最好的资源产 生资源选择方案两个步骤。作业执行就是将作业提交给资源来执行。 2 2 性能预测 2 2 1 性能预测意义 在网格的发展过程中，由于网格环境自身的特征，使得网格性能预测的重要 性日益显现出来。我们可以根据网格活动的历史运行状况，就某一事件的主要特 点进行分析和规律总结，预测未来一段时间内网格活动的情况，提前做好未来活 动所需资源的准备工作，提高响应速度，进而提高网格的性能。网格环境中性能 预测的意义主要有以下几点 7 1 ： 首先，性能预测是高效的资源管理的基础。网格资源数量巨大，种类繁多， 且具有异构特质，如何进行有效的资源管理与分配，是网格环境要解决的重要问 题之一。而性能预测提供网格资源未来的性能数据，可以对空闲的资源加以充分 利用，避免资源的闲置浪费，因此，性能预测可以提高网格资源的利用率。 其次，性能预测为高效的负载平衡提供支持。网格为用户提供的种种服务最 终要依靠网格任务在资源集上的本地执行来实现，如何对大量的网格任务进行分 配和再分配才能既保证任务的执行性能又充分利用可用资源，调度器首先需要获 得未来的资源性能数据，然后需要估测任务在这种资源性能环境中能够获得什么 第二章网格计算和负载平衡 样的运行性能，这些正是资源性能预测所要解决的问题。 再次，性能预测可以提高网格服务质量。不同的网格服务有着不同的资源需 求，这些资源需求制约着网格服务性能的发挥。而由于网格资源的共享性，网格 资源的性能是动态变化的，因此，需要对资源性能做出预测，才能保证服务的运 行性能，提高服务质量。另外，为了保证服务质量，网格中还采取一种资源预约 的办法，如果能够预测未来的请求用户，则可以提高资源预约的效率，保证网格 服务质量。 最后，性能预测可以保证网格系统的负载平衡。网格中存在着大量服务，这 些服务运行于一个巨大的、异构的、动态的资源集上，如何对这些大量的服务进 行合理的调度，以避免有些资源过分空闲而另一些资源过分繁忙的现象出现，这 不仅要求对资源的性能进行预测，而且还要对网格服务在资源可用度预测提供的 “沙箱”中运行时所能取得的性能表现做出预测，如此才能保证服务的合理调度 分配，保持网格系统的负载平衡。 2 2 2 性能预测分类 性能预测方法主要分为以下四类 8 】： ( 1 ) 特征估算法 算法的运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计 算机执行简单操作( 如赋值操作，比较操作等) 所需时间与算法中进行简单操作 次数的乘积。特征估算法是根据问题的规模和算法自身特点的分析，计算出各简 单操作次数。然后依据算法的语言实现和编译程序及资源属性得出各简单操作 ( 包括简单计算，简单通信，简单数据产生) 在资源上的处理时间。最后进行简 单操作次数的乘积预测出算法的运行时间即任务的完成时间。 ( 2 ) 资源预测转化成应用程序预测 资源监控是资源预测的基础，计算网格需要实时、准确、动态的性能监控信 息。根据这些监控信息，形成资源预测模型，得到资源的时间预测序列，预测在 给定时间内资源的使用情况。 根据应用程序在空载主机上的执行时间和主机资源预测序列计算出网格应 用程序在负载主机上运行时间的置信区间。 ( 3 ) 源码结合资源的综合分析法 应用工具从源码级别或者编译生成的目标代码级别获得应用程序的特征信 息，并用这些信息建立应用程序特征模型，作为评估预测引擎的一个输入。资源 工具周期性地监测资源的性能信息，并用这些信息建立资源特征模型，作为评估 预测引擎的另一个输入。评估引擎通过对两个建立好的模型进行综合分析，得出 9 第二章网格计算和负载平衡 应用程序性能预测。 ( 4 ) 应用程序历史信息预测法 相似的应用程序在执行时间上有相似性，这种相似性规律是这种预测方法的 基础，用曾经执行过相似应用程序的执行时间得出预测。核心是定义应用程序特 征的搜索策略，为预测定义应用程序的相似性。根据相似性的定义，把以前执行 过的任务按照不同的范畴分类，同一类任务具有相似性。然后利用同类任务，计 算新任务的预测值。 2 2 3 性能预测常用方法 一般说来，预测方法分为两大类。一类是定性预测，也称为直观性预测；另 一类是定量预测，它采用数学、数理统计或人工智能的方法进行预测。常用方法 包括以下几种 7 】： ( 1 ) 定性预测技术 用它来预测时，要用到与该预测对象相关的所有情报和判断资料。这类技术 通常用于对预测对象的历史情况不了解或了解很少的场合。这类预测常以市场调 查研究、特尔斐法或者其他类似的方法为基础。 ( 2 ) 时间序列分析预测技术 这类技术根据历史数据的统计分析来进行预测。其基本设想是过去的趋势会 持续到未来。所谓预测就是根据以往的动向，对未来若干时间间隔的估计。包括 移动算术平均模型，自回归模型，移动平均模型，自回归移动平均模型，白回 归差分滑动平均模型，自我平衡预测，趋势预测等等。 ( 3 ) 回归分析法 回归分析也称为解释性预测，它假设一个系统的输入变量和输出变量之间存 在着某种因果关系，通过研究输入变量与输出变量之间的关系，建立预测模型， 明确相互关系的密切程度，然后以输入变量为依据预测输出变量的变化。常用的 有线性一元回归法和线性多元回归法。 ( 4 ) 马尔可夫预测 使用马尔可夫预测法进行预测，先在状态空间中划分出若干状态，建立起这 些状态之间的状态转移概率矩阵，然后根据n 步转移概率矩阵计算未来n 时刻后 预测对象所处的状态。 ( 5 ) 神经网络系统 神经网络系统是由大量的、同时也是很简单的处理单元( 或称神经元) 广泛地 互相连接而形成的复杂网络系统。在神经网络中，修改权值的规则称为学习算法， 这些权值可以根据经验或学习来改变。这样，系统就可产生“进化”，产生更好 1 0 第二章网格计算和负载平衡 更准确的预测结果。 性能预测是网格架构最为重要的组成部分之一。由于不同的网格资源( 组成 网格的节点主机、网络、存储系统等) 能够提供给服务的性能往往相差巨大，并 且由于竞争的存在，同一个资源所能提供的性能也会发生动态变化，所以调度器 必须知道任务在实际运行的时候能够获得什么样的资源性能，以便能够在资源池 众多的可用资源中做出选择，使该网格任务获得最大性能，同时性能预测不能给 系统带来过多的负担，以免使系统的总体性能下降。为了在做出准确的预测和预 测自身代价之间取得折中，我们结合具体的天文图像合成网格服务自身特点和应 用背景，建立起能够准确刻画服务完成时间与各种资源性能之间关系的数学模 型，提出了基于蚂蚁算法的网格资源性能预测方法。 2 3 负载平衡 2 3 1 负载平衡概述 对于一个分布式计算机系统，由于任务到达的随机性，以及各处理结点处理 能力上的差异，当系统运行一段时间后，某些结点分配的任务还很多( 称之为超 载) ，而另一些结点却是空闲的( 称之为轻载) 。一方面，使超载结点上的任务尽可 能快地完成是当务之急；另一方面，使某些结点空闲是一种浪费。如何避免这种 空闲与忙等待并存的情况，从而有效地提高系统的资源利用率，减少任务地平均 响应时间，这成为了负载平衡产生的原因。 负载平衡试图均衡所有结点上的负载，以使得所有结点上的负载基本相等， 这种相等并非简单的任务数目相等，而是依据这些异构结点的性能分派的加权相 等，同时，负载平衡支持并行应用，它选取一些结点机作为并行处理单元，来构 造一台虚拟的并行机，并给它们分配一定的任务以实现并行计算。 一个好的负载平衡算法必须考虑以下几条要求 1 l 】： 有效性，算法的运行提高了系统的效率( 如降低了任务平均响应时间) 。为 提高算法的有效性，要求系统用于负载平衡的附加代价尽可能小。 稳定性，就是系统正常工作的能力。特别是当系统内大多数结点处于重载状 态时，算法的运行提高了系统的性能，而不是使重载的情况进一步恶化。为了提 高系统负载平衡的稳定性，要求解决任务迁移的抖动问题。 可靠性，一个结点的崩溃，并不影响其他结点的正常工作。 用户透明性，用户不必知道交付的任务具体在哪台机器上执行，对用户来说， 任务的迁移和远程执行都是透明的。 第二章网格计算和负载平衡 通用性，算法应该适用不同网络拓扑结构和不同机器数目。 2 3 2 负载平衡分类 所谓负载均衡就是要均衡计算结点上的负载，使其基本相等。在负载出现不 平衡时，需要进行负载的迁移。当然，平衡各结点的负载需要在计算能力和通信 开销之间进行权衡。负载均衡是提高并行程序执行效率的重要因素。关于负载均 衡有各式各样的设计方案，主要分为三类 1 0 】： 第一是静态负载平衡。任务分配与结点机当前状态无关。它是根据以往的经 验或系统本身信息的收集，把用户的任务分配给各结点机或对某些结点上的任务 进行重新分配。它的优点是较易实现，对轻载网络，静态负载平衡是种有效的方 案。 第二是动态负载平衡。当结点机的运算能力差别或负载波动较大时，应要考 虑动态负载平衡策略。在网络并行计算环境中，动态负载平衡就是系统根据当前 的负载分布情况，对新到任务进行动态分配或对各个结点上的负载进行动态的调 整，使重载结点的任务减少，轻载结点的任务增多，从而提高系统资源的利用率， 减少任务的平均响应时间。 第三是自适应负载平衡算法。它们通过动态地改变其参数、策略来调节其活 动以适应变化的系统状态。例如，在一定的情况下，某些负载分配策略执行得比 其它的更好，而在别的情况下，另外的策略更好，那么一个简单的自适应算法可 能根据对系统状态的观察来选择合适的负载分配算法。 动态负载平衡算法按照集中程度可以分为集中式、完全分布式、层次性或它 们中的一些结合算法【1 0 】。在动态集中式负载平衡的系统中，全局负载信息收集 在一个结点上，任何结点的负载变化信息都传给这个结点，负载平衡所有决定由 它作出。这种方式的好处在于能够以较少的开销收集全局信息，挑选出最佳结点 执行任务，并且可以扩充到较大的网络计算系统。在完全分布式负载平衡系统中， 每个结点保存相邻结点或系统中部分结点的负载信息，相互合作做出各自的负载 分配。这种策略实现较简单，并经过一段时间后，可以选择到较合适的结点执行 任务。缺点是不能获得最佳结点分配负载，很难扩展到成千上万个结点的网络计 算系统。层次性方法是根据集中式、分散式方法的优缺点结合而成的一种负载平 衡算法。它将系统分成层次性的子系统，在不同层次上特殊的结点作为负载平衡 决策的控制结点，以分散的集中方式控制整个系统的负载平衡。它和网络拓扑结 构有很强的相关性。 动态负载平衡在实际实现上，还存在如下两个问题【9 】：( 1 ) 各结点机的负载 评价。影响一台机器的负载因素非常复杂，如c p u 队列长度，可用资源的情况， 第二章网格计算和负载平衡 交付任务的要求等，有些信息是得不到或不准确的。( 2 ) 任务迁移的抖动问题。 由于存在网络延迟，通讯受阻等问题，使决策所用的信息过时，就可能使某一任 务在结点机间来回迁移，从而降低了系统的效率。因此设计出一种高效的、适用 面广，稳定可靠的负载平衡算法，在网络并行计算中就显得非常重要。 2 3 3 任务调度分类 调度问题是并行和分布式系统研究领域中最重要的问题之一。调度问题可以 依据负载的属性分为以下三个类别【1 4 】： 第一、负载不可划分调度。这类负载相对独立，不能进一步划分为子任务， 只能整体分配到一个处理器上执行。不可分负载调度问题是一个装箱问题，已被 证明是n p 完全问题，在实际场景中常通过一些启发式方法求取任务调度的次优 解。在动态任务调度中，调度器根据当前系统的状态分配动态产生的任务。 第二、负载模块可划分调度。负载可基于负载属性和系统的状态根据先验知 识划分为更小的模块。仅当所有模块执行完时整个负载才算处理完毕。模块之间 存在着优先执行的约束关系，即某个模块必须等某些模块执行完才能开始执行。 模块可分负载，可通过有向无环图( d a g ) 表示，节点表示模块任务，边表示 模块间的执行约束关系。d a g 调度问题已被证明是n p 完全问题。 第三、负载可任意划分调度。每个负载片都可以被单独处理，且负载中的所 有元素所要求的处理类型相同。所谓可以任意划分，是指负载可以划分成任意多 个不相交的负载片，每个负载片可以有任意大小。这类应用被称为可任意划分负 载，简称可分负载。 最早的可分负载调度研究出现在1 9 8 8 年 1 3 】。由于日益增长的数据并行应 用的需求，近几年来它已经成为并行调度领域新的研究热点。在大型实验数据的 处理、图像与信号处理、数据挖掘、计算生物学、科学计算、银行保险和各种在 线服务等领域中很多重要的应用都属于可分负载。可分负载的调度理论可以应用 在从并行机到计算网格的各种计算平台，如线性网络，总线网，树网，超立方体， 二维和三维阵列等网络拓扑结构。 由于可分负载调度采用线性模型对应用和网络建模，并且充分利用了负载可 任意划分的特性，可以使用连续数学的方法进行分析，模型简单易于处理，很多 重要类型的可分负载理论问题都可以获得最优解的解析解 4 8 【5 0