Implementation and Evaluation of an Efficient 2D Parallel Delaunay Triangulation Algorithm,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1997
Accession Number
ADA328005

Entities

People

  • Jonathan C. Hardwick

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Fluid Dynamics
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Differential Equations
  • Efficiency
  • Equations
  • Floating Point Operations
  • Geometry
  • Language
  • Normal Distribution
  • Partial Differential Equations
  • Three Dimensional
  • Triangles
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.