（计算数学专业论文）非结构网格的并行生成及计算.pdf

南京航空航天大学硕士学位论文 摘要 研究非结构网格的快速生成在流场计算中有着至关重要的意义 本文的主要目的 是研究和发展非结构网格的并行生成技术 以实现快速生成非结构网格 从而为流场 数值计算节省大量时间 进一步配合流场有效的并行计算算法 最终可实现高效 快 捷地模拟复杂流场 本文改进了r l o h n e r 的 波阵面 区域分裂算法 使得区域分裂后的子区域及 其边界更有益于网格的并行生成 针对区域初分裂后的公共边界 本文提出边界优化 策略 改善了边界的光滑性 有益于并行生成过程中网格的质量 利用改进的区域分 裂算法 对并行生成的初始网格重薪划分 实现了网格的并行光顺 其中 虚拟 边 界节点的光顺需要子区域之间相互通讯 完善了文献 1 1 3 中的子区域内生成网 格时接受新点及新单元的条件 在界面网格生成过程中 本文提出只接受新单元而拒 绝新点的策略 节省了机时 并行生成的时间 效率 加速比表明以上网格并行生成 方法是高效的 可行的 成功实现了网格的快速生成 在以上菲结构网格并行生成工作的基础上 本文进一步利用e u l e r 方程的有限体 积分区并行计算方法 对无粘可压缩绕流流场 在p v m 分布式并行环境下进行了数 值模拟 在e u l e r 方程的分区并行计算过程中 本文采用了j a m e s o n 有限体积法和 四步r u n g e k u t t a 显示时间推进格式 流场区域的划分采用改进的 波阵面 区域分 裂算法 虚拟 边界单元的物理量的计算由子区域之间相互通讯来完成 信息的发 送方式采用 循环式 发送方式 数值试验的结果以及并行计算的加速比 效率的统 计 进一步验证了网格并行生成方法以及并行计算算法的有效性 关键 司 区域分裂 非结构网格 网格并行生成 有限体积法 并行计算 非结构网格的并行生成及计算 a b s t r a c t 1 1 1 es t u d yo nh o wt oq m c e y g e n e r a t eu n s t r u c t u r e dg r i d si so fg r e a ts i g n i f i c a n c ef o rt h e f l u i df l o wc a l c u l a t i o n i no r d e rt os a v et h et i m eo fu n s t r u c t u r e dm e s hg e n e r a t i o n t h em a i n w o r ko ft h i sp a p e ri st od e v e l o pt h et e c h n i q u eo fp a r a l l e lu n s t r u c t u r e dg r i dg e n e r a t i o n w i t ht h ee f f e c t i v ep a r a l l e lc o m p u t a t i o na l g o r i t h m t h es i m u l a t i o no f c o m p l e x i n v i s c i df l o w i sf i n a l l ya c h i e v e dm o r e e f f i c i e n t l ya n dq u i c k l y i nt h i sp a p e r w ef i r s t l yi m p r o v et h er l o h n e r sw a v e f r o n t d o m a i n s p l i t t i n ga l g o r i t h m s ot h a tt h es u b g r i d sa n dt h e i rb o u n d a r i e sa r em o r ef a v o r a b l ef o rg r i dg e n e r a t i o n an e w o p t i m i z a t i o ns t r a t e g yo fs u b d o m a i n sb o u n d a r yi st h e np r e s e n t e di no r d e rt oi m p r o v et h e s m o o t h n e s so fb o u n d a r i e sa n dt h eq u a l i t yo f g r i d s a f t e rs u b d i v i d i n gt h ei n i t i a lm e s h e sb y u s i n gt h ea b o v ed o m a i n s p l i t t i n ga l g o r i t h m w es m o o t h t h eg r i db yt h ep a r a l l e lm e t h o d i n t h i s p h a s e s m o o t h i n g s u b j u n c t i v e b o u n d a r yp o i n t s n e e d sm u t u a lc o m m u n i c a t i o no f s u b d o m a i n s n e x t w ea l s oi m p r o v et h ec o n d i t i o n si nt h ep a p e r 1 1 3 o fr e c e i v i n gn e w p o i n t sa n de l e m e n t si nt h ec o u r s eo fg r i dg e n e r a t i o ni nt h es u b d o m a i na n dp r e s e n tan e w s t r a t e g yo fr e c e i v i n gn e w e l e m e n t so n l ya n dr e f u s i n gn e w p o i n t sd u r i n gt h ec o u r s eo fg r i d g e n e r a t i o no f t h ei n t e r f a c e w h i c hc a ns p a r em u c ht i m e t h er e s u l t so b t a i n e do nt h ep v m e n v i r o n m e n td e m o n s t r a t eh i g he f f e c t i v e n e s so f t h e a l g o r i t h m s b a s e do nt h ea b o v ea l g o r i t h mo fp a r a l l e l u n s t r u c t u r e d 鲥dg e n e r a t i o n ap a r a l l e l c o m p u t i n g m e t h o di sa p p l i e dt oa2 de u l e rs o l v e rf o rt r a n s o n i ca n ds u p e r s o n i cf l o wo na p v m p a r a l l e le n v i r o n m e n t j a m e s o nf i n i t e v o l u m es c h e m ea n df o u r s t a g e r u n g k u t t a t i m e s t e p p i n gm e t h o da r ee m p l o y e di nt h ep r o c e s so f t h ez o n a lp a r a l l e lc o m p u t a t i o no f e u l e re q u a t i o n s t h e w a v e f r o n t d o m a i nd e c o m p o s i t i o nm e t h o d d e v e l o p e da b o v ei su s e d i nt h ed i v i s i o no ff l o wf i e l dd o m a i n t h e q u a n t i t yo fp h y s i c sv a r i a b l e so nt h e s u b j u n c t i v e b o u n d a r ye l e m e n t sn e e d sm u t u a lc o m m u n i c a t i o no f s u b d o m a i n sd u r i n gt h es i m u l a t i o n t h e r e s u l t so fn u m e r i c a le x p e r i m e n t s t h es t a t i s t i c so fs p e e d u pr a t i oa n dp a r a l l e l e f f i c i e n c ya l ls h o wt h e s u c c e s so f p a r a l l e l u n s t r u c t u r e d g r i dg e n e r a t i o n m e t h o da n d p a r a l l e lc o m p u t a t i o n a l g o r i t h m k e yw o r d s d o m a i n s p l i t t i n g u n s t r u c t u r e dg r i d p a r a l l e lg r i dg e n e r a t i o n f i n i t e v o l u m es c h e m e p a r a l l e l c o m p u t i n g m e t h o d i i 堕室堕至堕丞查堂堡主堂垡丝苎 1 1 问题的背景 第一章绪论 近二三十年来 计算流体力学 c f d 作为现代流体力学新兴的学科分支 发 展极为迅速 也取得了很大成功 已经与理论分析 风洞试验和飞行试验一起成为流 体力学研究和飞行器设计的重要手段 事实上 计算流体力学的发展除了依赖于计算 机和数值计算方法的发展以外 还在很大程度上依赖于网格技术的发展 计算流体力学的发展也是伴随着计算机技术的发展而前进的 后者是前者的基 础 计算机的速度 内存和外围设备提高过程中的每一次飞跃都会带来计算流体力学 新的发展阶段 计算机的发展历史表明 为了达到更高的处理性能 除了提高运行速 度外 系统结构也必须不断改进 由于大规模集成电路的微型化在技术上困难越来越 大 进一步提高计算机的运行速度面临很大困难 事实上计算机运行速度提高的速率 已呈下降的趋势 因此计算机系统结构的改进成了人们关注的焦点 这方面的改进主 要围绕着增加同一时间间隔内的操作数量 即所谓并行处理技术 并行处理是一种有 效的强调开发计算过程中的并发事件的信息处理方式 并发性包含并行性 同时性和 流水性 并行事件可在同一时间间隔内发生在多个资源中 同时事件可在同一时刻发 生 流水线事件可在部分重叠时间内出现 作为主要应用领域的计算流体力学对计算机的高速计算能力和存储能力提出了 越来越高的要求 据美国航空航天研究中心a m e s 预测 c f d 需要每秒执行1 0 浮点 运算的计算机 如此庞大的计算量 只有在高性能的计算机上才能得以实现 而这种 高性能的计算机大都是并行机 正因为如此 许多从事计算流体研究的专家早在六七 十年代就对流体力学问题的并行化进行研究 从许多实际问题的并行化研究可以看 出 问题的不同 其并行化的程度也不同 因而 即使在同一台机上 不同的问题也 可以得出不同的并行加速比 而对同一问题 在不同的并行机上 其并行化的做法不 一样 并行化的效益也不一样 所以 研究一个应用算法的并行化前 必须仔细了解 所使用的并行机的结构和其配备的软件 我国高性能计算机的发展起步并不晚 早在二十世纪六十年代后期到七十年代 我国就自行研制了大型计算机 典型代表机器有1 5 0 9 0 5 7 1 8 和d j 2 6 0 等 它们采 用单双c p u 峰值速度约为lm o p s m i l l i o no p e r a t i o np e rs e c o n d 即所谓的百万次 机 二十世纪七十年代后期到八十年代 我国研制了向量机和多处理机其典型代表机 器有7 5 7 银河一i i i 等 它们采用卜4 个c p u 峰值速度达1 0 1 0 0m o p s 即所谓 的亿次机器 从八十年代后期到现在 我国研制了对称多处理机 大规模并行机和工 作站机群 其典型代表机器有曙光l 号 曙光 1 0 0 0 1 0 0 0 a 银河 i i i 和曙光2 0 0 0 等 韭缝塑旦整塑茎堡生盛垦盐墨 它们采用4 1 2 8 个c p u 峰值速度达1 g g i g a 1 0 9 f l o p s 一几十g f l o p s 即所谓的百 亿次机 相对于国内并行机的发展 国内流体力学问题并行算法的发展迟缓了许多 因而 结合国内现有的并行机 开展c f d 并行算法的研究是很有必要现实意义的 这也是流体力学学科发展的要求 1 2 网格生成技术现状 1 2 1 结构网格 生成结构贴体网格的常用方法有 1 t t m 4 7 法 采用求解椭圆形方程生成流 场的空间网格分布 2 通过求解双益型方程或抛物型方程的方法生成空间网格分 布 3 用代数方法来生成结构网格 对于复杂外形而言 生成单域贴体网格是相当困难的 即使能够勉强生成 网 格质量也不能保证 将直接影响流场解的效果 因此目前普遍采用分区网格技术 即 根据外形的特点将总体流场分为若干个子域 使每个子区域的网格拓扑相对简单 而 后再对每个子区域分别建立网格 常用的有分区对接 4 8 和分区重叠技术 4 9 1 2 2 非结构网格 相对于结构网格 非结构网格具有以下优点 1 由于非结构网格舍去了网格 节点的结构性限制 易于控制网格单元的大小 形状及网格节点的位置 因此比结构 网格具有更大的灵活性 特别是对复杂外形的适应能力非常强 2 对于结构网格 在计算域内网格线和平面都应保持连续 并正交于物体边界和相邻的网格线和面 而 非结构网格则无此限制 这就消除了网格生成中的另一个主要障碍 3 由于非结构 网格中一个节点周围的节点数和单元数都不固定 因此可以方便地作自适应计算 合 理分布网格的疏密 提高计算精度 但非结构网格也存在着以下缺点 1 非结构网格技术因需要记忆单元节点之间 的关联信息 需要较大的内存 2 结构网格中成熟的流场解计算方法不能简单地用 于非结构网格 3 不易应用多重网格技术 常用的非结构网格生成方法有以下两种 1 d e l a u n a y 三角化法 d e l a u n a y 三角化法和v o r o n o i 图有密切关系 1 8 5 0 年d i r i c h l c t 指出 对于给定 的平面点集 其v o r o n o i 图唯一确定 1 9 3 4 年d e l a u n a y 指出 对给定的平面点集 与v o r o n o i 图对应 存在唯一的三角化网 使得每个单元的最小内角最大 d e l a u n a y 三 角化法就是利用了这一特点 在区域内预先分布节点 采用适当准则 常用的为最大 最小准则 将点连接成网格单元 目前 较实用的d e l a u n a y 网格生成技术为b o w e r 2 堕塞堕至塾墨丕堂堡主堂焦笙塞 一 一 算法 优点 d e l a u n a y 三角化法具有良好的数学支持 生成效率高 不易引起网格空 间空透 数据结构相对简单 缺点 需在物面处进行布点控制 以避免物面穿透 保证物面的完整性 2 阵面推进法 a d v a n c i n g f r o n t m e t h o d 3 5 3 9 阵面推进法主要包括背景网格生成 初始阵面形成和空间网格生成三个基本步 骤 背景网格是一个包围感兴趣区域的空间网格 在这个网格的节点上定义网格步长 控制参数 在生成过程中通过这些参数来控制空间网格单元大小 阵面由边界向内推 进 由阵面及背景网格确定推进的方向和尺度 在推进过程中同时产生新的节点和网 格单元 并同时对点 线和面进行插入 删除等工作 直到计算区域被完全填满为止 优点 不会引起物面穿透 边界附近网格质量较高 缺点 生成效率低 费机时 三维时需要预生表面网格 网格质量对背景网格的 依赖性较强 较易引起网格空间穿透和流场空腔 1 2 3 自适应笛卡尔网格 5 0 a d a p t i v e l yr e f i n e dc a r t e s i a nm e t h o d 笛卡尔网格 矩形网格 时c f d 中最早使用 也是最易生成的一种网格 但比 较难处理好物面边界 因而不易准确地满足边界条件 而自适应笛卡尔网格是为了计 算复杂几何外形的流场 在原始的均匀笛卡尔网格的基础上根据物形特点和流场特点 在局部区域内不断进行网格细化得到的计算精度符合要求且分布合理的一种非均匀 的矩形网格 优点 无需预先生成表面网格 数据结构简单 具有天然的多重网格特性 可 较方便地应用多重网格法 可使用高精度算法 缺点 描述外形精度较低 不可能做到完全贴体 1 3 非结构网格并行生成的现状 由于非结构网格生成也很费机时 譬如 三维情况下计算一架完整飞机的湍流模 拟往往需要几百万个四面体单元 单单网格生成要耗费几个小时的c p u 时间 特别 地 在模拟运动物体的瞬间流动时 单单一次运行 往往需要生成流场局部或整体网 格上百次 目前所能提供的浮点运算速度最快 容量最大的超级计算机也未能解决网 格生成的费时问题 因此 如何快速生成非结构网格是计算流体力学 计算电磁学等 许多领域中急待解决的课题 研究非结构网格的快速生成在流场计算中有着至关重要 的意义 尽管网格生成技术目前在国内外已非常成熟 但是 对于网格并行生成技术的研 究却不是很多 国内 外可参考的文献比较少 r l o h n e r 1 1 3 在1 9 9 2 年第一 非结构网格的并行生成及计算 次利用阵面推进技术并行生成了网格 t 0 k u s a n y a 和j p e r a i r e 1 4 在1 9 9 6 年运 用d e l a u n a y 三角化法也并行生成了网格 前者的工作主要体现在 1 提出了区域 分裂算法 2 给出了网格并行生成的两种策略 3 实现了网格并行光顺 不足之处 区域分裂后 子区域的相邻区域个数至少两个 边界的查找非常麻烦 相邻区域个数 越多造成今后的网格生成过程中额外的通讯消耗 在生成网格过程中子域之间易形成 空腔 从而导致网格质量下降 子区域内的生成网格时 接受新点及新单元的条件有 待于进一步讨论 后者的工作体现在 在d e l a u n a y 三角化的过程中 每个子区域上 新节点插入后 引起子区域上的网格单元不同 出现了负载不平衡 通过确定单元 移动单元 子处理机之间相互通信 达到负载平衡 然后 继续插入新点 再平衡 直到达到要求为止 解决了r l o h n e r 方法的负载不平衡的问题 但是 事物总有两 面性的 这种方法最大的不足之处在于 每次新点插入一次 就要伴随着一次平衡 子处理机之间的额外通讯消耗远远多于r h o h n e r 方法中的通讯耗时 随着新插入节 点的增多 通讯消耗剧增 对于网格生成来说 这是得不偿失 另外 文 5 6 6 2 利用人工分区的方法生也成了非结构网格 但是 人工分区的局限性比较大 只能适 用于几何外形较简单的网格生成 因此 有必要进一步研究非结构网格的并行生成技 术 1 4 并行计算的基本术语 根据并行机不同的特性 并行机的分类有多种方法 最常用和最易接受的是 f l y n n 分类法 4 6 1 即按照指令流和数据流可将并行机分为 1 单指令流单数据s i s d 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 计算机 是 指包含一个c p u 的常用系统如工作站和计算服务器 2 单指令流多数据流s i m d s i n g l e i 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 计算 机 如阵列处理机等 是指对不同数据执行同一个指令 3 多指令流单数据流m i s d m u l 却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 计算 机 目前机型尚难确定 4 多指令多数据流m i m d m u l 卸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 计算机 如目前广泛使用的多处理机就属此类 各处理机对各自的数据独立的执行不同 的指令 根据内存组织形式可以将m i m d 计算机进一步分类为 1 共享存储m i m d 计算机 是指所有处理机使用一个公共内存 但由于受内存 容量限制和网络耗时 处理机还不能达到很大数目 2 分布存储m i m d 计算机 由多个处理机组成 每个处理机都有自己的局部内 存 由通讯网络来相互连接 因此 每个处理机实际上就是一个完整的计算 机 4 南京航空航天大学硕士学位论文 在分布存储编程过程中 各处理机制能接触自己的内存 当一个处理机需要另一 个处理机的数据时 必须解决信息传递 这样一个信息传递包括发送节点的信息准备 通过通讯网络的传送和目标节点的信息接收 当这一现象出现在共享存储系统时 则 被共享内存的信息存储所代替 因而 分布存储编程比共享存储编程要困难 同步控 制是非常重要的 可能 个处理机还没有另一个处理机所需要的信息 它就会处于等 待状态 这样会增加计算耗时 影响并行效率 此外 还要解决负载平衡问题 尽管 每个处理机能运行不同程序 但最常用的是单程多数据形式 所有处理机执行同一程 序对应于一套数据的不同部分 这就需要对数据进行有效的分配 使各处理机之间的 计算量达到平衡 数据交换和同步控制量达到最小 并行算法是指适合于在并行机上求解问题和处理数据的算法 根据具有不同结构 体系的并行机 可以定义不同的并行算法 如s i m d 算法 m i m d 算法等 并行算法的成本就是在最坏情况下求解一个问题时总的运行时间 可以表示为 c f p 其中t 为并行算法的运行时间 p 为处理机的台数 加速比是评价算法的并行性对运行时间的改进程度 令t 为一台处理机计算时所 需要的时间 为p 台处理机计算时所需要的时间 加速比可定义为 驴0 并行算法的效率反映了并行系统中处理机的利用情况 定义为 驴等 有时候并行算法虽有好的加速比 但处理机的利用率可能很低 也得不到高效率 早期的并行算法的研究通常忽略通讯和同步的时阀开销 事实上 在实际问题中 这两个因素对并行加速比有很大的影响 处理机之间的通讯问题 一般地 对于分布 式存储系统 在计算过程中 各处理机之间要进行信息交换 以致在每次通讯的时间 内处理既不能进行有效地计算 1 5 p v m 的分布式并行环境 5 1 p v m 是p a r a l l e lv i r t u a lm a c h i n e 的缩写 它能将一组m i s c r o s o f lw i n d o w s 以及 u n i x 或l i n i y x 系统的异构网络环境下的计算机虚拟成单个的并行计算机 p v m 是 由美国o a kr i d g e 国家实验室研制 是美国国家基金会资助的公开软件系统 p v m 提供在虚拟机系统的各个结点 单c p u 或单计算机 上创建任务以及支持任务间或 结点间同步和通信的手段 p v m 应用程序可以用c 或f o r t r a n 编写 使用p v m 提供 的消息传递 m e s s a g ep a s s i n g 机制实现并行计算 通过发送和接收消息 应用程序 非结构网格的并行生成及计算 的多个任务 或进程 可以互相协作 并行的解决一个大型科学与工程计算或大型事 务处理问题 p v m 具有通用性强和系统规模小的特点 即适合t c p i p 网络环境 又 适合于m p p 大型并行计算机系统 在有信息交换的并行编程中 程序一般是由标准的串行语句加上用于信息接收和 发送的库函数的调用 p v m 是一种信息传递接口 是目前国际上流行的并行编程环 境之一 包含了许多个函数 并行编程时需要加入p v m 的库函数 1 6 本文的主要工作及创新点 本文针对1 3 节中提到的问题 鉴于国内外关于网格并行生成技术方面的研究 在r l o h n e r 方法的研究基础上进行了改进 编制了非结构网格并行生成的程序 对 无粘可压缩绕流问题 本文采用分区并行计算的方法 进行了数值模拟 本文的工作主要体现在以下几个方面的工作 1 区域分裂算法 改进了r l o h n e r 的 波阵面 区域分裂算法 使之更适用于网格的并行生成 改进后的算法 与原算法进行比较 其优点 分裂后的子区域的相邻区域个数至多两 个 公共边界减少 子机之间的通信消耗减少 且容易查找子区域边界 编程简单 同时 此算法还简化了网格并行生成的策略 并且 改进的 波阵面 分裂算法也可 应用于并行计算中的初始网格区域分裂 2 子区域的边界优化 为了提高区域分裂后的子区域边界的光滑性 本文提出了边界并行优化策略 给出了单元移动的准则及单元移动后的子区域边界的整理方法 这使得分裂后区域边 界保持蓖好的光滑性 有利于网格质量的改善 3 并行生成了非结构网格 采用上述改进后的区域分裂算法 在并行生成菲结构网格时 省去了r l o h n e r 的网格并行生成策略中角落处的网格生成步骤 从而简化了网格生成程序 在子区域内网格生成时 完善了接受新点及新单元的条件 给出了活跃边的分 类 提出暂时性非活跃边及永久性非活跃边的概念 有助于理解网格并行生成的步骤 鉴于子区域内生成网格后的界面的几何特征 在界面网格生成时 本文提出的策略是 只生成新单元 不产生新点的策略 直接将空隙上的节点连接成网格 这样可以减少 生成时间 4 实现了网格并行光顺 在用阵面推进法生成各子区域网格时 很难做到各区生成的网格数完全相同 因 此 每个子机之间难免会存在负载不平衡 为此本文采用重新分区的策略解决这个问 题 在并行光顺时 给出了边界节点的分类 虚拟 边界节点的光顺需要子机之间 6 南京航空航天大学硕士学位论文 相互通讯 信息发送采用 循环式 发送方法 5 数值模拟 本文采用j a m e s o n 有限体积法在非结构网格上求解了e u l e r 方程 以检验生成 网格的质量 求解的方法是分区并行计算方法 本文采用改进后的区域分裂算法对复 杂几何外形区域流场进行划分 在分布式p v m 并行环境上 对有限体积法求解二维 e u l e r 方程的无粘可压缩绕流流场进行了数值试验 数值试验的结果以及并行计算的 加速比 效率的统计 进一步验证了网格并行生成方法以及并行计算算法的有效性 本文的创新点主要体现在以下几个方面 1 改进了文 1 中r l o h n e r 的 波阵面 区域分裂算法 文献 1 中的区域分裂算法的缺点 分裂后的子区域的相邻区域非常多 相邻区 域的数目增加 子区域的交界面也随之增加 这给子区域内的网格生成及交界面处网 格生成带来许多不便 譬如 界面网格生成时 需要多次判断相邻区域的号码 甚至 引起生成的阁格质量较差 同时 这也不利于串行程序代码向并行程序代码的转换 鉴于此算法存在的问题 本文改进了其区域分裂算法 改进后的算法能使得区域分裂 后的子区域的相邻区域至多为2 个 公共边界减少 且边界的查找方便 一方面有利 于网格的并行生成 网格的并行光顺及无粘流场的e u l e r 方程并行计算 另一方面 容易编制并行程序代码 同时 改进的算法弥补了原算法事后再探测边界的不足 2 提出了边界并行优化策略 区域初始分裂以后 子区域的边界出现不光滑现象 这对于后面的网格并行生成 有一定的影响 譬如 导致生成畸形单元 为了改善这种现象 本文提出了边界并行 优化策略 利用的优化方法是 给定准则 子区域之间相互移动单元 整理边界 在 单元的移动准则中 本文给出了单元移动的条件以及不需要移动的几类特殊单元 对 于单元移动前后的子区域的边界整理 本文也给出了相应的主要步骤 通过优化 子 区域的边界光滑程度得到明显的改善 此优化方法也可应用于并行计算中区域分裂后 的边界光顺 3 在子区域内生成网格时 本文完善了接受新点及新单元的条件 提出了暂时 性非活跃边及永久性非活跃边的概念 给出了活跃边的分类 有助于理解网格并行生 成的步骤 在界面网格生成的过程中 针对子区域内网格生成后留下的空隙的几何特 征 本文提出只生成新单元 不产生新点的策略 直接将空隙上的节点连接成网格 这样可以减少机时 非结构网格的并行生成及计算 2 1 引言 第二章区域分裂 区域分裂是c f d 中并行计算的重要前提 网格的并行生成 网格的并行自适应 及非结构网格上的并行计算求解 都要设及到区域分裂这一重要环节 并行计算机的有效运用取决于使处理的数据均衡的分配给每个子处理机并且保 证子处理机之间的通信消耗达到最小 这种分配问题即为负载平衡问题 相应的 计 算流体力学中的负载平衡问题是指寻找较好的区域分裂算法 将分裂后的子区域网格 数据发送给子处理机 做到负载平衡 在实际应用中 多数问题均建立在非结构网格 基础上的 因此 c f d 中的负载平衡的实质是保证分裂后的子区域内的三角单元数 目尽量相等及子区域的公共边界的长度尽量小 但是 在实际计算中 随着问题的不 同 同时满足以上两个标准是比较困难的 目前 对于并行计算来说 存在的区域分裂算法比较多 主要包括 贪婪 算 法 3 r c b 算法 4 5 r g b 算法 4 5 6 r s b 算法 5 6 8 多层r s b 算法 1 0 m i n c u t 算法 1 l 等等 针对网格的并行生成来讲 存在的分裂算法比较 少 r l o h n e r 在文献 1 3 中提出了应用于生成网格的 波阵面 区域分裂算法 这些算法将在第二部分分别介绍 以上算法各有优势 贪婪 算法 r c b 算法 r g b 算法 r s b 算法 多层r s b 算法 m i n c u t 算法 它们主要适用于非结构网格上的并行计算求解 而 波阵面 算法主要是针对网格的并行生成 当然 就网格的并行生成所要求的区域分裂来说 它也存在着一些不足 本章以r l o h n e r 的 波阵面 算法为基础 针对其存在的不 足 对此算法进行改进 将改进的算法应用于初始分裂 同时提出并行优化策略来改 善初始分裂后的边界光滑性 经过优化后的子区域边界更有益于今后的网格并行生 成 本章的区域分裂具体分为两个环节 1 初始分裂阶段 2 并行优化阶段 本章的第二部分介绍目前存在的主要区域分裂算法 第三部分给出了作者改进的 区域分裂算法及并行优化策略 第四部分将改进的 波阵面 算法及优化策略应用于 单翼型 双翼型及多段翼型网格的划分 2 2 区域分裂算法 目前存在的区域分裂的方法主要分为两大类 1 以三角形单元为基础的分裂方法 如 贪婪 算法 波阵面 算法 2 以网格的对偶图为基础的分裂方法 如 二 分法 宣室堕室堕丕盔堂堡主堂焦丝塞 2 2 1 以三角单元为基础的分裂方法 贪婪 算法 f a r h a t 的 贪婪 算法 t h e g r e e d y a l g o r i t h m 见 3 比较简单 产生的子区域边界短 且有较好的面比率 面比率的好坏是指分裂后的子区域形状是 否狭长 此算法首先分配给每个网格节点n 一个权w w i 为与节点n 相连接的三角 单元的数目 记q r 5 c 5 分别为子区域的网格 交界面边界 单元的个数 记c 为 整个计算区域的网格单元的个数 此算法可连续找到子区域q 1 q 2 n 9 一旦前 s 一1 个子区域被找到 则可以利用它们构成下一个子区域q 具体算法如下 1 查找第s 1 个子区域q 1 中权最小的点h 设它的权为 2 把与点n 连接的未标记单元全部存入第s 个子区域q 中 3 对于q 3 中的每个单元吒 重复以下步骤 标记单元e t 对于 的每个节点疗 w w 一1 把单元e 的未标记的相邻单元加入q 到中 更新c 5 当c 5 c p 时 停止3 不再继续 返回3 继续 此算法的优点 速度快 有好的面比率 主要缺点 产生大量的不连通子区域 相邻子区域数较多 波阵面 算法 r l o h n e r 在文 l 1 3 中提出了适合网格生成并行的 波阵 面 区域分裂算法 这种算法与 贪婪 算法类似 其缺点 子区域的相邻区域数目 非常多 公共边界数多 且边界的查找比较麻烦 这对今后的予区域网格并行生成及 并行程序的编制带来不便 相邻区域的数目增加 子区域的交界面也随之增加 特别 是在子区域网格生成后 生成交界面处网格时需要多次判断相邻区域的号码 且生成 的网格质量较差 算法的主要步骤如下 1 建立两个临时数组c l i s t 及s c l i s t 前者储存当前区域内的未标记点 后者 储存整个区域的未标记点 若一个点或单元已存在于某个子区域 则称此点 或单元被标记 否则 称未标记 2 给区域计数器赋初值 3 对下一个子区域 更新区域计数及子区域的单元计数 4 从数组s c l i s t 中顺序选择一个未标记点 同时标记此点 5 对于和此点连接的每个单元 若单元未被标记区域号 则标记此单元属于当前区域 非结构网格的并行生成及计算 对于此单元的每个顶点 若未被标记 则顺序的加入到数组c l i s t 的尾部 6 若子区域内的单元数超过单元平均数 则 删掉数组c l i s t 中已标记的点 并将数组c l i s t 中其余的点逐次加入到数组 s c l i s t 的第一个元数的位置 而数组s c l i s t 的所有元数顺次后移 然后 返回步骤3 否则 返回步骤5 继续 图2 1 显示的是此算法产生的单翼型的区域分裂图 图2 1 波阵面算法 2 2 2 以对偶图为基础的区域分裂算法 常用的区域分裂二分法是对三角网格的对偶图进行区域划分的 对偶图中的每 个顶点代表一个三角单元 该顶点与相应三角单元的重心重合 与直接对三角网格 划分相比 对偶图分裂可以减少浮点运算量 图2 2 是单翼型网格的对偶图 顶点 的个数为1 0 3 2 个 南京航空航天大学硕士学位论文 图2 2 单翼型网格的对偶图 假定仅有两个处理机 对偶图分裂问题成为对偶图二分问题 记g 矿 为某 网格的对偶图 其中 v 为顶点 对应于三角单元的重心 e 为边 对偶图中任 意两个顶点之间的连接线段 若找到一种分裂使得v ku 且hn k 巾 l k z l k i 其中l 为集合中单元的个数 记l e l 为区域的公共边 c u te d g e s 的 数目 则有 f e l i 协l h e h v v 2 v k v n t r n 分裂也使得l e j 达 到最小 一般地 l k i z 1 i 可理解为 吲 i i v i 吲一1 若 州为偶数 若n 川为奇数 对偶图区域二分法的基本思想 首先 依照算法把网格的对偶图分成顶点几乎相 等的两个子区域 然后 再重复利用二分法对每个子区域进行重新分区 依次进行下 去 直到新要求的子区域数目为止 显然 二分法可以得到2 一个子区域 其中 h 2 l 2 事实上 二分法要求并行机的处理器有较好的拓扑结构支持 1 顶点坐标二分法 r e c u r s i v ec o o r d i n a t eb i s e c t i o n 简称r c b r c b 算法的思想是 给定对偶图的顶点集合矿 v v 2 v vv v 都存 非结构网格的并行生成及计算 在点对v x y z y 为网格中三角单元的重心坐标 选定一个坐标方向 如 x 轴方向或y 轴方向 不失一般性 设此方向为x 轴方向 沿着x 轴方向将所有的k 进 行排序 升降 得到集合矿 y 然后 找到v 中的中间值 将 小于 的顶点分给一个子区域 大于 的顶点分给另一个子区域 具体算法如下 表 r c b 算法 1 确定方向 2 根据选择方向 对顶点的相应坐标排序 3 将排序后的顶点一分为二给每个子区域 4 在每个子区域重复应用1 至3 直到为所求 图2 3 是重复运用r c b 算法三次即分成8 个子区域的单翼型网格 从图中可看 到 这种算法分裂后的子区域狭长 忽略了顶点之间的相互连接信息 子区域的相邻 区域的个数一般多于2 个 公共边界较多 图2 3 r c b 算法 南京航空航天大学硕士学位论文 2 r e c u r s i v e g r a p h b i s e c t i o n r g b 算法 r c b 算法的弱点是没有充分利用对偶图中顶点之间的连接信息 r g b 算法克服 了这一缺陷 定义对偶图中顶点的距离 d v v 连接v t v j 之间路径的最短线段 如图2 4 示 顶点i j 之间的距离为从点i 出发到点j 的所有路径的最小值 图2 4 对偶图的顶点距离 i j 首先 确定对偶图中距离最大或接近最大的两个顶点v v 然后 根据其它顶 点与v v 的距离的远近进行分配 v v v m f j 若d v v r e f f d 则停止 返回步骤5 否则 返回步骤6 南京航空航天大学硕士学位论文 继续 9 探测每个子区域的边界信息 改进的 波阵面 算法的优点 与原算法相比 初始分裂后的子区域的相邻区 域数大大减少 一般不多于2 个 公共边界数也减少 这降低了编制并行程序代码的 复杂程度 而且边界的查找非常容易 也避免出现子区域独立生成网格后留下的复杂 交界面 省略了r l o h n e r 的网格并行生成策略中的第三个步骤即角落处的网格生成 这在第三章将会讨论 同时弥补了原算法事后再探测边界的不足 缺点 个别子 区域的形状狭长 表1 是单翼型网格区域划分后的公共边数 相邻区域平均个数及最 大相邻区域数的统计 从表中可以看出 这三个参数的大小都有所减小 特别是相邻 区域数目 改进后的算法仅为2 个 这对网格的生成是非常有利的 单翼型网格区域波阵面算法改进后的算法 公共边数9 5 0 9 2 4 相邻区域平均个数 4 11 7 5 最大相邻区域数 52 表l 子区域的个数 8 个 网格并行生成所要求的区域分裂与网格并行计算求解的区域分裂是有区别的 前 者的分裂对象是背景网格 后者的对象是最终生成的质量好的网格 背景网格的特点 是单元个数少 较粗糙 后者与之相反 将背景网格动态的分成所要求的子区域数 便可获得每个子区域的边界信息 这些边界信息为以后的网格生成划分了界限 分区 后的背景网格的单元不再起作用 子处理机所要的信息仅仅为子区域边界 然而 后 者的区域分裂以后 子区域的单元 边界都是并行计算效率的重要影响指标 显然 两者区域分裂后的单元 边界的作用截然不同 因此 改进后的 波阵面 算法的缺 点对于网格生成不会产生什么影响 对于并行计算来讲 改进后的 波阵面 算法也 可应用于网格的并行计算求解 其应用将在本文的第五章进行讨论 当然 改进后的 算法应用于并行计算中初始网格区域划分所得到的子区域边界还不是最短 因而 子 机之间的通讯消耗量还不可能达到最小 尽管改进的 波阵面 算法在并行计算中不 是最优的 但与现有的一些方法相比 它的子区域边界还是相对较短的 如表1 所示 因此 用于并行计算中还是具有优越性的 2 3 4 初始分裂的并行优化策略 初始分裂以后 某些子区域的边界出现不光滑现象 这对于后面的网格并行生成 有一定的影响 譬如 导致生成畸形单元 为了改善这种现象 初始分裂后的子区域 需要优化 本章采用的优化策略是 子处理机之间相互通讯进行并行优化初始分裂 利用的优化方法是 给定准则 子区域之间相互移动单元 通过优化 予区域的边界 光滑程度得到明显的改善 并且相邻区域的公共边界有所减少 在网格的并行光顺及 j 壁塑旦堡塑茎堑生盛壁盐簦 一 并行计算时 可以减少子机之间的通信消耗 对于外形复杂的物体 如 多段翼形 初始分裂后的并行优化尤其重要 一 优化策略 1 发送初始分裂后的子区域的单元 节点 边界信息 2 在各个子处理机上 确定需要移动给相邻区域的单元信息 并发送给相邻 处理机 同时整理单元移动后的子区域的边界 3 子处理机接收到相邻区域的移动单元信息后 再次整理子区域的边界 二 单元的移动准则 子区域中需要移动的单元主要分为两类 1 一个单元的相邻单元的区域号码至少有两个与此单元的区域号码相异 此 单元即为移动单元 如图2 6 区域i 与区域j 为相邻的予区域 在区域j 中 单元e 满足1 则单元e 即为需要移动的单元 图2 6 第一类移动单元 2 对于边界上的每个节点 若与它相连接的两条边界边的正向 逆时针方向 夹角小于某个角度 此角度可根据实际情况选取 则子区域内与此节点 连接的所有单元均为移动单元 如图2 7 示 区域i 与区域j 为相邻的予区域 在区域j 的公共边界a b c 上 与点b 连 接的边为a b b c 它们的夹角为边b c 沿逆时针旋转到边a b 所形成的 角 与之相反 在区域i 的公共边界c b a 上 与点b 连接的边为b a c b 它们的夹角为边b a 沿逆时针旋转到边c b 所形成的角 显然 这 两个夹角之和为3 6 0 度 假定 夹角 b c a b 小于某个角度 在区 南京航空航天大学硕士学位论文 域j 中 与点b 连接的单元e e 即为移动单元 然而 在区域i 中 由于夹角 删 大于给定的角度 与点b 连接的单元p p 岛 p 均 不需要移动 图2 7 第二类移动单元 事实上 为保证优化后的子区域的边界形状与原边界相差不大 在具体编 制程序时 几种特殊的单元是不需要移动的 它们是 1 属于不同区域的相邻单元均满足第一类准则 此时 以区域号码的大小 为依据 区域号码小的单元需要移动 反之 不需要移动 如图2 8 示 图2 8 第一种特殊单元 非结构网格的并行生成及计算 在区域i 中 单元e 满足第一类准则 在区域j 中 单元巨也满足此条准则 且e 与e 相邻 若i j 则e 被移动 2 不同区域的两个相邻单元 分别满足不同类的准则 此时 满足第二类准 则的