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

• 作者: 徐权 朱朝艳 王俊吉 郑澎 陈建军
• 来源期刊: 计算机工程与科学
• 学科: 数学
• 关键词: Delaunay三角化 网格生成 多线程并行算法 并行计算 OpenMP 原子操作
• 年，卷（期）: 2018,（5）
• 所属期刊栏目: 高性能计算
• 页码范围: 773-779
• 页数: 7页
• 分类号: O246
• 字数: 4275字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2018.05.002

摘要

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