Revision as of 21:26, 14 September 2017

Parallel Delaunay Refinement (PDR) With TetGen

Overview

The goal of this project is the development of a parallel mesh generator using CRTC’s PDR theory, which mathematically guarantees the following mesh generation requirements:

1. Stability: the quality of the mesh generated in parallel must be comparable to that of a mesh generated sequentially. The quality is defined in terms of the shape of the elements (using a chosen space-dependent metric), and the number of the elements (fewer is better for the same shape constraint).
2. Robustness: the ability of the software to correctly and efficiently process any input data. Operator intervention into a massively parallel computation is not only highly expensive, but most likely infeasible due to the large number of concurrently processed sub-problems.
3. Code re-use: a modular design of the parallel software that builds upon a previously designed sequential meshing code, such that it can be replaced and/or updated with a minimal effort. Due to the complexity of meshing codes, this is the only practical approach for keeping up with the ever-evolving sequential algorithms.
4. Scalability: the ratio of the time taken by the best sequential implementation to the time taken by the parallel implementation. The speedup is always limited by the inverse of the sequential fraction of the software, and therefore all non-trivial stages of the computation must be parallelized to leverage the current architectures with millions of cores.

The design and implementation of a sequential industrial strength code is labor intensive, it takes about 100 man-years. Parallel mesh generation code is even more labor intensive (by an order of magnitude for traditional parallel machines and expected to be higher for current and emerging architectures due to multiple memory and network hierarchies, fault-tolerance and power aware issues); however, because of the underlying theory that allows code re-use, this initial parallel implementation was achieved in less than six months with impressive functionality, i.e., the same as the sequential TetGen code.

The general idea of Delaunay refinement is based on the insertion of additional (Steiner) points inside the circumdisks of poor quality elements, which causes these elements to be destroyed, until they are gradually eliminated and replaced by better quality elements. It has been proven that this algorithm terminates by producing a mesh with guaranteed bounds on radius-edge ratio and on the density of elements. The main concern when parallelizing Delaunay refinement algorithms is the compatibility (i.e., data dependence) between Steiner points concurrently inserted by multiple threads or processes. Two points are Delaunay-independent if they can be safely inserted concurrently. PDR is based on overlapping the mesh with an octree, defining buffer zones around each leaf of the octree, and proving that points inserted outside the buffer zone of a leaf are always Delaunay-independent with respect to any points inserted inside this leaf.

There are two approaches to PDR, progressive and non-progressive, both of which rely on octree (data) decomposition in order to mathematically guarantee element quality and termination of the PDR algorithm for uniform isotropic Delaunay-based methods.

Compiling PDR (Shared Memory Release)

The PDR source code is provided as a compressed tar archive, which is available here. It can be extracted using the tar utility.

tar xvzf PDR-buildnumber.tar.gz

After extracting PDR, cd into the PDR directory. To perform an out-of-source-build, create a compilation directory.

mkdir build

cd build

Run cmake followed by make.

cmake ..

make

Two executables will be created:

• pdr: non-progressive pdr
• pdr_p: progressive pdr

Tool Configuration on Linux

PDR requires g++ 4.7 or higher and cmake. Both utilties, can be installed with the package manger for your Linux distribution (e.g., apt-get for Ubuntu and yum on CentOS).

Compilation has been performed and tested on CentOS with g++ version 4.9, Ubuntu with g++ versions 4.8.4, 4.9, and 5.3.1.

Tool Configuration on OSX

PDR requires g++ 4.7 or higher and cmake. CMake configuraiton and installation official instructions are provided by Kitware. If the CMake GUI is already installed in the /Applications directory, the command line tool can be activated by running

sudo "/Applications/CMake.app/Contents/bin/cmake-gui" --install

The gcc compiler included with xcode is an earlier version. The gcc47 package can be installed using the macports framework.

Compiling PDR (Initial MPI Release)

The PDR source code is provided as a compressed tar archive, which is available here. It can be extracted using the tar utility.

tar xvzf PDR-buildnumber.tar.gz

After extracting PDR, cd into the PDR directory. To perform an out-of-source-build, create a compilation directory.

mkdir build

cd build

Run cmake followed by make.

cmake ..

make

One executable will be created:

• pdr: non-progressive pdr

Tool Configuration on Linux

Compilation requires cmake and version 4.9.3 of the g++ compiler and openmpi 2.0.1 or higher.