多线程并行四面体网格优化算法

发布时间：2018-01-09 12:22

本文关键词：多线程并行四面体网格优化算法　出处：《浙江大学》2017年硕士论文　论文类型：学位论文

【摘要】：有限元法广泛应用于科学研究与工程设计计算,其关键环节之一是输入数据的准备,即有限元网格生成。一方面,网格生成涉及的人工工作量通常占据完成数值模拟全过程人工工作总量的绝大部分,是主要性能瓶颈。另一方面,网格质量是影响数值模拟计算精度和计算效率至关重要的因素。四面体网格适应任意复杂外形,自动生成和自适应更新能力强,在有限元分析中得到广泛采用。因边界约束和网格生成算法内在的原因,主流算法生成的初始四面体网格都会包含一定数量的低质量单元,需结合光滑化与拓扑变换等局部网格编辑操作予以优化调整后,才能满足后续有限元分析的要求。为尽可能提高网格质量,网格优化需循环迭代调用局部网格编辑操作,非常耗时。有数据表明,优化过程比利用快速Delaunay三角化算法生成同等规模网格的过程要慢5倍以上。大规模四面体网格生成实践中,网格优化已成为主要的性能瓶颈。为此,本文针对典型四面体网格优化算法包含的光滑化和拓扑变换等2类不同的局部编辑操作,开发了对应的任务分解策略以及相应的多线程并行算法。并行光滑化算法的任务分解策略采用经典的图着色算法,首先基于网格节点邻接关系构建邻接关系图,再通过对邻近关系图着色将待光滑点分解为多个独立点集。因每个点集中的点相互之间均不相邻,多个线程可同时移动对应点集中的点以优化邻接单元质量。并行拓扑变换算法的任务分解策略是本文的主要创新,其主要步骤如下:(1)计算待执行变换操作涉及到的四面体单元的特征点坐标;(2)基于特征点位置利用希尔伯特曲线对所有操作进行线性化排序;(3)将排序后的操作按序等分成与线程数相等的子集。拓扑变换算法的操作定义在四面体单元形成的空腔上执行。网格优化时,单个线程按序处理所分配子集中的局部操作。如不同线程同时执行的局部操作涉及的空腔出现干涉,只允许其中1个线程执行操作,其余线程放弃执行本次操作。因不同线程同时执行的操作在希尔伯特曲线上相距足够远,这些操作对应的空腔相互干涉的概率非常低,上述处理干涉情形的策略既易于实现,引起的性能损失也被证明可以接受。本文有针对性地提出了多项加速算法并行性能的技术,基于共享内存并行编程语言OpenMP开发了一套集成上述并行拓扑变换与并行光滑化算法在内的多线程并行四面体网格优化算法,选取典型输入研究了该算法的并行性能,初步验证了算法的有效性和适用性。
[Abstract]:Finite element method is widely used in scientific research and engineering design, one of the key links is the input data for the finite element mesh generation. On the one hand, the workload of artificial mesh generation involved usually occupy complete numerical simulation for the whole process of artificial work most of the total, is the main performance bottleneck. On the other hand, the grid quality is the simulation factors influencing the calculation accuracy and efficiency of the critical value. The tetrahedral mesh to arbitrary complex shape, automatic generation and adaptive updating ability, has been widely used in finite element analysis. Due to boundary constraints and grid generation algorithm inside, low quality unit mainstream algorithm to generate the initial tetrahedral mesh will contain a certain the number should be combined with local mesh smoothing and topology editing to be optimized, to satisfy the needs of finite element analysis For as much as possible to improve the quality of the grid, grid optimization iteration called local mesh editing operations, very time-consuming. Data show that during the optimization process than using fast Delaunay triangulation algorithm to generate the same size grid was 5 times slower. Large tetrahedral mesh generation practice, mesh optimization has become the main performance bottleneck for this. In this paper, the typical tetrahedral mesh optimization algorithm includes smoothing and topological transformation for 2 different local editing operations, developed the corresponding task decomposition strategy and multi thread parallel algorithm. And the corresponding line smoothing algorithm for task decomposition strategy using graph coloring algorithm, based on the grid node adjacency adjacency relation construction map through the neighborhood graph coloring to smooth point is decomposed into several independent sets. For each point between the points are not. Next, multiple threads can also move the corresponding point of concentration to optimize adjacent element quality. Parallel topology transform algorithm of task decomposition strategy is the main innovation of this paper, the main steps are as follows: (1) to compute feature points perform tetrahedron transform operation involving the coordinates; (2) the feature point location the linear order of all operations by using the Hilbert curve based on; (3) after the operation will be sorted into subsets and thread is equal to the number of sequential execution. Equal operational definition of topological transformation algorithm of cavity formation in tetrahedral mesh optimization. When the local operation of a single thread in order processing sub concentrated. The local cavity operation at the same time to perform different threads to interference, allowing only 1 threads operate the remaining threads to give up the implementation of this operation. Because of simultaneous execution of different threads operating in the Hilbert song The line is far enough, the probability of interference between the cavity corresponding to these operations is very low, the interference strategy is easy to implement, the performance loss caused also proved acceptable. This paper puts forward several accelerated algorithm of parallel performance technology, shared memory parallel programming language OpenMP to develop a set of integrated above parallel topological transformation and parallel smoothing algorithm, multi thread parallel tetrahedral mesh optimization algorithm based on the parallel performance of the algorithm selects the typical input, verify the validity and applicability of the algorithm.

【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TB115

【共引文献】