Parallelization of Plane Sweep Based Voronoi Construction with Compiler Directives
Parallelization of Plane Sweep Based Voronoi Construction with Compiler Directives
复制标题
DOI：
10.1109/compsac.2019.00136
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Anmol Paudel;Jie Yang;S. Puri
中科院分区：
文献类型：
--
作者：
Anmol Paudel;Jie Yang;S. Puri
Voronoi图的构造是计算几何和空间计算中常见的基本问题。文献中存在许多用于Voronoi图构建的顺序和并行算法。本文提出了一种多线程方法，其中我们用编译器指令增强了Fortune的planessweep算法的现有顺序实现。我们的细粒度并行算法的新颖之处在于利用了算法过程中遇到的每个事件点的并发性。在英特尔至强E5 CPU上，与使用包含2k-128k站点的数据集的顺序实现相比，我们使用OpenMP的共享内存并行化实现了大约2倍的加速。
Voronoi diagram construction is a common and fundamental problem in computational geometry and spatial computing. Numerous sequential and parallel algorithms for Voronoi diagram construction exists in literature. This paper presents a multi-threaded approach where we augment an existing sequential implementation of Fortune's planesweep algorithm with compiler directives. The novelty of our fine-grained parallel algorithm lies in exploiting the concurrency available at each event point encountered during the algorithm. On the Intel Xeon E5 CPU, our shared-memory parallelization with OpenMP achieves around 2x speedup compared to the sequential implementation using datasets containing 2k-128k sites.