基于无锁原子操作的多线程并行Delaunay三角化算法

基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法。在串行算法的基础上，对点集引入Hilbert排序，使相邻点在几何上亦相邻。引入互斥机制--仅当各空腔无公共单元及公共相邻边时，才可同时插入，根据Delaunay局部性准则可保证整个网格都具备Delaunay属性。每个单元用一个原子变量标记该单元是否已被占有，在计算Delaunay空腔时，各线程将试图写入该原子变量，但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权，以保证算法的互斥性。经数值实验表明，对于107的点集，该算法在16核下加速比可达7.06倍。

A multithreaded parallel Delaunay triangulationalgorithm based on lock-free atomic operations

This paper uses OpenMP to implement a fine-grain parallel incremental insertion algorithm for Delaunay triangulation, which adopts an exclusive criterion of cavity overlapping and lock-free atomic operations. Based on the serial algorithm, Hilbert sorting is introduced into the point set so that adjacent points are also geometrically adjacent. An exclusive criterion that the points can be inserted simultaneously only if their cavities share neither common elements nor common boundaries is introduced to guarantee that the whole mesh has the Delaunay property according to the Delaunay lemma. Each element uses an atomic variable to mark whether the element is occupied by any of the threads. While calculating the Delaunay cavities, threads try to occupy those elements, but only one of them can succeed to write the atomic variable, so the exclusivity of the algorithm is guaranteed. Numerical experiments on the platform with a 16-core Intel Xeon CPU E5-2640 v3 @ 2.60GHz and a 64 GiB memory show that,for a 107-point set, the algorithm can reach the speedup of 7.06 with 16 cores.