（计算机软件与理论专业论文）基于mpi的并行算法的研究.pdf

基于m p i 的并行算法的研究摘要并行处理技术近年来已成为计算机界研究的一个热点。采用并行处理技术来解决大数据量或时间复杂度高的问题不仅在计算机界，而且在其它科学领域都是首选的。而算法是并行处理技术的核心，所以研究并行算法是非常有意义的。本文以搭建基于m p i 的并行集群环境为基础，利用“体系结构设计算法一编程实现”的设计思路，j对并行计算机的体系结构和并行算法的理论基础以及m p i 并行程序的设计实现进行了逐一的阐述，最后以最短路径程序为例，重点研究了并行算法的理论以及并行算法设计过程中存在的一些问题，取得了一些有价值的研究成果。首先，简要阐述了并行计算机的分类和m p i 并行程序设计的基本理论，接下来研究利用现有的计算机资源，搭建小型的p c 集群系统，建立基于l i n u x 和m p i 的并行实验环境。其次，介绍了有关并行算法的理论的概念和对并行算法进行评价的指标，讨论了集群环境下并行算法的设计问题。并对本文中用到的编程模型进行重点阐述，对并行算法的评价指标进行了规定。然后，用最短路径的并行算法作为实验用例，深入研究了并行算法设计过程的一些问题，并把设计好的并行快速排序程序应用于最短路径算法。最后，构建现有的闲置计算机集群并行计算平台，对并行算法的性能进行了测试，给出了测试结果，并对结果进行了分析。实验结果表明，本文所设计的并行算法能达到一定的效果，对以后并行平台的搭建和并行算法的设计方面有一定的意义。关键词：并行处理技术；并行算法；最短路径；m p i ；集群r e s e a r c ho np a r a l l e la l g o r i t h mb a s e do nm p la b s t r a c tp a r a l l e lp r o c e s s i n gt e c h n o l o g yi so n eo ft h ei m p o r t a n tb r a n c h e si nc o m p u t e rs c i e n c e u s i n gp a r a l l e lp r o c e s s i n gt e c h n o l o g yt of e s o l v el a r g ea m o u n to f d a t ap r o b l e mo rt f i g l lt i m ec o m p l e x i t yp r o b l e mi st h ef i r s tc h o i c ei no t h e rs c i e n t i f i cf i e l d s ，a sw e l la si nt h ec o m p u t e rf i e l d a l g o r i t h mi st h ec o r eo fp a r a l l e lp r o c e s s i n gt e c h n o l o g y , s or e s e a r c h0 1 1p a r a l l e la l g o r i t h mi sm e a n i n g f u l i nt h i sp a p e r , ap a r a l l e le n v i r o n m e n t - c l u s t e rw i i sb u i l t ，w h i c hi sb a s e do nm p ! w i t ht h ed e s i g ni d e a so f ”a r c k i t e e t u r e a l g o r i t h md e s i g n - p r o g r a m m i n g ，- t h ea r c h i t e e t n r eo fp n r a l l e lc o m p u t e ra n dt h et h e o r e t i c a lb a s i so fp a r a l l e la l g o r i t h m s 舔w e l la st h ed e s i g na l i di m p l e m e n t a t i o no fm p ip a r a l l e lp r 0 黟卸晴w e 他e l a b o r a t e do n eb yo n e f i n a l l yt h es h o r t e s tp a t hp r o g r a mw i l l st a k e nf o r 髓鲫p l e , 田证t h ep a p e rf o c u s e s 衄t h e肿妇l l se x i s t i n gi nt h et h r i e so fp a r a l l e la l 鲫蛔s 铽破t h ed e s i g n 谤嘲跫鼹o fp a r a l l e la l g o r i t h m s ，a tl a s ts o n i cw l u a b l er e s e a r c hr e s u l t sw e f em a d ei nt h i sp a p e r f i r s t ，ab r i e fd e s e r i p t i o r lo ft h ec l a s s i f i c a t i o n 西p a r a l l e le o r n l p u t e r sa n d 恤b a s i ct h e o r yo fm p t p a r a l l e l o g r a m m i n gw a f ts h o w n , 蜘溅gt h ee x i s t i n ge o r r r p u l e l tl 骼o l l r c e s ，as m a l lp cd u s t e rs y s t e mw l l s + b u i l t r , i n l l i l yai p a l a l l o le x p e r i m o n t a te n v i 霉同毗越w 私e s t a b l i s h e d 、施c hw a l 5b a s e d1 3 1 1m p ia n dl i n u xo p e r a t i n gs y s t e m s o e o n 最i nt l l i sp a p e r , t h ec o n c e p to ft h e 。t h e o r yo fp a r a l l e la l g o 珊l i l l sa n dke v a t e a t i o n ，i n d i c a t o r so f p 搬l l e | a l g o r i t h m sw e 娼i n t r o d u c e d t h e l l 储圮d e s i g np r o b l e m so fp a r a u e la l g o r i t l u mb a s e do r le l u a t e r e de n v i r o n m e n tw e 把d i s 圮m s e d t h i sp a p e rf o e u a e s0 1 f ip a r a l l e lp m 萨狮m l i n gm o d e l s w e na n ds t i p u l a t e st h ee v a l u a t i o ni n d i c a t o r s 乐o rt 3 a r a l l da l g o r i t h m t h e n ，嘴i n gt h es l l o r t e s tp a t ha l g o r i t h ma sp a r a l l e le x p e r i m e n t a lc a s e s , s o m eo ft h ep r o b l e m sd u r i n gt h ep a r a l l e la l g o r i t h md e s i g np r o c e s s 啷s t u d i e dd e e p l 弼a n dag o o c lp a r a l l e lq u i c ks o r tp r o g r a mw h i c hh a db e e nd e s i g n e db e f o r ew a sa p p l i e dt ot h es h o r t e s tp a t ha l g o r i t h m f i n a l l y , u s i n gt h ee x i s t i n gi d l ec o m p u t e rc l u s t e r , ap a r a l l e lc o m p u t i n gp l a t f o r mw a sb u i l t t h ep e r f o r m a n c eo ft h ep a r a l l e la l g o r i t h mw a st e s t e d ，a n dt h et e s tr e s u l t sw e r eg i v e n ，i ia n dt h er e s u l t sw e r ea n a l y z e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep a r a l l e la l g o r i t h md e s i g n e di n t h i sp a p e ra c h i e v e sc e r t a i ne f f e c t s ，a n dh a sc e r t a i ns i g n i f i c a n c eo nb u l i d i n gp a r a l l e lp l a t f o r ma n dd e s i g no fp a r a l l e la l g o r i t h m ss t r u c t u r e s k e yw o r d s ：p a r a l l e lp r o c e s s i n gt e c h n o l o g y ；p a r a l l e la l g o r i t h m ：s h o r t e s tp a t h ；m p i ；c l u s t e ri i i浙江师范大学学位论文独创性声明奉人矗f 聊；f 孵2 f | 勺烈毫绝文楚我个人磊：谚锄j 措：， 、进j i 的毋；甓i 拍；及驭舒豹别 充域袋。论文t t 除r 特剐加强勃。i i - ；秘j 敛溺约地筇夕 ，誉包禽j 能人戒j 纯现葶0 纷发表或援7 ，；过的影；究成粟，i 0 童阳志甜夺研先j ；：弱珏车l 敞f ! 勺：融j 钒：劳论；c ： ， ? 丁明确声明；i ：表求了巍惫。本人：危令怠淡磐本一：i ! i j 的澎幸社 裂l 和长久承担。作暂龇孤学生期：揶年”；学位论文使用授权声明本入完全了解浙姐：师范久学钉笑傈留、绽辩j 学佗沦文的娥定，印：学校彳f 投住沿井向因客商笑机关歧机构送交沦文的复印件和f 耗f 文档，允硼：论文被套阅瑚l嵇隧，i j _ 以采刖影印、缩印绒童l 籀铬手段保存、乳。编。掌位沦文。同意浙江师范大学叮以用不网方式在不b d 媒体 ：发表、传播沦交的仝溜或部分内缚，保密的学位论义礁i 孵密籍遵守诧协议。似抒够名：多次群尘、锄隧名：獭锨t ：卅绀，玎f t ；5 2浙、江师范大学学位论文诚信承诺书我承诺自觉遵守 、平方阶o ( 刀 2 、立方阶o o 3 ) 、k 次方阶o ( 强 妨、指数阶o ( 2 刀) 。3 2 2 3 并行瘼算法的并行度p 咄o f p a r a l l e l i s m ，- d o p ) 是指该算法中可并行执行的操作数。若处理机资源无限，则算法的并行度也可以理解为可以利用来作并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程中保持并行度不变，所以更准确的说法还应该加上时问范围的限制，即在某时间范围内的并行度。从直观意义上可以说，并行度是刻画一个并行算法的“并行程度- 的量，它反映了软件并行性与硬件并行性匹配的程度。显然，与算法并行度有关的概念是粒度，一般而言，大豹粒度意味着能独立并行执行韵是大任务，算法的并行度小，小韵粒度意味着能独立并行执行的是小任务，算法的并行度大。并行算法的平均并行度可以这样定义：假设并行算法可以在牌个并行步内完成，第，步时算法的并行度为d o p ( i ) ，则算法的平均并行度为：2 l3 并行算法理论基础3 2 2 4 加速比和效率彳= 上主dop ( i )m 乞( 3 1 )最后可以用加速比和并行算法的效率来评价并行算法。其中并行算法的加速比可以定义为：s p = v 石- p( 3 2 )范围不一定在n n ( o ，1 ) 之间；式中，乃为最优串行算法在单处理机上的运行时间；乃为并行算法使用p 台处理机的计算时间。并行算法的效率为：廓= 詈( 3 3 )式中，p 为处理机台数。如果按照某种条件，如保持每台处理机的计算规模，并行算法加速比昂与处理机的台数p 成正比，则称该并行算法在该条件下，在该并行机上具有线性加速比。在某些条件下，若s p p ，则称该条件下，该算法具有超线性加速比。加速比和效率是最传统的并行算法评价标准，它们体现了在并行机上运用并行算法求解实际问题所能获得的好处。3 2 2 5 并行算法的可扩展性分析可扩展性是设计高性能并行机和并行算法所追求的一个重要目标。它可分为资源可扩展性、应用可扩展性和技术可扩展性三种。由于本文的主要研究对象之一是并行算法，为此本节主要对其中的应用可扩展性，也即并行算法的可扩展性进行讨论。并行算法的可扩展性【4 1 】是对并行算法有效利用增加的处理机数目能力的一种度量，与算法设计内在并行性和通信需求有关。1 9 9 3 年，a y g r a m a ，等提出了度量并行算法可扩展性的恒等效率方法 4 2 - 4 3 1 。假设某并行算法在由p 台同构处理机组成的并行机上的执行时间为乃，它对应的最优串行算法的执行时间为乃，则根据并行算法的效率公式有：3 并行算法理论基础廓丑p = 南= 焘r o = 南i + t o 4 ，乃尸五十正v 一7其中乃为并行算法在尸台处理机上执行时的通信、同步等时间开销。显然，式中的乃是问题规模”的增函数。对固定问题规模，随着处理机数尸的增加，乃不变，乃将增加，因此根据( 3 4 ) 式可知算法的效率将下降；对固定的处理机数p ，随着问题规模的增大，乃、乃都将增大，但乃由于增加的速度小于乃，因此算法的效率将增大。结合这两种情况可知，对某些并行算法而言，在p 增加的情况下，只要适当地增加问题规模，可以保持算法的效率不变，此即并行算法可扩展性的恒等效率度量方法。由于并行算法的通信开销乃的增长速率因体系结构而异，因此这里所说的并行算法的可扩展性指的是基于给定体系结构的并行算法的可扩展性，也即并行算法体系结构组合的可扩展性。进一步根据式( 3 4 ) 可知，为保持效率固定，乃必须正比于。换言之，下列等式应被满足互= f r o( 3 5 由于乃、乃为，私刀的函数，因此由式( 3 5 ) 可推得乃用户表示的函数式石= e ( 尸) ，即为并行算法对于效率占的恒等效率函数。若后何为p 韵线性函数，则称该并行算法是强可扩展的。并行算法的加速比可以抽取一些并行计算问题的规模特征，形成固定的加速比模型，比如a m d a h l 加速比模型湖；可变问题规模的加速比模型，比如g u s t a f s o n 加速比模型1 4 5 1 等。这里对加速比模型就不加详述。除了上面的这些评价指标之外，还可以用并行算法的可扩展性 4 1 1 来对并行算法进行评价。它可分为资源可扩展性、应用可扩展性和技术可扩展性三种。由于本文的主要研究对象之一是并行算法，为此本文主要在实验中对并行算法的应用可扩展性进行了分析。3 3 本章小结本章在对并行算法的理论基础进行了阐述，根据不同的方法可以将并行算法划分成不同的类别，并行算法一般来说通过三种途径进行设计，并行计算模型是对各种并3 并行算法理论基础行机( 至少是某一类并行机) 的基本特征的一种抽取，它使得设计的并行算法具有更强的生命力。在众多并行计算模型( 如p r a m 、c 3 等) 中，l o g p 模型是适用于分布式系统的。常用的评价并行算法性能的指标有加速比、效率、可扩展性等。其中加速比定义为最优串行算法的执行时间与p 台处理机并行执行时间的比值，效率定义为加速比与p 的比值，度量算法可扩展性的恒等效率函数定义为五= 厂e ( n 。通常情况下并行算法的设计追求高加速比、效率和强可扩展性。a m d a h l 加速比模型与g u s t a f s o n 加速比模型分别是固定问题规模和可变问题规模的并行加速比模型。2 44m pl 并行程序设计m p i 是消息传递界面( m e s s a g ep a s s i n gi n t e r f a c e ) 【2 5 3 3 。4 】的简称，它和另外一种并行编程环境p v m 一样，都提供了一组可用于消息传递的通信原语。由于本文并无在基于p v m 韵环境下搭建并行平台，就不对i v m 进行研究和描述。4 1 舯i 发展及特点m p i 是为了统一不同的m p p 厂家的消息传递a p t 而被开发出来的一个广泛用于编写消息传递程序的标准。m p i 的研究和发布过程如下：m p i 标准的初稿在1 9 9 2 年4 月的美国并行计算中心工作会议上被提出：4 9 9 3 年1 月m p i - i 在第一届m l 大会上被公布：1 9 9 4 年5 月m p i 标准被正式公布；t 9 9 5 年6 月非官方组织郴i 论坛推出新版本m p i - 1 1 ；1 9 9 7 年7 月非官方组织- - m p i 论坛推出了m | 2 。在推出m p i 2 之后，1 9 9 7 年7 月之前的原来m p i 的各种版本称为m p i - 1 现在最新的版本是2 0 0 9 年非官方组织- m p l 论发布的m p i - 2 2 。m 斑是在利用以前成熟和先进技术的基础上发展起来的标准，相对予日前广泛使甩的p v m l 2 s , 嬲2 1 ，除了具有p v m 的大部分优点，还具有以下特点：m p i 的实现方式有很多种，并且适合予多种开发工具和基础的开发语言：m p i 能有效地管理消息缓存区；m p i 能在多种并行计算机体系结构上有效运行；7m p i 能实现完全的异步通信，发送与接收完全能与计算重叠进行，m p i 异步执行时对使用者的其它软件不会造成影响：m p i 是完全可移植的标准平台。4 m p i 并行程序设计实际上，无论是p v m 还是m p i ，它们都提供了一组函数，通过这些函数的调用，子任务可加载到多个节点机上，并且节点机之间可进行消息的传递与接收，协同完成计算任务。鉴于m p i 的种种优越性，本文我们将使用m p i 这个并行计算环境进行实验。4 2m pi 的新特性m p i - 2 是对m p i 1 新的发展，主要有三大新特性：并行i o 、远程内存访问和动态进程管理，这三个领域是对m p i 1 所定义的严格的消息传递模型的扩展。此外m p i 一2 还引进了一些新包括外部接口的定义，c h 和f o r t r a n9 0 联编，对线程的支持和多种语言的编程等新特性，使得m p i 更加健壮和便于使用。m p i 2 中的并行i o 部分，又称为m p i i o ，它的产生是独立于论坛的，最先是m m 在模拟输入输出和消息传递时提出的。如果把向一个文件中写数据模拟成向一个文件系统发送消息，从一个文件中读数据可以模拟成从该文件接收消息，那么并行i o 需要使用聚合( c o l l e c t i v e ) 操作和非阻塞操作。换言之，并行i o 需要一些在m p i 中己经定义好且有实现方法的支持。m p i 2 中的i o 与u n i x 申的i o 有些相似，包括一些基本的操作，如打开( o p e n ) ，关闭( c l o s e ) ，定位( s e e k ) ，读( r e a d ) 和写( w r i t e ) 等操作。在m p i 中使用并行i o 的目的是获得更高的性能。4 2 1 单边通信单边通信是m p i - 2 版本的新增功能，因其执行过程中只需要一个进程的参与，所以由此得名。在远程内存访问r m a ( r e m o t em e m o r ya c c e s s ) 功能的支持下单边通信得以实现。远程内存访问是指一个进程通过读( g e t ) 、写口u t ) 和累计( a c c u m u l a t e ) 等操作直接读写另一个进程的内存数据单元，也就是直接对非本地的存储空间进行访问。它能够提供m p i 环境共享内存模型的元素。除了最基本的窗口操作外，还提供了窗口管理功能，用来实现对窗口操作的同步管理。远程内存访问的设计要满足下列需求：( 1 ) 处理详细的内存行为事件，诸如缓存一致、串行致等；( 2 ) 在类的体系结构中兼顾效率和通用性的平衡，这包括共享内存的多进程，非2 64 m p i 并行程序设计统一内存访i h - ( n u m a ) 机器，多个并行进程的分布式内存，s m p 集群等；( 3 ) 把数据运动的同步性与性能的提高相分离。4 2 2 动态进程管理m p i 2 增加了m p i 进程参与创建新进程或者建立与进程通信的能力，允许在程序运行期间动态改变进程的数目，并提供动态进程创建和管理的各种调用。动态进程管理的主要任务是：维护简单性和灵活性；与操作系统、资源管理器、复杂系统软件环境中的进程管理器之间的交互；避免与正确性的竞争环境。内部通信子是包含两个进程组的通信子它是m p i - t 中高级特征，也是m p i 2中动态进程操作的基础，m p i 2 中新定义的两个命令族都是基于内部通信子的，它可以创建新的进程集实现进程繁殖，也可以利用己存在的m p i 程序来建立通信连接，后者允许应用程序拥有并行客户并行服务器的进程结构。组通信是动态进程管理操作正确性的关键，这种正确性不仅包含创建新进程的进程之间还包括被创建的新进程，进程的结果集在内部通信子中表示。对于组成通信子的两个进程组，。调用进程把自己所在的组看作本地组，而把另一个组称为远地组，使用组间通信子时要求本地组进程发送的数据被远地组进程接收，而本地组接收的数据必须来自远地组。可以通过三种方式利用组间通信子进行通信，分别是，通过动态创建新的进程，父进程与子进程形成组间通信子上的通信；两个没有父子关系的进程闻建立组间通信子进行通信；将s o c k e t 通信转换为组问通信子上的通信。4 2 3 其他新特性( 1 ) 外部接口m p i 的外部接口使得库对外部m p i 的访问更加容易，库可以访问具体的实现。( 2 ) 扩展组操作m p i 2 不仅扩展了m p i 1 中内部通信子之间的组操作，允许在空间上做出选择，并且发送和接收缓冲区相同，还将m p i 1 中用在内部通信子之间的组操作用在各个通信子之间。2 74 m p l 并行程序设计( 3 ) 语言的通用性m p i 2 通过定义新函数和限定实现的具体行为来定义它的新特性，这些特性允许使用混合语言编程。4 3m pi 并行程序设计下面是典型的m p i 程序代码模式，如下图4 1 和图4 2 所示：图4 1i f 语句m p i 程序代码4 m p i 并行程序设计图4 2 堋i t c h 语句肿i 程序代码由图4 1 和图4 2 可以看出来上面的这些m p i 程序的代码都是以串行的方式编写的，但是在运行时不同的处理机会执行不同的代码块。但是并行程序并不仅仅是这么简单的，各个处理机之问或者和某一台处理机是需要相互协调才能完成并行程序的执2 94 m p i 并行程序设计行。下面我们对怎用利用m p i 来设计并行程序进行详细的阐述。一些m p i 消息传递通信的基本概念在这里就不做描述，文献【4 6 】中有详细的说明。4 3 1m pl 并行程序一般结构m p i 主要是为程序员提供一个并行环境库，程序员通过调用m p i 的库程序来达到并行的目的，可以只使用其中的6 个最基本的函数就能编写一个完整的m p i 程序去求解很多问题。这6 个基本函数，包括启动和结束m p i 环境，识别进程以及发送和接收消息：m p ii n i t ：启动m p i 运行环境( 初始化m p i 运行环境) ；m p ic o m ms i z e ：确定进程数；m p ic o m mr a n k ：确定自己的进程标识符；m p is e n d ：发送一条消息；m p ir e c v ：接收一条消息；m p if i n a l i z e ：结束m p i 环境。所以m p i 并行程序的一般结构如下图4 3 所示：i包含头文件( # i n c l u d e “m p i h ”等等)i初始化m p i 尊行环境( m p i i n i t )l消息交换处理和计算等等图4 3l d p i 并行程序一般结构由m p i 并行程序的一般结构可以知道，程序的核心主要是集中在消息处理和计算方面，要想把消息处理设置好，主要还是要设置好通信的方式，下面的小节我们将3 04 m p i 并行程序设计详细地描述m p i 并行程序通信模式。4 3 2m pi 并行程序通信模式m p i 并行程序的设计有几种通信模式，本文就简单介绍下点到点( p o i n tt op o i n t )通信的几种模式和集合通信的几种模式。4 3 2 1 点到点通信点到点( p o i n tt op o i n t ) 通信简称pt op 通信，是指两台节点机之间的通信，必须有s e n d 和r e c e v 成对出现。点到点通信共有1 2 对，又对应于阻塞通信方式和非阻塞通信方式两种。阻塞通信又可以划分为标准通信模式( m p is e n d ) ，缓冲通信模式( m p ib s e n d ) ，就绪通信模式( m p ir s e n d ) ，同步通信模式( m p ls s e n d ) 。对上述的这些通信模式来说，不管发送是什么操作，接收操作总是m p ir e c v 。本文采用的通信模式为就绪通信模式下面仅对就绪模式举个简单的例子来说明阻塞通信有什么特征，如下图4 4 所示：4 m p i 并行程序设计图4 4 就绪通信模式代码实例3 24 m p l 并行程序设计在图4 4 中的代码中，m p ir s e n d 即就绪通信模式的标志，其中b u r 表示待发送数据起始地址：v o i d ，1 0 表示待发送的数据个数：i n t ，m p i i n t 表示数据类型m p id a t a t y p e ，0 表示源地址：i n t ，1 2 3 标志通信标志：i n t ，m p ic o m m w o r l d表示通信子：m p ic o m m 。但是图4 4 中的代码不是安全的，因为一旦p r o = l 这个进程先于在p r o = 0 这个进程的接收操作，就开始发送数据，那么程序就会报错，所以可以在代码中加一个同步语句。即在p r o = 0 时，在m p i r e c v 语句之前加m p ib a r r i e r ( m p ic o m mw o r l d ) 语句；在p r o = l 时，在m p ir s e n d 语句之后加上m p ib a r r i e r ( m p ic o m mw o r l d ) 语句。这样的通信才是安全的。在点到点通信中的缓冲模式下，若缓冲区满，则可能导致程序死锁或出错，所以若想保证一个m p i 程序的安全，可以把所有的发送操作替换成同步模式，但是性能不一定很好，所以比较好的解决办法还是采用非阻塞通信。非阻塞通信除了能解决程序死锁问题之外还有一个日的就是把计算和通信重叠起来，从而改进并行的效率。非阻塞通信还包括下面的模式，如下图4 5 所示图4 5 非阻塞通信模式分类4 3 2 2 集合通信集合通信主要是对一组进程进行通信、同步和计算等。主要由下面几种形式。4 m p i 并行程序设计进程q进程1进程数上进程1l1 爻n1卜、11图4 6 ( 1 ) m p i 。b o a s t 操作12341 爻n1234图4 6 ( 2 ) m p i s c a t t e r m p i s c a t t e v 操作l234n 引1234图4 6 ( 3 ) m p i g a t h e r i d p i o a t h e r v 操作1234n 釜11 0图4 6 ( 4 ) l d p i r e d u c e 操作n 受nl2341234l234l234图4 6 ( 4 ) m p i a il g a t h e r m p i a il g a t h e r v 操作3 4。进程数4 m p i 并行程序设计进程1进程数上数据_l234数据_n 爱n1 01 01 01 01 01 01 01 0l o1 01 01 01 01 01 01 0图4 6 ( 5 ) m p i a i l r e d u c e 操作l一591 3261 01 4371 1 1 5481 21 6n 爱nl23456789 ；1 01 l1 21 31 41 51 6图4 矗( 6 ) m p i a 1 1 t o a t l 操作上面图4 6 中的( 1 ) ( 6 ) 共描述了六种集合通信模式下的操作，还可以把它们划分到l 和n 之间的三种关系下。4 4 程序设计实倪在本小节中，设计一个快速排序的并行算法，并在第五章中的最短路径算法中加以应用。下面给出主程序的伪代码。如下图4 7 所示4i v i p i 并行程序设计木启动m p i 计算半m p i i n it ( & a r g c ，& a r g v ) ：, m p i _ c o m m _ w o r l d 是通信子木半确定自己的进程标志符m yl d * m p i _ c o m m _ r a n k ( m p i _ c o m mw o r l d ，& m y l d ) ：水组内进程数是s u m l d * m p i c o m ms iz e ( m p i _ c o m m _ w o r l d ，& s u m l d ) ：* 0 号节点机机获取必要信息，并分配各节点机机进行工作木；宰获取待排序数组的长度木g e t d a t a s iz e ( ) ：a 动态生成待排序序n * d a t a = ( i n t ) r a n d ( )木0 号节点机将数据序列广播到其他节点机，i ：m p i b c a s t ( & d a t a s i z e ，1 ，m p i i n t ，0 ，m p i _ c o m m _ w o r l d ) ：木o e s 节点机调度执行排序木p a r a l l e lq s o r t ( d a t a ，0 ，d a t a s i z e i ，m ，0 ，m y l d ) ；* 0 号节点机打印排序完的有序序列木p r i n t f ( 9 6 d ”，d a t a ) ：木结束m p i 计算术m p i f i n a l i z e0 ：图4 7 并行快速排序主程序由图4 7 中的代码可以看出，程序的主要实施功能在p a r a l l e lq s o r t ( ) 函数的实现上。下面给出p a r a l l e l _ q s o r t ( ) 函数的实现过程：( 1 ) 首先定义一些需要用到的常量和变量并赋值；( 2 ) i f ( 处理器个数等于1 )执行串行排序；调用串行排序函数q s o r t0 ；( 3 )e 】s e4 m p i 并行程序设计由0 号节点机根据节点机个数划分数据，并发送到每个节点机上；( 4 ) 发送完毕( 5 ) 各个节点机递归地调用p a r a l l e l _ q s o r t0 函数；( 6 ) 最后排序好的数据全部发回0 号节点机。程序设计完成后，可以运行命令m p i c c 宰c _ ox x x 进行编译，编译后的输出文件名为x x x ，然后可以使用命令m p j r u n - n p ? x x x 来运行此程序，其中? 表示需要运行的节点机的数目。4 5 本章小结本章在继绪论中的“体系结构：设计算法编程实现的研究方法中，主要对并行程序的算法进行了设计。首先对m p i 的发展和特点及新特性给以描述，然后对m p i并行程序的一般结构进行总结，接着对m p i 并行程序中重要的通信模式进行分析，最后设计一个并行程序的实例一并行快速排序，并为第五章中的实例测试和分析做好准备。3 75 最短路径实例测试与分析5 1 最短路径并行算法设计本章主要对“体系结构设计算法编程实现 中的编程实现进行描述，主要是利用并行快速排序技术求解最短路径。最短路径问题是图论中的一个经典的问题 4 7 - 5 3 1 。一般来说最短路径问题分为单源最短路径和全源最短路径问题。单源最短路径的并行算法大多是基于d i j k s t r a 算法和m o o r e 算法的；求解所有顶点对间的最短路径的并行算法大多是基于f l o y d 算法，在此基础上实现矩阵乘法的并行化。目前求最短路径的算法还有a ，b e l l m a n f o r d ，t q q ，d k a ，d k d ，k ( = 3 ) 条次最短路径搜索算法等。本文中设计的算法是单源最短路径的并行算法，基于d i j k s t r a 算法的，d i j k s t m算法是目前解决最短路径问题的理论基础，只是不同应用对d i j k s t r a 算法采用了不同的改进方法。在进行数据处理时，对设置好的邻接矩阵的数据首先采用并行快速排序的算法进行处理，然后再由0 号节点机发送到其它节点机上进行并行处理。5 1 1dij k s t r a 算法首先定义叫啊) ，定义集合s 存放已经找到最短路径的顶点，集合t 存放当前还未找到最短路径的顶点，即有t - - v - s ，d i j k s t r a 算法描述如下：( 1 ) 用带权的邻接矩阵e d g e s 来表示带权有向图，e d g e s i j 表示弧 1 4 ，畛上的权值。若 k ，畛不存在，则置e d g e s i j = 0 0 ( 计算机上用一个允许的最大值代替) 。s 为已经找到的从k 出发的最短路径的终点集合，它初始化为空集。那么，从k 出发到图上其余各项点( 终点) k 可能达到的最短路径长度的初值为：d i = d e g e s s i ，v i v ：( 2 ) 选择巧，使得d j = m i n d i l v , ev - 田，巧就是当前求得的一条从k 出发的3 r5 最短路径实例测试与分析最短路径的终点。令肛s u 巧)( 3 ) 修改从k 出发到集合班s 上任一顶点妖可达的最短路径长度。如果d j 】+ e d g e s 【j 】【k 】 首先使存放最短路径的集合s 为空，( 2 ) 对存放临时标注节点的集合l 把数据分到各节点机和利用并行快速排序的算法，使序列有序； 本文对并行算法的基本理论进行了介绍，如并行算法的定义和分类，并行算法的设计方法、编程模型、性能评价等。另外本文对并行算法的性能度量主要是采用相对加速比来进行评价s p = t i t p 。( 3 ) 本文设计了利用并行快速排序技术的最短路径的并行方法。分析了算法的负载平衡问题，并在基于p c 集群的网络并行环境下，测试了文中给出的最短路径并行算法的性能，给出了算法的运行时问和加速比。实验结果表明：本算法能够正确求解最短路径问题 能有效地提高并行算法的性能。( 4 ) 通过对并行平台的搭建，对m p i 并行程序的设计，获得了一些并行算法实际应用的经验，加深了对m p i 的理解，并熟练掌握了并行机群系统的使用。6 2 本文存在的问题及将来工作由于本文是在实验室由几台p c 组成的小型集群系统，与大型多c p u 并行机进行比较自然存在较多弊端。还有之前对该领域相关知识储备的匮乏，虽然取得了一点成绩，积累了一些经验，但是从应用的角度来看，还有很多关键问题需要研究，主4 36 总结要有以下一些方面：( 1 ) 对于基于m p i 设计的程序来说，很好的处理负载平衡都是提高并行效率的关键。本文在设计和实现并行算法的过程中，没有深入考虑负载平衡的调度策略问题。现在，目前，本文所设计的并行算法的任务调度一部分由m p i 系统完成，一部分是通过应用程序控制，今后可以考虑设计一个动态分布式调度算法，平衡各节点机上的负载，使并行算法取得更高的运行效率。这就需要解决：什么时候启动负载平衡调度，每次平衡调度的源结点和目标结点是哪些，选择哪些任务进行等问题，这些需要进一步的研究。( 2 ) 本文在最短路径问题算法方面还需更进一步的研究，比如可以基于并行快速排序的基础上，对d i j k s t r a 算法做并行化处理，以后的研究可以这对这方面进行。( 3 ) 本人对并行算法的设计还处于初级的水平，并没有考虑到怎样去更好的进行并行粒度的划分和一些通讯的开销等等，所以以后若有机会和时间在此方面需要改进。参考文献【1 】b a r r yw i l k i n s o 重l , m i c h a e la l l e n ，p a r a l l e lp r o g r a m m i n g c ，c h i n am a c h i n ep r e s s ，2 0 0 5 【2 】k u a nc h i n gl i ，h s u nc h a n gc h a n g o nc o n s t r u c t i o no fav i s u a l i z a t i o nt o o l k i tf o rm p ip a r a l l e lp r o g r a m si nc l u s t e re n v i r o n m e n t s c a d v a n c e di n f o r m a t i o nn e t w o r k i n ga n da p p l i c a t i o n s , a i n a 2 0 0 5 t 9 t hi n t e m a t i o n n lc o n f e r e n c e 2 0 0 5 ，v 0 1 2 ：2 t 1 - - - 2 1 4 【3 】d h a b a l e s w a rk p a n d a , h o n a lm n i s 即c i a ti s s t t e0 1 1w o r ks t a t i o nd u s t e r sa n dn e t w o r kb a s e d 0 0 m p l l t i i l g p ，f a r a l l e lw _ dd i s t r i b u t e d c o m p u t i n g 1 9 9 7 ，4 0 ，l ，【4 】岬d e i , ? r i c kb r a d s h a w , a n d r e wl u s t k ，e r e m p ic l u s t 盯s y s t e ms o f t w a r e【j 】s p r i n g e rb e r l i n h e i d e l b e r g , 2 0 0 4 5 j 陆鑫达并行和分布计算技术现状及发展策略 j 中国计算机世界，1 9 9 8 6 孙家旭，张林波，迟学斌等网络并行计算与分布式编程环境 m ，科学出版社，1 9 9 6 7 王萃寒，赵晨，许小刚等分布式并行计算环境e j 计算机科学，2 0 0 33 0 ( 1 。) ：2 5 2 - 2 6 1 8 李学于，徐甲同并行处理技术跚 ，北京理工大学出版社，1 9 9 4 【9 】翱= t p ：，1 州哪：切p 5 嗷j l i s t s 2 0 0 9 0 6 【10 a m j f t y r m s o m ec o m p u t e fo r g a a i z a t i o n sa n dt h e i re f f e c t i v e r 圮s s 【j i1 e e e胁c o m p u t e r s 。2 i ( 9 ) ：9 4 8 - 9 6 0 ，19 7 2 “】a h k a r p p r o g r a m m i n gf o rp a r , d l e l i m n 【j 】珏陋ec o m l 眦e r , 2 0 ( 5 ) ：4 3 - 5 7 ，19 8 7 【12 1r w h 白c k n e y p e r f o r m a n c ep a r a m e t e r sm a db e n c h r a a r k i n g0 fs u p e 向o m p u t e r s【j 】p a r a b dc o m l m t i n 吕t 7 ：11n t1 3 0 ，t 9 9 1 f 13 】r w h o e k n e y t h ec o m m u n i c a t i o nc h a l l e n g ef o rm p p ：i n t e ! p a r a g o na a dm e i k oc s 一2 【j 】p a r a l l e lc o m p u t i n g ，2 0 ：3 8 9 3 9 8 ，1 9 9 4 【1 4 r w h o c l m e y t h es c i e n c eo fc o m p u t e rb e n c h m a r k i n g c ，t h es o c i e t yf o ri n d u s t r i a la n da p p l i e dm a t h e m a t i c s ，p h i l a d e l p h i a ，1 9 9 6 【15 r w h o c k n e ya n dc r j e s s h o p e p a r a l l e lc o m p u t e r s ：a r c h i t e c t u r e ，p r o g r a m m i n g ，a