Parallel mesh generation
Encyclopedia
Parallel mesh generation in numerical analysis
is a new research area between the boundaries of two scientific computing disciplines: computational geometry
and parallel computing
. Parallel mesh generation methods decompose the original mesh generation
problem into smaller subproblems which are solved (meshed) in parallel using multiple processors or threads. The existing parallel mesh generation methods can be classified in terms of two basic attributes:
One of the challenges in parallel mesh generation is to develop parallel meshing software using off-the-shelf sequential meshing codes.
The challenges in parallel mesh generation methods are: to maintain stability of the parallel mesher (i.e., retain the quality of finite elements generated by state-of-the-art sequential codes) and at the same time achieve 100% code re-use (i.e., leverage the continuously evolving and fully functional off-the-shelf sequential meshers) without substantial deterioration of the scalability of the parallel mesher.
There is a difference between parallel mesh generation and parallel triangulation. In parallel triangulation a pre-defined set of points is used to generate in parallel triangles that cover the convex hull of the set of points. A very efficient algorithm for parallel Delaunay triangulations appears in Blelloch et al.. This algorithm is extended in Clemens and Walkington for parallel mesh generation.
A parallel version of the MeshSim mesh generator by Simmetrix Inc., is available for both research and commercial use. It includes parallel implementations of surface, volume and boundary layer mesh generation as well as parallel mesh adaptivity. The algorithms it uses are based on those in reference and are scalable (both in the parallel sense and in the sense that they give speedup compared to the serial implementation) and stable. For multicore or multiprocessor systems, there is also a multithreaded version of these algorithms that are available in the base MeshSim product
Another parallel mesh generator is D3D, was developed by Daniel Rypl at Czech Technical University in Prague. D3D is a mesh generator capable to discretize in parallel (or sequentially) 3D domains into mixed meshes.
ended and permanent which makes the task of delivering state-of-the-art parallel mesh generation codes even more difficult.
An area with immediate high benefits to parallel mesh generation is domain decomposition. The DD problem as it is posed in is still open for 3D geometries and its solution will help to deliver stable and scalable methods that rely on off-the-shelf mesh generation codes for Delaunay and Advancing Front Techniques.
Finally, a long term investment to parallel mesh generation is to attract the attention of mathematicians with open problems in mesh generation and broader impact in mathematics.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
is a new research area between the boundaries of two scientific computing disciplines: computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
and parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
. Parallel mesh generation methods decompose the original mesh generation
Mesh generation
Mesh generation is the practice of generating a polygonal or polyhedral mesh that approximates a geometric domain. The term "grid generation" is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as finite element analysis or...
problem into smaller subproblems which are solved (meshed) in parallel using multiple processors or threads. The existing parallel mesh generation methods can be classified in terms of two basic attributes:
- the sequential technique used for meshing the individual subproblems and
- the degree of coupling between the subproblems.
One of the challenges in parallel mesh generation is to develop parallel meshing software using off-the-shelf sequential meshing codes.
Overview
Parallel mesh generation procedures in general decompose the original 2-dimensional (2D) or 3-dimensional (3D) mesh generation problem into N smaller subproblems which are solved (i.e., meshed) concurrently using P processors or threads. The subproblems can be formulated to be either tightly coupled, partially coupled or even decoupled. The coupling of the subproblems determines the intensity of the communication and the amount/type of synchronization required between the subproblems.The challenges in parallel mesh generation methods are: to maintain stability of the parallel mesher (i.e., retain the quality of finite elements generated by state-of-the-art sequential codes) and at the same time achieve 100% code re-use (i.e., leverage the continuously evolving and fully functional off-the-shelf sequential meshers) without substantial deterioration of the scalability of the parallel mesher.
There is a difference between parallel mesh generation and parallel triangulation. In parallel triangulation a pre-defined set of points is used to generate in parallel triangles that cover the convex hull of the set of points. A very efficient algorithm for parallel Delaunay triangulations appears in Blelloch et al.. This algorithm is extended in Clemens and Walkington for parallel mesh generation.
Parallel mesh generation software
While many solvers have been ported to parallel machines, grid generators have left behind. Still the preprocessing step of mesh generation remains a sequential bottleneck in the simulation cycle. That is why the need for developing of stable 3D parallel grid generator is well-justified. Work in this direction is carried out by several institutions. Fraunhofer Institute for Industrial Mathematics parTgen - partitioner and parallel tetrahedral mesh generator - partitioner and parallel tetrahedral mesh generator is an example of decoupled method developed and implemented by Evgeny Ivanov et al.A parallel version of the MeshSim mesh generator by Simmetrix Inc., is available for both research and commercial use. It includes parallel implementations of surface, volume and boundary layer mesh generation as well as parallel mesh adaptivity. The algorithms it uses are based on those in reference and are scalable (both in the parallel sense and in the sense that they give speedup compared to the serial implementation) and stable. For multicore or multiprocessor systems, there is also a multithreaded version of these algorithms that are available in the base MeshSim product
Another parallel mesh generator is D3D, was developed by Daniel Rypl at Czech Technical University in Prague. D3D is a mesh generator capable to discretize in parallel (or sequentially) 3D domains into mixed meshes.
Challenges in parallel mesh generation
It takes about ten to fifteen years to develop the algorithmic and software infrastructure for sequential industrial strength mesh generation libraries. Moreover, improvements in terms of quality, speed, and functionality are openended and permanent which makes the task of delivering state-of-the-art parallel mesh generation codes even more difficult.
An area with immediate high benefits to parallel mesh generation is domain decomposition. The DD problem as it is posed in is still open for 3D geometries and its solution will help to deliver stable and scalable methods that rely on off-the-shelf mesh generation codes for Delaunay and Advancing Front Techniques.
Finally, a long term investment to parallel mesh generation is to attract the attention of mathematicians with open problems in mesh generation and broader impact in mathematics.