基于AFT-Delaunay的二维解耦并行网格生成算法 张宇航;余飞;昌继海;曹杰;关振
【摘 要】面向平面任意几何区域网格生成,提出了一种将波前法AFT(Advancing Front Technique)与Delaunay法相结合的解耦并行网格生成算法.算法主要思想是沿着求解几何区域惯性轴,采用扩展的AFT-Delaunay算法生成高质量三角形网格墙,递归地将几何区域动态划分成多个彼此解耦的子区域;采用OpenMP多线程并行技术,将子区域分配给多个CPU并行生成子区域网格;子区域内部的网格生成复用AFT-Delaunay算法,保证了生成网格的质量、效率和一致性要求.本算法优先生成几何边界与交界面网格,有利于提高有限元计算精度;各个子区域的网格生成彼此完全解耦,因此并行网格生成过程无需通信.该方法克服了并行交界面网格质量恶化难题,且具有良好的并行加速比,能够全自动、高效率地并行生成高质量的三角网格.%Based on Advancing Front Technique (AFT) combined with a Delaunay method,a new decoupling parallel mesh generation algorithm for two dimensional region is proposed.The main idea of the algorithm is along the inertia axis of geometry domain by using extended AFT-Delaunay algorithm,and the domain is divided dynamically into a plurality of mutually d ecoupled subdomains.The algorithm uses the OpenMP multi-thread method to allocate the subdomains to multiple CPUs,and subdomain meshes are generated in parallel.The mesh generation within subdomains reuses AFT-Delaunay algorithm,which ensures the quality,speed and consistency of mesh requirements.Since the interface wall mesh is generated firstly,the mesh generation of each subdomain is completely decoupled from each other,so the parallel mesh generation processes run without communication.The proposed method overcomes the mesh quality degradation problem of the parallel interface and has good parallel speedup,which is able to fully automatically generate high-quality triangular mesh with highly efficiency in parallel manner.
【期刊名称】《计算力学学报》
【年(卷),期】2017(034)002
【总页数】办公自动化系统论文6页(P191-196)
【关键词】并行网格生成;解耦;AFT-Delaunay;墙网格
【作 者】ses张宇航;余飞;昌继海;曹杰;关振
【作者单位】大连理工大学 工程力学系 工业装备结构分析国家重点实验室,大连 116024;大连理工大学 工程力学系 工业装备结构分析国家重点实验室,大连 116024;大连理工大学 工程力学系 工业装备结构分析国家重点实验室,大连 116024;大连理工大学 工程力学系 工业装备结构分析国家重点实验室,大连 116024;大连理工大学 工程力学系 工业装备结构分析国家重点实验室,大连 116024
【正文语种】中 文
【中图分类】O242.21
有限元网格生成是工程计算的重要领域。大规模工程计算如在计算流体力学(CFD)以及飞行器的设计等数值模拟中，需要生成大规模的网格来进行数值计算。随着求解问题的规模日益增大，通常一个计算问题所需要生成有限元网格的数量，少则几千多则上百万个[1]。随着计算机技术的发展，并行计算机系统如多核共享内存和分布式计算机已经普及。因此，开发高效率、高质量的并行网格生成算法势在必行。
目前，并行网格生成的主要方法是区域分解[2,3]方法。该方法首先将待求解区域分解成一定数量的子区域，而后将这些子区域分配给多个处理器并行生成子区域的网格，最后再将各个子区域网格整合在一起。区域分解方法可以方便地复用现有成熟高效的串行算法，能够并行生成高质量的网格。根据并行网格生成算法的耦合程度，大致分为强耦合[4]、部分耦合[5]和解耦合[6]三类。耦合度的高低决定了算法并行处理的通信强度，以及处理一致性所需的同步类型和数量。高耦合度的并行算法可以提高网格质量，但不能满足大规模计算对网格生成速度的需求；而低耦合度算法在提高网格生成速度的同时却降低了网格质量。
并行网格生成方法中，Delaunay法[7,8]和AFT法[9]是生成非结构网格的主要方法。Delaunay法的优点是有严谨的数学理论基础[7]，以及Delaunay的准则保证了插点算法的局部操作性，因而适合并行生成网格。AFT法在边界恢复和生成网格的单元质量方面具有优势。Chew等[10]提出基于约束Delaunay[11]网格剖分的并行网格生成算法。当分区内网格生成算法涉及到分区边界时，即在分区边界上插入新的节点，与此同时与该分区共享边界的另一个分区，也在同样位置插入新节点以保持拓扑一致。分裂分区界面的操作必然需要两个分区之间的通讯，降低算法并行效率。Cignoni等[12]提出的DeWall算法是一种解耦并行算法，对传统的分而治之(D&C)方法进行了改进。DeWall算法的主要操作步骤是生成相
对复杂的Delaunay网格墙的过程，这限制了算法的并行可扩展性。同时在构造Delaunay墙网格时，会出现质量很差的单元。Linardakis等[13]提出一种基于中轴面连续分区的二维并行算法，即在并行算法之前对目标区域进行几何分区[14]。然后在分区界面附近生成一定密度的网格，以保证各个分区内的Delaunay插点操作不会穿透分区界面。该算法也是一种解耦的并行算法，但由于几何分区界面和已有边界通常会出现尖角，对于复杂区域要避免这样的尖角难度很大，而这些特征会影响生成的网格质量。
为了克服上述方法的不足，本文提出一种结合AFT与Delaunay两者优点，优先生成交界面墙网格的解耦并行网格生成算法。本文方法能够生成高质量的并行交界面网格，具有良好的并行加速比，能够全自动、高效率地并行生成高质量的三角网格。
本文方法与DeWall类似，优先生成沿区域惯性轴的墙网格。每次分解将区域分成左右区域以及墙网格三部分，墙网格使左右两个区域完全解耦。本文方法与DeWall方法的不同主要有两点，(1) 墙网格的生成方法不同。本文方法是沿着惯性轴使用AFT方法向区域内部执行Delaunay插点操作，生成满足质量要求的三角形单元，形成高质量墙网格。这种墙网格生成方法比DeWall方法控制力更强。(2) 网格质量高。由于采用AFT-Delaunay方法，保证了
生成的墙网格都是高质量的三角形，不会出现DeWall方法中质量差的网格。本文方法子区域内部网格生成复用AFT-Delaunay墙网格生成算法，保证了子区域内部网格同墙网格一样具有高质量网格。
2.1 整体算法
输入:模型离散边界
输出:模型内部网格
(1) 首先对输入几何区域的外部以及内部几何空洞的离散边界表达，进行初始约束Delaunay网格剖分，形成初始粗网格。
(2) 采用重心坐标法[15]计算区域背景网格的重心坐标，由重心x和y坐标轴确定竖直及水平方向的惯性轴引导AFT-Delaunay前沿推进方向，生成墙网格并输出。
(3) 利用单元邻接关系收集连通区域网格，计算子区域面积与模型总面积比值。如果比值大于设定值转入步骤(2)，否则转入步骤(4)。
(4) 复用AFT-Delaunay墙网格生成算法，生成子区域内部网格并输出。
2.2 AFT-Delaunay墙网格生成
算法首先将几何区域与惯性轴相交的某一离散边界作为起始推进前沿。然后，从推进前沿开始沿着区域惯性轴，用AFT方法根据单元尺寸的要求执行Delaunay插点操作，生成高质量的三角形墙网格。算法1列出了墙网格生成步骤，图1展示了算法生成AFT-Delaunay墙网格的过程。
(1) 取得区域边界与惯性轴相交的离散边boundaryFronts，作为生成墙网格的推进前沿，向区域内部推进生成单元。
(2) 采用扩展的AFT-Delaunay方法沿区域惯性轴推进，连续生成三角形单元。
晚钟 电影(3) 单元尺寸函数(element size function)计算推进前沿AB的第三点C，生成满足质量要求的三角形单元如图2所示。学术长青
(4) 执行Delaunay插点操作，将推进前沿AB生成的第三点C插入到网格中。
(5、6) 检测新生成AFT-Delauy单元的三个相邻单元，判断邻接单元如果与惯性轴相交，则进行步骤(7)更新墙单元的推进前沿队列，从而由推进前沿继续生成墙网格单元。
(8) 输出:墙网格。
2.3 子区域网格生成
以矩形离散边界区域为例，算法优先生成各个子区域交界的墙网格，如图3所示，因此各个子区域的网格生成彼此完全独立解耦。图4展示了墙网格将一个矩形区域分解成4个解耦区域的情况，其中最左上区域展示了子区域复用AFT-Delaunay墙网格生成算法来生成子区域内部网格的中间过程。
3.1 区域分解
用麦道30P30N三段翼型作为算例，验证本文并行算法的有效性。这里给出算法生成墙网格，将翼型区域分解成8个解耦子区域的情况如图5所示。由于算法采用AFT-Delaunay方法生成网格，从图6的局部放大图可以看出，墙网格(白网格)都是高质量的三角形网格。同时子区域内部及其边界处网格(黑网格)，保持了同墙网格一致的高质量三角形网格。
3.2 并行策略
由于本文算法优先生成各个子区域交界的高质量墙网格，各个子区域的网格生成彼此完全独立解耦，并行求解过程无需通信，因此算法适合并行执行。本文采用共享内存模型，使用OpenMP作为算法并行化实现平台，采用OpenMP的虚拟任务方法实现了动态线程并行。
电视剧大马帮(1) 对于墙网格分割的各个解耦子区域网格生成任务(mission)，采用OpenMP动态(dynamic)线程调度方式实现并行处理。
(2) 判断子区域面积与模型总面积比值决定是否继续分割子区域任务(mission)。SPLIT标志表示当前网格生成任务(mission)需要生成AFT-Delaunay墙网格继续进行区域分解；MESHDO-MAIN表示满足区域分解要求，可以复用墙网格算法生成子区域内部网格。
(3) 采用OpenMP临界区(critical)技术对线程之间共享的资源即任务队列(missions pool)进行保护,将分割的子区域任务mission加入任务队列，进行多线程并行生成子区域网格。
本文并行算法使用一台Dell PRECISION t5500工作站：CPU Intel Xeon X5650(2×2.67 GH
Z)、24线程、24G内存、Windows7 64位操作系统运行。并行运行算例分别进行2，4，8和16个子区域分解，并行生成大约630万个三角形单元。
区域分解并行算法可以方便地复用成熟串行算法。这里对比了本文并行算法与二维串行Delaunay网格生成程序Triangle[16]在生成相同规模(约630万)网格时的单元质量情况。对于三角形单元的质量，本文选取三角形单元内切圆半径r和外接圆半径R之比2r/R，作为网格单元质量的度量。表1和图7列出了Triangle以及不同分区数量和算例并行网格生成的网格单元质量分布情况。本文并行算法算例分区并行生成的网格中99%的三角形单元分布在单元质量0.9～1， 整体网格的最差单元质量为0.43，平均单元质量为0.99。由表1可知，对于最差单元质量与生成单元总数两个指标，本文并行算法与自身单线程串行运行生成网格质量相比仅有小幅波动，说明本文所提出的并行算法能够保持同串行算法的一致性，能够生成高质量的网格。由于采用AFT-Delaunay法，表1的Triangle网格质量0.9～1之间占比只为56.8%，结合图7可以看出本文方法生成网格从单元质量分布和单元质量均值方面明显好于Triangle生成的网格质量。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议