论文部分内容阅读
在计算固体力学、计算流体力学等领域中,以有限元方法为代表的数值模拟依赖高精度、高质量的网格输入。一些如直接数值模拟、大涡模拟、分离涡模拟等数值模拟方法所需网格规模通常在数亿甚至数十亿的量级。在数值模拟领域中,要生成复杂区域的网格,通常需要不断迭代加密,以满足设计与计算要求。如何快速生成大规模的网格,以及如何快速生成质量可靠的大规模网格,成为网格生成研究中亟待解决的难题。本文始于Delaunay三角化的经典B-W插点算法,根据算法中的空腔局部修改特性,建立了并行基本原则:仅当两个点所涉及修改的单元范围(即“空腔”)及其边界无交叠时,二者方可同时执行。既有的并行策略是在计算空腔与空腔修改之间插入同步,以分离读写过程。但大量同步带来了不必要的等待与同步开销的浪费。因此本文提出了一种更细粒度的避免数据竞争的机制——基于无锁原子操作的并行方法:对每一个单元,某个线程需要获取其写入权限时,只需通过一次原子条件交换操作即可保证只有一个线程处于可写状态,从而避免了数据竞争。原子变量在NUMA范围(通常是8核)内相比加锁而言效率很高,将其应用于Delaunay三角化算法中,8线程下达到约4.7倍的加速。将基于原子操作的并行方法应用于网格质量优化中的递归壳变换中,不仅解决了既有基于同步的并行方法无法并行递归壳变换(因其空腔需动态扩展)的困难,并且得益于递归壳变换对极差单元的处理能力,使并行网格优化算法在保有串行算法的优化能力基础上,性能得以大幅提升,在8线程下全优化算法达到原串行算法7倍以上的速度。本文的创新点如下:1.提出了基于无锁原子操作的多线程Delaunay三角化并行插点算法,较好的处理了基于同步并行方法进行插点时,同步等待引起的时间浪费问题,提高了并行效率。在实验环境中16线程实现了7倍以上的加速。2.将并行图着色算法应用于点光滑化算法的并行化,把一轮着色改进为多轮着色,基于高效的多轮着色选取可并行进行光滑处理的点集。在实验环境中,16线程实现了9倍以上的加速。3.针对同步并行方法无法动态扩展空腔的困难,提出了基于无锁原子操作的多线程并行递归壳变换算法。将并行递归壳变换算法、并行点光滑算法与其他拓扑变换算法结合,实现了与原串行网格优化算法相当的优化能力,并且显著提升它的时间效率。在实验环境中,8线程下实现了7倍以上的加速。