Multi-threaded Parallel Tetrahedral Mesh Generation And Quality Improvement Algorithms

In CSM(Computational Solid Mechanics)and CFD(Computational Fluid Dynamics),numerical simulations such as the Finite Element methods rely on the input of high-precision,highquality mesh to compute numerical solutions.Some numerical simulation methods such as DNS(Direct Numerical Simulation),LES(Large Eddy Simulation),and DES(Distributed Eddy Simulation)require meshes with hundreds of millions or even billions elements.Besides,in the field of numerical simulations,generating meshes of complex areas usually needs to refine and iterate continuously to meet design and computation requirements.How to generate large-scale meshes quickly,and how to generate large and reliable meshes quickly,become the urgent problems to be solved in mesh generation.Staring with the classic Delaunay Triangulation(DT)algorithm,where there are only localmodifications in each iteration,we propose the basic parallel principle: only when the elements to be modified(saying the “cavity”)and their boundaries of two modifications are not overlapped,should these two modifications be executed in parallel.An existing parallel strategy is to add a synchronization between cavity calculations and modifications,separating the read and write parts.However,a large amount of synchronizations bring wasted time waiting for the barriers and the barrier overhead itself.Hence,this paper introduces a parallel strategy with the atomic operations: for each element,when a thread is trying to get the write access of it,it can be guaranteed that only one thread,via a single atomic compare exchange operation,will successfully get the write access,which avoids data racing.Within the NUMA(Non-uniform Memory Access)bound(usually 8 cores),the atomic operations are quite efficient,compared to the locks.Applying it to the DT algorithm,it can achieve about 4.7 times speedup with 8 threads.Then we apply such parallel strategy based on atomic operations to the recursive shell transformations(ST)in mesh improvement.Not only it solves the difficulties where the existing parallel strategies based on synchronizations cannot be used in recursive ST,because cavities might be dynamically extended during the modification,but also largely promotes the performance of the mesh improving algorithm with reserving the quality improving ability of the serial algorithm,thanksto the recursive ST algorithm's ability of dealing with extremely bad elements.Here are the innovations of this article:1.We have proposed the multithreaded Delaunay triangulation algorithm based on lock-free atomic operations,which have reduced the wasted time when inserting points in the barrier-based strategy,and have increaded the parallel efficiency.In our numerical experiments,we haved achieved up to 7-times speedup with 16 threads.2.Using the parallel graph coloring algorithm,we revised the single coloring iteration into multiple ones,and the smoothing can be done in parallel.In our numerical experiments,we have achieved up to more than 9-times speedup with 16 threads.3.We have proposed a multithreaded parallel strategy based on lock-free atomic operations.Applying it to the parallel recursive ST algorithm,we have solved the difficulty of the existing parallel strategies based on synchronizations unable to deal with cavities that might be dynamically extended during modification.Using parallel recursive ST,together with the parallel smoothing and other parallel topological transformations,we have implemented the parallel mesh improving algorithm which reserves the serial algorihm's ability of quality improvement,and largely promote its time performance,up to 7-times speedup in total with 8 threads,compared with the original serial algorithm.