（计算机应用技术专业论文）jifex软件有限元分析并行化.pdf

大连理工大学硕士学位论文 摘要 随着现代力学、计算数学和计算机技术等学科的发展，有限元分析软件作为一个具 有巩固理论基础和广泛应用效力的数值分析工具，为解决复杂的工程分析计算问题提供 了有效帮助，在国民经济建设和科学技术发展中发挥了重大的作用。由大连理工大学工 程力学系和工业装备结构分析国家重点实验室共同研制开发的具有自主版权的有限元 分析软件j i f e x 软件就是其中之一。但是，由于受计算机c p u 计算速度的限制以及有 限存储空间的制约，使用传统的有限元分析软件分析超大规模的工程问题，往往会造成 计算时间过于漫长，甚至无法进行分析计算。这一点己成为传统有限元分析软件在工程 实践中得到更深层次应用的瓶颈问题之一。 近年来，由于高速网络的迅猛发展，使得机群并行计算成了当前国际上并行计算的 一个主要方向。机群并行计算具有巨大的计算潜能、良好的性能价格比和可扩展性，以 及灵活的体系结构等优点。将机群技术与传统有限元计算技术相结合，有效提高分析速 度，解决超大型有限元分析时间过长的问题，是当前国内外有限元研究与应用领域中最 引人注目的前沿课题之一。 本文对并行计算和消息传递接口m p i 进行了简单介绍，研究了基于分布式网络并行 计算环境的有限元分布式并行算法。经过分析之后对j e x 软件有限元分析部分采用了 方程组并行直接解法，该解法稳定性好、精度高、便于对现存的串行算法程序进行修改。 在增加并行求解模块的基础上保留了j i f e x 软件的原有接口。 本文设计并实现了一维变带宽存储矩阵的l d l o 分解算法和三角形方程组的并行解 法。由于大型结构刚度矩阵比较大，文中同时采用了矩阵的分块求解，将矩阵分块与并 行求解算法有效结合起来，达到了节约内存的效果。 最后，在组建的计算机机群上对并行化的j 既x 软件进行了实验测试。数值实验结 果表明，本文所实现的算法有很好的加速比和效率，经过并行化的f e x 软件有限元分 析速度明显加快。 关键词：j i f e x ；有限元分析；并行计算；消息传递接口 大连理工大学硕士学位论文 p a r a l l e l i z i n go ff i l l i t ee l e m e n ta n a l y s i si nj i f e xs o f h v a r e a b s t r a c t w l t h 廿1 ed e v e l o p m e n to im o d e mm e c h a 董1 i c s ，c o m p u 虹n gm a t l l e m a 虹c sa n dc o m p m e r t e c h n o l o g y ，a sm l i n e r i c a l 删y s i st o o lw h i c hh a ：v es o l i d 也e o r c 虹c a lf o u n d a t i o na n dw i d e a p p l i c a t i o np o w e r 】f i n i t ee l e m e n ta n a l y s i s ( f e a ) s o f h v a r eh e l pal o ti ns o l v i n gc o m p l e x e n g i n e e r i n gp m b l e m sa 1 1 dp i a ya ni m p o n a mr 0 1 ei i lt 1 1 en a t i o n a 王e c o n o m yb u i l d i n ga 1 1 dt 1 1 e d e v e l o p n l e n to fs c i e n c e o n eo f 仕【e mi st 1 1 en f 既s o f 时a r e ，w h j c hi sj o i n t l yd e v e l o p e db y d e p a n m e n tm e c h a 芏l i e s ，d a l i a nu 工l i v e r s 毋o ft e c h n o l o g ya n d 吐l es t a t ek e yl a b o r a t o r yo f s 批t u r a la n a l y s i sf o ri n d u s 砸a le 删p m c m h o w e v e r ，也ec a i c l l l a t i o ns p e e do fc p ua n d 血e 1 i m i t e ds t o r a g es p a c er e s 仃i c tt h eu s a g eo f 仃a d i t i o n a lf e as o f h v a r ef o r 恤e 趾a l y s i so f u l t r a l a r g e s c a l ee n g i n e e r i i l gp m b l e m s i to f t e nr e s u n s i l lt 0 01 0 n gc a l c u l a t i o nt i i i l e 舡1 d s o m e t i i i l e si tm a yb e c o m e 曲p o s s i b l e t h i sh a sb e c o m en l eb o t e n e c ko f 印p l y i n gt r a d i t i o n a l f e as o 脚a r et od e e p e re n g i n e “n gp r a c t i c e s i nr e c e n ty e a r s ，d u et ot h er a p i dd e v e l o p m e n to fl l i g hs p e e dn e t 、v o r k s ，c l u s t e rp 锄1 1 e l c o m p u t i n gh a sb e e nam 面o ri m e m a t i o n a lp a r a l l c l i s md i r e c t i o n c l u s 僦h a se n o 衄o u s p o t e n t i a jc a l c u l a t i o n ，ag o o dp e r f b 啪a n c e c o s tf a t i oa n dm en e x i b l ea r c m t e c t l l r e c o m b i l l a t i o n o fc l u s t e ra n df e ac a i li n c r e a s ea n a l y s i ss p e e da n dd e c r e a s e 廿1 et i m eo ft h ea n a l y s i so f u 1 仃a l a r g e - s c a i ee n 百n e e 血gp r o b i e m s ni so n eo f 也em o s tn o t a b l ef o n a r dt o p i c si nf e a a i l o v e rt h ew o d d i nt h i sp a p e r ，p a r a l l e lc o m p u t i n ga f l dm p ia r ei n 拄o d u c e da n dd i s 拄i b u t e df e ap a 融l e l a l g o r i t h m sb a s e do nd i s 廿i b u t e dn e 帆r o r k sa r es t u d i e d a 血e ras e r i e so fa n a l y s i s ，e q u a t i o n p a r a l l e ld i r e c ta l g o r i t h ，w h i c hl l a sg o o ds t a b i l i 够，h i 曲p r e c i s ea i l d 1 ea d v a n t a g eo fe a s i l y m o d i 母i n gt h ee x i s t e ds e r i a lp m g r 锄s ，i si r n p l e m e n t e dt of e ap a r to fj i f e x t h eo r i 百r l a l i n t e r f a c e so f j i f e xa r ep r e s e r v e do nt h eb a s eo f a d d i l l gp a r a l l e l i s mm o d u l e s p a r a i l e ll d l ld e c o n l p o s 衔o na l g o r i t h ma 1 1 d 仃i a n g i l l a re q u a t i o ns y s t e ms 0 1 m i o no no n e d i m e n s i o nv a r i a b l eb a n d 、i d mm a 灯i ) ( a r ed e s i g n e da n di m p l e m e n t e d b e c a u s e 也es t i f 血e s s m a 砸xo fl a r g es c a l es t r u c t l l r ei sh u g e ，m em a t r i xi sd i v i d c di t os m a l lb l o c k s t h ee 筒c i e m c o m b i n a t i o n o f p a r a l l e l i s ma 工1 d b l o c k m e t h o d m a k e t l l e l l s a g eo f m 锄o r yr e d u c e d f i t l “l y ，也ep a r a l l e h s mj i f e xs o f h 缸ei st e s t e do np cc l u s t e r s t h en u m e r k a lr c s u l t s s h o wt h a tt 1 1 ea l g o r i t h m sh a v e9 0 0 ds p e e d u pr a d i oa n de 伍c i e n c ya 1 1 dt h ef e as p e e do f j i f e xi so b v i o u s l ye x p e d i t e d k e yw o r d s ：j i f e x ；f i n i t ee i e m e n ta n a l y s i s ( f e a ) ；p a r a l l e lc o m p u t i n g ；m p i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 作者签名：查盆生日期： 0 0 8 i t b 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教颊完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名夸伟牟 锄始盘墨垒 兰! ! ! 年生月j 羔日 大连理工大学硕士学位论文 1 绪论 1 1 本文研究的内容及目的 本文研究基于分布式网络并行计算环境的有限元分布式并行算法，并采用消息传递 编程模型m p i 把现有的结构有限元分析与优化设计软件系统j i f e x 移植到并行平台上。 通过本文的研究，采用并行化技术，可以大大提高j i f e x 的有限元分析速度，减少 计算时间，使其更适合于工程与实际的需要。经过并行化改造的j i f e x ，将能处理规模 更大的有限元问题，使得对于大型或超大型问题的有限元分析成为可能。并能大大缩短 有限元分析的执行时间，因此具有很强的工程应用价值。 1 2 问题的提出及背景 1 2 1 有限元方法 在工程技术领域内，对于力学问题或其他场问题，人们已经得到了它们应遵循的基 本微分方程和相应的边界条件。但能用解析方法求出精确解的只是方程性质比较简单且 几何边界相当规则的少数问题。因此，人们多年来一直在寻求和发展另一种解决问题的 方法，即数值解法。 在若干近似数值解法中，有限元法是一种具有良好通用性的数值方法。有限元方法 是将连续体离散化的一种近似方法，其理论基础是变分原理、连续体剖分与分片插值技 术。按照这种方法，首先将连续的求解域离散为由一组有限个单元组成的组合体。这样 的组合体能用来模拟和逼近求解域。因为单元本身可以有不同的几何形状，且单元间能 够按各种不同的联结方式组合在一起，所以这个组合体可以模型化几何形状非常复杂的 求解域。有限元法另一重要步骤是利用在每一单元内假设的近似函数来表示求解域上未 知场函数。单元的近似函数通常由未知场函数在各个单元节点上的函数值以及单元插值 函数表达。因此，在一个问题的有限元分析中，未知场函数的节点值就成为新的未知量， 从而使一个连续的无限自由度问题化为离散的有限自由度问题。一经求出这些节点未知 量，就可以利用插值函数确定单元组合体上的场函数。显然，随着单元数目的增加，即 单元尺寸的缩小，解答的近似程度将不断改进。如果单元满足收敛条件，得到的近似解 最后将收敛于精确解。 有限元法的基本思想的提出，可以追溯到c o u r a l l t 在1 9 4 3 年的工作，他第一次尝试 应用定义在三角形区域上的分片连续函数和最小势能原理相结合来求解s t v e n a n t 扭转 问题。但只是到1 9 6 0 年以后，随着电子计算机的广泛应用和发展，有限元的发展速度 j i f l 软件有限元分析并行化 才显著加快。从确定单元特性和建立有限元方程的理论基础和途径来说，人们用的是结 构分析的矩阵法中的直接刚度法，这对我们明确有限元的一些物理概念是很有帮助的， 但是它只能处理一些简单的问题。不久，人们就发现有限元法是基于变分原理的里兹 ( r i t z ) 法的另一种形式。利用变分原理建立有限元方程与经典里兹法的主要区别在于前 者是在单元上而不是在全部求解域上假定近似函数，而且事先不要求满足任何边界条 件，因此可以用来处理很复杂的连续介质问题。从六十年代后期开始，进一步利用加权 残值法来确定单元特性和建立有限元方程。有限元法中所利用的伽辽金( g a i e r k i n ) 法，它 可以用于已经知道问题的控制方程和边界条件，但与之对应的泛函尚未找到或者根本不 存在的情况，因而进一步扩大了有限元的应用领域。 4 0 余年来，有限元法经历了诞生、发展和完善三个时期，到目前为止有限元方法在 算法的通用性方面已达到了很高的程度，不但在功能方面有相当广泛的覆盖面，且可用 于对各种材料组合和几何拓扑结构问题的求解。就有限元方法形态而言，除了最早诞生 的基于极小势能原理的位移有限元模式外，还发展了基于余能原理的应力平衡模式的有 限元法，基于广义势能原理的位移杂交模式有限元法，基于广义余能原理的应力杂交模 式有限元法，基于h w 混合变分原理的混合有限元模式，以及各种各样的特殊的有限 元法形式，如边界有限元法、有限条法、无限元法、有限元线法、有限体积法、离散元 法、半解析有限元法及综合有限元方法等等。这些名目繁多的有限元模式和方法形态的 出现，极大地提高了有限元方法求解各类科学和工程问题的能力和效率，但是在现有的 有限元方法中，最实用、最有效，灵活性最强的仍然是最早发展起来的基于最小势能原 理的位移有限元方法。 有限元法经过发展已由求解弹性力学平面问题扩展到空间问题、板壳问题；由求解 静力平衡问题扩展到求解动力问题、稳定问题；从线性分析扩展到物理、几何和边界的 非线性分析，分析的对象也从固体力学扩展到流体力学、传热学、电磁学等其他领域。 有限元法在工程分析中的作用已从单纯分析和校核发展到设计领域并和计算机辅助设 计紧密结合，成为c a e 工程的重要组成部分。有限元计算结果己成为各类工业产品设 计和性能分析的可靠根据。 随着现代力学、计算数学和计算机技术等学科的发展，有限元方法作为一个具有巩 固理论基础和广泛应用效力的数值分析工具，为解决复杂的工程分析计算问题提供了有 效帮助，在国民经济建设和科学技术发展中发挥了重大的作用f 1 】。大批优秀的计算方法 相继问世，许多通用和专用的分析软件不断投入使用，使得有限元方法已经成为工程数 值分析的有力工具，广泛应用于航天、航空、造船、机械、水利、建筑以及石油化工等 部门“j 。目前功能强大的商品化软件主要有n a s t r a n 、a n s y s 、a b a o u s 、c o s m o s 、 大连理工大学硕士学位论文 a d 玳a 等。 1 2 2j l f e x 软件概况 j 口e x 是由大连理工大学工程力学系工程力学研究所、工业装备结构分析国家重 点实验室研制开发的新一代有限元分析与结构优化设计软件系统。它是在多层子结构有 限元分析程序j i g f e x 、微机有限元分析软件d d j w 、计算机辅助结构优化设计软件 m c a d s 等自主版权软件的基础上发展起来的具有新的前后处理界面的集成化软件系 统。j i g f e x 的发展始于二十世纪七十年代，是中国最早开发出来的有自主版权的大型 通用有限元分析软件，于1 9 8 1 年通过了由中国国家教育部组织的技术鉴定，其后投入 工程应用，在运七飞机、气垫船、直线粒子加速器、重庆长江大桥等许多重要工程结构 设计分析中应用4 j 。 g f e x 自1 9 8 1 年推出第一个版本。在其后十几年时间里，j i g f e x 软件系统在应 用中不断发展，并相继发展了一批分支软件，如微机通用有限元分析软件系统d d j w 、 海洋石油平台设计分析软件d a s o s _ j 、高层建筑结构设计分析软件d a s t a b 、屈曲稳 定分析软件d d 丁t j q 、建筑结构计算机辅助设计软件f c a d 、结构优化设计软件d d d u 、 计算机辅助结构优化设计软件m c a d s 、j i g f e x 的微机系统以及结构与土动力学及渗 流分析软件d n s s 等。这些软件通过了各种形式的技术鉴定，在土木、机械、国防、 航空、航天、车辆、石油、化工等广泛的工业领域中应用，在经济建设和国防建设中发 挥了重要的作用。相应的一批研究应用成果获得了国家与部委级的科技奖励。其中一些 软件也成为商品化软件推广，在中国建立了比较广泛的用户群。j i g f e x 系统及其分支 软件，不仅在国内享有声誉，而且得到了国际同行的认可与重视( 在国外的文献与数据 库中给予介绍和评价) 。 在“七五”与“八五”期间，j i g f e x 软件系统相继被列为国家重点科技攻关项目， 并逐步向集成化软件和c a d c a e c a m 支撑系统方向发展。“七五”攻关的开发成果， 获得机电部科技进步奖和“七五”攻关重大成果奖。在“八五”攻关中开发出了基于造 型的有限元分析与结构优化软件系统j i g f e x 9 5 工作站和微机两种版本，1 9 9 5 年在国家 科委组织的“全国自主版权c a d 支撑软件评测”中获得有限元软件类唯一的一等奖， 1 9 9 6 年又获得两项国家“八五”科技攻关重大科技成果奖，1 9 9 8 年成为8 6 3 c d v 【s 目标 产品发展计划支持项目。 1 9 9 5 年c a d 支撑软件评测以后，程序开发组以m sw i n d o w s 9 ) 洲i n d o w sn t 系统 和c c + + 语言作为新的软件开发平台，以a u t o c a d 软件作为几何模型设计与有限元建 模工具，以奔腾微机为硬件平台，集中进行软件的集成化和商品化开发，全面翻新了有 j 删1 x 软件有限元分析并行化 限元前、后置处理和软件用户界面，并于1 9 9 7 年1 月正式推出了商品化的“结构有限 元分析与优化设计软件系统j e x ，在国内建立了一批用户，在国内c 削d c a e 领域的 影响逐步扩大，在国外也开展合作与市场开发。 j i f e x 是在m sw i n d o w s 9 x ，w i n d o w sn t 和a u t o c a d 软件平台上的商品化软件，该 版本将有限元建模与a u t o c a d 的几何设计集成一体，在全新的图形用户界面下实现了 交互式模型建立和有限元前处理的全自动数据生成。在w i n d o w s 9 ) 【w i i l d o w sn t 平台上 实现了有限元计算与前、后置处理一体化以及实时的计算可视化，在奔腾微机上具有大 规模工程计算能力：有限元模型达到近十万个节点规模的强度分析及接触分析。j e x 软件在分析功能、计算精度、模型化能力与软件实用性方面达到与国外同类软件相当的 水平，并且具有在诸如多功能结构优化设计、多层子结构方法、参变量变分方法接触分 析等方面的特色。 j 巧e x 具有大规模工程计算能力静力、动力、传热、屈曲稳定、非线性分析等， 有限元模型达到十万个节点规模的强度分析及非线性接触分析，具有强有力的结构优化 设计功能。j e x 软件在分析功能、计算精度、模型化能力与软件实用性方面与国外同 类软件接近或者相当，并且具有诸如多功能结构优化设计、多层子结构方法、参变量变 分方法、接触分析等自己的特色。该软件适用于各种工程结构、工业装备和机电产品的 强度、刚度、屈曲稳定性、动力响应、热传导、三维多体接触、弹塑性等力学性能的分 析计算，以及结构性能的优化设计。其应用范围覆盖了航空、航天、机械、车辆、土木、 建筑、水利、电力、石化等各个工业领域，是现代工业设计和高新技术开发的强有力的 软件工具。 1 2 3 有限元并行计算 随着科学技术的发展，人们正在不断建造更为快速的交通工具、更大规模的建筑物、 更大跨度的桥梁、更大功率的发电机组和更为精密的机械设备，其中工程结构分析是关 键技术环节之一，需要有限元分析的问题的规模也越来越大 5 1 。虽然目前计算机发展的 很迅速，但由于受计算机c p u 计算速度的限制以及有限存储空间的制约，使用传统的 有限元分析软件分析这些超大规模的工程问题，往往会造成计算时间过于漫长，甚至无 法进行分析计算。这一点已成为传统有限元分析软件在工程实践中得到更深层次应用的 瓶颈问题之一6 【7 。结构分析中有些问题虽然规模并不大，但计算时间很长f 如结构优化、 动力分析、结构反分析、蠕变等) ：另外，有限元的误差主要由离散化误差和计算中的 舍入误差组成，其中计算舍入误差可通过使用具有大量有效位的现代计算机加以缩小， 而离散化误差只有通过缩小单元尺寸来缩小。缩小单元尺寸，务必会增加计算量和计算 大连理工大学硕士学位论文 时间 8 1 。并行计算机和并行处理技术的出现为有效、省时地对大型或超大型复杂结构的 有限元精细分析提供了可靠的保证。 自从有了并行计算机，就有人开始开展有限元并行化的研究。以前，有限元并行算 法的研究基本上在巨型并行机上进行，由于传统巨型机价格十分昂贵，普及困难，因此 国内在有限元并行计算方面的工作开展得较晚，8 0 年代后期国内才逐渐开展这方面的工 作。近年来，由于高速网络的迅猛发展，使得机群并行计算成了当前国际上并行计算的 一个主要方向。因此，基于网络技术，通过高速信息网络，利用网上计算机资源，建立 网络并行计算平台，是近年来受到科学界和工程界高度重视的计算技术发展方向和当前 在并行处理领域出现的一种新趋势。机群并行计算具有巨大的计算潜能、良好的性能价 格比和可扩展性，以及灵活的体系结构等优点，基本上可满足民用科学技术的计算需要， 因此机群并行计算特别适用于一般的研究部门，这点很适合我国国情。在计算机硬件技 术和网络设备迅速发展的今天，其优势越来越明显1 9 】。g a i s tga 、k o h lja 、p a p a d o p o u l o s pm 等甚至认为m p p ( 大规模并行机) 似乎将有被淘汰的趋势，取而代之的是通过网络计 算平台来完成计算任纠”j 。 近年来，又出现了一批以m p i 、p v m 、e ，r 三s s 为代表的基于消息传递的并行程 序设计平台，极大的方便了用户，保证了程序的可移植性。其中最流行的两个并行计算 环境是p v m 和m p i 【1 1 】 1 ”。两种编程模式的基本环境构架的不同以及不同的库函数使得 它们有不同的优缺点。 p v m 最大的特点是灵活性包括异构平台上的可移植性、交互性和容错功能。 同一个p v m 程序可以在几乎所有的平台上运行，不仅如此，它还可以在多个操作系统 组成的异构系统环境下运行。这使得它可以作为异构集群一个跨平台工具来使用。p v m 还提供其他运行时的灵活性功能，比如动态派生任务，动态改变p 讧运行集群，动态 处理“组”。这使得一个p v m 程序可以植入容错功能和负载平衡，因为它可以侦察到 集群系统的变化，并可以把任务从一个节点移动到另一个节点。p v m 最大的缺点是性 能，因为灵活性的增加，导致了性能的下降。另外，p v m 支持的点到点的通信函数不 如m p i 丰富，例如p v m 不支持完全异步的消息传送。 为了使消息传递系统能被更多的人使用，能在更多的机器上运行，m p i 标准便应运 而生。在吸收了现存许多系统的最突出优点的基础上，学术界和工业界的研究人员共同 设计并制订了该标准。m p i 标准定义了用c 和f o 血a i l 编写消息传递应用程序所用到的 核心库例程的语法和语义，具有很多特点。首先，m p i 提供了一个易移植的编程接口和 一个可靠的通信接口，允许避免内存到内存的拷贝，允许通信重叠，具有良好的通信性 能；其次，它可以在异构系统中透明使用，即能在不同体系结构的处理器上运行；再者， j e ) ( 软件有限元分析并行化 m p i 提供的接口与现存消息传递系统接口( 如p v m ，n x ，e x p r e s s ，p 4 等) 相差不大，却 提供了更大的灵活性，能在更多的平台上运行。m p i 是一个标准，它没有规定具体的实 现细节，这给实现该标准的厂家带来了很大的灵活性，使m p i 可扩展性更好。m p i 提 供模块化的函数调用，函数种类和个数都很多，适用于各种场合。同时对一般的应用程 序来说，通常只用到其中的十几个最常用的库函数，程序本身比用p 讧编写的程序要 直观得多。现在大部分的有限元并行程序都是采用m p i 编写的。 将机群技术与传统有限元计算技术相结合，有效提高分析速度，解决超大型有限元 分析时间过长的问题，是当前国内外有限元研究与应用领域中最引人注目的前沿课题之 一0 为此，作者的论文题目选为j i f e x 的有限元分析并行化，研究基于分布式网络并行 计算环境的有限元分布式并行算法，并采用m p i 加以实现。希望通过本文的研究，使得 j 球e x 能解决大型和超大型问题，缩短有限元计算时间，推动m r e x 软件在大型工程结 构中的应用。 1 3 有限元并行算法的研究现状 1 9 7 5 年以前人们研究最多的是一些常规算法的并行性，如递归、矩阵乘法、方程组 的求解。1 9 7 5 年之后有限元并行算法的研究就逐渐发展起来，n o o ra 和f u l t o nre 首先从向量并行处理机的角度出发，论述了流水线向量并行机对有限元法未来的发展及 影响【1 4 。n o o r a 、k a m e lh 和f u l t o nr e 讨论了利用子结构方法建立并行计算问题及子 结构技术在并行计算中的优势，但没有作具体的研究 1 5 】。之后，j o r d a nhf 和s a w ”rp l 又对适用于结构并行分析的多处理机系统进行了讨论，但是没有讨论有限元并行分析 的具体过程“。 到了八十年代，随着并行算法理论进一步发展和成熟，根据所使用的不同类型的计 算机，有限元并行算法的研究也就越具体和广泛，适用于不同类型计算机的有限元并行 算法及其程序相继产生。结构静、动线性及非线性分析、优化设计、稳定分析等有限元 并行算法的研究越来越活跃，各种有限元并行分析的任务划分法相继形成。在有限元线 性静力分析方面，逐渐形成了以直接并行算法和迭代并行算法为基础的两个主要发展方 向。另外，耦合使用这两种方法也成为另一发展方向。以前，有限元并行算法的研究基 本上在巨型并行机上进行，由于价格昂贵，因此国内在有限元并行计算方面的工作开展 得较晚，8 0 年代后期国内才逐渐开展这方面的工作。 迭代并行算法优点是可避免或减少同步控制，缺点是不便于和目前现有的一些成熟 的大型软件接口，现有迭代法的收敛速度和稳定性还需迸一步改进。广泛研究和应用的 大连理工大学硕士学位论文 是预处理共轭梯度法( p c g ) 基础上的e b e 方法，主要适合于向量并行机。早期，b 糊g y e 和c a r e vgf 对e b e 方法进行了详细的讨论【1 7 l ；l a wkh 研究讨论了e b e 方法在有 限元分析中的具体实施过程【1 8 】。近年来，0 r t i g o s a e m 等分析了p c g 方法在几种不同体 系结构的并行计算机上的并行实施【” 。r 且oarm 【2 0 】和g u l l e m das 、d o d d sr h 【2 l j 在机群上采用m p i 实现了迭代并行算法。国内，余天堂、姜弘道在基于p 讧的分布式 网络并行环境下实现了p c 0 法田】；刘耀儒等在基于m p i 的分布式网络并行环境下实现 了e b e 法【2 3 1 ，都证明了e b e 方法是一种很有效的并行计算方法。 直接并行算法具有稳定性好、精度高和便于对现存的成熟的串行算法程序进行修改 等优点，缺点是设计不好的算法会造成较多的通信次数。有限元分析的两个关键阶段是： 由单元刚度矩阵组集总体刚度矩阵和求解系统方程组。由此得到并行化的两个主要内 容：是子结构直接并行法，该方法在结构划分上寻求子结构间的并行性，以取得任务 分配的并行；二是基于一般的有限元体系，主要对求解方程组耗时太多的部分采用直接 并行法。前者挖掘了力学问题自身的并行性，后者主要考虑了求解方程组的并行性。 对于子结构法的并行算法，n o o ra 、k a m e lh 、f u l t o nre 首先指出了该方法的优 势，但未作具体研究【l5 ；李强、邹经湘提出了一种结构静力分析的独立子结构并行计算 方法，可保证各处理机任务均和带宽最小【”】；o w e nd rj 、g o n c a l v e soja 也讨论了子 结构法在有限元中的应用【2 5 】；胡宁、张汝清也在子结构分析方面做了一些研究口。 对于方程组直接解法，国内外都有大量研究。方程组直接解法主要有三种，分别是 l u 分解法、c h 0 1 e s k v 分解法和l d l t 分解法，对于有限元分析过程中得到的对称正定 矩阵，l d l l 分解法是最为有效的一种算法。在各种并行平台上，三种算法都有不少研 究，限于时间与篇幅，我们不能一一列举。g e i s tga 、r o l i n ech 给出了在分布式存 储并行机上按行和列分配矩阵的两种n j 解法，研究结果表明这两种方法均能获得较高 的效率【2 7 】；张健飞、姜弘道 2 3 】和f 曲a tc 、w i l s o e 嘲研究并讨论了有限元方程组的的 l d l l 并行分解方法，数值实验结果表明对于求解有限元方程组，l d 0 1 分解算法的并行 化是一种行之有效的方法；迟学斌 3 们，王思群、魏紫銮【3 ”，梁维泰、周树荃【3 2 j 分别研 究了c h 0 1 e s b 分解算法，并在不同体系的并行计算机上实现了该算法。 从八十年代至今，有限元并行算法的研究一直方兴未艾。国际上掀起了利用并行机 进行工程分析和研究的高潮，有关有限元并行和相应的并行数值计算方面的研究迅速发 展。目前，这个领域发展的主流是直接法和迭代法的耦合使用。比如，先利用子结构并 行解法，进行静凝聚，然后，将子结构看成仅有界面节点的大单元，使用迭代法求解。 李强、邹经湘口叭，朱金福、乔新【3 3 】和d r a c o p o u l o smc 、c r i s f i e l dma 【3 4 】等人都研究过 子结构法和迭代法相结合的并行算法，数值实验结果表明两种方法的有效结合可以使得 衄：e = k 软件有限元分析并行化 有限元分析速度进一步加快。 近年来，由于高速网络的出现及其迅猛的发展，使得网络并行计算成了当前国际上 并行计算的一个主要方向。又出现了一批以m p i 、p v m 为代表的基于消息传递的并行 程序设计平台，极大地方便了用户，保证了程序的可移植性。因此基于分布式存储并行 平台的有限元并行算法开始成为研究热点。张健飞、姜弘道使用m p i 实现了有限元分析 中刚度矩阵的并行l d l t 分解算法，在p c 机群上的数值实验表明该算法具有较高的并 行加速比和效率口8 ；雒战平、刘之行通过生成一种特殊结构的刚度矩阵，设计了一套有 效的并行计算策略，实现了有限元分析的并行化，在曙光3 0 0 0 上的数值实验表明算法 随着开辟进程数目的增多，加速比变得比较理想【3 司；阮红河、袁勇在面向对象有限元分 析系统o o f e a 的基础上扩充并行计算模块，增加了并行预处理共轭梯度法求解器，并 在分布式环境下进行计算，结果表明算法具有不错的并行效率【3 6 】。 国内各大高校都开展了对于有限元并行化的研究。清华大学 2 2 1 ，西安交通大掣”】， 同济大掣”】以及河海大学在有限元并行程序研究方面都有投入。 1 。4 本文所做的工作 本文研究j i f e x 软件有限元分析部分的并行化。由于j e x 软件是一个持续发展 的软件系统，为了维持j i f e x 原有的组织结构，保持j i f e x 原有系统的完整性，以利于 皿7 e x 的后继开发和维护，采用迭代法显然是不合适的。而直接法拥有便于对现有串行 程序进行修改的优点，所以本文采用了直接法。直接法又分为子结构并行法和方程组直 接共行法。其中子结构法在结构划分时寻求子结构间的并行性，以此达到加快求解速度 的目的，子结构的划分质量对于求解速度的影响很大。子结构法要求在有限元网格剖分 时就把原有结构划分为多个子结构，同时为了保持结构上网格的连续性，相邻子结构界 面上的节点必须保持一致( 节点数及节点坐标相同) 。对于实际工程问题，区域的形状一 般较复杂，对于这类问题为了保证有限元并行分析时各处理机间负载平衡，在划分子结 构和剖分子结构前应首先计算好剖分后各子结构网格的自由度，尽量让它们一样大或比 较接近；同时还要保证子结构的边界结构简单，边界处理时间短。有限元网格剖分不属 于本文研究内容，而一般情况下没有针对子结构法所作的普通剖分得到的网格不能满足 子结构法边界结构简单的原则，采用子结构法会造成处理机间通信次数的大幅增加，并 行效果不会好。 因此，最终本文选择了方程组直接解法来完成j e x 有限元分析部分的并行化， 在原有的j i f e x 软件上增加了方程组并行直接求解模块。除了以上提到的稳定性好和精 大连理工大学硕士学位论文 度高的优点外，方程组直接解法对于有限元分析有多种工况时比迭代法更有优势。原因 在于我们只需要进行一次u ) 0 0 分解，以后只需要进行多次回代求解就可以了。 由于方程组求解占有限元静力分析总时间的大概7 0 以上，在动力分析中更是达 到了9 0 以上，高效的解决方程组并行求解可以显著的改善有限元分析的速度。在此基 础上，主要做了以下工作： ( 1 ) 研究了针对有限元分析中对称正定方程组的并行l d l 。分解算法，并在一维变 带宽存储的条件下实现了分块的u ) l 1 分解算法，这样做使得j e x 在占用内存较少的 情况下可以完成大规模有限元分析计算。 ( 2 ) 研究并实现了稀疏三角矩阵的并行求解算法，同样采用了维变带宽存储条件 下的分块算法。 ( 3 ) 在p c 机群上对算法的性能做了测试，给出了测试结果，并对结果进行了分析。 1 5 本文的组织结构 本文余下部分组织结构如下： 第2 章并行计算基本理论。主要介绍了并行计算的基本概念，并行计算机的体系 结构和访存模式，给出了代表机型；介绍了机群的发展和特征，给出了机群计算的优势； 最后介绍了并行算法设计，给出了并行算法的度量标准。 第3 章消息传递接口m p i 。主要介绍了m p i 的发展和基本概念以及m p i 程序设 计的知识，对m p i 的函数作了简单介绍。 第4 章并行方程组直接解法。首先介绍了串行l d 0 。分解算法，接着介绍了本文 采用的存储方式和实现的并行l d l l 分解算法，最后介绍了三角形方程组的并行求解算 法。 第5 章实验测试。在p c 机群上对算法的性能做了数值实验。给出了数值实验结 果，并对结果进行了分析和讨论。 最后是结论和展望。给出了本文的结论，并对进一步的工作进行了展望。 j 卫毛x 软件有限元分析并行化 2 并行计算基本理论 2 。1 并行性撅述 并行性是物质世界的一种普遍属性，是问题中具有可同时进行运算或操作的特性。 在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或不同的工作，它们在时 间上能相互重叠，这就体现了并行性。所以，并行性实际上包括了同时性和并发性两重 含义。同时性( s i m u 】t a n e i 劝指的是两个或多个事件在同一时刻发生；并发性( c o n c u r r e n c y ) 指的是两个或多个事件在同一时间间隔内发生p ”。 为什么要采用并行计算昵? 这是因为： ( 1 ) 它可以加快速度，即在更短的时间内解决相同的问题或在相同的时间内解决更 多、更复杂的问题，特别是对一些新出现的巨大挑战问题，不使用并行计算是根本无法 解决的； ( 2 ) 节省投入，并行计算可以以较低的投入完成串行计算能够完成的任务； ( 3 ) 物理极限的约束光速是不可逾越的速度极限，设备和材料也不可能做得无限小， 只有通过并行才能够不断提高速度。 实现或提高计算机系统的并行性，可以通过时间重叠、资源重复和资源共享等技术 途径来实现。 时间重叠( t i m es u p e i 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 ) 是在并行性概念中引入空间因素。通过重复设置硬件 资源来提高可靠性或并行性能。在结构上，采用多操作部件和多存储部件，早期受限于 硬件价格，资源重复是以提高可靠性为主；随着硬件价格的降低，资源重复被大量用于 提高系统的速度性能，成为提高并行性的一个重要方面。 资源共享( r e s o u r c es h a r i n g ) 是让多个用户按时闻顺序轮流地使用同套资源，包括 c p u 、主存、外设等硬件资源和软件资源、信息资源，以提高其利用率，从而提高整个 系统的性能。 2 2 并行计算机 并行计算的物质基础是高性能并行计算机( 包括分布式网络计算机) ，它们的发展直 接影响着并行算法的设计与实现。 大连理工大学硕士学位论文 2 2 1 并行计算机的体系结构 1 9 6 6 年f l y 皿提出了著名的f 1 y n n 分类法，根据指令流与数据流方式的不同将计算 机系统分类。指令流指机器执行的指令序列：数据流指指令调用的数据序列，包括输入 数据和中间结果。据此，可以把计算机系统分成以下四类口副： 单指令流单数据流s i s d ( s m g l ei n s 劬“o ns t r e 鼬& s i n 9 1 ed a t as t r e 锄) ； 单指令流多数据流s i m d ( s i i l g l ei n s 衄【c t i o ns 仃e 锄& m u l t i p l ed a t as 仃e 锄) ； 多指令流单数据流s d ( m u l t i p l ei i l s 订u c t i o ns 仃e 跚& s 吨l ed a 诅s t r e 锄) ： 多指令流多数据流m i m d ( h 如l t i p l ei n s 眦t i o ns 订e 锄& m l l l t i p l ed a t as t r e a m ) 。 国内外很少见到多指令流单数据流m 【s d 方面的产品，s i m d 和m i m d 并行计算机 是研究和开发的主流。s i m d 并行机对并行计算机的发展起到了重要推动作用，但9 0 年代以后，并行机均朝着m 玎v i d 方向发展，s i m d 并行机基本退出了历史舞台。 现在，并行计算机系统除少量专用的s n v i d 系统外，绝大部分为m i m d 系统，包 括向量并行机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 ) 、对称多处理机s 姗p ( s y l i n e t r i cm u l t i p r o c e s s 血g ) 、大规模并行处理机m p p ( m a s s i v e l yp 缸a l l e lp r o c e s s o r s ) 、工作站机群 c o w ( c l u s t e ro fw o r k s t a t i o n s ) 和分布式共享存储多处理机d s m ( d i s t r i b u t e ds h a r e d m e m o r y