Parallel mesh generation: Difference between revisions

Revision as of 19:04, 21 July 2008

Latest revision as of 13:30, 27 March 2025

(30 intermediate revisions by 22 users not shown)

Line 1:

'''Parallel mesh generation''' in [[numerical analysis]] is a new research area between the boundaries of two [[scientific computing]] disciplines: [[computational geometry]] and [[parallel computing]].<ref name="Chrisochoides">Nikos Chrisochoides, Parallel Mesh Generation, Chapter in ''Numerical Solution of Partial Differential Equations on Parallel Computers'', (Eds. Are Magnus Bruaset, Aslak Tveito), Springer-Verlag, pp 237-259, 2005.</ref>. 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: (1) the sequential technique used for meshing the individual subproblems and (2) 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.

{{Wikify|date=September 2007}}

#the sequential technique used for meshing the individual subproblems and

'''Parallel mesh generation''' in [[numerical analysis]] is a new research area between the boundaries of two [[scientific computing]] disciplines: [[computational geometry]] and [[parallel computing]]<ref name="Chrisochoides">Nikos Chrisochoides, Parallel Mesh Generation, Chapter in Numerical Solution of Partial Differential Equations on Parallel Computers, (Eds. Are Magnus Bruaset, Aslak Tveito), Springer-Verlag, pp 237-259, 2005.</ref>. 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: (1) the sequential technique used for meshing the individual subproblems and (2) 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.

#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.<ref name="Chrisochoides"/>. The subproblems can be formulated to be either tightly coupled,<ref>Nikos Chrisochoides and Demian Nave. Parallel [[Delaunay]] mesh generation kernel. Int. J. Numer. Meth. Engng., 58:161--176, 2003</ref><ref>Lohner, J.Camberos, and M.Marshal. Parallel Unstructured Grid

Generation. Chapter in ''Unstructured Scientific Computation on Scalable Multiprocessors''. (Eds. Piyush Mehrotra and Joel Saltz), pp 31--64, MIT Press, 1990.</ref>, partially coupled<ref name="ReferenceA">H. de Cougny and M.Shephard. Parallel volume meshing using face removals and hierarchical repartitioning. Comp. Meth. Appl. Mech. Engng.,

174(3-4):275--298, 1999.</ref><ref>Andrey Chernikov and Nikos Chrisochoides. Parallel Guaranteed Quality Planar Delaunay Mesh Refinement Concurrent Point Insertion. ''SIAM Journal for Scientific Computing'', Vol. 28, No. 5, pp 1907-1926, 2006.</ref> or even decoupled.<ref>J. Galtier and P. L. George. Prepartitioning as a way to mesh subdomains in parallel. Special Symposium on Trends in Unstructured Mesh Generation, pp 107--122. ASME/ASCE/SES, 1997.</ref><ref>Leonidas Linardakis and Nikos Chrisochoides. Delaunay Decoupling Method for Parallel Guaranteed Quality Planar Mesh Generation. ''SIAM Journal for Scientific Computing'', Vol. 27, No. 4, pp 1394-1423, 2006.</ref> The coupling of the subproblems determines the intensity of the communication and the amount/type of synchronization required between the subproblems.

subdomains in parallel. Special Symposium on Trends in Unstructured Mesh Generation, pp 107--122. ASME/ASCE/SES, 1997.</ref><ref>Leonidas Linardakis and Nikos Chrisochoides. Delaunay Decoupling Method for Parallel Guaranteed Quality Planar Mesh Generation. SIAM Journal for Scientific Computing, Vol. 27, No. 4, pp 1394-1423, 2006.</ref>. 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 triangulationstriangulation]]s appears in Blelloch et al.<ref>G. E. Blelloch, J.C. Hardwick, G.~L. Miller, and D. Talmor, Design and implementation of a practical parallel Delaunay algorithm, Algorithmica, 24 (1999), pp. 243--269.</ref>. This algorithm is extended in Clemens and Walkington<ref>Clemens Kadow and Noel Walkington. Design of a projection-based parallel Delaunay mesh generation and refinement algorithm. In proceedings of Fourth Symposium on Trends in Unstructured Mesh Generation, 2003.</ref> for parallel mesh generation.

==Parallel mesh generation software==

<!-- Deleted image removed: [[Image:partgen_jpegpartgen jpeg.jpg|right|350px|]] -->

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 <ref>Fraunhofer!-- InstituteDeleted forimage Industrial Mathematics, httpremoved://www.itwm.fhg.de</ref>. '''parTgen'''<ref>parTgen - partitioner and parallel tetrahedral mesh generator, http[[Image://www.itwm.fhg.de/en/hpc__partgen/partgen/</ref> - partitioner and parallel tetrahedral mesh generator is an example of decoupled method developed and implemented by Evgeny Ivanov etBearcap alpng.<ref>E.G. Ivanov, H. Andrae and A.N. Kudryavtsev, Domain png|left|250px|Decomposition Approach for Automatic Parallel Generation of Tetrahedralbearing Grids,cap Internationaland Mathematicaltetrahedral Journalmesh Computationalgeneration Methodson in32 AppliedCPUs]] Mathematics, Vol.6(2), 2006, pp. 178--193. </ref> <ref>H. Andrae, E. Ivanov, O. Gluchshenko, A. Kudryavtsev, Automatic Parallel Generation of Tetrahedral Grids by Using a Domain Decomposition Approach, Journal of Computational Mathematics and Mathematical Physics, Vol. 48(8), 2008, pp. 1448-1457 </ref>

<!-- Deleted image removed: [[Image:kneefem_pngkneefem png.png|250px|Decomposition of femoral prosthesis component and tetrahedral mesh generation on 16 CPUs]] -->

<!-- Deleted image removed: [[Image:kneetib_pngkneetib png.png|250px|Decomposition of tibial prosthesis component and tetrahedral mesh generation on 8 CPUs]] -->

A parallel version of the MeshSim mesh generator by Simmetrix Inc.,<ref>{{Cite web |url=http://www.simmetrix.com/products/SimulationModelingSuite/ParallelMeshSim/ParallelMeshSim.html |title=Parallel MeshSim |access-date=2009-08-05 |archive-date=2009-02-18 |archive-url=https://web.archive.org/web/20090218151631/http://simmetrix.com/products/SimulationModelingSuite/ParallelMeshSim/ParallelMeshSim.html |url-status=dead }}</ref> 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<ref name="ReferenceA"/> 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<ref>{{Cite web |url=http://www.simmetrix.com/products/SimulationModelingSuite/MeshSim/MeshSim.html |title=MeshSim |access-date=2009-08-05 |archive-date=2009-09-27 |archive-url=https://web.archive.org/web/20090927170512/http://www.simmetrix.com/products/SimulationModelingSuite/MeshSim/MeshSim.html |url-status=dead }}</ref>

[[Image:Bearcap_png.png|left|250px|Decomposition of bearing cap and tetrahedral mesh generation on 32 CPUs]]

[[Image:kneefem_png.png|250px|Decomposition of femoral prosthesis component and tetrahedral mesh generation on 16 CPUs]]

[[Image:kneetib_png.png|250px|Decomposition of tibial prosthesis component and tetrahedral mesh generation on 8 CPUs]]

Another parallel mesh generator is '''D3D''' ,<ref>D3D Mesh Generator Web page, [http://mech.fsv.cvut.cz/~dr/d3d.html D3D Mesh Generator Web page]</ref> was developed by Daniel Rypl<ref>University Web page of Daniel Rypl, http://mech.fsv.cvut.cz/~dr/</ref> at [[Czech Technical University in Prague]]. '''D3D''' is a mesh generator capable to discretize in parallel (or sequentially) 3D domains into mixed meshes.

----

Another parallel mesh generator is '''D3D''' <ref>D3D Mesh Generator Web page, http://mech.fsv.cvut.cz/~dr/d3d.html</ref> was developed by Daniel Rypl<ref>University Web page of Daniel Rypl, http://mech.fsv.cvut.cz/~dr/</ref> at Czech Technical University in Prague. '''D3D''' is a mesh generator capable to discretize in parallel (or sequentially) 3D domains into mixed meshes.

BOXERMesh<ref>[http://www.cambridgeflowsolutions.com/en/products/boxer-mesh.html BOXERMesh]</ref> is an unstructured hybrid mesh generator<ref>[http://www.cambridgeflowsolutions.com/uploads/2009_Scalable%20parallel%20mesh%20generation_AIAA_0981.pdf Scalable Parallel Mesh Generation]</ref> developed by Cambridge Flow Solutions.<ref>[http://www.cambridgeflowsolutions.com Cambridge Flow Solutions]</ref> Implemented as distributed-memory fully parallelised software, it is specifically designed to overcome the traditional bottlenecks constraining engineering simulation, delivering advanced meshing on geometries of arbitrary complexity and size. Its scalability has been demonstrated on very large meshes generated on HPC clusters.

==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 open

ended and permanent which makes the task of delivering state-of-the-art parallel mesh generation codes even more diffcult.

== Challenges in parallel mesh generation ==

An area with immediate high benefits to parallel mesh generation is ___domain decomposition. The DD problem as it is posed in <ref>Chrisochoides N., A Survey of Parallel Mesh Generation Methods, Brown University, Providence RI - 2005.</ref>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.

It takes aboutsubstantial ten to fifteen yearstime to develop the algorithmic and software infrastructure for commercial sequential industrial strength mesh generation libraries. Moreover, improvements in terms of quality, speed, and functionality are open

ended and permanent which makes the task of deliveringcreating state-of-the-artleading edge parallel mesh generation codes even more diffcultchallenging.

An area with immediate high benefits to parallel mesh generation is ___domain decomposition. The DD problem as it is posed in <ref>Chrisochoides N., ''A Survey of Parallel Mesh Generation Methods'', Brown University, Providence RI - 2005.</ref> 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.

==References See also ==

*[[Mesh generation]]

<references/>

*[[Parallel computing]]

== References ==

[[Category:Numerical differential equations]]

{{reflist}}

{{Mesh generation|state=autocollapse}}

[[Category:Mesh generation]]

[[Category:Parallel computing]]