（计算机应用技术专业论文）基于机群的并行计算环境研究及其在occam反演中的应用.pdf

桂林工学院硕士学位论文 基于机群的并行计算环境研究及其在o c c a m 反演中的应用 摘要 机群以其良好的灵活性和可扩展性及性能价格比，获得了越来越多的大学及科 研机构的青睐。目前的许多研究是在并行机机群或工作站机群上进行的。本文介 绍了并行计算的基本理论及支持网络并行计算的环境p v m ( p a r a l l e lv i r t u r a l m a c h i n e ) 。以最小成本建立了基于p v m 的c o w ( c l u s t e r0 fw o r k s t a t i o n ) 型的p c 机群并行系统，为此后的o c c a m 反演的并行提供了必要的硬件基础。首先搭建多 节点机群，然后利用p i n g p o n g 原理对节点间的通信延迟进行了测试，以及利用矩 阵相乘对机群的性能进行了测试，其加速比和效率最高分别达到了4 7 8 与0 8 5 ， 则该机群的性能比较理想。此外，在该机群环境下，注意了并行粒度的控制，尽 可能地减少通信次数。 其次，在大地电磁( m t ) 反演方法中，o c c a m 反演由于其稳定收敛以及不依 赖于初始模型的特性而得到广泛应用，但是拉格朗日乘子的求取导致大量的模型 正演，使得反演速度较低。为此，本文研究了用基于p c 机群的并行计算来解决这 一问题的方法。首先首先全面分析了o c c a m 反演基本原理和方法，挖掘了计算中 的并行成分；然后拉格朗日乘子扫描采用u 值计算一级的大粒度并行；给出了并 行计算的实现方法与实现流程图，将扫描任务编组分派到不同的节点完成，即在 p c 机群上，利用主一从编程模式实现o c c a m 反演的并行计算。主进程( m a s t e r ) 维 持全局数据结构，负责任务的划分和派发以及计算结果的接收和组合；子进程 ( s l a v e ) 负责给定任务的计算以及计算结果的返回。对于l l 值采用扫描方式时计 算量相对较大，但能提供给定区间中各u 值的拟合差曲线，且由于p 值点固定， 计算也独立，因而利用扫描方式实现并行。除此之外，在形成偏导数矩阵过程中， 由于正演部分各频点是独立计算的，频点间不存在数据的关联，采用基于频点计 算的大粒度并行方式。 此外，负载均衡也是要考虑的问题，综合平衡各节点的计算量，可获得更为合 理的并行效率。由于主进程计算量不大，为充分利用资源，不设置专用的控制节 点，主进程节点同时也用作子进程节点。同时根据实验数据，可以看出运行时间 都达到了令人满意的效果，由此看来可以显著地提高反演速度。除此之外，还得 出了关于p c 机群一些有意义的结论。 关键词：机群，并行计算，p v m ，o c c a m ，大地电磁 桂林工学院硕士学位论文 a b s t r a c t p cc l u s t e ri sm o r ea n dm o r ep o p u l a ri nu n i v e r s i t i e sa n dt h es c i e n t i f i cr e s e a r c h o r g a n i z a t i o n ，o w n i n g t oi t s f l e x i b i l i t y , e x t e n s i o na n dt h ep e r f o r m a n c et h a tp r i c e c o m p a r e dt o a tp r e s e n t ，m a n yr e s e a r c ha r ec a r r i e do u ti nt h ep a r a l l e lc l u s t e r so rt h e c l u s t e ro fp c t h i sa r t i c l ei n t r o d u c e dt h et h e o r yo fp a r a l l e lc o m p u t i n ga n dp a r a l l e l v i r t u r a lm a c h i n et h a ts u p p o r t sn e t w o r kp a r a l l e lc o m p u t i n g b ys m a l l e s tc o s t ，w eh a v e e s t a b l i s h e dc o w ( c l u s t e ro fw o r k s t a t i o n ) t h a tb a s e do np v m ，w h i c hh a sp r o v i d e dt h e e s s e n t i a l h a r d w a r ef o u n d a t i o nf o rc o m p u t i n go ft h eo c c a l ni n v e r s i o n f i r s t ，w eb u i l dt h e m u l t i p o i n tp cc l u s t e r , s e c o n d ，w et e s tt h ec o r r e s p o n d e n c ed e t e n t i o no ft h ep o i n tt o p o i n tt h a tu s e st h ep i n g p o n gp r i n c i p l ea n dt h ep e r f o r m a n c eo ft h ep cc l u s t e rt h a tu s e s m a t r i xm u l t i p l i c a t i o na sw e l l ，w h a ta c c e l e r a t i o na n de f f i c i e n c ya c h i e v e d4 7 8a n do 8 5 ， t h e nt h ep e r f o r m a n c eo ft h i sc o wi sq u i t eg o o d i na d d i t i o n ，w es h o u l dc o n t r o lt h e p a r a l l e lg r a n u l a r i t y , r e d u c et h ec o r r e s p o n d e n c ea sf a ra sp o s s i b l e i ne a r t he l e c t r o m a g n e t i s m ( m t ) i n v e r s i o nm e t h o d ，o c c a mi n v e r s i o ni su s e d w i d e l yb e c a u s eo fi t ss t a b l yr e s t r a i n sa sw e l la sd o e sn o tr e l yo nt h ei n i t i a lm o d e l c h a r a c t e r i s t i c b u to b t a i n i n gt h el a g r a n g ev a l u ec a u s e st h em o d e lt od e v e l o pm a s s i v e l y , t h et h ei n v e r s i o ns p e e di sv e r ys m a l l t h e r e f o r e ，t h i sa r t i c l es t u d i e dt h em e t h o dt os o l v e t h i sp r o b l e mb yp a r a l l e lc o m p u t i n gw h i c hb a s e do nt h ep cc l u s t e r f i r s t ，e l a b o r a t i n g o c c a mi n v e r s i o n ；s e c o n da d o p t i n gg r e a tg r a n u l a r i t yp a r a l l e lo fl a g r a n g es c a nw h i l e c a l c u l a t e st h ev a l u eo fl a ；t h e np r o d u c i n gt h er e a l i z a t i o nm e t h o da n dt h ef l o wc h a r to f t h ep a r a l l e lc o m p u t i n g w ed i s t r i b u t e dt h es c a nd u t yg r o u pt od i f f e r e n tp o i n t ，n a m e l yo n t h ep cc l u s t e r r e a l i z e dt h ep a r a l l e lc o m p u t i n go ft h eo c c a mi n v e r s i o nb ym a s t e r - s l a v e p r o g r a m m i n gp a t t e ro nt h ep cc l u s t e r t h e m a s t e rp r o c e s sm a i n t a i n st h eo v e r a l l c o n s t r u c t i o no fd a t a ，i sr e s p o n s i b l ef o rt h ed u t yd i v i s i o na n ds e n d i n ga sw e l la st h e r e c e i v i n ga n dc o m b i n a t i o no fc o m p u t i n gr e s u l t ；t h es l a v ep r o c e s si sr e s p o n s i b l ef o r c o m p u t i n gt h ea s s i g n e dd u t ya n dr e t u r n i n gt o t h ec o m p u t e dr e s u l t t h ew a yt h a t c o m p u t e si xb ys c a n n i n g ，w h i c hn e e d sl a r g ea m o u n to fc o m p u t a t i o n ，b u ti tc o u l dp r o v i d e t h ec h iv ef i t t i n go fd i f f e r e n tpv a l u e ，a n dc o m p u t a t i o ni si n d e p e n d e n tb e c a u s eo fi t s f i x e d 斗v a l u e ，s ow ea c h i e v ep a r a l l e lc o m p u t i n gb ys c a n n i n g i na d d i t i o n ，i nt h e f o r m a t i o no fp a r t i a ld e r i v a t i v em a t r i xp r o c e s s ，t h es p e e c hp a r to ft h e 丘e q u e n c yi s i n d e p e n d e n t ，t h ef r e q u e n c yd a t ap o i n td o e sn o ta s s o c i a t ew i t he a c ho t h e r s ow ea c h i e v e p a r a l l e lc o m p u t i n go f p a r t i a ld e r i v a t i v em a t r i xb a s e do nt h ef r e q u e n c y 桂林工 学院硕士学位论文 i na d d i t i o n ，t h el o a de q u a l i z a t i o ni sa l s ot h e q u e s t i o nw h i c hw en e e dt oc o n s i d e r i f w eb a l a n c ev a r i o u sn o d e s c o m p u t a t i o nl o a d ，m a yo b t a i n m o r er e a s o n a b l ep a r a l l e l e f f i c i e n c y b e c a u s eo ft h es m a l lc o m p u t a t i o nq u a n t i t yo ft h em a s t e rp r o c e s s i no r d e r t ou s er e s o u r c e si nf u l l ，w ed on o te s t a b l i s ht h es p e c i a lc o n t r o lp o i n t ，t h em a s t e r p r o c e s s p o i n ta l s os e r v e sa st h es l a v ep r o c e s sp o i n t a tt h es a m et i m e ，s i m u l t a n e o u s l ya c c o r d i n g t ot h ee x p e r i m e n t a t i o nd a t a ，w ec o u l ds e et h a tt h er u n n i n gt i m ei s s a t i s f y i n g a n dr a i s e t h ei n v e i s i o ns p e e do b v i o u s l y i na d d i t i o n ，w ec o u l do b t a i n e s o m es i g n i f i c a n tc o n c l u s i o n a b o u tp cc l u s t e l k e y w o r d s ：p cc l u s t e r , p a r a l l e lc o m p u t i n g ，p v m ，o c c a m ，m t 桂林工学院硕士学位论文 研究生学位论文独创性声明和版权使用授权说明 独创性声明 本人声明：所呈交的论文是我个人在刘羽教授指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人 已经发表或撰写过的研究成果，也不包含为获得桂林工学院或其它教育机构的学位 或证书而使用过的材料。对论文的完成提供过帮助的有关人员已在论文中作了明确 的说明并致以了谢意。 学位论文作者( 签字) ：继錾盛 签字日期：盐近。上日 版权使用授权说明 本人完全了解桂林工学院关于收集、保存、使用学位论文的规定，即：按照学 校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子 版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手 段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。( 保 密论文在解密后遵守此规定) 学位论文作者( 签字) ：三丝趣盏 指导教师签字：o 玉 l 址 签字日期：刎l j = ：趁 桂林工学院硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! i ：i ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ! = ! ! ! ! 1 1 1 论题提出的背景 第一章引言 现代计算技术的不断进步，促进了工程结构设计手段的不断发展，而现代工程 技术的机构工艺的飞速发展又反过来刺激了计算分析技术的进步。随着科学研究 和工程技术的不断开拓和发展，出现了各种各样的大型或超大型的复杂结构，对 这些大型或超大型复杂结构进行有效地分析，需要高性能计算机。虽然目前计算 机发展很迅速，但是由于受元器件物理性能的限制，使得单机速度的提高逐步达 到了极限，单机硬盘也很有限。因此单机有效、省时地解决那些大型或超大型复 杂问题较困难。 在现有中央处理器的速度限制下，使用多个处理器进行大规模并行计算，能 有效地提高计算机的计算能力，解决各类“具有挑战性”的问题。例如：天气预报、 地震分析等等。于是高性能计算机研究热点就集中在并行计算上，即从计算机体 系结构上找出路，将多个性质相同的或不相同的处理机通过互联网络连在一起形 成并行计算机。”所谓并行计算机就是由一组处理单元组成的，这组处理单元通过 相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。”目前， 并行处理已经发展成现代计算机的关键技术之一。近年来，由于高速信息网络的 出现及其突飞猛进的发展，使得网络并行计算成了当前国际上并行计算的一个主 要方向。网络并行计算具有巨大的计算潜能，并且其良好的性能价格比和可扩展 性，以及灵活的体系结构等优点，使得网络并行计算特别适合于一般的研究部门， 这点很适合我国的国情。近年来，又出现了一批以p v m 、m p i 、e x p r e s s 为代表 的基于消息传递的并行程序设计软件平台，这又极大地方便了用户，保证了程序 的可移植性。 另一方面，大地电磁( m t ) 反演方法中，o c c a m 反演由于其稳定收敛以及不 依赖于初始模型的特性而得到广泛应用。与其它的反演方法一样，o c c a m 反演采 用扫描和一维搜索的方式选取拉格朗日乘子，使得正演计算量很大。在解决高维 和大型问题时，利用微机进行o c c a m 反演时的计算速度非常慢，因此提高反演速 度成为当前研究的一个重要内容。为此，本文研究了用基于p c 机群的并行计算来 解决这一问题的方法。 桂林工学院硕士学位论文 1 2 目前国内外的研究现状 自2 0 世纪7 0 年代初到现在，并行计算的物质基础即并行计算机的发展已有 很长的历史。并行计算机是指两个或两个以上的处理器连接起来，可以并发操作 的机器，这样的机器也称为多处理机。如在文献【1 】和【2 】中分别对并行计算机的发 展作了详尽的介绍。 首先是共享存储的对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) ，s m p 结构 具有以下的特性：对称性：系统中任何处理器均可以访问任何存储单元和i 0 设 备；单地址空间：所有数据均驻留在同一共享存储器中，用户不必担心数据的 分配和再分配；高速缓存及一致性：多级高速缓存可支持数据的局部性，而其 一致性可由硬件来增强；低通信延迟：处理器间的通信可由简单的读写指令来 完成( 而多计算机系统中处理器间的通信要用多条指令才能完成发送接收操作) 。 但是s m p 存在以下的问题：欠可靠：总线、存储器或o s 失效均会造成系统崩 溃：可观的延迟：一般为数百个处理器周期；慢速增加的带宽：有人估计， s m p 存储器总线带宽每3 年只增加2 倍，而i 0 总线带宽增加速率则更慢：不 可扩放行：这就限制了最大处理器的数目一般不能超过1 0 。由于s m p 存在的这些 限制，分布存储的大规模并行处理机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 i m d ，因为它的程序有多个进程，它们分布在各个微处理机上，每个进程有自己 独立的地址空间，进程之间以消息传递进行相互通信。虽然m p p 具有潜在的高 可扩放行、通用型和高可用性。可扩放行：系统能扩展至成千上万个处理器， 而存储器和i 0 的容量及带宽亦能按比例的增加；通用性和可用性：m p p 支持 异步m i m d 模式和流行标准编程模式( 如p v m 、m p i ) ，在不同层次上支持单一 系统映象。但是也存在以下的问题：系统成本：因为m p p 系统包含大量的元件， 系统的成本会相应地高出一些；通信：使用了高速、专用高带宽、低延迟的互 联网络，显然也会在一定程度上增加成本；i o 的发展还跟不上系统中其他部分 的发展。 因此，随着并行互连网络技术的发展和工作站性能的提高，由l a n 互连而成 的工作站机群c o w 逐渐盛行。c o w ( c l u s t e ro fw o r k s t a t i o n s ) 是实现并行计算的一 种新主流技术，是属于分布存储的m i m d 并行机结构，是由工作站和互连网络两 部分组成。它是利用通用的高速网络将一组高性能工作站或高档p c 机，按某种结 构连接起来，在并行程序设计以及可视化人机交互集成开发环境的支持下，统一 调度，协调处理，实现高效并行处理的系统。c o w 的优点：( 1 ) 性能价格比高： 桂林工学院硕士学位论文 由高性能节点处理机组成的并行系统，具有很强的处理能力。但相对同等性能的 。m p p 等系统来说，价格要便宜的多；( 2 ) 复用性强：系统中的机器既是普通的工 作站，又是并行系统中的一个节点处理机，这样可以资源共享，充分利用现有的 机器设备；( 3 ) 同时可以支持多种平台：由于c o w 一般是靠高层的软件提供并行 计算环境，因此，用户可以根据应用要求选择不同的节点处理机来构造机群；( 4 ) 可扩展性：一般来说，在系统通信允许的情况下，增加系统中节点的个数，能提 高机群的整体性能；( 5 ) 用户编程方便：机群系统中，程序的并行化只是在原有 的c 、c + + 或f o r t r a n 串行程序中，插入相应的通信原语。用户使用的仍然是熟悉 的编程环境，不用适应新的环境。正是基于这些优点，许多公司和研究部门都推 出了基于机群结构的并行计算机。c o w 作为重要的并行计算系统，在大学、研究 所和重点实验室广泛安装，得到了越来越多的应用。 1 3 研究目的及意义 大地电磁( m t ) 资料反演方法中，o c c a m 反演由于其稳定收敛以及不依赖于 初始模型的特性而得到广泛应用。与其它的反演方法一样，o c c a m 反演采用扫描 和一维搜索的方式选取拉格朗日乘子，使得正演计算量很大。在解决高维和大型 问题时，利用微机进行o c c a m 反演时的计算速度非常慢，因此提高反演速度成为 当前研究的一个重要内容。提高反演速度的有效途径包括：从算法上加以改进， 如吴小平等对拉格朗日乘子求取算法的改进【9 】，各种偏导数矩阵的算法简化等； 采用并行计算，将计算的时间复杂性转换为空间复杂性。我们研究了基于p v m 的 网络并行机群环境下o c c a m 反演的并行化方案，给出了具体的并行计算流程，进 行了反演实例的串行与并行计算时间的对比。结果表明，并行计算能够明显地提 高处理速度。并行计算是利用网络上的计算机资源实现大问题的并行计算，这使 得许多优秀算法得以广泛的应用，使得o c c a m 反演大型计算成为可能。因此，研 究基于机群并行计算在o c c a m 反演中应用的计算方法，网络计算环境及其实现技 术的应用软件具有十分重要的意义。 机群并行计算就是利用互联网上的计算资源、实现大问题的计算，这种并行 计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越 来越多的用户希望能具有并行计算的环境，但是除了少数计算大户( 石油、天气 预报) 外，很多用户由于资金的问题不使用并行计算机。一旦需要并行计算，就 可以通过网络实现高性能计算。目前，国内外一般的应用单位都具有局域网或广 域网的节点，所以基本上具备机群计算的硬件环境；其次，网络并行的系统软件 桂林工学院硕士学位论文 p v m 是当前国际上公认的一种消息传递标准软件系统，有了它，就可以在不具备并 行机的情况下进行并行计算。由于该软件是美国国家基金资助的开放软件，没有 版权问题，可以从国际互联网上获取其代码及其相应的辅助工具程序，这种计算 环境特别适合我国的国情。 桂林工学院硕士学位论文 2 1 并行性 第二章并行计算基本原理 并行性是在某一特定问题中具有可以同时进行运算或操作的特性。在同一时 刻或是同一时间间隔内完成两种或两种以上性质相同或不同的工作，它们在时间 上能互相重叠，都体现了并行性。并行性实际上包含了同时性和并发性两种特性， 同时性( s i m u l t a n e i t y ) 指的是两个或多个事件在同一时刻发生：并发性 ( c o n c u r r e n c y ) 指的是两个或多个事件在同一时间间隔内发生。为提高计算机系统 的并行性，可以通过时间重叠、资源重复和资源共享的技术途径来实现。 时间重叠( 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 ) 是指在并行性概念中引入空间因素。通过重复 设置硬件资源来提高可靠性或并行性能，在结构上，采用多操作部件和多存储部 件。资源重复是以提高可靠性为主，但是早期受限于硬件价格，目前随着硬件价 格的降低，资源重复被大量用于提高系统的速度性能，现在资源重复已经成为提 高并行性的重要方面。例如在一个微处理器芯片中设立多个功能部件以及大量微 处理器构成的大规模并行处理机( m p p ) ，流水线计算机等。 资源共享( r e s o u r c es h a r i n g ) 是利用软件的方法让多个用户按一定时间顺序轮 流地使用同一套资源，包括c p u 、主存、外设等硬件资源和软件、信息资源，以 提高其利用率，从而提高整个系统的性能。例如，多道程序分时系统等。 2 2 并行计算体系结构 并行计算技术自6 0 年代中期和7 0 年代后期分别出现以来，其并行处理方式经 历了从阵列机( s i m d ) 、向量机、共享存储的对称多处理器系统( s m p ) 、分布存储 的大规模并行处理系统( m p p ) 到计算机机群( c l u s t e r ) 的演变过程。并行体系结构是 并行计算的基础，各种并行程序设计机制也都是针对不同的并行体系结构的。由 文献 2 和 5 可知，并行体系结构大致可分为如下五类： 1 阵列处理机( s 1 m d ) 由成千上万个功能非常简单的处理机构成，数据以某 种方式流经各台处理机，由它们进行处理。s i m d 类型并行机对并行计算机的发展 桂林工学院硕士学位论文 起到了重要的推动作用，但由于微处理芯片技术的发展，9 0 年代以后，用于科学 与工程计算的s i m d 类型并行机己基本退出了历史舞台。 2 向量处理计算机( v e c t o rm a c h i n e ) 向量机除标量寄存器和标量功能部件 外，还专门设有向量寄存器和向量流水功能部件，能对向量运算进行高速处理。 3 共享主存储处理机系统( s h a r e dm e m o r ym u l t i p r o c e s s o rs y s t e ms m p ) 多个处 理机共享一个中央存储器，一般还设有专门的多机同步通讯部件，能支持数据并 行或控制并行的开发。但处理机数目太多时，各处理机到中央存储器的通道成为 瓶颈，这就限制了这类机器的发展，这也是分布主存大规模并行机发展起来的原 因之一。 4 分布主存多处理机系统( d i s t r i b u t em e m o r ym a s s i v e l yp a r a l l e l p r o c e s s o r s ，m p p ) 具有很多个结点构成的并行机，每个结点有自己的处理机和存储 器，结点之间以互连网络相连，主要支持数据并行开发，也能支持控制并行的开 发。处理机采用微处理器，互连网络有二维网络、三位网络、树、环、超立方等。 有些处理机作为控制和i 0 结点，有完整的操作系统、网络软件和用户界面，多数 处理机作为运算结点则只运行微内核操作系统。 5 计算机机群系统( c l u s t e ro f c o m p u t e r s ) 由高性能网络或局域网物理地互连 的全体计算机结点的集合。典型情况下，每个计算机结点是一台s m p 服务器、一台 工作站或是一台p c 计算机，结点可以是同构的，也可以是异构的计算机数目一般 为几个至几十个，支持控制并行或数据并行的开发。每个结点上都有完整的操作 系统、网络和用户界面，都可作控制结点或运算结点，即结点之间是平等的。机 群系统最近几年的表现引人注目，由于具有出色的性价比、灵活性和良好的并行 处理能力，除了广泛作为研究课题外，在各个行业的应用发展也很快。 2 3c o w 的体系结构 c 0 w 即工作站机群是利用高速通用网络将一组高性能工作站或高档p c 机，按某 种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境下，统一 调度，协调处理，实现高效并行处理的系统。从结构和结点的通信方式来看，它 属于分布存储系统，主要利用消息传递方式实现各主机之间的通信，由建立在一 般操作系统之上的并行编程环境利用消息传递方式实现各主机之间的通信及系统 的资源管理及相互协作，同时也屏蔽工作站及网络的异构性。对程序员和用户来 说，机群系统是一个整体的并行系统。r i s c 技术、网络技术和并行编程环境的发 展使得机群系统这一新的并行处理系统形式成为当前研究的热点。目前已实现和 桂林工学院硕士学位论文 正在研究中的机群系统大多采用现有商用工作站和通用l a n 网络，这样既可以缩短 开发周期又可以利用最新的微处理器技术。大多数机群系统的并行编程环境也是 建立在u n i x 或w i n d o w s 操作系统之上，尽量利用商用系统的研究成果，减少系统的 开发和维护费用。从体系结构上来说有以下几个特征： ( 1 ) 构成系统的所有节点都是完整的商用计算机系统。节点机可以是高档 p c 、工作站，也可以是s m p 。每个节点机上都安装有一份完整的商用操作系统。 ( 2 ) 连接各个节点的互联网络提供节点间高性能、高可靠和可扩展的通信 服务，人们将这种网络称为系统域网( s y s t e ma r e an e t w o r k ，简称s a n ) 。这种 网络通过网络接口卡( n e t w o r ki n t e r f a c e ，简称n i ) 连接到节点机的i 0 总线上。 其中，少数专用网卡连到系统的内部总线。 ( 3 ) 整个系统呈现给用户的是一个单一的系统映象( s i n g l es y s t e mi m a g e ， 简称s s i ) 。系统中所有分布的资源被组织成一个统一的整体，由用户管理、使用， 用户感觉不到单个节点计算机的存在。从用户的角度看，一个机群系统就如同一 个具有巨大配置的单一计算机系统。s s i 由几个方面的内容构成，主要包括单一登 陆点( s i n g l ee n t r yp i o n t ) 、单一控制点( s i n g l ec o n t r o lp o i n t ) 、单一文件系统( s i n g l e f i l es y s t e m ) 、单一内存空间( s i n g l e m e m o r y ) 、单一作业管理( s i n g l ej o b m a n a g e m e n t ) ，此外，还有单一用户界面( s i n g l eu s e ri n t e r f a c e ) 、单一进程空 间( s i n g l ep r o c e s ss p a c e ) 等等。s s i 是机群系统中的关键技术之一。 ( 4 ) 整个系统具有高可用性( a v a i l a b i l i t y ) 。由于机群系统中的每个节点都 是一个完整的计算机系统，都有一个完整的操作系统映象，因此一个或几个节点 的崩溃不会导致整个系统停机，当节点出现故障时，这个系统可以降级使用直至 崩溃的节点得到修复，系统域网( s a n ) 是连接一个机群系统内部所有节点并且 向用户提供高性能、高可靠通信服务的网络软硬件设施的总和。一般来说，系统 域网只是用于系统内部互联，无需考虑对异种节点间通讯的支持，而且节点间也 是互相信任的( 可能牺牲安全以换取速度) ，这是系统域网实现高性能的一个重 要前提。目前人们讨论系统域网时多是指网络硬件( 包括n i ) ，而不涉及节点上 所采用的通讯软件。从机群节点互连的需要考虑，系统域网一般具备如下特征： ( 1 ) 系统域网应该能提供高通信带宽和低通信延迟。 ( 2 ) 系统域网应能保证数掘传输的可靠性。 ( 3 ) 系统域网应该具备良好的可扩展性，以适应不同规模的系统通信要求， 保证机群在不同的软硬件配置下均能提供高性能的服务。 ( 4 ) n i 智能化，由网卡自主完成尽可能多的通信控制功能，从而减轻节点c p u 的负担。 桂林工学院硕士学位论文 l 三e 昌；”“；璺；i ：! 鬟摹受专螽磬。息姥闯 il 厂丐元趸 li l i 忑i ； ：。：毒萤l 葫萎j 一 强兰窝霎：| | 粪| | 萎薹透镊褥 商品化硒络( 以太髑 了i 等) 幽2 - 1 机群的典型系统结构仍 机群的优点如下： ( 1 ) 可利用性 由于机群中每个结点都是传统的工作站，因此有大量现存的应用软件可以使 用，可以辅助编程。 ( 2 ) 容错性 由于系统中有大量冗余的软、硬件资源，因此即使部份结点失效，整个系统 仍能正常运作。 ( 3 ) 可伸缩。眭( s c a l a b i l i t y ) 增加系统的结点即可提高系统的性能。 ( 4 ) 性能价格比 机群以低廉的价格，拥有高性能计算机的计算能力，并能在其上研究适用于 m p p 的并行算法。使用己有的计算机及网络资源组建机群系统，则只须极少的资源 即能获得巨大的计算能力。 机群的缺点如下： 较难编写机群并行程序，特别当该系统中的计算机为异构机时，程序员必须 对整个系统的结构，包括网络结构有完整的了解，然后针对系统特定的结构编写 并行程序，才有可能获得高效的效率。网络的性能对系统的性能有重要的影响， 因此若选用较快速的网络，能大幅提高系统的性能。 2 4 并行计算模型 并行计算模型是研究并行算法的性能和开发具有可移植性的并行程序而建立 的一种理论计算模型。并行计算模型为并行计算提供了硬件和软件的界面，在该 桂林工学院硕士学位论文 界面的约定下，并行系统的硬件设计者和软件设计者可以开发对并行的支持机制， 从而提高系统的性能。并行计算模型的主要作用如下： 。 ( 1 )并行算法实现的基础：并行算法设计与分析依赖于并行计算模型，通常 人们针对同一问题可设计出多种不同算法以适应在不同模型上对该问题的求解， 并分析和评价并行算法的优劣。 ( 2 ) 给并行算法设计与分析提供了一个简单、方便的框架：由于并行计算模 型抽象了一类并行计算机的基本特征，避开了硬件结构过多的繁琐细节的限制， 从而保证了它在相当范围内的通用型，同时又能反映出不同算法的主要特征，为 算法设计提供启发、指导和评价的依据。 ( 3 ) 使并行算法设计具有一定的生命力：算法设计者避开了多种多样的具体 的并行计算机结构，依据并行计算模型来设计算法，这样，一方面可使研制者集 中精力开发应用问题固有的并行性，分析算法性能：另一方面设计出的算法具有 通用性，从而使并行算法的研制成为一项相对独立的活动。 1 9 7 8 年，s f o r f u n e 等提i 出p r a m ( p a r a l i e lr a n d o ma c c e s sm a c h i n e ) 模型，它是 简单的共享内存模型，适合于并行算法表达分析、比较，但太抽象，因此，针对 p r a m ，198 9 年，p b g ib b o n s 提出了 q s m ( q u e u e ds h a r e dm e m o r ym o d e 模型a p r a m 模型( a s y n c h r o n o u sr a m ) ，1 9 9 0 年v o l i a n f 提出了b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型，它是关于通信的模型，1 9 9 2 年a p a r n o y 等人提出了p o s t a l 模型，它是用于 消息传递系统，1 9 9 3 年c u l l e r 等人提出t p o s t a l 模型，它是分散控制和点到点通信 多处理机系统的一个并行计算模型，1 9 9 6 ，s e h a m b r u s h 等人提出了c u l ( c o m p u t a t i o n c o m m u n i c a t i o n ，c o n g e s t i o n ) 模型，它是一个与体系结构无关的粗粒度 并行计算模型。这些模型的发展过程，恰好体现了当代并行计算的发展过程：从共 享存储到分布存储，从同步到异步，它们一个比一个更接近实际，更加不断完善。 目前几种典型并行计算模型如下： ( 1 ) p r a m 2 1 模型：由若干处理器和一个全局可寻址的共享存储器组成，共享存 储器存放处理机执行的程序和要访问的数据，所有处理器采用同步方式，规定对 存储器访向为四种模式，即e r ( 互斥读) 、e w ( 互斥写) 、c r ( 并发读) 、c w ( 并发写) ， 相应于p r a m 为四种计算的模式。p r a m 的特点为：采用全局时钟同步控制，所有指令 均按锁步( l o c k - s t e p ) 方式操作，未考虑通信延迟；存储访向冲突和带宽等对实际 性能影响；每个处理器均在单位时间内访任何单元，但这很难做到。 ( 2 ) a p r a m 模型：基于p r a m 做了如下改进和补充：首先考虑存储器访问，冲突 和通信延迟，如存储竞争模型，延迟模型，局部模型等：其次改同步控制为异步 控制，如分段模型，层次模型等。 桂林工学院硕士学位论文 ( 3 ) b s p 模型：整个计算由一系列全局同步分开的，时间间隔为l 的超级步组成， 每个处理单元执行一个任务，处理器利用在超级步之前( 上一超级步) 准备好数据， 进行局部计算，并选择路由接收或发送消息。 ( 4 ) p o s t a l 模型：其定义为m p s ( n ，x ) ，其中n 为处理机数目，x 为消息的通 讯延迟，x 乏1 ，它是基于分散存储异步控制和点到点通信多处理机系统的一个计 算模型。 ( 5 ) l o g p 啪3 模型：取消了b s p 中超级步同步限制，扩充了b s p 模型通信开销描 述，由四个基本特性参数描述，l ：网络通信延迟，0 ：启动开销，g ：连续通信间隙， p ：处理机数目，l o g p 上计算表示为一组相互独立运行的进程或任务。抓住了网络 与处理机之间的性能瓶颈，处理机之间异步工作，并通过处理机间的消息传送来 完成同步，对多线程技术有一定的反映，可以估算算法的实际运行时间。 ( 6 ) c 3 乜1 ：它以工作站或高档微机组成的高性能可扩放的并行机群系统为目 标，意在能反映计算复杂度和通信模式与通信期间潜在的拥挤等诸因素对粗粒度 网络算法影响。主要由5 个参数描述：p ：处理机个数，h ：网络延迟，b ：网络的 对分宽度，即将网络等分成2 个子网络时所需断开的处理机连接的个数，s ：启动 时间，l ：消息包的长度，即消息包所包含的字节数。该模型可以度量网络的拥挤 对算法性能的影响；考虑了不同路由和不同发送或接收原语对通信的影响；不需 要用户指定调度细节，就可以评估超步的时间复杂性；给编程者提供了k 级路由的 思路。 ( 7 ) 互连网络模型：基于并行机互连网络结构的分散存储计算模型，强调并行 机拓扑结构特性。算法设计采用同步或异步控制，常用的有一维线性连接网，网 孔连接网，树型连接网，金字塔网和超立方连接网等多种，它只允许相邻处理器 直接通信，不相邻节点必须经中间结点转发。 2 5 并行算法的基本概念 2 5 1 并行算法的定义与目标 算法是解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定 类型问题的一系列运算。因此，并行算法可如下定义： 定义2 1 并行算法是一些可同时执行的诸进程的集合，这些进程互相作用和 协调动作从而达到给定问题的求解。 更一般来讲，并行算法是指在各种并行计算机上求解问题和处理数据的算法， 其本质是把多任务映射到多处理机中执行，或将现实的多维问题映射到具有特定 桂林工学院硕士学位论文 拓扑结构的多处理机上求解。 从计算复杂性的角度来考虑，一个算法的复杂性可表示为时间复杂性和空间 复杂性。从算法的结构来看，通常的串行算法树“深而窄”，这是因为传统的串 行算法是为一维问题设计的。比如，串行算法的常用手段递推算法，此时大型计 算则靠增加算法树的深度来实现。 并行算法的目标尽是可能减少时间复杂性，这通常是通过增加空间复杂性( 如 增加空间的维数及增加处理器的台数) 来实现的。所以，并行算法树采用截然不 同的“浅而宽”结构，即每个时刻可容纳的计算量相应增加，这样使整个算法的 步数尽可能地减少，或者说，通过增加每个时刻步的算法复杂性来减少整体的时 间复杂性。这样，就达到了把时间复杂性化为空间复杂性的目的。 定义2 2 粒度：是多个处理机可独立并行执行的任务大小的量度。大的粒度意 味着能独立并行执行的是大任务，而小的粒度意味着能独立并行执行的是小任务。 粒度是一个相对概念，与算法固有内在并行度和具体并行机有关。对于不同类型 的并行计算机，适合它的粒度等级是不同的。例如，大规模并行机，适合中等粒 度的并行，而在网络