| 基于无锁原子操作的多线程并行Delaunay三角化算法 |
| |
| 作者姓名： | 王俊吉 朱朝艳 陈建军 郑澎 徐权 |
| |
| 作者单位： | (1.浙江大学工程与科学计算研究中心,浙江 杭州 310027;2.浙江大学航空航天学院,浙江 杭州 310027;
3.中国工程物理研究院高性能数值模拟软件中心,北京 100088;4.浙江大学宁波理工学院,浙江 宁波 315100;
5.中国工程物理研究院计算机应用研究所,四川 绵阳 621900） |
| |
| 基金项目： | 科学挑战专题（TZ2016002） |
| |
| 摘 要： | 基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法。在串行算法的基础上,对点集引入Hilbert排序,使相邻点在几何上亦相邻。引入互斥机制--仅当各空腔无公共单元及公共相邻边时,才可同时插入,根据Delaunay局部性准则可保证整个网格都具备Delaunay属性。每个单元用一个原子变量标记该单元是否已被占有,在计算Delaunay空腔时,各线程将试图写入该原子变量,但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权,以保证算法的互斥性。经数值实验表明,对于107的点集,该算法在16核下加速比可达7.06倍。
|
| 关 键 词： | Delaunay三角化 网格生成 多线程并行算法 并行计算 OpenMP 原子操作 |
| 收稿时间： | 2017-11-02 |
| 修稿时间： | 2018-05-25 |
|
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
