（水工结构工程专业论文）面板堆石坝并行计算方法研究.pdf

大连理工大学硕士学位论文 摘要 面板堆石坝的数值求解是一个相当复杂的高度非线性问题。采用有限元串行算法求 解时，由于要形成总体刚度矩阵，即使是采用变带宽存储，当结构的规模增大，模型网 格数随之大大增加，会导致计算机内存容量不够，计算耗时很长，难以满足实际工程应 用和研究的需要。因此，面板堆石坝的三维非线性有限元分析，对并行计算提出了较高 的要求。 多波前子结构法是一种采用“分而治之策略的方法，非常适合于并行计算。根据 面板堆石坝的模型特点和计算特点，对其数值计算实现并行化，编制了适用于机群的多 波前子结构并行计算程序，并成功地应用于西龙池下库沥青混凝土面板堆石坝的有限元 数值分析。针对面板堆石坝的并行计算，本文开展了以下几个方面的工作： 1 研究了基于子结构多波前处理技术的并行算法，将求解区域分成几个子区域，各 个处理器内独立对子结构进行静凝聚，在子结构之间的界面公共点处进行通信，求解完 边界方程组后，各处理器并行回代求出子结构内部点的位移及单元应力。 2 针对面板堆石坝的建模特点，分析模型内在的并行性，可以将面板堆石坝各剖分 断面之间的坝体作为子结构。根据它的计算特点，在坝体分级填筑过程中子结构是变化 的，设计了两种并行方案，即先串行后并行算法和完全并行算法。 3 在原有的面板堆石坝三维非线性有限元静力计算程序的基础上，采用f o r t r a n 和m p i 语言编写了并行代码。并在机群分布系统上对西龙池下库沥青混凝土面板堆石坝 的进行了有限元数值分析。通过对加速比和并行效率进行分析，结果表明采用多波前子 结构并行方法求解面板堆石坝的三维非线性有限元问题是非常有效的。 关键词：面板堆石坝；有限元；并行计算；子结构；多波前法 面板堆石坝并行计算方法研究 r e s e a r c ho np a r a l l e lc o m p u t i n go fc o n c r e t e f a c e dr o c k f i l ld a m a b s t r a c t n u m e r i c a l l ys o l v i n gt h ec o n c r e t e - f a c e d r o c k f i l ld a mi sar a t h e rc o m p l e xa n dh i g h n o n l i n e a ri s s u e b e c a u s eo ff o r m i n gt h et o t a ls t i f f n e s sm a t r i xi ns e r i a ls o l u t i o nu s i n gf e m ( f i n i t ee l e m e n tm e t h o d ) ，e l e m e n tn u m b e ro ft h e m o d e li n c r e a s e ss i g n i f i c a n t l ya st h e s t r u c t u r a ls c a l ee n l a r g e s ，e v e ni f 晰t l lv a r i a b l eb a n d w i d t hs t o r a g e s ，w h i c hr e s u l t si nt h a tt h e c a p a c i t yo fc o m p u t e rm e m o r yi si n s u f f i c i e n t ，a n dt h a tc a l c u l a t i v et i m ei sl o n g i tc a n tm e e t t h en e e d so fe n g i n e e r i n ga p p l i c a t i o na n dr e s e a r c h t h e r e f o r et h ea n a l y s i so fc o n c r e t e - f a c e d r o c k f i l ld a mb yf e mh a si n c r e a s e dt h ed e m a n df o rh i g h - p e r f o r m a n c ec o m p u t i n g t h em u l t i - f r o n t a lm e t h o db a s e ds u b s t r u c t u r ei sv e r yg o o df o rp a r a l l e lc o m p u t i n gd u et o a d o p t i n gt h es t r a t e g yo f d i v i d ea n dc o n q u e r b a s e do nm o d e lf e a t u r e sa n dc a l c u l a t i o n c h a r a c t e r i s t i c so ft h ec o n c r e t e - f a c e dr o c k f i l ld a m ，t h ep a r a l l e l i z a t i o no fi t sn u m e r i c a la n a l y s i s w a si m p l e m e n t e d ap a r a l l e lm u l t i f r o n t a lc o d ef o rc o ww a sd e v e l o p e da n da p p l i e dt ot h e n u m e r i c a la n a l y s i so fx i l o n g c h il o w e rr e s e r v o i rd a m ，a na s p h a l tc o n c r e t ef a c e dr o c k f i l ld a m n ew o r ka b o u tp a r a l l e lc o m p u t i n go ft h ec o n c r e t e - f a c e dr o c k f i l ld a mh a sb e e nc a r r i e do u ta s f o l l o w s r e s e a r c ho ns u b s t r u c t u r ep a r a l l e la l g o r i t h m s 、析廿1m u l t i f r o n t a lp r o c e s s i n gt e c h n i q u eh a s b e e np e r f o r m e d t h es t r u c t u r ei sf i r s td i v i d e di n t os o m es u b s t r u c t u r e s t h e n ，t h ei n d e p e n d e n t f r o n t sc a nb ea s s e m b l e da n dc o n d e n s e di ne a c hp r o c e s s o r a sar e s u l t ，t h ec o n d e n s e di n t e r f a c e s t i f f n e s sm a t r i c e sa n dl o a dv e c t o r sa r eo b t a i n e d b ya s s e m b l i n g 、析t 1 1c o m m u n i c a t i o nb e t w e e n p r o c e s s o r sa n ds e r i a l l ys o l v i n gt h eg l o b a li n t e r f a c ee q u a t i o nt og e td i s p l a c e m e n t sa n dt h e n b a c k i n gt oe v e r ys u b s t r u c t u r ei np a r a l l e l ，t h ei n t e r - n o d a ld i s p l a c e m e n t sa n de l e m e n ts t r e s s e s a r ec o m p u t e d a c c o r d i n gt h em o d e l i n gf e a t u r eo fac o n c r e t e f a c e dr o c k f i l ld a m ，i n t r i n s i cp a r a l l e l i s m t h a ts o m en e i g h b o u r i n gd a ms e c t i o n sc o u l dm a k eu po fas u b s t r u c t u r eh a sb e e na n a l y z e d t w op a r a l l e ls c h e m e sw h i c ha r et h ef i r s ts e r i a la n dl a s tp a r a l l e la r i t h m e t i ca n dt h ef u l lp a r a l l e l a r i t h m e t i ch a v eb e e nd e s i g n e db yt h e c o m p u t a t i o nc h a r a c t e r i s t i c t h a ts u b s t r u c t u r e sa l e v a r i a b l ei n t h ep r o c e s so ff i l l i n gd a mb yd i f f e r e n tl e v e l o nt h eb a s i so f e x i s t i n g 3 一dn o n l i n e a rf e ms t a t i c s e r i a lp r o g r a m ，t h ea u t h o r p r o g r a m m e dap a r a l l e lc o d eu s i n gf o r t r a na n dm p il a n g u a g e p a r a l l e lp r o g r a mc a nb e a p p l i e dt of e mn u m e r i c a ls i m u l a t i o no fx i l o n g c h il o w e rr e s e r v o i rd a m ，a na s p h a l tc o n c r e t e f a c e dr o e k f i l ld a ms u c c e s s f u l l y b ya n a l y z i n gs p e e d u pr a t i o sa n dp a r a l l e le f f i c i e n c y ，t h e i i 大连理工大学硕士学位论文 c o n c l u s i o ns h o w st h a tt h ep a r a l l e lm u l t i f r o n t a lm e t h o dc a l lb eu s e dt or e l i a b l ya n a l y z et h e c o n c r e t e f a c e dr o c k _ i l l ld a m k e yw o r d s ：c o n c r e t e f a c e dr o c k f i l ld a m ；f i n i t ee l e m e n tm e t h o d ；p a r a l l e l c o m p u t i n g ；s u b s t r u c t u r e ；m u l t i f r o n t a lm e t h o d 1 1 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日期：丑蓝年_ z 一月尘一日 e l 期：趁年月j l 日 大连理工大学硕士学位论文 1绪论 1 1 研究背景 当前我国的水利水电工程发展迅速，拟建和在建的大坝无论是在数量上还是在规模 上都很惊人。高坝结构的力学分析具有计算规模大、非线形明显、不确定性的影响因素 多、对安全性要求高、施工周期长等种种特点，还存在多种耦合及需要反复计算等问题。 自1 9 6 0 年c l o u g h 首次提出有限单元法l l j 以来，它已经成为上述工程研究课题数值分析 的有力工具，促进了我国水利水电事业的发展。 其中，面板堆石坝 2 1 具有运行性良好，经济效益高等优点，成为可行性研究中优先 考虑的坝型，在国内外有了巨大的发展，拟建或在建的面板堆石坝达到了2 0 0 多米级高 度，规模极其庞大。因此，要求我们加大对地基和坝体的材料稳定性及整体结构稳定性 的研究，加强对材料和结构的破坏进行分析计算。 在静力计算【3 1 方面，包括施工填筑过程和蓄水过程中坝体的变形及应力状况的模拟 分析。根据实际工程，要采用多种材料，且堆石体为非线性，坝体经过多级施工加载完 成，所以计算过程也要分成多个荷载步和计算子步。可以看出，面板堆石坝的数值求解 是一个相当复杂的高度非线性问题。采用有限元串行算法求解时，由于要形成总体刚度 矩阵，即使是采用变带宽存储，当结构的规模增大，模型网格数随之大大增加，也会导 致计算机内存容量不够。如果要提高精度，需要加密网格，有时还采用大量的高阶单元， 从而使得有限元方程组的阶数巨大，普通计算机由于受到内存容量和运行速度的限制， 要么计算速度非常慢，要么无法计算，难以满足实际工程应用和研究的需要。 对位于高地震烈度区的坝体，动力反应分析是必不可少的。在动力计算【4 】方面，应 用动力非线性有限元方法，在等价线性的假定下完成。为了预估坝体地震加速度和应力 时程反应，一般采取逐步时程积分法在时域中求解的方法，计算量大，计算速度非常慢。 总之，如果对水利工程中的结构进行有限元数值模拟，要获得一个较好的精度，保 证计算结果的可靠性，必须将计算网格控制在一个适当的大小，又由于水工结构的规模 一般都很庞大，采用有限元法的计算量会非常大，因此对计算能力提出很高的要求1 5 棚。 虽然现在的计算机性能有了较大的提高，但仍无法满足工程需要。 因而提高计算规模和减少计算时间是水工结构数值计算面临的一个严峻的问题，高 性能并行计算是其中一种非常好的解决方案f 卜引。它是提高计算的稳定性、计算精度、 计算容量和计算速度等综合处理能力的一种有效的科学计算手段。它可以通过对求解问 题的并行设计、并行算法的使用以及计算服务器的并行处理，提高计算效率。并行计算 面板堆石坝并行计算方法研究 的基本思想就是：将某一问题的计算任务分成几份，把每一份分配给不同的处理器，各 个处理器协调工作，同时进行计算，完成求解。 采用普通的p c 机群就可以实现并行计算，既经济又可以充分利用资源。只要组成 的并行系统可扩展，处理器数目足够多，就能满足数值计算对硬件的要求。因此并行有 限元计算在水利工程中会发挥越来越显著的作用，研究并行计算是很有意义的。 1 2 并行计算发展概况 1 2 1 并行计算机发展概况 并行计算机作为高性能计算的硬件环境和物质基础，发展迅猛。1 9 5 2 年美国研制了 第一台位并行运算样机，1 9 5 3 年开发了具有位并行运算的第一台商业计算机i b m 7 0 1 ， 六十年代研制了流水线单处理机系统，七十年代出现了向量计算机、阵列计算机、相联 处理机等并行处理系统，八十年代以后计算机的体系结构取得了突破性进展，最具代表 性的是精简指令系统计算机、数据流计算机及智能计算机等。 1 9 6 6 年f l y r m l 9 j 按照指令流和数据流的多倍性概念将计算机结构进行了分类。根据 指令流和数据流的不同组合，可分为单指令单数据流( 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 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 ) 、多指令单数据流( m u l t i p l e i n s t r u c t i o ns i n g l ed a t a , m i s 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 , m i m d ) 。其中s i s d 是普通的串行机，m i s d 是不实际的计算机，可以构成并行计算机 的除少量专用的s i m d 系统外，绝大部分为m i m d 系统，包括并行向量处理机( p a r a l l e l v e c t o rp r o c e s s o r ，p v p ) 、对称多处理机( s y m m e t r i cm u l t i p l ep r o c e s s o r s ，s m 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 ) 、工作站机群( c l u s t e ro f w o r k s t a t i o n ，c o w ) 和分 布式共享存储( d i s t r i b u t e ds h a r e dm e m o r y ，d s m ) 多处理机。这五类并行机在科学和工程领 域中被广泛应用，表现出各自的优势和特色。实践证明，s m p 、m p p 与c o w 逐渐占据 了主导地位。 和s m p 、m p p 相比，机群的成本较低，节约系统资源，但同样可以达到很高的性 能，并且具有可扩展性、高吞吐量、易用性等特点。尤其在对现有单机上的软、硬产品 继承和商用软、硬件最新研究成果的快速运用上，都表现出了传统无法比拟的优势。 1 9 7 7 年至今，我国的超级计算机主要有银河机、神威机、深腾6 8 0 0 、曙光4 0 0 0 a 等。近几年来，我国高性能计算机的性能有大幅突破，进入快速增长期。即将落户上海 超级计算中心的曙光5 0 0 0 a 的l i n p a c k 性能达到1 7 4 9 万亿次每秒。可以看出，中国高 性能计算机在世界t o p 5 0 0 中占有一席之位，但还是有一定的差距。 大连理工大学硕士学位论文 1 2 2 有限元并行算法介绍 算法设计是并行程序设计的基础，随着有限元并行计算的发展，在建模、分析、求 解和后处理各个分析阶段挖掘并行性，研究出适用高效的并行算法。目前相对比较成熟 的有限元并行算法主要包括以下三种： ( 1 ) 大型方程组的并行求解【1 0 1 方程组的求解占了整个有限元分析8 0 以上的计 算量，是分析过程中最关键的步骤。早期的有限元并行算法仅对形成总体刚度矩阵后的 大型线形方程组进行并行求解，其它部分仍采用串行方法，实现比较容易，但是并行效 率较低。这种算法常用在内存需求不是很大，但计算量非常大的问题中。当求解问题规 模增大时，将会涉及到内外存交换，从而导致并行效率降低。 ( 2 ) 区域分解法它基本上采用了子结构的计算思想，实际上也可以理解为子结 构技术。1 9 7 7 年h p e t e r s s o n 、a n o o r 提出了有限元并行计算的子结构方法，但直到1 9 8 7 年区域分解法才在有限元计算中得以广泛应用，c h a r b e lf 砷“1 1 】在这方面做的工作较 多。它能够在结构级提高有限元的并行度，是一种粗粒度的算法，有非常好的并行效率 但要求各个子区域达到负载平衡，并且尽量降低各子区域之间的边界自由度以减少通信 量。对于规则结构而言，容易剖分且得到的子结构较好；对于那些极其不规则的结构来 说，区域分解非常复杂而且不一定能得到任务均衡的子结构，这已经成为该算法的一大 难点，一直没有得到很好的解决。 ( 3 ) e b e ( e l e m e n t b y e l e m e n t ) 法它是t j r h u g h e s 1 2 j 在19 8 3 年首先提出来的， 最初用于热传导问题，随后扩展到固体力学和结构力学领域。早先是为了节省串行算法 过程的存储与计算，但这一技术很快被成功应用于并行计算方面。它是在算法级提高有 限元并行度，避免了总刚的生成及存储，对单元和节点编号没有任何要求，对结构的形 状没有任何限制，这样就避免了不规则结构区域分解带来的复杂问题，能够方便的应用 于各种结构。但是e b e 需要在各个进程之间频繁进行数据交换，通信耗时比较大，对 并行效率造成了一定的影响。因此需要根据实际情况结合一些预处理技术，同时采用计 算与通信的大量重叠，提高算法的计算和通信间的比例，实现效率最优。 1 2 3 并行计算在水工结构中的研究 并行计算在科研计算、大气气象、企业应用及能源石油等等许多方面发挥着显著的 作用，在各应用领域的分布情况如图1 1 所示( 图片来自网址w w w i t l 6 8 c o r n ，作者： 洪钊峰) 。 一3 一 面板堆石坝并行计算方法研究 。t 特。，鬣裂嚣嚣滞裂器勰臻懒恻+ 。 f ，明囊蠢啊 1 8 图1 1 并行计算在各应用领域的分布情况 f i g 11 d i s t r i b u t i o n o f p a r a l l e lc o f n p m m i n i n a l l g p p l i c a f i a n f i e l d s 在水利工程方面，并行计算研究开展地相对较晚，还处于起步阶段。我国水利科研 工作者也做出了开刨性的工作，主要研究成果有： 刘耀儒1 5 - 6 1 j - 1 帅采用e b e 法对拱坝地基系统进行三维有限元数值分析，算法具 有较优的可扩展性，将其应用到实际工程二滩拱坝地基系统的数值模拟中，当使用 1 6 个c p u 进行计算时，效率可以达到4 3 。同时应用该并行程序对锦屏拱坝进行了有 限元数值计算，网格规模达到了百万自由度，计算仍取得了很好的并行效果。 马怀发”i 开发了混凝土试件的三维细观数值并行计算程序，在中国水利水电科学研 究院抗震中心联想深腾1 8 0 0 机群上进行测试，当采用5 个节点1 0 个c p u 进行计算时 并行效率维持在7 0 以上。 张友良【蚌1 ”组建w i n d o w s 下p c 机群并行系统，采用基于区域分解预处理技术的并 行共轭梯度法实现方程组的求解，对水布垭地下厂房进行三维有限元并行模拟，得到了 较好的加速比，还讨论了计算机之问的差异对负载的影响。 茹忠亮 2 0 - 2 。牲区域分解和共轭梯度算法的基础上，对水布垭电站尾水洞阶段的百万 单元模型进行了2 0 个开挖步的三维弹塑性并行有限元计算，大幅度减少计算时间，提 高计算效率。 大连理工大学硕士学位论文 姜弘道【捌对水利高性能计算的进展作了个综述，举例介绍了并行有限元法的最新 进展，指出从网络到网络是高性能计算发展的最新方向。 上述研究结果表明，水利水电工程相对于其它行业，并行有限元的研究是近些年的 事。尤其在国内，这方面的文献相对来说不是很多，系统性和深度也不够，需要水利工 作者加大对并行计算的投入，可以预料水工结构并行有限元将会越来越被重视。 1 3 本文主要工作内容 在并行计算硬件环境上，机群的优越性越来越被重视，具有性价比高、易构建、可 扩展等很多优点，因此利用研究所的普通计算机搭建了一个w i n d o w s 下的小型机群； 编程环境m p i 仅仅是作为函数库添加到现有的编程语言中，简单易行；另外基于子结构 的多波前处理并行有限元是最有前途的算法之一，通信量小，并行效率高。本文所有的 并行计算都是采用此算法在机群分布系统下实现的，使用v i s u a lf o r t r a n 语言和m p i 通 信标准。论文主要包括以下四个方面的内容： ( 1 ) 研究了基于子结构多波前处理技术的并行算法，将求解区域分成几个子区域， 各个处理器内独立对子结构进行静凝聚，在子结构之间的界面公共点处进行通信，求解 完边界方程组后，各处理器并行回代求出子结构内部点的位移及单元应力。 ( 2 ) 使用悬臂梁算例，在各种荷载条件下对波前法程序进行了验证，同时编制了 平面四节点并行多波前法程序，将其应用到重力坝平面模型的数值模拟，和a n s y s 计 算进行比较，结果基本一致。 ( 3 ) 针对面板堆石坝的建模特点，分析模型存在的并行性，可以将面板堆石坝各 剖分断面之间的坝体作为子结构，设计了面板堆石坝多波前子结构并行有限元求解算 法。 ( 4 ) 在原有的面板堆石坝三维非线性有限元静力计算程序的基础上，编写了并行 代码，同时将前处理程序并行化。并在机群分布系统上对西龙池下库沥青混凝土面板堆 石坝的进行了有限元数值分析，给出了并行模拟的加速比和效率。 2 并行计算的基本理论 2 1 并行程序的设计 2 1 1 并行编程模式 研究现有的并行应用程序，可以归纳出几种常用的并行编程模式1 0 1 ，分别为：主从 式( m a s t e r - s l a v e ) 、单程序流多数据流( s i n g l ep r o g r a mm u l t i p l ed a t a , s p m d ) 、数据流水线 ( d a t ap i p e i i n i n g ) 和分治策略( d i v i d ea n dc o n q u e r ) 等。 其中主从模式的基本思想是将一个待求解的任务分成一个主任务( 主进程) 和一些 从任务( 子进程) 。主进程负责分解任务并收集各子进程的求解结果，最后汇总得到问 题的最终解；子进程接收主进程发来的消息，并行进行计算，将各自的计算结果发送给 主进程，如图2 1 所示。 主进程 程n 汇总得最终解 图2 1 静态主从结构编程模式 f i g 2 1p r o g r a m m i n gm o d e o fs t a t i cm a s t e r - s l a v es t r u c t u r e 单程序流多数据流s p m d 模式的基本原理是并行运行的进程执行相同的代码段，但 却操作在各自不同的数据上，如图2 2 所示。 一6 一 大连理工大学硕士学位论文 分配数据 孑万卜 计算 计算计算 计算 通信+ 一通信+ 通信，通信 计算计算计算 计算 汇集计算结果 图2 2s p i h d 编程模式 f i g 2 2 s p m dp r o g r a m m i n gm o d e 数据流水线模式是将各计算进程组织成一条流水线，每个进程执行一个特定的计 算任务，示意图见2 3 。 输入 进程1 进程2 进程n 图2 3 数据流水线编程模式 f i g 2 3p r o g r a m m i n gm o d eo f d a t ap i p e l i n i n g 输出 分治策略模式很常见，它是将一个大而复杂的问题分解成若干个特性相同的子问题 分而治之。如图2 4 所示，一个计算任务实际上可组织成一棵树，实箭头线代表问题的 分解过程，虚箭头线代表归并过程，实际的计算是由树的叶节点并行完成。这种编程模 式很自然的使用在递归并行程序设计中。 原f - j 题 子问题 图2 4 分治策略的树形编程结构 f i g 2 4 t r e ep r o g r a m m i n gs t r u c t u r eo fd i v i d ea n dc o n q u e r 面板堆石坝并行计算方法研究 2 1 2 并行设计步骤 一般而言，并行程序的设计过程可分为4 步：任务划分( 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 设计过程【2 3 1 ，如图2 5 所示。 组 a 口 图2 5p c a m 设计过程示意图 f i g 2 5 s k e t c ho fs t e p sa b o u tp c a m d e s i g n i n g 下面对四个阶段分别作一个简述： 顾名思义，任务划分就是把总的计算量划分为多个小的任务，充分开拓程序的并发 性。只有执行的任务减少了才可能使单个处理器节省内存，减少计算时间。划分的要点 就是使数据集和计算集互不相交。最理想的情况是，分解后的各个任务执行时间相同且 任务之间共享数据最少，也就是几乎达到1 0 0 的并行效率。任务分解涉及到一个“粒 度 的概念。将求解问题分解成许多很小的任务属于细粒度分解，e b e 法就是属于这种 情况；相反，将问题分解成几个大的任务属于粗粒度分解，这种类型有区域分解法。它 们适用于不同的并行体系。 通信分析，确定如何协调任务的执行，采用合适的通信与同步机制，使通信开销尽 可能地小。几种主要的通信类型为：局部通信和全局通信：局部通信时，每个任务只 和较少的几个邻近的任务通信；全局通信发生在所有的任务之间。静态通信和动态通 信：静态通信的各个任务在程序编译时就确定了，且不随时间改变；动态通信，由所计 算的数据决定，在程序运行中是可变的。同步通信和异步通信：同步通信时，接收方 和发送方协同操作；异步通信时，接收方获取数据无需与发送方协同。通信中重要的一 点是需要防止死锁，程序因为执行顺序原因而被锁住。因此应该采取相应措施，比如： 采用非阻塞式通信，发送和接收配对，先发送后接收等等。 一8 一 大连理工大学硕士学位论文 在任务划分和通信阶段，并未考虑算法在具体并行机上的执行效率，通常需要进行 优化和组合。组合的目的就是通过合并小尺寸的任务来减少任务数，理想情况是任务数 和处理器数目一致。用增加计算和通信粒度的方法可以减少通信成本，既要保持足够的 灵活性又要减少软件工程代价，这几个相互矛盾的准则在组合阶段需要仔细权衡。 映射就是指定任务到哪个处理器上去执行，主要目标是减少算法的总执行时间，有 两种策略：把那些可并发执行的任务放在不同的处理器上，增强并行度；把那些需 频繁通信的任务置于同一个处理器上，以提高局部性。两者有时会冲突，需要权衡。映 射需要保证负载平衡。简单地说，负载平衡就是使所有处理器完成等量的任务，执行时 间相同。它与任务分配调度密切相关，一般动态调度可以取得较好的负载平衡效果， 但开销也很大。因此，如果静态调度有较好的负载平衡效果，就尽量采用静态调度技术， 否则，再采用动态调度。 2 2 计算环境的选择 这里的计算环境是指软件环境，包括：操作系统、编程模型及其实现平台和编程语 言。它们对计算性能的影响很大，下面主要对并行编程模型和并行编程语言进行介绍。 2 2 1并行编程模型及并行语言简介 并行程序开发模型多种多样，不同的并行系统有不同的程序设计模型，没有一个统 一的模型。目前比较流行的并行编程模型包括数据并行模型、消息传递模型以及共享变 量模型。 ( 1 ) 数据并行模型它既可以在s i m d 计算机上实现，也可以在s p m d 计算机上实 现，取决于粒度的大小。s i m d 程序着重开发指令级细粒度的并行性：s p m d 程序则着 重开发子程序级中粒度的并行性。数据并行模型具有单线程、松散同步、全局命名空间、 隐式相互作用和隐式数据分配等特点。 ( 2 ) 消息传递模型指各个并行的进程可以通过网络显式地传递消息来交换数据、 协调步伐和控制执行。它比较适合于开发大粒度的并行性，不仅可执行在共享变量的多 处理机上，而且可执行在分布存储的多计算机上。具有多线程、异步并行性、分开的地 址空间、显式相互作用和显式分配的特点。 ( 3 ) 共享变量模型指各处理器上的进程可以通过读写公共存储器中的共享变量相 互通信。它与数据并行模型相似，也具有单一的全局地址空间；与消息传递模型的相似 之处在于它是多线程和异步的。它不需要显式分配数据，但工作负载既可显式也可隐式 分配。 面板堆石坝并行计算方法研究 当前，最流行的编程模型是消息传递模型。它比另外两种模型更灵活，且提供了较 高的并行效率，两种广泛使用的标准库，即并行虚拟机( p a r a l l e lv i r t u a lm a c h i n e ，p v m ) 和 消息传递接e l ( m e s s a g ep a s s i n gi n t e r f a c e ，m p i ) ，使消息传递程序大大地增强了可移植性。 p v m 由美国橡树岭国家实验室于1 9 8 9 年开发的一种支持网络并行的自由软件，异构性 和可移植性是其设计的主要目的。用户通过它可以将一组由不同网络连接起来的、不同 类型的计算机看作是一台虚拟的并行机。但p v m 不是一个标准，可以修改源代码。m p i 是1 9 9 4 年推出的，目的在于将众多消息传递库标准化。它具有许多优点，将在下节中 详细说明。 并行程序通过并行语言来表达，主要有三种方式：设计全新的并行语言，完全摆 脱串行语言的束缚，从语言成分上直接支持并行；扩充原来串行语言的语法成分，采 用新的语言结构支持并行性；不改变串行语言，仅在并行程序设计中调用支持并行性 的库函数。 目前，第一种方式实现起来难度和工作量都很大，方式二实现难度有所降低，但仍 需要重新开发编译器，对于方式三，仅提供并行库，是一种对原来的串行程序设计改动 最小的并行化方法，编程者只需在串行程序中添加对并行函数的调用，即可实现并行程 序设计，操作简单，非常灵活。m p i 就是作为一个库在并行设计中应用越来越广泛。 本论文就是采用了消息传递模型，以及m p i 通信标准，具体的实现平台是m p i c h 2 。 2 2 2 并行编程环境帅i m p i 1o ，2 4 】是目前国际上应用最广泛的一个基于消息传递的并行编程工具，目的就是 服务于进程间通信。它提供了一种与语言和平台无关，可以被广泛使用的编写消息传递 程序的标准。 它具有移植性好、可扩展性好、功能强大、效率高、灵活等许多优点，而且有多种 不同的免费、高效、实用的版本。几乎所有的并行计算机厂商都提供对它的支持，一个 正确的m p i 程序，可以不加修改地在所有的并行机上运行。 由于m p i 是一个库而不是一门语言，所以对m p i 的使用必须和特定的语言结合起 来，进行一个所谓的语言绑定。f o r t r a n 是科学与工程计算的传统语言，c 和c + + 是 目前使用非常广泛的应用程序开发语言，因此对它们的支持是必须的。m p i 库可以被 f o r t ra n c c + + 调用，遵守所有程序对库函数的调用规则。从某种意义上，我们可以 把m p i + f o r t r a n c c + + 看成是一种并行语言。 m p i c h 是一种最重要的m p i 实现，本文就是在m p i c h 2 1 0 5 p 2 的软件环境下进行 并行计算的。 大连理工大学硕士学位论文 2 2 3 归l 的基本函数 在m p i 并行程序的运行过程中，首先要定义一个通信域，每个进程都会属于一个或 多个通信域。进程组就是通信域中所有进程的集合，每个进程分别由整数0 ，1 ，2 ， n 1 标识，都属于由m p i 环境系统变量m p ic o m mw o r l d 指定的通信域。 m p i 提供了两百多个函数，串行语言f o r t r a n 、c 以及c 抖可以直接调用这些函 数。理论上说，m p i 所有的通信功能可以用6 个基本函数来实现，它们构成m p i 子集。 本文所有程序都是在工程编程语言f o r t r a n 中添加m p i 函数库的编程环境下进行的， 下面给出这6 个基本函数： ( 1 ) m p i 初始化 m p i i n i t ( i e r r o r ) 它是m p i 程序的第一条可执行语句，完成m p i 程序所有的初始化工作。 ( 2 ) m p i 结束 m p i _ f i n a l i z e ( i e r r o r ) 它是m p i 程序的最后一条可执行语句，结束m p i 程序的运行。 ( 3 ) 获取进程标识 m p i c o m m _ r a n k ( m p i _ c o m m _ w o r l d ，r a n k ，i e r r o r ) 它返回调用进程在给定的通信域中的进程标识号，因此，每个进程可以与其它的进 程区别开来，实现各进程间的协作。r a n k 表示进程号，相当于身份证。 ( 4 ) 获取通信域包含的进程数 m p i c o m m _ s i z e ( m p i _ c o m m _ w o r l d ，s i z e ，m m 王o r ) 它返回给定的通信域中所包含的进程总数，各进程可以知道此通信域中共有多少个 进程在并行执行。s i z e 表示进程个数，是一个整型量。 ( 5 ) 消息发送 m p i _ s e n d ( b u f ，c o u n t ，d a t a t y p e ，d e s t ，t a g ，m p i _ c o m m _ w o r l d ， i e r r o r ) m p is e n d 指定一个发送缓冲区，它是由c o u n t 个类型为d a t a t y p e 的连续数 据组成，起始地址为b u f ；然后将发送缓冲区中的c o u n t 个d a t a t y p e 类型的数据 发送到目标进程d e s t ，t a g 为本次发送的消息标志。 ( 6 ) 消息接收 m p i _ r e c v ( b u f ，c o u n t ，d a t a t y p e ，s o u r c e ，t a g ，m p i c o m m _ w o r l d ， s t a t u s ，i e r r o r ) m p ir e c v 从指定的进程s o u r c e 接收c o u n t 个类型为d a t a t y p e 的连续数 据，保存在接收缓冲区中。该接收缓冲区由c o u n t 个类型为d a t a t y p e 的连续数据 面板堆石坝并行计算方法研究 组成，起始地址为b u f 。值得注意的是，接收到消息的长度必须小于或等于接收缓冲区 的长度，否则会发生溢出错误。s t a t u s 为返回状态。 2 3 机群的搭建 大连理工大学水利水电研究所水工教研室有十几台普通计算机，它们与校园网相 连。采用1 0 1 0 0m b s 自适应网卡和1 0 0m b s 交换机，在通信协议上使用t c p i p 协议。 本文就是利用这些计算机搭建了一个局域网微机机群，并考虑了两个方面的问题：能 够充分利用现有的分散的闲置的计算机资源实现并行计算。尽量不打扰其它计算机用 户正常的学习。因此，建立机群时机器仍原位不动并采用熟悉的w i n d o w s 操作系统。 建立的网络机群如图2 6 所示。它是4 个计算节点和一个服务节点( 兼作计算节点) 通过一台1 0 0m 交换机连接而成的星形拓扑结构的以太网，属于局域网机群。局域网通 过校园网与因特网相连。服务节点和各计算节点的配置如表2 1 所示。其中，s e r v e r 为 服务节点，其它为计算节点。 图2 6 局域网微机机群示意图 f i g 2 6 s k e t c ho fl a n ( 1 0 e a la r e an e t w o r k ) c o w 表2 1 各节点的配置 t a b 2 1 c o n f i g u r a t i o no fe a c hc o m p u t e r 大连理工大学硕士学位论文 2 4 并行算法的性能评价 对求解问题采用并行算法的最终目的就是为了减少计算时间、提高计算速度以及增 加计算规模。并行算法是否能达到这些目标，需要对它进行性能评价，关注的主要指标 有【2 5 】：并行度、加速比和效率。 ( 1 ) 并行度算法的并行度是指算法中可并行执行的操作数。在并行机上即为进 行并行计算的处理器的数目。从直观意义上说，并行度是刻画一个并行算法的“并行程 度 的量，反映了软件与硬件并行性匹配的程度。 ( 2 ) 加速比它是指：对于一个给定的应用，速度相对于串行程序的执行时间与 并行程序的执行时间的比值，如下： 2 他。 其中，瓦，乃分别为在并行机上用单处理器和p 个处理器执行算法所用的时间。 ( 3 ) 效率并行算法的效率是衡量并行系统中处理器能力发挥的程度。定义为加速 比和计算节点个数之比，如下式： 髟= 詈 住2 ， 其中，品为式( 2 1 ) 中所求的加速比，p 为处理器个数。 有时候，一个并行算法虽然有好的加速比，但处理器的利用率可能很低。明显地， 0