Computer Science Department
School of Computer Science, Carnegie Mellon University
Implementation and Evaluation of an Efficient 2D Parallel Delaunay Triangulation Algorithm
Jonathan C. Hardwick
April 1997
An earlier version of this paper appears in Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1997.
CMU-CS-97-129.ps
CMU-CS-97-129.ps.gz
This paper describes the derivation of an empirically efficient
parallel two-dimensional Delaunay triangulation program from a
theoretically efficient CREW PRAM algorithm. Compared to previous
work, the resulting implementation is not limited to datasets with a
uniform distribution of points, achieves significantly better speedups
over good serial code, and is widely portable due to its use of MPI as
a communication mechanism. Results are presented for a
loosely-coupled cluster of workstations, two distributed-memory
multicomputers, and a shared-memory multiprocessor. The Machiavelli
toolkit used to transform the nested data parallelism inherent in the
divide-and-conquer algorithm into achievable task and data
parallelism is also described and compared to previous techniques.
An earlier version of this paper will appear in SPAA'97.
21 pages
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu
School of Computer Science homepage