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

计算机工程与科学

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

王俊吉1,2,朱朝艳1,2,4,陈建军1,2,郑澎3，5,徐权3

(1.浙江大学工程与科学计算研究中心，浙江杭州 310027;2.浙江大学航空航天学院，浙江杭州 310027;

3.中国工程物理研究院高性能数值模拟软件中心，北京 100088;4.浙江大学宁波理工学院，浙江宁波 315100;

5.中国工程物理研究院计算机应用研究所，四川绵阳 621900）

收稿日期:2017-11-02 修回日期:2018-02-11 出版日期:2018-05-25 发布日期:2018-05-25
基金资助:
科学挑战专题（TZ2016002）

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.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

摘要：

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

关键词: Delaunay三角化, 网格生成, 多线程并行算法, 并行计算, OpenMP, 原子操作

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

王俊吉1,2,朱朝艳1,2,4,陈建军1,2,郑澎3，5,徐权3. 基于无锁原子操作的多线程并行Delaunay三角化算法[J]. 计算机工程与科学.

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

A multithreaded parallel Delaunay triangulation

algorithm based on lock-free atomic operations

[J]. Computer Engineering & Science.

[1]	傅游, 韩昊, 孙月娇, 梁建国, 叶雨曦, 花嵘. 基于OpenMP的硅晶体分子动力学模拟的空间分解着色及向量化研究#br#[J]. 计算机工程与科学, 2024, 46(09): 1566-1575.
[2]	吴超, 卫谦, 周俊伟, 李会民, 孙广中. 基于异构计算平台的背景噪声预处理并行算法[J]. 计算机工程与科学, 2023, 45(10): 1711-1719.
[3]	王鑫, 彭健. 基于HYB格式SpMV在新一代申威架构上的实现与优化[J]. 计算机工程与科学, 2023, 45(10): 1754-1762.
[4]	刘屹成, 刘晓燕, 严馨. 并行平衡级联支持向量机[J]. 计算机工程与科学, 2023, 45(07): 1170-1177.
[5]	臧照虎, 李晨, 王耀华, 陈小文, 郭阳. 面向众核系统的层次化栅栏同步机制[J]. 计算机工程与科学, 2022, 44(11): 1901-1908.
[6]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[7]	范培勤, 过武宏, 韩梅, 唐帅, 张驰, . 水声环境特征参数并行预报方法研究[J]. 计算机工程与科学, 2021, 43(11): 1920-1925.
[8]	龚昊, 刘莹, 冯建周, 赵仁良, 冷佳旭, . 基于GPU加速的脉冲多普勒雷达信号处理[J]. 计算机工程与科学, 2021, 43(07): 1141-1149.
[9]	焦育威, 王鹏, 辛罡, . 基于采样尺度自适应的多尺度量子谐振子优化算法并行化[J]. 计算机工程与科学, 2021, 43(07): 1200-1209.
[10]	俞茂学, 贾东宁, 魏志强, 许佳立, 马广浩. 一种基于国产异构众核处理器的C++智能源码转换框架[J]. 计算机工程与科学, 2021, 43(06): 997-1005.
[11]	丁哲昭, 储根深, 胡长军, 李扬. 基于申威众核处理器的圣维南求解程序的并行与优化[J]. 计算机工程与科学, 2021, 43(05): 820-829.
[12]	明平洲, 李治刚, 刘婷, 芦韡, 刘东, 曾辉, 余红星. ARM计算环境下堆芯程序的移植[J]. 计算机工程与科学, 2021, 43(04): 681-688.
[13]	丁峻宏, 苗新强, 李根国. 面向异构超算的结构分析高效并行计算方法[J]. 计算机工程与科学, 2020, 42(12): 2133-2140.
[14]	李彪, 刘杰, . 面向天河2A系统的基于蒙特卡罗方法的粒子输运异构协同计算[J]. 计算机工程与科学, 2020, 42(11): 1922-1928.
[15]	徐传福, 车永刚, 李大力, 王勇献, 王正华. 天河超级计算机上超大规模高精度计算流体力学并行计算研究进展[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1815-1826.