Efficient parallel implementations of near Delaunay triangulation with High Performance Fortran

author: Min-Bin Chen, Tyng-Ruey Chuang and Jan-Jan Wu
publication date: October 2004
cite this with: Min-Bin Chen, Tyng-Ruey Chuang and Jan-Jan Wu. Efficient parallel implementations of near Delaunay triangulation with High Performance Fortran. Concurrency and Computation: Practice and Experience, 16(12):1143-1159. October 2004.
link this with: http://tsm.iis.sinica.edu.tw/papers/ccpe04/
copyright: all rights reserved
category: others
tag:
full paper: pdf

Abstract

Unstructured mesh generation exposes highly irregular computation patterns, which imposes a challenge in implementing triangulation algorithms on parallel machines. This paper reports on an efficient parallel implementation of near Delaunay triangulation with High Performance Fortran (HPF). Our algorithm exploits embarrassing parallelism by performing sub-block triangulation and boundary merge independently at the same time. The sub-block triangulation is a divide & conquer Delaunay algorithm known for its sequential efficiency, and the boundary triangulation is an incremental construction algorithm with low overhead. Compared with 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. 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 42–86% can be achieved for an eight-node distributed memory system. We also compare efficiency of the HPF implementation with that of a similarly hand-coded MPI implementation. Copyright c 2004 John Wiley & Sons, Ltd.

 
papers:ccpe04:home Last modified: 2007/10/19 16:40