（计算机应用技术专业论文）基于mpi标准的并行计算平台的设计与实现.pdf

摘要 随着超级计算需求的扩大，人们把高性能计算更多的应用于数据挖掘应 用、图像处理业务、基因测序比对处理等数据处理领域。科学计算的规模迅 速膨胀，使得传统的串行计算已经不能满足要求，从而提出了并行计算的概 念。 并行计算是相对于串行计算来说的，它将进程相对独立的分配于不同的 节点上，由各自独立的操作系统调度，享有独立的c p u 和内存资源；进程 间通过消息传递相互交换信息。但是除了近来逐步完善并走向实用化的数据 流计算机之外，5 0 年来计算机系统结构虽取得重大进展，但并没有发生革命 性的变化，现已实用化的计算机是以冯诺依曼机器为原型，在此基础上加 入并提高并行处理实现的手段和并行处理的能力。 m p i 是1 9 9 4 年5 月发布的一种消息传递接口，是为消息传递程序提供 的标准库【i j 。m p i 以语言独立的形式来定义这个接口库，并提供了与c 和 f o r t r a n 语言的绑定，是目前商效率的超大规模并行计算最可信赖的平台。 目前，i n t e m e t 连接着大量的个人p c 机和各种超级计算机，汇集了大量 的计算资源。为了利用i m e m e t 上广泛分布的空闲计算资源，目前已经有多 个分布式计算项目，比如：s e t i h o m e ，g i m p s 等等。这些项目已经证实了 这种计算模型的可行性。这些系统的资源高度不稳定、用户不可信任、通信 带宽有限、延迟巨大。 本文采用目前国内外较为流行的面向对象系统分析技术，确定了由对象 层、结构与实例连接层、主题层、属性层和事件层构成的静态架构。最后， 给出由静态架构反射出来的用例视图，用于表示系统功能的高层逻辑模型， 实现在计算机集群的网络范围的分布式计算，该系统资源稳定、用户可信、 通信情况优良。 关键词：面向对象；并行计算；l d p i a b s t r a c t a c c o r d i n g t ot h e e x p a n s i o no fs u p e rc o m p u t i n gr e q u i r e m e n t s ，h i 曲 p e r f o r m a n c ec o m p u t i n gh a sh e l p e dp e o p l ei nd a t ap r o c e s s i n ga r e a ss u c ha s ：d a t a m i n i n ga p p l i c a t i o n s ，i m a g ep r o c e s s i n gb u s i n e s s ，g e n es e q u e n c i n gc o m p a r i n g h o w e v e r , c o n s i d e r i n gt h er a p i de x p a n s i o no ft h es c i e n t i f i cc o m p u t i n gs c a l e ，t h e t r a d i t i o n a ls e r i a lc a l c u l a t i o nh a sb e e nu n a b l et om e e tt h er e q u i r e m e n t s ，t h u st h e c o n c e p to f p a r a l l e lc o m p u t i n gh a sb e e nc a r r i e do u t p a r a l l e lc o m p u t i n gi si nc o n t r a s tt ot h es e r i a lc a l c u l a t i o n , i td i s t r i b u t e st h e p r o c e s s e st os e v e r a li n d e p e n d e n tn o d e s ，w h i c ha l es c h e d u l e db yi n d e p e n d e n t o p e r a t i n gs y s t e m ，a n dh a v ei n d e p e n d e n tc p ua n dm e m o r yr e s o u r c e s ；t h e e x c h a n g e so fi n f o r m a t i o nb e t w e e nn o d e sa r et h r o u g hm e s s a g et r a n s m i s s i o n t h e r ea r es o m ei m p o r t a n ti m p r o v e m e n t so nc o m p u t e rs y s t e ma r c h i t e c t u r ei nt h e r e c e n t5 0y e a r sa l t h o u g ht h e r ew a sn or e v o l u t i o n a r yc h a n g e se x c e p tt h ed a t af l o w c o m p u t e r w h i c hg r a d u a li m p r o v e m e n tt o w a r dp r a c t i c a la p p l i c a t i o n n l e c o m p u t e r sh a v eb e e np u ti n t oa p p l i c a t i o n s a r ea l lb a s e do nv o nn e u m a n n p r o t o t y p e ，a n di m p r o v et h em e a n sa n dc a p a b i l i t i e so fp a r a l l e lp r o c e s s i n go nt h i s b a s i s m p ii sak i n do fm e s s a g ep a s s i n gi n t e r f a c ew h i c hi sp u b l i s h e do nm a y , 1 9 9 4 i tp r o v i d e st h es t a n d a r dl i b r a r yf o rm e s s a g ep a s s i n gp r o c e d u r e m p id e f i n e s t h ei n t e r f a c el i b r a r yb yl a n g u a g ei n d e p e n d e n tf o r m ，a n dp r o v i d e st h eb i n d i n gw i t h ca n df o r t r a nl a n g u a g e t ti st h em o s tr e l i a b l ep l a t f o r mf o rh i 曲e f f i c i e n c y a n du l t r a - l a r g e s c a l ep a r a l l e lc o m p u t i n g a tp r e s e n t , t h ei n t e r n e tc o n n e c t sw i t hal o to fp ca n dv a r i o u s s u p e r - c o m p u t e r , a s s e m b l e dal a r g en u m b e ro fc o m p u t i n gr e s o u r c e s i no r d e rt o u s et h ee x t e n s i v e l yd i s t r i b u t e di d i ec a l c u l a t i o nr e s o u r c e so nt h ei n t e r a c t , t h e r ea r e a l r e a d yan u m b e ro fd i s t r i b u t e dc o m p u t i n gp r o j e c t sh a v eb e e n s e tu p ，f o re x a m p l e s e t i h o m e g i m p sa n ds oo n t h e s ep r o j e c t sh a v ec o n f i r m e dt h ef e a s i b i l i t y o fs u c hc a l c u l a t i o nm o d e l ，n l e s er e s o u r c e sa r eh i g h l yu n s t a b l ea n dc a nn o tb e t r u s t e db yu s e r s b a n d w i d t hi sl i m i t e da n d 触lo f t r e m e n d o u sd e l a y t 姑sp a p e ru s e st h eo b j e c t - u r i e n t e da n a l y s i st e c h n i q u e sw h i c hi sp o p u l a r i n s i d ea n do u t s i d et h ec o u n t r y , t h es t a t i cs t r u c t u r ei sm a d eu po fb yt h eo b j e c t l a y e r , t h es t r u c t u r ea n dl i n kl a v t h et h e m el e v e l ，t h ea t t r i b u t el e v e la n dt h e e v e n t sc o n s t i t u t el a y e r f i n a l l y , g i v eo u tt h eu s ec a s ev i e ww h i c hi sr e f l e c t e db y t h es t a t i cs t r u c t u r e ，t h eh i 曲l e v e ll o g i cm o d e lo fs y s t e mf u n c t i o n sa n dt h e i m p l e m e n t a t i o no ft h ed i s t r i b u t e dc o m p u t i n gi nt h ec o m p u t e rc l u s t e rn e t w o r k 1 1 1 es y s t e mh a ss t e a d yr e s o u r c e s c r e d i b l el l s 粥a n dg o o dc o m m u n i c a t i o n s k e yw o r d s ：o b j e c to r i e n t e d ；p a r a l l e lc o m p u t i n g ；m p i 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：霉熹业日期：兰! 盟二主竺 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即：东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：q 灿指导教师签名：窭丕主互譬 日 期：舭日期：蝠u 江 学位论文作者毕业后去向： 工作单位 通讯地址 电话： 邮编： 引言 4 0 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计 算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软 件( 特别是编译器与操作系统) 、应用软件，最后随着闳题求解环境的发展雨达 到顶峰。 对于可扩展的并行计算机体系结构根据指令流和数据流的不同，可把计算机 系统分为：单指令流单数据流、单指令流多数据流、多指令流单数据流、多指令 流多数据流。按同时执行的程序和数据的不同，可把计算机系统分为：单程序单 数据并行计算机、单程序多数据并行计算机、多程序单数据并行计算机、多程序 多数据并行计算机。五种实际并行计算机物理模型为：并行向量机、对称多处理 机、大规模并行处理机、工作站机群、分布共享存储多处理机。创建和使用并行 计算机的主要原因就是因为并行计算机是解决单处理器速度瓶颈的最好方法之 一。 但是高性能计算机的昂贵价格，使得高性能计算仍然只能停留在高端领域， 严重限制了并行计算的发展，目前，硬件技术的快速发展促进了超级计算走向并 行计算。但是在并行计算领域，相对于硬件，并行软件技术几十年来没有获得突 破性的进展。特别是分布式计算技术，自动并行识别技术等，软件技术的缓慢发 展阻止了并行计算走向中低端。 并行编程要达到良好的可编程性，必须解决结构性、通用性和可移植性问题。 并行编程的可编程性和用户并行编程能力的提高是走向普及的两个方面，网络并 行计算软件环境是现代并行计算的关键技术之一。1 。并行编程的最大的难题是要 解决数据依赖和控制依赖问题，几十年来始终处于研究过程中，没有达到m s d o s 到w i n d o w s 量级的提高，令用户失望。 m p i 是为消息传递程序提供的标准库，由标准消息传递函数及相关辅助函数 构成，进程通过调用这些函数( 类似调用子程序) 进行通信。m p i 以语言独立的 形式来定义这个接口痒，并提供了与e 和f o r t r a n 语言的绑定，是锃前高效率的 超大规模并行计算最可信赖的平台。 m p i 提供了一种与语言和平台无关、可以被广泛使用的、编写消息传递程序 的标准，用它来编写消息传递程序实用、可移植、高效和灵活，为并行软件技术 的发展提供了一个良好的平台。1 。 第一章并行计算简介 1 1 从超级计算到高性能计算 l1 1 超级计算( s u p e r c o m p u t i n g ) 超级计算，从技术的意义上说，是为了在问题的求解上追求更快的速度、更 高的精度、更大的规模、更好的性能价格比而采用的非主流计算的设施和方式。 计算速度是其追求的第一目标。 超级计算主要用于科学计算。早期的应用仅涉及格点差分模式计算( 气象预 报软件删5 ) ，有限元计算，空气动力学分析。几乎和数据处理无关。 超级计算中标准测试( b e n c h m a r k ) 的重点为浮点运算速度测试，包括如下几 个标准： 1 9 7 6 年发布的d h r y s t o n e ，主要用于测整数计算能力，计算单位是 d m i p s 。 1 9 7 6 年发布的w h e t s t o n e ，主要用于测浮点计算能力，计算单位是 m f l o p s 。 1 9 8 0 发布的l i n p a c k ，为解线性方程和线性最小二乘问题的子程序包。 主要用于测浮点计算能力。 1 1 2 高性能计算( h i g hp e r f o r m a n c ec o m p u t i n g ) 随着超级计算需求的扩大，上世纪8 0 年代初出现了小巨机的概念；随着超 级计算应用面的扩大，上世纪8 0 年代后期开始出现高性能计算的概念，把超级 计算推向了各个领域，超级计算追求的单一计算指标也转变为追求高性能的综合 指标。 用户群的扩大，价格的敏感度，p c 机产品化的成熟，迫使高性能计算采用 高性能的产品化部件构成高性能的产品化计算机系统，也促使高性能计算技术走 向开放。 1 2高性能计算应用领域的变迁 目前，科学和工程问题的数值模拟与仿真问题日益呈现以下显著特点： 计算密集； 数据密集： 网络密集； 并且要求在合理的时限内完成计算任务。 表1 - 1 任务计算时限 秒级制造业 分钟级短时天气预报( 当天) 小时级中期天气预报( 3 - 1 0 日) 尽可能快长期天气预报( 气候) 2 数据库技术的成熟，生物基因技术的发展，历史数据的几何级膨胀使人们把 高性能计算更多的应用于数据挖掘应用、图像处理业务、基因测序比对处理等数 据处理领域。随着科学计算规模的迅速膨胀，使得传统的串行计算已经不能满足 要求，从而提出了并行计算的概念。 存储嚣容量 图卜l 科学计算的规模的发展 1 3 并行计算的概念 并行计算是相对于串行计算来说的。 传统的串行计算，分为“指令”和“数据”两个部分，在程序执行时“独立 地申请和占有”内存空间，且所有计算均局限于该内存空间( 图i - 2 ) 。 图卜2 串行计算 所谓并彳亍计算分为时间上的并行和空间上的并行。时间上的并行就是指流水 线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算将进程 一 懈 懈 僻 伽 懈 相对独立的分配于不同的节点上，由各自独立的操作系统调度，享有独立的c p u 和内存资源( 内存可以共享) ；进程问通过消息传递相互交换信息( 图卜3 ) 。 图卜3 并行计算 1 4 可扩展的并行计算机体系结构 1 4 1 根据指令流和数据流的不同的计算机系统分类 1 4 1 1单指令流单数据流( s i s d ，s i n g l ei n s t r u c t i o ns i n g l ed a t a ) 这是传统的冯诺依曼串行机概念，一次只执行一条指令。s i s d 也常 被称为串行标量计算机( s e r i a ls c a l a rc o m p u t e r ) 。当今，s i s d 计算机已 经被整体淘汰了。即使是个人计算机或单片机也实现了一定的并行性以取得 较高的性能，现行的c p u ，大多数情况下，它们能同时执行两条或更多的指 令“。 1 4 1 2 单指令流多数据流( s i m d ，s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 它是指单一指令同时对不同的数据进行同一操作。在这样的机器中，单 一的控制部件操纵多个分开的处理部件。s i m d 机器能支持向量处理，它在 单一控制部件操纵下分派向量元素到各个处理部件并行完成计算。p e n t i u m 删x 和p e n t i u mi i i i i 处理器，在处理多媒体数据时即呈现出这种s i m d 结 构，一条m m ) ( 指令可对打包数据中的2 个、4 个或8 个数据同时操作。 1 4 1 3 多指令流单数据流( m i s d ，m u i t i p l ei n s t r u c t i o ns i n g l ed a t a ) 它的直接含义是几个指令对同一数据片操作。有两种方式来解释m i s d 类机器的组织。一种方式是：它有几个处理部件能接收几个不同的指令对同 一数据进行操作，这已被证明是不可能的也无实际意义和必要；另一种方式 是考虑让数据流通过一串处理部件，像向量处理机和搏动式阵列( s y s t o l i c a r r a y ) 这样的高度流水线式结构，可以被认为是属于这种方式的m i s d 结构。 流水线结构通过一系列阶段( 段或步) 来完成向量处理，每一段完成一个具 体的功能并产生一个中间结果。流水线的各个段代表旎加于这个向量的多个 指令，向量的各个元素可以认为是属于同一数据片；因此可看作是m i s d 结 构。 1 4 1 4 多指令流多数据流( m i m d ，m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a ) 它是指机器有多个处理部件，多条指令能同时对不同的数据进行处理。 多处理机系统、多计算机系统和数据流计算机都可算作此类。这类机器通过 并行处理实现最大的效能。并行不仅指多个处理器同时操作，丽且指多个程 序( 进程) 在同一时间片被执行。多处理机和多计算机之间的主要差别在于 4 存储器共享和处理机间通信机制的不同。多处理机系统中的处理机通过公用 存储器的共享变量实现相互通信。多计算机系统中的每个处理机有只属于本 结点的本地存储器，处理槐之间的通信通过结点间的消息传递来实现。数据 流计算机的指令由操作包和数据令牌组成，用数据令牌传送数据和激活指 令。它的指令不是在中央控制器控制下顺序执行的，而是在数据的可用性控 制下并行执行的，故也将其划入m i m d 类。p e n t i u mi i i i i 处理器实现了指 令的乱序执行，即：够执行条件的数据不分先后可激活该指令的执行。 数据个数d m s 指令个数m 图i - 4 根据指令流和数据流分类计算机系统 l ，4 ，2 按同时执行的程序和数据的不同的计算机系统分类 比照上面的划分方法，把计算机系统分为： i 4 2 i 单程序单数据并行计算机( s p s d ，s i n g l ep r o g r a ms i n g l ed a t a ) 图卜5 单程序单数据并行计算机模型 1 4 2 2 单程序多数据并行计算机( s p m d ，s i n g l ep r o g r a mh ( u l t i p l ed a t a ) 5 1 4 2 3 多程序单数据并行计算机( m p s d ，m u l t i p l ep r o g r a ms i n g l ed a t a ) 1 4 2 4 多程序多数据并行计算机( m p m d ，m u l t i p l ep r o g r a mm u l t i p l e d a t a ) 多程序多数据流，除初始启动多个可执行代码，其余与s p m d 模式一致。 蝴个一， 图卜6 根据同时执行的程序和数据分类计算机系统 1 4 3 五种实际物理机模型 并行计算机系统除少量专用的s i m d 系统外，绝大部分为m i m d 系统，实 际的机器体系结构包括： 1 4 3 1 并行向量机( p v p ，p a r a l l e lv e c t o rp r o c e s s o r ) 专门设计定制的高带宽交叉开关网络将专门设计定制的向量处理器v p 与共享存储模块连接起来，一般不使用高速缓存，而是使用大量的向量寄 存器和指令缓冲器。 总线 图卜7 并行向量机 、，p ：向量处理器 s m ；( s h a r e dm e m o r y ) 共享存储器 1 4 3 2对称多处理机( s m p ，s y m e t r i cm u l t i p r o c e s s o r ) s m p 系统一般使用商品化微处理器，具有片上或外置高速缓存，经由高 速总线( 或交叉开关) 连向共享存储器。每个处理器可等同地访问共享存 储器、i o 设备和操作系统服务。s m p 的主要特点是：单一操作系统映像， 全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载 情况，动态地分配各个进程到各个处理器，并保持各个处理器间的负载平 衡；低通信延迟，各个进程通过读写操作系统提供的共享数据缓存区来完 成处理器间的通信，其延迟通常小于网络通信延迟；共享总线带宽，所有 处理器共享总线带宽，完成对内存模块和i o 模块的访问“。同时，s m p 也 6 具有如下一些问题：欠可靠，总线、存储器、操作系统失效可能导致系统 崩溃；可扩展性较差，由于所有处理器都共享总线带宽，而总线带宽每3 年才增加2 倍，赶不上处理器速度和存储容量的增长步伐，因此s m p 的处 理器个数一般少于6 4 个，且只能提供每秒数百亿次的浮点运算。 訇向一声 图1 - 8 对称多处理机 p c ：( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 s m ：( s h a r e dm e m o r y ) 共享存储器 1 4 3 3 大规模并行处理机( 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 ) m p p 一般采用商品化微处理器和专门设计的互连网络，系统可以扩展到 数千个( 甚至更多) 处理器m 。 图l - 9 大规模并行处理机 p c ：( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 鹏：( m e m o r yb u s ) 存储器总线； n i c ：( n e t w o r ki n t e r f a c ec i r c u i t r y ) 网络接口电路 l m ：( l o c a lm e m o r y ) 本地存储器 1 4 3 4工作站机群( c o w ，c l u s t e ro fw o r k s t a t i o n ) c o w 的每个系统都是一个完整的工作站，一个节点可以是一台p c 或 s m p ，各个节点一般由商品化的网络互连，每个节点一般有本地磁盘，节点 上的网络接口是松散耦合到i o 总线上的，在每个节点上驻留一个完整的 操作系统。 7 图1 - 1 0t 作站机群 m ：( m e m o r y ) 内存 b ：( b u s ) 总线 l d ：( l o c a d i s k ) 本地硬盘 m b ：( m e m o r yb u s ) 存储器总线 n i c ：( n e t w o r ki n t e r f a c ec i r c u i t r y ) 网络接口电路 p c ：( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 l o b ：( i ob u s ) i o 总线 1 4 3 5分布共享存储多处理机( d s m ，d i s t r i b u t e ds h a r e dm e m o r y ) 高速缓存目录d i r 用以支持分布高速缓存的一致性。处理器对物理分 布的共享存储器的访问是不对称的，这也是d s m 与s m p 的区别所在m 。 d s m 具有如下主要特征： 物理上分布存储。内存模块局部在各个节点上，并通过高速互连网 络互连，避免了s m p 访问总线的带宽瓶颈，增强了并行机的可扩展 能力； 单一内存地址空间。尽管内存模块分布在各个节点上，但是所有这 些内存模块都由硬件进行了统一编址，并通过互连网络形成了并行 机的共享存储器。各个节点既可以访问自己的局部内存单元( 本地 访问) ，又可以直接访问其他节点的局部内存单元( 远端访问) ； 非一致内存访问模式( n u m a ，n o n u n i f o r mm e m o r ya c c e s s ) 。由于 远端访问必须通过高性能互连网络，而本地访问只需要直接访问局 部内存模块，因此远端访问延迟一般是本地访问延迟的3 倍以上： 单一的系统映像。类似于s m p ，在d s m 中，用户只看到一个操作系 统，它可以根据各节点的负载情况，动态地分配进程： 基于c a c h e 的数据一致性通常采用基于目录的c a c h e 一致性协议 来保证各节点的局部c a c h e 数据和存储器中数据的一致性。同时， 这种d s m 也称为高速缓存相关的非一致性内存访问( c c - n u m a ， c a c h ec o h e r e n tn o n - u n i f o r i l lm e m o r ya c c e s s ) 结构。 8 d s m 较好地改善了s m p 的可扩展性能。一般地，d s m 可以扩展到上百个 节点，能提供每秒数千亿次的浮点运算功能。但由于受c a c h e 一致性要求 和互连网络性能的限制，当节点数目进一步增加时，d s m 并行机的性能也将 大幅下降。 图1 - 1 1 分布共享存储多处理机 d i r ：( c a c h ed i r e c t o r y ) 高速缓存目录 l m ：( l o c a lm e m o r y ) 本地存储器 m b ：( m e m o r yb u s ) 存储器总线 n i c ：( n e t w o r ki n t e r f a c ec i r c u i t r y ) 网络接口电路 p c ：( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 综上所述，除了近来逐步完善并走向实用化的数据流计算机之外，5 0 年来计 算机系统结构虽取得重大进展，但并没有发生革命性的变化，现已实用化的计算 机仍是以冯诺依曼机器为原型，在此基础上加入并提高并行处理实现的手段和 并行处理的能力。 s m p 、m p p 、d s m 和c o w 等并行结构趋向融合，d s m 是s m p 和m p p 的自然结合，m p p 和c o w 的界限逐渐模糊“。在中国现在使用p v p 并行向量机很少，使用最多的是 s m p 、d s m 、c l u s t e r 架构的并行计算机。国内主要的高性能计算机厂商如曙光、 联想、浪潮生产的都是c l u s t e r 架构的并行计算机。节点为2 4 个处理器的s 船， 互连网络为千兆网、m y r i n e t 等，节点操作系统一般为l i n u x 。 和s m p 、d s m 等相比，集群在较低的费用下，具有高性能、可扩展性、高吞吐 量、易用性等特点“。按照应用目的( 科学计算商业计算) 分类，集群可分为 高性能集群和高可用集群；按照节点硬件分类，可以分为p c 集群、工作站集群、 s m p 集群；按照节点操作系统分类，可以分为l i n u x 集群、n t 集群等；按照节点体 系结构和操作系统的类型，可分为同构集群、异构集群等。 1 5并行计算机硬件结构抽象模型( 自然模型) 1 5 1 共享存储的模型和语言( 适于s 卿 a n s ix 3 h s o ，o p e n m p “2 1 1 5 2 消息传递的模型和语言( 适于咿p 、c l u s t e r 、c o w ) m p i ( f o r t r a n ，c ) p ( f o r t r a n 。c ) 9 1 5 3 数据并行的模型和语言( 适于在m p p c l u s t e r 上实现、s p m d 应用) h p f ( h i g hp e r f o r m a n c ef o r t r a n ) f o r t r a n9 0 1 5 4 基于程序构造的模型 c s p l i n d a ( f o r t r a n ，c ，g a u s s i a n ) g l o b a l ( m o l p r o c o l u m b u s ) 1 5 5 基于问题描述的模型 g a 脚a u n i t y 1 5 6 基于并行计算理论的模型 p r a m b s p l o g p 1 6 并行计算机的发展 并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与 协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个 最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构 的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 从8 0 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于s m p 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了c a c h e - - 致性问题的处理方案“。从此，c m m p 开创出的共享存储多处理器之路越走越宽： 现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。 同一时期，基于消息传递机制的并行计算机也开始不断涌现。8 0 年代中期， 加州理工成功地将6 4 个i 8 0 8 6 i 8 0 8 7 处理器通过超立方体互连结构连结起来。此 后，便先后出现了i n t e li p s c 系列、i n m o st r a n s p u t e r 系列、i n t e lp a r a g o n 以及i b ms p 的前身v u l c a n 等基于消息传递机制的并行计算机。 8 0 年代末到9 0 年代初，共享存储器方式的大规模并行计算机又获得了新的发 展。i b m5 将大量早期r i s c 微处理器通过蝶形互连网络连结起来。人们开始考虑 如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性 ( s c a l a b i l i t y ) 。9 0 年代初期，斯坦福大学提出了d a s h 计划，它通过维护一个保 存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后 来，i e e e 在此基础上提出了缓存一致性协议的标准。 9 0 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的锄一5 除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息： c r a yt 3 d 是一台n u b i a 结构的共享存储型并行计算机，但是它也提供了全局同步机 制、消息队列机制，并采取了一些减少消息传递延迟的技术。 随着商品化微处理器、网络设备的发展，以及m p i p v m 等并行编程标准的发 1 0 布，集群架构的并行计算机出现。i b ms p 2 系列机群系统就是其中的典型代表。 在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网 络连接起来。 今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连 网络构造，这种分布存储的并行计算机系统称为集群。国内几乎所有的高性能计 算机厂商都生产这种具有极高性能价格比的高性能计算机。并行计算机从此进入 了一个新的时代，并行计算的应用达到了前所未有的广度和深度。 第二章m p i 简介 2 1 并行计算发展的障碍 2 1 1 硬件上的障碍 高性能计算机昂贵的价格，使得高性能计算仍然只能停留在高端领域。但是 硬件技术的快速发展促进了超级计算走向并行计算；相比之下，软件技术的缓慢 发展则阻止了并行计算走向中低端。 从硬件技术上来讲，从上世纪4 0 年代第一台计算机e n i a c 的5 0 0 0 次秒到 目前的1 8 3 t 次秒，速度提高了三千七百亿倍，这主要归功于硬件技术的发展。 现有的并行计算设备： p o w e rc h a ll e n g ex l 并行对称多处理系统 日立s r 2 2 0 1 超级计算并行机系统 曙光2 0 0 0 - i i 超级服务器 2 1 2 软件上的障碍 在并行计算领域，相对于硬件，并行软件技术几十年来没有获得突破性的进 展。特别是分布式计算技术，自动并行识别技术等。 并行编程要达到良好的可编程性，必须解决结构性、通用性和可移植性问题。 ( 并行化编译器、自动并行化、用户指导和运行时间并行化) 最大的难题是要解 决数据依赖和控制依赖问题，几十年来始终处于研究过程中，没有达到m s d o s 到w i n d o w s 量级的提高，令用户失望。 要使并行计算到桌面，( 低端) ，除价格因素外，并行编程的可编程性和用户 并行编程能力的提高是走向普及的两个方面，而用户并行编程能力的培育是很难 在短期内实现的。因此，在可预见的时间内，如果没有很好的并行运行工具，超 级计算到桌面是不可能现实的。 2 2 并行算法的设计 对于相同的并行计算模型可以有多种不同的并行算法来描述和刻画。由于并 行算法设计的不同可能对程序的执行效率有很大的影响，不同的算法有几倍、几 十倍、甚至上百倍的性能差异是完全正常的。 并行算法基本上是随着并行机的发展而发展的。从本质上说不同的并行算法 是根据问题类别的不同和并行机体系结构的特点产生出来的。一个好的并行算法 要既能很好地匹配并行计算机硬件体系结构的特点，又能反映问题内在。 并行性对于s i m d 并行计算机一般适合同步并行算法；而m i l d 并行计算机则 适合异步并行算法。对于s p m d 和m p t d 这些新流行起来的并行计算机，设计并行 算法的思路和以前并行算法的思路有很大的不同。s p m d 和m p m d 并行算法的设计 对于集群计算有一个很重要的原则就是设法加大计算时间相对于通信时间的比 重，减少通信次数，甚至以计算换通信。这是因为，对于集群系统，一次通信的 开销要远远大于一次计算的开销。因此要尽可能降低通信的次数，或将两次通信 1 2 合并为一次通信。基于同样的原因，集群计算的并行粒度不可能太小，因为这 样会大大增加通信的开销。如果能够实现计算和通信的重叠，那将会更大地提高 整个程序的执行效率。因此对于机群计算，可以是数值或非数值的计算，这些都 不是影响性能的关键也可以是同步、松同步或异步的。但以同步和松同步为主， 并行的粒度一般是大粒度或中粒度的。一个好的算法一般应该呈现如下的计算模 式： 通信 或 等待 通信 或 等待 图2 - 1s p m d 并行算法的计算模式 上图没有考虑计算与通信的重叠，若能够实现计算与通信的重叠那将是更理 想的计算模式： 计算 计算 计算 计算与通信重叠的部分 夸 ll 产_ 。 ? | 通信 、 l _ _ _ _ _ _ _ _ _ _ _ _ 一 i r 1 、 l 一声。- _ l 通信 ! k j 7 、 通信 、 图2 2 计算与通信重叠的s p m d 并行算法的计算模式 对于m p m d 并行算法，各并行部分一般是异步执行的，而不是象s p m d 那样的 同步或松同步方式。因此只要能够大大降低通信次数、增大计算相对于通信的比 重，则该m p m d 算法就可以取得较高的效率“。下图给出了m p m d 算法的一种比较 合适的计算模式： = 气、厂一 。广、k ，、k = k 一厂弋广 通信 、j 图2 - 3 适合集群系统的m p m d 并行算法 2 3 帅i ( m e s s a g ep a s s i n gi n t e r f a c e ) 概述 在当前流行的并行机上主要的编程环境有消息传递、共享存储和数据并行。 其中消息传递具有良好的可移植性、可扩展性，具有完备的异步通信功能。 w p i 是1 9 9 4 年5 月发布的一种消息传递接口，是为消息传递程序提供的标 准库，由标准消息传递函数及相关辅助函数构成，进程通过调用这些函数( 类似 调用子程序) 通信：一个程序同时启动多份，形成多个独立的进程，在不同的处 理机上运行，拥有独立的内存空间，进程间通信通过调用m p i 函数来实现；每个 进程开始执行时，将获得一个唯一的序号。 m p i 实际上是一个消息传递函数库的标准说明，以语言独立的形式来定义这 个接口库，并提供了与c 和f o r t r a n 语言的绑定，是目前高效率的超大规模并行 计算最可信赖的平台。它能运行在所有的并行平台上，包括s m p 和p v p “”。程序 设计语言支持c 、f o r t r a n 和j a v a 。在国产的三大并行机系列：神威、银河和曙 光上都实现了对m p i 的支持。 m p i 标准化涉及到大约6 0 个国家的人们，他们主要来自于美国和欧洲的4 0 个组织，这包括并行计算机的多数主要生产商，还有来自大学、政府实验室和工 厂的研究者们“”。1 9 9 2 年4 月，并行计算研究中心在w i l l i a m s b u r g ，v i r g i n i a ， 召开了一个关于消息传递的标准的工作会议，会议上讨论了标准消息传递的必要 的、基本的特点，并建立了工作组继续进行标准化工作。 1 9 9 2 年1 0 月，m p i 的初步草稿m p i l 形成，m p l l 主要包含的是在w i l l i a m s b u r g 工作组会议上讨论的基本消息传递的接口，因为它的基本目的就是促进讨论并继 续此项工作，所以它主要集中在点对点的通信。1 9 9 3 年1 月，第一届m p i 会议 在d a l l a s 举行，1 9 9 3 年2 月m p i i 修定版本公布：之后定期召开了一系列关于m p i 的核心的研讨会；1 9 9 3 年11 月m p i 的草稿和概述分别发表于s u p e r c o m p u t i n g 9 3 和t h ep r o c e e d i n g s 。直到1 9 9 4 年5 月，w p i 标准正式发布。1 9 9 4 年7 月发布 了w p i 标准的勘误表“。 2 4m p i 的目的 i j p i 的目标总结起来包括以下几个在实际使用中都十分重要，但有时又是相 互矛盾的三个方面：较高的通信性能、较好的程序可移植性、强大的功划。具 1 4 体地说包括以下几个方面： 提供应用程序编程接口： 提高通信效率措施，包括避免存储器到存储器的多次重复拷贝、允许计 算和通信的重叠等： 可在异构环境下提供实现； 提供的接口可以方便c 语言和f o r t r a n 的调用： 提供可靠的通信接口，即用户不必处理通信失败； 定义的接口和现在已有接口差别不能太大，但是允许扩展以提供更大的 灵活性； 定义的接口能在基本的通信和系统软件无重大改变时在许多并行计算 机生产商的平台上实现，接口的语义是独立于语言的； 接口设计应是线程安全的。 m p