（流体力学专业论文）模拟非线性浅水波的Boussinesq方程并行算法研究.pdf

中文摘要 b o u s s i n e s q 方程是用于描述非线性色散波在浅水中传播的方程，以 b o u s s i n e s q 方程为基础的数学模型可以用来模拟复杂地形上波浪的传播情况以 及波浪与结构物之间的相互作用，它可以模拟波浪的折射、绕射、反射及浅化等 现象，因此在工程中具有广泛的应用。随着b o u s s i n e s q 方程的不断改进， b o u s s i n e s q 方程已经能进行深水区和大面积场的计算，但是受到计算机存储空间 及c p u 的限制，使用单个处理器计算已经不能满足工程实际的需要，本文从这 一实际情况出发，进行b o u s s i n e s q 方程的并行程序设计，结合高性能并行计算机 集群系统来进行b o u s s i n e s q 方程水波数值模拟计算。 本文首先综述了b o u s s i n e s q 方程在色散性、非线性等方面的改进，回顾了并 行算法在b o u s s i n e s q 方程中的应用，介绍了并行计算的分类和性能分析的方法。 本文采用的方程是m a d s e n 和s e h t f f e r ( 19 9 5 ) 推导所得的方程，该方程具有很好的 色散性，能适用于变水深、斜坡等复杂地形。对该方程在空间上采用了中心紧致 差分格式，时间上采用中心差分格式，使得在差分点个数不变的情况下取得了更 高的精度。方程的求解采用a d i 方法，使得方程的求解具有很好的稳定性。 本文采用了m p i + f o r t r a n 的并行程序语言编写程序，程序具有很好的可移植 性。对该方程采用了区域分解的并行算法进行并行程序设计，在不同方向计算时 进行不同的区域划分，在进行模型并行化的过程中考虑了进程的负载平衡、死锁 的避免、虚拟进程的设置等问题，进程间的数据交换通过消息的发送和接收来进 行，经模型验证并行程序计算结果和串行程序的计算结果是完全吻合的，并在一 定程度上缩短了计算时间。 关键词： b o u s s i n e s q 方程，m p i ，a d i 方法，区域分解 a b s t r a c t b o u s s i n e s qe q u a t i o ni san o n l i n e a rd i s p e r s i o nw a v ee q u a t i o ni ns h a l l o ww a t e r t h en u m e r i c a lm o d e l sb a s e do nb o u s s i n e s qe q u a t i o n sc o u l ds i m u l a t et h es i t u t i o no f w a v e sp r o p a g a t eo nu n e v e nb o u o ma n dt h ei n f l u e n c eb e t w e e nw a v e sa n ds t r u c t u r e i t c o u l ds i m u l a t er e f r a c t i o n ，d i f f r a c t i o n ，r e f l e c t i o n ，s h o a l i n ge t c t h e r e f o r e ，b o u s s i n e s q e q u a t i o nm o d e l sh a v eb e e nu s e dw i d e l y a l o n gw i t hc o n t i n u o u si m p r o v e m e n to f b o u s s i n e s qe q u a t i o n ，i tc o u l ds i m u l a t ed e e pw a t e rr e g i o na n dg r e a ta r e af i e l d ， h o w e v e r , c o m p u t i n go n l yb yo n ep r o c e s s o rc o u l dn o ts t a t i s f yt h ep r o j e c t s a c t u a ln e e d b e c a u s eo ft h el i m i t a t i o no ft h em e m o r y ss i z ea n dc p u ss p e e do fc o m p u t e r i nt h i s t h e s i s ，i td e s i g n sp a r a l l e lp r o g r a mo fb o u s s i n e s qe q u a t i o ni no r d e rt os o l v et h i s p r o b l e m ，a n du t i l i z e sh i g hp e r f o r m a n c ep a r a l l e lm a c h i n ec l u s t e rs y s t e mt ob o u s s i n e s q e q u a t i o n sw a v es i m u l a t i o n i nt h i st h e s i s ，t h ei m p r o v e m e n t so fd i s p e r s i v ep r o p e r t y , s h o a l i n g ，t h ea p p l i c a t i o n o fp a r a l l e lm e t o d so fb o u s s i n e s qe q u a t i o n sa r er e v i e w e d t h e np a r a l l e lm a c h i n e c l a s s i f i c a t i o na n dp e r f o r m a n c ea n a l y s i sm e t h o da r ei n t r o d u c e d i ta d o p t st h e b o u s s i n e s qe q u a t i o ns e tu pb ym a d s e na n ds c h i i f f e r ( 1 9 9 5 ) t h i se q u a t i o nh a sb e t t e r d i s p e r s i v ep r o p e r t yt h a ne v e r ；i tc a nb eu s e do nt e r r a i no fc h a n g e dd e p t ho fw a t e ra n d s l o p e t h ec e n t e rc o m p a c td i f f e r e n c ei ns p a c ea n dc e n t e rd i f f e r e n c ei nt i m ea r e a p p l i e di nb o u s s i n e s qe q u a t i o n a sar e s u l t ，i tc a no b t a i nh i g h e rp r e c i s i o nt h a nt h e c e n t e rd i f f e r e n c ei ns p a c ew h i l et h en u m b e ro fd i f f e r e n c ep o i n t si sn o tc h a n g e d a d i m e t h o di sa p p l i e dw h i l es o l v i n gt h i sd i f f e r e n c ee q u a t i o n i te n s u r e st h a tt h e 。s o l u t i o n p r o c e s si ss t a b l e m p i + f o r t r a np a r a l l e lp r o g r a ml a n g u a g ei su s e di nt h i sp a p e r t h ep r o g r a mh a s g o o dp o r t a b i l i t y a d o p t i n gr e g i o nd e c o m p o s i t i o nm e t h o dt od e s i g np a r a l l e lp r o g r a m ， t h et h e s i su s e sd i f f e r e n td e c o m p o s i t i o nr e g i o na tt h ed i f f e r e n tc o m p u t a t i o nd i r e c t i o n i tc o n s i d e r st h el o a db a l a n c e ，a v o i d i n gd e a dl o c k ，s e t t i n gd u m m y p r o c e s s o ra n ds oo n t h ed a t a se x c h a n g ea m o n gp r o c e s s o r su s e s “s e n da n dr e c e i v e ”m e t h o d a tl a s t ，t h i s p a r a l l e lp r o g r a mi sc o n f i r m e db ym o d e l s ，t h er e s u l to fc a l c u l a t i o nt a l l i e sw i t ht h e s e r i a lr e s u l t p a r a l l ep r o g r a mr e d u c e st h ec o m p u t i n gt i m ei nac e r t a i nd e g r e e k e y w o r d s ：b o u s s i n e s qe q u a t i o n ，m p i ，a d im e t h o d ，r e g i o nd e c o m p o s i t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤注盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：彳钮赦韵 签字日期： 呻年z 月，多曰 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞叁茔有关保留、使用学位论文的规定。 特授权墨壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 够缸钧 导师签名： 签字日期：j 唧年占月，才日签字日期：6 月f 扩日 0 7 丁 如矿 天津大学硕十学何沦文第一章绪论 1 1 研究背景及意义 第一章绪论 波浪是海岸工程设计中必须考虑的最重要因素之一。然而，近岸地区海底地 形通常比较浅，而且海脊、海沟、岛屿、暗礁等纵横交错，使得地形复杂多变。 复杂的地形使波浪在传播到该地区时发生折射、绕射、浅化和爬高等较大的变形。 尽管n s 方程建立的数学模型可以描述这些，但是在大面积波浪场中完全求解 n s 方程又是不现实的，于是科学工作者们研究各种物理问题的本质，提出了各 种波浪理论，建立相应的模型模拟对应的物理问题。由于近海水浅，波高变大， 非线性因素的作用比远海深水区要显著得多，从而近岸波浪场、流场无法用简单 的线性方程述。复杂的边界条件和非线性的影响成为现代科技人员必须面对和解 决的问题。 纵观表面波理论的发展，1 8 0 2 年f g e r s t n e r 发表深水波理论，后来1 8 4 5 年 g b a i r y 提出从深水到浅水的统一理论( 微幅波理论) ，到1 8 4 7 年g g s t o k e s 发 表有限振幅波理论，这样波浪的基础理论于1 9 世纪已建立起来。不过工程技术 人员对波浪理论的自由运用为人类征服大自然而服务却是近四十年来特别是电 子计算机问世以来才取得了长足的发展。 对于波浪在近海工程区域的变形的数值模拟方法主要有：( 1 ) 考虑地形折射 的射线法；( 2 ) 考虑单纯绕射的单点源法；( 3 ) 折射绕射综合模型。射线法是类比 光学上的折射，由线化波动方程的色散关系导出波浪传播方向与地形梯度的关 系，由波能守衡导出射线上波高与水深的近似关系。这种方法适用于地形很缓， 水面开阔的区域，无复杂的建筑物存在。单纯绕射理论是对线性化的e u l e r 方程 在等水深情况下简化为h e l m h o l t z 方程，通过求解h e l m h o l t z 方程的边值问题得 到波浪运动的散射势。这两种方法将折射和绕射分开考虑，对地形梯度也有一定 的限制，因而不适用与求解近海复杂水下地形和工程建筑物附近的波浪场。为了 综合考虑波浪的折射、绕射、浅化等变形，b e r k h o f f ( 1 9 7 2 ) 用小参数展开法和沿 水深方向积分的方法首次导出了短波折射绕射综合问题的缓坡方程( m i l ds l o p e e q u a t i o n ) ，此后，其他学者用变分原理( a o o j ，1 9 8 1 ，k i r b y ，1 9 8 3 ，d i n g e m a n s ， 1 9 8 5 ) 和摄动法( l o z a n o & m e y e r ，1 9 7 6 ，l o z a n o & l i u ，1 9 8 0 ) 得到了考虑流影响、摩 擦效应和波浪破碎条件的缓坡方程。围绕缓坡方程的计算方法有三类：有限元法、 天津大学硕十学位论文筇一章绪论 有限差分法、抛物化方法。其中抛物化方法由于其计算量小，适合于人面积波浪 场的推算，发展较快。抛物化缓坡方程首先由r a d d e r ( 1 9 7 9 ) 提出，后来t s a y & l i u ( 1 9 8 2 ) 、k i r b y ( 1 9 8 6 、1 9 8 8 ) 、i s o b e ( 1 9 8 6 ) 作了进一步研究，发展到能考虑大波 向角，不规则波的抛物化缓坡方程模拟。不过抛物化缓坡方程也有较大缺点，一 是波浪下游的反射小到可以忽略，二是不能用于有建筑物存在的区域。另一方面， 基于e u l e r 方程水深积分的b o u s s i n e s q 方程。以b o u s s i n e s q 方程为基础建立的数 学模型能够描述波浪在缓变地形和定常水深的流中的很多变形情况，如非线性、 频散、幅散、线性和非线性浅化、多向传播、绕射、地形引起的折射、流影响下 的折射、谐波等等，而且它不将入射波和反射波截然分开，可以考虑地形、建筑 物和非线性的综合作用，这正是抛物缓坡方程所不能实现的，因此，该数学模型 被广泛应用于求解近岸复杂工程区域波浪场。尽管这种方程的数学形式是浅水波 方程，但经过改进，该方程的适用范围已经扩展到深水。随着方程性能的改进和 求解方法的不断完善，该模型对上述各种物理现象的模拟效果也得到了很大的改 进。 不断完善和发展以b o u s s i n e s q 方程为基础的数学模型，使其能更准确、有效 地模拟近岸海域波浪场的各种自然现象，得到合理的波浪场运动规律，才能为近 海工程的实施提供可靠的依据。 虽然b o u s s i n e s q 方程对于模拟实际的物理问题取得了很大的进展，但是对于 大面积场波浪场的计算很耗时，对c p u 的占用率和内存的使用都较高，在单个 处理器上进行大尺度问题的计算是很不合适的，所以如何利用已有的串行程序算 法，设计并行计算的方法，缩短模型的计算时间提高计算效率将是我们需要考虑 的一个重要问题，本文从这个角度出发，提出了将b o u s s i n e s q 方程进行并行化设 计，缩短计算时间，提高计算效率，从而大大提高工程应用中的实际的需要，详 细的方法本文将会在以下章节中叙述。 1 2b o u s s i n e s q 方程的研究进展 1 8 7 2 年b o u s s i n e s q ( 1 8 7 2 ) 考虑波浪在平底传播时的非线性浅水方程的色散效 应而推导得到b o u s s i n e s q 方程。之后，p e r e g r i n e ( 1 9 6 7 ) 假定表征色散性的参数和 表征非线性的参数占， 1 ，且占2 = d ( 1 ) ，o ( v h ) = d ( 1 ) ，采用摄动法推导出 水深可变化的二维形式方程，其中占= a h 表征波浪的非线性特性，= a l 表 征色散性的参数。推导中忽略o ( u 4 ，掣2 占2 ) 项。方程中的变量为瞬时水位和水 深积分平均水平流速。该方程形式为： 2 天津大学硕十学位论文第一章绪论 署m 肌玎小。 詈+ o v - + 妒刁= j i 矗昙v o “) 】一言1 办2 昙v ( v 圳 ( 1 2 - l a ) ( 1 - 2 l b ) 此方程常被称为经典形式的b o u s s i n e s q 方程，或b o u s s i n e s q 方程的标准形式。 经典的b o u s s i n e s q 方程由质量守恒的连续方程和不可压无粘流体的动量方程构 成，动量方程中的三阶混合时间空间导数项称为b o u s s i n e s q 项，即色散项。 b o u s s i n e s q 方程将三维的波动问题简化为二维，使波浪数值模拟成为可能，它能 够反映波浪运动的各种变形，如折射、绕射、反射及波浪之间的相互作用。经典 的b o u s s i n e s q 方程假定垂向速度沿水深为线性分布，由此得出水平速度和压力水 深为二次分布。由于方程精确到o ( e ，2 ) ，方程中包含了弱非线性和弱色散性， 受色散精度的要求，经典的b o u s s i n e s q 方程仅适用于较浅的水域，一般 办厶o 1 2 。 1 2 1b o u s s i n e s q 方程色散性的改进 w i t t i n g ( 1 9 8 4 ) n 1 建立一组方程，用自由参数代替t a y l o r 展开速度的系数，然 后用匹配方程的频散和s t o k e s 一阶频散的p a d 6 展开确定自由参数。w i t t i n g 对线 性色散性的改进作了重大贡献，开拓了各种形式的b o u s s i n e s q 方程的发展前景。 他首次在b o u s s i n e s q 理论中引入了p a d 6 近似概念。p a d 6 近似通常优于t a y l o r 近 似，p a d 6 2 n , 2 n 近似的s t o k e s 线性相速平方的有效精度为0 ( r 4 l ，r = 脚。 n = l 和n = 2 分别可得： s t o k e s 一阶色散关系为： 圹一t a n h ( r ) 一= - - 盘2 dk ( 1 2 - 2 a ) ( 1 2 2 b ) ( 1 - 2 - 3 ) 天津大学颁十学位沦文第一章绪论 图l 一2 一l 所示为p a d d 2 ，2 季1 1 1 4 ，4 】近似的相速与s t o k e s 色散关系的比值，可见 p a d d 4 ，4 】近似展开保证r = 6 时，相速有很高的精度。 m a d s e n 等( 1 9 9 1 ) | 2 在动量方程中引入含有待定常数的三次偏微分项，使方程 的色散精度提高，方程隐含的色散关系为： c 21 士b k2 h 砂1 + ( 占+ ) 七2 厅 ( 1 2 4 ) 其中，c 为波速，k 波数。该方程的色散精度与b 值有关，当召取1 2 1 时， 色散误差最小。m a d s e n ( 1 9 9 1 ) 还给出了方程的波群速度关系式： 斗等一将 ( 1 - 2 5 ) 。 当b = 1 1 5 时，m a d s e n 改进方程的线性色散性能达到a i r y 波精确解的 p a d d 2 , 2 阶近似解。 1 , 3 工 。 苗1 2 5 u o 1 2 1 1 5 1 1 1 0 5 1 l 一 图1 2 一l 式( 1 2 2 a ) 和( 1 2 2 b ) - 与( 1 2 3 ) 确定的相速度比c 2 产蛔 1 ：式( 1 2 2 a ) ，即p a d d 2 , 2 ；2 ：式( 1 - 2 - 2 b ) ，即p a d 正 4 ，4 】 n w o g u ( 1 9 9 3 ) 协1 采用摄动法用某一水层的速度来改进b o u s s i n e s q 方程，通过 选择不同水深层的速度来提高方程的色散精度，优化方程色散性。该方程的线性 色散关系与式( 1 2 4 ) 一致，。只是用b = 一口一l 3 替换式中的b 。当口= 一1 3 时， 4 天津大学硕十学位论文笫一章绪沦 方程转化为标准形式的b o u s s i n e s q 方程，此时方程的色散精度达到o ( u 2 ) ；当 口= 一2 5 时，此时方程的色散精度达到o ( u 4 ) ；当口= 一0 3 9 0 ，即用z 。= - - 0 5 3 h 处流速时，方程的色散精度最高，达到p a d d 2 ，2 】阶近似。 s c h a f f e r 和m a d s e n ( 1 9 9 5 ) h 1 将上述两种色散改进方法结合起来，对n w o g u 方 程的连续方程和动量方程分别施以散度和梯度两重算子，得到一个含有五个待定 常数的改进型b o u s s i n e s q 方程。通过对待定常数的调整，方程的线性色散性达到 a i r y 波精确解的p a d d 4 ，4 阶精度。 通过科学工作者以前的一系列研究，b o u s s i n e s q 方程的色散性得到了很好的 改进。 1 2 2b o u s s i n e s q 方程非线性的改进 衡量非线性的一个简单方法是用s t o k e s 展开法分析b o u s s i n e s q 方程。选定 一个参考值，如规则波时用s t o k e s 三阶理论，双色波( 包括次谐波和超谐波的传 递函数) 用二阶理论。在浅水中，s t o k e s 展开和b o u s s i n e s q 方程有同样的解，但 随着的增大，各种形式的b o u s s i n e s q 方程都会偏离s t o k e s 解。非线性的改进 需要包含非线性和色散影响的附加项( 如掣2 ，占2 2 ，掣4 项) 。在改进b o u s s i n e s q 方程色散性的同时，为了模拟浅水中波浪变形和波浪的相互作用，许多学者对 b o u s s i n e s q 方程进行了非线性的改进。 w e ie ta 1 ( 1 9 9 5 ) 璐1 最早对b o u s s i n e s q 方程的非线性进行了改进。他在方程的 推导申，未作弱非线性的假设，保留了d ( 2 ) 和所有阶的占，导出完全非线性 b o u s s i n e s q 方程。该方程既适用于中等水深，又适用于波浪的强非线性相互作用， 但线性色散性只能达到p a d d 2 ，2 】阶精度。 g o b b i 和k i r b y ( 1 9 9 6 ) 阳1 提出一个完全非线性b o u s s i n e s q 类模型，色散精度为 d ( 枷4 ，在0 k d 1 5 时， 低阶谐波迅速偏离精确解，当k d = 2 5 时，误差达到1 0 0 。 m a d s e ne t a l ( 1 9 9 6 ) h 1 发展了两组高阶b o u s s i n e s q 方程。第一组方程由水深平 均速度表示，色散精度为p a d d 4 ，4 】展开，非线性精度为o ( c 5 t 4 ) 。当k d = 3 0 时， 二阶谐波传递函数误差为3 0 。第二组方程由特定水深层z 的速度表示，色散精 度为p a d d 4 ，4 】展开，非线性精度为o ( e 3 2 ) 。当k d = 3 0 时，二阶谐波传递函数 误差达3 5 。 。 m a d s e n ( 2 0 0 2 ) 1 提出了更高精度的方程，方程的非线性精度可达到和线性色 散性相同的精度，显著地改进了速度的垂向分布、线性色散关系、幅散、次谐波 和超谐波的非线性转换函数。该方程的适用范围可达到k h = 4 0 ，优于以前所有 的b o u s s i n e s q 方程。 天津大学硕十学位论文第一章绪论 1 3 并行算法在b o u s s i n e s q 方程模型中的应用回顾 随着并行概念的提出，各种并行标准的定制和并行编程语言的发展，并行算 法在b o u s s i n e s q 方程模型中也得到了一定的应用。比较有代表性的是x c a i ，q k p e d e r s e n ，h pl a n g t a n g e n ( 2 0 0 5 ) ：k h a i r i ll r f a n s i t a n g g a n g ，p a t r i c k l y n e t t ( 2 0 0 5 ) 嘲，在这两篇论文中，作者都采用了区域分解作为所采用的并行算 法。 k h a i r i ll r f a ns i t a n g g a n ge ta 1 采用pl y n e t te ta 1 n 铂推导的b o u s s i n e s q 方程，具 体的控制方程形式如下： 二维水深积分连续性方程： 百o h + v ( 矾) 二2 v 饵 ( 吉( 印2 一咖埘) 一i 1 2 ) v s + 哇仞叫训v 珊 ( 1 4 i ) 动量方程： 鲁+ 三v ( 呒死) + g v j 7 + 瓦0t - 1 2 v s + 乙v r - v ( 三矿s + 忉 + v 鲁仃+ 移) + 阮一，7 ) 纸v 沙+ j i ( z 口2 一，7 2 ) 帆v 冷+ 三仃+ 秘) 2 ) = 。 。( 1 - 4 - 2 ) 在方程( 1 4 1 ) 及( 1 - 4 - 2 ) 0 0 ，s = v u a ，t = v ( 以) + o h o r ，h 为静水深，r 为自由表面位移。 l y n e t tp ( 1 9 9 9 ) n 町给出了该控制方程的有限差分方法，在时间上采用了三阶显 式a d a m s b a s h f o r d 预测步和四阶隐式a d a m s b a s h f o r d 校正步相结合。在空间上 采用了四阶精度，对应的差分格式如下所列。 显式的预测方程： 彬1 = 略+ 击址( 2 3 一1 6 e i , 孑 + 5 2 、 ( 1 - 4 - 3 a ) 叼1 = + 西i f ( 2 3 f ， j 一1 6 f ；a l + 5 f 5 2 ) + 2 ( 砒一仉n - - ，l + ( 互) 荔2 ( 1 - 4 - 3 b ) 曙1 = + 西1 ，( 2 3 一1 6 g 7 岁- ”n - 2 ) + 2 ( q ) ：厂3 ，g w w l + ( 刚p i - ，2 ( 1 4 - 3 c ) 天津大学硕+ 学位论文第一章绪论 隐式校正方程为： 彬= 确+ i a t ( 9 c ；1 + 1 9 e ? j 一5 巧1 + 2 ) ( 1 - 4 - 4 a ) u w n + l = + 瓦1 f ( 9 + 1 9 砖一5 c 了1 + 2 ) + 2 ( 互) ：，+ ( e ) 易1 一( 巧) ： ( 1 4 - 4 b ) i , ji = y i , ”j + 去f ( 9 嘭1 + 1 9 吒一5 1 + 吒2 ) + 2 ( g 1 ) ：j + ( g 1 ) 才_ ( g 1 ) ： ( 1 - 4 - 4 c ) 中间变量u ，y 的表达式如下： u = “+ 三( 乞2 彳比+ ( z 。刊( m 。一仉眺m 吐】 y = y + 三( z 口2 - 矿h + ( z 。一r ) ( h - ) 一巩吨】 ( 1 _ 4 5 ) ( 1 4 6 ) 该方程的求解过程如下：( 1 ) 通过方程( 1 4 3 a ) ( 1 4 3 c ) 预测矿，甜州，1 ，5 ( 2 ) 将所求的矿，j g n 4 - 1 ，州代入到差分方程( 1 4 5 ) 和( 1 - 4 - 6 ) q b 得到新的材槲，v 胂1 值，在此处需要求解线性三对角方程组：( 3 ) 将第2 步中求得的“槲，1 ，肿1 预测值 代入到( 1 4 4 a ) ( 1 4 4 c ) 中，同时结合方程( 1 4 5 ) 和( 1 4 6 ) 进行迭代计算，待达到 指定精度的时候停止本时间层内的迭代进入到下一时间层的计算。 针对这样的方程求解过程，k h a i r i ll r f a ns i t a n g g a n ge ta 1 d 给出了对应得并行 算法，k h a i r i li r f a ns i t a n g g a n ge ta 1 采用区域分解的方法进行并行算法设计，同时 结合三对角方程的并行化设计进行问题的求解，。在此差分方法中，预测步和校 正步都有很好的并行性，划分成小区域上的边界数据可以通过在边晃处增加虚拟 数组，进程间数据传递来实现区域分解的并行。k h a i r i li r f a ns i t a n g g a n ge ta 1 通过 这种方法的并行程序设计取得了很好的效果。 x c a ie ta 1 t i 也对b o u s s i n e s q 方程的并行化方法进行了研究。该文中采用的 b o u s s i n e s q 方程模型来源于w ud m e ta 1 ( 1 9 8 2 ) n 钔采用的数学模型，在此论文中作 者也是采用了区域分解的方法，在每一区域中同时进行差分方程的求解。值得注 意的是在每一时间层中作者采用了s c h w a r z 迭代，当迭代所得的值达到控制的精 度时将所得的值作为新值来使用，分解所得的每一区域都会存在着一个最大误 差，在各区域每迭代完一次进行各区域间最大误差的比较，求得各进程上误差的 最大值，如果此误差值达到给定的精度，则退出此迭代计算，进入到下一步骤的 7 天津大学硕十学位论文第一章绪论 计算。 从已有的文献中可以发现区域分解法在b o u s s i n e s q 方程模型中具有很好的前 景，本文采用的b o u s s m e s q 方程模型和差分方法都有别于上述论文，但是其他工 作者在b o u s s i n e s q 方程模型并行化上所做的工作仍给了我很多启迪。在本文的第 三章中将论述本文所采用的b o s s i n e s q 方程模型及相应得差分方法，第四章中进 行了并行化方法的研究。 1 4 并行计算概论 所谓的并行计算是指同时对多个任务或多条指令、多个数据项进行处理，实 现这种任务的计算平台即并行计算机，可以是专门设计的含有多个处理器的计算 机或是以某种方式互连起来的若干独立的计算机。并行计算的基本思想是，n 台 计算机能提供n 倍的单机速度，但实际情况并不能达到如此好的效果，由于各 进程间的相互联系，进程间的数据传递、信息通讯等都要占用一定的时间，所以 并行计算时间并不能单纯的认为是串行计算时间在n 个处理器上的平均。但是 通过合适的并行化程序设计，可以明显地缩短计算时间，达到较好的加速比，在 进行并行化程序设计之前先要对问题的并行化可行性进行分析，某些问题的并行 、化可行性较高，通过合适的程序设计会达到较好的并行效果，反之并行性较低， 并行部分在整个程序的计算比重较小，这就失去了并行化的必要。 人类对计算速度的要求是无止境的，但是c p u 的设计总是有其物理极限的， 如何能利用现有的计算机资源，缩短计算时间，并行计算提供了一个很好的前景。 人们对并行计算的要求也体现在了很多方面，如医学，军事，流体力学，生物等 很多领域。对于科学和工程中数值模拟需要对大量的数据进行很多次重复计算以 得到很好的效果，计算需要在要求的时间内完成；在制造业中，计算结果必须在 尽量短的时间内得到，这样才能满足实际的需要。 并行计算在很多方面具有广泛的应用，而对于并行计算的实现也具有很多同 的方法，根据实现并行计算的各种方法侧重点不同可以将并行计算机系统进行不 同的分类。 1 4 1 并行计算机的分类n 吐n 根据计算机能同时执行的指令和数据的多少可以将并行计算机进行如下的 分类，这是f l y n n ( 1 9 9 6 ) 仓j 造的一种分类方法，对于并行计算机主要包括两种系 统： ( 1 ) 单指令多数据计算机( 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 ) 天津大学硕十学何论文 第一章绪论 所谓单指令多数据计算机，就是用相同的指令同时对不同的数据进行操作， 这种计算机系统适合在数据阵列运算应用，提高计算效率。 ( 2 ) 多指令多数据计算机( m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ) 这种类型的计算机系统，每个处理器都有一个分离的子程序，每个程序为每 个对应得处理器生成一个指令流，每条指令对应不同的数据进行操作。 对于上面的这种并行计算机系统划分划分方法，如果依据的执行单位不是指 令而是程序，那么对应的上面两种计算机类型可以得到一种新的并行计算机类型 划分方法：单程序多数据计算机( s i n g l e p r o g r a mm u l t i p l e d a t a ) 和多；程序多数据计 算机( m u l t i p l e p r o g r a mm u t i p l e d a t a ) ，这种情况下它的划分粒度是程序而不是指 令。 根据计算机系统存储方式的不同，可以将计算机进行如下分类： ( 1 ) 共享内存计算机系统( 如图1 3 1 ) 共享内存计算机系统由多个处理器享有同一个内存空间，每一个处理器都可 以直接对内存的数据进行读取，这样可以避免各处理器之间数据的交换。 ( 2 ) 分布式内存计算机系统( 如图1 - 3 - 2 ) 分布式内存计算机系统是每个处理器都有对应的存储器，其他的处理器不可 以访问本地的存储器。在多计算机系统中，主存储器分布在各台计算机中，每个 处理器只能访问自己的存储单元，各个处理器之间通过消息传递来交换数据信 息，协调和控制各个处理器的执行。这种类型的多计算机具有很好的可移植性和 可扩展性，受到广泛的应用。 ( 3 ) 分布式共享内存并行计算机系统( 如图1 3 3 ) 这种计算机系统兼有了上面两者的特点，既有共享内存的特性，又有分布式 内存的特性。在每个计算机上有多个处理器共享一个本地存储器，在此计算机上， 处理器可以直接读写存储器中的数据，不需要通过数据传递实现数据交换，而在 各个计算机之间它们又是分布式共享存储器的，每个计算机之间则需要通过消息 传递来实现所需数据的交换，每个计算机之间的数据不能直接访问。这种计算机 系统提高了整个计算机系统的计算能力，提高了系统的模块性和扩展性。 处理器 图1 3 1 共享内存式并行计算机 9 处理嚣 存俺单元 图1 3 2 分布式内存并行计算机系 天津大学硕十学位论文第一章绍沦 图1 - 3 3 分布式共享内存并行计算机系统 1 4 2 并行计算模型 就目前的使用来看，并行计算主要有两种编程模型n 幻：消息传递编程模型和 共享存储模型。消息传递编程模型对应着分布式内存计算机系统，而共享存储模 型对应着共享内存计算机系统，但是前一种模型在共享内存计算机系统中也是可 以使用的。共享存储模型变成较为简单“幻，适合于数据并行，消息传递编程模型 级别较低，编程相对较为复杂，但他的应用较共享存储模型更为广泛，并且有很 好的可扩展性和可移植性。 ( 1 ) 消息传递编程模型 在消息传递编程模型中，一个并行程序由多个并行任务组成，每个并行任务 拥有自己的数据并对其进行操作，任务之间数据的交换是通过显式的消息传递语 句来完成的。消息传递模型为程序员提供了更加灵活的控制手段和表达形式，一 些用数据并行模型很难表达的并行算法，采用消息传递模型则可以很容易地实 现，虽然它提供了很好的灵活性，但是它将各个进程间复杂的信息交换和协调控 制交给了程序员，加重了程序员的负担，虽然如此，消息传递编程模型的通行模 型还是相对简单和清楚的。 现在广泛使用的并行编程模型主要有两个：p v m ( p a r a l l e lv i r t u a lm a c h i n e 并 行虚拟机) 和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 起源于19 8 9 年美国橡树岭国家实验室( o r n l ) ，p v m 是一个公共的并行程序开发环境，它允 许将网络上基于u n i x 操作系统的并行机或单处理机的集合当成一台单一的并行 虚拟机来使用。m p l 是m p i 论坛组织在1 9 9 4 年4 月制定完成的，发展m p i 的 目的是为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 ) 厂商提供明确定义的基本例程( 1 4 1 。 p v m 和m p l 所提供的功能大致相同，它们都提供了与c 语言和f o r t r a n 语言的 绑定，都具有很好的可移植性和可扩展性，但两者的侧重点又有所不同，p v m i o 天津大学硕士学位论文第一章绪论 强调在异构环境下的移植性和互操作性，并支持动态的资源管理和定程度的容 错，一个完整的p v m 系统由三部分组成：p v m 守护进程( p v m d ) ，p v m 消息库 和p v m 监控台进程，m p l 不像p v m 那样包括进程管理、虚拟机配置和i o 支 持，它只是_ 个通讯接口层，m p i 更强调的是性能，不同的m p i 实现之间缺乏 互操作性，本身不支持容错，m p i 比较适合于开发m p p 或同构集群上的并行应 用，可以有较高的通信性能，而p v m 更适合于异构的集群系统。 本文将使用m p i 进行并行程序的编制，关于m p i 的详细内容将在第二章介 绍。 ( 2 ) 共享存储模型 共享存储模型是将指相同的操作同时作用在不同的数据上，是一种较高层次 的编程模型。在共享存储模型中，一个并行程序由多个共享内存的并行任务组成， 它提供给编程者一个全局的地址空间，数据的交换通过使用共享内存中的数据来 完成。这种编程模型对编程者来说只需简单指明可以并行执行的循环，而不需考 虑计算和数据如何划分，编译器会自动完成并行操作任务。这种并行模型相对简 单，但它一般适用于数据并行的问题，对于非数据并行的任务并不能取得很好的 效果1 酊。 o p e n m p 是针对共享存储模型的并行程序开发标准，它是由o p e 叫v i p a r c h i t e c t u r er e v i e wb o a r d 于1 9 9 7 年推出，现在已发展到2 0 版。o p e 心w 支持 的编程语言包括f o r t r a n 、c 和c + + 。o p e 心l p 是建立在现存串行语言之上的n 射， 它定义了一套编译指导语句，用于指定程序的并行性、数据的共享和私有等信息， 为s m p ( s y m m c t r i cm u l t i - p r o c e s s o r ) 系统提供多处理器并行程序设计的应用编程 接口。 1 4 3 并行程序的性能分析方法n 町 判断某一并行程序的执行性能需要依靠一些参数的计算比较来得到，针对并 行计算性能分析这一问题已经存在着相应的分析方法，例如加速比、效率等等。 对于并行程序的所消耗的时间主要包括了这样的几个部分：( 1 ) 并行程序中串行 部分的计算时间；( 2 ) 并行程序中并行部分所执行的时间；( 3 ) 进程间信息交换的 通讯时间。以上的三部分组成了整个并行计算所需的总时间。并行程序性能的分 析主要就是依靠这几个时间部分之间的关系来进行的。下面详述几个并行程序性 能分析的指标。 ( 1 ) 加速比 加速比是指使用一个处理器的执行时间和使用具有n 个处理器的多处理机 的执行时间的比值。将使用一个处理器的执行时间定义为f 。，将使用具有n 个 天津大学硕十学何论文第一章绪论 处理器的多处理机系统的执行时间定义为，。，加速比定义为s ( ) ，那么加速比 的计算公式如下所示： s ( 刀) ：立 f p ( 2 ) 效率 效率说明了处理器用于计算的时间比例，可以表示为使用一个处理器的执行 时间和使用n 个处理器的执行时间的n 倍的比值来表示。若使用和上述相同的变 量定义方法，同时效率定义为e ( 功，则效率的计算公式可以定义为： 胁，2 南 ( 1 - 3 2 ) ( 3 ) a m d a h l 定律及g u s t a f s o n 定律 缸n d a h l 定律的基本思想是固定问题的规模，g u s t a f s o n 定律的基本思想是固 定并行计算的执行时间，通过这两种不同的假设得到了两种不同的加速系数计算 方法。 在a m d a h l 定律中，假设不