（计算机系统结构专业论文）基于agent网格计算性能监测与调节的研究.pdf

中国科学技术大学博士学位论文 摘要 摘要 近年来，网格计算受到人们的普遍关注，是当今高性能并行计算研究的前沿 课题。所谓网格( g r i d ) 就是在缺少中央控制、没有全知者( o m n i s c i e n c e ) 以及强 的信任关系的情况下能够协同使用地理分布的各种资源。因此网格计算环境相对 于一般网络计算环境来说，有着更为复杂的特征，如存在多管理域、站点自治、 系统的动态性、异构性和通信延迟的不确定性更高等。用户无法预知应用程序运 行时刻的情况，这就导致应用程序极度复杂、低性能和不健壮。 为了实时监控、调节和改进并行和分布式应用的性能，研究开发预测监控分 析和调节并行和分布式应用工具环境。人们进行了许多的研究和努力。为了调节 应用的运行性能，人们使用了不同的方式，这些方式从算法调节到手工交互式调 节。算法调节是由算法来实现的，它通常对某一类特定的算法和静态环境有效， 并且导致应用软件的复杂度增加和难以维护。人工调节是一种交互式的调节代替 算法调节的方式，它依赖于可视化技术，提供给用户一个完整的应用性能图，但 是，这种方法难以用在大型分布式系统和网格这种具有大量处理器的场合。对一 些大型科学计算来说，应用程序的运行可能为几天或更长时间，因此，用户难以 实现实时监测程序的运行变化和对其性能进行实时调节，而且其效果受用户的经 验和专业水平的限制。 本文对已有的技术进行新的扩充，利用智能a g e n t 技术来监测和调节应用性 能，给出了使用智能a g e n t 对网格计算进行实时监控的新方法。智能a g e n t 非常 适合这种动态环境，它们能够收集和分析数据集，并且可以自动做出修改性能参 数的决策。另一重要特点是在智能a g e n t 中，它们能够互相协作的工作，这种分 布式a g e n t 结构，可以支持具有大量处理器的网格环境，并且具有很好的扩展性。 同样，这种分布式结构对支持异构和协作同样是有益的。该模型是多a g e n t 系统， 它由多个智能a g e n t 组成，采用多层次分布式结构，每个a g e n t 负责收集所在结 点的动态变化情况，负责收集分析性能参数。利用a g e n t 的智能性，加以分析综 合并实时调整，然后对参数进行适当调整使应用程序更加适应网格的动态环境， 获得更高的性能。 网格环境中结点负载的预测和对应用程序运行时间的预测是任务调度和资 源分配的基础。为了实时调整、改进并行和分布式应用的性能、获得高性能资源 分配以及任务调度算法，就需对结点的负载进行有效的预测。本文使用排队论对 结点的负载进行预测。使用多元回归分析来对应用程序的运行时间进行预测，即： 找出应用程序运行时间与结点性能参数之间的关系，从而给定任一个结点就可知 应用程序在该结点上的运行时间，为高性能的任务的调度提供基础。 中国科学技术大学博士学位论文 摘要 本文的主要创新点有： 1 把a g e n t 技术引入到网格计算中，用其来收集结点性能信息。对信息进行 提取分类构造知识库，并利用智能a g e n t 的智能推理的特性来实时监控网格计算 中应用程序中的性能问题。 2 结点负载信息是高性能作业调度和资源分配算法的基础。本文利用a g e n t 收集应用程序及结点各种性能参数。然后利用a g e n t 的智能性，利用排队论对 结点的负载进行预测。 3 给出了基于多元回归分析的应用程序运行时间的预测方法，即找出应用程 序运行时间与结点性能参数之间的关系，从而给定任一个结点就可知应用程序在 该结点上的运行时间，为高性能的任务的调度提供基础。 4 本文在网格环境下将并行遗传算法用于门阵列模式布局，并在布局目标函 数中引入了通道拥挤度的概念，使布局的构形更趋合理。 5 研究实现了网格环境下，基于主从式并行遗传算法求解多项式方程根的算 法。 关键词网格计算，性能预测，性能分析，性能调节，智能a g e n t ，门阵列布局， 方程根 中国科学技术大学博士学位论文 摘要 a b s t r a c t n o w a d a y s t h er e s e a r c ha n d e x p l o i t a t i o no f t h eg d d c o m p u t i n ga r eg e e i n gm o r ea n d m o r ea a e n t i o n i te n a b l e st h ec o o r d i n a t e du s eo fg e o g r a p h i c a l l yd i s t r i b u t e dr e s o u r c e s i nt h ea b s e n c eo f c e n w a lc o n t r o l ，o m n i s c i e n c ea n d s t r o n gt r u s tr e l a t i o n s h i p s h o w e v e r ， t h em a n a g e m e n to fr e s o u r c e si nt h eg r i de n v i r o n m e n ti sm o r ec o m p l e xt h a ni n g e n e r a lo n e s ，a s r e s o u r c e sa r e a u t o n o m o u s ，o w n e db yd i f f e r e n ti n d i v i d u a l s o r o r g a n i z a t i o n s ，a n dm o r e ( g e o g r a p h i c a l l y ) d i s t r i b u t e d ，h e t e r o g e n e o u s i nn a t u r e a p p l i c a f i o n sr u n n i n g o nt h e s e p l a t f o r m sm a ye x h i b i t d i v e r s ea n d u n p r e d i c t a b l e p e r f o r m a n c eb e c a u s eo fp l a t f o r mh e t e r o g e n e i t ya n dv a r y i n gr e s o u r e 圯a v a i l a b i l i t y , r e s u l t i n gf r o mc o m p e t i t i o nw i t ho i l i e ra p p l i c a t i o n so rf r o mm i g r a t i o no fa p p l i c a t i o n s t h e m s e l v e st oad i f f e r e n te x e c u t i o ne n v i r o n m e n t n u m e r o u ss c a t t e r e de f f o r t sh a v ec o n c e n t r a t e do nd e v e l o p i n gs p e c i f i ct o o l st oh e l p u s e r s i n s t r u m e n t ， a n a l y z e ，p r e d i c t ， a n dt u n et h e p e r f o r m a n c e o f p a r a l l e l a n d d i s t r i b u t e da p p f i c a t i o n su s i n gb r o a d r a n g eo fa p p r o a c h e s m o s to ft h e s ea p p r o a c h e s t e n dt ob ea p p l i e da tr u n - t i m e u s u a l l y , t h ep e r f o r m a n c ed a t an e c e s s a r yf o rr u n - t i m e s u p p o r t a r e g a t h e r e db y t h ei n s l r u m e n t a t i o no fp a r a l l e l a p p l i c a t i o n a l g o r i t h m i c s t e e r i n gi s ac u s t o m i z e ds o l u t i o n u s u a l l y , i ti se f f e c t i v eb e c a u s eo fi t s a p p l i c a t i o n s p e c i f i c c u s t o m i z a t i o n ，b u tu s u a l l y , t h i sa p p r o a c h l e a d st o c o m p l e x s o f t w a r e a p p l i c a t i o n s w h i c ha r ch a r dt om a i n t a i n m a n u a ls t e e r i n gi sa ni n t e r a c t i v ea p p r o a c h t h a tr e p l a c e st h ea l g o r i t h mi nt h es t e e r i n gl o o pw i t ht h eh u m a nu s e r t h i sa p p r o a c hi s b a s e do nv i s u a l i z a t i o nt e c h n i q u e st op r o v i d et h eu s e rw i t hac o m p l e t ep i c t u r eo ft h e a p p l i c a t i o n sp e r f o r m a n c e u n f o r t u n a t e l y , c u r r e n t v i s u a l i z a t i o nm e t h o d o l o g i e sc a n n o t b es c a l e df o rs y s t e mu t i l i z i n gl a r g en u m b e ro fp r o c e s s o r a l s o ，i ti sn o tu n u s u a lf o r l a r g ea p p l i c a t i o n st ob e c a r d e do u to v e rs e v e r a ld a y s ，a n dt h u s ，i ti sn o tf e a s i b l ef o ra h u m a nu s e r t o c o n s t a n t l y m o n i t o r c h a n g e st a k i n gp l a c e i nt h e a p p l i c a t i o n s p e r f o r m a n c e t h i sd i s s e r t a t i o n p r e s e n t s an e ws y s t e m p a r a d i g m t om o n i t o ra n dt u n et h e p e r f o r m a n c e o fp a r a l l e l a p p l i c a t i o n ，b a s e d o nu s i n gi n t e l l i g e n t a g e n t s t oc o l l e c t a n a l y s i s a n dd e c i d eu p o np e r f o r m a n c ep a r a m e t e r sv a l u e s t h e yc a nc o u e c ta n d a n a l y z e d a t as e t sa n dm o r ei m p o r t a n t l yc a l lm o d i f yp e r f o r m a n c ep a r a m e t e r s a u t o n o m o u s l y a n o t h e ri m p o r t a n tf e a t u r ei ni n t e l l i g e n ta g e n t s i st h e i ra b i l i t yt ow o r k c o u a b o r a t i v e l yi ng i r de n v k o n m e n t s h i g h p e r f o r m a n c es c h e d u l i n gi s b a s e do np r e d i c t i o no ft h en o d el o a d i nt h i s 中国科学技术大学博士学位论文 摘要 d i s s e r t a t i o n ，w ec r e a t eas u i t a b l ei n t e l l i g e n ta g e n tt oc o l l e c tp e r f o r m a n c ep a r a m e t e r s o rt h e a p p l i c a t i o n s a n d p e r f o r m a n c ep a r a m e t e r s o ft h e n o d e u s i n gg e n e t i c a l g o d t h r aa n d t h et h e o r yo f q u e u e sp r e d i c tt h el o a do f n o d ei ng r i d u s i n gr e g r e s s i o na n a l y s i sp r e d i c tt h er u n n i n g t i m eo ft h ea p p l i c a t i o n s f i n d i n gt h e t i m eo ft h ea p p l i c a t i o n sa n d p e r f o r m a n c ep a r a m e t e r so f t h en o d e r e l a t i o n s h i p g i v i n g a n yn o d e ，w ec a nk n o wt h er u n n i n gt i m eo ft h ea p p l i c a t i o n t h er u n n i n gt i m eo ft h e a p p l i c a t i o n i st h ef o u n d a t i o no f l l i g h p e r f o r m a n c es c h e d u l i n g m a n yo ft o d a y s s o f t w a r e a p p l i c a t i o n s h a v ei n t e n s i v ed e m a n d sf o r c o m p u t i n g r e s o u r c e sa n d r e q u i r es u p e r c o m p u t i n gp o w e r t h e r ea r ef i v en e wi d e a sb r o u g h tf o r t hi nt h i sd i s s e r t a t i o n ： ( 1 ) t h i s d i s s e r t a t i o n p r e s e n t s an e w a p p r o a c hu s i n gi n t e l l i g e n t a g e n t s f o r p e r f o r m a n c em o n i t o r i n g a n d t u n i n g ( 2 ) h i 曲一p e r f o r m a n c es c h e d u l i n gi s b a s e do np r e d i c t i o nt h en o d el o a d i nt h i s d i s s e r t a t i o n ，w ec r e a t e as u i t a b l e i n t e l l i g e n ta g e n tt o c o l l e c tp e r f o r m a n c e p a r a m e t e r so ft h ea p p l i c a t i o n sa n dt h en o d e u s i n gg e n e t i ca l g o r i t h ma n d t h e t h e o r y o f q u e u e sp r e d i c t t h el o a do fn o d ei ng r i d ( 3 ) u s i n gr e g r e s s i o na n a l y s i sp r e d i c tt h er u n n i n g t i m eo ft h ea p p l i c a t i o n s f i n d i n g t h et i m eo ft h e a p p l i c a t i o n s a n d p e r f o r m a n c ep a r a m e t e r s o ft h en o d e r e l a t i o n s h i p g i v i n ga n yn o d e ，w e c a nk n o wt h er u n n i n gt i m eo ft h ea p p l i c a t i o n t h e r u n n i n g t i m eo ft h ea p p l i c a t i o ni sh i g h - p e r f o r m a n c es c h e d u l i n gf o u n d a d o n ( 4 ) t h eg a t ea r r a yp l a c e m e n tp r o b l e mi sn p - c o m p l e m e n t t h i sp a p e r u s e sp a r a l l e l g e n e t i ca l g o r i t h m t os o l v ei t ac o r r e s p o n d i n gm a t h sm o d e li sp r e s e n t e da n da p r o p e ro b j e c t i v ef u n c t i o ni sc o n s t r u c t e d t h ea l g o r i t h mh a sb e e nr u no nt e s t i n s t a n c e s i t ss o l u t i o n sa r eo b s e r v e dt ob eq u i t eg o o d ( 5 ) ap a r a l l e lg e n e t i ca l g o r i t h m f o r f i n d i n g a l lr o o t so f c o m p l e x f u n c t i o n a le q u a t i o n i sp r e s e n t r e s e a r c h e sa r em a d eo ns o m et e c h n i c a lp r o b l e m sf o rr e a l i z i n g w e d e s c r i b et h ed e s i g na n di m p l e m e n to fg e n e t i ca l g o r i t h mf o rf i n d i n gr o o t so f c o m p l e x f u n c t i o n a le q u a t i o n k e y w o r d s ：g r i dc o m p u t a t i o n ，p e r f o r m a n c et u n i n g ，c o m p u t a t i o n a lp e r f o r m a n c e ， i n t e l l i g e n ta g e n t ，p e r f o r m a n c ea n a l y s i s ，g a t ea r r a yp l a c e m e n t ，f u n c t i o n a le q u a t i o n r o o t 中国科学技术大学博士学位论文 第一章绪论 第一章绪论 本章作为诸论，第一节首先介绍了研究的背景。第二节介绍了网格计算与监 控的意义。第三节介绍了研究的动机与思路。第四节给出了本文的主要研究内容。 第五节给出了全文的组织结构。 1 1 研究的背景 尽管高性能并行单机系统的运行算速度正以万亿次每秒量级向前发展，然 而，科学与工程计算对计算能力的需求是永无止境的! 当前高性能并行单机系统 还远不能满足人们对计算能力的要求。因此，由巨型机、工作站和高性能微机通 过高速互连网络连接组成并行分布式计算环境即网格计算应运而生。然而，由 于网格环境中资源的动态性、非独占性、异构性、分布性和网络通信延迟的不确 定性等因素导致了应用程序的复杂和低效，难以达到预期的性能。 网格计算惭dc o m p u t i n g ) 的概念来源于电网( f j e c 廿i c a p o w e rc m d ) ，人们试 图实现：类似于家用电器能够极为方便的从电网中使用电力资源，计算应用也能 够便利地从一个大范围的分布的资源池中获取所需的各种计算资源f l 】。国际上 自九十年代初以来兴起了高性能网格计算热潮。美国、欧洲和日本等国家，网格 计算环境的研究开始出现。近年来有飞速发展的趋势，大批网格项目开始实施， 并建立了多个计算实验床。如彼兹堡超级计算中心的d h s c 工程，普渡大学 s i m d m i m d 系统，卡拉基璃龙大学基于n e c t a r 的异构系统，a r 驴n n eg l o b u s 等。 目前粗颗粒的远距离跨结点应用已经初步实现，但网格应用仍很复杂，性能还不 完善，没有得到广泛的运用。其发展趋势是更有效地利用网格资源，实现更高效 的网格计算环境。在网格计算中用户面临的网络环境的不确定性，用户无法预知 运行时刻的情况，这就导致应用极度复杂、低性能和不健壮。虽然目前国际已研 制开发一些工具，用来预测分析甚至调节并行和分布式计算的性能，如： c e a ( c a u s e - c f f e c ta n a l y s i s ) ，a i m s ( i n s t r u m e n t a t i o na n dm o n i t o r i n gs y s t e m ) ， p a r a d y n fw i s c o n s i n ) ，p a b l o ( m l n o i s ) ，f a l c o n ( i b m ) 等，但这些工具或环境主要 用在单机或集群的分布式并行计算，而不适合于网格计算的动态环境【2 】。 国内的网格计算环境国家网格计划也已立项，并进入实施阶段。该项目 计划将国内目前已有的各高性能中心连接起来形成一个虚拟的高性熊环境，首先 中国科学技术大学博士学位论文 第一章绪论 采用传统的方法和手段实现对各结点的远程使用。第二步是实现粗颗粒的跨结点 的网格计算应用。第三步是实现较为复杂的网格应用，支持大规模用户群。并逐 步向信息网格、知识网格等方向发展，开发新的应用模式，如远程教育、网上交 易等。 i n t e r n e t 的出现使得人们能够大范围地共享各种信息，也使得人们比以往任何 时候都更加渴望能够更广泛地共享各种资源。使用i n t e r n e t 作为低层，研究人员 可以将很大范围上地理分布的异构计算机系统集合在一起形成一个大规模的计 算平台。该领域的研究产生了一个新的软件体系结构，称之为网格( g r i d ) l 1 】。近 年来世界各地开展了许多相关的研究项目【3 - 2 8 ，初步的研究结果表明网格计算 确实是一个可行的高性能广域分布式计算模型，同时这些初步的结果也展示了许 多急需解决的挑战性问题。如何有效地性能监控、管理资源和任务调度是影响网 格计算是否成功的最重要因素之一。 1 2 网格计算与性能监控的意义 网格计算是近年来得到快速发展的广域网络计算技术。研究人员试图将很大 范围上地理分布的异构计算机系统集合在一起形成一个大规模的计算平台，称之 为网格( g r i d ) 。它是由最初的元计算发展而来 2 9 3 2 ，可以这样认为：网格就是 在缺少中央控制、没有全知者( o m n i s c i e n c e ) 以及强的信任关系的情况下能够协同 使用地理分布的各种资源。其最大的优点之一就是有利于全国范围内( 或世界范 围内) 各种计算资源和数据资源的共享 1 】。 采用多个计算设备共同解决问题以弥补单机计算性能不足的思想由来已久， 从早期的多处理器计算机到已得到广泛使用的各种集群 3 3 1 。在一个分布式系统 里，计算机可以通过远端过程调用f p , p c ) 、o o p 、远端方法调用( r m i ) 等方法使用 远程资源 3 4 3 7 。现代商业分布式平台，如：c o r b a 、d c o m 、j i n i 等已得到 了大量的使用 3 9 3 9 。在更广的范围里，w e b 服务使用x m l 、s o a p 等协议实 现资源共享，以w e b 作为低层的类似的分布式处理系统也已出现。如：对象 w e b ( w e b o fo b j e c t s ) 、处处分布式对象( d i s t r i b u t e do b j e c t se v e r y w h e r e ) 等 4 0 - - 4 1 。 随着通信技术的发展和计算技术的提高，正逐渐可以将越来越大范围的，更多的 计算设备组织在一起，共同解决问题。利用n t e m e t 破译r s a 密码和搜索外星人 两个项目都成功地使用了成千上万台计算机共同工作【6 ，7 】，大范围的广域分布 式计算初步显示了它诱人的发展前景。现实世界的许多科学问题无法用单个计算 机有效地计算，如计划2 0 0 5 进行的欧洲高能粒子实验预期产生的计算任务和数 据都是十分惊人的( 数据网格项目是它的重要前期工作之一) 【5 】。对更高的计算能 力的渴望从来都没有因为单机计算能力的增长而缓解，人们希望能够实现更有效 中国科学技术大学博士学位论文 第一章绪论 的广域计算。另外，在网格计算的研究过程中，研究人员发现借助于网格核心服 务，计算网格系统除了能提供廉价、高效的高性能计算以外，通过设计相应的服 务软件，它还能提供许多额外的服务。因此发展出数据网格、服务网格等多种衍 生类型 3 】。 通过使用网格技术，人们希望能够实现廉价、普遍的高性能计算。能够合作 存取各种数据信息，能够提供广域多媒体应用等等。由于网格计算是个新的研究 领域，网格计算环境相对于一般网络计算环境，有着更为复杂的特征，如存在多 管理域、站点自治、系统的动态性、异构性和通信延迟的不确定性更高，硬件和 软件两个层次上都存在异构性等等。实现有效的网格计算还有很多需要解决的问 题，具体包括资源调度和管理、系统安全、编程模式、性能监控和数据存取等【3 】。 在网格计算中，用户面临的网络环境的不确定性，因此无法预知运行时刻的情况， 这就导致了应用极度复杂低性能和不健壮。其中，在网格环境里如何有效地监控 结点的动态变化和应用程序运行情况是影响网格计算是否成功的最重要因素之 1 3 研究的动机及思路 在网格计算中用户面临的网络环境的不确定性，用户无法预知运行时刻的 情况，这就导致了应用极度复杂、低性能和不健壮。考虑和研究网格整个系统 的性能目前是比较困难的或者说是难以实现的。本文所研究的性能问题是针对 应用，即局部性能，而不是全局性能。为了实时调整和改进并行和分布式应用 的性能，本文研究采用a g e n t 技术设计一种a g e n t 结构，并利用a g e n t 收集应 用程序及结点的各种性能参数。然后利用a g e n t 的智能性，加以分析综合并实 时调整，使应用程序更加适应网格的动态环境，获得更高的性能。该模型是多 a g e n t 系统，它由多个智能a g e n t 组成，采用多层次分布式结构。每个a g e n t 负责收集所在结点的动态变化情况，负责收集分析性能参数。网格环境中结点 负载的预测和对应用程序运行时间的预测是任务调度和资源分配的基础。本文 使用排队论对结点的负载进行预测，使用多元回归分析来对应用程序的运行时 间进行预测。 1 4 本文的研究内容 研究开发预测监控分析和调节并行和分布式应用工具环境，人们进行了许多 中国科学技术大学博士学位论文 第一章绪论 的研究和努力。为了调节应用的运行性能，人们使用了不同的方式，这些方式从 算法调节到手工交互式调节。算法调节是由算法来实现的，它通常对某一类特定 的算法和静态环境有效，并且导致应用软件的复杂度增加和难以维护。人工调节 是一种交互式的调节代替算法调节的方式。它依赖于可视化技术，提供给用户一 个完整的应用性能图。但是，这种方法难以用在大型分布式系统和网格这种具有 大量处理器的场合。对一些大型科学计算来说，应用程序的运行可能为几天或更 长，因此，用户难以实现实时监测程序的运行变化和对其性能进行实时调节，而 且其效果受用户的经验和专业水平的限制【2 】。本文对已有的技术进行新的扩充， 利用智能a g e n t 技术来监测和调节应用性能，给出了使用智能a g e n t 对并行和分 布计算进行实时监控的新方法。 本文研究建立一个合适的智能控制结构，帮助用户监测、分析和调节他们需 长时问运行的并行应用程序。智能a g e n t 非常适合这种动态环境，它们能够收集 和分析数据集。更重要的是，它们可以自动做出修改性能参数的决策。另一重要 特点是在智能a g e n t 中，它们能够互相协作的工作。这种分布式a g e n t 结构，可 以支持具有大量处理器的网络环境，并且具有很好的扩展性。同样，这种分布式 结构对支持异构和协作同样是有益的。虽然，a g e n t 被认为与应用竞争资源，但 它们通过标准库来交换信息和通信，以减少通信量。除了分布式结构外，使用 h e n r i s t i c 技术性能a g e n t 对性能参数进行修改可以减少对原应用的干扰。性能分 析工具的基本目标是帮助程序员了解程序的性能参数，特别是分析和定位应用程 序中性能较差，造成性能瓶颈的部分。这样的工具可以用来了解普通的并行应用 程序的运行效果，对于分析应用程序的性能有很大的帮助。 结点负载信息是高性能作业调度和资源分配算法的基础。为了实时调整、改 进并行和分布式应用的性能、获得高性能资源分配和作业调度算法，就需对结点 的负载进行有效的预测。本文利用a g e n t 收集应用程序及结点各种性能参数。然 后利用a g e n t 的智能性，加以分析综合并预测结点在未来时间段结点的负载，给 分配资源和任务的调度提供依据，使应用程序更加适应网格的动态环境，获得更 高的性能。 并行计算的目的就是缩短应用程序的运行时间。而一个并行应用程序的运行 时间是由最慢的那一并行成分所决定的。网格环境下资源动态变化以及它们用户 的程序的错综复杂的关系，使得程序员无法预测应用程序在运行过程中的动态行 为，无法有效地排除或缓解多个结点同时分工执行同一任务时可能引起争用、访 问冲突等现象，从而影响程序的可靠性和高效性。因此，必须采取有效的方法对 应用程序的运行时间进行预测。即找出程序运行时问与结点性能参数之间的关 系，为高性能的分配资源和任务调度提供基础。本文给出了基于多元回归分析的 应用程序运行时间的预测方法，即找出应用程序运行时间与结点性能参数之间的 中国科学技术大学博士学位论文第一章绪论 关系，从而给定任一个结点就可知应用程序在该结点上的运行时间。任务迁移是 解决网格计算的性能“瓶颈”的主要方法之一，而要实现任务迁移其中重要一点 就是解决任务问的通信问题。本文提出一种基于a g e n t 位置透明的任务迁移通信 问题的解决方案。 门阵列模式布局是一类n p 完全问题。本文在网格环境下将并行遗传算法用 于门阵列模式布局，并在布局目标函数中引入了通道拥挤度的概念，使布局的构 形更趋合理。 本文提出一种在网格环境下基于根的分布理论和p g a 的求多项式方程根的 并行算法。在算法中首先利用多项式方程根的分布理论，确定根的个数和范围； 在确定的范围内利用并行模拟退火遗传算法进行求根。算法简单实用，且便于并 行实现。本文通过使用该算法求多项式方程的根，所求的结果数据相当令人满意。 1 5 本文的组织结构 本文共分八章，组织结构如下： 第一章为绪论，首先介绍研究的背景、研究目标、研究现状、为什么要研究 网格计算和网格计算的主要研究领域，然后对网格环境下的应用性能调节方案和 主要的技术及领域应用的最新进展等进行了综述，最后介绍本文的主要工作及组 织结构。 第二章详细介绍了网格的分类、特征、结构、主要的研究方向和网格与一般 分布式计算系统相比所具有的特点。对应用性能监测、调节方法和必要性进行了 阐述，回顾了目前世界上主要的网格项目和目前世界上主要的并行和分布式计算 的性能分析和调节工具。 第三章对有关a g e n t 理论和实践两方面的研究现状、关键技术、发展趋势和 主要的应用领域进行了叙述和讨论。研究采用a g e n t 技术设计一种a g e n t 结构， 利用a g e n t 收集应用程序及结点各种性能参数，给出了a g e n t 的基本概念及定义。 介绍多a g e n t 系统的概念。给出了基于a g e n t 监测系统的总体结构设计及实现技 术和a g e n t 的形式化描述和具体实现。 第四章叙述了结点负载预测的必要性，并利用a g e n t 的智能性，加以分析综 合并预测结点在未来时间段结点的负载，给出了基于排队论的预测方法。给资源 分配和任务的调度提供依据，使应用程序更加适应网格的动态环境，获得更高的 性能。 第五章介绍了网格环境下应用性能分析研究的特点、难点和必要性。在网格 环境下开发软件，如何提高应用程序的性能已成为人们研究的热点和难点。本章 给出了基于多元回归分析的应用程序运行时间的预测方法，并提出一种基于 中国科学技术大学博士学位论文第一章绪论 a g e n t 的位置透明的任务迁移通信问题的解决方案。 第六章介绍有关遗传算法( g a ) 的基本思想及基本要素。将并行遗传算法用 于门阵列模式布局，并在布局目标函数中引入了通道拥挤度的概念，使布局的构 形更趋合理。 第七章介绍多项式方程求根问题的理论意义、应用价值和目前已有算法的 局限性。提出在网格环境下一种基于根的分布理论和p g a 的求多项式方程根 的高效算法。在算法中首先利用多项式方程根的分布理论，确定根的个数和范 围。在确定的范围内利用并行遗传算法进行求根。本章通过使用该算法求多项 式方程的根，所求的结果数据令人满意。 第八章给出了本文总结和进一步研究的内容。 中国科学技术大学博士学位论文 第二章网格计算与性能监控 第二章网格计算与性能监控 国际上自九十年代后期兴起了高性能网格计算热潮。美国、欧洲和日本等国 家，网格计算环境的研究开始出现，近年来有飞速发展的趋势，大批网格项目开 始实施，并建立了多个计算实验床。如彼兹堡超级计算中心的d h s c t 程，普渡大 学s i m d m i m d 系统，卡拉基一梅龙大学基于n e c t a r 的异构系统，a r g o n n eg l o b u s 等。目前粗颗粒的远距离跨结点应用已经初步实现，但网格应用仍很复杂，性能 还不完善，没有得到广泛的运用。其发展趋势是更有效地利用网格资源，实现更 高效的网格计算环境。虽然目前国际上已研制开发一些工具，用来预测监视分析 甚至调节并行和分布式计算的性能。如：c e a ( c a u s e e f f e c ta n a l y s i s ) ， a i m s ( i n s t r u m e n t a t i o na n dm o n i t o r i n gs y s t e m ) ，p a r a d y n ( w i s c o n s i n ) ， p a b l o ( i l l i n o i s ) ，f a l c o n ( i b m ) 等。但这些工具或环境主要用在单机或集群的 分布式并行计算，而不适合于网格计算的动态环境【2 。 本章第一节介绍了网格计算的个较为通用的定义和分类、网格与一般分布 式计算系统相比所具有的特点和其主要研究方向。第二节阐述了网格资源监控和 应用性能监控工具的必要性和主要的发展趋势。第三节回顾了目前世界上主要的 网格项目。第四节回顾了目前世界上主要的并行和分布式计算的性能分析和调节 工具。第五节对本章所述内容进行了小结。 2 1 网格计算 随着i n t e r n e t 的发展，研究人员可以将很大范围上地理分布的异构计算机 系统集合在一起形成一个大规模的计算平台。该领域的研究产生了一个新的软件 体系结构，称之为网格( g r i d ) 。网格计算( g r i dc o m p u t i n g ) 的概念来源予电网 ( e l e c t r i c a lp o w e rg r i d ) ，人们试图实现：类似于家用电器能够极为方便的从 电网中使用电力资源，计算应用也能够便利地从一个大范围的分布的资源池中获 取所需的各种计算资源f 1 。近年来世界各地开展了许多相关的研究项目，初步 的研究结果表明网格计算确实是一个可行的高性能广域分布式计算模型，同时这 些初步的结果也展示了许多急需解决的挑战性问题。网格计算最大优点是有利于 中国科学技术大学博士学位论文 第二章网格计算与性能监控 全国 全球) 范围内各种计算和数据资源的共享，这些包括数据资源、高性能计算 机、贵重设备、软件等。 2 1 1 网格的定义 目前，网格计算还没有一个十分精确的定义，下面是i a nf o s t e r 给出的一 个较为通用的定义。 定义2 1网格就是在缺少中央控制、没有全知者( o m n i s c i e n c e ) 以及强的信任 关系的情况下能够协同使用地理分布的各种资源。 通常网格系统可分为计算网格( c o m p u t a t i o n a lg r i d ) 、数据网格( d a t ag r i d ) 和服务网格( s e r v i c eg r i d ) 三类 3 】： 1 计算网格是一个能够提供可信赖的、一致的、普遍的和廉价的高端计算 能力的硬件和软件底层，有着更高的计算能力。分布式超级计算网格在多个机器 上执行并行应用以减少一个工作( j o b ) 的执行时问，一般是有巨大挑战性的问 题( k i l l e ra p p l i c a t i o n s ) 。 2 数据网格是用来提供从多个广域分布的数据源合成新的信息底层的系 统，典型的应用包括从多个信息源得到相关信息的数据挖掘以及处理分布数据的 各种物理高能实验。 3 服务网格提供单机所不能提供的各种服务。这些应用往往更重视性价比 而不是单单追求绝对的性能，资源需求是动态的通过一个虚拟空间提供用户和应 用间的实时交互，因此需要支持跨越多个不同机器的服务质量 需求包括：单点登录 ( s i n g l es i g no n ) 。即用户只需要注册一次就可以任意使用网格中他有权存取 的资源；授权，用户可以给程序授权以存取可用的资源。同样，程序可以给另外 的程序授权和各种局域安全系统整合，基于用户的信任关系，不需要资源提供者 之间进行合作、交互来构造安全环境。网格通信保护需求，灵活的消息保护，支 持各种可靠的通信协议。支持独立的数据单元，现在一般采用x 5 0 9 协议。网格 授权( a u 七h o r i z a t i o n ) 需求：由资源拥有者授权，能进行各种限制的授权。一 个通用的办法是给网格中的每个实体分配一个全局唯一的证书，每个实体可以通 过将其权限的一个子集授权给第三方来创建一个临时身份叫做代理。 3 编程模式：由于网格环境的复杂性，目前没有一致意见认为哪种编程模 式最适合网格环境。在各种网格项目中针对各自的特殊情况，采用了多种已存在 的编程技术，包括： ( 1 ) 底层技术如流通信( u d p ，t c p ，m u l t i c a s t ，) 等。 ( 2 ) 共享内存和多线程( d i s t r i b u t e ds h a r e dm e m o r yt e c h n i q u e s ) 。 中国科学技术大学博士学位论文 第二章网格计算与性能监控 ( 3 ) 数据并行。 ( 4 ) 消息传递( m p i ，p v m ) 。 ( 5 ) 远端过程调用( d c e 中采用) 。 ( 6 ) 面向对象( c o r b a ) 等。 ( 7 ) 代理( a g e n t s ) 。 网格环境下的共享内存编程模式也被采用，其主要好处在于容错和持续 ( p e r s i s t e n c e ) 。由于网格中的通信能力对设计网格应用程序有着重大的影响， 编程也被广泛地使用