（系统分析与集成专业论文）连通分量问题的多机并行算法研究.pdf

摘要连通分量问题作为图论中的经典问题，在许多领域的应用中起到了重要的作用。由于应用范围的扩大，信息的增加，其串行算法的性能也受到影响。随着v l s i 技术的发展和并行计算机的出现，为人们快速求解图论问题提供了一条新的途径。本文首先介绍了当代并行计算机体系结构，分析了各种并行计算模型和并行算法编程模型的特点。接下来讨论了在m p i 中，解决消息传递过程中的异构性问题，以及在多种不同通信模式下的操作方式。然后对求解连通分量问题的几种并行算法进行了性能分析，列表比较其时间复杂性和并行计算成本。选择了其中的一种算法一顶点倒塌算法做进一步研究，编写出基于m p i的c 语言程序，在多机并行环境中对程序进行性能分析，分析数据显示该程序取得了较好的并行计算效果。关键词：连通分量：顶点倒塌；并行计算a b s t r a c ta so n eo ft h ec l a s s i c a lq u e s t i o no fg r a p h i ct h e o r y , c o n n e c t e dc o m p o n e n tt h e o r yp l a ya ni m p o r t a n tr o l ei nm a n yf i e l d t h ep e r f o r m a n c eo fi t ss e r i a la l g o r i t h mi sa f f e c t e da l o n gw i t ht h ei n c r e a s eo fi n f o r m a t i o n i ta f f o r dan e ww a yt os o l v et h ep r o b l e mo fg r a p h i ct h e o r ya st h ed e v e l o p m e n to fv l s ia n dt h ea p p e a r a n c eo fp a r a l l e lc o m p m e r t h i sp a p e ri n t r o d u c et h ep a r a l l e lc o m p u t e rs y s t e mo ft h et i m ef i r s t l y ，a n a l y s i st h ec h a r a c t e r i s t i co fv a r i o u sp a r a l l e lc o m p m em o d e l sa n dp a r a l l e la l g o r i t h mm o d e l s t h es e c o n d ，d i s c u s sh o wt or e s o l v et h ei s o m e r o u sp r o b l e mo fm e s s a g ep a s s i n gi nm p i ，a n dt h eo p e r a t i o na b o u td i f f e r e n tc o m m u n i c a t i o nm o d e ，a n dt h e n ，a n a l y s i st h ep e r f o r m a n c eo fs o m ep a r a l l e la l g o r i t h mt os o l v et h eq u e s t i o na b o u tc o n n e c t e dc o m p o n e n t ，c o m p a r et h e i rc o m p l e x i t yo f r u n t i m ea n dt h ec o s to f p a r a l l e lc o m p u t et h r o u g ht a b l e s ，a n dc h o o s et h ev e r t e xc o l l a p s ea l g o r i t h mt or e s e a r c h ，c o d ei t scp r o g r a mb a s e do nm p i ，a n a l y s i st h ep e r f o r m a n c eu n d e rt h em u l t i - c o m p m e rp a r a l l e ls y s t e m i td o e sw e l lt h r o u g ht h ea n a l y t i cr e s u l t k e yw o r d s ：c o n n e c t e dc o m p o n e n t ；v e r t e xc o l l a p s e ；p a r a l l e la l g o r i t h mi i1 1 选题的目的和意义1 绪论现代计算机技术极大的促进了计算科学的发展，几乎所有的学科都开始走向定量化和精确化。但在实践中，由于受到物理器件极限速度和技术水平的限制，使得单处理机远远满足不了现代许多科学领域中大规模计算课题对计算资源的需求。计算机单机技术发展的有限性和科学工程计算需求的无限性之间的矛盾决定了计算机发展必然走上多机并行计算的道路。并行计算是通过把一个大的计算问题分解成许多彼此独立且又相关的子问题，然后把它们散列到各个结点机上并发执行从而最终解决问题的一种方法。这种并行计算方法将成为未来主流计算模式，并行处理技术的发展将成为未来国家科技发展的主要推动力量。一些发达国家纷纷制定高性能并行计算机发展战略计划，提出很高目标，投入大量资金，加速研究开发步伐。多年来，随着大规模集成电路技术的不断进步，以多c p u 为基础的高性能并行计算机得到了迅速的发展，其高端系统正向百万亿次、千万亿次迈进。我国对高性能并行计算的研究开发也给予了很大重视，并将其纳入国家“8 6 3 计划”。目前，我国已研制出神州、银河、曙光等系列高性能计算机，由曙光公司推出的百万亿次数据处理超级服务器曙光4 0 0 0 l ，再一次刷新国产超级服务器的历史纪录，使得国产高性能产业再上新台阶，其中涉及的部分并行技术( 如机群操作系统、虫洞透信芯片设计、并行优化编译等) ，已达到国际先进水平。尽管并行处理技术在近年来得到长足发展，在硬件方面( 如并行计算机制造、硬件级别的指令并行等方面) 突破较大，但在软件方面的发展还有待进一步提高，存在许多问题亟待解决，其中包括并行系统软件、并行算法以及并行应用程序等。由于算法是软件的核心，因此研究与并行处理系统相适应的并行算法对推动并行处理技术的发展具有重要作用。图论( g r a p h i ct h e o r y ) ，是以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系，图论则是研究事物对象在上述表示法中具有的特征与性质的学科。现实世界中许多状态都可以用图来描述，例如交通运输、城市规划、信息传递、电路网络、工作调配等都可以用点和边连接起来的图来模拟。在计算机科学、物理学、化学、建筑学、心理学、经济学、运筹学、电讯工程等学科中都有广泛的应用。在计算机科学中，它在形式语言、数据结构、分布式系统、操作系统等方面均有很重要的应用。但很多图论问题虽容易表达，却难以求解。已经证明有相当多的图论问题都是n p 完全的。随着v l s i 技术的发展和并行计算机的出现，为人们快速求解图论问题提供了一条新的途径。运用多处理机系统来求解图论问题，将会在科学和工程应用中发挥重要的作用。连通分量问题作为图论中的经典问题之一，其并行算法的实现有着较强的应用价值，在许多领域的应用中会起到重要的作用。求解图的连通分量是并行图论算法中最活跃的研究领域之一。有很多新的思想和方法会在研究过程中提出。若能将某些针对专属并行模型的算法加以适当改造，使其在普通的多机并行环境中运行，则既能扩大包括连通分量问题在内的图论问题的应用范围，也能进一步促进并行计算技术的普及和发展。1 2 国内外研究现状如何找出图g 中所有连通分量的问题称为连通分量问题。连通分量问题的解决方法常见的有三种：利用图的遍历搜索算法基于传递闭包的方法顶点倒塌法。其中第一种方法由于遍历时需要考虑前后节点的依赖关系，不易并行化实现，一般仍以串行算法为主；基于传递闭包的方法是在求出图的传递闭包矩阵之后，再进行求解连通分量，该算法主要适用于s i m d c c 模型 2 】，有一定的局限性，而且由于传递闭包算法1 2 j 的并行计算成本较高( 达到0 ( n a l 0 9 2 n ) ) ，也会影响到该并行算法的性能；顶点倒塌法则是专门针对并行计算提出的方法，多个顶点的处理具有很强的独立性，很适合分配给多个处理器并行处理。该算法1 9 7 6年由h i r s c h b e r g ”】首次提出，主要应用于二维网孔模型。除了这三种常见的方法之外，1 9 8 1 年，l i p t o n v a l d e s 曾提出了一种在树机上实现的连通算法1 1 “，在算法的循环执行过程中，每一遍执行考虑邻接矩阵的一行，即在第i 遍时，只将邻接矩阵的第i 行读入树的叶节点处理器中。利用树形模型的特点，将顶点i 的现行连通分量标号亦保持在叶节点中。最近，还有人提出了利用树网模型来设计求解连通分量的算法，在n n 的处理器阵列中，先将每个顶点划为一个小组：然后重复的对每组g 寻找它所邻近的最低号码的组号h ，如果h g ，则将g 归并入h ，利用树网中的第i 个根( 控制器) 保存顶点i 所应连向的最低号码的节点。在多种求解连通分量的并行算法中，顶点倒塌法应用得最为广泛。1 3 本文的主要工作本文主要分析了在不同并行计算模型中，各种求解连通分量问题算法的性能。分别研究分析了基于闭包传递的算法、顶点倒塌算法、l i p t o n - v a l d e s 连通分量算法和树网模型上的连通分量算法。在分析的过程中，将求解连通分量问题的串行算法用作并行算法性能分析的参考。最后，选择了应用范围最为广泛，并行计算成本相对较低的顶点倒塌算法，根据其算法思想，编写出基于m p i 的c 语言程序，在多机并行环境中对其性能进行了分析。本文主要做了以下工作：1 分析用于并行计算的物理模型和算法编程模型，研究各种模型的适用范围以及在实际应用中的优缺点。2 讨论了m p i 中，解决消息传递过程中的异构性问题，以及在多种不同通信模式下的操作方式。3 研究分析了基于闭包传递的算法、顶点倒塌算法、l i p t o n v a l d e s 连通分量算法和树网模型上的连通分量算法，对其算法性能进行综合比较。4 在m p i 环境中，用c 语言编写顶点倒塌算法程序，在并行环境中输入数据测试，针对实验结果进行性能分析。2 并行计算基本理论2 1 当代并行计算机体系结构2 1 1 并行计算机系统的发展并行计算机是相对传统串行计算机而言的，所谓串行计算机就是只有单个处理器单元顺序执行计算程序的计算机，所以也称之为顺序计算机。顺序计算机最早是从位串行操作到字并行操作、从定点运算到浮点运算改进过来的；然后它按照图2 1 所示的过程逐步演变出各种并行计算机系统 3 1 ：从顺序标量处理计算机开始，首先用先行技术预取指令，达到重叠操作实现功能并行：支持功能并行可使用多功能部件和流水线两种方法；而流水线技术对处理向量数据元素的重复相同的操作表现出强大的威力，从而产生了向量流水线计算机( 包括存储器到存储器和寄存器到寄存器两种结构) ；不同于时间上并行的流水线计算机，另一分支的并行机是空间上并行的s i m d ( 单指令流多数据流) 并行机，它用同一控制器同步地控制所有处理器阵列执行相同操作来开发空间上的并行性；如果用不同的控制器异步地控制相应处理单元执行各自的操作，则就派生出另一类m i m d( 多指令流多数据流) 并行机；其中，如果各处理单元通过公用存储器中的共享变量实现相互通信，则就成为多处理机( m u l f i p r o c e s s o r s ) ；如果处理单元之间使用消息传递的方式来实现相互通信，则成为多计算机( m u l t i , c o m p u t e r s ) ，它也是当今最流行的并行计算机。2 1 2f l y 分类法丈规雏并行整理巍棚p p )图2 11 9 6 6 年f l y n n n 按照指令流和数据流的多倍性概念将计算机系统结构进行了分类。其中指令流是指机器所执行的指令序列，数据流是指指令流所调用的数据序列，而多倍性是指机器的瓶颈部件上所可能并行执行的最大指令或数据的个数。根据指令流和数据流的不同组合，计算机系统可分为如图2 2 ( a ) 所示的单指令流单数据流s i s d ( s i n g l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ) ，图2 2 ( b ) 所示的单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) ，图z 2 ( c ) 所示的多指令流单数据流m i s d ( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ) ，图2 2 ( d ) 所示的多指令流多数据流m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 。其中，s i s d 就是传统的单处理机( 又叫串行机或顺序机) ，m i s d 是一种不太实际的计算机，但也有部分学者把超标量机和脉动阵列机归属于此类，而s m d 和m i m d 就是最常见的并行计算机。s i s d 计算机彻$ 1 m o 计算机c ) m i s d 懒呻i v l m d 嗍2 1 3 并行计算机结构模型图2 2i谩砑：ljc u ：拄翻啡ffp u ：址理斛flm m 主存麓块ls m ：共辜主喜iic s ：拄捌罐i硌：指令藏fid s ：勰淀l大型并行机系统结构p 】一般可以分为六类：单指令流多数据流机s i m d( s i n g ei n s t r u c i o nm u l i p l ed a t a ) ：并行向最处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) ；对称多处理机s m p ( s y m m e a - i cm u l t i p r o c e s s o r ) ；大规模并行处理机m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) ；工作站机群c o w ( c l u s t e ro f w o r k s t a t i o n )和分布式共享存储d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 多处理机。s i m d 计算机为专用，其余的5 种均属于多指令流多数据流m i m d ( m i l l d d l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as l r e a m ) 计算机。目前绝大多数近代并行机均用商品硬件构成，而p v p 计算机的部件很多都是定制( c u s t o m - m a d e ) 的。一( 1 ) 并行向量处理机( p v p ) ：这样的系统中包含了少量的高性能专门设计定制的向量处理器v p ，每个至少具有1 g f l o p s 的处理能力。系统中使用了专门设计的高带宽的交叉开关网络将v p 连向共享存储模块，存储器可以每秒兆字节的速度向处理器提供数据。这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。( 2 ) 对称多处理机( s m p ) ：该系统使用商用微处理器( 具有片上或外置高速缓存) ，它们经由高速总线( 或交叉开关) 连向共享存储器。这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等。重要的是系统是对称的，每个处理器可等同的访问共享存储器、i o 设备和操作系统等。正是对称，才能开拓较高的并行度；也正是共享存储，也限制了系统中的处理器不能太多( 一般少于6 4 个) ，同时总线和交叉开关互连一旦做成也难于扩展。( 3 ) 大规模并行处理机( m p p ) ：一般是指超大型( v e r yl a r g e s c a l e ) 计算机系统，它具有如下特性：处理结点采用商用微处理器：系统中有物理上的分布存储器；采用高通信带宽和低延迟的互连网络( 专门设计和定制的) ；能扩放至成百上千个处理器：它是一种异步的m i m d 机器，每个都有其私有地址空间，进程间采用传递消息相互作用。m p p 的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。( 4 ) 分布共享存储多处理机( d s m ) ：d s m 和s m p 的主要差别是，d s m 在物理上有分布在各节点中的局存从而形成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个单地址的编程空间。d s m 相对于m p p 的优越性是编程较容易。( 5 ) 工作站机群( c o w ) ：在有些情况下，机群往往是低成本的变形的m p p 。c o w 的重要界线和特征是：o c o w 的每个节点都是一个完整的工作站( 不包括监视器、键盘、鼠标等) ，这样的节点有时叫做“无头工作站”，一个节点也可以是一台p c 或s m p ：各节点通过一种低成本的商品网络( 如以太网、f d d i和a t m 开关等) 互连( 有的商用机群也使用定做的网络) ；各节点内总是有本地磁盘，而m p p 节点内却没有；节点内的网络接口是松耦合到i o 总线上的，而m p p 内的网络是连到处理节点的储存总线上的，因而可谓是紧耦合式的；有一个完整的操作系统驻留在每个节点中，而m p p 中通常只是个微核，c o w的操作系统是工作站u n i x ，加上一个附加的软件层以支持单一系统映象、并行度、通信和负载平衡等。现在，m p p 和c o w 之间的界限越来越模糊。例如，m ms p 2 它虽视为m p p ，但它却有一个机群结构。机群相对于m p p 有性能价格比高的优势，所以在发展可扩放并行计算机方面呼声很高。2 2 并行计算模型在并行机上求解问题，首先要写出求解问题的并行算法。并行算法是在并行计算模型上设计出来的，而并行计算模型是从不同的并行计算机体系结构模型中抽象出来的。2 2 1s i m d 同步并行计算模型1 ，s i m d 共享储存模型( d p r a m 模型描述p r a m ( p a r a l l e lr a n d o m a c c e s sm a c h i n e ) 模型嗍，即并行随即存取机器，也称之为共享存储器的s i m d 模型，是一种抽象的并行计算模型。在这种模型中，假定存在着一个容量无限大的共享存储器；有有限或无限个功能相同的处理器，且其均具有简单的算术运算和逻辑判断功能；在任何时刻处理器均可通过共享存储单元相互交换数据。根据处理器对共享存储单元同时读、同时写的限制，p r a m 模型又可分为：不允许同时读和写( e x c l u s i v e r e a da n de x c l u s i v e w r i t e ) 的p r a m 模型，简记之为p r a m e r e w ；允许同时读但不允许同时写( c o n c u r r e n t - r e a da n de x c l u s i v e w r i t e ) 的p r a m 模型，简记之为p r a m c r e w ；允许同时读和写( c o n c u r r e n t r e a da n dc o n c u r r e n t w n t e ) 的p r a m 模型，简记之为p r a m - c r c w 。显然，允许同时写是不现实的，于是又对p r a m c r c w 模型做了进一步的约定：只允许所有的处理器同时写相同的数，此时称之为公共( c o m m o n ) 的p r a m c r c w ，简记之为c p i 乙a m c r c w ；只允许最优先的处理器先写，此时称为优先( p r i o r i t y ) 的p r a m c r c w ，简记之为p p r a m - c r c w ；允许任意处理器自由写，此时称为任意( a r b i t r a r y )的p r a m c r c w ，简记之为a p r a m c r c w 。上述模型中，p r a m e r e w 是最弱的计算模型，而p r a m - c r c w 是最强的计算模型。令t m 表示某一并行算法在并行模型m 上的运行时间，则t e r e w t c r e w t c r c w( 2 ) p r 心d 模型优点它特别适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行在不同并行机上；且有可能在p r a m模型中加入一些诸如同步和通信等需要考虑的问题。( 3 ) p r a m 模型缺点p r a m 是一个同步模型，这就意味着所有的指令均按锁步方式操作，用户虽感觉不到同步的存在，但它的确是很费时的；共享单一存储器的假定，显然不适合于分布存储的异步的m i m d 机器；假定每个处理器均可在单位时间内访问任何存储单元而略去存取竞争和有限带宽等是不现实的。2 s i m d 分布存储模型分布存储的s i m d 模型，简记之为s i m d d m ，也称为s i m d 互连网络模型，简记之为s i m d i n 。很多实验性的和商品并行机几乎都是基于这种结构。其中各处理器( 包括算术逻辑单元和本地存储器) ，通过各种互连网络连接起来，从而形成各种不同互连结构的分布存储s m 模型，常用的有：采用一维线性连接的s i m d 模型，简记之为s i m d l c ；采用网孔连接的s i m d 模型，简记之为s i m d m c ；采用树形连接的s i m d 模型，简记之为s i m d t c ；采用立方环连接的s i m d 模型，简记之为s i m d c c c 等。2 , 2 2m i m d 异步并行计算模型1 异步p r a m 模型( 1 ) 模型特点分相( p h a s e ) p r a m 模型是一个异步的p r a m 模型，简记之为a p r a m 7 1 ，是由p 个处理器组成，其特点是每个处理器都有其本地存储器、局部时钟和局部程序：处理器间的通信经过共享全局存储器：无全局时钟，各处理器异步地独立执行各自的指令；处理器任何时间依赖关系需明确地在各处理器的程序中加入同步障( s y n c h r o n i z a t i o nb a r r i e r ) ；一条指令可在非确定但有限地时间内完成。( 2 ) a p r a m 模型中地指令类型a p r a m 模型中有四类指令：全局读：将全局存储单元中的内容读入本地存储器单元中：局部操作：对本地存储器中的数执行操作，其结果存入本地存储器中；全局写：将本地存储器单元中的内容写入全本地存储器单元中；同步：同步是计算中的个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序。( 3 ) a p r a m 模型中的时间计算使用a p r a m 模型计算算法的时间复杂度时，假定局部操作取单位时间；全局读写时间为d ，它定量化了通信延迟，代表读写全局存储器的平均时间，d 随机器中的处理器增加而增加；同步障的时间为b ，它是处理器数p 的非降函数b = b ( p ) 。在a p r a m 中假定上述参数服从如下关系：2 d b p令t p h 为全局相内各处理器指令执行时间中最长者，则整个程序运行时间t为各相的时间加上b 乘以同步障次数，即：t = t p h + b 同步障次数总之，a p r a m 模型比起p r a m 来更接近于实际的并行机，且保留了p r a m编程的简洁性；由于使用了同步障，所以不管各处理器遇到的延迟多长，程序必定是正确的，且因为a p r a m 模型中的成本参数是定量化的，所以算法的分析也是不难的。2 ，b s p 模型( 1 ) b s p 模型的基本参数大同步并行b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型f 8 】，其早期最简单的版本叫做x p r a m 模型，它是作为计算机语言和体系结构之间的桥梁，并以下述三个参数描述的分布存储的多计算机模型：处理器存储器模块；施行处理器存储器模块对之间点到点传递信息的选路器；执行以时间间隔l 为周期的所谓同步障同步器。( 2 ) b s p 模型中的计算在b s p 模型中，计算是由一系列用全局同步分开的周期为l 的超级步( s u p e r s t e p ) 所组成。在各超级步中，每个处理器均执行局部计算，并通过选路器接收和发送消息；然后做一全局检查，以确定该超级步是否已由所有的处理器完成：若是，则前进到下一超级步，否则下一个l 周期被分配给未曾完成的超级步。2 2 3 其它并行计算模型1 分布式计算模型一个基于异步通信的分布式计算模型，简记之为m i m d a c ，可以抽象为一个无向图g ( v ，e ) ，其中，顶点集对应则处理器集合，边集对应着处理器间双向通信链集合。每个处理器都赋予唯一的编号，且只具有知晓与其有线相连的近邻处理器的局部知识。系统中并无共享存储器，各处理器之间的通信是通过发送和接收消息完成的。在算法运行期间，每个处理器除了执行自己的计算任务外，还向邻近的处理器发送消息和接受并处理来自邻近处理器的消息。假定计算时间远小于通信时间，并且假定通信链是无故障的，这样每个处理器发送绘近邻处理器的消息总可在有限( 但不确定) 的时间内到达。在一条通信链上同一方向上所到达的消息，服从先进先出( f i f o ) 的规则。在这种基于异步通信的分布式计算模型上开发的算法也叫做分布式算法( d i s t r i b u t e d a j 【g o r i t h m ) ，度量它的标准主要是通信复杂度。2 比较器网络对于基于比较关系运算的一大类计算问题，可直接使用比较网络【9 ( c o m p a r a t o rn e t w o r k ) 求解，该网络是由b a t h e r 比较器根据一定的拓扑结构按级排列而成。这种比较器是一个双输入双输出的比较交换单元，可将两输入数据按大小自动分别置于两个输出端。对于一个n x n 的比较器网络而言，通常假定只能有r d 2 对数据可同时进行比较交换操作，而且还限制，在每一级任何一个数都不能与两个或两个以上的其他数同时进行比较，否则的话，后续的条件交换就比较复杂而影响连线的规整性。2 3 并行算法编程模型对于用户而言，所设计的任何并行算法最终总要通过并行编程在具体并行机上执行实现。不同的并行机体系结构模型其编程风范也不同。不同的并行编程风范，是建立在不同的并行程序设计模型上的。2 3 1 数据并行模型数据并行( d a t a p a r a l l e l ) 模型既可以在s i m d 计算机上实现，也可以在s p m d计算机上实现，这取决于粒度大小。s i m d 程序着重开发指令级细粒度的并行性；s p m d 程序着重开发子程序级中粒度的并行性。数据并行程序设计强调的是局部计算和数据选路操作，它比较适合于使用规则网络、模板和多维信号及图像数据集来求解细粒度的应用问题。数据并行操作的同步是在编译时而不是在运行时完成的。硬件同步则是通过控制器执行s i m d 程序的锁步操作完成的。在同步的s i m d 程序中，所有p e 问的通信则直接由硬件控制，除所有p e 间操作需要锁步外，p e 间的数据通信也是以锁步方式进行的。这些同步指令的执行和数据选路操作使得s i m d 计算机在开发大型数组、大型网格或网状数据的空间并行性时相当有效。下面是一个计算兀值的数据并行程序的例子：伊计算n 数据并行编程代码段+ ，m a i n ( ) d o u b l el o c a l n ，t e m p n , p i ，w ；l o n gi j ，t , n = 1 0 0 0 0 0 ；a ：w = 1 o n ；b ：f o r a l l ( i = o ；i n ；i + + ) p ：l o c a l i = ( i + o 5 ) + wq ：t e m p i = 4 o ( 1 0 + l o c a l i + l o c a l i ) ；c ：p i 2 s u m ( t e m p ) ；d ：p r i n f f ( 1 p ii s f 、i l ”, p i + w ) ；2 3 2 消息传递模型在消息传递( m e s s a g e p a s s i n g ) 模型中，驻留在不同节点上的进程可以通过网络传递消息相互通信。消息可以是指令、数据、同步信号或中断信号等。在消息传递的并行程序中，用户必须明确地为进程分配数据和负载，它比较适合于开发大粒度的并行性，这些程序是多线程的和异步的，要求显示同步，以确保正确的执行顺序。然而这些进程均有其分开的地址空间。消息传递模型比数据并行模型灵活。两种广泛使用的标注库p v m 和m p i 使消息传递程序大大地增加了可移植性。消息传递不仅可以执行在共享变量的多处理机上，而且可执行在分布存储的多计算机上。总的来说，消息传递模型具有以下特点：多线程( m u l t i t h r e a d i n g ) ：消息传递程序是由多个进程组成，每个进程都有其自己的控制线且可执行不同的代码；控制并行和数据并行均可支持。异步并行性( a s y n c h r o n o u sp a r a u e l i s m ) ：消息传递程序的诸线程彼此异步地执行，使用诸如路障和阻塞通信的方法来同步各个进程。分离地址空间( s e p a r a t e a d d r e s ss p a c e ) ：并行程序的进程驻留在不同地址空间内，一个进程中的数据变量在其它进程中是看不见的，因此一个进程不能读写另一进程中的变量，进程的相互作用通过执行特殊的消息传递操作实现。显式分配( e x p l i c i t a l l o c a t i o n ) ：负载和数据均由用户显式地分配给进程，为了减少设计和编码地复杂性，用户常使用单一代码方法编写s p m d 应用程序。下面用m p i 以c 语言表示方式来示例上一节所举的计算“值的消息传递程序：胪计算n 消息传递编程代码段，# d e f i n en1 0 0 0 0 0m a i n ( ) d o u b l el o c a l = 0 0 ，p i ，w , t e m p = 0 o ；l o n gi , t a s k e d ，n u m t a s k ；w = i o n ；m p i _ i n i t ( & a r g c ，& a r g v ) ；m p i _ c o m m _ r a n k ( m p l _ c o m mw o r l d ，& t a s k i d ) ；m p i _ c o m m _ s i z e ( m p i _ c o m mw o r l d ，& n u m t a s k ) ；f o r ( i = t a s k e d ；i n ；i = i + n u m a s k ) t e m p = ( i + 0 ，5 ) + w ；l o c a l = 4 0 ( 1 0 + t e m p + t e m p ) + l o c a l ；)1 1 ，m p i _ r e d u c e ( & l o c a l ，& p i ，1 ，m p i _ d o u b l e ，m p i _ m a x ，0 ，m p i c o m m _ w o r l d ) ；i f ( t a s k e d = 2 0 ) p r i n f ( “p ii s ”，p i + w ) ；m p l f i n a l i z e 0 ；)2 3 3 共享变量模型在共享变量( s h a r e dv a r i a b l e ) 模型中，驻留在各处理器上的进程可以通过读写公共存储器中的共享变量相互通信。它与数据并行模型的相似之处在于它有一个单一的全局名字空间；它与消息传递模型的相似之处在于它是多线程的和异步的。然而数据是驻留在单一共享地址空间中，因此不需要显式分配数据，而工作负载既可显式也可隐式分配。通信通过共享的读写变量隐式完成，而同步必须是显示的，可以保持进程执行的正确顺序。共享变量模型目前已有一个可接受的标准o p e n l v i p 。下面给出用类c 语言代码书写的计算a 值的共享变量程序：计算”消息传递编程代码段# d e f i n en1 0 0 0 0 0m a i n ( ) d o u b l el o c a l , p i = 0 。o 硝l o n g i ；w = 1 o n ；# p r a g m ap a r a l l e l# p r a g m as h a r e d ( p i ，w )# p r a g m al o c a l ( i ，l o c a l )# p r a g m ap f o ri t e r a e ( i 2 0 ；n ；1 )f o r ( i - o ；i 心j ；i 抖) l o c a l = ( i + 0 5 ) + w ；l o c a l = 4 o ( 1 0 + l o c a l + l o c a l ) ；)# p r a g m ac r n c np i = p i + l o c a l ；)p r i n f ( p ii s f h ，p i + w )2 4 并行算法的复杂性度量2 4 1 复杂性度量参数算法可用不同的标准度量，但我们主要关心的是算法与求解问题规模n 之间的关系。对于一个给定的具有规模1 1 _ 的问题，通常有各种可能的输入集合。在s i m d 计算模型上的并行算法，将分析算法的运行时间和所需的处理器数，在最坏情况下与问题规模n 的关系：运行时间t ( n ) ：运行时间就是在给定模型上求解问题所需要的时间。即算法从开始执行到结束所经过的时间。此时间通常包含在一个处理器内执行算术和逻辑运算所需的计算时间t c ，以及数据从源处理器经过互连网络到达目的处理器所需要的选路时间t r 。处理器数p ( n ) ：求解给定问题所需的处理器的数目，它是问题规模n 的函数。在m i m d 计算模型上，对基于共享存储的算法，其时间还应包含同步等时间，它们与s i m d 模型上的复杂度度量基本一致：而对于基于异步通信的分布式计算模型，其算法的度量标准主要有两个：通信复杂度：是指算法在整个执行期间所传送的消息的总数，它可能是基本长度的消息的总数，或者是传送消息的二进制位数的总和。时间复杂度：是指算法从第一台处理器上开始执行到最后一台处理器上终止的这段时间间隔。2 4 2 并行算法的性能评价并行算法成本：成本c ( n ) 定义为并行算法的运行时间t ( n ) 与其所需的处理数p ( n ) 的乘积，即c ( n ) - - - - t ( n ) p ( n ) 。换句话说，成本等于最坏情况下求解一个问题时的总的执行步数。加速比：加速比s p ( n ) 气( n ) t p ( n ) 。其中，t 。( n ) 是求解一个问题的最快的串行算法在最坏情况下的运行时间；而t 。( n ) 是求解同一问题的并行算法在最坏情况下的运行时间。可见，加速比是评价算法的并行性对运行时间改进的程度。因为任何并行算法都能在一台串行机上模拟，所以t s ( n ) p ( n ) t p ( n ) ，从而1 s 。( n ) p ( n ) 。并行算法的效率：效率e p ( n ) = s p ( n ) p ( n ) ，它反映了并行系统中处理器的利用情况。因为有时候一个并行算法虽然有好的加速，但处理器的利用率可能很低。3 基于消息传递的并行编程环境m p im p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是目前最重要的一个基于消息传递的并行编程工具，它具有移植性好、功能强大、效率高等许多优点，而且有多种不同的免费、高效、实用的实现版本，几乎所有的并行计算机厂商都对它提供支持，成为了事实上的并行编程标准。m p i 目前已经在p c w i n d o w s 、所有主要的u n i x工作站以及并行机上得到实现。这就意味着，一个用标准的c 或f o r t r a n 加上m p i 实现的消息传递并行程序，可以不做修改的运行在单台p c 机、单台工作站、机群系统和m p p 系统上，无论这些机器由谁制造，用的是什么操作系统。3 1m p i 的产生与实现1 9 9 2 年4 月，美国o a k r i d g e n a t i o n a l l a b o r a t o r y 的d w a l k e r 首先提出了建立一个基于分布存贮网络的消息传递标准的倡议。同年1 1 月，在s u p e r c o m p u t i n g 9 2 会议上，正式成立了旨在建立一个标准平台的m p i 论坛( m e s s a g ep a s s i n gi n t e r f a c ef o r u m ) ，该论坛不仅包括了许多p v m 、e x p r e s s 等的研制者及并行程序用户，还吸收了许多著名计算机厂商的代表，如c r a y 、i b m 、i n t e l 、t h i n k i n gm a c h i n e s 。随后论坛于1 9 9 4 年5 月，公布了m p i 标准，在1 9 9 5 年6 月又推出新版本m p l l 1 ，于1 9 9 7 年7 月推出了m p i 的扩充部分m p i2 。在制定m p i 标准的过程中，标准的制定者们充分吸收了许多现有的消息传递系统中有吸引力的特点，而不是只取其中一种作为标准。m p i 的标准化工作涉及到大约6 0 个国家的人员，他们主要来自美国和欧洲的4 0 个组织，其中包括大多数主要的并行计算机生产厂商，以及来自大学、政府实验室和公司的研究人员。m p i 不是一个独立的自包含系统，而是建立在本地并行程序设计环境之上，其进程管理和y o 均由本地并行程序设计环境提供。例如，m p i 可以建立在i b ms p 2 的p o f j m p l 之上，也可以建立在i n t e lp a r a g o n 的o s f n x 之上。除了这些商业版本的m p i 实现之外，国际上的研发团体还开发了一些免费版本的m p i 实现，主要包括以下几种。1 m p i c hm p i c h 1 明是目前一种最重要的m p i 实现，它可以免费从h t t p ：w w w - u n i x m c s a n l g o v m p i m p i c h 取得。更为重要的是，m p i c h 是一个与m p i - 1 规范同步发展的版本，每当m p i 推出新的版本，就会有相应的m p i c h 实现版本。目前m p i c h 的最新版本是m p i c h - 1 2 5 ，它支持部分m p i c h - - 2 的特征。2 l a ml a m 1 1 1 ( l o c a l a r e a m u l t i c o m p u t e r ) 也是m p i 标准的一个免费实现，由美国o h i os t a t eu n i v e r s i t y 开发，它当前的最新版本是l a m m p l 6 5 9 ，可以从h t t p ：w w w 1 a m m p i o r g d o w n i o a d 下载。l a m 为程序的开发提供了良好的并行调试功能，并能够有效支持异构的计算机网络系统。3 c h i m pc h i m p 1 2 1 是e d i n b l 】r 曲大学开发的另外一个免费m p i 实现，是在e p c c( e d i n b u r g hp a r a l l e lc o m p u t i n gc e n t e r ) 的支持下进行的，从卸：t i p e p c c e d a c u l d p u b p a c k a g e s c h i m p r e l e a s e 可以免费下载该软件。3 2m p i 的消息一个消息可以比作一封信。需要定义消息的内容( 即信的内容) ，还需要定义消息的发送者或接收者( 即信封上面的源地址，接收地址) 。前者称为消息缓冲( m e s s a g eb u f f e r ) ，后者称为消息信封( m e s s a g ee n v e l o p ) 。在m p i 中，消息缓冲由三元组 来标识，而消息信封则由三元组 来标识。用三元组来标识消息缓冲和消息信封，使得m p i 消息可以表达更为丰富的信息，因此m p i 可以比其他的消息传递如p v m ，提供更强大的消息传递功能。3 2 1 消息数据类型每个m p i 消息都有相应的数据类型，m p i 通过引入消息数据类型来解决消息传递过程中的异构性问题以及数据不连续问题。m p i 的消息数据类型可以分为两种：预定义数据类型和派生数据类型。1 预定义数据类型m p l 支持异构计算( h e t e r o g e n e o u sc o m p u t i n g ) ，它指的是由不同计算机组ir 成的系统( 如工作站网络) 上运行应用程序。m p i 通过提供预定义数据类型来解决异构计算中的互操作问题。针对不同语言的绑定，m p l 分别建立了预定义数据类型和语言之间的对应关系，目前已经包括了c 和f o r r a n 中的所有基本数据类型。2 派生数据类型派生数据类型是指允许定义由数据类型不同且地址空间不连续的数据项组成的消息。派生数据类型可以用类型图来描述，这