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

摘要

有限元法广泛应用于科学研究与工程设计计算，其关键环节之一是输入数据的准备，即有限元网格生成。一方面，网格生成涉及的人工工作量通常占据完成数值模拟全过程人工工作总量的绝大部分，是主要性能瓶颈。另一方面，网格质量是影响数值模拟计算精度和计算效率至关重要的因素。
　　四面体网格适应任意复杂外形，自动生成和自适应更新能力强，在有限元分析中得到广泛采用。因边界约束和网格生成算法内在的原因，主流算法生成的初始四面体网格都会包含一定数量的低质量单元，需结合光滑化与拓扑变换等局部网格编辑操作予以优化调整后，才能满足后续有限元分析的要求。为尽可能提高网格质量，网格优化需循环迭代调用局部网格编辑操作，非常耗时。有数据表明，优化过程比利用快速Delaunay三角化算法生成同等规模网格的过程要慢5倍以上。大规模四面体网格生成实践中，网格优化已成为主要的性能瓶颈。
　　为此，本文针对典型四面体网格优化算法包含的光滑化和拓扑变换等2类不同的局部编辑操作，开发了对应的任务分解策略以及相应的多线程并行算法。并行光滑化算法的任务分解策略采用经典的图着色算法，首先基于网格节点邻接关系构建邻接关系图，再通过对邻近关系图着色将待光滑点分解为多个独立点集。因每个点集中的点相互之间均不相邻，多个线程可同时移动对应点集中的点以优化邻接单元质量。
　　并行拓扑变换算法的任务分解策略是本文的主要创新，其主要步骤如下:
　　(1)计算待执行变换操作涉及到的四面体单元的特征点坐标;
　　(2)基于特征点位置利用希尔伯特曲线对所有操作进行线性化排序;
　　(3)将排序后的操作按序等分成与线程数相等的子集。
　　拓扑变换算法的操作定义在四面体单元形成的空腔上执行。网格优化时，单个线程按序处理所分配子集中的局部操作。如不同线程同时执行的局部操作涉及的空腔出现干涉，只允许其中1个线程执行操作，其余线程放弃执行本次操作。因不同线程同时执行的操作在希尔伯特曲线上相距足够远，这些操作对应的空腔相互干涉的概率非常低，上述处理干涉情形的策略既易于实现，引起的性能损失也被证明可以接受。
　　本文有针对性地提出了多项加速算法并行性能的技术，基于共享内存并行编程语言OpenMP开发了一套集成上述并行拓扑变换与并行光滑化算法在内的多线程并行四面体网格优化算法，选取典型输入研究了该算法的并行性能，初步验证了算法的有效性和适用性。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 四面体网格质量的度量准则

1．3 网格优化算法流程

1．4 网格优化算法并行化研究

1．5 OpenMP并行化技术

1．6 研究思路及创新点

1．7 文章结构

第2章 串行四面体网格优化算法

2．1 引言

2．2 拓扑优化算法

2．2．1 边删除算法

2．2．2 多面删除算法

2．2．3 边收缩算法

2．2．4 边分割算法

2．3 点光滑化算法

2．4 串行算法比较

第3章 并行网格优化算法

3．1 引言

3．2．1 希尔伯特空间曲线

3．2．2 边删除算法并行化

3．2．3 多面删除算法并行化

3．2．4 边收缩算法并行化

3．2．5 边分割算法并行化

3．2．6 并行拓扑优化算法的优化

3．3 点光滑化网格优化算法并行化

3．3．1 图着色算法

3．3．2 基于图着色的并行点光滑化

第4章 数值实验及分析

4．1 引言

4．2．1 边删除算法

4．2．2 多面删除算法

4．2．3 边收缩算法

4．2．4 边分割算法

4．3 点光滑化优化算法并行实验分析

4．4 单次优化流程时间占比分析

4．5 整体优化流程并行实验分析

4．6 本章小结

第5章 总结及展望

5．1 研究总结

5．2 未来展望

参考文献

作者在学期间主要的研究成果

致谢