Parallel Processing for Geometric Applications
Chandrasekhar Narayanaswami · 1995
A framework is presented for the parallelization of a set of commonly encountered geometric problems. It combines the use of the uniform grid technique, parallel sorting, and data partitioning for parallelization. For many problems, the use of these techniques leads to algorithms whose complexity is linear in the sizes of the input, output, and intermediate results. In average cases, the sizes of the intermediate results are linear in some metric of the input and output. The data structures used by these techniques are simple to build, regularize memory access patterns, and promote locality of memory references in the parallel machine. The framework is used to develop parallel algorithms for determining the convex hull of a set of points in the plane, the intersections between a set of segments in the plane, and the boundaries of the Boolean combinations of polygons and polyhedra. Approximate complexity analyses for the convex hull and Boolean combination algorithms are provided and compared with experimental results. The implementation on a shared-memory Sequent Balance 21000 shows speedups ranging from 9 to 12 with 15 processors. Close to linear speedups have been achieved in most phases of our algorithms. Implementation on the Intel iPSC Hypercube also shows respectable performance.