（电力系统及其自动化专业论文）面向并行自适应算法的网格库设计.pdf

华中科技大学硕，士学位论文 a b s t r a c t t h e i m p r o v e m e n to ft h es e r i a ls t r u c t u r eo fm e s hr e p r e s e n t a t i o nu s e di nt h es o f t w a r eo f e s i a ( e n g i n e e r i n gs y s t e mi n t e g r a t e da n a l y s i s ) i si n t r o d u c e dd u r i n gt h ed e v e l o p m e n to f p r e s i a ，ag u ia p p l i c a t i o no fe s i a ，a n dt h ei m p r o v e m e n ti sp r o p o s e df o rf u r t h e ra n a l y s i s a n dc o n t r a s t w es e t u pap a r a l l e lm u l t i p l a t f o m l p a r a l l e le s i a b a s e do nl a m m p i + 十a n d t h ei m p l e m e n t a t i o ni sd i s c u s s e di nt h i sp a p e ri nd e t a i l t h et h e o r ya n di t si m p l e m e n t a t i o no fg e n e r a lp a r a l l e l d i s t r i b u t e dp l a t f o r mb a s e dm e s h l i b r a r yp e s i aa r cp r o p o s e di nt h i sp a p e r p e s i ac a r ls t o r ea n dm a n a g et h em e s hd a t au s e d i nt h em e s h b a s e da p p l i c a t i o n se f f i c i e n t l ya n dc a np r o v i d eu s e r sw i t ht h eu n i f i e d ，e a s y u s e d c l a s si n t e r f a c e a f t e rr e v i e w i n gt h ed a t as t r u c t u r eo fm e s h b a s e da p p l i c a t i o n s ，w ei n t r o d u c e a ni m p r o v e ds e r i a lm o d e la n di t se x t e n s i o nt op a r a l l e ls t r u c t u r e w ed i s c u s st h es p e c i a ld e s i g nr e q u i r e m e n to ft h ea d a p t i v ec o m p u t a t i o no fd a t a s t r u c t u r e ，c o n s i d e r i n gt h ec h a r a c t e r i s t i co fp a r a l l e l d i s t r i b u t ec o m p u t a t i o ne n v i r o n m e n ta n d a l g o r i t h m t h el o a db a l a n c ea l g o r i t h mu s e di nt h i sm e s hl i b r a r yi s a l s os u p p o r t e da n d s h o u l db es p e c i a l l ya d d r e s s e d f u r t h e rm o r e ，w ep r o p o s eam e t h o dt oi m p l e m e n tt h e d y n a m i cl o a db a l a n c es t r a t e g y i t i sa k e yp o i n tw h a ti st h em o d e lo fp e s i aa n dh o w i tw o r k s a t i e rr e f e r e n c i n gt h e t h e o r ya n dd e s i g no fo t h e rm e s hl i b r a r i e s w ea n a l y z et h ec o n c e p tm o d e lo fp e s i aa n d t h e i m p l e m e n t a t i o nm o d e l t h e0 0 pa n ds t lt e c h n i q u ea r ed i s c u s se i t h e r t h ep a r t i t i o n s t r a t e g yu s e di nl a m m p i + + i ss o m e h o ws t a t i ca n d i td o e sn o tp r o v i d e d y n a m i c s u p p o r t f o rt h ea p p l i c a t i o nr e l i e do n w eh a v ei m p l e m e n tt h eu s e ri n t e r f a c ca n dc a l b a c kf u n c t i o no f p e s i aa n dw ew i l ld i s c u s st h e me i t h e r a tt h ee n do ft h i sp a p e lw es h o wh o wp e s i a w o r k sw i t ht h r e ee x a m p l e sa n dt h er e s u l t sw e r ea n a l y z e da n dc o n t r a s t e df o rf u r t h e r u n d e r s t a n d i n g k e yw o r d s ：p a r a l l e lc o m p u t a t i o n m e s h a d a p t i v ec o m p u t a t i o n f i n i t ee l e m e n t i i 华中科技大学硕士学位论文 1 1 课题背景 第一章绪论 结构化和非结构化计算网格技术被广泛地应用在有限元计算【1 、数字仿真系统 f 2 】、虚拟现实1 3 l 等数值计算仿真领域中。在这些数值计算中的网格类型、数目根据 不同的分析对象及应用场合会有较大的差异。也就足说，这些计算中的网格所表示的 空问的数据结构通常是不规则的。因此，女i i f , , j j l ：发个i 百向具体应用的网格数据模型， 以有效地表达、存储和管理这些类型数目各异的空间网格就成为网格计算仿真软件开 发的一个重要课题。 随着人们对数值计算仿真要求的不断提高，数值计算软件的计算能力诈面临着严 峻的考验。为了提高这些数值计算软件的计算能力，国内外众多学者f 在将并行技 术引入到数值分析软件中并取得了许多重大成果【l 】。但是，人们在将并行计算技术引 入数值计算软件的同时也给空间网格数据的表达提出了新的更高的要求。适用与并行 环境的网格库不仅要求对计算模型空间结构的有效表达、合理存储和简便管理，同时 还要求在并行运算的多个计算分区问保持网格数据的一致性和简捷性。 随着人们将计算自动化技术以及将“设计一分析一制造”一体化技术引入到数值 分析软件中，网格自适应策略也越来越多地被应用到数值分析软件中。人们希望在分 析和计算过程中通过对网格局部参数的自动调整在计算精度和计算速度上取得折中。 进一步地，如果要求在并行环境中应用网格自适应算法，还要保证网格库能够提供在 并行网格分区内及分区边界上局部网格进行自动调整的支持，同时确保所表达网格数 据的一致性和实时性。 近年来，随着并行技术的迅猛发展，计算结点上负载平衡问题也得到了学者们的 广泛关注。如何测量及评估计算结点上的计算负载? 如何在并行软件中平衡这些负 载? 进一步地，如何确定参与计算的结点个数以及如何选结点以达到计算量的最优分 配? 这些都成为j f , j ：i ；i 算研究中的热点问题1 4 l 。具体地来说，基f 刚格的数值分析软 什同样需要考虑负载平衡问题；其中的网格库也需要提供相应的负载计算模型。 华中科技大学硕士学位论文 另一方面，由于数值分析软件的特殊性，它对空| 、日j 数掘结构的依赖性非常显著 5 。 然而，日阿对这些软件的丌发、研究人多仪天注其实现的县体算法上，而刘一j 二如何有 效地组织这些空问数据往往并不重视。许多早期的数值分析计算软件【1 】仅仅将这些空 间数据简单的通过静态或者动态数组的结构“列表”存储在存储器中。虽然这种数据 组织方式对于某些特定的问题在特定的计算环境中是简捷且有效的，但是随着上述新 的汁算技术的引入，这些简单的数据表达方式越来越显现u ：其不能适应新需求的弊 端。研究数值计算的学者们也逐渐丌始关注这个问题，并提出了许多新的有效的思路 【6 】。 总之，并行计算技术、自适应计算技术、动态负载平衡技术的引入，使数值分析 软件对空间网格数据表达方式的要求越来越高。本文试图探讨一种利用o o p 及s t l 技术进行的网格空问数据表达、存储及绷织的方法，并通过实例对比说明其优点。 1 2 课题研究历史和现状 1 2 1 并行，分布式计算环境 早期计算机的工作方式都是串行的，其上执行的计算任务也都是串行计算。传统 的串行计算，分为“指令”和“数据”两个部分，在程序执行时“独立地申请和占有” 内存空问，并且所有计算均局限于该内存空问。并行计算将计算进程相对独立地分配 到不同的计算节点上，山各自独立的操作系统凋度，享有独立的c p u 和内存资源( g , j 存可以共享) 。结点、进程间的信息交换通过消息传递机制来实现。 串行计算机的计算能力可扩展性较差：在串行计算平台确定之后，其计算能力有 一个明确的上限。由于计算平台升级和更新的周期较长、成本较高，串行计算平台的 发展远远无法满足人们对计算能力的增长【7 。并行计算机的研制就是为了适应这种计 算要求的增长，它诞生的标志是7 0 年代超级计算机i l l i a c i v 和c r a y 1 的研制成 功。 以c r a y 1 为代表的向量机和以i l l i a c 。i v 为代表的并行机之间的竞争，是7 0 年代计算机界的热门话题。这是超级计算机历史上第一次有关可扩展性与可编程性的 较量，最后以向最机的胜利而告终。从j l e ，并行计算机沉寂多年，而以c r a y 为代表 华中科技大学硕士学位论文 的向量机则称雄超级计算机界十几载。 8 0 年代后期，向最机的造价越来越高，而性能提高茸j 越来越难。c r a y 3 的时钟 周期为2 n s ，c r a y 。4 为i n s 。在这种形势下，并行计算机再一次得到广泛的关注。随 后，在1 9 9 0 年的超级计算机大会上，h i l l i s 博士公丌宣称：“传统的巨型机( 向量巨 型机) 5 年内将被淘汰”。9 0 年代初，s g i 推出了一个具有共享存储的s m p 结构的并 行计算机，具有可编程性，成为并行计算的主流技术。 最近几年，超级计算应用领域对计算机性能的需求飞速增长，不仅向量机不能担 此重任，s m p 和p v p 也已力不从心。在1 9 9 6 年1 1 月公御的t o p 5 0 0 中，m p p 仍呈 上升趋势，而s m p 出现了转折，呈下滑之态。并行计算机向何处去? 美籍并行处理 专家黄铠教授早在1 9 9 3 年就指出：“并行处理的发展趋势是用分靠式共享存储结构 ( d i s t r i b u t e ds h a r e dm e m o r y ，d s m ) 和标准u n i x 来构造可扩展超级计算机。”即并 行计算机发展的趋辨既不是s m p ，也不是m p p ，而是两者优势互补的d s m 。 随着网络技术的迅速发展，今年来，基于高速网络技术的分和式计算也得到了迅 速的发展。分布式计算，即“n 层”计算，是一种新兴的模式，它允许应用程序要素 在网络的不同的硬件平台上运行。通过在分布式计算环境下使用构件技术，应用程序 设计人员不必再对软件的位置只做出一种决定，然后将其用于所有用户。构件可以在 网络内的不同平台上运行，用户可以不知道构件的物理位置。s u n 公司的“网络即 计算机”的说法终于成为现实。如果用户的台式机计算资源有限，他可以依靠在服务 器或大型机上运行的构件，而更强大的工作站用户则可以选择在本地运行一个应用程 序的更多的构件。可以说，分布式计算是未来应用并行技术进行计算的计算平台发展 方向。 总之，并行分布式计算环境的发展有由向量机向并行机、由主机并行计算向网络 分布式计算、由同构组件向异构组件发展的趋势。相应的，基于并行环境的计算程序 也越来越多地应用消息传递机制( 如d c o m ，l a m m p i + + 等) 进行组建。这是由于 这种机制能够同时适用于并行机以及网络计算两种计算平台。 1 2 2 对并行分稚式计算网格数据表达的研究 数值分析软件中对网格数据的组织方式大致经历了由a r r a y - b a s e d 8 】的方式到 华中科技大学硕士学位论文 m e s h b a s e d 8 的方式再到f r a m e b a s e d 1 0 1 的方式。随着并行分彳| j 式平台的发展，基 于网格的数值分析程序也逐渐从单纯的数据存储结构向各种能方便集成各种算法的 网格库的方向发展。 m w b e a l p 8 1 和m s s h e p h a r d 在1 9 9 7 年提出的面向拓扑结构的网格数据结构。 这种结构虽然比较数组存储方案有了较大的提高，但是不太适应网格自适应等要求拓 扑结构经常变化的应用场合。s b a l s y 在其丌发的p e t s c 系统中应用c 语言构建面向 并行机制的数值计算框架，但是特定应用的数据及算法无法直接插入该系统，而只能 嵌入其提供的代码中。这些方法都是m e s h b a s e d 方案的典型实例。 p o o m a 系统和s a m r a i 引入了面向应用的概念，但是其提出的网格存储框架却 只适用于结构化的网格数据。j e n sg e r l a c h 1 0 等人则提出了一个基于网格的并行计算 通用c + + 框架，并在j a n u s 中得以实现。其最大的特点就是将c + + 的标准模版库引入 网格库的构建中，使得计算系统可以方便地处理不同类型的网格。j e a n f r a n c o i s r e m a d e 1 5 等人在其论文中提出并实现了一个面向串行算法的网格数据库a o m d ， 提出了一些设计中的重要概念，值得关注。其他值得特别关注的还有j d t e r e s c o 在 2 0 0 1 年发表的论文ah i e r a r c h i c a lp a r t i t i o nm o d e lf o ra d a p t i v ef i n i t ee l e m e n t c o m p u t a t i o n 中提出的针对f e m 的并行分区模型，作者针对并行分布式环境的特点 详细分析了对m e s h b a s e 方案的扩展。这些f r a m e b a s e d 方案j 下在讨论发展之中，并 且代表了今后网格库技术发展的方向。 另外，虽然并行自适应技术在数值分析的许多领域取得了成功 1 6 1 1 1 7 1 8 ，将它 应用在并行特别是分布式环境下却遇到了许多问题。例如，还没有有效的方法来解决 并行分区边界变动时网格数据一致性问题；还没有有效的方法解决动念负载平衡中网 格在分区间迁移的问题等等。这些都是今后网格库发展中要逐步解决的问题。本文也 尝试探讨在这些方面进行改进的一些问题。 1 3 课题研究内容和预期成果 1 3 1 研究内容 根据上述的课题研究背景以及相关研究的历史及现状，结合研究所( 华中科技大 华中科技大学硕t 士学位论文 学工程计算与仿真研究所) f 在进行的针对工程动态过程三维非线性有限元集成分析 软件e s i a ( e n g i n e e r i n gs y s t e mi n t e g r a t e da n a l y s i s ) 图彤化时处理器p r e s i a 的j l ：发 工作，我们深入研究了e s i a 软件前处理部分的网格数据表达形式并提出了相应改进 方案。 在进行p r e s i a 的图形化开发过程中，我们注意到：有限元计算软件前处理器应 该能够处理各种不同的网格类型和混合网格【6 】；应该能够在向用户提供对网格局部进 行增加、删除、修改操作的同时减少对整体网格的遍历次数：应该尽量避免或减少【b 于局部几何拓扑的变化导致的前处理程序网格的重新划分；应该在保持原有映射网格 生成算法灵活、高效的同时为自动网格生成算法提供数据支持和接口支持；应该能够 在并行环境中运行e s i ai ； 处理程序；应该能够提供e s i a 前处理器针对网格细化( 或 粗化) 的自适应算法支持。 基于上面的考虑，我们设想首先在通用并行分夼式平台上丌发一个支持这些功 能的网格库同时兼容e s i a 原有的数据格式。以逐步替换e s i a 原有的对网格数掘的 组织方式。我们的具体工作包括： ( 1 ) 分析e s i a 存储方式及其改进方案 ( 2 ) 研究网格库运行在串行并行平台的特点 ( 3 ) 研究自适应算法和负载平衡算法对网格库提出的特殊要求 ( 4 ) 研究利用l a m m p i + + 实现分布式多平台的方法 ( 5 ) 研究利用c + + 实现这个网格库的方法 1 3 2 研究预期成果 ( 1 ) 开发的面向算法的网格库能准确表达用于串行数值计算的网格数据 ( 2 ) 丌发的面向并行算法的网格库能准确表达用于m p i 平台并行数值计算的网格 数据 ( 3 ) 网格库能够支持特定的网格划分自适应算法 ( 4 ) 网格库能够实现简单的动念负载平衡，相对效率有所提高 华中科技大学硕士学位论文 1 4 章节安排 论文各章的安排如f ： ( 1 ) 第一章( 即本章) 为本文的绪论，主要对课题的背景、意义以及研究内容进 行综述； ( 2 ) 第二章首先定义本文用到的术语符号，然后了介绍串行网格和并行网格的表 达力式及符臼的特点； ( 3 ) 第三章介绍了并行分布式计算平台和技术的基本概念并探讨了针对网格数值 分析软件的特点实现并行自适应算法的途径，最后介绍在并行平台的网格库 中实现负载平衡的相关问题； ( 4 ) 第四章是本文的重点，着重讨论了利用o o p 技术和s t l 技术进行面向并行自 适应网格库p e s i a 设计的概念模型及其实现模型并讨论如何提供高效用户接 口的方法； ( 5 ) 第五章介绍了利用本文讨论的网格库进行的网格表达及计算的几个实例： ( 6 ) 第六章总结了本文的研究工作并做出展望； 论文最后部分是参考文献列表以及作者攻读硕士研究生期间发表论文的列表。 6 华中科技大学硕士学位论文 2 1 基本术语符号定义 第二章计算网格 为了讨论的方便，我们先本文中将要用到的一些重要的术语符号定义如下 符号术语意义 m 表示计算网格的一个实例 m ( i , j )表示一个网格实体，其中i 表示实体的编号，j 表 示实体的维数。 n ( m 0 ) ) 表示网格m 中j 维实体的总数 n ( m ，d ，q )表示网格- i 柴d 维实体的q 维邻体j i 均数日 n b n ( m ) 表示嘲格m 的j f 均邻体数日矩阵 r l ( m ，d ，q )表示网格表达m 中d 维实体的q 维邻边是否在实 体每一个m ( i j ) 中都有直接的表达【指针、引用等) r l ( m ) 表示邻体直接访问矩阵 p i表示第i 个计算分区 b o u n d a r y m ，p i ，p j )表示在网格m 上分割并行区域p i 与p j 之间的边 界 a d d r ( p i ，m ( i j ) )表示分区p i 内的网格实体m ( i 0 ) 的网格局部地址 m e s s a g e m ( i , j ) ，m ( m ，n ) 】表示从实体m ( i j ) 到m ( m ，n ) 的消息 2 2 几何模型的表示 表2 1 1 基本术语表 工程应用中的几何形体尽管千差力别，但大体上可以分为两类：流形几何和非流 形几何。 华中科技大学硕士学位论文 b ) 非瀛形几何 图2 2 1 流形几何和非流形儿何 顾名思义，流形( m a n i f o l d ) 是多片多层的意思。每一片都可看作平坦的，然后 一片片的拼接起来，形成我们所研究的几何对象【2 0 】。在局部都具有欧式几何结构， 从而可以引入坐标，但注意一个点可能出现在两个以上的片中，也就会有两个以上的 坐标，因此要有坐标的协调和转换，反映在几何上便是各种的拼接方式。除了流行几 何外的其他几何形体都可以划为非流形几何的范畴。 2 2 1 流形几何 流形几何的表达方式比较简单，一般地，通常采用基于边界的方案 2 0 】：几何形 体被划分为相同坐标下的各维( d i m e n s i o n ) 几何。其中，d ( d o ) 维几何体可以由d l 维几何组成的边界表示；0 维几何体就是几何体上单独点。可以参考相关文献 【2 0 2 1 1 1 2 2 】了解流形几何的常用表达方法。 2 2 2 非流形几何 工程实际应用的几何形体大都是非流形几何，它的表达方法要相对复杂一些。已 经有很多成熟的方法又来有效地表示非流形几何模型。例如，k w e i l e r 在其论文中深 入探讨了对非流形几何的表达方法。他采用r e g i o n s h e l l f a c e l o o p - e d g e - v e r t e x 构成 的树型拓扑结构表达的非流形几何形体能有效地进行各种几何拓扑变换及图形操作。 2 2 3 几何模型离散化一网格 网格( m e s h ) 是对几何区域的离散化。我们在利用网格这个离散化的数据表达实 际几何形体的时候要注意的最主要的原则就是两者的一致对应关系 2 0 】。网格要尽可 能准确地反映其对应几何物体的几何空阻j 结构，同时还需要针对具体的问题做出取 舍。 华中科技大学硕r 士学位论文 2 3 串行网格模型的表示 对于应用在串行计算中的网格m ，我们可以用几种不同的方式对其空问拓扑的构 成、相互关系以及定义其上的物理属性加以描述。 计算网格可以被简单地区分为结构化网格( s t r u c t u r em e s h ) 【1 1 和非结构化网格 ( u n s t r u c t u r em e s h ) 。在结构化网格巾，面( f a c e ) 和单元( c e l l ) 之m 排列和相对关 系类似一个矩形或立方体结构。网格中的相邻结点之阳j 有确定的儿f u j 关系。例如，在 下图的结构化网格中，结点e ( i j ) 右边的相邻结点是p ( i + l , j ) ，【二而的相邻结点是 p ( i j + 1 ) ；在规则的二维结构化网格巾，每一个内部结点有四个与之相连的内部结点。 不规则的结构化网格可以看作是规则的结构化网格进行拉伸压缩变化后的网格。对于 结构化网格，我们可以利用简单的二维或三维表“依序”存储所有结点信息。这是许 多基于结构化网格的数值分析软件( 如e s i a ) 存储网格数据的方法。非结构化网格 也是常用于数值分析的网格形式，他提供了更加灵活的表达复杂几何形体的方法。这 种网格可以由各种形式的单元组成，如三角形单元、四边形单元、四面体单元、六面 体单元等。出于结点之间没有了特定的逻辑联系，单元之间的关系必须显示地声明。 因此，一个特定结点相邻结点的数目同其他结点可能有较大的不同。作结构化网格的 拓扑结构较为复杂，而且现代数值分析软件大量采用非结构化网格，因此对于非结构 化网格存储结构的研究将是本文的重点。 结构化罔格 f t l ，j ) 1 。l + 1 一 i ，j 7 i + 1 生标列衰 n o d o l 非结构化网格 6 n o d e 7 x 2y 2 n o d e 6x 6v 6 单元判衰 e l e m e n l la u a d1234 e l e m e n t 2t r i354 8 4 0 m o n t 3t r i456 图2 3 1 结构化和非结构化网格 9 华中科技大学硕士学位论文 我们可以利用所有网格实体( e n t i t y ) 及实体问相互关系的“全集”刘网格加以 描述。这种方法虽然能够将算法对于网格数据结构的依赖关系减少到最小，卸1 i 町能 在实际的系统中得以完全实现：计算机有限的存储能力和求解问题的不可预测复杂性 都不允许在实际系统中存在这样的全集。 实际上，大多数的实际应用中的网格表达的大都只是上述全集的子集。这些子集 定义在各种不同的数值算法范围上。例如网格生成、网格细化( 粗化) 、载荷( 边界) 定义、差分( 变分) 方程式求解以及汁算结果后处理等中应用算法都有自己不同的子 集。 图2 3 2 不同过程有不同的表达子集 早期的有限元软件有完全区分开来的前处理、求解和后处理程序( 通常是三个独 立的应用程序) 。他们分别运行在独立的进程空间，前后有相承相继的逻辑关系，各 有不同的网格表示子集( 如图所示) p r e p r o m 、c a l p r o m 矛l jp o s t p r o m 等。他们 之问通过文件交换的方式交换网格数据。但是，现代有限元分析软件通常要求这三个 不同的过程能够共享相同的逻辑存储区域以进行一些前后联系的操作( 如自适应计 算) 。 对各个网格数据子集进行表达的方法大体上分为两类：( 1 ) 完全表达所有算法要 使用的数据；( 2 ) 部分表达所有算法要使用的数据，在需要的时候由已有的数据生成 新的数据。 2 3 i 常用的数据结构 对上述数据的表达可以采取不同的数据结构，例如数组、链表、拓扑树、集合等 等。但是，采用不同的网格数据结构对于网格数值分析算法实行性的影响是不同的。 m wb e a l l 和m s s h e p h a r d 在其论文ag e n e r a lt o p o l o g y b a s e dm e s hd a t as t r u c t u r e 8 】 o 华中科技大学硕士学位论文 中描述了种基r 网格几何拓结构的描述疗法，并比较t 也f f j 在数据存储和执行效率 l 二的i ：1 1 1 。i ，) 外，m i t 的j u s t i nl e g a k i s 捉ri 个桀于边翼结点( w i n g e d - e d g en o d e ) 的非结构化网格表示方法，并在l a t h 软件l 1 得以实现。 图2 3 1 3l a t h 的三种不同网格表达方式 华中科技大学硕t 士学位论文 在其论文中，b e a l l 所描述的拓扑结构将网格的了窀问拓扑关系同数据逻辑存储天 系联系起来，所有的i 种方式都“完整”表达了整个刚格中不同实体的结构，幽此小 可避免的存在不少冗余的信息。b e n i 的这种方法虽然能够减少算法访问数据的时f l i j ， 但对于维护数据的简捷性和一致性却不定是最好的疗式。例如上图中的l e g a k i s 边 翼结点模型虽然“简捷”表达了网格的拓扑结构，但山1 二是“阳j 接”的表达方式，实 际存储结点和存储实体并不没有重合。这对网格局部修改算法( 如增加、细化、删除 等) 的实现造成了不小的困难。 2 3 2 改进的数据结构 从上节的分析中我们可以看出：网格表达的结构简捷性和算法的可操作性总是 对相互制约的因素。如果采用的模型很简捷地表达了网格的拓扑结构，则算法必须相 戍地增7 j f f 搜索、重矬等额外的过程：反之，铭法就会简，弘得多。这就是汁钎科学f f f “窄 l l l j 一时问”的矛盾统一体在数值分析软什i t 的jl 休休王见。那么，如何j 能n 鹏栉之川 达到最好的平衡呢? 如何根据不同情况采用不同的网格表示模型呢? 我们需要首先 分析数值分析软件的特点。 有限元等数值分析软件在不同的计算阶段对于网格数据的要求是不同的。例如， 在前处理阶段引用极多的实体间层次性的拓扑关系在求解阶段通常不会被用到；而在 求解阶段需要直接反映的单元特性数据在前处理中就很少涉及。也就是说，针对不同 的算法所需要的网格表达子集是不同的，而这些集合在一定情况下可以互相转换。因 此，我们可以没想丌发一个丽对算法的网格表示模型。这个模型能够根抒 网格上应厂h 算法的不同并依据用户程序的要求动态地调整其中的网格信息数据。另外，需要注意 的是，这个模型还应该能够直接反映网格的空间拓扑结构以方便算法操作。下面，我 们首先定义几个基本概念： 网格实体( m e s he n t i t y ) 是网格模型中的基本逻辑单元，也是基本的存储单元。 主要包括：零维顶点( v e r t e x ) 、一维边( e d g e ) 、二维面( f a c e ) 和三维体( r e g i o n ) 。 我们用m ( i j ) 表示个网格实体，其中i 表示实体的编号，j 表示实体的几何维数。 华中科技大学硕士学位论文 图2 3 4 网格实体 网格邻体( m e s ha d j a c e n c y ) 是网格中特定实体的相邻实体。需要注意的是，这 晕的“相邻”指的是直接相邻而中问没有其他任何维实体相隔。对于m ( i ，j ) 而吉，其 相邻实体m ( p ，q ) 分为三类：上级邻体( q j ) 、同级实体( q _ j ) 以及下级实体( q ( 的变 化。f n 足网格进行迁移的图解。引起网格迂移的原因可能是山j 二自通鹰操作0 i 起f f j 分区问负载失衡，也呵能是为了特殊边界( 如边界含有儿何空腔) 而做出的局部凋整。 边界恢复( r e c o v e r ) ，就是在进行边界迁移之后重新根据分区网格邻接直接访问 矩阵r l ( m ) 恢复边界处网格实体的邻接关系。f 图表示了网格迁移的一个实例。 ，i：，贮 图2 4 3 网格迁移过程 引入了这些概念之后，我们的网格模型也要作一些调整： 首先，网格实体中要能存储其所属分区的信息。这样才能执行分区的建立和初试 化工作，也为网格迁移提供基本信息。网格实体的分区信息由负责并行计算的全局进 程进行管理和分配，如负载分配进程等，一般由并行计算的主结点进行。 其次，分区边界上的网格实体必须存储自身在其他分区拷贝的所有局部地址，这 样不仅可以区分出网格边界，也能够执行串行计算网格上的算法而不需要进行过多的 调整。这是由于，在引入了局部地址后，上层算法并不需要知道f 在操纵的网格是在 哪一个分区上，是否在分区边界上。这些区分、边界的判断工作都有网格实体自己进 行了处理了。 例如，运行在p l 上的算法a l 要对m ( u ) 进行操作( 注意，这里的m ( i j ) ) 可能 查墨全塑堡! ：旦整虚堕丝盒垄奎垫窒回呈! 查垫坚垡2 星查查垄：塑墨至查垄塾堡旦 2 0 华中科技大学硕士学位论文 给a l 说明操作小町执行：如果存在就进步判断是否存在其他分区拷n ! ，没有就如 串行分区那样处理，否则就判断其状态，待其空闲时对其进行锁定( 通过局部地址发 消息给所有其他分区拷贝) 后进行同串行算法一样的处理。处理结束后发出消息通知 其他分区的所有拷贝进行实体更新并解除锁定。下面是这个过程的流程图： 图2 4 4 网格操作流程图 显然，正在运行的算法a 1 只用判断操作是否成功就可以了，而不必知道分区的 存在。这对于算法独立和算法移植是非常有意义的。 华中科技大学硕，士学位论文 再次，网格实体必须存储一个自身的引用计数器( r e f e r e n c ec o u n t e r ) 以在多个 分区进程对州实体进行读取操作时进行同步。这种做法是苍r 消息传递的并行程序 通常的做法 2 4 l ，我们也在此网格库中采用这种方式。! 然，这种同步方式电存在一 定的问题。由- j 并行尤其是分布式环境中各个处理器( p r o c e s s o r ) 之间的关系松散， 在某个处理器进程失效之后，应该尽可能地减少其对其他处理进程的影响。但是，出 于在单个网格实体中引入自身的计数器，使得单个网格实体的错误锁定可能会引起多 个处理器进程的处理。我们可以引入资源竞争的机制解决这个问题。 例如，我们”，以将引用计数器扩展成为一个逻辑划断单元，不仅包含币元被引用 的情况，还包含该实体最近被访问的记录信息。当某一边乔上的实体被误锁之后，其 他的进程可以根据访问的历史记录判断该实体是否被误锁。如果被误锁，就将其迁移 至该进程所在的分区后解锁。这样，对于出现失效的处理器进程，经过一段时间( 可 能非常短) 的计算之后，其运行分区的实体就全部被迁移到其他分区中进行处理了。 下图是这个过程的图示： p t !p 2 ( 失效) p iip 2 ( 失效 图2 4 5 解除实体误锁 当然，引入了逻辑判断单元之后会给网格数据的存储带来额外的丌销，访问实体 的速度也会相应降低。 华中科技大学硕士学位论文 最后，我们在2 3 2 中讨论的邻体直接访问矩阵应该能够在不同的分区中得以区 别。即在不同的分区应浚保存该分区自己独立的r l ( m ) 矩阵。对于边界上的实体，由 于存在不同分区内的多个拷贝，每个拷贝的直接访问表达矩阵会有所区别。但是，这 种区别不会引起歧义。需要指出的是，分区r l ( m ) 矩阵通常在网格迁移算法前后被改 动，而当所有分区都在执行相同豹算法时应该保证致。 2 4 3 对比及评价 由上可知，运行在并行平台上的数值程序由f 同时存在多个处理器在不同分区上 对网格进行操作，网格模型要做出相应的调整以适应多个分区的要求。我们分别讨论 了在常用的串行计算网格表示方案的基础上和在改进方案的基础上引入并行机制的 不同方法。对比而言，我们可以看出： ( 1 ) 在常用的方案中难于做到数据完整性和致性的平衡；而改进方案中由于 对单个实体的可控性加强了，结合实体直接访问矩阵r l ( m ) 可以较好地解决两者的矛 盾。 ( 2 ) 引入实体局部地址可以使得上层的算法程序针对并行平台的改动减少到最 少。 ( 3 ) 引入实体局部地址使得网格迁移变得简捷和直接，而不用像常用的表示法 那样每次分区变动都要进行分区的重新初始化，为分区负载平衡提供了方便。 ( 4 ) 引入实体引用计数器使得分区间同步简捷易行。将引用计数器转变为逻辑 判断单元能够有效地解决实体误锁的问题。 华中科技大学硕士学位论文 第三章并行环境及并行网格自适应算法 3 1 并行分布式环境及技术 大体可以从并行分布计算体系结构和并行分布式平台卜运行的算法两个方面的 发展来把握并行，分前i 式技术的发展历史。 3 1 1 并行，分布式平台 并行和分布计算技术自6 0 年代中期和7 0 年代后期分别出现以来，其并行处理方 式经历了从阵列机( s i m d ) 、向量机及向量并行机、共享存储的对称多处理器系统 ( s m p ) 、分布存储的大规模并行处理系统( m p p ) 到n u m a ( t e 一致访问的分布共享存储) 并行机系统和计算机机群系统( c i u s t e r s ) 的演变过程。 实际应用中的并行分布式计算物理模型主要有一f 几种： ( 1 ) p v p ( p a r a l l e lv e c t o rp r o c e s s o r , 并行向量机) ( 2 ) s m p ( s y m m e t r i cm u l t i p r o c e s s o r , 对称多处理机) ( 3 ) 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 , 大规模并行处理机) ( 4 ) c o w ( c l u s 把ro fw o r k s t m i o n ，工作站机群) ( 5 ) d s m ( d i s t d b u t e d s h a r e dm e m o r y , 分布共享存储多处理机) 不。 糕懋圆 瓢黼镥 图3 1 1 并行计算平台示意图 无论采用哪种硬件平台，我们都可以根据处理器的分布情况用以上的简图加以表 华中科技大学硕士学位论文 在上图所示的6 种情况叶i ，堆结点的s m p 各个处理器之间的通讯，r 销最小，用 高速交换机连接的单处理器系统的荇个处理器之洲的通讯r 销相对较大，而通讯速度 最慢的是用以太网连接的单处理器机系统的各个处理器之间的通讯。在处理器的速度 相差不大的情况下，我们需要重点考虑处理器之问的通信优化。 另外，如果考虑处理器之间性能不平衡的情况，就不仅需要考虑通讯丌销问题还 要考虑为不同性能的处理器选择不同的计算载荷。 3 1 2 并行，分布式算法 根据并行处理系统指令流数据流不同的分配方法，我们可以将并行机分为四类： ( 1 ) s i s d ( 单指令流单数据流) 系统 ( 2 ) s i m d ( 单指令流多数据流) 系统 ( 3 ) m i s d ( 多指令流单数据流) 系统 ( 4 ) m i m d ( 多指令流多数据流) 系统 不同的系统模型所适合的并行分稚式算法各有特点，他们都具有下面的特性： ( 1 ) 计算粒度，是衡量软件进程所含计算量的尺度。粒度决定了计算中所用数 据项和程序模块的规模； ( 2 ) 并行度，反映了可以利用并行处理的机会，通常会影响并行算法的效率； ( 3 ) 通信模式和同步，反映了处理器之间数据共享的效率； ( 4 ) 操作均匀性，这是指要完成的基本操作的类型； ( 5 ) 存储需求和数据结构，并行计算时需要用到数据的组织方式。算法中选定 的数据结构和数据传送模式都会影响存储效率。时问和空间复杂性二者都是并行算法 粒度的重要指标。 3 1 3 面向算法的平台构建思路 不同的算法对不同计算平台上的适应程度是不同的。对于并行分布式数值算法， 我们关心算法的并行度p a r a l l e l ( a ) 以及算法完整运行一次的资源占有量 r e s o u r c e ( a ， p n ) ) 。我们的目标是在最小的资源占有量的基础上达到最大的并行度。 为此，可以定义下面的目标评价函数来评价算法a 对特定平台的适应程度。其中，a l 、 a 2 为权重因子常量，代表我们对两者不同的关注程度： p n 表示参与计算的处理器集 华中科技大学硕士学位论文 p l a t f o 朋( n , a ) 口1 + p a r a l & l ( 9 + 瓦赢丽l 为了简化讨论，我们将资源占有量r e s o u r c e ( a ， p n ) ) 用统一的时间单位t o 来衡量 而不考虑对系统内存的资源占有量。这样简化是可以接受的，因为对f 现代并行算法 、f 台来说，系统存储容量可以假定足足够的 2 5 1 。 假设算法a 在每个处理机上运行次的执行指令周期数为t i m e r u n ( p i ，a ) ，处理 器p i 由于算法同步性要求等待处理器p j 的指令周期数为t i m e w a i t ( p i ，p j ，a ) ，系统分 配给处理器p i 计算该问题的比例为r a t i o a l l o e a t e ( p i ，a ) ，则资源占有量 r e s o u r c e ( a ， p n ) ) 可以表达为： ( 7 j 榭尺蝴 ，柳+ g l m e w a i t ( p i ，毋，固) + r a t i o a l l o c a t e ( p i ，揶 t - l g - i 由此可知，在各个结点处理器计算能力没有明显区别的情况下，为了减少特定算 法的资源占有量，我们应该：( 1 ) 尽量提高r a t i o a l l o c a t e ( p i ，a ) ，即在各个结点应能 保证尽可能多地将处理器时间分配给并行计算的进程；( 2 ) 尽量减少处理器之间的同 步时间，即要求处理器之间通讯速度快而且通讯频度和通讯量尽可能少：( 3 ) 每一个 处理器的分配的运算载荷尽可能少。 但是，这些因素之间的制约关系是明显的。例如如果使每一个处理器的运算量减 少就要增加处理个数n ，同时处理器间的通讯量增加了，很难保证一定会减少总的资 源占有量。再如，为了减少等待时间( 通讯量) ，我们需要在算法中增加额外的计算 以“压缩”和“解压”彼此间的通讯信息。 为此，我们需要研究不同算法对处理器计算周期以及他们之间通讯能力的要求， 以选择合适的并行算法平台。具体到并行网格数值分析软件中，由于改变消息( 通信) 传递机制可明显影响处理的等待时间，采用通讯效率较高的共享存储区的s m p 平台 或者高速互联的分布式处理器平台是比较好的选择。 华中科技大学硕t 士学位论文 3 2 并行网格自适应算法 3 2 1 网格自适应 在基于网格的数值分析软件中，一个常见的问题是要求在计算( 网格生成、方程 求解) 过程中为了将计算误差平均分配到整个计算区域中对网格的密度做自动的修 改。例如，在求解的结果变化较大