Accession Number : ADA328005
Title : Implementation and Evaluation of an Efficient 2D Parallel Delaunay Triangulation Algorithm,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Hardwick, Jonathan C.
PDF Url : ADA328005
Report Date : APR 1997
Pagination or Media Count : 20
Abstract : 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.
Descriptors : *ALGORITHMS, *PARALLEL PROCESSING, DATA BASES, DATA MANAGEMENT, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, COMPUTER PROGRAM VERIFICATION, TRIANGULATION.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE