（测试计量技术及仪器专业论文）网格计算在有限元并行计算方法中的应用研究.pdf

湖北工业大学颈士学位论文 摘要 如今大规模的有限元法工程计算问题对计算机计算能力豹要求越 水越高。计算机网络技术迅速发展后，如何充分发掘利用互联网资源， 。其现大规模的科学与工程的并行计算，是网格计算技术的应庸之一。 本文研究的是如何在网格计算环境中实现有限元法并行计算。首 先文章介绍有限元法并褥计算的研究状况，随后介绍网格计算的概念， 癜用发展及网格系统。然系结构。重点介绍了目前流行的网格计算工具 包g l o b u s ，详细诡明了g l o b u s 构成的网格计算环境的安装配置及网格 计算环境中媳蠹鍪拳羲羧计。最磺，也是。本文的重点，采用j a v a 语言开发 纛黼灞蹲目攀攀搿储计算的有限元并行计算系统的原型d p f e m ，探讨了该系 统的硬件组成和运作机制。在此基础上，进行了有限元并行计算的实 验。计算结果表明，运用网格计算技术实现的并行算法可以极大地提 高有限元法的计算速度。 本文所采用的网格计算环境基于高速校园网，通过网络连接分布 的计算资源，形成对用户透明的网格计算环境，最终实现有限元法并 行计算。该环境可在i n t e r n e t i n t r a n e t 上实现，构成系统的计算机可以 楚异构的，客户端的程序类型可以是不同的。因此，本文的研究有利 。鼍潺厨卿格计算技术提高工程运算速度和闲置设备利用效率，推动网 格计算技术向科学和工程数值计算方向发展。 关键词：网格计算，有限元法，并行计算，g l o b u s ，j a v a 湖北工业大学硕士学位论文 a b s tr a e t 。w e h a v e h i g h e re x p e c t a t i o n s f o r c o m p u t i n gc a p a b i l i t y o ft h e c o m p u t e ri n 。e x t e n s i v ee n g i n e e r i n gc a l c u l a t i o nq u e s t i o n a b o u tf i n i t e 一6 t e m e n tm e t h o dn o w a d a y s a f t e rc o m p u t e ra n dn e t w o r kt e c h n o l o g yi s d e v e l o p e dr a p i d l y ，h o wt of u l l ye x p l o r ea n du t i l i z er e s o u r c e so fi n t e r n e t ， r e a l i z i n gt h ep a r a l l e lc o m p u t a t i o no fe x t e n s i v es c i e n c ea n dp r o j e c t ，：i sa l l i m p o r t a n ta p p l i c a t i o no ft h eg r i dc o m p u t i n gt e c h n o l o g y t h i s p a p e ri n t r o d u c e sh o wt o r e a l i z ep a r a l l e lc o m p u t i n go ff i n i t e e l e m e n tm e t h o d 疆g r i dc o m p u t i n ge n v i r o n m e 霉t a tf i r s ti t i n t r o d n c e st h e r e s e a “c ha c t i t 滋r yo fp a r a l l e lc o m p u t i n go ff i n i t ec l e m e n tm e t h o d t h e ni t i n t r 囊嘲晦湎ec o n c e p t i o na n da p p l i c a t i o nd e v e l o p m e n to fg r i dc o m p u t i n g ， i 黪? a i n gt h ea r c h i t e c t u r e o fg r i ds y s t e m i ti n t r o d u c e sg l o b u ss p e c i a l l y ， 潮港i c hi sp o p u l a ra sa g r i dc o m p u t i n gt o o l k i t ，a n d e x p l a i n st h ei n s t a l l a t i o n ， c o n f i g u r a t i o na n dp r o g r a m m e ro fg r i dc o m p u t i n ge n v i r o n m e n tb u i ! d e d w i t hg l o b u s ap r o t o t y p eo fd i s t r i b u t e dp a r a l l e lf i n i t ee l e m e n tm e t h o d ( d p f e m )b a s e do ng r i dc o m p u t i n gi sd e v e l o p e d h a r d w a r ec o m p o n e n t un dw o r km e c h a n i s mo ft h i s s y s t e m i sa l s od i s c u s s e di nt h i s p a p e r m o r e o v e r ，as i m u l a t i o ne x p e r i m e n t a t i o na b o u td p f e mi st a k e n t h e r e s u l ti n d i c a t e sc o m p u t i n gs p e e dc a nb eg r e a t l yi m p r o v e db yu s i n gg r i d c o m p u t i n gi np a r a l l e lf i n i t ee l e m e n tm e t h o d l i n k i n g d i s t r i b u t e dn e te n v i r o n m e n t t h r o u g hi n t e r n e t ，f o r m i n g t r a n s p a r e n tg r i dc o m p u t i n ge n v i r o n m e n tf o ru s e r ，d p f e mb a s e so n c a m p u sn e t t h i se n v i r o n m e n tcanb er e a l i z e do ni n t e r n e t i n t r a n e t ，a n d t h ec o m p u t e ri ni tc a nl o c a t ei nd i f f e r e n ta r e a s ，a n dc l i e n t sp r o c e d u r e t y p ec a nb ed i f f e r e n tt o o s ot h er e s e a r c ho ft h ep a p e rh e l p st ou s en e t t e c h n o l o g yt oi m p r o v ep r o j e c to p e r a t i o nt e m p oa n ds t a n d - b ye q u i p m e n t u t i l i z a t i o ne f f i c i e n c y ，p r o m o t eg r i dc o m p u t i n gt e c h n o l o g yt os c i e n t i f i c e n g i n e e r i n gn u m e r i c a lc a l c u l a t i o nd i r e c t i o ni sd e v e l o p e d k e yw o r d s ：g r i dc o m p u t i n g ，f i n i t ee l e m e n tm e t h o d ，p a r a l l e lc o m p u t i n g ， g 】o b u s 。j a v a 湖北工业大学硕士学位论文 1 1 课题来源及意义 1 1 1 课题来源 第1 章绪言 本课题是湖北省自然科学基金项目网格计算在分布式仿真技术中的应用研 究的一部分( 编号4 1 3 0 4 0 4 0 2 ) 。 1 1 2 课题研究的意义 i n t e r n e t 的飞速发展使网格计算成为继传统因特网、w e b 之后的第三次互联 网革命。所谓网格计算( g r i dc o m p u t i n g ) ，也称为网格( g r i d ) ，其鼻祖美国a r g o n n e 国家实验室的i a nf o s t e r 博士定义，“网格是一种面向虚拟组织的资源共享技术” “。它将网络上的各种资源，如超级计算机、大规模存储设施、个人计算机和各 种外部设备等组织在一个统一的框架下，从而能够以方便的方法解决各种分布式 应用的问题。传统因特网实现了计算机硬件的连通，w e b 实现了网页的连通，而 网格则试图实现互联网上所有资源的全面连通。它面向地理分布的资源和用户提 供可靠的、一致的高端资源服务的硬件和软件基础设施。许多研究都能在网格计 算里不断发展。 并行计算是提高计算机系统计算速度和处理能力的一种有效手段。自六十年 代出现并行处理概念以来，发达国家在并行处理技术上已达到很高的水平，已用并 行处理技术求解了相当多的实际问题嘲。国内在并行算法研究方面也取得了定的 进展。小。“。有限元法并行计算因为算法复杂，计算量大而实现难度较大。传统的 并行计算环境，如p v m 、m p i 等，大多基于类u n i x 系统。本文的不同之处是基于 w i n d o w s 系统，结合网格计算技术来进行有限元并行计算。并且比较不同并行计算 模式下的计算速度，以探索一种最佳的有限元并行计算模式。 国内外虽然有一些有限元法并行计算方面的研究和应用，但结合了网格计算 技术来研究则是一种全新的尝试“”“。利用网格计算技术实现计算资源、存储 资源、设备、数据库甚至人力的共享，可以有效解决并行计算领域计算、可视化 等方面的高效并行处理，也是针对计算机及相关技术向科学运算渗透提出的一种 湖北工业大学硕士学位论文 新的解决方案。网格应用的发展目的，是为了提高当前i n t e m e t 上的计算机计算能 力，存储信息，各种硬件设施和人力资源的利用率，同时使得互联网上的用户可 以非常方便的得到许多以前享受不到的服务。作者在参与浙江桃天门跨海大桥的 监控工作期间就曾经使用同济大学开发的d o c t o rb r i d g e 桥梁软件，该软件可以很 好的计算桥梁的结构应力。作为一款单机版的专业软件，它价格昂贵，如果电脑 上没有安装这个软件，就无法进行相关分析和计算。有没有办法不购买该软件， 而且能“获得”相关分析和计算能力呢? 现在看来是可以的，在我们理想的网格 环境下，i n t e m e t 上的计算机的相关资源，包括存储的信息，安装的软件，数据库 甚至使用计算机的人，都成为了网格环境的组成部分。就是说商业公司可以在服 务器端安装好这类专业软件，并且提供必要的端口供客户登陆，客户只需要通过 浏览器访问这些端口就能够进行必要的有限元分析和计算。当然，浏览器提供的 端口处会提供客户需要的参数设置等，以满足不同客户的需求。这也是我们进行 基于网格环境的有限元并行计算研究的应用前景之一。 研究本课题的意义在于： ( 1 ) 本课题研究立足于网格的具体应用。在全面介绍网格计算及相关技术基 础上，将网格计算的应用向具体行业渗透。力求对应用需求所驱动的网格计算技 术做实践性尝试。 ( 2 ) 对工程运算领域而言，将网格计算技术运用于有限元并行计算问题的解 决，通过网格计算环境实现有限元的并行处理，是工程计算领域一种新的思路和 解决方案，有利于提高空闲计算设备的利用率。由于网格计算本身的特点，在网 格这种基础设施的支撑下，达到网格技术、计算模式的集成和广泛融合。同时它 对于建立一种全新的稳定高效的工程计算模式具有引导作用。 ( 3 1 网格计算本身蕴藏着巨大的商机，将引起一场大的产业应用。近来，各种 工程的计算量越来越大，基于网格计算思想的并行处理模式的提出，实现资源和 信息共享，无疑是一种比较理想的方式，而且这种共享可建立在当前日益发展的 i n t e r n e t 软硬件和w e b 技术的基础上，在结合了网格计算技术之后工程计算将向新 的领域发展。 f 4 ) 论文中建立的基于网格计算的有限元并行计算环境在结构上是灵活和易 于伸缩的，为实现远程资源共享和协作试验提供了良好的基础设施。在此基础上， 有限元计算应用网格可能与其他行业的网格在很大程度上达到资源跨地域、跨领 域、跨行业的全面集成和共享。 湖北工业大学硕士学位论文 1 2 国内外研究现状 1 2 1 网格计算应用研究简介 从2 0 世纪9 0 年代初至今，得益于超大规模集成电路等微电子技术的革新， 商用微处理器的速度每1 8 个月翻一番，存储密度每1 2 个月翻一番，网络速度每9 个月翻一番。虽然计算机的性能以如此快的速度增长，却仍远远满足不了应用的 需求。过去人们将问题的解决确定在建立高性能的超级计算机。但是超级计算机 的性价比比较低，其应用面受到很大的局限。1 9 9 5 年b e r k e l e y 发表了“ac a s ef o r n o w ”标志着集群的兴起。在相当长的时间内，高性能集群技术在高性能计算领 域占有非常大的份额，但是集群的规模不可能无限制地扩大，其性能达不到线性 增长的需求。p 2 p 计算突破了集群计算地域的限制，虽然集合了大量的计算能力， 具有计算能力超强，成本低等的特点，但由于处理单元的相对独立性以及计算能 力的不稳定性，也未形成广泛的应用。目前高性能计算有关的科学合作领域，正 在涌现出另一个具有划时代的新生事物一一网格计算( g r i dc o m p u t i n g ) ，它将掀起 互联网继i n t e r a c t 、w e b 之后的第三次浪潮，其实质就是要将万维网( w o r l dw i d e w e b ) 升华为网格( g r e a tg l o b a lg r i d ) 。 高性能计算的应用需求使计算能力不可能在单一计算机上获得，因此须通过 构建“网络虚拟超级计算机”或“元计算机”来获得超强的计算能力。网格计算( g r i d 咖l n i n g ) 通过网络连接地理上分布的各类计算机( 包括集群) 、数据库、各类设备 和存储设备等，形成对用户透明的虚拟的高性能计算环境。 网格计算技术是 n t e m e t 应用的最新发展。作为信息产业的新热点，网格计算 是近期解决如高能物理实验、破解基因代码等数据量极大的科学工程计算问题的 有效途径。中科院计算所所长李国杰院士认为，我国“8 6 3 ”计划已经启动了中国 网格技术的研究，着手建立中国的国家高性能计算环境和国家信息网格分布。重 点是开发一个“网格计算协议”( g r i dc o m p u t i n gp r o t o c 0 1 ) ，它应用于网络资源的连 接们。 建立大规模的网格系统的关键技术是网格系统软件，特别是网格操作系统， 其核心技术包括网格资源的管理、信息优化使用技术、网格中作业调度技术、网 格中的并行实现和网络安全技术等。目前已有成功的网格实现平台有美国的“国 家技术网格州t g ) ”、“分布万亿次级计算设施( d t f ) ”、美国宇航局的i d g 、美国能 湖北工业大学硕士学位论文 源部的a s c ig r i d 以及欧盟的d a t ag r i d 等。1 9 9 9 年的s e t i ho m e 项目是网格 计算的一个成功典范。i b m 正在构筑一项名为“g r i dc o m p u t i n g ”的计划，旨在通 过因特网向每一台个人电脑提供超级的处理能力；s u n 则推出s u n 【g r i d e n g i n e 企 业版；日本政府将开发比世界最快的超级计算机还要快1 0 倍的网格计算机( g r i d c o m p u t e r ) ，定名为“国家研究网格计划”。网格计算成为近年网络市场发展的热点。 知名公司对网格技术研究的投入，国家对网格研究的重点扶持，使得国内外对网 格的研究的应用提到了一个新的高度，出现了众多的行业网格。 f o r b e s a s a p 预测网格技术的应用在近年将达到高峰，并带来因特网的新 生。如果网格技术船促使市场按预期的1 7 年增长率持续成长的话，那么在2 0 2 0 年将会形成一个年产值2 0 万亿美元的大产业。我国也已开展了以中国科学院和清 华大学牵头的“国家高性能计算环境”和“先进计算基础设施北京上海试点工程” 两个项目，国家计算网格应用前景十分广阔。网格将成为生物工程、气候模拟、 能源探索、航空航天、数字地球等重要科技领域的重要工具。计算发展的主流方 向即是集群化向网格化，这也是i n t e m e t 的发展方向“。 1 2 2 网格计算技术在有限元并行计算领域的应用 网格计算以其异构环境下实现可扩展的广泛的资源共享越来越受到专家、学 者甚至社会各界的极大关注。作为一种面向问题和应用的技术，其发展仍然依赖 于其他行业的专业网格来扩充和推动。随着w e bs e r v i c e s 等的发展，网格计算技 术正在与其它相关技术进行融合。就目前而言，对网格技术的许多研究工作仍处 在不断摸索的阶段。 并行计算是当前提高工程运算速度的重要方法。其中的有限元并行计算算法 复杂，计算量较大。自从7 0 年代初期弗行机问世以来，不少结构分析家及计算数 学家致力于有限元分析的并行计算，开辟了并行计算力学这一新的研究领域。除 对传统的有限元分析寻求向量化与并行化并在各种向量机与并行机系统上实现 外，还在有限元分析和设计过程中的各个层次探索提高并行度的各种策略和技术。 研究的内容主要涉及到： ( 1 ) 有限元并行计算( 或称为刚度矩阵并行计算) ： ( 2 ) 线性代数方程组并行求解： ( 3 ) 代数特征值的并行计算( 特别是广义特征值问题的并行计算) ； 4 湖北工业大学硕士学位论文 ( 4 ) 直接积分的并行计算以及带宽优化等； 由于并行计算的困难( 如任务分配的困难：现有算法语言的限制；现有串行处 理方式的约束；通讯开销与计算开销间的平衡等等) ，国内讨论有限元并行计算的 并行算法理论和并行算法设计与分析的居多，研究并行算法的实现并解决实际问 题的不多。本文结合了网格计算技术，从结构应力有限元分析入手，构建有限元 并行计算的网格环境来实现具体的并行计算算法。 1 3 本论文研究工作 论文通过应甩嗣格计算技术，从软硬件两方面来实现有限元法并行计算，旨 在高性能工程运算方面作一些尝试。论文通过解决网格环境在w m d o w s 2 0 0 0 操作 系统上的多机部署和环境测试，然后编制并行计算的有限元程序，解决计算的并 行化、分布式和数据资源的共享，最后在网格环境中实现有限元法并行计算。 全文研究的重点是： ( 1 ) 有限元并行计算的算法设计； ( 2 ) 基于网格计算的并行计算环境的安装配置及该环境中的程序设计； ( 3 ) 在网格环境中实现有限元并行计算。 第一章为本文绪论，介绍课题来源及其意义，课题的国内外研究现状和存在 的不足，接着介绍了课题期间主要的研究工作。 第二章介绍有限元法并行计算方法。首先简单介绍传统有限元法的一般原理 和有限元计算过程，然后探讨有限元计算方法的并行实现，最后对有限元并彳亍计 算算法做了研究，并结合具体算法讨论有限元法并行计算实现的方法。 第三章简单介绍网格计算技术以及网格计算环境。首先介绍网格计算的产生， 网格计算的概念，网格计算研究的内容，相关技术，网格系统体系结构，网格计 算的应用等。最后介绍了网格计算环境g l o b u st o o l k i t 。 第四章介绍网格计算环境的配置与编程。本文中的网格计算环境基于g l o b u s t o o l k i t 。本章介绍g l o b u s t o o l k i t 的安装和配置，g l o b u s 的系统架构以及在g l o b u s 中如何进行程序设计。 第五章介绍了如何在网格计算环境中实现有限元并行计算。本文开发了一个 基于网格计算环境的分布式的有限元并行计算( d i s t r i b u t e dp a r a l l df i n i t ee l e m e n t m e t h o d ) 的环境原型d p f e m ，介绍了d p f e m 的设计过程以及相关数值计算结果， 湖北工业大学硕士学位论文 得出相关结论。并且将网格计算环境中的并行计算和其他环境中的并行计算作了 比较。 第六章是全文总结，介绍论文已经完成的工作和存在的不足之处，展望将要 进一步研究的内容。 本文的创新之处在于； ( 1 ) 研究了有限元并行计算算法，即子结构法和并行预处理共轭梯度法； ( 2 ) 在w i n d o w s 平台部署的网格计算环境中实现了有限元并行计算。 目前国内外对网格计算技术的理论研究及应用还处在起步阶段，该技术的标 准化、实甩化、产业化的过程还需要更多的投入和不断的理论、应用实践来进一 步完善，本论文的研究也仅是在目前网格计算技术还不太成熟的情况做的一点探 索，对于此方面的研究和应用以及存在的困难还有待进一步深入探讨。 湖北工业大学硕士学位论文 第2 章有限元并行计算方法 本章首先简单介绍传统有限元法的一般原理和有限元计算过程，然后探讨有 限元计算方法的并行实现，最后对有限元并行计算算法做了研究，并结合具体算 法讨论有限元法并行计算实现的方法。 2 1 有限元法介绍 2 1 1 有限元法 有限元法是一种数值计算方法。与差分方法不同，它不是直接就定解问题原 有形式进行离散化求数值解，而是根据变分原理先将定解问题变换为变分问题， 然后利用函数分片多项式插值方法进行离散化求数值解。在几何和物理条件比较 复杂的问题中，有限元方法比差分方法有更广泛的适应性。因此它可广泛应用于 各种微分方程描述的场问题的求解。例如，对于不太规则的定解区域，差分方法 往往会出现困难，有限元方法则显得相当灵活。 有限元法的形成可以追溯到2 0 世纪5 0 年代，来源于固体力学中矩阵结构法 的发展和工程师对结构相似性的直觉判断从固体力学的角度来看，桁架结构 等标准离散系统与人为分割成有限个分区后的连续系统在结构上存在相似性。有 限单元法与结构分析的矩阵表示法密切相关，这种表示方法( 矩阵表示法) 在1 9 5 2 年由l a n g e f o r s 提出“。1 9 5 6 年他们在纽约举行的航空学会年会上介绍了一种新 的计算方法，将矩阵位移法推广到求解平面应力问题。他们把结构划分成一个个 三角形和矩形的“单元”，利用单元中近似位移函数，求得单元节点力与节点位移关 系的单元刚度矩阵“。1 9 5 4 1 9 5 5 年，j h a r g y r i s 在航空工程杂志上发表了一系列 能量原理和结构分析的论文“。2 0 世纪6 0 年代以后，有限元方法取得了迅速进 展。 应用方面，有限元方法侧重于定态问题( 椭圆型方程) ，例如，在固体力学中， 有限元方法已趋完善，国际上已有许多标准有限元计算程序( 如a n s y s ) 用于作结 构分析。有限元方法也应用于依赖时间的问题，例如流体力学中提出的抛物型方 程与双曲型方程的初边值问题。除了应用于结构分析，有限元方法还能解决归结 为场问题的工程问题。有限元法的巨大发展，为工程设计和优化提供了有力的工 具。 7 湖北工业大学硕士学位论文 2 1 2 传统有限元法计算过程 有限元法求解一般步骤如图2 1 所示： 图2 1 有限元法求解一般步骤 ( 1 ) 先将求解域离散为有限个单元，单元与单元只在节点相互连接；即原始 连续求解域用有限个单元的集合近似代替； ( 2 ) 对每个单元选择一个简单的场函数近似表示真实场函数在其上的分布规 律，该简单函数可由单元节点上物理量来表示，通常称为插值函数或位移函数； ( 3 ) 把单元外力( 体力、温度等) 转换到节点上作为节点等效力； ( 4 ) 基于问翻甥翻功程，建立单元节点的平衡方程( b 阙蛆，程) ： ( 5 ) 借助于矩阵表示，把所有单元的刚度方程组合成整体的网8 度方程，这是 一组以节点物理量为未知量的线形方程组，引入边界条件求解该方程组即可。 图2 2 平面应力问题的力学模型及有限元模型类比 对于一个简单的平面应力问题，图2 2 对它的力学模型和有限元模型作了对 湖北工业大学硕士学位论文 2 2 有限元计算方法的并行实现 2 2 1 并行计算 并行计算是提高计算机系统计算速度和处理能力的种有效手段。它的基本 思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分， 各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、 含有多个处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构 成的集群“。优点是具有巨大的数值计算和数据处理能力，能够被广泛地应用于 多个领域。 并行计算基于一个简单的想法：n 台计算机应该能够提供n 倍的计算能力，不 论当前计算机的速度如何，都可以期望被求解的问题将在1 n 的时间内完成。显 然这只是一个理想的情况，因为被求解的问题在通常情况下都不可能被分解为完 全独立的各个部分，而是需要进行必要的数据交换和同步。尽管如此，并行计算 仍然可以使整个计算机系统的性能得到实质性的改进，而改进的程度取决于欲求 解问题自身的并行程度。 2 2 2 有限元法并行计算方法概述 归纳起来，对于给定的有限元矩阵方程定解问题，有限元方法的计算可以分 为两个阶段：( 1 惮元局部级的计算；圆韧彩移稻麴鲍哥暾 首先，有限元法的主要计算量集中在有限元方程组的求解。传统的求解方法 是采用消去法，要求在解有限元方程组之前形成总体刚度矩阵，或采用波前法， 此时要求在求解过程中逐步组集总体刚度矩阵。但是，由于有限元的刚度矩阵是 带状矩阵，并且在其带状内存在大量零元素，应用消去法解有限元方程组时，会 出现大量“填充”，即在消去去过程中，一些带状内的零元素变成非零元素。因此 应用消去法的一个缺点是必须存储带状内的所有元素( 若考虑总体刚度矩阵的对称 性，存储量可以减半) ，存储量很大。消去法的另一个缺点是，一般需在形成总体 刚度矩阵之后才能求解有限元方程。而应用迭代法解有限元方程组，则一般不会 产生“填充”，只要精心编写程序，也不用组集总体刚度矩阵。 关于有限元方程组的并行求解，可根据有限元方程组的具体情况，选用不同 的方法。应该指出，对于由线性结构动力分析问题或者考虑多种不同载荷工况时 9 湖北工业大学硕士学位论文 的静力分析问题导出的有限元方程组时，用直接法求解，消元和矩阵分解只要进 行一次就可以得到各离散时间步上的数值解或者不同载荷工况下的数值解，这时 用直接法非常省效，并因此发展出了等带宽和变带宽存储格式下矩阵l d l 并行分 解算法、对称带状线性方程组求解的并行算法等。但是，对于非线性结构动力分 析问题、结构的几何形状极不规则的结构分析问题或有限元网格节点编号不当等 而导致的有限元方程组，其系数矩阵的非零元素的分布较为紊乱，无一定规律可 循。这时用直接法就会很不方便，计算量和存储量很大，需采用迭代法求解。然 而，采用经典的迭代法，如共扼梯度法等，则睡b 于有限元方程组的系数矩阵虽然 对称，但条件数往往不好，丽不能较快地收敛到问题的解。所以预处理迭代法是 目前应用于解有限元方程维行之有效的方法 下面，我们筒述一下单元局部级计算的并行与向量实现基本问题。单元局部 组的计算包括：形状函数的确定及其局部导数的计算；局部坐标与总体坐标之间 变换利用g a u s s 求积公式计算单元刚度矩阵和单元载荷向量的计算，单元刚度矩 阵组集成总体刚度矩阵以及单元载荷向量组集成总体载荷向量等。 各种不同的并行机与向量机，由于处理机数日的不同，处理机之间连接方式 不同以及向量机、巨型计算机之间存在着基本的差别等，设计有限元的并行算法 必须考虑上述因素。原则上，在有限元的不同计算阶段要求不同韵并行与向量计 算机结构，以获得最优的使用效率。 很显然，各单元的计算是相互独立的，单元局部组的计算具有直观的并行性。 以计算单元刚度矩阵为例，假定考虑的是二维方程用8 点的矩形单元求解，则计 算单元刚度矩阵应使用9 点g a u s s 求积公式在中型计算机上，各单元刚度矩阵是 依次计算的，通过对遍及所有单元的循环来实现，各单元内部，通过循环9 次实 现向量求积。 在处理机阵列上，假设处理机数目与单元数目相同，交换串行计算时的二重 嵌套循环的顺序便可实现并行计算。即每次考虑一个g a u s s 点的计算，所有单元 的计算可同时进行，循环9 次后便可求得各单元的刚度矩阵。 若处理机的数目小于单元的数目，则可对求解区域分块，各分块予区域上单 元的数目与处理机数目匹配。 有限元计算时通常要考虑关联节点的信息。利用处理机阵列计算单元刚度 矩阵的一个优点是，各处理机与之最邻近的4 个处理机之间的通信可以方便地实 现，而关联节点的信息保存在4 个邻近的处理机上。 1 0 湖北工业大学硕士学位论文 一般地，由于各单元刚度矩阵的计算仅仅与本单元的信息有关而不涉及其它 任何单元，完全并行。当然，根据具体情况，可采用不同的并行计算方案，如： ( 1 ) 每次同时计算一个单元刚度矩阵的多个位置处的元素； ( 2 ) 每次同时计算多个单元刚度炬阵在同一位置处的元素： ( 3 ) 每次同时计算多个单元刚度矩阵在多个位置处的元素。 对于单元刚度矩阵的向量计算，主要是向量长度的选取及向量的具体组织问 题，由于任何一个向量算法都要求尽可能地组织长向量的向量运算。注意到上述 第( 2 ) 、( 3 ) 方案每次同时计算出的元素均较第( 1 ) 张方案要多，所以常采用第( 2 ) 、( 3 ) 方案组织向量计算。 总体刚度短阵是将所有单元刚度矩阵按照其节点编号依据“对号入座”的原 则组集而成的，由于相邻单元之间存在共同节点，所以组集总体刚度矩阵不能像 单元刚度矩阵那样完全并行，即所有单元的单元刚度矩阵不可能向总体刚度矩阵 中实现一次性叠加，否则就有可能在计算过程中发生存取冲突和计算错误。 进一步分析可知，组集总体刚度矩阵最大的并行只能在于每次同对叠加互相 没有共同节点的多个单元刚度矩阵的所有元素，或者每次同时叠加所有单元剐度 矩阵中那些不致于导致存取冲突和计算结果错误，能保证总体刚度短阵各位置处 的元素在每次的同时计算中只被一个单元所影晦的所有元素。当然，根据具体情 况，在实际计算过程中也可采用不同的方案。如： ( 1 ) 每次同时叠加一个单元刚度矩阵多个位置处的元素； ( 2 ) 每次同时叠加多个单元剐度矩阵在同一位置处的元素： ( 3 ) 每次同时登加多个单元刚度矩阵在多个位置处的元素。 值得指出的是，组集总体刚度矩阵与总体刚度矩阵的存储格式，及解有限元 方程组所采用的并行与向量计算方案密切相关。一般地，对一个大型线性结构分 析问题，其相应的总体刚度矩阵是对称稀疏的。进一步，如果有限元网格节点编 号遵循某种适当的规则，它还是带状的( 等带宽或变带宽) 。目前常用的存储格式是 等带宽格式和变糯黻 关于约束条件的并行处理，我们知道，根据有限元法算出的总体刚度矩阵还 不能直接用于对总体平衡方程组的求解。因为，这时的总体刚度矩阵往往是半正 定的奇异矩阵，并且这时的总体平衡方程组还不满足给定的位移边界条件，必须 消除刚体位移的影响，即修正总体平衡方程组来满足位移边界条件，才能进行求 解。修正总体平衡方程组是通过加入边界条件的方法来解决的。目前加入边界条 湖北工业大学硕士学位论文 - _ - _ _ _ - _ 一i _ _ _ - - - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ - _ _ _ - - _ _ _ _ _ 件的方法通常有倒换方程式法、降阶删除法和置大数法。其中置大数法最易并行 实现，是目前许多大型计算机程序中所采用的方法。 有限元素法是研究结构分析问题的有效方法。应用有限元素法研究结构静力 分析问题，其目的是形成刚度矩阵【刚与载荷 ， ；其次是解下列线性代数方程组： 【刚似t ， ( 2 1 ) 式中 x 表位移。随后，计算有关物理量，如应力等。 对于结构动力分析问题，其前期工作是形成刚度矩阵1 ，质量矩阵f m 】，阻 尼矩阵【c 】，随后解下列基本方程： 【l f 】 q + f c 】协+ 畔】佃) 怛o ) )( 2 2 ) ； 式中佃 表位移，怛 表示载荷，初始条件为 g ( 0 ) ) ，也( o ) ) 。 处理基本方程( 2 有两种不同的途径。途径之一是直接积分法，途径之二是作 适当变换使问题转化为下列广义特征值问题， 【4 】扛 ；饥别仁( 2 3 ) 综上所述，可见传统的有限元结构分析并行计算的数学问题主要包括有： ( 1 ) 有限元并行计算( 或称剐度阵并行计算) ； ( 2 ) 线代数方程组并行求解； ( 3 ) 代数特征值的并行计算( 特别是广义特征值问题并行计算) ； ( 4 ) 壹接积分的并行算法等； ( 5 ) 带宽优化等问题。 应用串行计算机处理有限元问题，国内外已有不少专著及程序包。自从7 0 年 代初期并行机问世以来，不少结构分析家及计算数学家致力于有限元分析的并行 计算，开辟了并行计算力学这一新的研究领域。除对传统的有限元分析寻求向量 化与并行化并在各种向量机与并行机系统上实现外，还在有限元分析和设计过程 的各个层次探索提高并行度的各种策略和技术。在美国，n a s a 的工作居于领先 地位，值得一提的是a k n o o r ，在a k n o o r l 9 8 7 年发表的文章“计算结构 力学的进展与动向”与1 9 8 8 年发表的文章“有限元结构分析的并行处理”中全面 地论述了这一领域的发展现状 2 5 2 6 】。在g c a r e ，1 9 8 5 年发表的文章【2 7 】中论述 了开发有限元分析各个层次并行性的有关技术。这三篇文章是本领域具有指导性 1 2 湖北工业大学硕士学位论文 的文章，值得研究。此外，自从1 9 8 3 年以来a k n o or 主编的四部书，也很有 参考价值 2 8 - 3 。 2 3 有限元并行计算算法 一般来讲，有限元法处理结构分析问题的基本过程大致可以分为以下几个相 继的阶段： ( 1 ) 数据准备阶段，包括将一个受力连续体结构“离散化”，剖分成一定数量 的有限小的单元，以及生成各单元、结点的信息和某些必要的信息处理； ( 2 ) 单元分析阶段，包括单元刚度矩阵、单元荷载列阵的计算； ( 3 ) 单元蒇欧自$ 拗段，包括蒯靴蓟酃辅鸲疆辞增荷载列嗡慨 ( 4 ) 约束处理阶段。即根据结构的约束信息对系统方程组进行适当修改： ( 5 ) 系统方程组求解阶段，由此得到全部未知的结点位移； ( 6 ) 后处理阶段，包括各单元的应力应变计算等。 通常，( 1 ) 、( 4 ) 、( 6 ) 阶段所费的时间在整个结构分析中所占的比例是极小的。 相反，( 2 ) 、( 3 ) 、( 5 ) 阶段则是有限元结构分析的关键，占去绝大部分的时间。并 行有限元提高处理速度的关键就是提高( 2 ) 、( 3 ) 、( 5 ) 阶段的并行度。有限元分析 的并行方法，包括以下两个方面的内容，一是子域( 子结构) 并行分析方法；二 是基于一般的有限元体系，主要是对求解方程组耗时太多的解方程组部分采用并 行分析方法。前者是挖掘了力学问题自身的并行性，而后者主要考虑了求解方程 组算法的并行性。当然，这两种方法也可耦合使用，这样可使有限元分析最大限 度地并行化，这是目前研究最多、使用最广的一种方法。 对于复杂结构的有限元分析，大部分机时用于求解方程组。因此实旌并行求 解方程组，有利于提高并行效率。线性方法组的并行求解方法有直接法和迭代法 两种，这两种方法各自优缺点。有限元并行分析中采用最多的方法是耦合使用上 述两种方法，将结构划分成若干个子结构，并行形成各子结构的单元刚度矩阵， 再并行对各子结构刚度矩阵进行组装和静凝聚，然后采用预处理共轭梯度法( p c g ) 并行求解界面方程，尔后并行回代求各子结构的内点位移和计算应变、应力。以 往的有限元并行计算大都在巨型并行机上进行的。 在有限元分析中，对结构应力的计算是十分费时的。因此，在并行算法发展 起来后，把并行分析应用于结构应力分析，引起了人们的极大重视。 湖北工业大学硕士学位论文 这里采用子结构并行分析法的静力弹性有限元并行算法，力求实现最大程度 的并行。 2 3 、1 子结构法与并行预处理共轭梯度法 子结构法，就是把有限元求解区域划分为若干个子结构，分别形成和组装各 子结构的刚度矩阵和荷载列阵，通过静凝聚形成界面整体方程，求解界面整体方 程得到界面结点位移，再回代求得各子结构内点位移。 子结构并行分析法，就是并行形成和组装各子结构的剐度矩阵和荷载列阵， 并行进行各子结构的静凝聚，然后并行求解界面方程得界面位移，己知界面结点 位移后并行回代得备予结构内点位移。 预处理共轭梯度法，是解大规模方程组的一个常用的有效的迭代法，它具有 迭代法的一般都有的两个优点，需要机器存贮量少和程序编制简单。同时只要矩 阵不是严格病态，则通过数次迭代就可以得到满意的结果。采用预处理共轭梯度 法求解界面方程，可避免组装界面方程的整体刚度矩阵和荷载列阵。 2 3 2 线性方程组的并行预处理共轭梯度法 与通常的直接法相比，利用p c g 法可以不需要组装系统总体刚度矩阵，有利 于大规模问题的求解对于大量处理器的并行计算，p e g 法可在单元一级实现。并 行计算中，引入单元块结构。单元块是多个单元的集合。p c g 法在单元块上实现对， 只需要组装单元块的刚度矩阵，这是完全并行化的。迭代过程中，大量计算也是 在单元块内进行，处理器问通讯是少量的。 线性方程组并行直接解法，其优点是算法稳定性好、精度高；其缺点是在并 行求解方程过程中，由于调用系统功能实现同步，会耗费不必要的进程等待信息 和传送信息的时间，导致并行效率下降，另外直接解法必须形成完整的系数矩阵， 对有限元方程而言，就是必须形成结构的整体刚度矩阵。线性方程组的另一类并 行解法是并行迭代解法，并行迭代解法的主要优点是：可避免或减少同步控制， 不必形成完整的整体刚度矩阵；主要缺点是：对算法的稳定性和收敛速度要求较 高，且不能预测计算时间。线性方程组并行迭代解法中使用较普遍的是预处理共 轭梯度法( p e g ) 。下面研究一种适合于分布式系统的用p c g 法求解线性方程组的 并行算法。 1 4 湖北工业大学硕士学位论文 ( 1 ) 串行p c g 算法 对于方程【4 】扛 - b ) 给 x 卜一个初值 习。，计算 ，) 。一 6 ) 一m w 。 协。一 c r 厂) 。 纠。一仇 f o r k - 0 ，1 ，2 ，如 | i l ) m 一 p ) 。 q 一 r 蔓扛 。 q 一 p k 矗k a 旦 x ) 。+ 。_ 工) | + 口 p ) 。 i fl x k + l - - “忭st h e nr e t u r n r ) 。“_ r ) 。一口 ) 。+ ， t 。- 【c 4 ，) 。 - 一a 似。r 。t ) 。 y 。量 a p ) 。+ ，t i p 。+ t ) 。+ 。 e n d f o r 其中，为容许收敛误差， c 】为预处理矩阵，选取 c 的方法有很多，要根 据 的情况选择不同的方法。 ( 2 ) 并行p c g 算法 下面介绍一种适用于有限元并行分析的方程组的并行p c g 算法。 设系数矩阵f 4 】由p 个子矩阵m 5 ) 】o 。1 ，p ) 组成，向量 6 ) 为p 个子向量 湖北工业大学硕士学位论文 “) o 。1 ，p ) 之和，预处理矩阵 c 】由p 个子矩阵【c 扛】o ，1 ，p ) 组成。将阻m 】、 伪。) 存储在第s 台处理机上。m p 】、p 。) 分别为有限元分析中第s 个子结构的劲 度矩阵和载荷矩阵，缸 为第s 个子结构的结点位移。 了表示局部通讯求和，了表示全局通讯求和。 篙 “ 在分布式系统上，并行p c g 算法如下2 l ： 给缸。) 一个初值仁o h ，计算 【c 卜【c n 】“c m 】 黑 ( m 为与第s 个子矩阵相邻的子矩阵数) r oip o 卜m 扣】缸h f o ) oi 【c o 】1 ，) o h 。三 。+ h d 。 oi 如5 o f o r k 一0 ，l 2 ，d o 协5 h “。阻o 】t p t a ? - ，磙0