Parallel 2D Delaunay triangulations in HPP and MPI

This paper reports on efficient parallel implementations of two-dimensional Delaunay triangulation in High Performance Fortran (HPF) and in Message Passing Interface (MPI). Our parallelization algorithm performs subblock triangulation and boundary merge independently at the same time. The sub-block triangulation is by a divide & conquer Delaunay algorithm known for its sequential efficiency, and the boundary triangulation is by an incremental construction algorithm with low overhead. Compared to prior work, our parallelization method is both simple and efficient. In the paper we also describe a solution to the collinear points problem that usually arises in large data sets for divide & conquer algorithm. Our experiences with the HPF implementation show that with careful control of the data distribution, we are able to parallelize the program using HPF´s standard directives and extrinsic procedures. Experimental results on several parallel platforms, including an IBM SP2 and a DEC Alpha farm, show that a parallel efficiency of 31%-59% can be achieved for an 8-node distributed memory system. We also compare efficiency of the HPF implementation to that of a similarly hand-coded MPI implementation