OpenACC Based GPU Parallelization ofPlane Sweep Algorithm for GeometricIntersection
Anmol Paudel
Satish Puri
Marquette University
Milwaukee, WIIntroduction• Scalable spatial computation on high performance computing (HPC)
environment has been a long-standing challenge in computational
geometry.
• Harnessing the massive parallelism of graphics accelerators helps tosatisfy the time-critical nature of applications involving spatial
computation.
• Many computational geometry algorithms exhibit irregularcomputation and memory access patterns. As such, parallel
algorithms need to be carefully designed to effectively run on a GPUarchitectureIntroduction (contd.)• Geometric intersection is a class of problems
involving operations on shapes represented asline segments, rectangles (MBR), and polygons.
• Line segment intersection problem is one of themost basic problem in spatial computing and allother operations for bigger problems like polygon
overlay or polygon clipping depends on resultsfrom itLine Segment Intersection Problem• The line segment intersection problem basically asks two questions –• Intersection detection problem• “are the line segments intersecting or not?”• And if they are intersecting• intersection reporting problem• “what are the points of intersection?”• We present an algorithmic solution for the secondSome Common Methods• Simple brute force method• Filter and refine method that uses a heuristic to avoid unnecessaryintersection computations• Plane Sweep

Contribution• To the best of our knowledge, this is the first work demonstrating aneffective parallelization of plane sweep on GPUs
• A reduction based technique to find neighbors in the sweepline toreduce the added complexities of parallelization• Completely directives-based implementation of all algorithmsPlane Sweep• Technique to solve computational geometry problems by sweeping throughthe problem space• Plane Sweep reduces O(n2) segment to segment pair-wise computation
into• O(nlogn) for identification• O(n + klogn) for reporting, good algorithm when k << n• Works best if the dataset can fit in memory• Parallelization difficult due to the in-order sequential processing of events
stored in a binary tree and a priority queue data structure.
• Widely used in many other computational geometry problems like Voronoi
diagram or Delaunay triangulationIn Computational Geometry• Lines in computer application are usually finite lines with start andend points – not just y = mx + c• Finding line intersection in computers might not be as simple assolving two mathematical equations.
• Complex geometries like triangle, quadrilateral or any n-vertices
polygon are further stored as a bunch of points.
• For example a quadrilateral would be stored like
(x1,y1,x2,y2,x3,y3,x4,y4)

Directive-based Programming• I would usually have a slide here discussing about Directive-based
programming and why we choose that route• But since this is WACCPD …
• Let’s just say directives are the future of accelerators and parallel
programmingStart Event Sweeplines

Algorithmic Analysis• Time Complexity• each of the N lines will have two sweeplines => 2N2 comparison steps• each of the K intersection event will also produce a sweepline => K*N steps• total is 2N2 + K ∗ N steps.
• Assuming K << N, the time-complexity of this algorithm is O(N2)• Space Complexity• There will be 2N sweeplines for N lines• K sweeplines for K intersection events.
• Total Memory requirement will be 2N +K• Assuming K << N, the space-complexity of the algorithm is O(N).

41010

Segment Intersection Phases

Testing parallelizability with OpenMP

Machines Used
• Everest cluster at Marquette University• This machine was used to run the OpenMP codes and on the Intel Xeon E5
CPU v4 E5-2695• Bridges cluster at the Pittsburgh Supercomputing Center• A single GPU node of this cluster was used which contained the NVIDIA Tesla
P100• NCSA ROGER Supercomputer• Sequential GEOS and OpenMP code was run on Intel Xeon E5-2660v3• GPU experiments using OpenACC on Nvidia Tesla P100

Conclusion• Using Nvidia Tesla P100 GPU, our implementation achieves around
40X speedup for line segment intersection problem on 40K and 80K
data sets compared to sequential CGAL library• Directives prove to be a promising avenue to explore in the future forparallelizing other spatial computations as well.

THANK YOU!