（应用数学专业论文）二维浅水波方程组的并行算法研究.pdf

摘要摘要高精度高分辨的无结构网格有限体积法是一种守恒型的高性能算法。这种算法现被越来越多的引进到守恒型浅水波方程的数值计算中。本文基于这种求解二维浅水波方程组的数值模型，对二维浅水波方程组的并行算法进行了研究。并行计算是目前提高计算速度的最有效的方法之一。本文对并行计算中的一些基本知识进行了介绍，并说明了并行程序设计所涉及到的并行程序设计模型、并行程序设计方法、并行编程模式等。对本文进行研究的物理平台一一联想机群进行介绍，同时给出了与f o r t r a n 捆绑使用的并行库m p i 的常用接口的调用方式、参数说明等。通信直接影响着并行计算的性能，本文主要介绍了m p i 的点点通信和组通信。介绍了本文求解二维浅水波方程组所采用的商精度高分辨的无结构网格有限体积数值模型。区域分裂算法是并行计算中的重要方法之一。本文对于无结构网格的区域分裂问题，建立了以最小化最大执行时间为目标函数的m m e t 区域分裂的数学模型，设计了求解该模型的算法。通过计算得出了较好的理论并行加速比和并行效率。在该算法基础上，进一步改进算法，使得采用新算法后，求解该模型的计算效率和计算精度都得到了提高，尤其是计算效率有较大的提高。采用本文建立的m m e t 区域分裂模型，对无结构网格进行了区域分裂。对区域分裂后得到的数据进行预处理，为并行计算的执行作数据准备。采用对等模式和标准通信模式，在原有的串行程序基础上进行了并行程序的设计。最后对己有的采用高精度高分辨的无结构网格有限体积数值模型对钱塘江涌潮进行二维数值模拟的串行程序进行了并行化，并且在联想机群上进行了并行实现。关键词：浅水波方程，并行计算，并行m p i 库，无结构网格，区域分裂，高性能有限体积法摘要a b s t r a c tt h eh i i g ho r d e ra n dh i g hr e s o l u t i o nf i n i t ev o l u m em e t h o di sac o n s e r v a t i v eh i g h - p e r f o r m a n c ea l g o r i t h i ns c h e m eo nu n s t r u c t u r e dg r i d s i ti sb e i n gu s e dt os o l v et h en u m e r i c a lc a l c u l a t i n go fs h a l l o ww a t e re q u a t i o nm o r ea n dm o r e b a s e do ni t , t h ep a r a l l e lc o m p u t i n go f 2 ds h a l l o ww a t e re q u a t i o n sw a sr e s e a r c h e d t h ep a r a l l e lc o m p u t i n gi so n eo ft h em o s te f f e c t i v ew a y st oi m p r o v et h ec a l c u l a t i n gs p e e da tp r e s e n t s o m ef u n d a m e n t a lk n o w l e d g eo f p a r a l l e lc o m p u t i n gw a si n t r o d u c e d , p r o g r a m m i n gm o d e l s 、p r o g r a m m i n gm e t h o d s 、p r o g r a m m i n gp a t t e r n sa n ds oo nw h i c hi si n v o l v e di np a r a l l e lp r o g r a m m i n gw e r ed e s c r i b e d l c n o v oc l u s t e rw a si n t r o d u c e da st h ep h y s i c a lp l a t f o r mo ft h es t u d y a l s o , t h ec a l l i n gm e t h o d , p a r a m e t e re x p l a i n i n go ft h eu s u a li n t e r f a c ei nm p lw h i c hi sal i b r a r yu s e dw i t l it h ef o r t r a nl a n g u a g ew g l eg i v e no u t t h ep e r f o r m a n c eo fp a r a l l e lc o m p u t i n gw a si n f l u e n c e db yt h ec o m m u n i c a t i o nd i r e c t l y m a i n l y , t h ep o i n t - t o - p o i n tc o m m u n i c a t i o na n dt h ec o l l e c t i v ec o m m u n i c a t i o n sw e t p r e s e n t e d t os o l v et h e2 - ds h a l l o ww a t e re q u a t i o n s ，t h en u m e r i c a lm o d e lw h i c ha d o p t e dt h eh j i g ho r d e ra n dh i g hr e s o l u t i o nf i n i t ev o l u m em e t h o do nu n s t r u c t u r e dg r i d sw a si n t r o d u c e d d o m a i nd e c o m p o s i t i o na l g o r i t h mi so n eo ft h em o s ti m p o r t a n ts c h e m e si np a r a l l e lc o m p u t i n g a b o u tt h ed e c o m p o s i t i o no fu n s t r u c t u r e dg r i d s ，am a t h e m a t i c a lm o d e l ( m m e t ) h a sb e e nb u i l t ，w h i c hm j l l i m i z i n gt h em a x i m u me x e c u t i o nt i m eo fs u b - d o m a i n sw a sm a d ea so b j e c t i v ef u n c t i o n t h e n , a na l g o r i t h mw a sd e s i g n e df o rt h i sm o d e l b yc a l c u l a t i n g , ag d o ds p e e d u pa n de f 五c i e n c yw e r ea c h i e v e d 。a tt h eb a s i so f t h ea l g o r i t h m , an e wa l g o r i t h mw a sg i v e no u t u s i n gt h en e wo n e ，t h ea d v a n t a g eo ft h en o wa l g o r i t h mo nc o m p u t i n gr e s u l ta n dc o m p u t i n ge f f i c i e n c yw a sa p p r o v e d ,e s p e c i a l l yo nc o m p u t i n ge f f i c i e n c y a b o u tt h ed o m a i nd e c o m p o s i t i o no fu n s t r u c t u r e dg r i d s ，t h em m e tm o d e lw a sa d o p t e d a f t e rt h ed o m a i nd e c o m p o s i t i o n , t h ed a t aw e r ep r e h a n d l e df o rp a r a l l e lc o m p u t i n g p a r a l l e lp r o g r a m m i n gw a sd e s i g n e do nt h eb a s i so fs e r i a lp r o g r a m m i n gb yu s i n gp e e r - t o - p e e rm o d ea n ds t a n d a r dc o m m u n i c a t i o nm o d e f i n a l l y , t h es e r i a lp r o g r a m m i n gw h i c hh a sb e e np r o g r a m m e df o rs i m u l a t i n go ft h et i d a lb o r ei nq i a n t a n ge s t u a r yw h i c ha d o p t e dt h eh i 曲o r d e ra n dh i r 曲r e s o l u t i o nf m i t ev o l u m em e t h o dw a sp a r a l l e l i z e do nt h el e n o v oc l u s t e r k e yw o r d s ：s h a l l o ww a t e re q u a t i o n , p a r a l l e lc o m p u t i n g ，m p i ，u n s t r u c t u r e d 鲥d s ，d o m a i nd e c o m p o s i t i o n ，f i n i t ev o l u m em e t h o dn学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。论文作者c 签名，；二之么乙鑫一7 年弓月叫日学位论文使用授权说明河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。敝储c ：蔓幽l 一刁年弓月孑日第一章绪论第一章绪论1 1 研究背景及意义当科学技术发展到上世纪六七十年代后，工程与科学研究领域中涌现出了一系列规模巨大，时限要求较高的数值计算问题。例如：卫星图像数据分析、长期数值天气预报、油田整体油藏模拟、流体分析、核武器数值模拟、航空航天飞行器的设计、微观世界模拟等等，都向传统的手工计算和基于v o nn e u m a n n 串行机计算技术提出了挑战。单处理器的v o nn e u m a n n 串行机，既要受到顺序处理的限制，其电信号传播速度又要受到光速限制，而且所采用的超大规模集成( v l s i ) 器件本身的开关速度也有物理极限。因此，早期发展起来的以v o nn e u m a n n 型计算机为工具的串行处理技术，其信号处理与数值计算速度已经越来越无法满足大型工程建设相关数值分析和科学计算的需要。为了克服传统的串行机对提高运行速度的限制，从6 0 年代起，人们就开始探索数值计算方法的并行化技术和计算结构的并行化设计方法。近二十年来0 , 2 1 ，以并行计算技术、并行算法和并行计算机结构为核心的并行化技术受到了国际国内计算数学界、计算机科学界乃至整个工程与科学界的广泛重视。1 9 8 9 年3 月，美国国防部提出的一项旨在保持其国际技术领先地位的报告中明确地将“并行处理”列为2 2 项重大项目的第3 项；日本政府则将并行技术与软件工程和人工智能并列为重点发展的三大技术；在国内，并行技术近年来也受到了极大的关注，在航天、气象和石油勘探等领域，国家先后投巨资研制出了速度达上亿次以上的巨型阵列式并行处理机银河1 号( y h - i ) 和由4 台( y h 1 ) 耦合而成的银河2 号( 壬- 2 ) 计算机。浅水动力学起源很早，于1 8 7 1 年提出的一维非恒定流的圣维南方程嘲( 称为一维浅水方程) 可作为近代浅水动力学研究的里程碑。后来圣维南方程又被推广为二维浅水方程组。只是到y 2 0 世纪5 0 年代电子计算机被广泛应用以及受计算气动力学进展的带动，经过4 0 年的努力，才逐步走出一条新路一计算浅水动力学。它是以流体力学为理论基础，并与计算数学，基础数学，应用数学以及计算机科学密切相关。由于水流流动的复杂性，使得流场数值计算的工作量非常巨大，以至于即使是运算速度最快的单机也无法仔细模拟大型工程流场问题。为此，激发了许多计算工作者一直在寻求行之有效的算法来提高计算速度。然而尽管改进的串行算法可以在一定程度上提高计算效率，但经过大量的实验和理论分析，人们发现并行计算方法更为有效。然而，并行计算技术在在我国计算流体动力学领域，对于河道、海洋方面的应用研究还非常少，对于浅水流动的并行计算更是几乎刚刚开始。因此，本文对二维浅水波方程组的并行计算进行研究是对这一领域的探索，具有河海大学硕士学位论文一定的学术意义；另一方面，通过并行计算提高了求解浅水问题的效率，节约了大量的科学研究时间，具有一定实际应用价值，而且并行计算也是当前及将来科学计算的一个必然趋势和方向。1 2 课题研究现状目前国内外对于浅水流动的并行计算主要有以下途径：( 1 ) 并行有限元方法( p a r a l l e lf i n i t ee l e m e n tm e t h o d )该方法多用于固体力学中的结构并行分析领域，它开展的研究很早，成果也很多，研究范围涵盖了整个结构有限元分析领域，主要包括弹性静力分析、非弹性分析、动力分析、耦合分析、断裂分析、自适应有限元分析、随机有限元分析和网格生成等。随着并行有限元理论的日益成熟，它也逐渐被运用到浅水动力学等非结构领域。近年来国外主要的研究工作发表的有：1 9 9 5 1 9 9 7 年问 4 , s j s l ，k a z i ok a s h i y a m a ，k a t s u y as 越t o h 等人在无结构网格上讨论了大规模风暴潮和潮流的并行有限元方法，并采用并行有限元方法模拟了东京湾1 9 5 9 年的涌浪。2 0 0 2 年1 7 1 m m o r a n d ic e c c h i ，m a p i r o z z i 对v e n i c el a g o o n 的潮汐运动采用并行有限元方法在m i m d 分布式多处理机上进行了数值模拟。国内这方面的研究工作略晚且很少，根据所查到的资料和文献，清华大学的江春波教授2 0 0 2 年【1 9 1 在水利学报上发表的论文中采用该方法首次实现了二维浅水流动的并行数值模拟，为应用并行计算这一技术进行大规模洪水预报和水环境的数值模拟进行了初步探索。( 2 ) 基于有限体积法( p a r a l l e lf i n i t ev o l u m em e t h o d ) 的并行计算有限体积法早在二十世纪五十年代末就开始发展，但一般认为是m c d o n a l d z在1 9 7 1 年【3 j 首次用于求解二维欧拉方程提出的。将有限体积法应用于浅水流动的模拟是从8 0 年代开始的。但是直到9 0 年代中后期才有了较多的发展。在此期间有限差分方法占据了主导地位，有限元法也得到了飞速发展。相对而言，有限体积法的研究却很少，但其产生的背景和特点已经逐步显示出它的优势。有限体积法吸收了有限差分和有限元的一些重要思想和技巧。它具有有限差分的简单高效性，计算量与有限差分法相仿，同时又拥有有限元的几何灵活性( 可以方便的用于无结构网格) 。能够方便地数值模拟复杂边界的流场问题。近年来经过改进的高精度高分辨有限体积法被越来越多的应用于求解溃坝、洪水演进、河口涌潮等间断流问题。因此，目前国内外已发表的文献主要集中在应用有限体积法计算含有间断水流的流场运算。而对于应用有限体积法对浅水流动进行并行计算的研究也是第一章绪论刚刚起步。国外主要的研究成果有：2 0 0 3 年i 1 0 1 第1 6 届a s c e i 程技术会议上b r e t tf s a n d e r s ，j o h nc p a u 采用隐式有限体积浅水模型在并行b o e w u l f 机群上对一个假设的长为4 0 0 0 米，宽为2 5 0 0 米，平均水深为6 米的矩形盆地进行了流场并行数值计算。在2 0 0 4 年【1 1 i 第8 届国际计算技术和工程年度论j c 云；( a n s c s e ) & p s u w a n- n a s r i ，j a s a v a n a m 等入对溃坝问题采用有限体积法进行了并行数值模拟。丽在国内，目前几乎还没有应用有限体积法进行并行计算的研究成果发表。本文正是基于无结构网格下的高性能有限体积法去求解二维浅水波方程组，从而设计出该有限体积模型的并行计算方法以期提高计算效率。( 3 ) 基于其它一些方法的并行计算研究基于差分法( f i n i t ed i f f e r e n c em e t h o d ) 求解浅水方程的并行计算0 2 i 。并行谱元素法【1 3 , 1 4 1 ( p a r a l l e ls p e c t r a le l e m e n tm e t h o d ) ，它是谱元素方法的并行化方法，谱元素方法是有限元和谱方法的一种折中，兼具有限元方法的灵活性以及谱方法的高计算精度，是一种典型的高阶非重叠区域分解方法。并行谱分析( ”i ( p a r a l l e ls p e c t r a lt r a n s f o r mm e t h o d ) 则是原有用于求解非线性浅水方程的谱分析方法结合消息传递模式产生的一种并行计算方法。1 3 本文的主要工作、结构和创新本文基于高精度高分辨的无结构有限体积数值模型求解二维浅水波方程组，针对整个计算区域的无结构网格的区域分裂问题建立了最小化最大执行时问的m m e t ( m i n i m i z i n g 函m 衄e x e c u t i o nt r i n e ) 数学模型，同时设计了求解该模型的算法，并进一步对原有算法进行了改进，从而解决了并行计算时的网格划分问题。然后将已有的串行计算程序经过并行性分析，改写成了并行程序。最后将每一个子区域对应于一个计算节点，并结合实际应用，基于分布式存储环境m p i ，在联想机群上实现了二维浅水流动的并行计算。本文共分为七章：第一章主要介绍了浅水流动并行计算的研究现状以及研究意义第二章对劳行计算进行了概述。主要介绍了几类当代主流并行机机型，并行程序设计模型，程序并行化方法，并行编程模式，一般并行程序设计过程以及并行计算的性能评价指标。第三章主要对构成本文所使用的机群( c l u s t e r ) 的硬件环境及软件环境作了叙述，并大致阐述了与f o r t r a n 捆绑使用的消息传递并行库m p i 的并行编程模式及特点等。河海大学硕士学位论文第四章介绍高精度高分辨的无结构有限体积法以及采用这种方法建立的二维浅水波方程组数值计算模型。第五章在整个计算区域上建立了无结构f v m 网格，针对无结构网格的区域分裂问题，建立了最小化最大执行时间的m m e t 区域分裂数学模型，同时对该模型的求解进行了算法设计，并且进一步改进了求解算法，将前后两种算法的计算效率进行了比较。结果表明，改进后的算法在计算时间和计算精瘦上都要比之前的算法好。第六章首先采用本文提出的区域分裂法对计算区域进行区域分裂，然后对得到的数据进行并行计算前的预处理，并结合f o r t r a n 7 7 和m p i 将原有的串行程序进行并行化设计。最后在联想机群上对钱塘江涌潮进行了二维数值模拟的并行实现。第七章总结和展望。对全文进行总结，并提出今后要进一步研究的主要问题。本文主要创新工作：( 1 ) 本文针对无结构网格的区域分裂问题，建立了一个最小化最大执行时间的m m e t 区域分裂数学模型，并设计了求解该模型的算法，得出了采用该模型进行并行计算的理论加速比和并行效率。( 2 ) 对已有的用于求解无结构网格区域分裂的m m e t 数学模型的算法作了进一步改进，并将新算法的计算结果和计算时间与原算法进行比较，结果表明新算法大大提高了应用该模型进行区域分裂的效率，同时计算精度也得到了一定的提高。( 3 ) 对采用m m e t 区域分裂模型进行分裂后所得到的数据进行了并行计算前的预处理，建立了存有各单元信息的数据库，便于调用。( 4 ) 对基于无结构网格的高精度高分辨有限体积数值模型求解二维浅水波方程组所编制的串行程序进行了并行性分析，在此基础上，采用对等编程模式以及f o r t r a n + m p i 并行编程语言对串行程序进行了并行化设计，并在联想机群上进行了并行实现。4第二章并行计算概述第二章并行计算概述2 1 当代的并行计算机结构体系当代的并行计算机系统已形成了多指令多数据流m i m d ( m u l t i p l e - i r m t r u e d o nm u l t i p l e d 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 i m d ( s i n g l e - i n s t r u c t i o nm u l t i p l e d a t a ) 随着计算机技术的笈展已逐步退出了历史舞台。当代主流并行机机型1 2 , 1 6 1主要包括：共享存储多处理机系统的对称多处理机s m p ；分布存储多计算机系统的大规模并行机m p p ；机群系统的大规模并行处理系统m p p 机群s p 2 和工作站机群c o w 。2 1 1 共享存储多处理机系统的对称多处理机s m p t ”i ( s y m m e t r i cm u t t i p r o c e s s o r )s n i p 并行机一般采用商用微处理器，通常有片上和片外c a c h e ，互连网络基于总线连接，系统存储器采用集中式共享存储，访存模型采用u m a ( 均匀存储访问模型) 结构。代表机器有：s g i p o w e r c h a l l e n g e ，d e c a l p h a s e r v e r ，d a w n i n g1 等。其结构模型如下：总线或交叉开关图2 1 对称多处理机s m i p 结构模型对称多处理机的优点在于：对称性，即任一处理器均可以访问任何存储单元及输入和输出设备i 单地址空间，所以具有易编程性，易达到动态负载平衡，而无需显示数据分配；高速缓存及其一致性，即支持数据局部性，硬件维持一致性；低通信延迟，处理器间的通信靠l o a d s t o r e 来完成等。但是这种并行结构存在着在系统总线b u s 等方面欠可靠、通信延迟( 相对于c p u ) 从而使各处理器之间竞争加剧、慢速增加的带宽、不可扩放性等问题。2 1 2 分布存储多计算机系统大规模并行机m p p “7 1 ( m a s s i v e l yp a r a l l e l河海大学硕士学位论文p r o c e s s o r )大规模并行机是由成百上千个处理器组成的大规模计算机系统，规模可以根据实际需要进行变化。访存模型采用n o r m a ( 非远程存储访问模型) 结构，互连网络采用高带宽低延迟定制，各节点间紧耦合。代表产品有i n t e lo p t i o nr e d ，i b ms p 2 ，d a w n i n g1 0 0 0 等。其结构模型如下：圈2 2 大规模并行机m p i 结构模型m p p 并行系统中每一个节点都拥有自己的处理器、存储器、加设备等，因此具有良好的可扩放性。从系统成本角度，大都采用商用处理器，具有相对稳定的结构。就其通用性和可用性而言：具有交互性强，通信方式可基于p 或m p i 消息传递模式，可以进行批处理，互连对用户透明，单一系统映象等特点。但是由于它是一个异步多指令流多数据流m i m d 机，所以系统必须通过特殊的方法才能使得数据达到同步，而且数据同步会消耗大量的资源，这也正是m p p并行系统目前并没有被广泛应用的原因之一。另外，虽然消息传递系统相对共享存储系统比较容易实现，使它成为实现超大规模并行处理的重要手段，不过由于价格和应用领域的原因，基于消息传递的m p p 系统的研制逐渐成为了政府行为。2 1 3 机群系统邮1 ( c l u s t e rs y s t e m )( 1 ) 机群型大规模并行机s p 2图2 3 机群型大规模并行机s p 2 结构模型6第二章并行计算概述大规模并行机s p 2 采用机群体系结构，拥有标准环境、标准编程模型、系统可用性、精选的单一系统映像等特点。它的系统结构则采用了高性能开关h p s多级q 网络和宽节点、窄节点和窄节点2 等设置。结构模型如上图2 3 。( 2 ) 工作站机群c o w ( c l u s t e ro f w o r l 岱t a t i o n )工作站机群属于分布式存储，简单说来，工作站机群= 工作站+ 商用互连网络。每个节点是一个完整的计算机，有自己的磁盘和操作系统，这里工作站可以是p c 机、s m p 机器甚至是一些小型工作站。商用互连网络常采用如以太网、f d d i 、a t m 等，网络接口与节点的i o 总线松耦合相连。各节点除了可以作为一个单一的计算资源供交互式用户使用外，还可以协同工作并表现为一个单一的、集中的计算资源供并行计算任务使用。典型的工作站机群有：b e o w u l f 、b e r k e l e yn o w 、a l p h af a r m 、f ) 【c o w 。c o w 的一般结构模型如下：图2 4 c o w 结构模型根据节点的拥有情况机群旧可分为专用机群，非专用机群；根据节点的系统配置可分为同构机群、异构机群；根据应用目标可分为高性能机群、高可用性机群等；根据节点的硬件构成可分为p c 机群、工作站机群c o w 和s m p 机群；根据节点的操作系统可分为l i n u x 机群、s o l a r i s 机群、n t 机群等。工作站机群在高性能计算机中所占比例迅速增加，它使得高性能计算机的“平民化”。目前，在国内外的许多大学和研究机构，都构建了工作站机群。工作站机群的迅猛发展是由于它与共享存储多处理机系统的对称多处理机s m p 及分布存储多计算机系统大规模并行机m p p 等并行系统相比而言具有以下优点：( a ) 机群价格便宜并且易于构建；( b ) 作为机群节点的工作站系统的处理性能越来越强大，更快的处理器和更高效的多c p u 机器大量进入市场：( c ) 局域网上新的网络技术和新的通信协议的引入，机群节点间的通信能获7河海大学硕士学位论文得更高的带宽和较小的延迟；( d ) 机群系统比传统的并行计算机更易于融合到已有的网络系统中去；( c ) 机群上的开发工具更成熟，传统并行计算机上缺乏一个统一的标准；( d 机群的可扩放性良好，节点的性能也很容易通过增加内存或改善处理器性能获得提高；( 曲与p v m 、m p i 等支持并行性和交互操作的库函数相结合，易于实现并行编程。本文的并行计算在河海大学校园网格中的联想机群上实现。2 2 并行程序设计模型目前并行程序设计还没有统一的模型能够被广泛接受。比较流行f l t , 1 9 l 的主要有：数据并行模型( d a bp a r t i e r ) 、消息传递模型( m e s s a g ep a s s i n g ) 、共享变量模型( s h a r e dv a f i a b l e ) 。( 1 ) 数据并行模型( d a t ap a r a l l e l )数据模型是s i m d 的自然模型，同时也可运行于s p m d 、m i m d 机器上。它采用局部计算和数据选路操作，适合于使用规则网络、模板和多维信号及图像数据集来求解细粒度的应用问题。数据并行操作的同步是在编译时而不是在运行时完成的。该模型的主要特点有：支持单线程、并行操作于聚合数据结构( 数组) 、松散同步、全局命名空间、隐式相互作用、隐式半隐式数据分布。数据并行编程模型的编程级别比较高，编程相对简单，但它仅适用于数据并行问题。( 2 ) 消息传递模型( m e s s a g ep a s s i n g )消息传递即各个并行执行的部分之间通过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内存的，因此消息传递模型是大规模并行处理机m p p 和工作站机群c o w 的自然编程模型，但是也可应用于共享变量多机系统，适合开发大粒度的并行性。消息传递模型比其它模型更为灵活，广泛使用的标准消息传递库m p i 和p v m 又使得基于消息传递的并行程序更具有可移植性。它的主要特点有：支持多线程、异步并行性、分开的地址空间、显式相互作用、显式数据映射和负载分配、常采用s p m d 形式编码等。消息传递编程模型的编程级别相对较低，但消息传递编程模型可以有更广泛的应用范围。本文的并行计算以工作站机群为作业平台，故选择采用消息传递模型。下文中将会对标准消息传递库m p i 作具体介绍。( 3 ) 共享变量模型( s h a r e dv a r i a b , e )共享变量模型是较高层次上的模型，是p v p 、s m p 、d s m 的自然模型。该模型的主要特点有：支持多线程、异步并行、单一共享地址空间、显式相互作用、8第二章并行计算概述隐式隐式数据分布、隐式通信( 共享变量的读写) 。2 3 程序并行化方法并行程序的开发主要有以下三种方法【1 7 l ：( 8 ) 自动并行化( b ) 并行库( c ) 重新编写并行代码图2 5 三种程序并行化方法对于这三种方法，目前最常用的就是提供并行库这种方法。仅仅提供并行库是一种对原来的串行程序设计改动最小的并行化方法。这样，原来的串行编译器也能够使用而不需要任何修改，编程者只需要在原来的串行程序中加入对并行库的调用就可以实现并行程序设计。现在已经开发并比较流行的函数库m p i 就是属于这样一种并行库。2 4 并行编程模式并行编程模式1 2 0 2 0 捌主要有：对等模式( p e e r - t o p e e r ) 、主一从模式( m a s t e r - s l a v e ) 、数据流水线( d a t ap i p e l i n i n g ) 、分治策略( d i v i d ea n dc o n q u e r ) 。一般机群系统下，常用的并行编程模式是主一从模式和对等模式，其中实现对等模式，是比较容易理解和接受的，因为各个部分地位相同，功能和代码基本一致，只不过是处理的数据或对象不同。( 1 ) 对等模式( p e e r - t o - p e e r )它也被称为单控制流多数据流模式( s i n g l ep r o g r a mm u l t i p l ed a t a ) ，其基本思想是并行运行的进程均执行相同的代码段，但却操作在各自不同的数据上。这种编程模式首先需要将应用程序的数据预先分配给各个计算进程( 处理器) ；然后诸计算进程并行的完成各自的计算任务，包括计算过程中各进程问的数据交换( 施9河海大学硕士学位论文行通信同步) ；最后才将各计算结果汇集起来，一般指定某一个进程将结果输出。其结构模型如图所示：图2 6 对等编程模式( 2 ) 主一从模式( m a s t e r - s l a v e )其基本思想是将一个待求解的任务分成一个主任务( 主进程) 和一些从任务( 子进程) 。主进程负责任务的分解、派发和收集诸子任务的求解结果并最后汇总得到问题的最终解。而诸子进程则负责接收主进程发来的消息，并行进行各自计算，并最终向主进程发回各自的计算结果。如下图所示( 设采用p 个子进程) ：图2 7 主一从式编程模式( 3 ) 数据流水线( d a t ap i p e l i n e )其基本思想是将各计算进程组织成一条流水线，每个进程执行一个特定的计算任务，相当于流水线的一个阶段。一个计算任务在功能上划分成一些子任务( 进程) ，这些子任务完成某种特定功能的计算工作，而且一旦前面一个子任务完成，后继的予任务就可立即开始。在整个计算过程中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，且通信可以完全异步地进行。其执行过程如下图所示( 设启动p 个进程) ：1 0第二章并行计算概述输入，由简出一p 阶段l 输出图2 s 数据流水线编程模式( 4 ) 分治策略( d i ，i d ea n dc o n q u e r )分治策略的基本思想是将一个大而复杂的问题分解成若干个特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，则可反复使用分治策略，直至很容易求解诸予问题为止。问题求解可分为三步：将输入分解成若干个规模近于相等的子问题；同时递归地求解诸子问题：归并各子问题的解成为原问题的解。2 5 一般并行程序设计过程一般并行程序设计可分为以下几个步骤1 1 7 1 ：划分( p a r t i t i o n i n g ) 、通信( c o m m u n i c a t i o n ) 、组合( a g g l o m e r a t i o n ) 、映射( m a p p i n g ) ，这个过程也被简称为p c a m 设计过程。( 1 ) 划分( p a r t i t i o n i n g )划分是指将原任务分解成若干小的任务，充分开拓算法的并发性和可扩放性。具体做法是首先进行数据分解( 称域分解) ，再进行计算功能的分解( 称功能分解) ，同时要注意使数据集和计算集互不相交。在划分阶段可以不考虑计算所采用的处理器数目和目标机器体系结构的情况。( 2 ) 通信( c o m m u n i c a t i o n )通信分析是p c a m 设计过程的重要阶段。在任务划分结束之后，任务之间一般不能完全独立执行，一个任务中的计算可能要用到另一个任务中的数据，也就产生了相应的通信要求。所谓通信，就是为了完成整个并行计算，在各个任务之间需要进行数据传输( 或数据交流) 。诸任务是并发执行的，但通信恰恰限制了这种并发性，所以通信常会成为并行计算的瓶颈问题。通信通常有以下几种模式：局部全局通信、结构化非结构化通信、静态动态通信、同步异步通信。( 3 ) 组合( a g g l o m 啪t i o n )任务组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行的过程。在任务划分和通信分析阶段，实际都没有具体考虑到并行的执行效率，任务组合就是以有效的并行执行为目的。通信量与任务子集的表面成正比，计算量与任务子集的体积成正比，所以需要合理的合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了理想组合过程，但是一般情况下，子河海大学硕士学位论文任务数都要大于处理器数。组合的主要目的是提高效率和减少通信成本，同时又保持映射和扩展的灵活性，降低软件工程成本。( 4 ) 映射( m a p p i n g )任务映射是指经组合后得到的每一个任务都要对应到具体的处理器，定位到运行机器上，其目的是为了减少算法的总执行时间，这也是进行并行计算的根本目的所在。它有以下两个策略：把那些可并行执行的任务放在不同的处理器上，以增加并行度；把那些需频繁通信的任务置于同一个处理器上，以减少局部通信时间。很多情况下，任务数要大于处理器数，此时，就会存在负载平衡和任务分配问题。负载平衡不是任务简单的平均划分，更重要的是所有处理器应该在大致相等的时间内完成所分配到的任务，因此必须减少同步等待时间，这包括等待其他进程结束运行的时间和串行执行的代码部分。基于区域分解技术的算法有很多专用和通用的负载平衡技术，它们试图将划分阶段产生的细粒度任务组合成每一个处理器对应一个粗粒度的任务。其方法有递归对剖、局部算法、概率方法、循环映射等。任务分配通常有静态的和动态的两种方法。静态分配一般是任务到进程的算术映射。静态分配的优点是没有运行时任务管理的开销，但为了实现负载平衡，要求不同任务的工作量和处理器的性能是可以预测的并且拥有足够的可供分配的任务。动态分配相对灵活，可以运行时在不同处理器间动态地进行负载的调整。2 6 并行计算的性能评价。瑚1并行加速比和并行效率是评价并行计算的主要性能指标。( 1 ) 并行加速l 七( p a r a l l e ls p e e d u p ) ：相对最优的串行程序在单个c p u 上执行的墙上时间与模拟同一问题的并行程序在多个c p u 上执行的墙上时问之比。即：假设串行执行时间为瓦，p 个处理机并行执行的时间为l ，则加速比为：卟( 2 ) 并行效率( p a r a l l e l e f f i c i e n c y ) ；加速比与并行计算所用c p u 数之比。假设p个处理机的加速比为s 。，则并行效率为：2第二章并行计算概述e ，= 等2 7 本章小结本章主要对并行计算相关知识进行介绍说明。对当代比较流行的主要代表并行机机型及其结构模型进行了介绍，重点介绍了工作站机群这类并行机，工作站机群使得高性能计算“平民化”，促进了科学研究的发展。并行程序设计没有统一的模型，本文只是给出了应用比较广泛的几种模型。并行化方法一般有三种，其中提供并行库这种方法是比较简单且对原串行程序改动较小的一种，本文的并行程序设计就是采用这种方法。并行编程模式决定着通信方式，直接影响了并行程序的正确性和效率，从而影响整个系统的性能，所以在文中也给予了一定的介绍。最后简单介绍了一般并行程序的设计过程，以及并行计算性能评价的两个主要指标并行加速比和并行效率。河海大学硕士学位论文第三章机群系统与m p i 并行库本文对浅水流动的并行研究采用了河海大学网格中已有的联想机群作为计算平台。河海大学校园网格系统是一个拥有多种接入方式的高速网络传输平台，系统核心采用了千兆以太网技术，通过千兆交换机连接了信息中心的高性能计算设备和各学院计算机群，包括土木学院的惠普机群、水电学院的曙光机群、计算机及信息工程学院的m m 刀片服务器机群等等。同时，采用了干兆防火墙等设备对超级计算机进行安全保护，整个校园网络和网格平台都具有很高的可用性、可靠性及安全性，可以为用户提供更高效、更可靠、更安全的服务。下面将对联想机群的硬件配置和软件配置作详细介绍。3 1 机群硬件配置计算节点由1 6 台联想服务器构成，分别命名为c o l o l 、c 0 1 0 2 c 0 1 1 6 ，管理节点为1 片联想服务器。c p u 型号为i n t e l x e o n 2 8 g 2 ，系统的内存总容量为3 2 g b ，磁盘总容量l ，2 8 t b ，系统峰值可达1 7 9 2g f l o p s 。机群系统采用局域网连接，网络拓扑结构采用适合局域网的星型拓扑结构，该结构是指各工作节点以星型方式连接成网。3 2 机群软件配置3 2 1 操作系统该机群所有节点上的操作系统均采用r e d h a tl i n u x9 0 t 川。l i n u x 系统是真正的多用户、多任务操作系统，多个任务或应用可同时运行，并且是由操作系统而不是由应用来进行任务的控制和时钟周期的分配。它的许多组成部分的源代码是开放的，任何人都可以通过i n t e m e t 或其它一些媒体免费得到它，并且可以自由修改和重新发布它。l i n u x 最受人关注的特点是在同样的硬件条件下，它要比现有其它的操作系统如：u n 权环境和w i n d o n w s n r 环境，能提供更快的执行速度和更出色的健壮性。3 2 2 并行环境机群的并行环境采f f j m p i ( m p i c h - 1 ) 并彳亍库。m 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 是一个库而不是- - f 语言，但是它提供的接口可以方便c ，c + + 语言和f o r t r a n7 7 f o r t r a n 9 0 的调用。可以把它看作是一种在原来1 4第三章机群系统与m p i 并行库串行语言基础之上扩展后得到的并行语言。m p i 提供t - - 种与语言和平台无关，却可以被广泛使用的编写消息传递程序的标准。用它来编写消息传递程序，不仅实用、可移植、高效和灵活，而且和当前已有的串行实现没有太大变化。3 3m p i 并行库3 3 1 一般i v i p i 并行程序的设计过程一个i v i p i 程序的设计过程可以用以下框图来表示：图3 1m 魄序的框架结构m p i 相对于f o r t r a n 实现的头文件是m p 试h ，用f o r 删语言编写的m p i并行程序必须有m p i 的f o r t r a n 头文件m p i h 。如果是f o r t r a i l 7 7 程序需m i n c l u d em p i h 调用，如果f 硼眦9 0 程序则需要将i n c l l 】d em p 正hl 玫为u s em p i ，则此时m p i就被定义成为一个f o r t r a n 调用的模块。3 3 2m p i 中的常用接口“19 2 卵在m p i 1 中共有1 2 8 个调用接口，在m p i 2 中有2 8 7 个，应该说m p i 是比较庞大的。但是一般来说，只要掌握以下常用的几个函数接口就可以进行m p i 并行程序设计了。首先介绍用来m p i