OpenACC Based GPU Parallelization of Plane Sweep Algorithm for Geometric Intersection
OpenACC Based GPU Parallelization of Plane Sweep Algorithm for Geometric Intersection
复制标题
基于OpenACC的几何交平面扫描算法的GPU并行化
DOI：
10.1007/978-3-030-12274-4_6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Puri
中科院分区：
文献类型：
--
作者：
Anmol Paudel;S. Puri
线段求交是计算几何中的基本运算之一。地理信息系统(GIS)中的复杂问题，如使用多边形数据寻找地图覆盖或空间连接，需要求解线段交点。平面扫描范式用于高效地寻找几何交点。然而，由于其对空间事件的有序处理，因此很难并行化。提出了一种新的细粒度几何求交并行算法，并利用OpenMP和Openacc实现了该算法的CPU和GPU。据我们所知，这是第一个展示了平面扫描在GPU上有效并行化的工作。
Line segment intersection is one of the elementary operations in computational geometry. Complex problems in Geographic Information Systems (GIS) like finding map overlays or spatial joins using polygonal data require solving segment intersections. Plane sweep paradigm is used for finding geometric intersection in an efficient manner. However, it is difficult to parallelize due to its in-order processing of spatial events. We present a new fine-grained parallel algorithm for geometric intersection and its CPU and GPU implementation using OpenMP and OpenACC. To the best of our knowledge, this is the first work demonstrating an effective parallelization of plane sweep on GPUs.