（计算机应用技术专业论文）基于net平台的并行计算在随机游走算法的应用.pdf

中文摘要 论文题目： 专业： 硕士生： 指导教师： 基于n e t 平台的并行计算在随机游走算法的应用 计算机应用技术 康国庆( 签名) 王家华( 签名) 摘要 油气储层的随机游走建模的算法是一个大规模计算的问题。 实践已经证明利用自回避随机游走建模方法可以解决曲流河空间位置，从而提高油 藏评价和建模的效果。在这种方法的建模中，算法需要长时间的运算。例如，在奔腾4 2 4 g 的微机上需要运算8 个小时，在得到的五百多万个可能性相同的实现中，才能够选 出合格的结果。所以，利用并行计算方法，缩短运行时间，对于自回避随机游走建模方 法的实际应用而言，具有重要的意义。 本文分析了当前并行计算的基本理论，和常用编程技术的特点，面向自身需求对基 于n e t 平台并行计算的关键技术进行具体研究。在此基础上设计和实现了油气储层随机 游走建模并行计算系统。本文做的主要工作如下： 1 ) 分析研究了当前分布式并行计算领域几种常用编程技术的特点和不足，研究了以分 布式对象为方法的n e tr e m o t i n g 的关键技术、实现细节。以此为基础构思了系统 的整体思路。该设计的特点就是通信量小、反应速度快、可以方便的扩充该并行系 统的客户机数量。 2 ) 针对随机游走算法的特点，在详细设计该系统时，使用了粗粒度的并行计算方式， 改造了随机种子的回收方式，用实现服务器分发种子；使用了异步通信模式，从而 提高了整个系统的运算能力。 3 ) 在开发随机游走并行计算系统中，针对油田输入数据格式的多种多样，设计了灵活 的数据导入系统，可以方便的支持新的数据格式；程序设计中使用了大量的设计模 式，使系统的易用性，可扩展性得到了提高。 4 ) 最后，本文还利用实际工区的数据做了分析和验证。对系统的加速比做了讨论，使 用n d e p e n d 对软件的代码质量做了度量。结果表明该系统能在不破坏现有网络环 境下提供了可靠的，易于扩充的并行计算能力。 关键词：并行计算随机游走n e t 论文类型：应用研究 i l 英文摘要 s u b j e c t ： s p e c i a l i t y ： n a m e ： i n s t r u c t o r ： n e tp l a t f o r mb a s e dt h ea p p l i c a t i o no fp a r a l l e lc o m p u t i n gi nr a n d o mw a l k c o m p u t e ra p p l i c a t i o nt e c h n o l o g y a b s l r a c 。l 。 i ti sam a s s i v ec o m p u t a t i o np r o b l e mf o rt h ea l g o r i t h mo fh y d r o c a r b o nr e s e r v o i r s r a n d o m w a l km o d e l i n g p r a c t i c eh a sp r o v e dt h a tu s eo fs e l f - a v o i d i n gr a n d o mw a l km o d e lw a y st os o l v et h e m e a n d e r i n gr i v e rs p a c el o c a t i o n ，t h e r e b yi m p r o v i n gt h ee v a l u a t i o na n dr e s e r v o i rm o d e l i n g r e s u l t s h o w e v e r ，t h i sm e t h o do fm o d e l i n g ，a l g o r i t h mn e e d sal o n gp e r i o do fo p e r a t i o n t h e r e f o r e ，t h eu s eo fp a r a l l e lc o m p u t i n gm e t h o d s ，s h o r t e n i n gt h et r a v e lt i m ef o rs e l f - a v o i d i n g r a n d o mw a l km o d e lo ft h ep r a c t i c a la p p l i c a t i o no fm e t h o d s ，h a sg r e a ts i g n i f i c a n c e t h i sp a p e ra n a l y z e dt h ec u r r e n tf i e l do fp a r a l l e lc o m p u t i n gt e c h n o l o g yc o m m o n l yu s e d p r o g r a m m i n gf e a t u r e s ，a n df a c et ot h es p e c i f i cr e q u i r e m e n tb a s e do n n e tp l a t f o r mp a r a l l e l c o m p u t i n gt h ek e yt e c h n o l o g ys p e c i f i cr e s e a r c h o nt h eb a s i s ，d e s i g na n di m p l e m e n t a t i o n r a n d o mw a l kr e s e r v o i rm o d e l i n gp a r a l l e lc o m p u t i n gs y s t e m k e y c o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 ) t h i sd i s s e r t a t i o nr e s e a r c h e do nt h ea l g o r i t h mo fs e l f - a v o i d i n gr a n d o mw a l kt ot h e m o d e l i n gm e t h o do ft h es i n g l ep e r i o ds n a k i n gf i v e rm a i n s t r e a ml i n e t h em i c r o - f a c e s m o r p h o l o g yo fc r e v a s s e - s p l a y , m a r g i n a lb a n k ，n a t u r a ll e v e e ，a b a n d o n e dc h a n n e le t c w a ss t u d i e d ，a n df i l t r a t i o nr i v e rt y p ew a si m p r o v e d 2 ) a n a l y z e dt h ec h a r a c t e r i s t i c sa n ds h o r t c o m i n g so fc u r r e n tp r o g r a m m i n gm e t h o d so f d i s t r i b u t e d p a r a l l e l c o m p u t i n g s t u d i e dn e t r e m o t i n gk e yt e c h n o l o g y , i m p l e m e n t a t i o nd e t a i l 、航t hd i s t r i b u t e do b j e c tt e c h n o l o g y , a c c o r d i n gt ot h i sw a yd e s i g n t h es y s t e m sa r c h i t e c t u r e 3 ) i n t h ed e v e l o p m e n to fr a n d o mw a l kp a r a l l e lc o m p u t i n gs y s t e m ，t h eo i lf i e l dt oe n t e r d a t af o rav a r i e t yo ff o r m a t s ，d e s i g naf l e x i b l ed a t ai m p o r ts y s t e mt h a tc a nf a c i l i t a t et h e s u p p o r to ft h en e wd a t af o r m a t p r o c e d u r e su s e di nt h ed e s i g no fal a r g en u m b e ro f d e s i g np a t t e r n s ，t h es y s t e m se a s eo fu s e ，s c a l a b i l i t yh a v eb e e ne n h a n c e d 4 ) f i n a l l y , t h er e s u l t sw e r ea n a l y z e da n dv a l i d a t e db yu s i n ga c t u a lw o r k a r e ad a t a i ti s d i s c u s s e ds y s t e m sa c c e l e r a t er a t ea n dm e t r i cs o f t w a r e sc o d eq u a l i t yb yn d e p e n dt o o l s t h eo u t c o m ei n d i c a t et h es y s t e mp r o v i d er e l i a b l e ，e a s ye x t e n dp a r a l l e lc o m p u t i n g a b i l i t ya n dt h a tn e e d n td e s t r o ye n v i r o n m e n ti ne x i s t e n c e k e y w o r d s ：p a r a l l e lc o m p u t i n g r a n d o mw a l k n e t ； t h e s i s ：a p p l i c a t i o ns t u d y i i i 学位论文创新性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他 人已经发表或撰写过的研究成果；也不包含为获得西安石油大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：趣区i 煞日期：2 2 篁：1 2 学位论文使用授权的说明 本人完全了解西安石油大学有关保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属西安石油大学。学校享有以任何方法发表、复制、 公开阅览、借阅以及申请专利等权利，同时授权中国科学技术信息研究所将本论文收录 到中国学位论文全文数据库并通过网络向社会公众提供信息服务。本人离校后发表 或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为西安石油大 学。 论文作者签名： 导师签名： 日期竺塑：望 日期：t ! ! ：! ( 2 注：如本论文涉密，请在使用授权的说明中指出( 含解密年限等) 。 第一章绪论 1 1 引言 第一章绪论 随机游走模型在经济、金融、计算机科学、生物等领域应用极为广泛，利用随机游 走模型刻画河流沉积环境中河道砂体分布方面的文献最早见于文献【l j ，及王家华教授的 专著油气储层随机建模【2 1 。曲流河沉积相随机模拟系统是一个复杂的系统，也是储 层建模领域的难点和重点。采用随机游走对沉积相进行随机模拟可使用来自地质、地震 的数据，获得模拟区域特征的多个图像，辅助地质人员认识储层的物性空间分布和物源 分布特征。 实践证明随机游走模型的理论可用来描述河道走向，随机游走模型可用于刻画河流 沉积环境中的河道砂体的分布，其优点在于可以描述河道砂体的连续性形态、河道宽度、 河道弯曲程度以及河道分叉与汇合程度。在模拟河道走向时，由于随机游走模型算法有 很强的针对性，这些随机游走模型都是针对不同的环境提出的，可以根据不同环境建立 不同的随机模型，不同的环境应用不同的随机模型。在g a s o r 3 4 系统中，创新性的提 出来应用于储层沉积相的随机游走建模对井位数据进行分析，来真实的模拟河流沉积环 境，以尽量准确描述河道砂体的分布，判断河流走向，为石油地质分析的预测和决策做 出合理的判断提供很好的依据和支持。 曲流河不论是现代还是古代都是最常见和最重要的河流类型，不仅砂体成因类型最 多，且伴随着河道侧向迁移及频繁地决口改道、废弃，使得砂体时空分布极为复杂1 6 j 。 这决定了对曲流河的模拟就是在复杂地质条件下的一种模拟。按照曲流河的沉积特点和 演变规律，主要形成主河道、废弃河道、决口水道、决口扇、天然堤、河漫滩六种成因 砂体，其中河道成因的砂体( 包括主河道、废弃河道和决口水道) 不仅厚度大，而且分布 广，是河流相储层的骨架砂体，也是油气主要的储集空间。对曲流河河流相的模拟研究 具有重要的意义。 然而基于随机模拟的建模系统有一个特点，由于随机性的存在，一般对给定的输入 会给出许多个结果来，也称为实现。在随机建模系统中，如果想得到适合实际情况的实 现，一般需要利用多个随机种子，进行许多次的计算。然而，利用自回避随机游走已模 拟曲流河的建模过程，则需要更长时间的计算，利用到几十万次乃至上百万次的实现， 然后在其中选取一些比较合理的结果。这个过程是十分耗费时间的，所以说随机建模是 个大规模计算的问题，随机游走储层建模系统也就是这样一个系统。为了减少建模系统 的运行时间，提高建模的效率，就需要提高系统的运算速度。一方面，可以通过优化随 机游走算法，提高计算机的硬件能力来减少系统的运行时问，另一方面可以通过使用并 行计算技术，利用其它的主机协同工作来提高系统的运算能力。 西安石油大学硕：学位论文 为了提高计算速度和效率，将该建模系统运用并行计算技术，能够将空闲的计算资 源综合起来实现计算能力的提高。在设计该系统时，首先将单机版随机游走建模系统进 行了详细的分析，针对自回避游走算法的特点，考虑了实现并行计算该算法的方式。其 次，面向实际应用并考虑易扩展性，确定了随机游走储层建模并行计算系统的概要设计。 第三，结合n e t 平台、在c 撑开发环境中实现了随机游走建模并行计算系统。最后利用某 油田工区的实际数据做了验证，结果表明该系统能够利用现有的机器设备，能够实现科 学计算的并行化，提高了整个系统的计算能力。 1 2 课题的来源目的及意义 随机游走模型的理论可用来描述河道走向，随机游走模型可用于刻画河流沉积环境 中的河道砂体的分布，其优点在于可以描述河道砂体的连续性形态、河道宽度、河道弯 曲程度以及河道分叉与汇合程度。在原来的系统中，针对不同的河形，可以使用不同的 游走方法，并且可以根据已知的地质认识，比如，弯曲度、河道主方向、弧长、振幅等 参数来限制选取的产生的河流形态。 目前的算法程序是基于n e t 平台的单机程序。在筛选河形时，如果在给定的筛选条件 较宽松的情况下，那么得到好的河形比较困难，计算结果随意性较大；反之，如果设定 的条件较为严格，那么在较短的时间将得不到合适的河形。该系统曾经对某工区通过8 个小时的计算5 百多万个实现中才选出既符合该工区地质特征，又符合所加的人为干预 条件的储层模型来。可见提高运算速度，提高系统的执行效率是当前该软件应用的难点。 以下是原始版本的河流相储层随机游走软件在某计算机某条件下运行的情况。 目标主机配置如下：c p u 是a m da t h l o n3 2 0 0 + ，内存为l g ，运算情况如表l l 。 表l 一1 单机随机游走算法在不同时间内实现的个数 时间( 单位秒)产生实现的个数 试验1 1 0 1 0 3 7 试验2 3 03 2 2 4 试验3 6 07 0 5 9 试验4 1 8 02 2 9 4 0 试验5 3 6 0 04 6 3 9 7 l 试验6 7 2 0 08 4 7 0 4 l 试验7 2 8 8 0 05 1 0 2 1 5 9 表l l 结果是根据相同条件，同一个工区的数据，不同的时间计算的结果。如果想 要找出河流的形态较好，且又符合所设定的限制条件的河流，大量运算是必不可少的， 所以要研究提高该系统计算能力的问题，这个问题对整个系统的应用有重要意义。 第一章绪论 1 3 并行计算的国内外研究现状 1 3 1 并行计算 并行计算【7 , s l 就是：通过网络相互联接的两个以上的处理机相互协调，同时计算同一 个任务的不同部分，从而提高问题求解速度，或者求解单机无法求解的大规模问题。并 行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源， 节约成本一使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的 存储器限制。 为利用并行计算，通常计算问题表现为以下特征： 1 ) 将工作分离成离散部分，有助于同时解决； 2 ) 随时并及时地执行多个程序指令； 3 ) 多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并 行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行 计算。 并行程序并行处理的任务包之间有很大的联系，而且并行计算的每一个任务块都是 必要的，没有浪费的分割的，就是每个任务包都要处理，而且计算结果相互影响，就要 求每个的计算结果要绝对正确，而且在时间上要尽量做到同步，它的任务包个数有限， 在一个有限的时间应该是可能完成的。 目前两种最重要的并行编程模型是数据并行和消息传递【3 2 , 3 3 1 ，数据并行编程模型的 编程级别比较高，编程相对简单，但它仅适用于数据并行问题；消息传递编程模型的编 程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。 数据并行即将相同的操作同时作用于不同的数据，因此适合在p v p 及s m p 并行计算 机上运行，在向量机上通过数据并行求解问题的实践也说明数据并行是可以高效地解决 一大类科学与工程计算问题的。 数据并行编程模型是一种较高层次上的模型，它提供给编程者一个全局的地址空间。 一般这种形式的语言本身就提供并行执行的语义，因此对于编程者来说只需要简单地指 明执行什么样的并行操作和并行操作的对象，就实现了数据并行的编程，数据并行的表 达是相对简单和简洁的，它不需要编程者关心并行机是如何对该操作进行并行执行的。 数据并行编程模型虽然可以解决一大类科学与工程计算问题，但是对于非数据并行 类的问题，如果通过数据并行的方式来解决，一般难以取得较高的效率数据并行不容易 表达，甚至无法表达其它形式的并行特征。数据并行发展到现在，高效的编译实现成为 它面临的一个主要问题。有了高效的编译器数据并行程序就可以在共享内存和分布式内 两安石油大学硕士学位论文 存的并行机上都取得高效率，这样可以提高并行程序的开发效率，提高并行程序的可移 植性，进一步推广并行程序设计。 消息传递即各个并行执行的部分之间，通过传递消息来交换信息，协调步伐控制执 行。消息传递一般是面向分布式内存的，但是它也可适用于共享内存的并行机。消息传 递为编程者提供了更灵活的控制手段和表达并行的方法，一些用数据并行方法很难表达 的并行算法都可以用消息传递模型来实现。灵活性和控制手段的多样化是消息传递并行 程序能提供高的执行效率的重要原因。 消息传递模型一方面为编程者提供了灵活性；另一方面它也将各个并行执行部分之 间复杂的信息交换和协调控制的任务交给了编程者。这在一定程度上增加了编程者的负 担，这也是消息传递编程模型编程级别低的主要原因。虽然如此消息传递的基本通信模 式是简单和清楚的学习和掌握这些部分并不困难，因此，目前大量的并行程序设计仍然 是消息传递并行编程模式。 m p i 加，l l 】( m e s s a g ep a s s i n gi n t e r f a c e ) 是消息传递并行程序设计的标准之一，当前通 用的是m p l l 1 规范。正在制定的m p l 2 0 规范除支持消息传递外，还支持m p i 的i o 规 范和进程管理规范。m p i 正成为并行程序设计事实上的工业标准。而最流行的m p i 工 具集当属m p i c h ，是目前高效率的超大规模并行计算( 1 0 0 0 个处理器) 最可信赖的平台。 m p i 的实现包括m p i c h 、l a m 、i b mm p l 等多个版本，最常用和稳定的是m p i c h ， 曙光天潮系列的m p i 以m p i c h 为基础进行了定制和优化。 它的目标：是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准 m p i 以语言独立的形式来定义这个接口库，并提供了与c 、f o r t r a n 和j a v a 语言的绑定。 这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性，由于这个原因， m p i 在并行计算界被广泛地接受 2 9 , 3 0 】。 1 3 2 n e t 平台与并行计算 n e t 【1 2 , 1 3 , 1 4 平台定义：m i c r o s o f t n e t 是m i c r o s o f t n e tx m lw e bs e r v i c e s 平台。 x m lw e bs e r v i c e s 允许应用程序通过i n t e r n e t 进行通讯和共享数据，而不管采用的是哪 种操作系统，设备或编程语言。m i c r o s o f t n e t 平台提供x m lw e bs e r v i c e s 并将这些服 务集成在一起，为个人用户的好处是无缝的，吸引人的体验。 在n e t 平台上来做并行计算，那么有三种方式： l 、使用n e t 平台支持的语言【2 3 , 2 4 1 如c # ，来重新实现m p i 定义的标准和规范。 a l e x a n d e rc h u d i n o v ，v l a d i m i rr o g a n o v 的论文【1 5 】中描述了俄罗斯科学院多处理机系 统研究中心按照m p i 规范设计的t - - s y s t e m 。该系统使用的纯0 0 语言c # 做实现语言。 2 、使用n e t 平台中的语言做为包装器跨语言调用( p - - i n v o k e ) c 的动态库。 j e r e m i a hw i l l c o c k 、a n d r e wl u m s d a i n e 的一篇论文【1 6 】，详细讨论了用c # 语言实现m p i 4 第一章绪论 的实现框架。文章中考虑了与虚拟机和c l i ( 公共语言接口) 结合，实现的方式是用c + + n e t 做映射包装成n e t 库，然后在使用c # 做用户接口。也讨论了低级库引用c 接口的m p i 实现，包装的n e t 库。文后对其两种实现性能做了测试和比较。 现在有很多面向对象的m p i 库：d k a f u r aa n dl h u a n g 的m p i + + 【1 7 】；j m s q u y r e s ，b c m c c a n d l e s s a n da l u m s d a i n e 的o o m p i t l 8 ，1 9 】；还有针对j a v a t 2 0 引2 2 1 ，p y t h o n 2 5 2 6 1 ， r u b y t z 7 i 的m p i 等等。 3 、使用n e tr e m o t i n g ，自己提出通信方案，实现并行扩展。 抛弃m p i 的规范，通过使用n e tr e m o t i n g 设计自己的实现方案，得到并行计算的优 势。本文就是通过使用分布式对象，自己控制通信的过程，不依赖于m p i 库的实现，来 得到并行计算的效果，这样能够最大控制整个的计算过程。 1 4 论文结构 本文共分七章。 第一章：绪论。简单介绍了本课题的研究背景、课题来源、课题的国内外研究现状 以及本论文将要研究的内容。 第二章：n e t 平台与并行计算。对并行计算和n e t 平台相关概念进行了探讨。 第三章：随机游走河流相建模概述。对随机游走在河流相建模的应用做了介绍。讨 论了曲流河的特点、一些地质属性概念，讨论了几种随机游走的游走特点。 第四章：随机游走的并行计算概要设计。分析了单机版的随机游走河流相建模系统， 考虑了对并行计算有影响的随机种子、筛选算法、匹配率的重要方面。针对实验室的具 体情况，设计了随机游走并行计算的物理模型和逻辑模型。并对软件设计方法和软件设 计规范做出了规定。 第五章：随机游走并行计算系统的详细设计与实现。本章将对系统中的数据导入子 系统、服务器注册与环境设置子系统，服务端客户端通信子系统、客户端随机游走子系 统和显示结果设计子系统分别做了设计和实现。 第六章：随机游走的并行计算系统的应用和度量。本章对该系统选定一个实际工区， 对于不同的机器数目的条件下做了系统运算能力测试，其后对加速比做了探讨。本章第 二部分展示了使用n d e p e n d 软件质量度量工具对本系统整体进行度量的结果。 第七章：结论与展望。 西安石油大学硕士学位论文 第二章n e t 平台与并行计算 2 1 并行计算及并行编程环境 并行计算【2 8 】就是在并行计算机上所作的计算，它和通常所说的高性能计算、超级计 算是同义词，任何高性能计算和超级计算总离不开并行计算。随着计算机和计算方法的 飞速发展，几乎所有的学科都走向定量化和精确化，从而产生了一系列诸如计算物理、 计算化学、计算生物学、计算地质学、计算气象学和计算材料学等的计算学科，在世界 上逐渐形成了所谓计算科学与工程( c s e ，c o m p u t a t i o n a ls c i e n c e & e n g i n e e r i n g ) 的计算 性学科分支。如今，计算科学已经与传统的理论科学和实验科学并列，成为第三门科学。 高速并行计算主要有三种类型的应用需求： ( 1 ) 计算密集型应用，如大型科学工程计算与数值模拟； ( 2 ) 数据密集型应用，如数字图书馆、数据仓库、数据开采和计算可视化等。 ( 3 ) 网络密集型应用，如协同工作、遥控和远程医疗诊断等。 2 1 1 并行计算的分类 自本世纪5 0 年代初美国研制的第一台位并行运算样机以来，并行计算机的发展已经 历了巨大的变化，在硬件和软件技术方面取得了很多成就，产生了多种多样、各具特色、 各有长处的并行处理系统。 根据f l y n n 的分类方法，并行计算机可以分为单指令多数据流 ( s i m d ，s i n g l e - i n s t r u c t i o nm u l t i p l e d a t a ) 和多指令多数据流( m i m d ，m u l t i p l e i n s t r u c t i o n m u l t i p l e d a t a ) 计算机两大类。 1 单指令多数据流( s i m d ) 这种结构并行系统中，处理机同时执行相同的指令流，而同 时处理不同的数据流。s i m d 又可分为如下三种类型： ( 1 ) 阵列型：包括最早的l l l i a c i v ，t h i n k i n gm a c h i n e s 的c m 2 ，m a s p a r 的m p - l 和m p 2 ， 以及d a p 系列。 ( 2 ) 管道型：管道型向量机与列阵型不同，采用的是多路分时技术，不同的数据流采用 同一指令流的不同部分进行并行操作。如早期的c r a y 机和a s c 机。 ( 3 ) 联想型：实际上是一种存储类型而不是计算机机器，可并行同时检索出多个匹配的 存储内容。 s i m d 型机灵活性差但结构简单，可减少每个处理单元的费用。虽然s i m d 型机早 期取得了很大的成功，但很多厂商转向了能力更强的m i m d 型机。 2 多指令多数据流( m i m d ) m i m d 模式覆盖了很宽的各类互联并行计算系统，其基本 思想是每个处理单元都是独立的，每个单元都可以运行不同的程序，处理机之间采用高 6 第二章n e t 平台与并行计算 速网络通讯进行数据共享和同步。m i m d 可分为如下两大类型： ( 1 ) 共享存储器模式( p r a m ) 。这种模式中，存在一个每个处理机都能访问的共享存 储器，假定本地存储器和共享存储器的时间是相同的。已经有一些这种类型并行机，如 c r a yx m e f u j i t s uv p 5 0 0 ，国产银河i i 等。但实际上这种模式可扩展性差，还没有更高性 能的机器出现，因为当处理器增多时，这种模式无法保证大量的处理器访问共享存储器 的时间是一个常量。 ( 2 ) 分布式存储器模式。目前，大部分并行计算机是分布式存储器模式，每个处理单 元是独立的、拥有自己的存储器，每个结点通过高速网络交换数据和信息，结点间的连 接方式有总线结构、环状结构、m e s h 结构和超立方体结构等。通常，每个处理单元由多 个处理器组成，其中某些处理器用于管理和数据传输。 分布式存储器模式也称为消息传递( m e s s a g e p a s s i n g ) 模式，处理单元可向某一地址或 某些地址的处理单元发送各类消息，接收单元保存消息在缓存器中并通知目的任务。当 前的主流高性能机大规模并行计算机( m p p , m a s s i v e l yp a r a l l e p r o c e s s o r ) 多是此类模 式，如i b ms p 2 ，i n t e rp a r a g o n ，n c u b e ，c m 5 ，c r a yt 3 d ，曙光系列等。 从互联结构方式上，并行计算机可分为紧耦合和松耦合两类方式，早期的并行机常 采用紧耦合方式，即由多路开关连接多个微处理器构成，如列阵机、向量机等。而现在 多采用松耦合的方式，由多个高速的独立处理机通过高速专用网络互联形成大规模的 m p p 并行机。随着网络技术的发展和工作站、微机的普及，自然产生了一种更为灵活的 并行计算模式网络并行计算。 机群系统是利用高速通用网络将一组高性能工作站或高档p c 机，按某种结构连接 起来，并在并行程序设计以及可视化人机交互集成开发环境下，统一调度，协调处理， 实现高效并行处理的网络计算系统。从结构和结点的通信方式来看，机群系统属于分布 式存储器模式，主要利用消息传递方式实现计算结点之间的通信，由建立在一般操作系 统之上的并行编程环境完成系统的资源管理和相互协作，同时也屏蔽计算结点和网络的 异构性。构架计算机机群是实现网络并行计算的主要形式之一。 与传统的并行处理系统相比，机群系统具有如下特点： ( 1 ) 投资低、风险小：用户购置传统并行计算机很昂贵，总是担心使用和效率问题。 一旦不合适，等于浪费了大笔资金。而机群系统的投资相对少，不但可以用于进行网络 并行计算，还可以单机使用。 ( 2 ) 节约系统资源：由于机群系统的结构比较灵活，可以将不同体系结构、不同性能的 工作站连在一起，这样就可以充分利用现有设备。此外，平常计算机单机平均利用率仅 为1 0 左右，将这些单机结点组成机群系统，则可以有效地利用它们进行并行计算。 ( 3 ) 性能价格比高：由于工作站和p c 机是商业化产品，价格比较低。而十几台、几 十台工作站或p c 机组成的机群系统足可抵上售价几百万甚至几千万美元的巨型机或 m p p 系统的计算能力。 7 两安石油大学硕二e 学位论文 ( 4 ) 可扩展性好：从规模上说，机群系统大多采用通用网络，系统扩展容易；从性能 上说，对大多数中、租粒度的并行应用，机群系统具有较高的效率。 ( 5 ) 用户编程方便：机群用户无需学习新的并行编程语言( 如并行c 、并行c + + 、并 行f o r t r a n 等) ，只要利用所提供的并行程序设计环境，用常规c 、c + + 、j a v a 、c 群等编 程语言就能开发出可以在机群系统上运行的软件。 正是由于机群计算具有以上特点，随着网络技术和并行编程环境的发展，这一新的 计算模式成为当前研究的热点。 2 1 2 并行编程环境 2 1 2 1 消息传递编程环境 机群计算需要一个可移植的编程环境，基于消息传递的并行编程是机群环境中最常 见、最简单的编程模式。消息传递编程是一种显式编程，大多数系统要使用诸如s e n d 发送和r e c e i v e 接收函数来交换数据，可以说在一组互联的计算机上安装上消息传递编 程环境就已经形成了一个最简单的机群。最常见的消息传递并行编程环境有并行虚拟机 ( p v m ，p a r a l l e lv i r t u a lm a c h i n e ) 和消息传递接i ( m p i ，m e s s a g ep a s s i n gi n t e r f a c e ) 。 p v m 3 2 , 3 3 1 是美国国家基金会资助的开放软件，由美国o a kr i d g e 国家实验室开发， 后有e m o r y 大学、t e n n e s s e e 大学和卡内基梅隆大学等许多单位参与，经众多项目研究 者和爱好者努力，p v m 已经发布p v m i 0 、p v m 2 0 、p v m 3 0 、p v m 3 4 等多个版本。 p v m 模型：p v m 模型将应用程序看成组件集合，每个组件代表一个子算法，并表 现为多个事件，事件通过通讯和同步与其它事件协作，其并行单元是进程和任务。该模 型包括两类进程：监护进程和应用进程，提供了c 和f o r t r a n 7 7 的两类函数库，用户通 过这些库实现任务在网络上的并行处理。p v m 使用“宿主集”( h o s t p 0 0 1 ) 来表示虚拟机。 在虚拟机上，运行d a e m o n 进程，进程相互协作以仿真并行计算系统，应用程序向d a e m o n 进程申请并获得服务。 p v m 的特点：p v m 提供了一系列的子过程，包括向协作进程集注册或注销；在虚 拟机中加入或删除宿主机；启动和终止任务；同步发送信号等。p v m 提供了在任务执行 期间打包和发送信息的过程，其动态进程组建在基本p v m 进程之上。其工作模式是主 从模式，第一台启动p v m 的称为主机，其它由监护进程或用户启动的称为从机，它允 许同一个用户启动并使用网络上的同一p v m 服务。 p v m 的不足：首先，p v m 它过分依赖现有的网络与通信协议、通信开销大，缺乏 完整、高效的集束通信功能，使得数据移动操作过多，缺乏虚拟拓扑结构，不能充分利 用邻近通信，这些使得很多p v m 功能对用户不透明；其次，p v m 局限于对消息类型的 第二章n e t 平台与并行计算 管理，缺乏进程组的通信上下文机制、线程安全机制等，安全问题严重；再次，由用户 管理的消息缓冲区极易出错，动态进程组和虚拟机管理存在竞争现象。为了能正确使用 p v m 环境，用户需要有丰富的编程经验和技巧。 m p i 是为m i m d 模式分布式存储器并行计算机和机群系统制定的消息传递标准，目 标是为这类机器建立一个可移植的、易使用的标准消息传递环境。该标准的制定工作开 始于1 9 9 2 年4 月美国威廉斯堡举行的分布式存储器的消息传递环境会议，现在已经有 4 0 多个大学、科研机构和计算机公司等组织和6 0 多位专家参与m p i 的制定。m p i 提供 一个独立于平台的消息传递库标准，实现了程序的可移植性，支持p c 机、工作站和几 乎所有并行机，用m p i 编写的程序可不加修改地应用于所有操作系统平台。 m p i 的特点：基于m p i 的应用程序可从某种型号并行机上不做任何修改地转移到另 一型号的并行机上运行，m p i 是一个可移植的标准平台；m p i 提供了四种数据方式，分 别为标准方式、就绪方法、缓冲方式和同步方式，在m p i 中实现了点对点通信；m p i 还 具有集体通信、主动消息、并行i 0 、动态进程与进程控制等特点，这些特点使得m p i 并行库功能异常完善和强大。 m p 的不足：首先，m p i 的进程控制是相对静态的，它认为所有进程( 其并发单位 为进程) 都是预先静态初始化的，没有规定新开始一个并行应用的方法，尽管m p i 2 对 此进行了改进，增加了开始进程组的函数m p is p a w n ( ) 及组内进程间发送控制信号的函 数，但仍然不支持对于进程状态的动态查询；其次，由于m p i 旨在提供一个通用标准的 消息传递平台，并不直接实现资源管理，使其缺乏资源管理功能；再次，在m p i 1 中， 进程组和计算结点被认为是静态分配和初始化，在并行程序以进程组的方式运行时，一 个进程或计算结点失败，整个并行程序都将失败，虽然m p i 2 提供了动态进程和进程控 制机制，但仍未提供自动恢复机制，m p i 没有较好的容错功能。 作为两种主要的消息传递编程环境，m p i 和p v m 得到了广泛的使用。但是这两种 编程环境对负载平衡、容错和系统可扩展支持有限，而且随着面向对象技术的推广以及 各种新的软件开发环境的发布，开发人员将对象概念引入并行编程环境的研制，产生了 各种基于分布式对象技术的并行计算系统。 2 1 2 2 分布式对象技术 分布对象技术【3 l 】是伴随网络而发展起来的一种面向对象的技术。以前的计算机系统 多是单机系统，多个用户是通过联机终端来访问的，没有网络的概念。网络出现后，产 生了c l i e n t s e r v e r 的计算服务模式，多个客户端可以共享数据库服务器和打印服务器等 等。随着网络的更进一步发展，许多软件需要在不同厂家的网络产品、硬件平台、网络 协议异构环境下运行，应用的规模也从局域网发展到广域网。在这种情况下， c l i e n t s e r v e r 模式的局限性也就暴露出来了，于是中间件应运而生。中间件是位于操作 9 西安石油大学硕士学位论文 系统和应用软件之间的通用服务，它的丰要作用是用来屏蔽网络硬件平台的差异性和操 作系统与网络协议的异构性，使应用软件能够比较平滑地运行于不同平台上。同时中间 件在负载平衡、连接管理和调度方面起了很大的作用，使企业级应用的性能得到大幅提 升，满足了关键业务的需求。但是在这个阶段，客户端是请求服务的，服务器端是提供 服务的，它们的关系是不对称的。随着面向对象技术的进一步发展，出现了分布式对象 技术。可以这么说，分布式对象技术是随着网络和面向对象技术的发展而不断地完善起 来的。9 0 年代初c o r b a1 0 标准的颁布，揭开了分布式对象计算的序幕。 分布对象计算中，通常参与计算的计算体( 分布对象) 是对称的。分布对象往往又 被称为组件( c o m p o n e n t ) ，组件是一些独立的代码的封装体，在分布计算的环境下可 以是一个简单的对象，但大多数情况下是一组相关的对象复合体，提供一定的服务。分 布环境下，组件是一些灵敏的软件模块，它们可以位置透明、语言独立和平台独立地互 相发送消息，实现请求服务。 传统的面向对象技术有两个基本的特点：封装性和继承性，通常其强调的是代码复 用，对象往往仅存在于一个程序中，程序的外界并不可能感知和访问这些对象。而分布 式对象技术主要使用了面向对象技术的封装性，组件可以分布在网络的任何位置。对外 界来说，它所需关心的只是组件的界面，至于内部是如何实现的则无需考虑，远程客户 通过方法调用来访问它。这是分布式对象技术和传统的面向对象技术的最大的不同点。 此外，分布对象计算系统中都不支持跨站点的继承性，例如，假设对象1 是对象2 的一个特例，而2 个对象将要分布在不同站点上，如果完全按照面向对象的概念的话， 对象l 可以继承对象2 的代码和数据；但是在分布式环境下，对象l 要想继承对象2 的 代码和属性是非常困难的，没有任何一个分布系统能够支持这种继承性，因为实现代价 太大。 另外，在分布式对象里一般不提对象，而提组件。那么，组件和对象有什么区别呢? 在面向对象技术里可以有很小的一个对象，比如说一个邮政编码做一个对象；但在分布 对象计算中，往往会把一些小的相关的对象组合在一起，形成一个相对比较大的组件， 通过这个组件来提供一系列的服务。目前国际上，分布式对象技术有三大流派 一o b r a 、c o m d c o m 和j a v a 。c o r b a 技术是最早出现的，1 9 9 1 年o m g 颁布 了c o b r a1 0 标准，在当时来说做得非常漂亮；再有就是m i c r o s o r 的c o m 系列，从 最初的c o m 发展成现在的d c o m ，形成了m i c r o s o t t 一套分布式对象的计算平台；而 s u n 公司的j a v a 平台，在其最早推出的时候，只提供了远程的方法调用，在当时并不能 被称为分布式对象计算，只是属于网络计算里的一种，接着推出的j a v a b e a n ，也还不 足以和上述两大流派抗衡，而其目前的版本叫j 2 e e ，推出了e j b ，除了语言外还有组件 的标准以及组件之间协同工作通讯的框架。于是，也就形成了目前的三大流派。 应该说，这三者之中，c o b r a 标准是做的最漂亮的。c o b r a 标准主要分为3 个层 次：对象请求