（计算机软件与理论专业论文）一个可移植的远程计算环境及其技术研究.pdf

圭查奎望查兰堕主兰堡垒苎一一一! ! 墨 摘要 j 使用异构网络系统进行高性能科学计算或“通用的”事务处理在过去的几年中已被证明 i 是苟行的。但是局域网上的并行计算存在着透明性差和计算容量有限的问题，随着网络技术 的不断发展，网络计算已经不再局限于局域环境中，利用广域网络中的计算机完成计算成为 新的研究焦点。人们一直在讨论四通八达的计算机网络会给人类社会带来怎样的影响，许多 机构都在致力于研究将地理上分布的各高性能计算机进行协同使用，即元计算( 也称为网格 计算) 。当前已经出现了许多基于广域网的元计算系统，其中有些研究项目得到了各国政府 的资助。 无差别地使用远程资源已经是一个毫无争议的主题，问题是在什么样的层次上和以什么 ) r 一7 样的方式利用这些分布式的资源：7 从我国网络基础设施的现实条件出发，卿研究了类特 ， 殊的元计算，即所谓的g r i d r p c 计算。lg r i d r p c 系统不仅把硬件看作是一种可以共享的资 f 源，而且把软件也看作是可以共享的资源。对于缺乏高性能计算机和编写并行软件困难的普 ， 遍情况来说，研究怎么样远程使用并行软件库就显得尤其重要。，r 一 i ， 本文的主要研究内容和贡献如下： ( 1 ) 针对局域网上的并行计算透明性差和计算容量有限的问题，本文论述了和分析了元计 算( m e t a c o m p u t i n g ) 的研究现状，并提出我们在目前的现实条件发展元计算环境的 设想。 f ( 2 ) 在广域网上构造计算环境，可移植性是至关重要的( 因为要面对的硬件是千差万别。 j a v a 语言及其分布式对象技术r m i 则以良好的跨平台特性真正地实现了“编写一次 即可随处运行”的设想，因此绝大多数研究者都选择j a v a 语言作为开发基于广域网 计算系统的基础。在分析相关工作优点与局限性的基础上? j ；受提出了一个使用。i 作为中间层、后端使用j a v a 消息传递环境的远程计算解决方案： a v a 并行虚拟环境 j p v e ( j a v ap a r a l 1 e lv i r t u a le n v i r o n m e n t ) 。i p v e 支持对象系列化和“动态类载 入”。能够实时调整需要、易于维护、灵活、强化了计算手段。j p v e 中分了三类实 体、四种应用角色，分工明确，从软件工程和资源管理的角度来说，对并行计算的普 及无疑是有利的，j y ( 3 ) 我们实现了一个j p v e 中的负载监测系统j s y s 。它能够实时测量构成计算环境的网络 和节点机的负载状况，并将负载倍息通过a p i 调用的形式传递给应用程序，供动态负 上海交通大学博士学位论文摘要 载平衡算法使用。j s y s 体现了动态可扩展性、异构性、致透明性以及效率的设计 思想。 ( 4 ) 虽然粗粒度的s p m d 计算可以加速程序的执行，然而考虑处理器对应用程序不同的 处理性能可以进一步发掘这种能力。此外程序的响应时间与系统的负载状况有很大的 关系，任务调度和数据划分在很大程度上决定并行计算的性能。在这个j p v e 环境下，7 ， 本文研究了程序的响应时间与系统的负载状况之间的关系，提出最大异构任务调度算 ， 法i f 它充分考虑了系统对于程序的处理特征及系统的结构和状态，在缩短计算密集型 程序响应时间方面取得了较好的效果。 ( 5 ) 在异构系统并行计算中，通信和计算的能力这两个系统的主要特征对于系统性能的发 挥至关重要。但由于通信量度量的不太容易及其引入后任务调度的复杂，所以现在少 有考虑通信在调度中的影响。同时，子任务的协同是协作模式并行算法的一个重要特 x 一一一。 征。j 本文给出了异构环境下的消息传递并行算法运行时间模型。在这个时间模型的基 础上，彩d 提出了修正的协作任务最优化调度算法。j 算法不仅考虑到子任务的协同、 工作站的计算能力及与此相关的负载平衡问题，而且考虑了网络的通信能力和计算中 产生的通信开销，因而更加准确和更加符合实际的应用 ( 6 ) 最优化协作任务调度算法时间复杂度较高。本文又接着提出了启发式的算法h c s ， h c s 虽然比传统最优化算法多考虑了通信的问题，但由于采用了启发式算法，时间 复杂度并没有因此而增加，朝着实用化的方向迈出了重要的一步。 需要指出的是，( 4 ) ( 6 ) 讨论的数据并行程序都是基于j p v e 环境供用户调用的并行程序， 是一种会反复使用和受系统控制的应用程序( r e c u r r i n ga p p l i c a t i o n s ) ，在算法方面就可能得 到系统额外的信息和一些加强的假设，这是与单纯执行用户提交作业的远程计算所不同的地 方。 最后，本论文给出了结论，并概述了今后进一步研究的方向。 关键词t 糁计算迫垦焦递t 型算，复妻汗衡，协作任务调度 上海交通大学博士学位论文摘要 i ti sp r o v e dt h a th i g hp e r f o r m a n c es c i e n t i f i cc o m p u t i n go rg e n e r a l p u r p o s et r a n s a c t i o nc a l lb e p r o c e s s e de f f e c t i v e l yb yu t i l i z i n gh e t e r o g e n e o u sn e t w o r ks y s t e m h o w e v e r ，p a r a l l e lc o m p u t i n g o n t h el a nh a ss o m ed e f e c t ss u c ha sl a c k i n gt r a n s p a r e n c ya n dc o m p u t i n gc a p a c i t yl i m i t e d a l o n g w i t ht h ed e v e l o p i n go fn e t w o r kt e c h n o l o g y , n e t w o r kc o m p u t i n gn ol o n g e rl i m i t e dt ol a n m a n y r e s e a r c h e r sa r ei n v e s t i g a t i n gh o wt oe x t e n di tt ow a n e n v i r o n m e n t c u r r e n t l y , t h e r ea r em a n y w a n b a s e dc o m p u t i n ga n dc o o p e r a t i v es y s t e m st h a ta r ec a l l e dm e t a c o m p u t i n gs y s t e m s o m eo f t h e ma r ef o u n d e d b y r e l a t i v eg o v e r n m e n t s a c c e s s i n g r e m o t er e s o u r c e st r a n s p a r e n t l yi saf e l l o wf e l l i n g ，b u tt h ep r o b l e mi st h a ta tw h i c h l e v e la n d b y w h i c hm a n n e rw ec a nh a r n e s st h e s ed i s t r i b u t e dr e s o u r c e s a c c o r d i n gt ot h ec o n d i t i o n o fo u rn a t i o n a ln e t w o r ki n f r a s t r u c t u r e , w ei n v e s t i g a t eas p e c i a lk i n do f m e t a c o m p o t i n gt h a ti s s o c a l l e dg r i d r p c g r i d r p cr e g a r d sn o t o n l yt h eh a r d w a r eb u ta l s ot h es o t b , v a r ea ss h a r e a b l e r e s o u r c e s f o rt h eu n i v e r s a lc o n d i t i o no f l a c k i n gh i g hp e r f o r m a n c ec o m p u t e ra n dp a r a l l e ls o l w a r e ， s t u d y i n gh o w t ou s er e m o t ep a r a e ll i b r a r yi si m p o r t a n t t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w i n g ： ( 1 ) p a r a l l e lc o m p u t i n go nl a nh a st h es h o r t c o m i n go fl a c k i n gt r a n s p a r e n c ya n d c o m p u t i n g c a p a c i t yl i m i t e d a i ma tt h i sp r o b l e m ，t h i sd i s s e r t a t i o nf i r s tr e v i e w sa n da n a l y z e st h er e s e a r c h s t a t u so f m e t a c o m p u t i n g t h e n ，w ep r o p o s et h et e n t a t i v ep l a nf o rd e v e l o p i n gm e t a c o m p u t i n g u n d e ro u r p r a c t i c a lc o n d i t i o n ( 2 ) p o a a b i l i t yi sv e r yi m p o r t a n tf o rw a n b a s e dc o m p u t i n gs y s t e m sb e c a u s et h e i rh a r d w a r e sa r e g r e a td i f f e r e n c e s j a v al a n g u a g ea n dr m id i s t r i b u t e do b j e c tt e c h n o l o g yh a v et h eg o o dc h a r a c t e r t h a t “w r i t eo n c e ，r u na n y w h e r e ”，s om o s tr e s e a r c h e r sm a d ej a v a t e c h n o l o g y a st h e c o m p o n e n tf o rc o n s t r u c t i n gm e t a c o m p u t i n gs y s t e m b a s e do nt h ea n a l y s i so fr e l a t e dw o r k s ，w e d e s i g nar e m o t ec o m p u t i n g s c h e m ew h i c hu s e sr m ia sm i d d l e w a r ea n dj a v a m e s s a g ep a s s i n g e n v i r o n m e n ta sb a c k - e n d ，c a l l e dj p v e ( j a v ap a r a l l e lv i r t u a l e n v i r o n m e n i ) j p v es u p p o r t s o b j e c ts e r i a l i z a t i o na n d “d y n a m i cc o d ed o w n l o a d ”，s oi ti sm o r ep o w e r f u l ，e a s i e rm a i n t e n a n c e ， f l e x i b i l i t ya n dc a l lr e a l - t i m ea d j u s t m e n tt od e m a n d j p v eh a st h r e em a j o rc o m p o n e n t s ，f o u r d i f f e r e n te n t i t i e sa n dt h e i rd u t i e sa r ec l e a r f r o mt h ev i e w p o i n to fs o f t w a r ee n g i n e e r i n ga n d r e s o u r c e sm a n a g e ，t h a ti sa l s op r o f i t a b l ef o rp o p u l a r i z a t i o no f p a r a l l e l c o m p u t i n g “i 圭塑奎望盔茎堡主堂竺丝奎 塑墨 ( 3 ) w ea l s oi m p l e m e n tj s y s ，t h el o a di n s p e c t i n gs y s t e mi nt h ej p v e j s y sg a t h e r st h el o a d i n f o r m a t i o no fn e t w o r ka n dn o d em a c h i n e sa n dp r o v i d e s t h i si n f o r m a t i o nt o a p p l i c a t i o n s t h r o u g ha p i i te m b o d i e st h ed e s i g np h i l o s o p h yo fs c a l a b l e ，h e t e r o g e n e o u s ，t r a n s p a r e n ta n d e f f i c i e n t ( 4 ) a l t h o u g he x e c u t i n gs p m d t a s k si nac o a i s e g r a i n e df a s h i o nc a ny i e l dac o s t 。e f f e c t i v es o l u t i o n ， h e t e r o g e n e o u sc o m p u t i n gs e e m sm o r ep o w e r f u l f u r t h e r m o r e ，t h es y s t e m s l o a di so fv i t a l i m p o r t a n c et ot h ec o m p l e t et i m eo fap r o g r a m t a s ks c h e d u l i n gm e t h o da n dd a t ap a r t i t i o n s c h e m e sd e t e r m i n et h ep a r a l l e lc o m p u t i n gp e r f o r m a n c et oal a r g ee x t e n t i nt h i sd i s s e r t a t i o n ，a b i g g e s t - h e t e r o g e n e o u ss c h e d u l i n ga l g o r i t h mi sp r e s e n t e d i th a sf u l l y c o n s i d e r e dt h es y s t e m c h a r a c t e r i s t i c s ，s t r u c t u r ea n d s t a t e t h er e s u l t so fe x p e r i m e n ts h o wt h e a l g o r i t h m c a n s i g n i f i c a n t l y s h o r t e nt h er e s p o n s et i m eo f c o m p u t a t i o n - i n t e n s i v e j o b s ( 5 ) t h em a j o rs y s t e mc h a r a c t e r i s t i c s c o m m u n i c a t i o na n dc o m p u t a t i o nc a p a b i l i t y a r e t h ek e y st o g o o dp e r f o r m a n c e w h e n e x e c u t i n gs p m d - s t y l e t a s k so n h e t e r o g e n e o u ss y s t e m t h e c o m p u t a t i o n - b o u n da n dc o m m u n i c a t i o n - b o u n d c h a r a c t e r i s t i c so ft h es p m dt a s k sm u s ta l s ob e t a k e ni n t oc o n s i d e r a t i o ni nt h es c h e d u l i n gs c h e m e s o nt h eo t h e rh a n d ，al a r g ea n du s e f u l s u b s e to f p a r a l l e la p p l i c a t i o n sc a nb ec h a r a c t e r i z e du s i n gd a t ap a r a l l e l i t e r a t i v es y n c h r o n o u s a l g o r i t h m s t h e c l a s s e so f d i s t r i b u t e da p p l i c a t i o n sr e q u i r es o m ef o r mo f s y n c h r o n i z a t i o na m o n g t h es u b t a s k s ，h e n c et h en e e df o rc o s c h e d u l i n gt og u a r a n t e et h a ts u b t a s k ss t a r ta tt h es a m et i m e a n de x e c u t ea tt h es a m ep a c eo nag r o u po fw o r k s t a t i o n s ap a r t i t i o n i n ga n dc o s c h e d u l i n g a l g o r i t h mw i t hm i n i m u m t a s k sf i n i s ht i m ei sp r e s e n t e d o n ei m p o r t a n tr a t i o n a lc h a r a c t e r i s t i co f t h i sa l g o r i t h mi si th a sc o n s i d e r e dt h ec o m m u n i c a t i o no v e r h e a d ，s oi ti sm o r ev a l i da n dp r a c t i c a l a sc o m p a r et os i m i l a ra l g o r i t h m s ( 6 ) t h et i m ec o m p l e x i t yo fo p t i m a lc o s c h e d u l i n ga l g o r i t h mi sr e l a t i v eh i g h t h i sd i s s e r t a t i o nt h e n p r o p o s e s ah e u r i s t i c c o s c h e d u l i n ga l g o r i t h m h c s h c sa l t h o u g hc o n s i d e r so n em o r e c o m m u n i c a t i o nf a c t o rt h a nt r a d i t i o n a lc o s h e d u l i n g a l g o r i t h m t i ta d o p t sh e u r i s t i cm e t h o d ，s ot h e t i m ec o m p l e x i t yd o c s n ti n c r e a s es i m u l t a n e o u s l y t h a tt a k e sa l li m p o r t a n ts t e pt o w a r dp r a c t i c a l w a 弘 i ti sn o t e dt h a tt h ed a t a - p a r a l l e lp r o g r a md i s c u s s e da t ( 4 卜_ 啪年尹胃乒酲 上海交通大学博士论文 1 1 引言 第1 章绪论 随着科学技术的加速发展，科学工作者要求解问题的规模不断增大，从而需要更高的 计算能力即高性能计算。高性能计算的研究水平已经成为衡量一个国家高新科技水平和综 合实力的重要标志。利用高性能计算技术可以对所研究的对象进行数值模拟和动态显示， 从而获得实验很难甚至无法得到的结果，因此其被广泛应用于航天航空、气象气候、信息 安全、生命科学、石油物探、材料工程甚至模拟宇宙演化过程等领域中。高性能计算技术 的发展使得计算科学成为人类认识和改造世界的新的方法和途径。它推动了当代科学和高 新技术的发展，并将逐渐影响人们的生活方式。 要实现高性能计算，通常可有两个途径：设计巨型机或引入分布并行计算的概念。因 为前者需开发专用的硬件和软件，所以投资巨大，应用往往局限在军事机构或超大型公司， 并且受到工艺水平等众多因素的制约；而分布式并行计算往往可以充分利用现有的资源， 且通用性较强，所以应用比较广泛。 所谓分布并行计算，就是分而治之，在不违背前后偏序关系的前提下尽可能让多个任 务同时在多台主机上执行。随着网络传输速度的不断提高以及硬件价格的降低，分布并行 计算显示出了强大的生命力，如果算法设计合理，其性能可赶上甚至超过某些巨型机。 美国国家超级计算应用中心( n c s a ) 主任l a r r ys m a r r 曾指出，当前的计算机界有一种 很明显的趋势，那就是利用网络将各种不同的计算机连接起来构成一个虚拟的计算系统来 求解复杂的问题 1 。而这样的一个系统必然是异构计算系统。 异构计算( h e t e r o g e n e o u sc o m p u t i n g ，h c ) 的概念源于9 0 年代初期，指由高速网络连 接的一系列计算单元( 处理机) 协同完成某特定任务，使系统开销最小。其中异构是相对 同构而言的( 同构实际是异构的一个特例) ，即系统中处理机计算速度、系统结构、负载以 上海交逯大学端士论文 及数据砖翰珞式窝髑络类型霹缝互不摆网，这为势行程缪豹设计鞠运行带来了一些朗题。 首先悬数据编址的问题，比如，x 8 6 系列所采取的小端编址的方法( l i t t l ee n d i a n ) 帮在存蔽多子一个警节静鼓舞簿，将离位辨字节披在毒蟪，将低位静字节薇在酝垃。嚣u l t r a s p a r c 芯片，使用犬端编址( b i ge n d i a n ) 的方法，将低位的字节放在高址，将高位的字节 放在低址。所以如鬃二者之阐道信发送四字节的整数时，逶倍环壤必须谶行字节位鲎静转 换，促使被发送的消息在两螽机器上的语义一致。 其次，一个并行程序若袋在两台不同系统结构的计算单元上运行，则簧求程序所使用 豹透信巧壤支持嚣粒系统，辩逶援搜。 再次，由于各童机的计算能力不同。必须考虑异构任务的匹配和调魔。以减少计算瓶 颈、提高诗算单元馈蠲效率并提毫诗舞性艉。 尽管丽临种种挑战，但肄构并行计算也孕育着无穷的机会。麓少它有如下若干优点： 使用珑有硬件，减少计算成本； 如果能够合理腹配和调度，可能实现超线性加速比； 可以剃用计算琦题本身的异构性实现性艟饶化，帮将特定裘型的运算安排到专糟杭上 运行，提离运行速度： 虚拟机资源可以随时增减。这有勘于采用最新的计算和网络技术。比如，可使用千兆 鞋太耀、f d d i ( 光纾势凑数据接瓣) 、h i p p i ( 裹性能弦行接翻) 、s o n e t ( 煎步兜纡疆络) 和a t m ( 异步传输模式) 等先进网络技术来提高传输速率： 程亭撼可鞋傻糟自己熬悉瓣耳壤进行程澎湃茇窝调试工露： 应用程序或基本操作系统中可以毫不费力地实现用户级或稷序级的容错。 分布式计算可推进谤同王作。 为了霄效开发异构系统，不仅嚣癸硬件的支持，更主要韵悬瓣要一个通用的网络编稳 环境，由此产生了p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 和m p i ( m e s s a g e p a s s i n g i n t e r f a c e ) 。 1 3p v m 概述 p v m 的创始人题e m o r y 大学豹v a i d ys u n d e r a m 和o a kr i d g e 嗣家实骏塞的a 1g e i s t ， 戴最初目的是为当时新兴的网络异构计算开发个研究框架。以后在1 9 9 1 年公开发布版本 2 0 ，荠不龋蔓蘩，现在己攘掇叛本3 4 莠伴蠢相瘫豹j a v a 实现版本。健燃平台也献纯t f n i x 2 上海交通大学博士论文 转向兼容w i n d o w sn t 操作系统。 p v m 具有以下特点： 通用性强，既适用于t c p i p 网络，又适用于m p p 大规模并行系统； 系统规模小： 为所有的并行机厂商所支持； 源代码开放软件，群策群力，不断发展： 技术发展成熟： 应用人员遍布全世界： 一批标准数学软件正在移植到p v m 平台。 p v m 的关键是虚拟机，即把整个异构计算系统看成一个大的虚拟机。p v m 提供必要的功 能使任务在虚拟机上启动执行并支持任务之间的通信和同步。在p 系统中任务的概念和 u n i x 中进程类似，但不完全相同。由于p v m 提供通信和同步机制，应用程序可以写成一系 列子任务以并行执行，通过发送和接受消息，多个任务可以相互协作并行地解决整个问题。 p v m 支持应用程序、机器和网络等各个层次上的异构。换句话说，p v m 允许应用程序利 用适合其解的最佳的系统结构组合。如果不同的计算机具有不同的整型、浮点型数的表示 形式，p v m 能够处理所有的数据类型转换。另外，p v m 允许虚拟计算机内部由多种形式的网 络互联。 p v m 由两部分组成。第一部分是守护进程p v m d 。该进程必须驻留在组成并行虚拟机的 每个成员机上。当一个用户欲执行p v m 应用程序时，他她可在任何一个主机上执行p v m d ， 然后在该主机上定义自己的并行虚拟机系统构成，与此同时该虚拟机上所有成员的p v m d 都 自动相继启动。此后，用户的应用程序就可在任何一个主机下启动执行。不同的用户可以 定义不同的虚拟机，彼此之问可以重叠，但它们可相互独立同时运行。 p v m 的第二个部分是系统定义的原语( 函数) 库。备种原语的功能包括消息传送、进程 派生、进程协调同步以及虚拟机组成控制等。应用程序可以有选择地使用最合适的原语编 程。同应用程序的不同部分可以使用不同的程序设计语言( c 或f o r t r a n 7 7 ) 。从用户角度 来看，p v m 软件为程序员提供了最佳的程序设计环境。 主海变逯大学擗士论文 m p i 是消息传遂爨垂( m e s s a g ep a s s i n gi n t e r f a c e ) 豹楚髂，它也是一秘蒡露编翟珏 域。为了统一互不兼容的用户界面，1 9 9 2 年成藏了m p i 论坛( m p if o r u m ，简称m p i f ) ，负 赛翻定游意传递赛瑟静象标准，支持最佳舞霹移楗平台。m p i 在标准仡过纛串羧浚了欧美0 个主要组织的6 0 名代表参加，包括研制并行计算机的大多数厂商。以及来自大学、实验室 与工韭赛的研究人员。正式的棘准化过穰是从1 9 9 2 年4 月由并彳亍计算研究中心( t h e c e n t e r f o rr e s e a r c ho i lp a r a l l e lc o m p u t a t i o n ) 支持召开的研讨会上歼始的。在会上讨论了作 为一个标准消息传递界面所篡有的基本特征。当年n 月发表了草稿( 1 9 9 3 年2 月修改) 。 1 9 9 4 年发鸯了m p i 豹定义与 式验舨本w p il ，并子9 7 年疑袭了m p i2 。 m p i 的目标是嚣开发一个广泛用千编写消息传递程序的标准。要求用户界面实用、可 移撬、寒效、灵活，匏广泛爝予套类并行极，黪期是努毒式存馕瓣并行橇。透1 0 霉来每个 计算机厂商都在开发标准平台上作了大量的工作，出现丁一批可移植的消息传递环境。m p i 正是吸取r 德们各蠢的有益经验，犀释获句法葛语法两方面确定核心库函数，使之自适用 于更多的并行机。 m p i 的完整目标簧求如下： i )设计个应爆穆岸设计接口( 并不定要实现编译器线系统调耀库) 。 2 )允许肖效的通讯，避免内存到内存的拷贝，允许计算与通信的重叠以及进行处理器通 通，如浆可能熬话。 3 )允许实现异构环境下的版本。 4 )允许便攀l 懿c 奄f o r t r a n 7 7 戆绑囊。 5 )假设一个可靠的通信接羽：用户不必处理那些通信错误，这蝗错误应由底层通信子系 统处理。 6 ) 定义一个接口使之与网翦的一些应用类似，如p v m 。撇，e x p r e s s ，p 4 等，并提供扩 展使之有极大的荧活性。 7 ) 定义个接口，傻之可以在许多厂糍豹平裔上实现，嚣不必搓底层避馈熬系绞软终上 进行大的改动。 8 ) 接曩黔浯义应燕独立于港害戆。 9 )接口应设计为线程安全( t h r e a d s a f e t y ) 的。 鲡瓦n 搬辩i 毪交特患戮熹静菠逢释接收，及组的穰念。i p i 特掰在多点之阍的集群 4 上海突避大学髂士论文 逶攘上作了缀多工终。m p i 中豹集群逶售方式包括：广播( b r o a d c a s t ) ，收嶷( g a t h e r ) ， 发敞( s c a t t e r ) ，同步( b a r r i e r ) 以及全局归约运算( r e d u c eo p e r a t i o n ) 。m p i 究全支 待撵步发送秘接牧，繇棼疆塞式( n o n b l o c k i n g ) 发送鞠接收，筑蓑囊歪实现计算鸯逮痞 的遂叠。m p i 在各自甄不干扰的通信上下文( c o m m u n i c a t i o nc o n t e x t ) 中通信。通信上下 文爵戳台并。分截和鬟维。不道，静fl 串不支持动态诗葬送程的生或，毽这己在m p i2 中弥补。 作为一个新标准，m p i 吸收了大避消息传递环境如i n t e ln x 2 ，e x p r e s s ，n c u b e s v e r t e x ，p 4 和p a i o i i a c s ，以及z i p c o d e ，c h i m p ，p v m ，c h a m e l e o n 和p i c l 的优点，将之融 合在一起，并在某些方面做了优化和改进。虽然m p i 推出才几年，但在国际上已普遍使用， 曼鲻户与使翅p v m 鹁羯户相巍。 参考文献 2 详尽地讨论了p v m 和m p i 在特征上的差肄。 1 5 存在的问题 p v m 和m p i 代袭了目前并行程序设计环蟪的主流，无数的并行程序趄基于这两个工 具嚣开发驰，阑酵。也毒无数戆计算撬系统支持这嚣令王其，包旗各静超缀；十算撬、u n i x 工作站群和b i t 工作站群。但是他们使用起来并不方便，有着自身不可克服的缺点：首先， 透明经和灵活性菱，编写莛柬较为困难；表现梵： 1 ) 用户必颁了解运行环境的阿络结构，包括各个运行结点机器的i p 地址和域名。 2 ) 用户必须在运行程庠的各个结点梳上拥有嫩碍。 3 ) 用户必须针对不同的系统结构对网程序进行多次的缓译，以产生相应系统结构上可以 运行的代码。 4 ) 用户必壤手动黥掩援玛拷炎到各个参与运算的续点枫嚣土。 5 ) 在u n i x 工作站群上运行时，用户必须建立各个工作站之间的信任关系，这样就带来较 大嚣安全憋患。 6 ) 缺乏负裁平衡和任务调度机制，用户要对参与计算的进程的分布进行一定干预和指导。 7 ) 由于异构系统上代玛和数据格式静举间，缀难进行当系统配鬻敬变或受载重大鼙仡时靛 进程迁穆，因而这种在同构系统上成功的动态负载平衡方式在这里实现起来非常困难。 其次，由于p v m 和m p i 由c 或c + + 实现，提供c 、c + + 、f o r t r a n 接口。使得用p v m 暑nm p l 开发豹并行獠序不能拄异构系缀中做到无缝移植、运行，这又表现为： 上海交通大学博士论文 8 ) 需要对被移植并行程序之源代码进行显式编译以生成对应于特定系统的执行代码。 9 ) 被移植的并行程序的源代码有可能需要做少量修改方可在特定的系统上通过编译。 1 0 1 当全新的系统出现时，需要将p v m 和m p i 移植到新的系统上方可将原有的并行程序 移植到新的系统上。 最后鉴于局域网络的容量有限，c l u s t e r 虽然提供了相当高的计算能力，但是相比与 广域网络上无限待开发的计算潜力来说还是很小的。 1 6 本文的主要贡献、创新点及章节安排 ( 1 ) 针对局域网上的并行计算透明性差和计算容量有限的问题，本文论述了和分析了元 计算( m e t a c o m p u t i n g ) 的研究现状，并提出我们在目前的现实条件发展元计算环境 的设想。这是第一章和第二章的内容。 ( 2 ) 提出一个使用r m i 作为中间层、端到端完全可移植且计算功能有所加强的远程计算 解决方案：j a v a 并行虚拟环境j p v e ( j a v ap a r a l l e lv i r t u a le n v i r o n m e n t ) 。j p v e 支持对象系列化和“动态类载入”，能够实时调整需要、易于维护、灵活、强化了 计算手段，而没有了现有g r i d r p c 系统固有的缺陷。这是第三章的研究内容。 ( 3 ) 我们实现了一个j p v e 中的负载监测系统j s y s 。j s y s 体现了动态可扩展性、异构性、 一致透明性以及效率的设计思想。 ( 4 ) 在这个j p v e 环境的前提下，研究了程序的响应时间与系统的负载状况之间的关系， 提出最大异构任务调度算法，它充分考虑了系统对于程序的处理特征及系统的结构 和状态，在缩短计算密集型程序响应时间方面取得了较好的效果。这是第四章的研 究内容。 ( 5 ) 在异构系统并行计算中。通信和计算的能力这两个系统的主要特征对于系统性能的 发挥至关重要。但由于通信量度量的不太容易及其引入后任务调度的复杂，所以现 在少有考虑通信在调度中的影响。同时子任务的协同是协作模式并行算法的一个 重要特征。本文给出了异构环境下的消息传递并行算法运行时间模型，在这个时间 模型的基础上，我们提出了修正的协作任务最优化调度算法。算法不仅考虑到子任 务的协同、工作站的计算能力及与此相关的负载平衡问题，而且考虑了网络的通信 能力和计算中产生的通信开销，因而更加准确和更加符合实际的应用。这是第五章 6 上海交通大学博士论文 的研究内容。 ( 6 ) 最优化协调度算法时间复杂度较高。本文又接着提出了启发式的算法h c s ，h c s 虽然比传统最优化算法多考虑了通信的问题，但由于采用了启发式算法，时间复杂 度并没有因此而增加，朝着实用化的方向迈出了重要的一步。这也是第五章的研究 内容。 需要说明的是，( 4 ) ( 6 ) 讨论的数据并行程序都是基于j p v e 环境供用户调用的并行程 序t 是一种会反复使用和受系统控制的应用程序( r e c u r r i n ga p p l i c a t i o n s ) ，在算法方面就可 能得到系统额外的信息和一些加强的假设，这是与单纯执行用户提交作业的远程计算所不 同的地方。 第六章给出了本论文的主要结论和进一步研究的方向。 7 上海交通大学博士论文 笫2 章元计算概述 使用异构网络系统进行高性能科学计算或“通用的”事务处理在过去的几年中已被证 明是可行的。设想，即使一台p c 的计算能力是有限的，但如果将成百上千的p c 用高速网 络连接在一起，其总和的性能肯定是非常高的。并且应该可以与超级计算机相媲美：同时， 这么多的p c 的价格则远远低于那些精心制作的超级计算机的。这就是c l u s t e r ，真正物美 价廉的东西。自然，这样连接而成的系统多为异构系统。从结构上来说，目前的超级计算 机与c l u s t e r 其实是类似的，只不过超级计算机的组成元素是简化的处理机，仅拥有私有 内存，偶尔有i o 处理的能力：而且连接这些组成元素是比局域网更快的内部网络罢了。 但c l u s t e r 仅是从对超级计算机性能的不断挖掘向全球互连网中公共计算服务潜力提 炼进行转变的第一步行动。如果积极考虑网络性能对计算的影响，那么我们其实可以将更 大范围的网络上计算机连接起来提供整体的计算服务，这个大范围的网络可以是校园网。 城域网，全国网络，以至于全球互联网。连接的对象也不局限于低性能计算机。那些超级 计算机也可以作为一个节点连入这个计算服务系统，并起到中流砥柱的作用。这就是元系 统。 元计算( m e t a e o m p u t i n g ) ，又称元计算系统( m e t a c o m p u t i n gs y s t e m ) ，或元计算机 ( m e t a e o m p u t e r ) ，这一术语随着时间的延伸，有不同的定义或含义。早期( 1 9 9 2 年) 的 元计算被定义为用户通过网络环境可透明地使用的那些计算资源，因此元计算实质上是一 个由软件有机连接的异构计算资源的网络。在这种软件连接方式下，对这些计算资源的使 用之简便犹如使用一台p c 机。由于元计算系统的主要功能之一是将地理上分布的各高性 能计算机进行协同使用，所以有的学者干脆简称元计算为分布式高性能计算。近年来，有 些学者还把元计算系统称为元系统( m e t a s y s t e m ) 甚至元计算环境( m e t a c o m p u t i n g e n v i r o n m e n t ) 3 】【4 】 5 】【6 】 7 】。9 0 年代中期后国外不少学者将元计算称为网格计算( g r i d c o m p u t i n g ) ，比喻它如同电力网一样，可让用户如用电那样来使用高性能计算能力。本 文中将对这两种术语不加区别的使用。 我们认为比较确切的元计算系统的含义是：从物理上讲，元计算系统是由高速网络互 连的、在地理上分离的资源的集合( 包括计算资源和信息资源等) 。从逻辑上讲，它是由软 件有机地连接的异构计算资源的网络，在这种软件构成方式下，对这些资源的使用犹如使 旷厶p c 机那样方便这就舭元计算系统的主要特意是宫麓廊用户强辨一懈i 8 分布、共享、安全和容错的服务环境。它可根据用户需求，选择最合适的场所和方式来执 行用户程序( 如要求满足一定的求解速度、在规定的时间内完成求解任务等) 。元计算系统 向用户展示的是一个拥有强大计算能力、存储容量和i 0 能力的单一系统映象，用户可对 它进行方便的使用。因此它绝不是众多异构计算和信息资源的简单合成。 2 1 元计算环境( m e t a c o m p u t i n ge n v i r o n m e n t ) 2 1 i t 元系统 在讲元计算环境之前，有必要解释一下元系统( m e t a s y s t e m ) 。 从广义上讲，元系统是一个异构系统，这个系统由某种网络将多个组件无缝的结合在 一起，每个组件有自己的分工，完成某一特定的任务。整个系统通过网络将所有组件协调 起来完成一个总体目标，并对外表现为一个单一的整体。组件对外是不可见的。 从这个意义上来说，任何形式的集体都可以算是个元系统。小至由细胞核、细胞膜 组成的细胞，大至一个班级，一个公司，以至于一个国家都