基于MPI的并行程序设计

精品资料全集分享

维普资讯

第 l 6卷

20 0 6年 8月

第 8期

计算机技术与发展( MP SI R T C X) I ' E HNOL Y ND D VE OP NT E OG A E L ME

V1 6 No. o1 8.

Au . 2 0 g 0 6

基于 MP I的并行程序设计张翠莲，方爱，亚楠刘王(东师范大学信息管理学院，东济南 2 0 1 )山山 50 4摘要：绍消息传递接口标准 ( I和分析并行程序设计方法的基础上，出了在并行程序设计中需要进行算法级分在介 MP )提

析和程序级测试，以此来对影响具体的并行程序执行效率的因素进行分析，用实例验证了分析结果。最后对 MP的实并 I现之—— MPc{..版本的不足，出了改进的方法。 II12 5提

关键词：息传递；消通信； I并行程序 MP;中图分类号： P 1 . T 3 11 文献标识码： A文章编号：6 3 2 X 2 0 ) 8 0 7— 3 17—6 9 ( 0 6 0— 0 2 0

Pa a l lPr g a s g s d O lM PI r le o r m De i n Ba e i Z HANG i in, U a g a, ANG— a Cu—a LI F n -iW l Yan n

( ol e f nomai n gmetS adn om l nvr t,ia 5 0 4 C i ) C lg fr t nMa ae n,hn o gN r a U i sy J n2 0 1, hn e oI o ei n aA src:ntip prMPImesg asi trae snrd cdadp rll rga btatI s ae, h ( saepss gi efc)iit ue aal ormmi c ncs nlsd Thnp tow r— n n o n ep n t h iiaaye . e u r ada ge f p

pyn￣ n h aayi adpormmi t tof do t h atr f t gteseic rga A atmehd 'po lg a o tm ls n rga n e t i u te[c s f ci h pc iporm. tl, tosae rm￣ t m— i n s g s n o ae n f s l Oipo eted f in y o h rv h ei e c fteM PI c CH1 2. . 5. Ke wo d: sa ep si; o y l S mesg as

n c mmu iain; g ncto MPIp rl lpo rm; a al rg a e

0引言计算机技术极大地促进了计算科学的发展，与此同时科学计算对计算速度也提出了更强大的需求，如人类基例

群系统占到

0 o的 6 .%。并行计算机系统的出现 O8

就需要对程序进行并行设计，这种需求使得各种不同的并行编程环境得到了很大的发展。现行高性能计算机系统中使用的并行编程环境主要有两种：、 (a U iul P, Pr dVr a M a tMahn ) MP ( sa eP sig Itr c )。P M的 cie和 I Mesg as nef e J V n a

因、全球气候准确预报、海洋环流循环、核爆炸模拟等等， 没有万亿次以上的高性能计算机是无法解决的，这些问题使得计算机的性能亟待改善。但在实践中，由于受到物理器件极限速度和技术水平的限制，得单处理机远远满足使不了许多领域中的大规模计算课题对计算资源的需求。

开发始于 18年， 98由美国橡树岭国家试验室发起。目前

很多人采用 MP作为并行开发环境。 I

而多个处理器协同的求解问题极大地提高了计算速度，满足了大规模数据处理的需求。对并行处理的需求极大地促进了并行技术的发展，因此许多大规模并行计算机系统相继问世， P P Pr l et l e￥l并行向量处如 V (a ll c r x s" ae V o P￣ os,理机 ) S、 MP( y S mmer hpoesr/ h rd Me oy tc Mu ircs sS ae m r i o

1 MP简介 IMP是为开发基于消息传递模型的并行程序而制定 I的工业标准，目的是为了提高并行程序的可移植性和易其用性，用户必须显式地通过发送和接受消息来实现处理器之间的数据交换。为了开发一个高标准并具有可移植性

Poe￣r共享内存多处理机 ) MP Ma i l a Ul rc s s,、 P( sv y r e s eP a Poe o, r s r大规模并行处理机 ) D M( ir ue hr css、 S Ds b t S a d t i d e Me oy分布式共享存储多处理机)l m r, _等。但传统的并行 J系统的高成本性、专用性、系统规模的不可伸缩性等使其难以推广到普通的商业应用和科学计算中_。高性能集 2]群系统因其性能价格比高、高可复用性、

强可扩展性、 用户编程方便等优点在科学研究中得到了广泛的应用。在

的消息传递库，由厂商 ( IM,ne等)软件开发商如 B It l、(aa f K I等 )研究中心 ( N, MP等 ) Pr o, A st、 A LG和大学 ( ni u h Ma l d等) E d br, r a n g yn共同于 19 92年成立了 MP论 I坛L。经过共同研究和使用， I 4 J MP论坛先后于 19 94年和19年后提出了 MP一1 MP一 _。MP具有移植 97 I和 I 25 J I

性好、功能强大、效率高等多种优点，而且有多种不同的免费、高效、实用的实现版本，几乎所有的并行计算机厂商都提供对它的支持，这是其它并行环境所无法比拟的 MP 1只是一个并行编程语言标准，编写基于 M P的并行程要 I

20年 6 05月刚刚发布的全球高性能计算 T P 0 O 50中，集收稿日期：0 5 1 3 20—1—1

作者简介：张翠莲 (9 0一)女， 18,山东泰安人，士研究生，硕研究方向为并行算法、图像恢复；刘方爱，教授，博导，研究方向为并行处理、并行计算模型和互联网络。

序，还必须借助 MP的某种具体实现。MPC I IH是最重要的一种 MP实现，一个与 MP规范同步发展的版本。 I是 I 每当 MP推出新的版本时， I就会有相应的 MPC的实现 IH

精品资料全集分享

维普资讯

第8期

张翠莲等：基于 MP的并行程序设计 I

7 3

版本，目前常用的版本是 m i一126在 Wi o s的 p h . ., c n w下 d一

递。一个基本的 MP程序的流程图如图 2 I所示。

个常见版本是 mp hn. ..,中的所有实验均采用 i .t12 5文 c

此版本作为实验环境。C I H MP是 E i u h开发的另一 d br n g个免费 MP实现，在 E￣ ( d b g aal o u— I是 P E i u hP rl l mp t nr eC

臣固— —————— .————

I————一—

.

I塑 堡+ +

堡 J

i et ) n C nr的支持下进行的。L M( a A e ic g e A kcl r Mu i m— a top tr是 Ln x平台下另一个免费的 MP实现。它由 O一 ue) iu I

匾巫亘亟[面而图 2 M

P程序设计流程图 I

}州立大学开发， i r o主要用于异构的网格计算并行系统。

2基于 MP的程序设计方法 I并行程序设计可以通过多种方法实现，它们各有特点，适合于不同的场合。最常用的是共享变量方法和消并

设计并行程序的目的是为了提高算法的效率，尽可能地减少时间复杂性。但并不是所有的算法都能在并行机上并行运算，而且能在并行机上并行运算的算法并不一定都能达到加速的目的，以分析并行算法效率，于并行所对程序设计具有重要的指导意义。在将一个并行算法写成并行程序之前，行算法级的分析，在并行程序运行先进再

息传递方法。共享变量方法的主要特点是利用共享存储器中共享变量来实现处理机间的通信，它主要用在共享存储结构中。消息传递方法的主要特点是不同处理机间必须通过网络传送消息来相互通信，并达到任务间需要的同 步操作，它主要应用于分布式存储结构中。MP是基于 I消息传递模型的，在这种模型中，把任务分成若干部分(进程)让每个处理器(,节点 )自运行不同或者相同的部分独 (进程)。驻留在不同处理器(节点)上的进程可以通过网 络传递消息来互相通信，从而达到并行计算的效果，减少计算的时间，其执行过程如图 1所示。其中进程的分配、 结果的收集均通过消息传递来完成。在 MP中， I通过指定通信因子和组来对进程进行一种逻辑上的划分，通讯因子定义了进程组内或组间通讯的上下文。

的过程中进行程序静态测试和程序动态测试，及时地修改

调整程序，使其能更高效地执行。算法级的分析主要是对时间复杂度的分析。在消息传递系统中，整个的执行时间由两部分组成，即计算时间和通信时间。可用下式表示：T=￡+￡, T㈣ p衄坤㈣而： + da m

其中 t r为启动时间，含在源进程处将消息打包以及 mt￣包

在目的进程处将消息解包所需要的时间；砒表示发送一 a d个数据字所需的传送时间。程序级的调试主要是包含对并行程序任务的分配、数据的划分方法、消息的大小、负载的均衡等方面。于同一个应用程序、同的数据划分方法，对不 在时间复杂度相同的情况下，运行时间可能是不同的；对于不同的应用程序，在其他条件相同的情况下，要传递

的

消息的大小对整个的通信时间有着很大的影响。对于集群而言，负载的均衡也是影响并行效率的关键因素之一。

3并行程序测试3 1测试环境 .图 1消息传递模型的执行过程

硬件环境是由 3台计算机组成的集群，置均为配 C U: t etml,3MH, P I dPni a I73 z内存 12;点机操作 n t I 9MB节系统为 Wi o s 00Poe i a和 Wi o s P网络类 n w 0 r so l d 2 f sn n w; d X

消息传递的多处理机编程可以通过下面的方法实现：() 1设计全新的并行编程模型；

() 2扩展现有串行高级编程语言的语法和保留字来实现消息传递； () 3使用现有的高级串行编程语言并提供消息传递的扩展链接库。MP是运用方法 ( )实现的。采用 MP构建一个 I 3来 I并行计算环境主要用到 6个函数。这些函数的函数名为I nt—I i, I o—C mm—Sie z, I o—C mm—Ra k, n I—

型： 0 p以太网； 1 Mbs 0消息传递系统： IH一12 5 m; MPC . .网络协议： P;代 编程语言： i aC++60 Vs l u 。

确保集群上的每台节点机都安装 m i .t125并 p hn.., c以相同的用户名和密码(要求密码不为空)进行注册，然后对主控计算机进行配置。并对 V U +进行相应的 sl i a C+

设置，使其能与 MPC整合，行程序的执行利用了 IH并m i .t12 5的图形化的应用程序 g k Im。 p hn. .. c u MPn3 2测试及相关分析 .

S n, I Rev e d— c,

I Fn le— iaz。 i

I Ii— nt和

I i—F—

nle az实现 MP环境的初始化和结束。 i I

I C MM—— O

测试实例之一使用并行方式计算，函数， z 令 ( ):rl

WO L R D通信因子是在 MP环境初始化过程中创建的。 IMP— o I C mm— S获取缺省组 ( o p Gru )的大小； I MP—

4 (+z )则 l ( )x= 7求解思想是在微小间隔内/1 , x d f【,0

用求和运算近似积分运算，这种方法本身具有很好的可并行性。设值为将[,]区间所分的间隔数， 01并行时间复杂度为 O(,比串行

程序的数量级要小， )但并且消息的

Cm o m—R n ak获取本进程【用进程]调在缺省组中的逻辑号 ( 0开始 ) MP— ed和 MP— ev现消息的传从； I Sn I Rc实

精品资料全集分享

维普资讯

7 4

计算机技术与发展fri o i ihi o(=l<h;++) yeu+=dt[; w; g mr l s t aa i]pi f“ o%df m%d” mye tmy ) rt I t o n( g r\n, rs, i; l u d

第 l卷 6

传递只涉及 n以及各个处理机计算得到的部分和，通信开销比较小，适合并行化。程序中数据的划分依据是每个进程的进程号，以将连续的数据块分配给某个进程，可或者按照某种规律 (例如所有分配给同一进程的数据为首项不

MP— eue&myeu, e l 1 MP—IT, I S M,, IR dc ( rs t&r u,, I N MP— U 0 l stMP— DMM— IC WOR D) L;

同的等差数列)进行分配。程序运行过程中对数据划分方式的改变使得程序的运行效率及结果的精确性有所变化。 实验结果表明后者的分配方法使得程序的效率高于前者。 以下实验结果均采取第二种数据划分方法。 1表给出了在不同数量的处理机下的实验结果，程序的加速比接近最本

i my==O ed ie f i ( d ){ nwt=MP— u e) m I Wtn (;p n (T eSm%d; s t; r t h I i if L s n Je ) ru l

p n (w lc c 1=%f’ec i— t t t )} r t“ a okt e if ll m .\, L me s r i; nwt a w meMP— n le ) I a z(; i

}

大加速比，并行效率较高、通信量较小，其中每个节点的计算能力是影响算法的主要因素。为加快算法的执行效率，可采用主频较高的处理器或者减少节点的工作负载。表 1第二种数据划分方法的实验结果 n=1o o 0 00 0 O处理机台数3 2

在相同的条件下，程序运行结果如表 2从表中可以，看到从运行时间和结果的精确性来说，单机均优于多机。 本程序的通信量较大，为减少通信量，可采用多种方法： ①对每个节点机，仅传递其计算所需的数据；②采用高速网络，减少消息延时

; ③使用 S (hr m r r e i ) MP S a dMe oy o sn机群，分利 e P csg充

测量值与实际值的误差 (真实值取前 2位 ) 50 0 00 0 0 0 1 5 .0 0 0 0 0 0 15 0 0 00 0 0 0 1 1 .0 0 0 0 0 0 9 8

运行时问() s0. 5 2 0 5 6 2 0. 3 8 5 8 1O

加速比292 .4 19 7 .6

用节点内固有的高速通信。表 2若干个数据求和运算结果

1

000006 .00002 000002

133\ .63 64

处理机台数3 2 1

运行时间() s0. 3 21 01 2 0. 9 1 01 3 1 0.o2 7 0 86

求和结果1( o 0) 2 0 1 o O1 Oo 1( o 0) o O

测试实例之二是将一个文件中的若干个数据相加，保存数据的文件是一个记事本文件，放在各个节点的硬盘存

上，处理机个数为 nmp c。设总共有 n个数据( u rs o本程序中取 n= 100 )程序代码如下所示。 00 0,本程序中涉及两次消息传递操作，根进程将 n个数据广播给所有进程，各进程将部分计算结果汇集给根进程，总的通信时间为：故T∞Ⅱ= ( s￣+ d )+( s￣+￡a)Ⅱ的 tm a t仂| tm t d 植

4结

论

MP提供了良好的并行程序接口， I通过调用 MP的 I库程序，可以达到并行化程序的目的，但并行程序的设计相对于串行程序的设计来说要复杂得多，文中提出了影响并行程序设计的诸多因素，并通过实例来演示了可以通过算法级测试和程序级测试来及时调整具体的应用程序。 文中使用的 MPC IH为并行程序的实现提供了并行环境， 并且可以根据具体应用程序的不同来选择处理机，基本达到了测试并行程序的目的。但它是先进行单纯的后台计算，然后给用户输出一组时间数据，即求解同一个问题使用单个到多个处理器的时间值。用户必须比较时间值并额外计算加速比、并行效率，才可以对并行程序进行评价， 这种方式，只是提供给用户几个呆板的数据，具体的分析还得靠用户去做，并且不能让用户深刻地体会到并行的理念和优越性。如果将衡量并行程序性能的指标集成到此软件中，并且让后台在进行并行计算的同时，前台能同步

总的计算时间包括各个进程并行计算部分和的时间

以及一次根进程对部分和求和的时间：￡呷= ( n mpo s )哪 ∞岫l n/ u r￣+1￡

故 T= 2蛐仰+ (+ 1￡恤+ (/u pos+ p￡竹 )d a n nm r c1￡ )一

从分析来看，本程序中通信时间在总的执行时间中占 了主导地位，对通信延迟比较大的工作站网络来说，多机处理的效率未必优于单机。vi n ( t r, a a v] o￣n m g c r* r[ ) d ac h g{ r ls r t,nw i;s em ir & b at i ed t it a sm; u e t w me me fr t

i i,u posit a MA Sz] n my nm rc; 协[ X IE; t d nditix l lg, r s t n,,o 1 h mye u=0,eut w, i l rs; l

MP— n ( ro&a ) I Ii&a, ; t g MP— o m—i ( ! ( )— R D, u g t ) I C m s e MP一X MM WO L&n n g z￣; MP— o I C mm— ak MP一 DMM— R D, r ( !C n WO L&my ) i; d i m i==O f y ( d )

地以生动的图像(例如进度条 )演示各处理机计算的情来况，则既可以向用户演示并行程序执行效率的情况，又可以生动地演示各处理机的使用情况。总之，并行程序设计涉及到诸多方面的技术，只依靠某一种方法或某一个软件工具是难以设计出高质量的程序的，需要用多种方法，研究多种软件工具有机地协调应用。参考文献：[]曾庆华，麟 . 1陈天可扩展并行计算机系统结构和发展现状

{t oe (B.a”; ir pn“ dt) s m.fri ; o( t=O i ni<M;++) i

ir>dt i; sm> a[] t air c s(; s m.le )} t oMP一] 3 d t, X I E MP—I T,0 MP—C MM— I￣a a a MA S Z, I N t(, I O WO L ) R D; s r i=MP— i (; t t me a wt I Wt ) mex=MAXS Z n mp o s l=myd*x h= l+x I E/ u r c; w a i; h o w;

(下转第 7 6页)

精品资料全集分享

维普资讯

7 6

计算机技术与发展

第 1 6卷

口，>,< b,>,< b, e b c>,< b, e>, c,< c>, c,<

故两种

定义在实质上是等价的。应用文中所给的等价定义可以很快地判定前面例 2 的盖住集。

e>, d,< d>, d,, e e>}试判定 R上的盖< e><,,

住集 O v。 O R

该例中所给的二元关系是以序对集合的形式给出的，两个元素之间的关系不明显，接根据上述定义不好判定直该偏序关系的盖住集 () R XV。

例 3设集合 A:{,,, e, a b cd,}R是A上的偏序关系。 R={口，<口>,口 b>,<口，<, c>,口，>,< d< a, e>,< b,>, b, b< c>, b,< e>, c,>,<< c

2偏序关系中“盖住”的等价定义及应用通过对上述定义的分析，出以下的等价定义。给 定义’于任意< a b>∈ R且 a= b则<口 b对，,,>∈, Rl R—, R1 R1 令= 则一( OR1为盖住集。 ) 文中所给的等价定义是立足于集合的观点，应用此等

c e>, d,,< d>, d,>, e g}试判定 R上的< e<,>,盖住集 O v 0 R。解：={口， <口>,< b, b>, c c>,< d, <, d>,< e e>}, R1= R— ={口，< b>,口，< c>,<口，>, d< a, e>,< b, c>, b e>, c e>, d,<,<,< e>}

价定义判定偏序关系的盖住集，不仅有条理，而且步骤清晰。可从以下几步求盖住集：

R1 oR1={口，< c>,<口， e>,< b e>}, ()= R1 R1 R1 X VR一( o )={口，< b>,<口，>, d< b c>,< c e>,< d,,, e>}

() 1首先从 R中找出所有 n= b的序对集合。 () 2计算集合 R和的差R1即 R1,=R—。 () R1 3将与其自身复合，得集合 R2。 () 4计算集合 R1 R的差， R1 2和 2则一R为盖住集。因此，实际用于偏序关系的盖住集的判定，不仅效率高，而且准确。 下面证明文中所给的等价定义与现有教材中的定义是等价的。现有教材中的定义的前提条件分为前提 1将和前提 2:

3结束语文中通过对教材中偏序关系中“盖住”义的深入分定析，将定义“对于任意 a b∈ A,<口 b>∈ R,,当，口≠ b

且没有其它元素 c满足<口 c>∈R和< f b>∈ R,,,则称元素 b盖住元素口并且记，:{口 b> I,<, b n∈ A;盖住口” b l改为“于任意< n b>∈ R且 n= b对，,

前提 1对于任意 n b∈ A,< n b:,当，>∈ R,≠ b n;前提 2且没有其它元素 c足<口 c:满，>∈ R和< c,b>∈ R。

则< n b>∈ I, R1,尺令：R—, R1 R1 则一( oR1为 )盖住集”得出一种等价的定义形式。文中所给的等价定，义是立足于集合的观点，此等价定义判定偏序关系的应用盖住集，不仅有条理，而且步骤清晰。参考文献：[]左孝凌，为鉴， 1李刘永才 .离散数学[ .海：海科学技 M]上上术文献出版社，92 18 .

对于前提 1实际上排除了 R中所有a= b的序对，而在文中所给的等价定义中“于任意<口 b∈R且口：对，>

b财<口 b>∈, R1,, 令：R一/”也排除了 R中所 R,有口=b的序对。 R即 1:{口 b>J口 b>∈ R A<,<, 1 ( a,< b>∈ )。 }

前提 2实际上是在满足了前提 1的基础上，排除所再有满足“在其它元素 c足<口 c存满，>∈ R和< c b∈,>

[] K la,ub 2 o nB B syRC R s SC DsrtMa e taSrc m,os . i e c e t mail t— h c u tr (or di )M] B i g H hr d ctnPes ue F ut i n[ . ei:￣ e E uao rs, s hE t o i n i2 01. 0

R”<口 b>序对，的， R中剩下的序对集合即为盖住集。 而在文中所给的等价定义中提出 R1 R1一( oR1为 )盖住集，满足了前提 1条件， 1 R1的 R oR1运算的结果正

[]何光明，海艳 .散数学学练考[]北京：华大学出 3王离 M .清版社，0 4 20 .

是所有满足“存在其它元素 c满足<口 c>∈R和< c,, b>∈R”<口 b>序对集合。的，而R1 R oR1排除一( 1 )了所有满足“存在其它元素 c满足<口 c>∈R和< c,, b>∈ R”<口 b>序对。的，(上接第 7 4页)[]计算机科学，033 ( )18 6 . J. 20,0 9:5

—11 【]何敬鹏， 2周容，新 .个小型集群系统的建立和初步俞建一

[]杨思春，云霞 .元关系反对称性的判定[]微机发展， 4周二 J.2 0,4 3 .3 4 0 4 1 ( )9—9,

[]杨思春，小林 .二元关系传递性研究[]微机发展， 5王 j.2 0,3 1 )8—8, 0 3 1 ( 0:8 9

s nadJ .a ll o pt g 19,2 6:8—88 t dr[]Pr l m ui,962 ()79 2 . a aeC n

[]王萃寒， 4赵[]张岳， 5陈

晨，许小刚，分布式并行计算环境： I等. MP渝，亦嘉， . I计结构的分析和比较孙等 MP设

应用[]计算机应用研究，0 4 1:2— 3 . J. 20 ()27 2 0[] G opW, kE D) e a A ih efmac P- 3 r , CsN,t 1 h—pr r ne c p 8 . g o ra【 I l mrt no h IMes g—p sig I dae t be mpe me a i ft eN sa e as me c o n

[]计算机科学，033 ()2— 6 J. 20,01:5 2 . []计算机科学，04 3 ()13 6 . J. 20,12:6—16

本文来源：https://www.bwwdw.com/article/lg8j.html