(计算机软件与理论专业论文)pc机群环境mpi并行dft运算的研究.pdf_第1页
(计算机软件与理论专业论文)pc机群环境mpi并行dft运算的研究.pdf_第2页
(计算机软件与理论专业论文)pc机群环境mpi并行dft运算的研究.pdf_第3页
(计算机软件与理论专业论文)pc机群环境mpi并行dft运算的研究.pdf_第4页
(计算机软件与理论专业论文)pc机群环境mpi并行dft运算的研究.pdf_第5页
已阅读5页,还剩45页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 并行d f t 是解决大数据量d f t 运算耗时过久的重要途径,在p c 机群上实 现并行d 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 ) 消息 传递机制。在此基础上,建立了基于l i n u x 和m p 的p c 机群实验环境。m p 并行程序设计与传统程序设计存在显著差异,本文讨论了在机群系统上进行m p i 并行程序设计的过程和方法,并且具体用于实现m p i 并行d f t 运算。讨论了p c 机群环境下m p i 并行一维和二维d f t 的编程实现,并利用建立的平台,对并行 算法进行了测试,比较了并行d f t 和传统d f t 运算耗时的差异。同时,比较了 并行算法的设计中网络通信( 消息传递) 因素对并行效果的影响。最后,根据理 论研究和实际测试的结果,总结了利用p c 机群系统进行并行d f t 运算的可行 性,得出了一些有意义的结论。 关键字:p c 机群消息传递m p i 并行算法d f t a b s t r a c t ap a r a l l e ld f ti st h ei m p o r t a n tm e t h o dt oe n h a l i c et h es p e e do fm u l t i r ,l ed a t a sd f t o 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 tp r o c e e d e di nac l u s t e ro f p c s t l i s p a p e rf i r s t l y i n t r o d u c e dt h eb a s i c t h e r a p y o fp a r e l l e l a l g o r i t h m s ,a n d t h e n d i s c u s s e dt h ec l u s t e ro fp c s s y s t e m a n d m p i a c c o r d i n g t ot h i st h e o r y , a na p p r o p r i a t e l a b o r a t o r ye 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 nl i n u xa n dm p i ,w a s e s t a b l i s h e d t h e r ea r eg r e a td i f f e r e n c e sb e t w e e nt h en e w l yd e v i s e dm p ip r o g r a m m i n g m 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 rd i s c u s s e dt h em e t h o dh o wt o p r o c e e dt h em p ip a r a l l e lp r o g r a 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 t t h eo n ed i m e n s i o n a la n dt w od i m e n s i o n a lm p ip a r a l l e ld f tp r o g r a m s n et i m e d i f f e r e n c e sb e t w e e np a r a l l e ld p ta n dt r a d i t i o n a lo n ew e r ea n a l y s e da f t e rt h i sp r o g r a m w a st e s t e d 1 na d d i t i o n t h ee f f e c t so f p a r a l l e le f f i c i e n c y c a u s e d b y n e t w o r k c o n l l r l t l n i c a t i o ni np a r a l l e ld f ta n dw a d i t i o n a lo n ew e r ea l s oc o m p a r e d f i n a l l y , f r o m t h et h e o r a t i c a la n d p r a c t i c a ls t u d y , t h ef 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 ld f t i nc l u s t e r o fp c sw a sd 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 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 r o 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 sd f t 第一章绪论 由于高性能计算机的发展以及其应用的开益广泛,对科学技术以至整个人类社会 都产生了巨大影响,人们越来越清楚的认识到,计算机已经成为理论分析和实验并列 的第三种科学研究手段,并且充当越来越重要的角色。同时,计算机数值模拟与辅助 设计对计算机的性能提出越来越高的要求,为了满足发展的需要,除了提高元器件的 速度之外,系统结构也必须改进,特别是在现有的元器件速度到达极限时,改进计算 机系统的系统结构,跳出元器件速度的物理限制,就显得更加必要。现阶段,计算机 系统结构的改进主要围绕着并行处理技术展开,即增加同一时间间隔内的操作数量。 这样一来,单处理器计算机系统对高性能计算就不能满足需求。此时,研究发展并行 计算机就显得尤为重要。使用并行处理技术,在并行计算机上设计求解问题的方法称 之为并行计算。并行技术主要是用于大规模、高性能计算的应用领域。 1 1 研究的背景和意义 在计算机学科的图象处理领域以及光学学科光传输领域中离散傅立叶变换( d f t ) 有着广泛的应用。傅立叶变换运算由于其运算量十分巨大,实际应用十分困难。1 9 6 5 年c o o l e y 和t u k e y 发表了快速傅立叶变换的著名论文,使离散傅立叶变换的运算量 大大下降,对数字图象信号处理的发展起到了非常关键的作用,此后,各种快速算法 不断涌现。但是,随着其应用范围的日益广泛,有些问题需要处理的数据量非常大, 有些问题则要求极快的计算速度,目前的计算速度达不到实际要求。因此,新的技术 运由而生。高性能p c 计算集群以其巨大的存储容量和很快的计算速度得到了的到了 信号处理界的广泛重视,近年来成为了研究热点。如何在p c 并行机群计算机上快速 有效的计算离散傅立叶变换成了一个新的研究课题。 并行运算是解决大数据量数值运算耗时过久的重要途径,在p c 机群上实现并行 运算是一种低成本、高效率的解决方案。香港科技大学物理系的l i n u xp cc l u s t e r 计 划1 1 :2 0 0 1 年用8 0 台1 4 g i - i 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 a f t o a t i n g p o i n t o p e r a t i o n s p e r s e c o n d ) ,与2 0 0 1 年6 月的世界第 5 0 0 大速度持平,总花费只有1 2 0 万港币; 本论文所进行的讨论是我校计算机系与光学重点学科的合作项目机群系统 分布式计算的研究,应用对象为在光学学科“非线性导波和强激光传输方向”等项目 研究中实现快速高效的离散傅立叶变换,特别是二维或多维离散傅立叶变换,以解决 当前其光传输数值模拟研究中,大数据量的傅立叶变换计算速度过慢的问题。 1 2 本论文的主要工作 本文研究了在p c 机群环境中实现并行d f t 运算的相关问题。 论文首先研究利用现有计算机资源,构建小型的机群系统,建立基于l i n u x 和 m p i 的实验环境。在此基础上,介绍了开发m p i 并行程序的过程,并结合离散傅立叶 变换的特点,设计实现了基于m h 的并行d f t 程序。并且在实验环境中测试了并行 程序的性能。 本论文对机群环境作的研究和探索,主要包括以下工作: 第一,对并行计算体系结构进行讨论,通过建立基于l i n u x 和m p 的并行机群 实验环境,探索可扩展p c 机群系统的构建和实现方法。 第二,研究了消息传递模式下机群系统并行程序模型以及影响并行程序性能的因 素;讨论了m p i 程序设计的基本模式和方法,以及在m p i 机群环境下开发并行程序 的框架和过程。 第三给出了机群m p i 环境下并行d f t 的并行程序实现。 第四,在自行建立的并行实验平台上,对并行d f t 程序。眭能做了测试。 最后,根据理论研究和实际测试的结果,总结了利用机群系统进行高速d f t 运 算的可行性,以及分析提出进一步改进的思路。 2 1 并行化概述 第二章并行计算基本理论 并行计算机的发展基于人们在两方面的认识:第一,单机性能不可能满足大规模 科学与工程问题的计算需求,而并行计算机是实现高性能计算、解决挑战性计算问题 的唯一途径;第二,同时性和并行性是物质世界的一种普遍属性,具有实际物理背景 的计算问题在许多情况下都可以划分成能够并行计算的多个子任务。针对某一具体应 用问题,我们可以利用它们内部的并行性,设计并行算法,将其分解成为互相独立但 彼此又有一定联系的若干个子问题,分别交给各台处理机,而所有的处理机按并行算 法完成初始应用问题的求解。例如,根据几十个常用应用软件的统计,6 0 8 0 的标 量计算可以被向量化,而9 0 左右的串行计算可以并行化【2 】。 实现或提高计算机系统的并行性,可以通过时间重叠、资源重复和资源共享等技 术途径来实现。 时问重叠( t i m es u p e r p o s i t i o n ) 是在并行性概念中引入时间因素,让多个处理过 程在时间上相互错开,轮流重叠的使用同一套硬件设备的各个部分,以加快硬件周转 而赢得速度。 资源重复( r e s o u r c e r 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 年m j f l y r m 提出了著名的f l y n n 分类法,根据指令流与数据流方式的不同 将计算机系统分类。指令流指机器执行的序列;数据流指指令调用的数据序列,包括 输入数据和中间结果;据此,可以把计算机系统分成: 单指令流单数据流s i s d ( s i n g l e i n s t r u c t i o ns t r e a m s i n g l ed a t as t r e a m ) : 单指令流多数据流s i m d ( s i n g l e i n s t r u c t i o ns t r e a m m u l t i p l ed a t a s t r e a m ) : 多指令流单数据流m i s d ( m u l t i p l e i n s t r u c t i o ns t r e a m s i n g l ed a t as t r e a m ) : 多指令流多数据流m i m d ( m u l t i p l e i n s t r u c t i o ns t r e a m m 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 m d 型并行计算机是研究和开发的主流。 2 2 1 向量处理s i m i ) 型并行机 向量处理机是典型的s i m d 并行机。向量机的特点是利用流水线的概念,把一个 计算部件拆成几段,在流水线的每一部分操作一个子功能,通过时间重叠实现并行加 速,其代表机型为c r a y 一1 向量机。s i m d 类型并行机对并行计算机的发展起到了重要 推动作用,但由于微处理芯片技术的发展,单处理器的性能都非常强大。9 0 年代以后, 并行机均朝着m i m i ) 方向发展。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 系统两种形式【4 】。 m p p ( m a s s i v e l y p 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 s 、c r a yt 3 d 、国产y h 一3 和曙 光1 0 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 f w 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 ci v ,其为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 ) :内容主要为高性能计算的软件研究。 目前,高性能计算的发展应用可分为以下两大类 ( 1 ) 面向高端用户,追求细粒度、超高速的大规模并行计算机系统,由数百以 至更大多数目的c p u 组成,如以下的的系统: 陈列处理机,如d a p 向量并行机,如c r a y - 1 、国产银河一1 等 s i m d 并行机,如t h i n k m a c h i n e 公司的c m 2 、m p l 、m p 2 等 大规模并行机( m p p ) ,如m m s 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 m 并行语言) 利用现有的顺序高级语言并提供用于消息传递的外部函数库( 如e x p r e s s 、 m p i - m e s s a g ep a s s i n g i 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 5 并行计算模型 图2 - 1 问题的并行求解过程图 并行计算模型( 也称为编程模型、类型性模型、概念性模型或理想化模型) 是指 将各种并行机( 至少是某一类并行机) 的基本特征抽取出来,形成一个处于具体并行 机之上的抽象并行计算机,类似于顺序计算的y o n n e u m n n 模型。 并行算法的设汁可以从两个角度进行:( 1 ) 依据并行计算模型设计并行算法,然 后将其映射到具体并行机中;( 2 ) 直接基于具体并行机进行并行算法的设计与分析。 显然,相比于第二种并行算法设计而言,并行计算模型起到了屏蔽了并行机实现细节 的作用,使得设计的算法可映射到一类并行机上,具有更强的主命力。 具体而言,并行计算模型的主要作用如下: 为并行算法的研究提供了一个比较通用的物质基础。 - 为并行算法的设计与分析提供了一种简单、方便的框架。 使得设计的并行算法具有一定的生命力,可以适用于多种具体的并行机。 迄今为止,已经有多种并行计算模型存在,如p r a m 模型、l 0 驴模型、c 3 模型、 b d m 模型等,但其中的每一种只抽象了实际并行机的一个或几个方面,尚无一种适 用于所有并行机川。 2 6 并行通信与同步 进行并行计算时,处理器之间的数据调度、传输,需要通信开销。基于共享存储 的并行计算模型的通信是依靠全局存储变量完成的,所以其通信开销并不是很大,但 是在基于分布存储特别是消息传递的并行计算模型上,数据在处理器之间选路、传输 可能花费的时间要长的多。 并行系统执行给定算法的过程中,出现某些处理机的一些计算必须在其他处理机 的一些计算完成之后才能进行时,同步是必要的,同步就是保证此类情况得以正确实 施。同步要有两方面的开销:一是实现同步一般要求对所有处理机作某种检查,在此 是要花费时间的;二是某些处理器或是所有处理器都可能闲置,等待准许继续进行计 算的消息。目前已经有各种技术来实现同步,包括软件技术与硬件支持州。 2 7 并行算法的性能度量 对于一个给定问题,如果设计了一个新的并行算法,就必须对该算法的性能进行 评价。性能度量的目的就是为并行算法的设计与分析提供一个统一的衡量标准。在当 前并行计算环境中,并行算法的性能度量一般涉及到求解问题的规模与分类、具体并 行机的性能、影响算法的关键因素、并行算法评价准则等方面的问题。本节对度量并 行算法性能的一些基本概念进行介绍。 ( 1 ) 运行时间。并行算法的运行时间是指算法在并行计算机上求解一个问题所 需的时间。即表示算法开始执行到执行结束的这一段时间。如果多个处理机不能同时 开始或同时结束时,则算法的运行时间定义为:从最早开始执行的处理机开始执行算 起直到最后一台处理机执行完所经过的时间。在计算机上实现一种算法之前,通常需 要对其运行时间进行理论分析。对并行算法运行时问的分析包括估计它在最坏隋况下 的计算时间和通信时间,其中的计算时间是用算法所需执行的基本操作数或步数表 示,通信时间则是根据计算得到的通信次数和每步的通信量,依据并行计算模型计算 得到。理论分析得到的算法运行时间常表示为问题输入规模的函数。对于一个规模为 n 的问题,算法的运行时间可用t ( n ) 表示,它是输入规模n 的函数。 ( 2 ) 并行度与粒度。算法的并行度d o p ( d e g r e eo fp a r a l l e l i s m ) 是指该算法中 可并行执行的操作数。若处理机资源无限,则算法的并行度也可以理解为可以利用来 作并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程中保持并行度 不变,所以更准确的说法还应该加上时间范围的限制,即在某时间范围内的并行度。 从直观意义上可以说,并行度是刻画一个并行算法的“并行程度”的量,它反映了软 件并行性与硬件并行性匹配的程度。显然。与算法并行度有关的概念是粒度,一般而 言,大的粒度意味看能独立并行执行的是大任务,算法的并行度小,小的粒度意味着 能独立并行执行的是小任务,算法的并行度大。 ( 3 ) 加速比和效率。加速比和效率是最传统的并行算法评价标准,它们体现了 在并行机上运用并行算法求解实际问题所能获得的好处。 并行算法的加速比定义为: s p = j p 式中,t t 最优串行算法在单处理机上的运行时间;t 厂并行算法使用p 台处理 机的计算时间。 并行算法的效率定义为: 驴 式中,p 为处理机台数。 如果按照某种条件,如保持每台处理机的计算规模,并行算法加速比斗与处理机 的台数尸成正比,则称该并行算法在该条件下,在该并行机上具有线性加速比。在某 些条件下,若s 。 p ,则称该条件下,该算法具有超线性加速比a ( 4 ) 可扩展性,可扩展性是设计高性能并行计算机和并行算法所追求的另一个 重要目标。由于并行系统的性能与系统规模、问题规模、算法内在并行性以及由于通 信、同步和进程创建等引起的系统开销等因素有关。而这些因素对并行系统的结构和 应用程序的可扩展性都有影响,因此可扩展性也是衡量并行系统性能的一个重要指 标。衡量系统可扩展性的方法有很多,比较直接的定义为并行系统的性能与处理机数 目成线形比例的关系。 2 8 并行算法设计应注意的问题 根据并行化的特点分析,无论采用什么方法进行设计并行算法,以下几点都是决 定并行效率的重要因素: 第一,挖掘并行性。针对一个具体问题设计其并行算法时,可根据求解该问题的 串行算法出发,分析其明显的并行性,加以并行化,并应该利用相关知识,深刻挖掘 问题内在的可并行性。 第二,并行算法依赖并行的环境。并行算法与进行并行的环境密切联系,一个并 行算法在不同的并行系统上的差别很大,所以说,要根据并行的环境有针对性的设计 并行算法。 第三,考虑通信开销。通信开销是一个必须考虑的因素,因为有时通信在真个算 法中占用时间的比例很大,特别是在分布存储的并行环境下,要尽量减少通信开销, 才能设计出高率的并行算法。 1 0 第三章p c 机群系统及m p i 消息传递 3 1p c 机群系统 可扩展并行p c 机群是现在超级计算的一种解决方案,也是目前最好、最经济的一 种方案。机群系统是利用高速通用网络将一组高性能工作站或高档p c 机,统一调度, 协调处理,实现高效并行处理的系统。其基本计算节点可以是普通微机,而分布操作 系统和计算软件是开放的,可以免费下载。 从结构和结点问的通信方式来看,它属于分布存储系统,主要利用消息传递方式 实现各主机之间的通信,由建立在一般操作系统之上的并行编程环境完成系统的资源 管理及相互协作,同时也屏蔽工作站及网络的异构性。对程序员和用户来说,机群系 统是一个整体的并行系统。机群系统中的主机和网络可以是同构的,也可以是异构的。 目前已实现和正在研究中的机群系统大多采用现有商用工作站和通用l a n 网络,这 样既可以缩短开发周期,又可以利用最新的微处理器技术。大多数机群系统的并行编 程环境也是建立在一般的u n i x 操作系统之上,尽量利用商用系统的研究成果,减少 系统的开发与维护费用。 从应用的角度看,r i s c 技术、网络技术和并行编程环境的发展使得机群系统这 新的并行处理系统形式正成为当前研究的热点_ j 【。 由于r 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 n d a 、p 4 等。这些系统的适应平台非常广,应用程序在这些系统上的可移 植性较好,特别是p v m 和m p i ,由于其开放性,受到许多大学和研究机构都有广泛 的重视,在这些环境下开发了许多应用程序。 运用机群系统进行并行运算的研究,主要原因是它与传统的并行处理系统相比有 以下几个明显的特点: ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站和通用l a n 网络,使结 点主机及系统管理相对容易,且可靠性高。开发的重点在通信和并行编程环境上,既 不用重新研制计算结点,又不用重新设计操作系统和编译系统,节省了大量的研制时 间,缩短了开发周期。 ( 2 ) 系统价格低。由于生产批量小,传统巨型机或m p p 的价格都比较昂贵,往往 要几百万到上千万美元。而构成机群的工作站或高档p c 机是批量生产的,因而售价 较底。由近十台或几十台工作站组成的机群系统可以满足相当多数应用的要求,且价 格较低。 ( 3 ) 节约系统资。由于机群系统的结构比较灵活,可以将不同体系结构,不同性能 的工作站连在一起,这样就可以充分利用现有设备。从使用效率上看,机群系统的资 源利用率也比单机系统要高得多。u c b e r k e l e y 计算机系1 0 0 多台工作站的使用情况调 查表明,一般单机系统的使用率不到1 0 ,而机群系统中的资源利用率可达到8 0 左 右【9 1 。另一方面,即是用户设备更新,原有的一些性能较低或型号较旧的机器在机群 系统中仍可发挥作用。 ( 4 】系统扩展性好。从规模上说,机群系统大多使用通用网络,系统扩展容易;从 性能上说,对大多数中、粗粒度的并行应用都有较高的效率。 3 2 机群环境并行算法的设计 对于相同的计算模型,可以有多种不同的并行算法来描述和刻画。由于并行算法 设计的不同,可能对程序的执行效率有很大影响 1 0 1 1 1 1 1 1 2 1 。 并行算法基本是随着并行机的发展而发展的。不同的并行算法是根据问题类别的 不同和并行机体系结构的特点而设计的,一个好的并行算法既要很好的匹配并行计算 机硬件体系结构的特点,又要反映问题内在的并行性。 对于机群环境,设计并行算法的思路相比传统计算环境,设计思想有了很大的不 同,一个很重要的原则就是设法加大计算时间相当于通信时间的比重,减少通信次数。 这是因为对于机群系统,一次通信的开销远远大于一次计算的开销,因此要尽可能的 降低通信的次数,或将几次通信台并为一次通信。 图4 1 简单描述了机群系统s p m d ( s i n g l ep r o g r a m em u l t i p l ed a t a s ) 并行算法设计 的一般模式。 图4 - 1 机群系统s p m d 并行设计模式 前面已经分析得出,机群系统的效率主要为通信开销所制约。如果能实现计算和 通信的重叠,将会大大提高整个程序的执行效率。图4 - 2 描述了计算与通信重叠的 s p m d 并行算法的设计模式。 ,7 j _ r j ; j ; , l l ,7 - r ?、 , : 1 , l ,7 r , | j ; , 。 计算与通信的重叠部丹 图4 - 2 计算与通信重叠的s p m d 并行计算模型 3 3 消息传递机制 消息传递是并行编程模型的一种重要模式。所谓消息传递就是指并行执行的部分 之间通过消息传递来交换信息、协调步伐、控制执行。消息传递一般是面向分布式存 储结构,但是它也可以适用于共享存储的并行机。消息传递为编程者提供了灵活的控 制手段和表达并行的方法,灵活性和控制手段的多样性,也是消息传递并行程序能提 供高的执行效率的重要原因。 在编程设计的级别方面,消息传递机制属于低级别的设计模型。这是因为,消息 传递模型一方面为编程者提供了灵活性,另一方面,它也将各个并行执行部分之州复 杂的信息交换和协调、控制的任务交由编程者,这在一定程度上增加了编程者的负担。 虽然如此,消息传递的基本通信模式是简单和清楚的,学习和使用并不困难。在目前, 大量的并行程序设计使用的都是消息传递并行模型。 3 4 m 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 诞生于数年之后,由几所大学和国家实验室出于创建消息传递库标准的目的共同开发 成功旧 t 4 l 。 对m p i 的定义,可从以下三个方面束认识: ( 1 ) m p i 是一个库,而不是- - f q 语言。m p i 库可以被f o r t r a n 或c 语言调用, 他遵守语言语法中对过程或函数的调用规则。 ( 2 ) m p i 是一种标准或规范的代表,而不特指某一个对它的具体实现。现在, 几乎所有的并行计算机制造商都提供对m p i 的支持,可以在网络中免费得到m p i 在 不同并行计算机上的实现,一个正确的m p 程序,可以不加修改的在所有并行机上执 行。 ( 3 ) m p 是一种消息传递编程模型,并成为这种编程模型的代表和事实上的标 准。m p i 虽然很庞大,但是它的最终目的是服务于进程问通信这一目标。 m p 的标准化开始于1 9 9 2 年4 月。在1 9 9 2 年1 1 月推出了m p l l 0 ,并在1 9 9 3 1 4 年2 月完成修订版本。1 9 9 5 年6 月推出了m p i 的新版本m p l l 1 ,为原来的m p i 作了 进一步的修改、完善和扩充。1 9 9 7 年7 月,在对m p i 做了重大扩充的基础上,又推 出了m p i 的扩充部分m p i - 2 ,而把原来的m p i 各种版本称为m p l 1 。m p p l 目前已经 基本成熟稳定。m p 9 2 目前已经出现实验测试性版本( 如m p i c h 2 ) ,但还没有完整的 正式版本口“。 m p i 的特点概括来说有三方面:较高的通信性能;较好的程序可移值性;强大的 功能。具体来说,包括以下几个方面: ( 1 ) 通用性:m p i 是可移植的标准平台,其通讯单元包含上、下文和组的信息,以 保证消息传递的安全性。 ( 2 ) 点对点通讯:m p i 能有效地管理消息缓存区,具有结构化缓存、扩充数据类型 及异构性,m p i 异步执行时能保护用户的其它软件不受影响,能实现完全的异步通信。 立即发送与接受可完全与计算覆盖进行。 ( 3 ) 数据汇集方式:具有内定和用户自定义的数据汇集操作方式,可对大量数据进 行整体传输,可直接或依拓扑结构定义子组。 ( 4 ) m p i 的实现方式多样化,同一编程界面可有多种开发工具,具有面向应用的信 息传递拓扑结构:内定支持网格和图拓扑结构。 ( 5 ) 良好的操作环境:具有差错控制功能m p l 2 在f 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 5 m p i 的通信模型 分布存储环境下,消息传递是多个并行任务之间沟通的桥梁。m p i 消息传递的灵 活性也体现在通信机制方面。并行程序设计者可以根据通信需求,选择合适的通信方 式,实现高效率的消息传递。m p i 提供了点到点通信和全局通信两种通信形式”1 【阍。 3 5 1 点到点通信 对于源和目的任务之间的直接通信,m p i 提供了点到点的发送和接收函数。负责 发送的任务将数据放入到发送缓冲区,发送给接收数据的特定目标任务,后者有相应 的接收缓冲区。点到点的通信有两种发送和接收方式:阻塞和非阻塞。阻塞发送的完 成意味着数据已拷贝出缓冲区,即通信缓冲区可重新分配。阻塞接收的完成意味着到 来的消息已拷贝入用户接收缓冲区,即接收方已可以使用。但是,发送的完成并不意 味着一个匹配的接收已发生,发送的消息可能被缓存在系统的缓冲区中。这样,发送 可在匹配接收发生之前完成。非阻塞操作可以使得计算与通信重叠( 必须有系统硬件支 持) ,m p i 的非阻塞操作立即返回一句柄,这不意味着数据已经拷贝出发送缓冲区( 或 数据已拷贝入用户接收缓冲区) ,该句柄可用来在适当的时候完成( m p i - w a i t ) 或检测 ( m p i - t e s t ) 对应的非阻塞操作。 m p i 提供具有以下语义的阻塞和非阻塞发送: 标准发送:发送操作可以在相应的接收前后发生,发送完成则发送者缓冲区可用; 就绪发送:发送操作仅在相应的接收发生后才能发出,其完成则发送者缓冲区可 用: 同步发送:发送操作可在相应的接收前后发生,但仅在接收完成后才返回( 完成) 。 图3 1 描述了点到点通信的一般形式。 阻塞发送阻塞接收 d 数据发送 - 习 返回返回 非阻塞发送 数据未接收 非阻塞接收 d口 返同返同 3 5 2 通信器 图3 - 1 m p i 中点到点通信 m p i 的一个关键特征就是通信器,以对象形式存在,作为通信操作的附加参数。 通信器为开发消息传递程序提供了模块化支持,从而强有力地支持开发并行库和大规 1 6 模代码。通信器的概念来自于z i pc o d e 和c c l 的全局通信。在m p i 中,进程以组内的 相对l a n k 来标识,通信器参数则说明所涉及的进程组,使用该通信器的通信操作限制 在该进程组的进程之间。这样,一组进程集上的库代码被用于另一组进程集时,库代 码无需改动,而只要重定义描述该进程集的通信器。每一个通信器定义了一个唯一的进 程组通信上下文。由上下文和区别消息的t a g 一起来进一步区别不同进程上下文的 具有同一一个标识的消息。上下文由系统严格管理,对用户是透明的,有力地保证了库 代码的消息通信互不干扰。m p i 提供了各种机制用于创建和管理通信器。在初始化时 预定义一个通信器( i v i p i c o m m w o r l d ) ,相应的进程组包含了初始化时存在的所有 进程。 3 5 3 全局通信 m p i 有一组丰富的全局通信函数,包括b a r r i e r s y n c h r o n i z a t i o n 、b r o a d c a s t 、s c a a e r 、 g a t h e r 和各种归约操作。通信器用来标识参与全局通信的进程组,这样全局通信可以 包括任意预定义的进程子集。 3 6 m p i 语言绑定 由于m p i 是一个库而不是一门语言,因此对m p i 的使用必须和特定的语言结合 起来进行。f o r t r a n 是科学与工程计算的领域语言,而c 语言是目前使用最广泛的 系统和应用程序开发语言之一,所以在m p i 规范中,m p i 与f o r t r a n 和c 都做了 绑定,目前c + + 也得到了支持。 3 7 m p i 数据类型 m p i 引入消息的数据类型( d a t at y p e ) 属性的目的有两个:一是支持异构系统计 算:二是允许消息来自不连续的或类型不一致的存储区,例如,可以传送数组的一列, 或传送一个结构值,而该结构的每个元素的类型不同。d a t a t y p e s 定义了消息中不连 续的数据项及其可能不同的数据类型。d a t a t y p e 由应用程序在执行时通过基本的数 据类型创建。对于c 和f o r t r a n ,m p i 均预定义了一组数据类型( 如m p i - f l o a t 、 m p i c h a r 等1 ,这些与语言中的数据类型相对应。另外,用户可自定义其它的数据 类型,如多维向量或类c 语言中的结构。m p i 还允许发送和接收不同的数据类型,使 得数据重映射方便灵活。 3 8 m p i 的主要实现 m p i 处于讨论阶段时,就已经出现了m p i 的模型实现,m p i 标准发布后,国际上 已有许多m p i 实现,其中以自由软件形式发布的l a m 和m p i c h l l 8 1 较为流行。 l a m ( l o c a l a r e am a c h i n e ) 是o h i o 超级计算中心开发的基于异构网络机群的并行 程序支撑环境,向用户提供m p i 编程界面及一个完整的运行调试环境。l a m 的结构 是开放的、高度结构化的。其运行代码由三部分组成:d a e m o n 、接口库及维护调试工 具( l a m 命令) 。l a m 启动后,在虚拟机的每一个节点上运行一个d a e m o n ,用户通过 l a m 的加载命令以s p m d 或m p m d 形式将任务加载到指定的节点上运行,用户通过 调用库接口完成消息传递。l a m 支持动态进程组及虚拟机的动态扩充。 m p i c h

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论