（计算机软件与理论专业论文）基于大数分解算法对nomangrid的性能测评.pdf

摘要 摘要 网格通过组织各种网络空闲资源，为用户提供方便强大的服务接口，以实 现计算资源、存储资源、数据资源等的全面共享。已有的计算网格系统都存在 中心管理节点，网络通信和管理开销制约着i n t e m e t 上大规模普通计算资源的有 效利用，为解决这一瓶颈而设计的n o m a n g r i d 采用无管理节点式的体系结构， 在实现模块采用有效的信息管理机制、递归资源调度算法，从而不需要任何的 中心节点来对系统中全局或者局部的资源进行管理。 n o m a n g r i d 原型系统设计完成之后，需要对原型系统的计算能力、信息管 理机制的有效性以及任务调度的正确性进行测评，为考察系统的运行效率以及 计算能力，选取参数扫描型的应用问题，设计符合要求的实验方案来检验 n o m a n g r i d 原型系统的性能。大数分解应用具有高吞吐和高计算量，需要大量 计算资源，从而符合n o m a n g r i d 原型系统的任务需求。 本文基于大数分解算法中的椭圆曲线算法设计了在典型网络拓扑结构上的 实验方案，实现椭圆曲线分解算法的并行化，把大数分解过程划分成相互之间 完全独立的多个子任务，这些子任务之间没有约束，在计算过程中不会产生通 信，从而符合参数扫描型的任务需求。通过在n o m a n g r i d 原型系统的运行，在 不同规模的应用问题，不同的节点规模上对大数分解算法进行测试，收集数据 数据，分析实验结果，对n o m a n g r i d 原型系统的性能进行了分析和评价。 实验结果显示n o m a n - g r i d 通过在没有中心服务器的前提下，把网络通信量 均衡的分布到系统中各个节点，同时保证了有效的调度任务，使系统中所有的 节点都得到充分的利用，任务负载与节点的计算能力基本成正比，而且对环境 的动态性有一定的适应能力，可以在故障情况下继续正确运行。n o m a n - g r i d 系 统的表现符合预期目标，在高吞吐率计算领域可以有更大的发展前景。 关键词：网格计算参数扫描大数分解任务划分评价分析 a b s t r a c t a bs t r a c t g r i dc o m p u t i n gs y s t e mp r o v i d e su s e r sw i t hp o w e r f u la n dc o n v e n i e n ts e r v i c e i n t e r f a c e st os h a r et h ec o m p u t a t i o n 、d a t aa n ds t o r a g er e s o u r c e sb yt h eo r g a n i z a t i o no f t h ec o m p u t e ri d l et i m eo ni n t e m e t b u ti np r e v i o u sy e a r s ，t h ec o m p u t a t i o ng r i d s y s t e mi n c l u d e sm a n a g e m e n tn o d e ，w h i c hm a k e sn e t w o r kc o m m u n i c a t i o n sa n d m a n a g e m e n tc o s th i g h ，b e c a u s eo ft h eh e t e r o g e n e i t ya n dd y n a m i co ft h ei n t e m e t ， t h es c a l eo f 酣dc o m p u t i n gi su s u a l l yr e s t r i c t e d t os o l v et h e s ep r o b l e m s ，af u l l y d i s t r i b u t e dg r i dc o m p u t a t i o nm o d e lb a s e do nn o d ea u t o n o m y , a sw e l la sa l l i n f o r m a t i o nm a n a g e m e n tm e c h a n i s m ，ar e s o u r c e ss c h e d u l ea l g o r i t h ma n das o l u t i o n f o rt h ed y n a m i co fe n v i r o n m e n tm a t c h e d ，i si n t r o d u c e di nt h i sd i s s e r t a t i o n a c c o r d i n g t ot h i st h e o r y , p r o t o t y p es y s t e mn a m e dn o m a n - g r i di sd e s i g n e da n dr e a l i z e d 、析t l lt h e p r i m a r ye x p e r i m e n ta n da n a l y s e s a f t e rt h en o m a n g r i ds y s t e mi sr e a l i z e d ，t h ee f f e c t i v e n e s so fi n f o r m a t i o n m a n a g e m e n tm e c h a n i s m s ，a n dt h ec o r r e c t n e s so ft a s ks c h e d u l i n gs h o u l db ee x a m e d i n o r d e rt ot e s t s y s t e m se f f i c i e n c ya n dc o m p u t i n gp o w e r , c h o o s et h ep a r a m e t e r so f t h ea p p l i c a t i o no fs c a n b a s e dd e s i g nt om e e tt h er e q u i r e m e n t so ft h ee x p e r i m e n t a l p r o g r a mt ot e s tt h ep r o t o t y p es y s t e mn o m a n g r i dp e r f o r m a n c e t h ea p p l i c a t i o no f b i gn u m b e rf a c t o r i z a t i o nh a v eh i g l lt h r o u g h p u ta n dh i g hc a l c u l a t i o nc a p a c i t y , a n d n e e dal a r g en u m b e ro fc o m p u t i n gr e s o u r c e s ，t h e r e b yi tm e e tn o m a n g r i dp r o t o t y p e s y s t e m sd e m a n d t k sa r t i c l eu s e st h ee l l i p t i cc u r v em e t h o d st od e s i g ns e v e r a ls p e c i a lp r o g r a m st o t e s tt h ep e r f o r m a n c eo fn o m a n g r i d t h ea l g o r i t h mi sd i v i d e di n t ot h o u s a n d so f i n d e p e n d e n ts u b - t a s k s ，w h i c hh a v en oc o m m u n i c a t i o n sd u r i n gt h ew h o l ec a l c u l a t i o n o ft h ef a c t o r i z a t i o n , a n dt h u ss a t i s f i e st h ep a r a m e t e r ss w e e p i n g sr e q u i r e s t h e e x p e r i m e n t sa r ed o n ei nd i f f e r e n ts i z eo fn o d e sa n dt o p o l o g y b yt h ea n a l y s i so f e x p e r i m e n t a lr e s u l t s ，t h en o m a n g r i dp r o t o t y p es y s t e m sp e r f o r m a n c ei st e s t e d t h ee x p e r i m e n t a ld a t as h o w st h a tt h es y s t e mb a l a n c e st h en e t w o r kt r a f f i ca n d d i s t r i b u t e si tt oa l ln o d e se q u a l l yw i t h o u tac e n t r a ls e r v e r , w h i l ee n s u r i n gt h ee f f e c t i v e n a b s t m c t t a s ks c h e d u l i n g ，b e s i d e st h ee n v i r o n m e n th a v ead y n a m i ca d a p t a b i l i t yt oa v o i d n e t w o r kf a u l t s ot h a ta l lt h en o d e sa r ef u l l yu t i l i z e da n dt h et a s kl o a di sp r o p o r t i o n a l t ot h ec o m p u t i n gc a p a b i l i t y k e yw o r d s ：g r i dc o m p u t i n gp a r a m e t e rs w e e pi n t e g e rf a c t o r i z a t i o nt a s k s c h e d u l et e s t i n g a n a l y s i s i i i 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外j 本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 第一节网格的发展和现状 二十世纪六十年代末，人类采用信息包传输和开放式整体结构技术，组建 了a r p a n e t ，从而诞生了i n t e r n e t 1 1 。到了九十年代初，万维网应运而生，随着 人们日常工作遇到的商业计算越来越复杂，人们越来越需要数据处理能力更强 大的计算机。网格技术正是在此背景之下出现，并且正在逐渐地由一个新兴名 词转变成为运用于商业、科研、医药等各行业的技术产物。 网格一词译自英文单词“g r i d ”，是把整个因特网整合成一台巨大的超级计算 机，它的发展目标是利用网络上的闲余计算资源，并把它们虚拟成为高性能计 算机，使用户能利用它解决高计算量的问题1 2 】。最终实现计算资源、存储资源、 数据资源、信息资源、知识资源、专家资源的全面共享，其规模可以大到某个 洲，小到企事业内部、局域网、甚至家庭和个人。 网格计算最初的定义为：计算网格是一个硬件和软件的基础设施，它提供 了可靠的、一致的、普遍的和廉价的方法来获得高端的计算能力【3 j ，该概念强调 的是地理上分布的资源之间的共享和协同；同时相关研究者也给出了网格定义 的三个标准：一是在非集中控制的环境中协同使用资源，二是使用标准的、开 放的和通用的协议和接口，三是提供非平凡的服务。 网格的发展经历了三个阶段：第一阶段是网格的萌芽阶段，开始于9 0 年代 早期，研究内容是关于千兆网试验床以及一些元计算方面的工作；第二阶段是 一些早期的试验，时间大概从9 0 年代中期到晚期，出现了一些比较重要的开创 性和奠基性的研究项目，比如i w a y 4 1 ， g l o b u s t s ! ，l e g i o n i 6 1 等；目前是网格计 算的迅速发展阶段，关于网格的研究、开发和应用项目大量出现，出现了影响 很大的组织全球网格论坛g g f ( g l o b a lg r i df o r u m ) ，同时网格计算也不再仅仅 局限于科学研究，工业界与学术界联盟，正致力于使网格计算在更广泛的领域 得到推广和应用。 根据网格共享资源的目的，计算机科学家提出并实现了多种网格，如以共 享计算资源为目标的计算网格、将网络上信息资源进行有效组织的信息网格、 面向广域网环境中数据的管理与传输的数据网格、为各种计算资源提供统一的 服务访问方式的服务网格等。当前在复杂科学计算领域中仍然以超级计算机作 第一章引言 为主宰，但是由于其造价极高，通常只被用于航天局、气象局这样的国家级部 门。网格计算【7 】( g r i dc o m p u t i n g ) 作为一种新的计算模式，以其低廉的造价和 超强的数据处理能力倍受青睐。目前很多大公司开始投入其中，如i b m 构筑的 一项名为g r i dc o m p u t i n g 的计划，旨在通过因特网，向每一台个人电脑提供超 级的处理能力。2 0 0 1 年1 1 月，s u n 推出了s u ng r i de n g i n e 企业版软件的p 版【8 j ， 旨在促进网格计算的发展。 2 0 0 2 年网格首次运用到商业领域。除此以外，网格还可运用于生物医学， 提供药品开发人员所需的计算能力，用以研究药物和蛋白质分子的形态与运动； 运用于工程；用网格计算进行复杂的仿真与设计；用于数据搜集分析，地理信 息科学、制造、石油加工、货物运输、甚至零售企业都要维护昂贵的设备，时 常会出现问题，造成不好的结果，网格能够存储和处理所有交易；用于娱乐产 业、特殊效果设计、超级视频会议等。 第二节网格计算的关键问题 网格计算为大运算量的复杂问题提供了新的解决方案，在世界范围内有许 多正在研究或已经投入使用的网格项目，如g l o b u s t g l 、l e g i o n 、e u r o g r i d t l o 】等， 我国有国家高性能计算环境( n h p c e ) 和中科院的织女星网格【l l 】等研究项目。 高吞吐率网格计算的研究主要关注以下几个方面的性能：中心性、可扩展 性、和安全性。 1 2 1 管理节点的中心性 资源管理【1 2 】是网格计算的重要功能之一，但i n t e m e t 上资源众多，分属于不 同的管理域，且具有异构性和动态性，实时监视这些资源的动态信息，需要巨 大的管理及网络等开销，同时也限制了网格计算系统的规模。 以s u p e r w e b 、j a v e l i n 、c h a r l o t t e 为代表的系统，采用单一的中心代理来完 成用户请求、空闲资源管理和任务调度等所有的管理工作，这使得中心成为瓶 颈，并且具有潜在的单点失效，造成系统瘫痪的风险。 这些代表性系统的研究表明，对大量动态变化的资源无论是进行集中管理 还是分布式管理都需要巨大的管理和通信开销，这本质地制约着i n t e r n e t 上大规 模普通计算资源的有效利用。 为解决上述问题，x t r e m w e b 、b a y a n i h a n 、以及j a v e l i n 的后续研究j a v e l i 叶斗、 2 第一章引言 j a v e l i n2 0 等系统采用代理网络来替代单一的代理，每个代理管理有限数量的资 源，同时由一个中心服务器来管理所有代理。由此带来的管理开销以及维护代 理间的一致性和同步的开销都是非常大的。 还有些网格系统，如s e t t h o m e 将服务分散到多个服务器，x t r e m w e b 和 b a y a n i h a a 采用代理服务器网络来取代单一的中心代理，但由于管理节点的存在， 限制了系统的可靠性和可扩展性。因此如何消除中心制对网格系统的影响是发 展网格需要解决的关键问题。 1 2 2 网格规模的可扩展性 网格可以提供动态的服务，能够适应网络的变化。同时网格并非限制性的， 它实现了高度的可扩展性。 对于高吞吐计算环境来说，共享的主要是连接在i n t e m e t 上大量的普通计算 资源，如个人电脑、工作站等，要想在性能上超过现有的超级计算机，高吞吐 率计算环境必须能够容纳超大规模的资源。如果一个网格系统能够将i n t e r n e t 上 连接的千万台计算资源集成起来，统一为一个大规模应用服务，其能够达到的 规模将是惊人的。要在网格资源规模不断扩大、应用不断增长的情况下，不降 低性能是网格计算要解决的问题。 另一方面，i n t e m e t 是一个异构的环境，包含各种各样的计算资源，这些计 算资源往往具有不同的c p u 类型、不同的操作系统等；要想共享多种异构的计 算资源，高吞吐率计算环境必须能够适应不同的平台，提供一个统一的资源访 问接口，使用户能够方便地使用远程计算资源。目前很多高吞吐率计算环境均 采用j a v a 作为编程语言，正是由于其良好的可移植性和跨平台特性。 在i n t e m e t 环境中，由于i p v 4 1 3 j 的限制，很多企业、公司、校园网内的大量 计算资源无法拥有一个公有的i p 地址。通常采用方法是各个公司内部或校园网 内建立一个自己分配i p 地址( 私网地址) 的i n t r a n e t 网络，然后通过一个或多 个拥有公有i p 地址的服务器网关接入到i n t e m e t ，使内部的计算机可以访问外部 具有公有地址的计算机，现有的i n t e m e t 技术可以通过n a t t l 4 】( n e t w o r ka d d r e s s t r a n s l a t i o n ) 和n a p t ( n e t w o r ka d d r e s sp o r tt r a n s l a t i o n ) 很好的支持这一点， 但是外部的计算机主动与私网内的计算机通信，特别是某个私网内的计算机与 另一个私网内的机器的相互通信却非常困难，到目前为止没有一个很好的解决 方案。如果能解决这个问题，不仅能使高吞吐率环境容纳更大范围内的计算资 第一章引言 源，而且能够增加更多的应用范围，如企业之间、公司之间的计算资源共享， 多个校园网之间的资源共享等。 1 2 3 信息资源的安全性 i n t e m e t 的安全性主要提供两方面的安全服务：( 1 ) 访问控制服务，用来保 护各种资源不被非授权使用；( 2 ) 通信安全服务，用来提供认证，数据保密与 完整性，以及通信端的不可否认性服务。但这两个安全服务不能完全解决网格 系统的安全问题。网格系统必须具有抗拒各种非法攻击和入侵的能力，确保系 统的正常高效运行和保证系统中的各个信息的安全。因此，网格系统的安全问 题的覆盖面更广，解决方案也更加复杂。 一个网格系统的网格安全体系在考虑i n t e m e t 安全问题之外，还必须考虑网 格计算环境的如下特征：( 1 ) 网格计算环境中的用户数量很大，且是动态可变 的；( 2 ) 网格计算环境中的资源数量很大，且是动态可变的；( 3 ) 网格计算环 境中的计算过程可在其执行过程中动态请求，启动进程和申请、释放资源；( 4 ) 一个计算过程可由多个进程组成，进程间存在不同的通信机制，底层的通信连 接在程序的执行过程中可动态地创建并执行：( 5 ) 资源可支持不同的认证和授 权机制；( 6 ) 用户在不同的资源上可有不同的标识；( 7 ) 资源和用户属于多个 组织。正是由于网格计算环境的特殊性，因此在设计网格安全机制时特别要考 虑计算环境的动态主体特性，并要保证网格计算环境中不同主体之间的相互鉴 别和各主体间通信的保密性和完整性。 对于基于i n t e m e t 的高吞吐率计算环境来说，所有的资源都是连接在i n t e m e t 上，为所有用户服务，用户也是通过i n t e m e t 将任务提交到不同的计算资源上， 一个良好的高吞吐率计算系统应能保证资源提供者和用户的安全。对于资源提 供者来说，系统不能破坏资源提供者的资源，不能泄漏其隐私，保证其所提供 的资源的绝对安全，这是资源提供者愿意加入系统的前提；而对于用户来说， 任务通过i n t e m e t 发布到各个计算资源上，系统应保证用户的商业秘密不被泄漏， 这是用户愿意使用系统的前提。但由于基于i n t e m e t 的高吞吐率环境中资源和用 户的大规模和动态性，其安全性比一般的网格计算系统更加难以保证。 网格研究除了上面的三个主要特点外，网格计算还至少需要具备基本的任 务管理功能。用户提交任务、为任务指定所需资源、删除任务并监测任务运行 状态。任务调度：用户提交的任务由该功能按照任务类型、所需资源、可用资 4 第一章引言 源等安排运行日程和策略：资源管理：确定并监测网格资源状况，收集任务运 行时的资源占用数据。这些问题也是目前因特网普遍存在的问题。 本文主要研究适用于高吞吐率计算的计算网格，讨论对环境动态性具有自 适应能力的完全分布式体系结构和相关算法，设计并实现无资源管理白协调网 格计算的原型系统，并对此原型系统进行测试和讨论。 第三节网格测试的介绍 网格系统的测试主要包括两个部分：功能性测试和性能测试。 功能测试( f u n c t i o nt e s t i n g ) ：验证测试软件功能能否正常按照它的设计工作。 测试运行软件时的期望行为是否符合原设计，一般采用白盒测试方法。 性能测试( p e r f o r m a n c et e s t i n g ) ：评价一个产品或组建与性能需求是否符合 的测试。包括负载测试、强度测试、数据库容量测试、基准测试等类型。 性能测试的目标是验证在各种负载情况下网格服务的性能。进行性能测试 的最佳方式是使得多个测试客户运行完整的网格服务测试，包括请求提交和应 答验证。 网格性能测试可以模拟频繁使用网格服务的情况，进而才能发现所存在的 缺陷。网格软件性能测试解决方案主要包括： 多机测试：可以在网络中利用多台机器或通过运行模拟虚拟用户的网格软 件测试工具，从而可以产生比单一机器所能够产生的数目更大的负载。 定制场景：网格软件性能测试工具应至少提供默认的负载测试场景( 如各 种拓扑等) ，或者允许测试用户定制的特殊场景，如节点加入和节点失效等情况。 这些场景可以模拟现实世界中可能发生的情况，而这些情况在正常使用网格服 务时发生的可能性较大。 监视器：网格软件测试中的监视器可以在负载测试发生时监视各种系统资 源，包括各节点的任务分布情况、各节点的消息发送情况等。 快捷方便的测试用例管理与维护，对于构建一个合理而有效的网格软件测 试环境是必不可少的。在设计面向服务的网格系统软件测试方案时，针对网格 系统所提供的系统a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) 接口和相应的网格 服务，提供相应的测试方案。 通过网格系统测试方案提供统一的任务生成管理等功能。这种体系结构的 第一章引言 优点是灵活性和可扩展性，可以根据网格系统软件的发展进一步扩充相应的测 试用例，从而最大限度地维持该方案的体系结构；同时，又能确保系统满足最 新的网格软件测试需求。本文提出的测试方案期望达到全面合理的测试目的。 第四节本文的内容安排 网格技术可以把分布在各地的计算机联网，设计出来的网格系统，将充足 的计算资源分配给每个用户，如同个人使用一台虚拟的超级计算机一样。如何 对网格系统进行科学的测试是本文研究的主要问题。 介绍了无资源管理自协调网格计算原型系统n o m a n g r i d 原型系统，并以大 数分解问题为目标，对此原型系统的性能进行测试和研究。 自治分布式体系结构是n o m a n g r i d 网格计算模型的核心，本文第二章对其 进行了叙述，并重点介绍了系统中每个节点的功能，系统的信息任务管理机制 和工作流程。 第三章引入了符合n o m a n g r i d 系统任务需求的大数分解算法，以及算法的 移植过程；第四章设计了评价机制，设计试验方案，在n o m a n 。g r i d 上运行大数 分解，并对测试结果进行了分析。 文章最后一章对全文进行了工作总结并介绍了未来的工作方向。 6 第二章n o m a n g r i d 的原理 第二章n o m a n - g rid 的原理 网格技术可以把分布在各地的计算机联网，设计出来的网格系统，将充足 的计算资源分配给每个用户，如同个人使用一台虚拟的超级计算机一样。根据 资源共享的思想设计出来的网格系统要符合网格的发展要求，并且有效避免或 解决瓶颈问题。 n o m a n - c n i d ”】是一个用于共享i n t e m e t 上空闲计算资源的分布式网格计算 系统。该系统采用完全分布式的体系结构的思想，不需要任何的中心节点来对 系统中全局或者局部的资源进行管理，系统中的计算节点各自管理自己的计算 资源。在该系统中，由于不存在任何的全局或局部管理节点，节点可以任意加 入和退出系统，同时用户可以在系统中的任何节点提交自己的计算任务。考虑 到j a v a 的平台无关性，n o m a n g r i d 原型系统采用j a v a 语言编写。 第一节n o m a n g r i d 的思想和系统组成 2 1 1n o m a n - g rid 的思想 在众多的网格研究领域中，有效利用i n t e r a c t 上大量资源的闲余计算能力， 解决大规模分布式计算问题是计算网格的一个重要研究方向。为能进行如此条 件下的大规模计算，此类计算网格必须能够聚合数量巨大的计算资源，并能在 动态的i n t e m c t 环境中充分利用这些计算资源。 为解决节点资源管理的问题，一类方案是集中式的体系结构。中心式的网 格体系结构是通过一个管理节点对网格系统中所有的节点进行管理和维护。当 有新节点加入时要到中心节点进行登记，当有任务运行时，中心节点进行任务 分发和结果统计，如果在计算过程中有信息交互，中心节点进行收集和发送， 节点失效时，中心节点会更新网格节点信息。由于中心节点体制机理比较容易 实现，大多的网格系统采用的是中心式的网格体系结构。但随着规模的上升， 这一体系方案的性能受到影响，网格的中心节点需要处理大量管理信息和节点 间的交互信息，给网格的进一步发展带来瓶颈。 另外一种方案利用p 2 p 1 6 1 思想来提高系统的可扩展性，典型的系统是 p a r a d r o p p e r 。它是一个全球计算系统，在p a r a d r o p p e r 中，用户通过局部的m a n a g e r 节点提交计算，该m a n a g e r 负责调度任务，并采用心跳监测的方法来监测运行该 7 第二章n o m a n g r i d 的原理 任务节点的状态。p a r a d r o p p e r 的任务调度算法将任务以较大概率调度到负载比 较轻的节点，以达到负载平衡，为有效调度，每个节点的负载发生变化后，需 要通知自己的邻居节点，节点的负载以任务队列的长度来衡量。 这两种方法前者由于中心管理的原因无法形成比较大的规模，后者则需要 比较大的节点之间通信量，仍处于研究阶段。 与这些研究的方案不同，n o m a n g r i d 并没有采用类似租约或心跳监测的方 法来监测资源和任务的运行，它不对资源和任务的运行进行管理，而是消耗较 少的空闲资源为代价使任务在动态环境中能够完成；在合适的任务粒度条件下， 其任务调度算法能保证每个节点的计算能力得到充分利用，同时慢速节点不会 成为系统的瓶颈。 为达到不额外投资进行硬件环境的改善，同时有效地利用i n t e m e t 上大量存 在的普通计算资源的目的，提出了一种低管理开销的网格计算模型n o m a n g r i d 和与该模型相适应的信息机制、任务调度算法和有限任务复制算法。该模型在 大规模动态资源环境中具有良好的可用性和可扩展性。通过仿真结果表明，该 模型完整地解决了对数量巨大的动态资源进行全局或局部管理所带来的问题。 在动态的环境中负载分布合理，系统中的计算资源能够得到充分利用。 2 1 2n o m a n - g ri d 的体系结构 在n o m a n g - r i d 系统部署的计算网络中，所有节点地位平等、功能完全相同， 系统中没有全局或局部的管理节点，每个节点通过与邻居节点的连接，从而实 现对整个网络的交互，n o m a n - g r i d 系统网络拓扑结构如图2 1 所示： 图2 1n o m a n g r i d 计算网格结构 8 第二章n o m a n g r i d 的原理 n o m a l l g r i d 由多个计算资源( 本文称单个计算资源为一个节点) 互连而成， 逻辑上相连的节点在n o m a n - g r i d 中互称为邻居节点。在该模型中不存在任何管 理节点，所有节点地位相等、功能相同，各自管理本地的资源；节点只要与系 统中已有的节点建立邻居关系就能共享自己的空闲计算能力，为别的节点提供 服务，同时需要计算能力的用户在系统中的每个节点上都能够提交计算问题。 每个节点的功能模型如图2 2 所示： 图2 2 节点功能模型 某些分布式计算问题，如参数扫描f 。刀、蒙特卡罗模拟1 1 8 】等被分解为多个相 互独立的任务之后，在用户控制的节点上提交( 也称为任务提交源节点) ；每个 节点中的任务管理器接收来自任务源节点或邻居节点调度过来的任务，将其组 织成一个任务队列，并收集任务运行结果，将其返回到相应的任务源节点：信 息管理维护一个邻居节点表，保存本节点所有邻居节点的一些简单信息；任务 调度器从任务管理器获取任务，根据邻居节点表的信息将其调度到某个邻居节 点处理或本地运行，并在调度过程中更新邻居节点表的信息；n o m a n g r i d 试图 利用的是节点的空闲计算能力，因此必须尊重资源拥有者对于资源使用条件的 描述，本地资源管理模块负责监视本节点的资源运行状况，并根据监测结果控 制调度到本节点运行的任务的创建、挂起、运行和中止，一旦资源的使用超过 资源提供者设置的条件，则将正在运行的任务挂起，反之则唤醒挂起的任务， 使之继续运行。 9 第二章n o m a n - o r i d 的原理 2 1 3n o m a n - g ri d 的信息机制 每个节点的信息管理模块维护一个邻居节点表，保存本节点以及其所有邻 居节点相对于本节点的相对能力信息和控制资源竞争的控制信息。 在n o m a n g r i d 系统中，用户在任何节点上都可能提交计算问题，当系统中 存在多个任务源节点时，由于缺乏全局知识，可能会出现多个任务源节点竞争 同一个资源的情况，n o m a n g r i d 希望通过节点之间的简单协商达成一致，自然 地形成一定的资源范围为各自的任务源节点服务。为达到这一目标，信息管理 模块设置了一个控制信息c ( u ，v ) ，来标记邻居节点v 在资源竞争中相对于节 点u 的状态。 定义1 本地能力：如果节点v 正在为n o m a n - g r i d 运行任务，则本地无能 力，否则本地有能力，记l ( v ，v ) 为节点v 的本地能力。 定义2 相对能力：记r ( u ，v ) 为节点u 的邻居节点v 相对于节点u 的相对 能力。 控制信息包括三种状态：b o u n d a r y 、d o m i n a t e 和n o r m a l ( 1 ) b o u n d a r y ：该节点属于另一个资源范围，本节点不能向其调度任务，称 该节点为本节点的边界节点 ( 2 ) d o m i n a t e ：本节点优先为来自于该节点的任务服务，称该节点为本节点 的控制节点 ( 3 ) n o r m a h 如果不是上面两种状态，就标记为n o r m a l 表2 1 邻居节点表示例 节点i d相对能力控制信息 u r ( u ，u )c ( u ，l d v r ( u ，v )c ( u ，v ) a r ( u ，a )c ( u ，a ) b r ( u ，b )c ( u ，b ) 假设节点u 的邻居节点为节点v 、a 、b ，则节点u 的邻居节点表如表2 1 所示。节点u 被虚拟成自身的一个邻居节点，总是放置在邻居节点表的第一项， 根据相对能力的定义，该虚拟邻居节点相对于节点u 的相对能力r 哪，u ) 就是 节点u 的本地能力l ( u ，l d 。系统初始和新节点加入系统时，每个节点的相对 1 0 第二章n o m a n g r i d 的原理 能力均设置为有能力，控制信息设置为n o r m a l 。 信息管理【1 9 】是任务调度的基础，任务调度器根据本地的邻居节点信息表将 任务调度到相对能力为有能力的邻居节点上运行或处理。为准确地调度任务， 本地邻居节点表必须尽量反映邻居节点的真实信息，但在n o m a n - g r i d 中，并不 实时探测邻居节点状态或主动向邻居节点报告本节点的状态，而是只有在任务 调度、任务完成、节点加入三个事件发生时，如果本节点相对于控制节点的相 对能力由无能力变成了有能力，则通知控制节点更新本节点的状态信息；在这 种情况下，由于环境的动态性，邻居节点表中的信息可能并不完全准确，但 n o m a n g r i d 的任务调度机制可以保证任务仍能准确的调度。采用这种信息变更 策略能大大减少维护邻居节点表所带来的开销。 2 1 4n o m a n - g ri d 的任务分发机制 在信息管理的基础上，研究设计了一个与之相适应的任务调度算法，在没 有全局知识的情况下，根据邻居节点表的信息将任务分布到网络中的各个空闲 节点运行。为充分利用系统中空闲的资源，尽量减少任务调度所带来的开销， 任务调度算法遵循三个基本原则： 原则1 ：一个节点同时只能运行一个任务； 原则2 ：节点空闲时自身优先运行任务； 原则3 ：出现资源竞争时，遵循给定的资源竞争策略调度任务； 当节点接收到用户提交的任务或邻居节点调度过来的任务时，将其放置在 任务队列中，等待调度。节点如果发现任务队列中存在待调度的任务，并且邻 居节点信息表中存在着有能力的邻居节点时，启动任务调度，并在调度过程中 更新邻居节点表的信息，以迸行下一个任务的调度。以节点u 为例，任务调度 如算法1 所示。 算法1 任务调度算法 1 节点u 根据邻居节点表判断r ( u ，u ) 是否等于1 ，如是，则将任务调度 到自身运行，设置r ( u ，u ) = 0 。转到5 ，否则转到2 。 2 从邻居节点表中顺序选择一个相对能力为1 的邻居节点，将任务发送到 该节点( 以v 表示) ，设置r ( u ，v ) = 0 。 3 节点v 收到任务后，执行资源竞争算法； 3 1如节点v 可以为u 提供服务，则将该任务放置在任务队列中，为防止 第二章n o m a n g r i d 的原理 任务逆向调度回节点u ，设置r ( v ，u ) = 0 ，并判断本节点任务队列中的任务数 是否小于能力信息标记为1 的邻居节点数，如是，则向节点u 返回本节点仍有 能力信息，否则不返回任何信息，转到5 ； 3 2 如节点v 拒绝为u 服务，则转到2 ； 4 节点u 收到节点v 有能力信息后，设置r ( u ，v ) = l ，如果使得节点u 相对于其控制节点的相对能力由0 变成1 ，则向节点u 的控制节点传播有能力的 信息。 5 节点u 取出下一个待调度任务，转到1 。 算法2 资源竞争算法 1 节点v 根据邻居节点表查找自身的控制节点； 2 如控制节点不存在，则接收该任务，并设置c f v ，u ) = d o m i n a t e ，结束； 3 如控制节点存在( 以k 表示，此时c ( v ，k ) = d o m i n a t e ) ，判断k 是否等 于u ； 3 1 如是，则结束； 3 2 如不是，则通知节点u 本节点拒绝为之服务，设置c ( v ，u ) = b o u n d a r y ， 同时设置r ( v ，= o ，避免向节点u 调度任务； 4 节点u 收到节点v 拒绝服务的消息后，同样设置c ( u ，v ) = b o u n d a r y ， 避免引起新的冲突。 邻居节点表被表示成一个循环链表，并维护一个指向节点的指针，初始值 为邻居节点表的第二项( 第一个真正的邻居节点) 。从邻居节点表中查找有能力 的邻居节点时，总是先判断本节点( 邻居节点表的第一项) 是否有能力，然后 再从当前指针指向的节点开始查找，指针不断下移，直到找到一个有能力的邻 居节点或者指针到达查找之前的位置为止。采用这种策略会将任务调度到离任 务源节点最近的空闲节点运行。 按照任务调度算法，用户提交的任务逐步以任务源节点为中心往外扩展， 当系统中存在着多个任务源节点时，多个节点可能都向某个节点调度任务，形 成资源竞争，n o m a n g r i d 的资源竞争算法采用先到优先服务的策略来解决这个 问题；如果来自于某个方向邻居节点的任务先达到本节点，则本节点及其邻居 节点优先为该方向的邻居节点服务，同时拒绝为其它方向的邻居节点服务。 任务调度算法实际上是以各个任务源节点为根的广度优先搜索过程，在系 统拓扑上形成以各个任务源节点为中心的资源范围，在一段时间内，特定范围 1 2 第二章n o m a n g r i d 的原理 内的资源只为该任务源节点服务。但这个资源范围并不是固定不变的，而是随 着系统的运行情况动态变化，当某个边界节点相对于其控制节点为有能力的时 间持续超过设定的时间而没有收到来自于控制节点的任务时，该节点会打破现 在的边界，以便其它范围内的节点可以重新竞争本节点，使得系统中所有资源 能在动态竞争中得到充分利用。 任务控制和资源的竞争机制是n o m a n g r i d 思想中突破中心制限制的关键所 在，通过信息机制和任务分发来做到负载均衡和无管理节点。 第二节n o m a n g r i d 原型系统的结构和机制 根据第一节的思想原则，使用j a v a 语言实现了无资源管理自协调网格计算 模型，采用基于节点自治的完全分布式网络计算模型的体系结构，与之相适应 的信息管理机制、资源调度算法与动态性解决方案，使该模型在大规模、动态 的i n t e m e t 环境中，具有良好的可扩展性、可靠性和可用性。在此系统中，不存 在任何资源管理节点，系统中的所有节点功能相同、地位对等，每个节点都可 以随时向系统中分布的计算资源提交运行任务请求，由多个节点共同完成大规 模计算任务，同时能够协调、监控各个子计算任务的运行情况。 本章阐述n o m a n - c n j d 的体系结构和工作流程，重点介绍n o m a n - g r i d 原型 系统节点的实现方法和节点间的通信机制。每个节点由四个子系统组成，子系 统是并发的线程，分别由四个类使用接口r u n n a b l e 方式产生，线程间的通信使 用非阻塞管道。下面分别介绍节点的实现方法和节点间的通信机制。 2 2 1n o m a n - g ri d 的系统结构 n o m a n g r i d 系统上的每一个节点要完成与用户交互、信息管理、任务的调 度和运行、网络通信等功能，因此，n o m a n - g r i d 体系结构可以划分为以下4 个 功能结构模块，如图2 3 ： 第二章n o m a n g r i d 的原理 图2 3n o m a n - g r i d 体系结构 核心系统 核心系统是原型系统最重要的组成部分，负责统一的调度，对其他三个子 线程占有支配地位，可以随时终止其他线程。核心系统在j a v a 类c o r e s y s t e m 中实现，c o r e s y s t e m 的定义为： p u b l i cc l a s sc o r e s y s t e mi m p l e m e n t sr u n n a b l e ( ： 核心系统实现的主要功能包括： 网络发送网络接收：对网络中其他节点发送来的信息( 包括任务、节点能 力变更信息等) 并进行处理；把本地节点信息发送到网络上特定节点。 信息管理：在节点运行过程中维护邻居节点表，同时维护本地节点资源的 回收恢复，为任务调用提供调度依据。 任务调度接收：按照n o m a n g r i d 模型的任务调度规则把任务队列中的任 务调度到相应的节点上运行；同时接收其他节点调度过来的任务放置到相应的 任务队列中。 任务运行结束处理：本地节点上有任务运行完成时，把运行结果返回到相 应的任务源节点。 任务结果返回处理：如果节点是任务源节点，当发送出去的任务有运行结 果返回时，把返回的结果放置到结果队列里面，同时需要将已经结束的任务从 本地任务队列中删除。 网络监听系统和界面系统通知核心系统邻居节点变化时，核心系统根据信 1 4 第二章n o m a n g r i d 的原理 息管理规则修改邻居节点表。 当本地提交所有任务完成之后，核心系统通知界面系统应用完成。 开启任务运行系统、网络监听系统、界面系统。 结束所有系统，退出n o m a n - g r i d 系统。 为了实现上述各项功能，核心系统处理算