（计算数学专业论文）并行多极边界元的gmres算法及其应用.pdf

摘要 摘要 本文系统研究了静电场中多极展开法和极小残值算法，以及两者的结 合点，将基于多极展开法的广义极小残值算法引入弹塑性边界元问题。对 其过程中各环节的并行性分别进行了研究，设计了并行算法，并在所构建 的集群系统上完成了程序实现。由于本方法的高效性和低的内存占有量， 使边界元法运算大规模问题成为可能。 本文共分为5 章，第1 章为绪论部分，概述了并行计算、并行边界元 法和快速多极展开法的发展状况，指出了本课题的来源、内容和意义。 第2 章介绍了集群系统的定义、特点、分类，以及集群系统环境下并 行程序设计中两种消息传递机制p v m 和m p i ，将其特点作了比较，对 m p i 作了重点介绍；并研究了集群系统的构建过程，进行了具体实施。 第3 章介绍了并行算法的定义及其分类，提出了并行程序开发的基本 概念，阐述了并行算法的设计思想及其性能评价指标，重点介绍并行程序 设计中m p i 的调用方式及其功能，并引入一种高效的调度策略。 第4 章介绍了k r y l o v 子空间方法的基础理论，并给出g m r e s 算法详 细的迭代计算步骤及实用化处理，介绍了快速多极展开法的基本思想、相 关理论及其使用条件，描述了基于快速多极展开法的广义极小残值算法。 第5 章以弹塑性问题模型为例，叙述了基于f m m 的g m r e s 算法在 弹塑性边界元中的应用，并针对边界元问题自身固有的并行性，对其具体 计算过程进行并行化研究，设计了基于集群系统的并行算法，最后通过对 实验结果的分析，进一步体现了并行多极展开g m r e s 算法的正确性和实 用价值。 关键词并行计算；边界元法；集群系统；消息传递接口；并行边界元法 广义极小残值算法；快速多极展开法 燕山大学理学硕士学位论文 a b s t r a c t i nt h i sp a p e r , w es t u d yt h ef a s tm u l t i p o l em e t h o d ( f m m ) i n e l e c t r o s t a t i c s a n dg m r e sa l g o r i t h m ，b e s i d e st h ec o m b i n i n gp o i n to ft h e m ，a n dt h e nu s et h e g m r e sa l g o r i t h mb a s e do nf m mi n t ot h eb e mf o re l a s t o - p l a s t i cp r o b l e m c o m b i n i n gt r a d i t i o n a lb e m w i t hf m ma n dg m r e sa l g o r i t h n lb a s e do nt h e s t u d yo fe a c ht a c h eo ft h ep a r a l l e lc o m p u t i n gp r o c e s s ，w ed e s i g nt h ep a r a l l e l a l g o r i t h m ，t h e nr e a l i z e dt h ep r o g r a mi nt h ep a r a l l e lc l u s t e rs y s t e mc o n s t r u c t e d i nt h i sp a p e r d u et oi t sh i g he f f i c i e n c ya n dl o wc o m p u t i n gm e m o r yd e m a n d i n g ， t h ea b o v em e t h o dm a k e st h el a r g e - s c a l ec o m p u t i n gp o s s i b l e t h ep a p e ri n c l u d e sf i v ec h a p t e r s c h a p t e r1i s i n t r o d u c t i o n ，w i n c h s u m m a r i z e st h ed e v e l o p m e n to fp a r a l l e lc o m p u t i n g ，p a r a l l e lb e ma n df m m ， t h e np r e s e n t e dt h es o u r c e ，s i g n i f i c a n c eo ft h et a s ka n dt h em a j o rw o r ko ft h e p a p e l i nc h a p t e r2 ，t h ed e f i n i t m na n dc h a r a c t e r i s t i c so fc l u s t e rs y s t e ma r e i l l u s t r a t e d t o g e t h e rw i t h i t sc l a s s i f i c a t i o n 1 1 1 ep a p e ra l s oi l l u s t r a t e sa n d c o m p a r e st w ok i n d so fm e s s a g ep a s s i n gm e t h o d ，p v ma n dm p i ，w h i c hc a nb e u s e di np a r a l l e lp r o g r a m m i n gi nt h ec l u s t e rs y s t e m t h e ni ti n t r o d u c e sm p l w i t hs t r e s s ；f i n a l l y , t h ec o n t r u c t i o np r o c e d u r eo fp a r a l l e lc l u s t e rs y s t e mi s s t u d i e da n dr e a l i z e d i nc h a p t e r3 ，a f t e rb r i e f l yi n t r o d u c i n gt h ed e f i n i t m na n dc l a s s i f i c a t i o no f p a r a l l e la l g o r i t h m ，w ep r e s e n ti t sd e s i g n i n gi d e aa n de v a l u a t i n gm e t h o d t h e n t h et r a n s f e rm o d eo f m p it o g e t h e rw i t hak i n do f e f f i c i e n ts c h e d u l i n gm e t h o di s i n t r o d u c e d i nc h a p t e r4 ，t h eb a s i ct h e o r yo fk r y l o vs u b s p a c em e t h o di si n t r o d u c e d ， a n dt h ed e t a i l e di t e r a t i v e s t e p sa n dt h eu t i l i z a t m nd i s p o s a lo fg m r e s a l g o r i t h ma r ep r e s e n t e d t h e nas e r i e so fc o r r e l a t i v et h e o r yo ff m mi n i i a b s t r a c t i n t r o d u c e da n d f i n a l l y , t h eg m r e sa l g o r i t h mb a s e do nf 删i sp r e s e n t e d i nc h a p t e r5 ，w et a k et h ee l a s o p l a s t i cm o d e lf o re x a m p l e ，d e p i c tt h e u t i l i z a t i o no ff a s tm u l t i p o l eg m r e sa l g o r i t h mi nb e m ，t h e nb a s e do nt h e s t u d yo fi t si n h e r e n tp a r a l l e lc h a r a c t e r s ，w ed e s i g nt h ep a r a l l e la l g o r i t h mi nt h e c l u s t e rs y s t e ma n dt h er e s u ho f e x p e r i m e n tf u r t h e rd e m o n s t r a t et h e v a l i d i t ya n d e f f i c i e n c yo f p a r a l l e lf a s tm u l t i p o l eg m r e s k e y w o r d sp a r a l l e lc o m p u t a t i o n ；b e m ；t h ec l u s t e rs y s t e m ；m p i ；t h ep a r a l l e l b e m ；g m r e s ；f m m m 燕山大学理学硕士学位论文 第1 章绪论 第1 章绪论 本文涉及计算数学、计算力学、边界元等多个领域，构建了基于d e b i a n g u r d l i n u x 年 i m p i 的集群系统，深入研究了并行g m r e s ( t h eg e n e r a l i z e d m i n i m a lr e n d u a la l g o r i t h m ) 算法及其f o r t r 8 n 源程序，提出了并行边界元法 的基本计算结构，最露实现了g m r e s 算法在三维边界元问题中的应用。 1 1 并行计算综述 1 1 1 并行计算的产生与发展 计算机，做为人类脑力劳动辅助工具，经产生傻越来越普遍的应用 在社会的各个领域。源于对高性能的追求，人们早在计算机发展的初期， 就认谖到了并行计算的童要性，而且在计算机发展过程中也一直试图在系 统的各个层次上开发并行性。然而由于应用范围与技术条件的限制，早期 成果并不显著。 近些年，随着科技的向前发展，人们对问题的研究也不断深入。高科 技领域对计冀机性能提出了越来越商的要求，新一代的计算机系统，无论 在计算能力和计算速度，都比原有计算桃系统优越。但是，物理上的极限 和工程实际中的河题使单机速度根难满足应用需求，并行计算的概念就引 起了普遍关注。美国国防部尖端研究规划总署( a p p a ) 曾于1 9 8 2 年初在纽约 召开巨型机和并行体系结构的专家会议，得出的结论是：提高目前计算机 系统性我的难一方法是选择“大量的并行”。如今，大力开展并行计算的研 究，充分挖掘计算机体系结构和计算问题本身的内在并行性，己成为当今 世界上一个崭新的研究课题】。 并行处理技术有其产生的必然性： 首先，对于那些要求快速计算的应用阀题，单处理机由于器件受物理 速度的限制而无法满足要求，除了增强处理器本身的计算能力外，并行处 理是一种突破计算能力的有效手段； l 燕山大学理学硕士学位论文 其次，对于那些大型复杂的科学工程计算问题，为了提高计算精度， 往往需要加密计算网格，而细网格的计算也意味着大计算量，它通常需要 在并行机上实现： 最后，对于那些实时性要求很高的应用问题，传统的串行处理往往难 以满足实时性的需要而必须在并行机上用并行算法求解。但就计算科学而 言，并行计算理论仍处于发展阶段，特别是早期的并行机均很昂贵，编写 并行软件又很难，所以并行性的优点尚未被普遍的认同。 自6 0 年代末以来，并行计算已经过几十年的研究与发展，从历史上看， 并行算法研究的高峰期似乎在七十年代和八十年代。这一阶段，在各种不 同互连结构的s i m d 3 模型上和共享存储的s i m d 模型上设计出了很多优秀 的非数值并行算法，它们在整个并行算法研究历史上占据着辉煌的一页。 九十年代中期以后，并行算法的研究渐渐面向实际而内容有所拓宽。 不但研究并行算法的设计与分析，而且也同时兼顾到并行机体系结构和并 行程序设计。近几年来，并行计算已经成为高性能计算和大规模计算中的 关键技术。无论在软件技术上，还是从硬件结构上，高性能、大规模计算 已和并行计算无法分割【2 ，”。 当前，由于一批具有重大意义的科学工程计算问题不断对计算机的计 算能力提出了严峻挑战，国际国内高性能计算的研究十分活跃，并行算法 的研究也更讲究实用，更多地集中在应用领域并行算法的研究上，包括计 算生物学、计算化学、计算流体动力学、飞行动力学、计算机辅助设计、 数据库管理、油藏建模、中长期天气预报、海洋环流和求解n - b o d y 问题等， 以及面向应用的大型科学与工程问题的并行数值计算，诸如求解大型稀疏 方程组、大型非线性方程和有限元分析等。 1 1 2m p i 的产生和主要实现 软件环境与应用程序的开发逐渐成为并行计算的主要发展方向。在分 布式内存m i m d 机上各进程之间主要靠消息传递来协同工作，这就需要消 息传递平台的支持。 目前，国际上通用的并行平台有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 ( p a r a l l e l v i r t u a lm a c h i n e ) 两种。 2 第1 章绪论 本文采用m p i 作为程序开发的并行平台，m p i 是目前最重要的并行编 程工具，它具有移植性好、功能强大、效率高等众多优点，而且具有多种 不同的免费、高效、实用的实现版本，几乎所有的并行计算机厂商都提供 对它的支持，这是其他的并行编程环境所无法比拟的。 先后有来自美国和欧洲各国共4 0 多个组织的6 0 多位专家参与了m p i 的 标准化指定工作，世界上许多著名的计算机厂商和大学及研究所的科研人 员也都为m p i 的指定付出了努力。 m p i 的标准化始于1 9 9 2 年4 月在威吉尼亚的威廉姆斯堡召开的分布存 储环境中消息传递标准的讨论会，其间提出了作为标准消息传递接口所应 具有的基本特点，同年1 1 月完成了第一个草案m p h ，旨在引起广泛关注， 以推动消息传递接口标准化的进程。m p h 讨论了几种点到点通信的规范， 没有涉及集群通信的规范。在f l j d o n g a r r a ，h e m p e l 等于1 9 9 2 年1 1 月推出m p i 1 0 之后，一个对m p i 其重要推动作用的非官方论坛m p i 论坛应运而生， m p i 论坛于1 9 9 3 年1 1 月完成了m p i 标准的指定工作。1 9 9 5 年6 月，在对 m p l l o 版本进一步修改完善的基础上，新版本m p l l 1 诞生，但其中缺乏对 许多重要但实现起来比较复杂的功能的定义，比如i o ；于是1 9 9 7 年7 月 m p i 2 被推出，它是原有m p i 的重要扩充部分，主要有三方面内容：并行i o ， 远程存储访问和动态进程管理。原有的m p i 版本并称为m p i 1 。虽然m p i 的 产生时间相对较晚，但基于以上种种优点，在短短几年内便迅速得以普及， 成为消息传递并行编程模式的标准，也从另一方面证明自身的生命力和优 越性。 由于m p i 不是一门语言而是一个库，因此对m p i 的使用必须和特定的 语言结合起来进行。f o r t r a n 是科学与工程计算的领域语言，而c 语言是目 前使用最广泛的系统和应用程序开发的语言之一，因此对f o r t r a n 和c 语言 的支持是必须的。所以在m p i 规范中，明确提出了m p i 与f o r t r a i l 7 7 和c 语言 的绑定，并且给出了通用接口和针对f o r t r a n 7 7 和c 语言的专业接口说明。 目前，m p i 正在进一步做与f o r t r a n 9 0 和c + + 的结合。文中涉及的研究以m p i 与f o r t r a n 7 7 的绑定为编程的基础。 m p i 的模型实现在m p i 出现初期就出现，m p i 标准发布后，国际上已有 3 燕山大学理学硕士学位论文 许多m p i 实现，其中以自由软件形式发布的m p i c h 和l a m 【5 1 较为流行： l a m ( l o c a la r e am u l t i c o m p u t e r ) 是免费的m p i 实现，它是o h i o 超级计算中心 开发的基于异构网络集群的并行程序的支撑环境，向用户提供m p i 编程界 面及一个完整的运行调试环境；m p i c h 是一种更为最重要的m p i 免费实现， 它是a r g o n n e 家实验室和密西西比州立大学伴随m p i 的制定过程联合 开发的一个可移植的m p i 实现，其主要目标是实现一个可移植性好而且高 效的m p i 接口。更为重要的是，m p i c h 是一个与m p i 1 规范同步发展的版 本；本文在l i n u x 环境下名为m p i c h 1 2 5 t a r g z 的m p i c h 软件包的配置下进 行m p i 并行程序的设计与执行，h t t p ：w w w m c s a n l g o v m p i m p i c h 为其官方 下载地址。 1 2 并行边界元法 1 2 1边界元法 工程、物理问题的数学模型的解如果可以转化为某个边界积分方程的 形式，那么用数值方法求解边界积分方程以达到求解数学模型的方法就是 边界元法，所以边界元法又被称为边界积分方程法。它是将区域内的偏微 分方程的边值归化为边界上的积分，如果边界归化的途径不同，可以从同 一边值问题得到几个不同形式的边界积分方程，也就形成了不同的边界元 法【6 】。 边界元法广泛应用于数学物理问题，如石油、天然气的勘探与开发、 大型结构问题、航天航空问题、天气预报等问题的计算中，并随着有限元 法的发展而在7 0 年代后期被英国安普敦大学b r e b b i ac a 1 7 1 提出的求解偏 微分方程初、边值问题的数值计算方法，由于它一般只需进行边界剖分， 有降低维数进行数值计算的特性，并且具有所占计算机内存小，计算时间 短，与有限元法相耦合能更好的解决工程实际问题等优点，所以边界元法 已在各个工程领域获得广泛应用。 边晃元法的深入研究始于一些前苏联学者，如m i k h l i n 、s m i m o w 、 g a k h o w 和i v a n o v 等，他们研究了标量型、矢量型积分方程及积分区域内奇 点和间断的情况，从而为进一步应用边界积分方程方法开辟了道路。7 0 年 4 第1 章绪论 代末，b r e b b i a 系统的总结了有限元法中的离散技术并应用于边界积分问 题，使得边界元法成为了一种独立的求解偏微分方程的数值方法，并首次 提出了“边界元法”( b o u n d a r ye l e m e n tm e t h o d ，b e m ) 这一名称，从而使边 界元真正的脱颖而出，成为工程分析和计算的一种新的有效工具。此时边 界元法已经应用到了弹性力学、断裂力学、弹塑性力学以及有势场等领域。 在国内，边界元法的研究相对较晚，1 9 7 8 年杜庆华教授率先独立研究 边界元法，并作出了推荐和综述 8 1 ，推动了国内边界元法的研究和发展。 紧接着，冯康、胡海昌、何广乾等一大批著名的数学和力学家加入到边界 元法的研究行列，使我国的边界元法研究得到了迅速发展。我国大部分边 界积分方程边界元法方面的工作是从固体力学方面的工程应用开始 的，后来迅速的转入非线性问题领域。 1 2 2 并行边界元法的发展现状 边界元法与有限元法相比，具有降低求解问题的维数、提高计算精度 的优点。但是，边界元法最后归结所得方程组的系数矩阵一般具有非对称 和满系数的特点，其存储量与全部节点的总自由度数的平方成正比，采用 直接法求解时，其运算量与总自由度数的立方成正比。因此当应用边界元 求解大规模问题，划分的单元比较多时，其运算量和存储量都将剧增，因 而极大的限制了边界元法在大规模工程问题中的应用。 在边界元法发展初期，由于微机条件的限制，求解问题的规模有限， 为了处理大规模问题，通常采用多子域法。但是，由于受计算机硬件技术 条件发展速度的限制，用传统的边界元串行解法求解问题的规模己不能满 足工程实际的需求。 但随着并行计算机系统及并行求解环境的出现，并行计算就成为一个 重要的研究方向。 在国内外，结合不同的并行环境，针对不问的问题进行了边界元法并 行计算的深入研究和探索。但是随着并行机及并行求解环境的出现，国内 外结合不同的并行环境，针对不同的课题进行了边界元并行算法的研究， 利用并行算法求解边界元问题是当前边界元领域的前沿课题。 在国际上，1 9 9 2 年a z u c c h i n i t 9 】和j h k a n e 1 0 1 分别在微机t r a n s d u t c r 燕山大学理学硕士学位论文 环境下进行了边界元并行算法研究。n i c a r n i y a “j 等人在工作站集群上用区 域分割法求解了二维位势问题，并讨论了并行效率，同时他们还在两台工 作站集群上进行了自适应边界元法的研究，其中一台进行边界元计算，另 一台进行误差分析。l s y a n g 1 2 1 在q c d p a x 并行机上用s q r 法求解了边界 元系统方程。其中文献 1 3 在i b m3 0 9 0 6 0 0 e 上用6 个c p u 进行边界元并行 计算，并行加速比达n 4 7 。e m d a o u d i 和j l o b r y 1 4 1 在t r a l l s p u t e r 环境下作 了初步的分布式并行边界元算法研究。m s i n g b e r 和d e w o m b l e 15 】等人 进一步讨论了负载平衡的方法。n k a r n i y a ，h 1 w a s e 和e k i t a 1 6 1 采用两台 计算机做了并行二维自适应边界元计算，其中一台做边界元计算，另一台 做误差分析。r a b i a l e c k i 和m m e r k e l 1 7 1 讨论了网络并行环境下的边界元 法计算，主要着重于如何进行方程组并行求解。a z u c c h i n i 和s m u k h e r j e e 【l8 对在向量机上边界元并行计算的研究作了总结和讨论。 在国内，西北工业大学叶天麟口9 1 在s g ip o w e rc h a l l e n g i 作站上用 k r y l o v 子空间法并行求解了不连续边界元法的方程。清华大学尹欣等【2 0 1 在 基于l i n u x 网络操作系统的p v m 系统上，用8 台微机对三维摩擦弹性接触问 题进行了求解，完成了5 万多自由度规模的运算，取得了很好的效果。燕山 大学的化春键f 2 l j 在网络平台上用两台微机实现了对三维弹塑性摩擦接触 问题的并行计算，将原c p u 的使用时间缩短了4 0 。陈一鸣【2 2 1 等开发了以 三维弹塑性摩擦接触边界元法f o r t r a n 语言平台的七台微机网络并行算法及 其软件，用以三维弹塑性摩擦接触边界元法为基础的精密带钢轧制接触快 速算法模型，并且同时模拟轧材与轧辊的耦合变形，对压下率、摩擦系数、 前张力和后张力等九组不同轧制条件，完成了宽厚l i f t 2 0 0 带钢轧制三维变形 计算，得到了“猫耳型”轧制压力横向分布等新颖结果，计算时间比原来 缩短6 倍。刘德义 2 3 等改善了非线性方程求解的迭代算法，建立了求解弹 塑性接触边界元问题的网络并行算法，大大的加快了计算速度。 要最大限度地利用并行环境，必须对边界元法的算法进行分析，对从 系统矩阵积分过程到方程求解过程的并行性进行讨论，并设法实现其与并 行环境紧密结合，才能高效率地求解大规模边界元问题。因此，国际上有 许多边界元研究者正在开展这方面的研究。我国也在这方面正在做出自己 6 第l 章绪论 应有的贡献。 1 3 。陕速多极展开法( f m m ) 1 3 1快速多极展开法 快速多极展开法( f a s tm u l t i p o l em e t h o d s ，简称f m m ) 是对求和项 n1 y 二近似计算的方法，源于静电场计算，用于计算大量粒子间两两相互作 百t 用的电场解析，其计算的近似程度和展开的项数密切相关。在多体静电场 问题中，对已知包含n 个电荷吼的单位立方体内，每个电荷的位置为x ， 求解电荷之间的相互作用力类问题，直接计算的计算量是o ( n 2 ) 阶的，当i l 增大时计算量将急剧上升。在物理研究领域，这种繁琐计算经常是不可避 免的。f m m 基本点在于将粒子按空间位置分为不同的集合，当集合相距足 够远时，集合之间粒子的相互作用以级数展开法计算，否则两两直接计算； 集合内粒子的相互作用两两直接计算。 二十世纪八十年代中期，美国耶鲁大学的r o k h l i n 2 4 1 等人提出了一种 求解积分方程的快速算法快速多极子方法( f a s tm u k i p o l em e t h o d ) 。该 法最初用来分析大量电荷的静电场和大量天体的引力场。上世纪8 0 年代后 期，g r e e n g a r d 等 2 5 1 提出一种快速多极展开，基于球谐函数在空间中的多极 展开，采用递归算法结构使计算量级降为o ( n ) 阶。该方法减少计算量显著 而得到了迅速且广泛应用。g r e e n g a r d 等已将f m m 方法应用于二维静电模 等离子体粒子模拟。在九十年代初，r o k h l i n 2 6 , 2 7 将其扩展到声波和电磁波 散射问题的求解。美国i l l i n o i s 大学的c h e w 的研究小组迅速将之用于求解电 磁散射积分方程，并陆续在f m m 的基础上发展了多层快速多极子方法【2 8 ( m l f m a ) ，射线传播快速多极子方法【2 9 1 ( r p f m m ) ，最陡下降快速多极子 方法( s d f m m ) n i 远场近似快速多极子方法【3 1 ( f a f f a ) 等改进和变形算 法。美 n c o y o t e 公司开发的用于m e m s 设计的软件a u t o m e m s ，采用边界 元快速算法，每个p e n t u r nf l s o oc p u 的峰值计算速度超过了每小时1 2 5 万 个单元。近几年，国内学者对f m m 的应用给予了积极的关注，如银燕【3 2 】 等将f m m 应用于无网格等离子体静电模粒子的模拟。王浩刚o3 】对f m m 中 7 燕山大学理学硕士学位论文 不变项的计算进行了优化。 1 3 2f m m 在边界元中的应用 将f m m 应用于边界元法发展起来的边界元快速多极算法p 4 j 己成为近 些年来国际上边界元的另一重要突破。在这种快速算法中，对于核函数与 远场边界变量乘积的边界积分不必离散为对于远场各单个节点未知量的 线性组合，而用节点集群的多极展开式来近似，从而将边界元法的满阵方 程组化为具有稀疏矩阵的方程组。在对于存储的需求和求解时间两方面都 从原来的o ( n 3 ) 减少到o ( l o g h ) 量级。这一具有突破性的改进对于求解大 规模问题带来了非常可观的效益。为边界元法研究者展示了广阔的应用前 景。 将f m m 应用于边界积分方程的迭代求解，可追溯至u r o k h l i n 的论文口”。 其广泛应用于线弹性和低雷诺数的液体动力学问题，在二维问题中运算等 价点是胛= o ( 1 0 2 ) ，对目前的微机来说这一差别是非常有意义的。但一直 没有应用于三维椭圆边值问题中。这是因为f m m 适用于三维边值问题，只 有解题规模超过n = 0 ( 1 0 3 一1 0 4 ) 时才有意义。当时，唯有一个研究组研究 将f m m 应用于三维l a p l a c e s 方程的相应边界积分方程中 9 6 1 。 最近，g r e e n g a r da n dr o k h l i n 提出了三维f m m ，并且将其运算等价点 降为n = 0 ( 1 0 2 ) 。在未来的微机上边界元程序使三维f m m 将更具吸引力。 国外多位学者在边界元的研究中引入快速多极算法口7 “ ，并且取得良好的 效果。a t a l l a 4 2 1 利用快速多极展开方法对板的声辐射进行了研究。f m m 没 有被广泛应用于非l a p l a c e s 控制方程的边值问题，原因在于除了它的控制 方程不同外，还因为其它偏微分方程不像l a p l a c e s 方程直接涉及多体静电 学问题一样适应f m m 。不过，已有少数研究者克服上一困难，如ge t a l 4 3 1 对二维双调和方程的研究，p e f f c ea n dn a p i e r 4 4 1 对二维线弹一l 生n a v i e r 方程的 研究，s a n g a n ia n dm o 【4 5 1 对三维低雷诺数方程( s t o k e s s 方程) 的研究等。他 们成果的特点可归纳为使积分方程适应f m m l 4 “，或者使f m m 适应积分方 程【4 4 4 5 】。但是，上述适应变换繁琐而往往使问题特殊化。特别是g r e e n b a u m e t a l 4 6 】的近似方法，不能扩展到三维。s a n g a n ia n dm o 4 5 1 提出的f m m 不能 扩展n - - 维线弹性问题，因为它只适用于刚性质点。p e k c ea n dn a p i e r t 4 4 j 第1 章绪论 给出的f m m ，计算效率较差。 国内在边界元快速多计算法方面的研究也取得了较大进展，2 0 0 2 年， 清华大学姚振汉教授课题组率先将泰勒级数展开式适用于2 维弹性问题边 界元法中【4 7 1 ，成功地模拟了复合材料不同粒子变形一应力场。与此同时， 申光宪课题组将静电多极展开式适用于3 维弹性问题边界积分方程中【1 “， 完成大规模轧辊辊型模拟计算。但是，目前国内在边界元快速多极算法的 并行性研究方面公开发表的文献依然相对较少，我国在边界元法研究领域 已经开展了2 0 多年的研究工作，如能为快速多极展开方法设计出高效率的 并行算法以实现更大规模的计算，这将对拓宽边界元法的应用范围具有重 要的理论价值和实际意义。 1 4 课题的来源、内容和意义 本课题来源于河北省自然科学基金项目：“精密轧制过程模拟的边界 元法并行计算研究”。应用对象为三维弹性边界元法研究中实现方程组的快 速求解过程，以解决实际工程应用过程中计算及存储量过大、求解方程组 速度过慢的问题。 本课题的研究内容包括： ( 1 ) 对集群系统进行学习研究，通过实际搭建1 6 个c p u 的并行集群硬件 环境，探索建立基于d e b i a n l i n u x 和m p i 的可靠的、可移植的、可扩展的网 络并行平台的方法。 ( 2 ) 对网络集群系统环境下并行算法的设计与分析进行研究，通过对 m p i 技术的深入学习，讨论在集群环境下开发和运行m p i 并行程序的方法 和过程。 ( 3 ) 通过对静电场中的f m m 算法和g m r e s 算法的学习，研究基于f m m 的g m r e s 算法的基本思想，及其在边界元中的应用。 ( 4 ) 通过分析串行计算结构中存在的并行性，结合本文建立的并行集群 系统的软、硬件特点，根据区域分解法及动静结合的调度策略，设计并行 多极g m r e s 算法。 ( 5 ) 在对并行计算和传统边界元法研究的基础上，将并行计算的思想渗 9 燕山大学理学硕士学位论文 透到边界积分项中，并引入并行多极展开g m r e s 方法求解边界元方程组， 实现了边界元法整个求解过程的并行处理，更新传统边界元法的计算结构。 本课题对多极展开法与广义极小残值算法进行研究，并将两者进行结 合，构造了基于f m m 的g m r e s 算法，应用于弹塑性边界元问题，采用基 于m p i 的并行计算技术及动静结合的调度方案，在集群中成功地实现了其 并行分布处理，属并行计算、轧制理论以及边界元法研究的领域前沿，具 有重大的学术和现实意义，工程应用前景宽广。 1 0 第2 章并行程序实现环境的构建 第2 章并行程序实现环境的构建 并行计算机、并行计算环境及并行算法是并行计算赖以生存的基础， 并行计算技术的发展与它们息息相关。在本章将主要介绍p c 集群系统和 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ，消息传递界面) 消息传递模式，及实际情况 中基于d e b i a n l i n u x 和i m p i 的p c 集群计算环境的构建。 并行程序设计环境应包括硬件平台、操作系统和并行程序语言、编译、 编程、调试及性能分析工具等。首先对并行程序设计环境的基础集群 系统进行简要的介绍。 2 1 集群系统简介 2 1 1 并行计算机体系结构 并行计算机体系结构是具体执行并行处理的实体，指并行处理系统( 主 要是分布式系统) 中处理机或者节点机之间的互连方式，它直接影响并行算 法的实现效率。 并行计算机体系结构可分为向量并行计算机、共享存储器并行计算机 及分布式存储器并行计算机。向量并行计算机能对向量计算进行高速并行 处理；共享存储器并行计算机系统特征是多个处理器共享内存；分布式存 储器并行计算机由多个节点构成，每个节点都有独立的处理器及内存，节 点之间以阏络相连，而节点的数目可以由几个到有数千个不等【4 ”。 其中，分布式存储并行计算机又可细分为大规模并行机( m a s s i v e l y p a r a l l e lp r o c e s s o r s ) 、分布共享存储器并行机( d i s t r i b u t e ds h a r e dm e m o r y p r o c e s s o r ) 及虚拟基享存储器的并行机( v i r t u a ls h a r e dm e m o r yp r o c e s s o r ) 、 及可伸缩性的共享存储器并行机( s c a l a b l es h a r e dm e m o r yp r o c e s s o r ) 等 4 ”。 共享存储m i m d 并行机是指多台处理机通过互连网络共享一个统一的 内存空间或多个存储器模块，各个处理机可以执行相同或不同的指令流， 可以直接访问所有的数据，通过共享内存来实现处理机间的通信与协调。 分布存储m i m d 并行机系统中每台处理机都有自己的局部存储器，构 燕山大学理学硕士学位论文 成一个单独的节点，节点之间通过互连网络相互连接，每台处理机只能直 接访问局部内存，不能访问其它处理机的存储器，它们之间的协调以消息 传递的方式进行。 与共享存储m i m d 并行机比较，分布存储并行机具有很好的可扩展性， 可以最大5 艮度的增加处理机的数量，是目前实现超大规模科学与工程计算 的唯一途径。但由于它的每个节点机需要依赖消息传递来相互通信，而消 息传递对编程者是不透明的，所以，分布存储并行机系统的编程较共享存 储复杂。 分布存储m m d 并行机系统主要有大规模并行计算机( m a s s i v e l y p a r a l l e lp r o c e s s o r s ，m p p ) 系统和集群( c l u s t e r ) 系统。 m p p 5 0 , 5 1 系统m p p 系统是最常见的并行系统，由大量的功能相同的处 理机通过互连网络连接而成，且往往采用专用结构。如：i b ms p 2 、i n t e l p a r a g o n x p s 、c m 5 、和国产y h 3 等。 c l u s t e r 【5 2 , 5 3 系统集群也称为群集、簇集，是利用高速通用网络将一组 高性能工作站或高档p c 机，按某种结构连接起来，并在并行程序设计以及 可视化人机交互继承开发环境的支持下，统一调度，协调处理，实现高效 并行处理的系统。c l u s t e r 的互连一般采用通用局域网，女l l e t h e r n e t 、f d d i 、 m y r i n e t 、a t m 等。 集群系统包括工作站集群n o w ( n e t w o r ko f w o r k s t a t i o n s ) 、p c 集群、全 对称集群等。由于该类集群系统充分利用各个单位自己的现有资源来组织 并行计算，特别适合于财力不足的科研单位和大学研究所，今年来得到了 快速的发展，目前我国自行研制的曙光1 0 0 0 a 、曙光2 0 0 0 等都属于这类并 行机。可以预见，随着高性能网络产品的完善以及各种软硬件支持的增多 和系统软件、应用软件的丰富，新一代高性能c l u s t e r 系统必将成为未来高 性能计算领域、商务计算和网络信息服务的主流平台之一，未来的超级服 务器将大量采用集群技术。 c l u s t e r 与m p p 相比，具有以下优点： 开发周期短，投资风险小：由于c l u s t e r 系统的节点机、操作系统、网 络通信全采用成熟的技术，因而节省了大量研制时间；c l u s t e r 系统的每个 第2 章并行程序实现环境的构建 节点都有一台独立的工作站或高档p c 机，相比于m p p 系统而言，系统性能 的发挥可得到保证，避免资金的浪费。 系统性价比高：传统巨型机或m p p 的价格都比较昂贵，工作站或高档 p c 机由于是批量生产出来的，所以售价较低，且由近十台或几十台工作站 组成的c l u s t e r 系统可以满足大多数应用的需求，因而性价比比较高。 节约系统资源：可以充分利用现有设备，将不同体系结构、不同性能 的工作站连接在一起，包括原有的一些性能较低或型号较旧的机器在 c l u s t e r 系统中仍能发挥作用。 系统可扩展性好：从规模上看，c l u s t e r 系统大多使用通用网络，系统 扩展容易；从性能上看，对大多数中、粗粒度的并行应用都有较高的效率。 系统容错性好：c l u s t e r 系统的一个重要发展方向是作为应用服务器、 数据库服务器等。因此，c l u s t e r 体系在软件的功能上下了很多功夫，个 重要的贡献就是失效切换技术，它是指当系统中的一个节点出错时，这个 节点上的任务可转移到其它节点上继续进行，用户本身感觉不到这种变化。 这也是导致这种机型的发展前途非常之好，特别是可以用作超级服务器和 服务器聚集。 应用面较广：由于c l u s t e r 是建立在成熟的技术基础之上的，因此与m p p 系统相比，c l u s t e r 往往能获得更广泛的应用。 c l u s t e r 系统对现有单机上的软、硬件产品的继承和对商用软、硬件最 新研究成果的快速应用，都表现出传统m p p 无法比拟的优势。 2 1 2 集群系统的定义 集群系统是利用高速通用网络将一组单机或多处理器系统，按照某种 结构连接起来，每台计算机都有独立存储器、i 0 设备和操作系统，并在并 行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处 理，实现高效并行处理的系统 5 4 1 。从结构和节点间的通信方式来看，它属 于分布式存储系统，主要利用消息传递方式实现各主机之间的通信，由建 立在一般操作系统之上的并行编程环境完成系统的资源管理及相互协作， 同时也屏蔽工作站及网络的异构性，对程序员和用户来说，集群系统是一 个统一的并行系统。集群系统中的主机和网络可以是同构的，也可以是异 1 3 燕山大学理学硕士学位论文 构的。目前已实现和正在研究中的集群系统大多采用现有商用工作站和通 用l a n 网络，这样既可以缩短开发周期又可以利用最新的微处理器技术。 大多数集群系统的并行编程环境也是建立在一般的u n i x 操作系统之上，尽 量利用商用系统的研究成果，减少系统的开发和维护费用。 2 1 3 集群系统的特点 集群系统之所以能够从技术可能发展到实际应用主要是它与传统的并 行处理系统相比有以下几个明显的特点： ( 1 ) 系统开发周期短由于集群系统大多采用商用工作站和通用l a n 网络，使节点主机及系统管理相对容易，可靠性高。开发的重点在通信和 并行编程环境上，既不用重新研制计算节点，又不用重新设计操作系统和 编译系统，这就节省了大量的研制时间。 ( 2 ) 用户投资风险小用户在购置传统巨型机或m p p 系统时很不放心， 担心使用效率不高，系统性能发挥不好，从而浪费大量资金。而集群系统 不仅是一个并行处理系统，它的每个节点同时也是一台独立的工作站，即 使整个系统对某些应用问题并行效率不高，它的节点仍然可以作为单个工 作站使用。 ( 3 ) 系统价格低 由于生产批量小，传统巨型机或m p p 的价格都比较昂 贵。工作站或高档p c 机由于是批量生产出来的，因而售价较低。由近十台 或几十台工作站组成的集群系统可以满足多数应用的要求，而价格却较低。 ( 4 ) 可伸缩性强在网络上增加新的计算机，可提高计算能力。 ( 5 ) 异构性可将不同系统结构的计算机组成一个异构并行计算环境。 2 1 4 集群系统的分类 最常见的三种集群类型包括高性能科学计算集群、负载均衡集群和高 可用性集群。 2 1 4 1 科学计算集群通常，科学计算集群是指利用集群开发并行应用 程序，以解决复杂的科学问题。这是并行计算的基础，