• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A multithreaded parallel Delaunay triangulation
algorithm based on lock-free atomic operations

WANG Jun-ji1,2,ZHU Chao-yan1,2,4,CHEN Jian-jun1,2,ZHENG Peng3,5,XU Quan3   

  1. (1.Center for Engineering and Scientific Computation,Zhejiang University,Hangzhou 310027;
    2.School of Aeronautics and Astronautics,Zhejiang University,Hangzhou 310027;
    3.Software Center for High Performance Numerical Simulation,China Academy of Engineering Physics,Beijing 100088;
    4.Ningbo Institute of Technology,Zhejiang University,Ningbo 315100;
    5.Institute of Computer Application,China Academy of Engineering Physics,Mianyang 621900,China)
  • Received:2017-11-02 Revised:2018-02-11 Online:2018-05-25 Published:2018-05-25

Abstract:

 

 
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.
 

Key words: Delaunay triangulation, mesh generation, multithreaded parallel algorithm, parallel computing, OpenMP, atomic operation