（计算数学专业论文）位势问题的并行多极边界元法.pdf

摘要 摘要 边界元法( b o u n d a r ye l e m e n tm e t h o d ，简称b z m ) 是新兴的离散解析工 具，广泛应用于机械，土木建筑，化工，海洋，航天和电气等工程领域； 成为当代计算机数值分析技术的核心部分。， 本文在传统三维位势边界元法的基础上，结合并行多极展开法和广义 极小残值法给出了三维位势并行快速多极边界元法。模拟了立方体闭域介 质的热流闷题，同非并行算法相比，并行多极边界元法有高速性和低内存 占有量等优点。 本文分为五章。第一章绪论部分，概述了边界元法，并行计算和数值 并行计算，以及快速多极展开法的发展历史，现状和近年来的发展动向。 第二章，详细介绍了并行计算平台，并行算法设计的基本原理和并行程序 设计的基础知识，对矩阵求逆的串行算法进行并行优化，给出并行算法源 程序，并对并行和非并行算法进行比较分析。第三章在介绍了二维位势边 界元法基础后，给出并行二维位势边界元法算例，通过数值试验表明并行 边界元法的优越性，这一章不属于算法级的并行优化，所以数值结果不改 变复杂度。第四章；我们着重介绍了快速多极展开法的数据结构，并且对 求解矩阵特征值的过程进行了算法级的并行优化，利用并行多极算法求解 矩阵特征值，在改进算法的基础上，降低了计算复杂度。最后一章，我们 结合边界元，并行，和多极展开这三个领域，提出了并行三维位势快速多 极边界元法，给出了立方体闭域介质热流问题的数值算例。数值试验表明， 对于大规模问题，并行多极边界元法在达到同样的计算精度时，具有较高 的计算速度和低的内存占有量的特点。 关键词边界元法；并行计算；特征值问题；快速多极展开法；位势问题 燕山大学理学硕士学位论文 a b s t r a c t b o u n d a r ye l e m e n tm e t h o d ( b e mf o rs h o r t ) i sab u r g e o n i n ga n a l y t i c a lt o o l f o rd i s p e r s a l i ti sw i d e l yu s e di nm e c h a n i c s ，c i v i le n g i n e e r i n g ，c h e m i c a l e n g i n e e r i n g ，o c e a n i c s ，s p a c i n ge n g i n e e r i n g ，e l e c t r i ce n g i n e e r i n ga n d s oo n , a n d b e c o m e sc o r eo f t h et e c h n o l o g yo f m o d e mc o m p u t i n gn u m e r i c a la n a l y s i s o nt h eb a s i so f t h et r a d i t i o n a lt h r e ed i m e n s i o n a lp o t e n t i a lb e m , c o m b i n i n g w i t ht h ep a r a l l e lm u l t i p o l ee x p a n s i o na n dn eg e n e r a l i z e dm i n i m a lr e s i d u a l a l g o r i t h m ( g m r e s ) ，w ea d v i s et h ep a r a l l e lm u l t i p o l em e t h o df o rt h et h r e e d i m e n s i o n a lp o t e n t i a lp r o b l e mi nt h i sp a p e r 、) i ks i m u l a t et h eh e a t - f l o wp r o b l e m o f t h ec l o s e dc u b i cf i e l d , c o m p a r e dw i t ht h en o n - p a r a l l e la l g o r i t h m ；t h em e t h o d w eu s e dh a st h es t r o n g p o i n ts u c ha sh i g hs p e e da n dl o wm e m o r yu s i n g w ed i v i d et h i sp a p e ri n t of i v ec h a p t e r s i nt h ef i r s ts e c t i o n , w es l l m m a r i 7 壅 t h e b e m , p a r a l l e lc o m p u t i n g a n dn u m e r i c a l p a r a l l e lc o m p u t i n g ，t h e d e v e l o p m e n ta n dt h es t a t u sq u oa n dt h ed e v e l o p i n gt r e n do ft h ef a s tm u l t i p o l e m e t h o d ( f m m ) i nt h es e c o n dc h a p t e r , w ei n t r o d u c et h e f l a to fp a r a l l e l c o m p u t i n g ，t h eb a s i cp r i n c i p l eo f t h ep a r a l l e la r i t h m e t i cd e s i g n i n ga n d t h eb a s i c k n o w l e d g eo fp a r a l l e lp r o g r a m m i n g w ea l s oa d v i s eap a r a l l e la l g o r i t h mf o r c o m p u t i n gc o n t r a r y m a t r i x i nt h ee n do ft h i s c h a p t e r , w ec o m p a r et h e n o n - p a r a h e lm e t h o dw i t ht h ep a r a l l e lm e t h o d ，a n df i n do u tt h a tt h el a t t e ro n ei s m u c hb e t t e r i nt h et h i r dp a r t , a f t e ri n t r o d u c i n gt h eb a s i so ft h et w o - d i m e n s i o n a l p o t e n t i a lb e m w ei n t r o d u c eap a r a l l e la l g o r i t h mf o rt w o - d i m e n s i o n a lp o t e n t i a l b e m , f r o mt h en u m e r i c a le x p e r i m e n t , w ec a n s e et h a tt h ep a r a l l e lo n ei so f h i g h s u p e r i o r i t y , b u tt h ep a r a l l e li nt h i sc h a p t e ri sn o tt h ea r i t h m e t i c - l e v e lo n e ，t h e c o m p l e x i t yo ft h i sm e t h o di sn o tc h a n g e d i nt h ef o r t hp a r t ，w ei n t r o d u c et h e d a t as t r u c t u r eo ft h ef m ma n dp u tf c i r w a r dt h ea r i t h m e t i c l e v e lp a r a l l e l o p t i m i z a t i o no ft h ep r o c e s so fc o m p u t i n gt h ee i g e n v a l u e so f am a t r i x w eu s e t h ep a r a l l e lf m mt om ic et h i sp r o b l e m , w en o to n l yb e t t e r m e n tt h ea l g o r i t h m , a b s t r a c t b u ta l s or e d u c et h cc o m p l e x i t y i nt h el a s ts e c t i o n , w ec o m b i n et h et h r e ef i e i d s ， b e m , p a r a l l e lc o m p u t i n g , a n df m m , a n da d v a n c et h ep a r a l l e lt h r e e p o t e n t i a l f m mb e m ，p r e s e n tt h en u m e r i c a le x p e r i m e n to fc l o s e dc u b i ch e a t f l o w p r o b l e m t h er e s u l t ss h o wt h a tf o rt h el a r g es c a l ep r o b l e m , p a r a l l e lf m m b e m h a st h ec h a r a c t e r i s t i c so f h i g hc o m p u t i n gs p e e da n d l o wm e m o r y u s i n gw h e n t h e 或l l n ec o m p u t i n g p r e c i s i o ni sg a i n e d k e y w o r d sb 0 1 1 i l d a r ye 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 ；e i g e n p r o b l e r n ；f a s t m t t l t i p o l em e t h o d ；p o t e n t i a lp r o b l e m 1 i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文位势问题的并行多极边 界元法，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研 究工作所取得的成果据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均己在文中以明确方式注明本声明的法律结果将完全由本人承担。 作者签字馋瞒橱 日期：如年月2 口日 燕山大学硕士学位论文使用授权书 位势问题的并行多极边界元法系本人在燕山大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有， 本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解 燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密c z ( 请在以上相应方框内打“”) 作者签名：谗- 稿椅 日期：耐年f 月加 导师签名。哪日期：2 序月知日 第1 章绪论 第1 章绪论 本文涉及边界元法、多极展开法、数值并行计算原理与方法和并行程 序设计等多个领域，对二维位势边界元法进行并行优化，给出并行多极法 求解矩阵特征值的算法，并利用并行快速多极边界元法求解了三维位势问 题。 ， 1 1 边界元法的发展历史和现状 物理问题的数学模型一般有三种主要的形式，第一种是描写微元的微 分方程，。第二种是综合整个区域的变分式，第三种归结为区域边界上的积 分方程，同一实际问题往往可以同时找到这三种形式，并且在数学上的推 导也是相通的。上述三种问题都是描写无限自由度的问题，如果存在封闭 的解析解，则可以求出需要的结果。由于方程及实际问题的复杂性，绝大 多数问题找不到这样的解析解。于是将无限自由度的问题经过离散化处理 而化为有限自由度的问题。现代计算机在有限自由度的问题上大有用武之 地，这也是电子计算机问世以后物理和工程计算方法飞速发展的原因之一。 有限差分法直接从微分方程出发，将求解区域划分为网格，近似的用 差分，差商代替微分，微商，于是无限自由度的闯题化为有限自由度的闯 题。这种方法在解决规则边界的问题时极为方便，但是正是由于这种限制 而增加了它的局限性，即对于非规则的边界问题适用性较差。 有限元法的重要归化途径是从微分方程所对应的泛函出发：用变分原 理结合区域剖分得到离散算式即代数方程组它克服了有限差分法对区域 形状的限制，对于各种形状的边界都能够灵活处理，有限元法是目前工程 计算的主要手段，这种方法的主要困难有两个：一是要找出微分方程对应 的交分式，二是由于区域的剖分随着网格的加细而使方程组的维数增大， 尽管使用计算机仍然不能达到快速精确的要求。 + 随着科学技术的发展，出现了新的计算方法即边界元法。这种方法是 用控制微分方程的基本解建立相应的边界积分方程，再对它结合边界的剖 燕山大学理学硕士学位论文 分而得到离散算式。由于只在边界上剖分，因此实际上是将问题降维处理， 降维的结果必然减少代数方程组的未知数。由于积分方程可以用加权余量 法得到，即由于近似函数引起的误差的合理分配而达到最佳效果。这样就 避免了寻找泛函的麻烦，这也是边界元法迅速发展的原因之一。 同源的三种数学模型产生三种等价的计算方法，离散的根据不同，手 段各异，表现出的效果也不同，有时差别很大。 边界元法是在经典的积分方程的基础上，吸取了有限元法的离散技术 而发展起来的计算方法。从计算格式形成的全过程看，关键问题有两个， 一个是问题的边界化，即将给定区域的定解问题化为只考虑边界的问题。 这一步的关键是格林( g r e e n ) 公式，这是边界元法的基石。边界化的结果是 使问题降维，如果是各维尺度相近的大型问题，代数方程组的未知数按照 指数规律减少，这无疑将大大减少准备工作、存储量与机时。有限元法要 将全部区域及边界离散，并要求将全部节点纳入方程进行计算，这是因为 这些节点值包含在同一封闭方程组中。边界元法的封闭方程组中只有边界 节点上的计算量，解完方程组再根据需要有目的地求内部值，因此减少了 计算的盲目性。 形成格式的第二个关键是边界的离散化。单是就离散技术本身而言，一 与有限元法没有什么区别。由于只是对边界离散化，因此计算误差只来源 于边界，这就使我们将减少误差的全部精力放在边界上。又由于区域内由 解析公式计算，这就提高了计算精度，并且达到内部值的某些特殊要求， 如连续性、可微性等。 计算格式形成的两个关键已经体现了计算简单，适应性强，精度高的 优点，这正是边界元法的生命力所在。 电子计算机的发展开创了数值求解积分方程的新时期，一些学者研究 了解积分方程的直接解法和间接解法，解决了一些弹性力学问题。2 0 世纪 6 0 年代末，得到了三维弹性静力问题积分方程的数值解。至此，为边界元 法奠定了理论基础和应用基础。 2 0 世纪8 0 年代以来，世界各国已经从基本理论与方法的研究向深广的 领域发展，在波的传播、断裂力学、接触问题、耦合问题的弹塑性、震动 2 第1 章绪论 问题、电磁场、流体力学、生物力学、等离子运动等方面都取得了不少进 展。 边界元法的研究正处在上升阶段，应扩大在上述领域的研究与应用。 加强基本理论( 基本解，奇异积分，收敛性，误差估计，边界元外推法) 的研 究，研究大型满秩非对称正定系数矩阵方程组的解法，开发有实用价值， 能在微机上使用的程序包等。 1 2 并行计算与数值并行计算 并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。 完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器( 可以 几个、几十个、几千个、几万个等) 通过网络连接以一定的方式有序地组织 起来( 一定的连接方式涉及网络的互联拓扑、通信协议等，而有序的组织则 涉及操作系统、中间软件等) 。并行计算的主要目的：一是为了提供比传统 计算机快的计算速度；二是解决传统计算机无法解决的问题。 并行计算在许多计算机应用领域都产生了巨大的影响，使原来无法解 决的应用问题成为可能。 并行计算的研究内容广泛，包括并行计算机系统结构、并行算法设计、 并行编程环境等，具体表现在下面几个方面： 并行计算机的设计：包括并行计算机的结构设计、互联拓扑、网络通 信等。设计并行计算机重要的一点要考虑处理机数目的按比例增长( 即可扩 展性) 及支持快速通信及处理机问的数据共享等。 有效算法的设计：如果没有有效的并行算法，并行计算机无法使用， 而并行算法的设计完全不同于串行算法的设计，不同的并行计算机的算法 设计不同，只有将不同的并行计算机与不同的实际问题相结合，才能设计 出有效的并行算法。主要研究内容包括并行计算模型、芽行算法的一般设 计方法、基本设计技术和一般设计过程，并讨论一些数值并行算法与非数 值并行算法的设计 评价并行算法的方法：对于给定的并行计算机及运行在上面的并行算 法，需要评价运行性能。性能分析需解决的问题：如何利用基于并行计算 3 燕山大学理学硕士学位论文 机及其相适应的并行算法去快速地解决问题，及如何有效地利用各个处理 器。研究内容包括结合机器与算法，提出相应的性能评测指标，为设计高 效的并行算法提供依据。 并行计算机语言：与传统的机器语言不同，并行计算机语言依赖于并 行计算机，并行计算机语言必须简洁，编程容易，可以有效地实现，目前 的语言有：p v m 、m p i 、i - i p f 等，而且新的编程语言与编程模式正在不断地 出现。 并行编程环境与工具：为了使编程容易，必须开发综合的编程环境与 工具，且能达到两个目的：并行计算机的底层机构对用户透明；为用户提 供设计与开发程序所需要的调试器与模拟器等工具。 并行程序的可移植性：可移植性为并行程序设计的主要问题，要求在 一台并行机上开发的程序不加修改或进行少量修改即可在另一台计算机上 运行。这一点为目前受到了广泛关注的重要课题。 并行计算机的自动编程：可否设计一个并行化编译器，使用户的串行 程序通过并行化编译器编译，直接可在并行机上运行。到目前为此，这种 编译器还不存在，而仅有一些半自动并行化编译器。 开展并行数值方法的研究是当务之急，也是一项长远的战略性任务， 应该积极开拓，持之以恒，不断创新，多出成果，努力使我国的并行计算 保持在一个较高的科学水平。并行算法的研究应该包含两个层次，一个是 算法和程序设计，一个是数值计算方法。 目前，对数值并行算法的研究已经涉及到线性代数方程组的并行直接 算法和迭代算法，偏微分方程的并行数值解法等。 1 3 多极展开法 n b o d y 问题是计算一系列星体或粒子之间相互作用力的问题。它有很 多领域的应用，例如在模拟星系中星体之间由于万有引力而产生的演变， 模拟离子在静电力作用下所产生的改变等。许多n b o d y 问题中，粒子之间 大量的作用力不可忽视，但是粒子间的作用力随着距离的增加而减少。分 级结构的f m m 算法是一种用于解决此类问题的有效的，准确的算法。 4 第1 章绪论 g r e e g a r d 和r o k h l i m 提出了解决n - b o d y 问题的a d a p t i v ef m m 算法。用 a d a p t i v ef m m 算法解决n b o d y 问题，可以获得有效的并行性能。使用两 种分割技术：递归的二分技术和c o s t z o n e 技术( 一种更简单的，更有效的新 技术，尤其是在较多处理器系统中更有效) ，可以使得解决n - b o d y 问题的 a d a p t i v ef m m 算法可以产生很好的并行性，尤其是在支持共享存储的多处 理系统中。f m m 是在深入研究i s a a cn e w t o n 在1 6 9 7 年提出的理论基础上 给出的：粒子间的作用力随着距离的增加而减小，在计算大量的粒子对某 一粒子的作用力时，如果距离足够远，这些粒子可以近似为一个等价的粒 子。目前应用最广泛而且最具有前途的解决n - b o d y 问题的算法是b h 算法 和f m m 算法，f m m 算法比b h 算法难于编程，但是提供了更好的误差控 制，拥有较好的渐进复杂度，尤其是对于均匀分布的问题。除了在n _ b o d y 问题中的应用，f m m 还具有很多的应用。 多极展开法即对求和项y 土近似计算的方法。计算的近似程度和展开 = c 的项数密切相关。在多体静电场问题中，对已知包含玎个电荷吼的单位立方 体内，每个电荷的位置为五，求解电荷之间的相互作用力类问题，直接计 算的计算量是o ( n 2 ) 阶的，当”增大时计算量将急剧上升。在物理研究领域， 这种繁琐计算经常是不可避免的。 将多极展开法应用于边界积分方程的迭代求解，可以追溯到r o k l i n 的论 文【1 q 。其广泛应用于线弹性和低雷诺数的液体动力学词题，在二维问题中 运算等价点是o ( 1 02 ) ，对目前的微机来说这一差别是非常有意义的。但一 直没有应用于三维椭圆边值问题中。这是因为f d m 适用于三维边值问题， 只有解题规模超过疗= o ( 1 0 3 1 04 ) 时才有意义。当时，唯有一个研究组研 究将f m m 应用于三维l a p h c c s 方程的相应边界积分方程中网。 最近，g r e e n g a r d 肃l r o k h l i n 提出了三维多极展开法，并且将其运算等价 点降为o ( n 2 ) 。在未来的微机上边界元程序将使f m m 更具吸引力。多极展 开法没有被广泛应用于t e l a p l a c e s 控制方程的边值问题，原因在于除了它 的控制方程不同外，还因为其它偏微分方程不像l a p l a c e s 方程直接涉及多 体静电学问题一样适应多极展开法不过，已有少数学者克服上一困难， s 燕山大学理学硕士学位论文 如g r e e n b a u m 等1 4 】对二维双调和方程的研究，p e i r c e 和n a p i e r f l 对二维线弹性 n a v i e r 方程的研究，s a n g a n i 和m o t 6 】对三维低雷诺数方程即s t o k e s s 方程的研 究等。他们成果的特点可归纳为使积分方程适应f m m t r l ，或者使f m m 适应 积分方程【8 】。并且，上述适应变换是繁琐而往往使问题特殊化。特别是 g r e e n b a u m e t a l 的近似方法，不能扩展到三维。s a n g a n i 和m o 提出的多极展开 法只适用于刚性质点不能扩展到三维线弹性问题。p e j r c e 和n a p i e r 给出的多 极展开法，计算效率较差。 近几年，国内学者对多极展开法的应用给予了积极的关注，如银燕即 等将多极展开法应用于无网格等离子体静电模粒子的模拟。王浩刚【1 0 】对多 极展开法中不变项的计算进行了优化。2 0 0 2 年，清华大学姚振汉教授课题 组率先将泰勒级数展开式适用于二维弹性问题边界元法中【1 1j ，成功地模拟 了复合材料不同粒子变形一应力场。与此同时，燕山大学的申光宪教授课 题组将静电多极展开式适用于三维弹性问题的边界积分方程中【1 2 1 ，完成大 规模轧辊辊型模拟计算。 1 4 课题的来源、内容和意义 本课题来源于河北省自然科学基金项目：“精密轧制过程模拟的边界 元法并行计算研究”。课题研究的主要内容有； 、 ( 1 ) 对求解矩阵特征值的过程进行了算法级的并行优化，利用并行多极 算法求解矩阵特征值，在改进算法的基础上，降低计算复杂度。 ( 2 ) 结合边界元，并行，和多极展开这三个领域，提出了并行三维位势 快速多极边界元法，并给出立方体闭域介质热流问题的数值算例。 本课题的研究，突破了传统串行算法的束缚，给出了并行矩阵求逆， 并行二维位势边界元法，并行多极法求解矩阵特征值，以及并行多极三维 位势边界元法，及其这些算法的具体实现，并对试验结果作了分析。本文 在理论上属并行计算及边界元法研究的领域前沿，具有重大的学术和现实 意义，工程应用前景宽广。 6 第2 章并行计算及并行程序设计 第2 章并行计算及并行程序设计 2 1 并行计算平台 2 1 1 并行计算机的控制结构 对并行计算机的分类有多种方法，其中最著名的是1 9 6 6 年由m j f l y m i 提出的分类法；称为f 1 y r m 分类法。f l y n n 分类法是从计算机的运行机制进行 分类的。首先作如下定义： 指令流( i n s t r u c t i o ns t r e a m ) ：机器执行的指令序列。 数据流( d a t as t r e a m ) ：由指令流调用的数据序列，包括输入数据和中间 结果。 ，f l y n n 根据指令流和数据流的不同组织方式，把计算机系统的结构分为 以下四类： 单指令流单数据流( s i n g l e i n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m , s i s d ) 。 单指令流多数据流( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m , s l m d ) 。 多指令流单数据流( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m , m i s d ) 。 多指令流多数据流( m u l t i p l ei n s t r u c t i o ns t r e a mm u k i p l ed a t as t r e a m , m i m d ) 。 s i s d 就是普通的顺序处理的串行机。s i m d 和m i m d 是典型的并行计算 机。 在一台s i m d 计算机中，有一个控制部件( 又称为控制单元，c o n t r o lu n i t ) 和许多处理单元q 舯c e s s i l l gu n i t ) 。大量的处理单元通常构成阵列，因此s i m d 计算机有时也称为阵列处理机。所有的处理单元在控制部件的统二控制下 工作控制部件向所有的处理单元广播同一条指令，所有的处理单元同时 执行这条指令，但是每个处理单元操作的数据不同。控制部件可以有选择 地屏蔽掉一些处理单元，被屏蔽掉的处理单元不执行控制部件广播的指令 7 燕山大学理学硕士学位论文 在m i m d 计算机中没有统一的控制部件。在m i m d 中，各处理器可以独 立地执行不同的指令。实际上，在s i m d 机中，各处理单元执行的是同一个 程序，而在m i m d 机上，各处理器可以独立执行不同的程序。在m i m d 中， 每个处理器都有控制部件，各处理器通过互连网络进行通信。m i m d 结构比 s i m d 结构更加灵活。s i m d 计算机通常要求实际问题包含大量的对不同数 据的相同运算( 例如向量运算和矩阵运算) 才能发挥其优势。而m i m d 计算机 则无此要求，它可以适应更多的并行算法，因此可以更加充分地开掘实际 问题的并行性。s i m d 所使用的c p u 通常是专门设计的，而m i m d 可以使用 通用c p u 。 2 1 2 并行计算机系统结构模型 从系统结构的角度来说，并行计算机一般可以分为6 类：单指令流多数 据流计算机为s i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 、并行向 量处理机为p v p ( p a r a u e lv e c t o rp r o c e s s o r ) 、对称多处理机为s m p ( s y m m e t r i c m u l t i p r o c e s s o r ) 、大规模并行处理机为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 ) 、工 作站机群为c o w ( c l u s t e ro fw o r k s t a t i o i l s 。n 咖o r ko fw o r k s t a t i o n s , n o w ) 、 分布式共享存储多处理机为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 ) 。这6 种中，除 了s i m d 外，其余5 种均属于m 【m d 计算机。例如：s i m d 计算机结构如图2 1 所示，其中p e 表示处理单元，p 表示处理器，m 表示存储器。 图2 1s 1 m d 计算机结构图 f i g 2 1t h es t r u c t u r ef i g u r eo f t h es i m dc o m p u t e r 8 第2 章并行计算及并行程序设计 s i m d 中通常包含大量处理单元p e ，而控制部件只有一个。控制部件广 播一条指令，所有的处理单元同时执行这条指令，但不同的处理单元操作 的数据可能不同。 大规模并行处理机：大规模并行处理机一般指规模非常大的并行计算 机系统，含有成千上万个处理器。它一般采用分布的存储器，存储器一般 为处理器私有，各处理器之间用消息传递的方式通信。大规模并行处理机 的互连网络一般是专门设计定制的。m p p 的结构如图2 2 所示，其中m b 表 示存储器总线，p c 表示处理器和高速缓存，n i c 表示网络接口电路，l m 表 示本地存储器。网络接口电路( n e t w o r k i n t e r f a c ec i r c u i t 珂, n i c ) 是用来将计算 机与网络( 例如局域网) 连接起来的接口电路。典型的n i c 包括一个嵌入式的 处理器，一些输入、输出缓冲器，以及些控制存储器和控制逻辑，它的 功能有；将消息格式化、路由选择、流和错误控制等。 图2 - 2 大规模并行处理机结构图 f i g 2 - 2t h es l a u c t u r ef i g u r eo f t h em p pc o m p u t e r 分布式共享存储器多处理机：分布式共享存储器多处理机的主要特点 是它的存储器在物理上是分布在各个结点中的，但是通过硬件和软件为用 户提供一个单一地址的编程空间，即形成一个虚拟的共享存储器。它通过 高速缓存目录支持分布高速缓存的一致性。d s m 与m p p 的区别在于存储器 在逻辑上是共享的。d s m 的结构如图2 - 3 所示，其中d i r 表示高速缓存目录， 9 燕山大学理学硕士学位论文 其它符号同前。 图2 3 分布式共享存储器多处理机结构图 f i g 2 3t h es t r u c t u r ef i g u r eo f t h ed s mc o m p u t e r 2 2 并行算法设计的基本原理 2 2 1 并发的类型 并行程序必须以某种形式给出任务的并行性，它们可以以下面的方式 给出： 2 2 1 1 数据并行这种类型的并行性表现为：并行的在不同的数据上进行相 同的操作，称为数据并行性表现出这种并行性的问题通常称为数据并行 的问题。数据并行问题的一个突出特点是对大多数的这类问题，数据并行 性的程度( 可以并行进行数据并行的操作数目) 随着问题规模的增加而增大， 这意味着对于这类问题，可以用较多的处理器来有效的处理更大规模的问 题。 2 2 1 2 任务并行通常来说，很多的予任务都可以并行的执行。这种并行性 表现为子任务的并行执行，因此被称为任务并行性。任务并行性比数据并 行性要复杂一些( 实际上，用任务并行性完全可以描述数据并行性的问题) 。 2 2 1 3 流水并行流水并行性是指在同一个数据流上同时的执行多个程序 ( 后续的程序处理的是前面程序处理过的数据流) 。流水并行性通常也被称为 流水线在流水线上，计算的并行性表现为：每个处理器上运行一个不同 l o 第2 章并行计算及并行程序设计 的程序，它们构成一个完整的处理流程，每个处理器把自己处理完的数据 马上传递给( 逻辑上) 的下一个处理器。这样实际上形成了处理器间的一个流 水线，因此称为流水并行性。 2 2 1 4 混合并行很多的问题中的并行性表现为数据并行性，任务并行性和 流水并行性的混合。某个问题表现出的流水并行性通常独立于问题的规模， 而任务和数据并行性则相反，它们通常会随问题规模的增长而增长。通常 情况下，任务并行性可以用来开发租粒度的并行性，而数据并行性用来开 发细粒度的并行性，因此，任务并行性和数据并行性的组合可以用来有效 的开发应用在大量处理器上的并行算法。 2 2 2 分解技术 设计并行算法的一个基本的步骤是描述完成给定任务所需要的计算， 并把这些计算分解为可以并行执行的子任务集。一个好的任务分解应该具 有下面的特点： ( 1 ) 它应该有很高的并行度。 ( 2 ) 子任务间的交互( 通信和同步) 应该尽可能的少 2 2 2 1 递归分解递归分解通常用来对采用分治方法的问题进行任务分解。 这种方法将任务分解为独立的子任务，这个分解的过程会递归地进行；问 题的答案是所有的子任务的答案的组合。分治策略表现出一种自然的并行 性。 2 2 2 2 数据分解对那些具有大型数据结构的算法来说，数据分解是一种非 常有用的方法。它可以分为两个步骤。第一个步骤中，对计算操作的数据( 或 称为域) 进行划分，第二个步骤根据数据的划分来将对应的计算组织成相应 的子任务 ， 一般的来说，当我们需要决定对数据如何划分或者是对那哪些数据进 行划分时，我们需要看哪一种划分能够得到一个最好的( 或者最简单的) 计算 划分因为数据划分的目的只不过是为了得到种合理的计算划分对有 些问题来说，对输入数据进行划分效果比较好，而对有些问题，对输出数 燕山大学理学硕士学位论文 据( 计算结果) 进行划分要更好一些。在使用数据分解的时候，需要对所有可 能的数据划分方式进行考察。 2 2 3 任务的分配：任务映射与负载平衡 任务映射：上一节中讨论的分解算法可以用来识别出问题中可以提供 的并行性，并且把计算分解为可以并行执行的子任务。要完成对问题的计 算，下一步是将这些子任务分配给可用的处理器来执行。给出一个子任务 集和一个可用处理器集，有很多种可能的方法来在它们之间建立某种映射 关系，为了判断哪种映射更好，我们需要使用下面的评价标准： ( 1 ) 分配给每个处理器的计算任务应该均衡，这样才能减少处理器因为 等待其它处理器完成计算任务而造成的空闲。 ( 2 ) 不同处理器之间的交互应该最少，这样处理器可以用更多的时间去 完成有效的工作。 负载平衡：并行算法设计中使用的负载平衡技术可以分为两类：静态 负载平衡与动态负载平衡。静态负载平衡技术在算法的实际执行前将计算 任务分配给处理器；而动态负载平衡在算法的实际执行过程中将计算任务 分配给处理器。 2 3 并行算法的一般设计方法 ， 设计并行算法一般有3 种方法：第一是检查和开拓现有串行算法中固 有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但 对很多应用问题仍不失为一种有效的方法；第二是从问题本身的描述出发， 根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难 度，但所设计的并行算法通常是高效的；第三是借助已有的并行算法求解 新问题。 2 3 1 串行算法的直接并行化 通过长期的研究与摸索，人们已经设计和积累了大量的串行算法。这 些串行算法在解决实际问题中是十分有效的。如果能将串行算法并行化， 1 2 第2 章并行计算及并行程序设计 那么这些串行程序也有可能通过少量的修改而直接变成并行程序。许多并 行编程语言都支持通过在原有的串行程序中加入并行原语( 例如某些通信命 令等) 的方法将串行程序并行化。因此，在已有的串行算法的基础上，开发 其并行性，直接将其并行化是并行程序设计中优先考虑的方法。 直接并行化已有串行算法时要注意两个问题：第一，并非所有的串行 算法都可以并行化。某些串行算法有内在的串行性，比如在某些串行算法 中，每一步都要用到上一步的结果。只有当上一步完全结束后，下步才 能开始。这样，各步之间就不能并行，只能考虑其它的并行化办法。第二， 好的串行算法并行化后并不一定能得到优秀的并行算法：另一方面，不好 的串行算法并行化后也可能是优秀的并行算法。例如，串行算法中是没有 冗余计算的i 但是在并行算法中，使用适当的冗余计算也可能使并行算法 效率更高。加入冗余计算的并行算法就可能比直接由串行算法并行化得到 的算法效率高： 直接并行化的关键在于分析和暴露原有串行算法中固有的并行性。直 接并行化也不是机械的，完全直接的。有时为了暴露算法的并行性，要对 串行算法进行一些适当的改动。总之，要在保证算法正确性的前提下，尽 量提高算法的效率。 科学和工程中有大量数值计算问题。针对这些问题，人们已经设计出 了许多串行数值计算方法。在设计这些问题的并行算法时，大多采用串行 算法直接并行化的方法。这样做的一个显著优点是：算法的稳定性、收敛 性等问题在串行算法中已有结论，不必再考虑。 2 3 2 从问题描述开始设计并行算法 ， 一些串行算法有内在的串行性，很难直接并行化。此时只能从问题本 身出发，直接设计并行算法。研究与设计一个新的芽行算法是一项具有挑 战意义的创造性工作，往往比较困难。它要求算法设计者对问题本身有比 较深刻的了解。但是，由于直接设计算法是直接从问题的特性出发，通常 可以得到很好的并行算法。 1 3 燕山大学理学硕士学位论文 2 3 3 借用已有算法求解新问题 “借用法”是指借用已知的某类问题的求解算法来求解另一类问题， 而这两类问题表面上可能是完全不同的。因为这两类问题完全不同，所以 初学者很难联想到被借用的方法。使用借用法需要很高的技巧，同时算法 设计者要有敏锐的观察力并且在并行算法方面有丰富的经验。 2 4 并行程序设计 2 4 1 基本要素的定义 进程( p r o c e s s ) ：进程是并行程序中的基本计算单位，它对应于有相应代 码段所执行的操作。程序是一些进程的集合。进程控制是指对诸进程进行 管理，其主要功能有：进程管理、进程调度和进程保护。费时的进程称为 重量级进程，反之为轻量级进程，又叫做线程( t h r e a d s ) ，为统一起见，约 定任务= 进程= 重量级进程。轻量级进程= 线程。 线程：线程是控制流线的简称，就是被执行的一个指令序列。 进程间相互操作表现为通信和同步。 通信：通信是指进程之间的数据传输。 同步：同步是进程之间相互等待。同步操作有三种：原子性、控制同 步和数据同步。 2 4 2 并行程序 2 4 2 1 并行编程风范并行编程风范( p a r a l l e lp r o g r a m m i n gp a r a d i g m s ) 是指 构造运行在并行机上的并行算法的方法。目前主要有以下五种方法，它们 既可以单独使用，也可以组合使用。 相并行( p h a s ep a r a l l e l ) 是一个并行程序由一些超级步组成，每个超级步 内，各个进程执行独自的计算，然后进行交互作用。如图2 - 4 ( a ) 所示，其优 点是方便差错和性能分析，其缺点是计算和交互作用不能重叠，所以在实 际使用中存在很大的局限性。 1 4 第2 章并行计算及并行程序设计 分治并行( d i v i d ea n dc o n q u e rp a r a l l e l ) ，如图2 - 4 泐所示，父进程将负载 分成小的负载指派给子进程，这些子进程并行的完成各自的计算，其结果 由父进程加以归并。其缺点是难以达到负载的平衡。 流水线并行( p i p e l i n ep a r a l l e l ) ，如图2 4 ( c ) 所示，一些进程形成流水作 业法，诸进程在流水线的不同地段同时重叠的执行操作以达到整体并行的 效果。 主从并行( m a s t e rs h v ep a r a l l e l ) ，如图2 - 4 ( d ) 所示，一个主程序执行并 行程序的串行部分并形成一些同时并行执行计算的子进程；当某一子进程 完成计算后就报告给主进程，主进程再分配新的任务给它。整个的协调工 作由主进程完成，其缺点是主进程易成为系统瓶颈。 工作池并行( w o r kp o o lp a r a l l e d ，如图2 - 4 ( e ) 所示，开始时池中只有一 件工作，任何空间的进程都可以取出并执行之，执行中可能产生一个或多 个新工作并把它们放回池中，供别的空间进程受领之，当池中变空时则并 行程序结束。这种并行的优点是容易达到负载平衡，然而实现工作池被多 个进程有效的访问比较难。 2 4 2 2 并行程序设计模型并行程序设计模型( p a r a l l e lp r o g r a mm o d e l ) 是一 种程序抽象的集合，它给程序员提供了一幅计算机硬件软件系统透明的简 图，程序员利用这些模型可以设计并行程序。主要有隐式并行和显式并行。 隐式并行：程序员不明确地指定程序的并行性，而让编译器和运行支 持系统自动开拓它。隐式并