（系统分析与集成专业论文）机群环境下二维傅立叶变换的并行算法研究.pdf

摘要 并行f f t 是解决大数据量f f t 运算耗时过久的重要途径，在p c 机群上实现 并行f f t 是一种低成本、高效率的解决方案。本论文首先介绍了并行计算的基本 理论，然后介绍了计算机机群系统和m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 消息传 递机制。在此基础上，建立了基于w i n d o w ss e v e r2 0 0 3 和m p l 的p c 机群实验环 境。m p i 并行程序设计与传统程序设计存在显著差异，本文讨论了在机群系统上 进行m p i 并行程序设计的过程和方法，并且具体用于实现m p i 并行d f t 运算。讨 论了p c 机群环境下m p i 并行一维和二维f f t 的编程实现，并利用建立的平台， 对并行算法进行了测试，比较了并行算法和传统运算耗时的差异。最后，根据理 论研究和实际测试的结果，总结了利用p c 机群系统进行并行f f i 运算和并行二 维f f t 运算的可行性，得出了一些有意义的结论和方法。 关键字：p c 机群消息传递肿i 并行算法f f t 2 一df f t i l l a b s t r a c t a p a r a l l e lf f 于i st h ei m p o r t a n tm e t h o dt oe n h a n c et h es p e e do f m u l t i p l ed a t af f to p e r a t i o na n di st h el o w - c o s t ，h i g he f f i c i e n c yp r o j e c t p r o c e e d e di nac l u s t e ro fp c s t h i sp a p e rf i r s t l yi n t r o d u c e dt h eb a s i c t h e r a p yo fp a r a l l e la l g o r i t h m s ，a n dt h e nd i s c u s s e dt h ec l u s t e ro fp c s s y s t e ma n dm p i a c c o r d i n gt ot h i st h e o r y ，a na p p r o p r i a t el a b o r a t o r y e n v i r o n m e n t ，as i m p l ec l u s t e ro fp c sb a s e do nw i n d o w ss e v e r2 0 0 3a n dm p i ， w a se s t a b lis h e d t h e r ea r eg r e a td if f e r e n c e sb e t w e e nt h en e w l yd e v is e d m p ip r o g r a m m i n gm o d ea n dt h et r a d i t i o n a lo n e s e c o n d l y ，t h i sp a p e r d i s c u s s e dt h em e t h o dh o wt oe x e c u t et h em p ip a r a l l e lp r o g r a m m i n gi n c l u s t e re n v i r o n m e n ta n dh o wt oi m p l e m e n tt h eo n ed i m e n s i o n a la n dt 胃o d i m e n s i o n a lm p ip a r a l l e lf f tp r o g r a m s t h et i m ed i f f e r e n c e sb e t w e e n p a r a l l e lp r o g r a m sa n dt r a d i t i o n a lo n ew e r ea n a l y z e da f t e rt h i sp r o g r a m w a st e s t e d 。f i n a l l y ，f r o mt h et h e o r e t i c a la n dp r a c t i c a ls t u d y ，t h e f e a s i b i l i t yo fp r o c e e d i n gp a r a l l e lf f ta n d2 - df f ti nc l u s t e ro fp c sw a s d i s c u s s e da n ds o m em e a n i n g f u lc o n c l u s i o n sa n dw a y sw e r ea l s oa c h i e v e d 。 k e y w o r d s ：c l u s t e ro fp c s m e s s a g ep a s s i n g m p ip a r a l l e la l g o r i t h m s f f t2 - df f t 湖北大学学位论文藤刽惺声龋帮使用授权说鞠 原创性声明 本人鬈鬟痔鹾：辫里交熬学整谂文，是零太在导师戆掺零下，羲立进行礤究 工作所取得的成果。除文中融经注明弓l 用的内容外，本论文不禽任何欺他个人或 集薅鑫经发表躐撰写遗懿裕菇或藏票。露本文麴磷究骰密羹簧贡熬瓣令人帮集 体，均己在文中以明确方式标明。本声明的法律质果由本人承担。 论文 乍豢签名：秀鬟奎k 对闼：扣彩年舞箩基 攀谴论文谴霹授权说葫 本人完全了解湖北大学关予收集、保存、使用学位论文的规定，即；按照学 校要求提交学像论文的印利本和窀子版本；学校有权保存学位论文酌印刷本和电 子版，黉提供霹录检索与阕觉骚务；学接可以采惹影邸、缩露、数字化或其它复 制手段保存论文；在不以赢利为目的前提下，举校可以公布论文的部分或全都内 容。 ( 保密论文在解密厢遵守此规定) 论文豫者签名： 签名醚翅：知w # 年f 月萝基 i i 导筛签名乏墨施导筛签名缈务，毽 签名墨裳洲融胃妒 1 绪论 由于高性能计算机的发展以及其应用的日益广泛，对科学技术以至整个人类 社会都产生了巨大影响，人们越来越清楚的认识到，计算机已经成为理论分析和 实验并列的第三种科学研究手段，并且充当越来越重要的角色。同时，计算机数 值模拟与辅助设计对计算机的性能提出越来越高的要求，为了满足发展的需要， 除了提高元器件的速度之外，系统结构也必须改进，特别是在现有的元器件速度 到达极限时，改进计算机系统的系统结构，跳出元器件速度的物理限制，就显得 更加必要。现阶段，计算机系统结构的改进主要围绕着并行处理技术展开，即增 加同一时间间隔内的操作数量。这样一来，单处理器计算机系统对高性能计算就 不能满足需求。此时，研究发展并行计算机就显得尤为重要。使用并行处理技术， 在并行计算机上设计求解问题的方法称之为并行计算。并行技术主要是用于大规 模、高性能计算的应用领域。 1 1 研究的背景和意义 在计算机学科的图象处理领域以及光学学科光传输领域中离散傅立叶变换 ( d f t ) 有着广泛的应用。在数字信号处理中，信号是用有限精度的数的序列来表 示的，用数字运算来实现处理。而离散时间信号处理既包括了作为一种特殊情况 的数字信号处理，也包括了用其他一些离散时间计算处理样本序列的可能。傅立 叶变换运算由于其运算量十分巨大，实际应用十分困难。c o o l e y 和t u k e y ( 1 9 6 5 ) 所研究出的计算离散傅氏变换的快速傅立叶变换，将计算量从0 ( n ) 下降到 0 ( n l o g n ) ，从而使得f f t 在数字信号处理、石油勘探、地震预报、医学断层诊 断、编码理论、量子物理及概率论等领域都得到了广泛的应用。此后，各种快速 算法不断涌现。但是，随着其应用范围的日益广泛，有些问题需要处理的数据量 非常大，有些问题则要求极快的计算速度，目前的计算速度达不到实际要求。因 此，新的技术应运而生。高性能p c 计算集群以其巨大的存储容量和很快的计算 速度得到了的到了信号处理界的广泛重视，近年来成为了研究热点。如何在p c 并行机群计算机上快速有效的计算离散傅立叶变换成了一个新的研究课题。 并行运算是解决大数据量数值运算耗时过久的重要途径，在p c 机群上实现 并行运算是一种低成本、高效率的解决方案。香港科技大学物理系的l i n u xp c c l u s t e r 计划：2 0 0 1 年用8 0 台1 4 g h za m d 微机实现了6 7 g f l o p s 的实测速度( 理 论峰值为1 8 9 g f l o p s ，g f l o p s = g i g af l o a t i n g - p o i n to p e r a t i o n sp e rs e c o n d ) ， 与2 0 0 1 年6 月的世界第5 0 0 大速度持平，总花费只有1 2 0 万港币。 1 2 国内外现状 目前，实现快速傅立叶变换的串行算法很多，如基一2 的时间抽取算法和频 率抽取算法、n 为复合数的f f t 算法、分裂基f f t 算法( s r f f t ) 、素因子算法( p f a ) ， w i n o g r a d 傅立叶变换算法( w f t a ) ，实序列的f f t 、多维f f t 变换等。 国外围绕快速傅立叶变换的并行计算进行了多项研究和开发美国n e w m e x i c o 大学v a s i l i o sg e o r g i t s i s 等人设计了2 - df f t 程序，可处理5 1 2 5 1 2 个点的图象，其底层通信基于p v m ，将2 - df f t 转化成卜df f t 并行计算，完成 了二维图象的变换。 目前最新的研究成果是由麻省理工学院计算机科学实验室超级计算技术组 开发的f f t w ，f f t w 是计算离散f o u r i e r 变换( d f t ) 的快速c 程序的一个完整集合， 它可计算一维或多维、实数据和复数据以及任意规模的d f t 。在f f t w 中，d f t 的计算由执行器完成，执行器是由许多高度优化的、可组装的子代码模块组成的。 f f t w 有一个规划器，规划器用以根据具体机器的体系结构特点和具体的d f t 宽 度n ，在运行时寻找一种有效的子代码块组装方式，因此使得f f t w 具有很好的 自适应性和很快的运行速度。f f r w 还包含对共享和分布式存储系统的并行交换。 在我国，8 0 年代初就开展了并行算法研究。快速傅立叶变换的并行算法主 要包括：基于s i m d m c 2 ，s i m d b f ，s i m d - c c ，m i m d d m 四种体系结构上的f f t 算法， 它们都是基一2 f f t 算法，算法各有利弊，受体系结构影响较大。 1 3 本论文的主要工作 本文研究了在p c 机群环境中实现并行2 - df f t 运算的相关问题。 论文菌先研究利用现有计算机资源，构建小型的机群系统，建立基于 w i n d o w s 2 0 0 3 霸游i 豹实验环凌。程忿墓确上，分缁7 开发m p i 并行程序赘过程， 并结合快速傅立时变换的特点，设计实现了基于m p i 的并行2 - df f r 程序。并且 在实验环臻中灞试了并行稷序的毪能。 本论文对机群环境作的研究和探索，主要包括以下正作： 第一，对并行计算体系结构进行讨论，通过娥立基予w i n d o w s 2 0 0 3 和m p i 戆并行撬群实验环境，探索霹扩展您规嚣系统静橡建露实瑷方法。 第二，研究了消息传递模式下机群系统并行程序模型以及影响并行程序性能 静鬻素：讨论了m p i 程痔设计熬基零模式帮方法，戳及在m p i 祝群繇凌下歼发并 行糨序的糕架和过程。 第三，给出了视群潆 环境下并行f f t 和2 - df f t 静并行程序实现。 第四，在自行建立的并行实验平台上，对并行f f t 和2 - df f t 程序性能做了 测试。 最后，根据理论硬究耧实际测试豹结鬃，慧缕了利用撬群系绕遴行嵩遮2 一d f f t 运算的可行性，以及分析提出谶一步改进的思路。 3 2 1 并行化概述 并行计算基本理论 并行计算机的发展基于人们在两方面的认识：第一，单机性能不可能满足大 规模科学与工程问题的计算需求，而并行计算机是实现高性能计算、解决挑战性 计算问题的唯一途径：第二，同时性和并行性是物质世界的一种普遍属性，具有 实际物理背景的计算问题在许多情况下都可以划分成能够并行计算的多个子任 务。针对某一具体应用问题，我们可以利用它们内部的并行性，设计并行算法， 将其分解成为互相独立但彼此又有一定联系的若干个子问题，分别交给各台处理 机，而所有的处理机按并行算法完成初始应用问题的求解。例如，根据几十个常 用应用软件的统计，6 0 一8 0 的标量计算可以被向量化，而9 0 左右的串行计算 可以并行化“。 实现或提高计算机系统的并行性，可以通过时间重叠、资源重复和资源共享 等技术途径来实现。 时间藿叠( t i m es u p e r p o s i t i o n ) 是在并行性概念中引入时间因素，让多个 处理过程在时间上相互错开，轮流重叠的使用同一套硬件设备的各个部分，以加 快硬件周转而赢得速度。 资源重复( r e s o u r c er e p l i c a t i o n ) 是在并行概念中引入空间因素，通过重复 设置硬件资源来提高可靠性或并行性能。在结构上，采用多操作部件和多存储部 件，早期受限于硬件价格，资源重复是以提高可靠性为主，随着硬件价格的减低， 资源重复利用被大量用于提高系统的速度性能，成为提高并行性的重要方面。 资源共享( r e s o u r c es h a r i n g ) 是时间顺序轮流地使用同一套资源，包括c p u 、 主存、外设硬件资源和软件、信息资源，以提高其利用率，从而提高整个系统的 性能。 2 2 并行计算机的分类嘲 并行计算机即并行计算环境是并行算法赖以生存的物质基础，它们的发展直 接影响着并行算法的设计和实现。 1 9 6 6 年辕j 。f l y n n 掩密了著髭靛f l y n n 分类法，搬撼指令流与数摇演l 方 式的不同将计算机系统分类。指令流指机器执行的序列：数据流指指令调用的数 据净梦| j ，包攒输入数据和中澜结果；掇此，w 以把诗算视系统分成： 单指令流单数据流s i s d ( s i n # 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 ) ； 单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o ns 仃e a mm u l t i p l ed a t as t r e a m ) ； 多指令波攀数攒滤m i s d ( m u l 蛀p mi n s t r u c t i o ns 智e a ms i n g l ed a t as 在e a m ) ； 多指令流多数据流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 i m d 登翻m i e ) 黧著彳亍诗算祝是研究襄帮发静圭流。 2 2 。1 向量处理s i m d 型并符梳 蠢量处毽辊是典鍪豹s i m d 并行梳。淘黧视豹特点是剩翔流永线的搋念，把 一个计算部件拆成几段，在流水线的每一部分操作一个子功能，通过时间重叠实 现并行加速，其代表机型为t r a y 一1 向量机。s i l l d 类攘并行机对并彳亍计算机的发 展起到了重要攘动 乍用，健出于微处理芯片技术的发展，攀处理器的性能郝非 常强大。9 0 年代以后，并行机均朝着m i n d 方向发展。s i m d 类型并行机基本退 基了掰史舞螽。 2 2 。2 共事存储m i m d 并行多处瑾枫 共享存镰m i m d 劳抒多楚理捉将多台处邂祝逶过曩违嬲终共享个凌戆内 存空间，并通过该内襻空间米实现处理机之间的协调。内存空间也可以由多个存 德器模块梅袋。在蘧类并嚣梳中，每螽筵瑗钒霹戳魏幸亍穗露簸不同豹指令滤，可 以直接访问到所有的数据。处理机间的通信煅借助主存来实现的。 该系统静优点是并行纯的效率较高，稻对容易编写并行程序。由于处理器间 传送数据经由共享存储器进行，延迟较小。因此，容易设计出小粒度、负载平挺、 高效的并行程序。其缺点是系统中处瑷器太多时，对获享内存的竞争会严重影响 效率，霹戬使援裹速缓渖存绩( c a c h e ) 释交叉开关存镰( c r o s s b a rs w i t c h m e m o r y ) 等技术，来减少竞争现象。但这些技术依然有一些难以克服的缺点，如高速缓冲 存储技术：系统中每一个处理器有一个独立的高速缓冲存储模组，以减少处理器 对共享内存的访问，但在共享内存中写入某内存单元，应同时更改存在各高速缓 冲存储中相关单元的内容，称为缓冲存储一致性问题，虽然已经有多方法解决此 问题，但仍无可避免地对系统性能产生负面影响。通过上述措施可以减少竞争， 但处理器的数目一般不能超过1 0 0 个，从而影响此类系统的发展。 2 2 3 分布存储m i m d 并行多处理机 为了突破共享存储并行机系统中处理器与内存系统间的瓶颈，分布存储 m i m d 并行多处理机器系统应运而生。该系统中每台处理机有自己的局部存储器， 构成一个单独的节点，节点之间通过互连网相互连接。每台处理机只能直接访问 局部内存，不能访问其它处理机的存储器，它们之间的协调以消息传递的方式进 行。 与共享存储器并行机比较，分布式存储并行机具有很好的可扩展性，可以最 大限度地增加处理机的数量，是目前实现超大规模科学与工程计算的唯一途径。 但由于它的每个节点机需要依赖消息传递来相互通信，而消息传递对编程者是不 透明的，所以，分布存储并行多处理机系统的编程较共享存储复杂。 分布存储m i m d 并行多处理机其主要有m p p 系统和c l u s t e 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 s ) 系统是最常见的并行系统，由成百上千 的功能相同的处理机通过互连网络连接而成，且往往都采用专用结构。m p p 的优 点是拥有良好的伸缩性，只要为系统增加更多的结点，便能增加系统的计算峰值， 现时市场上大部分的高性能计算机都是m p p ，如i n t e rp a r a g o nx p 5 ，c r a yt 3 d 、 国产y h 一3 和曙光1 0 0 等。但是，m p p 的缺点是较难为其开发并行程序，程序员 需要根据系统的特点来平衡并行程序的粒度和结点间通信量。 计算机集群也叫计算机机群。是指把两个以上高性能的工作站或高档次p c 用互连网连接在一起，并配以相应的支撑软件，构成一个分布式并行计算机系统， 结点问的消息传递和程序执行均是并行化的。具有并行计算性能而且可以能加速 作业的执行，这是和一般的网络系统不同的。c l u s t e r 的互连大多采用通用局部 网，如e t h e r n e t ，f d d i ，m y r i n e t ，a t m 等。集群系统包括工作站群n o w ( n e t w o r k o fw o r k s t a t i o n s ) ，p c 机群、全对称s m p 机群等。 2 3 并行计算机的应用和发展 作为并行计算的物质基础的计算机硬件在不断的更新。最初是在单处理机内 部增设流水线处理部件、多功能单元、关联存储器等来开发指令级的并行性，为 了进一步提高并行度，必然导致向开发程序级和任务级的并行性的多计算机系统 发展。把多台计算机联合起来，互相配合，各尽其能。利用功能专门化、多机群 和网络化这三种基本技术向着异构型多处理机系统，同构型多处理机系统和分布 式处理系统发展。 1 9 7 2 年在美国诞生了世界上第一台并行计算机i l l i a cn ，其为8 x 8 = 6 4 的阵 列机。但是它的加速比还是满足不了求解超大规模计算问题的要求，因此9 0 年 代，开始研究大规模并行机与网络并行机群。 并行计算机是一种高性能的超级计算机，其运算速度应达到每秒万亿次、百 万亿次甚至于更高，以此来解决诸如气象模拟、流体分析、污染分析、人类染色 体、燃烧系统、海洋环境以及核试验模拟等一系列的问题。 上述种种应用，早己不仅仅用与实验室，而且已经有了实用产品。美国于 1 9 9 1 年度开始执行“高性能计算与通信( h p c c ) ”项目，目的是解决一批重要和 对科学技术有挑战性的问题，其中的两个基于并行计算的问题是 ( 1 ) 高性能计算机系统( h p c s ) ：内容主要为并行计算机系统研究。 ( 2 ) 先进软件技术与算法( a s t a ) ：内容主要为高性能计算的软件研究。 目前，高性能计算的发展应用可分为以下两丈类： ( i ) 面向高端用户，追求细粒度、超高速的大规模并行计算机系统，由数百 以至更大多数目的c p u 组成，如以下的系统： 陈列处理机，如d a p 向量并行机，如c r a y 一1 、国产银河一1 等 s i m d 并行机，如t h i n km a c h i n e 公司的c m 2 ，m pl ，m p 2 等 大规模并行机( m p p ) ，如i b ms p 2 ，i n t e lp a r a g o n ，c m - 5 、国产曙光 机等 这类系统由于其价格昂贵、使用不方便，因此主要面向高端用户，难于普及， 不利于开发这类系统的软件及相关的并行算法。 ( 2 ) 基于网络技术的并行计算环境 此类系统一般由p c 微机通过网络构建而成。一般微机的平均使用率只有3 0 左右，随着网络技术高速发展，性能在过去几年高速增长。由大量计算机通过网 络组成的虚拟并行计算环境，其能力足以进行高性能计算，其优点为可伸缩可扩 展性强、能利用现有资源组建并行计算环境、价格便宜、系统灵活等。这类网络 并行多计算机系统中，各台计算机具有自己的存贮器地址空间，通过消息传递 ( m e s s a g e p a s s i n g ) 来进行并行计算。典型的实现方式有： 扩充现有的顺序高级语言的语法和保留字来处理消息传递( 如 c ，c + + ，f o r t r a n 扩展为并行c ，c + + ，f o r t r a n ) 设计专用的并行程序设计语言( 如o c c a r n 并行语言) 利用现有的顺序高级语言并提供用于消息传递的外部函数库( 如 e x p r e s s ，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 - p a r a l l e lv i r t u a lm a c h i n e ) 2 4 物理问题的并行求解过程 一个物理问题并行求解的最终目的是将该问题映射到并行机上，而映射过程 是通过不同层次上的抽象来实现的。一般的映射模型如图2 - 1 所示。 图2 1 问题的并行求解过程图 2 5 荠符计算模型 并行计算模型( 也称为犏稷模粼、类型性棋烈、概念性模型娥瑕想化模型) 是籀将备静势行橇( 至少楚蘩一类并存筑) 蠡冬基本褥鲢麴取貔来，形藏一令憝予其 髂势器枧之上鳇蘩蒙劳嚣静冀秘，类叛予颓彦谤舞戆v o r tn e u m a n n 壤溪。 著嚣簿法的设汁霹菇瓢瓣令辩痰遴行：( i ) 藏摊并行诗舞模墅没计井 亍舞法， 然朦将冀映射到具体并行枫中：( 2 ) 直接基予具体并符机遴毒亍莠行籁法的设计与 分析。显然，相比于第二种并行算法设计而亩，并行计算援型起到了屏蔽了并行 辊囊瑰缨第壤樽浚诗菸募法霹姨瓣戮一类势行税上，县畜受强豹擞愈力。 爨髂褥吉，势嚣诗算耩豢鹣主蘩箨蔫蘩下： 为并哥亍算法豹研究掇供了一令毙较通用静镌震墓稿。 为并行算法的设计与矜析掇供了一种简单、方便的框架。 穗褥设诗静并行冀法舆霄一定豹垒禽力，萄以适弱予多静舆体豹菸行飘。 迄今努止，基疆毒多耱劳行诗箕模鳌窿在，热 嚣麟嫫墼、l o g e 模鍪、e 3 模麓、b d m 模型等，但慕串的每一种只抽象了实际并行祝靛一个或几个方藤，隧 无i 孛滚簇予瑟青弗行极“。 2 。6 并行道蓿专露步 进行弗箨诗冀辩，箍璨嚣之鬻豹数据潇庹、橹输，需妥透信释锩。基予共享 存储的并行计算模魁的通俗怒依靠全局存储变爨毙成的，所以其通储汗销并不是 裰大，毽楚茬基于分毒存鼹特剃是满意传遂酌并行诗算模爨上，数播菇避淫器之 藩逡蘧、传埝霹戆麓费戆辩鬻娶羲蕊多。 并行系统执行络定算法的过程中，出现莱些她遴祝的一些计冀必须在其诬处 理爨蛉一魑计算完成之惹劣熬进行时，丽步是必袋瓣，霹步就是供溅_ 醛：类情嚣褥 以砸确实施。同步瓣有两方灏姻开销：一魑实现间步一般簧求对所有处理机作某 蛰羧奎，在魏是要凌羹瓣瓣戆；二是募鳌筵溪器躐是嚣骞懿理器嚣麓戆阕嚣，等 待礁诲继续避荦亍诗冀斡滚患。霹翦已经育各稀技术来实现阏步，包耩歙 宰技术与 硬件支持”。 2 7 并行算法的性能度量 对于一个给定问题，如果设计了一个新的并行算法，就必须对该算法的性能 进行评价。性能度量的目的就是为并行算法的设计与分析提供一个统一的衡量标 准。在当前并行计算环境中，并行算法的性能度量一般涉及到求解问题的规模与 分类、具体并行机的性能、影响算法的关键因素、并行算法评价准则等方面的问 题。本节对度量并行算法性能的一些基本概念进行介绍。 ( 1 ) 运行时间。并行算法的运行时间是指算法在并行计算机上求解一个问题 所需的时间。即表示算法开始执行到执行结束的这一段时间。如果多个处理机不 能同时开始或同时结束时，则算法的运行时间定义为：从最早开始执行的处理机 开始执行算起直到最后一台处理机执行完所进程的时间。在计算机上实现一种算 法之前，通常需要对其运行时间进行理论分析。对并行算法运行时问的分析包括 估计它在最坏情况下的计算时间和通信时间，其中的计算时间是用算法所需执行 的基本操作数或步数表示，通信时间则是根据计算得到的通信次数和每步的通信 量，依据并行计算模型计算得到。理论分析得到的算法运行时间常表示为问题输 入规模的函数。对于一个规模为n 的问题，算法的运行时间可用r ( 1 3 ) 表示，它 是输入规模n 的函数。 ( 2 ) 并行度与粒度。算法的并行度d o p ( d e g r e eo fp a r a l l e l i s m ) 是指该算 法中可并行执行的操作数。若处理机资源无限，则算法的并行度也可以理解为可 以利用来做并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程 中保持并行度不变，所以更准确的说法还应该加上时间范围的限制，即在某时间 范围内的并行度。从直观意义上可以说，并行度是刻画一个并行算法的“并行程 度”的量，它反映了软件并行性与硬件并行性匹配的程度。显然。与算法并行度 有关的概念是粒度，一般而言，大的粒度意味看能独立并行执行的是大任务，算 法的并行度小，小的粒度意味着能独立并行执行的是小任务，算法的并行度大。 ( 3 ) 加速比和效率。加速比和效率是最传统的并行算法评价标准，它们体现 了在并行机上运用并行算法求解实际问题所能获得的好处。 并行算法的加速比定义为： 耻 式中，t ，一最优串行算法在单处理机上的运行时间：t p 并行算法使用p 台处理 机的计算时间 并行算法的效率定义为： 。s ， 坼2 言 式中p 为处理机台数。 如果按照某种条件，如保持每台处理机的计算规模，并行算法加速比斗与处 理机的台数成正比，则称该并行算法在该条件下，在该并行机上具有线性加速比。 在某些条件下，若s p p ，则称该条件下，该算法具有超线性加速比。 ( 4 ) 可扩展性。可扩展性是设计高性能并行计算机和并行算法所追求的另一 个重要目标。由于并行系统的性能与系统规模、问题规模、算法内在并行性以及 由于通信、同步和进程创建等引起的系统开销等因素有关，而这些因素对并行系 统的结构和应用程序的可扩展性都有影响，因此可扩展性也是衡量并行系统性能 的一个重要指标。衡量系统可扩展性的方法有很多，比较直接的定义为并行系统 的性能与处理机数目成线形比例的关系。 2 8 并行算法设计应注意的问题 根据并行化的特点分析，无论采用什么方法进行设计并行算法，以下几点都 是决定并行效率的重要因素： 第一，挖掘并行性。针对一个具体问题设计其并行算法时，可根据求解该问 题的串行算法出发，分析其明显的并行性，加以并行化，并应该利用相关知识， 深刻挖掘问题内在的可并行性。 第二，并行算法依赖并行的环境。并行算法与进行并行的环境密切联系，一 个并行算法在不同的并行系统上的差别很大，所以说，要根据并行的环境有针对 性的设计并行算法。 第三，考虑通信开销。通信开销是一个必须考虑的因素，因为有时通信在真 个算法中占用时间的比例很大，特别是在分布存储的并行环境下，要尽量减少通 信开销，才能设计出高效率的并行算法。 3 p c 机群系统及m p i 消息传递 3 。1p c 机群系统 瓤扩展弗牙p c 枧群是现在超级诗冀的一秘解决方案，魄是嚣 ；蓼最爵、簸经 济的一种方案。机群系统是利用高速通用网络将一组商性能正作站或高档p c 机， 统一溪麦，协调赴瓒，实现麓效著簿经理静系缓。冀蕤本诗舞节轰霹疆是普通徽 机，而分布操作系统和计算软件是开放的，可以免赞下载。 放结构帮结点阖瀚逶信方式来看，它属予分布存储系统，主要稠用消息传递 方式实现各熏机之间的通信，由建立在一般操作系统之上的并萼子编稳环境完成系 统的资源管避及相互协作，同时也屏蔽工作站及网络的异构性。对程序员和用户 来说，机群系统是一个整体憋并行系统。辊群系统串的圭楗秘耀终可数是因捻豹， 也可以是异构的。目前己实现和正在研究中的机群系统大多聚用现有商用工作站 彝运麓l a n 羯终，这群甄霹敬缩短嚣发嚣翳，又霹激程矮最凝静畿鲶瑷器羧零。 大多数机群系统的并行编程环境也是建立在一般的u n i x 或w i n d o w s 操作系统之 上，爆量穰蔫商瑟系统静研究成莱，减少系统的开羧与维护赞用。 从应用的角度看，r i s c 技术、腿络技术j 并行缡程环境的发展使得机群系 统这一新的并行处理系统形式正成为当前研究的热点”。 囊于r i s c 按拳鹃发震，健褥徽簸瑾器静性缝不颓提商。离挡芯片静运冀能 力平均每年增长3 0 ，价格不断降低，直接使用商用正作站城p c 机作为运算结 点的钒群系统在缩熹穗能上黥够简处理器韵发展保持溺步增长。 网络技术的进步使得松散耦合系统的通僚瓶颈逐步得到缀勰。隧终传辕速度 的提高，有效地提高了应用程序之间的通信带宽。快速以太网的速率为1 0 0 m b p s ， a t m 局城网鲍磐宽达戮1 5 5 m b p s ，6 2 2 m b p s 懿产熬毪已经磅裁成功。瑟嚣关搜拳茨 发展则大幅度地降低了传输延迟，使褥许多高速局域网能和m p p 中的专用互谶网 络夔瞧耱稳当。 并行编程环境的开发使得新编并彳亍程序或改写串行程序烫为容易。著行_ 敷用 程痔的开发和不丽系统之闽的可移植往一壹怒传统并行系统能否广泛应用的一 个关键。由于机群系统的发展，近年来出现了多个并行程序开发及运霉亍系统，毙 如p v m ，m p i ，e x p r e s s ，l i m a ，p 4 等。这些系统的适应平台非常广，应用程序 在这些系统上静可移禳毪较好，特掰是p v m 和m p i ，由于英开放强，受妥许多大 学和研究机构都有广泛的擞视，穰这些环境下开发了许多应用程序。 运用机群系统迸行并行运算酌研究，主要原因是它与传统的并行处理系统相 比钶以下几个明显啦特点： ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站和道用l a n 网络， 使缝点主极及系统餐理稿鼹骞曩，屡可靠羧蹇。矛发夔重杰在逶倍农著牙缝程琢 境止，既不用重新研制计算结点，又不用爨新设计操作系统和编译系统，节省了 大豢豹研鬣羁寺漓，缩短了开发竭鬻。 ( 2 ) 系统价格低。由于嶷产批擞小，传统巨型机或m p p 的价格都比较昂贵， 往往要凡酉万刮上千万美煎。丽构成枫群的工作站或高档p c 视是批量生产的， 因而售价较底。由i 鲢十台或几十台工作站缝成的机群系统霹以满足姻当多数应用 的辩求，且价格较低。 ( 3 ) 节约系统炎。由予壤嚣系统瓣结毒奄毙较灵溪，可以犍不嗣髂系缕糖，不 同性能的工作站连在一起，这样就w 以充分利用现有设备。从使用效率上糈，机 群系统戆资源零j 溪率毽魄攀狡系统凄意褥多。u c b e r k e l e y 计算飘系t 0 0 多台工 作站的使用情况调焱表明，一般单机系统的使用率不到1 0 ，而机群系统中的资 源利用率可达到8 0 左右9 。另一方面，即是用户设备更新，原有的一些性能较 低竣型号较l 霹懿援；爨在撬瓣系统参爨霉发撵终爰。 ( 4 ) 系统扩展做好。从规模上说，机群系统大多使用通用网络，系统扩展容 荔；觚经麓上说，对大多数串、藉羧度豹势行应蔫都有较嵩豹效率。 3 2 橇群环境并行算法靛设诗 对手稳霹静诗舞模墅，霹疆有雾耱不闲鹣并行算法亲擦述帮刻燕。宙予并于亍 算法设计的不同，w 能对瑕序的执行效率农很大影响1 1 1 m 耵。 并行算法基本怒随着并行机的发展而发展的。不同的并行算法是根据问题类 别瓣不固巍并毒亍援髂系缝掇熬特意 嚣设诗翳，一个好懿势露算法魏簧缀努懿嚣琵 并行计算机硬件体系结构的特点，又要反映问题内在的并行性。 对于机群环境，设计并行算法的思路相比传统计算环境，设计思想有了很大 的不同，个很重要的原则就是设法加大计算时间相当于通信时间的比重，减少 通信次数。这是因为对于机群系统，一次通信的开销远远大于一次计算的开销， 因此要尽可能的降低通信的次数，或将几次通信合并为一次通信。 图3 1 简单描述了机群系统s p m d ( s i n g l ep r o g r a mm u l t i p l ed a t a ) 并行算 法设计的一般模式。 图3 1 机群系统s p m d 并行设计模式 前面已经分析得出，机群系统的效率主要为通信开销所制约。如果能实现计 算和通信的重叠，将会大大提高整个程序的执行效率。图4 - 2 描述了计算与通信 重叠的s p m d 并行算法的设计模式。 r j ， ， r ，、 墟甜 j ， j ； ， 一 7 t r ， r 、 ，、 ， 通信 、 ， j ， l lk 、，r ， r ； ，、 ， 通信 、 ，j ， ， 、_ 一一一一， 计算与通倌蚺重叠邮丹 图3 2 计算与通信重叠的s p m d 并行计算模型 3 3 消息传递机制 消息传递是并行编程模型的一种重要模式。所谓消息传递就是指并行执行的 部分之间通过消息传递来交换信息、协调步伐、控制执行。消息传递一般是面向 分布式存储结构，但是它也可以适用于共享存储的并行机。消息传递为编程者提 供了灵活的控制手段和表达并行的方法，灵活性和控制手段的多样性，也是消息 传递并行程序能提供高的执行效率的重要原因。 在编程设计的级别方面，消息传递机制属于低级别的设计模型。这是因为， 消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并行执行部 分之间复杂的信息交换和协调、控制的任务交由编程者，这在一定程度上增加了 编程者的负担。虽然如此，消息传递的基本通信模式是简单和清楚的，学习和使 用并不困难。在目前，大量的并行程序设计使用的都是消息传递并行模型。 3 4m p i 系统简介 并行程序日益增强的简易性和灵活性增加了它对于科学家或工程师的吸引 力。在众多的并行程序库中，应用较广泛的有消息传递接口( m p i ) 标准和并行 虚拟机( p v m ) 环境。p v m 是o a kr i d g e 国家实验室和t e n n e s s e e 大学在1 9 8 9 年开 发出来的：m p i 诞生于数年之后，由几所大学和国家实验室出于创建消息传递库 标准的目的共同开发成功1 1 钔。 对m p i 的定义，可从以下三个方面来认识： ( 1 ) m p i 是一个库，而不是一门语言。m p i 库可以被f o r t r a n 或c 语言调用， 他遵守语言语法中对过程或函数的调用规则。 ( 2 ) m p i 是一种标准或规范的代表，而不是特指某一个对它的具体实现。现 在，几乎所有的并行计算机制造商都提供对m p i 的支持，可以在网络中免费得到 m p i 在不同并行计算机上的实现，一个正确的m p i 程序，可以不加修改的在所有 并行机上执行。 ( 3 ) m p i 是一种消息传递编程模型，并成为这种编程模型的代表和事于上的 标准。m p i 虽然很庞大，但是它的最终目的是服务与进程间通信这一目标。m p i 的标准化开始于1 9 9 2 年4 月。在1 9 9 2 年1 1 月推出了m p l l 0 ，并在1 9 9 3 年2 月完成修订版本。1 9 9 5 年6 月推出了m p i 的新版本m p i i 1 ，为原来的m p i 作了 迸步的修改、完善和扩充。1 9 9 7 年7 月，在对m p i 做了重大扩充的基础上， 又推出了m p i 的扩充部分m p i - 2 ，而把原来的m p i 各种版本称为m p i 一1 m p i i 目前已经基本成熟稳定。m p i - 2 目前已经出现实验测试性版本( 如艘i c h 2 ) ，但还 没有完整懿正式舨本“”。 m p i 的特点概括来说有三方面：较高的通信性能；较好的稔序可移值性：强大 的功能。具体来说，包括以下几个方面： ( 1 ) 通用性：m p i 是可移植的标准平台，其通讯单元包禽上、下义和组的信息， 以傈证消息传递的安全性。 ( 2 ) 点慰患逶讯：m p ie 有效地管理灌爨缓存区，其有结擒化缓存、扩充数据 类型及异稳健，m p i 异步撬行辩能傈护餍户韵箕它软俘不受影晌，能实现完全的 异步通信。立郢发送与接受可完全与计算覆盖进行。 ( 3 ) 数据汇集方式：具有内定和用户自定义的数据汇集操作方式，可对大量数 据进行躲体传输，可直接馘依拓扑结构定义子组。 ( 4 ) m p i 的实现方式多样化，同一编程界颟可有多种开发正具，具有厦向应 用的信息传递拓扑结构：内定支持阙格靼图据扑结构。 ( 5 ) 良好的操馋环境：典有差错控铡功能m p l 2 在i o 、主动淡患、进纛痞动、 饕态进程控赘等方覆有进一步增强m p i 还有在x 密盈下逡行的m p i c h 敝本。甭 户珂戳在x 窗翻下阁u p s h o t 或n u p s h o t 壹观地考察m p i 藏用程序运行过程中各 箍疆器之闯的同步、计算、消患发送、接收等情况，从而为程序的修改提供依据。 3 5m p i 的通信模型 分布存储环境下，消息传递是多个并行任务之间沟通的桥梁。m p i 消患传递 的灵活性也体现在通信机制方预。并行程序设计者可阻根据通信需求，选择合适 的通信方式，实现商效率的消息传递。m p i 提供了点到点通信葶全局通信瓶种通 信形式 1 6 】。 3 5 1 点到点通信 辩予源和目的任务之间的直接通信，m p i 掇供了点到点的发邀和接收灏数。 受交获送黎柽务褥鼗撼款入弱发送缓薛区，发送缭疆救鼗攥黪特定霾耩强务，嚣 者有捆碰豹接收缓冲区。点列点酌通信有磺辩发送籀接收方式：戳塞和非隧塞。 阻塞发邀酌完成意味着数精甚l 拷贝出缓冲区，即通信缓冲鹾可堂新分配。阻塞接 收黝凳成意味善至来的消息墨拷煲入甩户接收缓冲医，即接收方邑碍啦使惩+ 但 是，发送魏宠或并不意昧饕一个莲酝豹接竣溅发燕，发送静漩惑霹黥被缓存在系 凌麓缓渖嚣孛。这撵，发送哥在篷辩攘渡发热之蓊突藏。蓦遥塞搽馋可荔锭褥诗 算与邋信重叠( 必须有系统硬件支持) ，b l p i 的q 阻塞操作盛即返嘲一句柄，这不 意绦辫数据已经拷援凄发送缓狰嚣( 或数据麓撩炙入用声援狡缓摊灏) ，该筒柄可 用来栽逶当的对候宪成( m p i - w a i t ) 蠛检测( 凇i - t e s t ) 对应的嚣阻塞操作。 m p i 摄嵌美舂疆下落义翡阻塞秘霉疆塞发送： 榕壤发送：发遴搡 乍以在耜皮麴接收髓爝发生，发送宠戏剿教送者缓冲医 可用： 羧绻发送：发送搽终嫂浅枢应黪接牧发生瓣才靛发出，獒突艘劐发送嚣缓洚 蘧惩： 麓步发送：发送搽传辩在衽应懿接浚蒋爱淡妻，毽蔹在接收毙成看才送霾( 竞 成) 。 图3 - 3 摇述了点蓟廉遗情的一般形式。 鞋囊发滋瓣寒接裁 厂、 数据发遴 k 厂 ， r ( 塑) 趱回 趱回 非蔽塞接收 嚣艇塞袭邀 数据岽攘浚 回 k 口 邋同 螺同 鬻争3m p i 中煮戮患通傣 3 5 2 通信器 m p i 的个关键特征就疑通信嚣，以对爨形戏脊在，作为邋信搽作的附加参 数。遴镶器为开发漤惠建遴程廖提供了模块仡支撩，获瑟强毒力蟪支持嚣菱筹 亍 瘴和大规模代码。遴傣器的概念来趣予z i pc o d e 秘c c l 皎全鼹邋德。在m p i 中， 进程以缎内的相对r a n k 来标识，通信器参数剡说鞠所涉及的进程组，使用该通 信器的邋馕操作限制在该遴程缀的进程之阗。送榉，一缝进程集上黝痒代硝被翅 于勇一缀避糕集对，疼代麓蠢甓改动，瑟只要黧定义攥述该滋翟煞酌逶售嚣。每 一拿遵傣器定义了一令难黪进程缀逶售上下文。赉土下文窝嚣潮溪惠懿t a g 一起来谶一步区别不同进獠上下文的县有同个标识的消息。上下文由系统严格 警理，趱瘸户是逶羁的，霄力缝谦澄了津载璐躺溺患透信互不予魏。m p i 撼供了 各耪枫镶耀予创建和管爆逶傣器。程初始豫黠预定义个遥傣嚣 辨；一c 溅洳驿蘸强) ，穗纛黪懑程缢镑含了裙戆豫瓣荐在嚣菸毒进程。 3 5 3 全局通信 鹾p j 麓一缢车富