Internal:IMR 2018 Short Course

Notes

Parallel Optimization of Tetrahedral Meshes, D. Benítez1, E. Rodríguez, J.M. Escobar, R. Montenegro

6th European Conference on Computational Mechanics (ECCM 6) & 7th European Con-ference on Computational Fluid Dynamics (ECFD 7), 2018 [1]

Summary

A new algorithm on distributed-memory parallel computers for our simultaneous untangling and smoothing of tetrahedral meshes .

Overview

The method is based on

• partitioning a mesh
• optimizing interior vertices
• optimizing boundary vertices of interior partitions, and
• communicating updated coordinates of boundary vertices.

In each mesh sweep, the interior vertices of all partitions are optimized in parallel. For partition boundaries, independent sets of non-fixed vertices are created; each of them is optimized in parallel after all interior vertices have been optimized

Distributed Combinatorial Maps for Parallel Mesh Processing, Guillaume Damiand, Aldo Gonzalez-Lorenzo, Florence Zara and Florent Dupont

Algorithms 2018, 11(7), 105; doi:10.3390/a11070105 [2]

Summary

"Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to
represent the topology of big meshes by splitting them into independent parts. "

"To sum up, this topological representation can be used to describe an nD mesh, while providing
high level operations to iterate through the cells of the mesh, retrieve the incidence and adjacency
relations between the cells, and modify the mesh by using the numerous existing operations. "

Code is part of CGAL

https://doc.cgal.org/latest/Combinatorial_map/index.html#Chapter_Combinatorial_Maps

Application

Adaptive Hexahedral Subdivision (ie octree refinement)

• MPI-based
• Uses a single template (1:8) for splitting the octree
• Shared faces and edges between processes are split independently and asyncronous messages are used to achieve conformity. ( Like PCDM 2D)

Performance Data

Speedup 6.3 on 32 cores

Parallel anisotropic 3D mesh adaptation by mesh modification, Frédéric Alauzet & Xiangrong Li & E. Seegyoung Seol & Mark S. Shephard

Engineering with Computers (2006) 21: 247–258, DOI 10.1007/s00366-005-0009-3 [3]

Algorithm

1. Mesh coarsening to eliminate the initial short edges
2. Intelligent mesh refinement that includes operations
   for ensuring the proper geometric approximation of
   the mesh to the geometric domain and proper shape
   to match the metric field, and
3. Mesh optimization to improve the quality of the
   final mesh

" The Flexible distributed Mesh DataBase (FMDB) has been used to support the needed mesh-based parallel
operations on distributed meshes including communications between mesh partitions, migrating mesh entities between the partitions and the dynamic mesh load balancing. "

"The mesh load balancing is also critical for the parallel procedure to achieve desirable performance. The Zoltan library is used to make partition assignment during the dynamic load balancing."

Coarsening

Mesh migration-based parallelization is used:

"More precisely, whenever a mesh modification operation on partition boundaries is desired, we migrate the mesh entities within the polyhedron associated with (i.e., the mesh regions affected by) the operation into one partition and since then we apply the operation as in serial."

The above step is repeated until all coarsening operations are applied.

Process id-based scheme is use to resolve conflicting requests.

Mesh Refinement

"Mesh refinement relies on tagging mesh edges and
applying edge, face and region subdivision templates,
which changes mesh topology but not geometry. "

Steps

1. "Marked mesh edges and their neighboring mesh
   faces on partition boundaries are subdivided using the
   four templates."
2. Boundary Modifications Synchronization
3. Refinement of volume with no communication

Parallel Vertex Snapping (on curved boundary)

Use direct snapping or collapse operations , if vertex is on partition boundary communicate to ensure validity and/or collect cavity.

Load Balancing

Using Zoltan redistribute the global distributed mesh in (FMDB)

Performance

No time/speedup data are available besides a phrase "In the example, the speedup of the parallel procedure is between 1.2 and 2" pg 255

A parallel advancing front grid generation scheme, Rainald Löhner

Int. J. Numer. Meth. Engng. 2001 [4]

Summary

A parallel advancing front scheme has been developed. The domain to be gridded is first subdivided spatially using a relatively coarse octree.

Boxes are then identified and gridded in parallel. A scheme that resembles closely the advancing front technique on scalar machines is recovered by only considering
the boxes of the active front that generate small elements.

Grid generation

The algorithm uses many passes.

In each pass the faces of the front are divided using an octree. From faces in "far enough " octree leaves points are advanced simutaneusly

only the boxes covering the active front in regions where the smallest
new elements are being introduced are considered.

Shared Faces between leaves are eliminated shifting the octree leaves and remeshing the front.

Work balancing is achieved using overdecomposition of the octree.

Mesh Improvement

Swapping

Checks are done in parallel , actual flipping sequentially

Removal of bad elements (Edge Contraction)

Indentify edges around bad elements in parallel , contract them either by collapsing an endpoint onto the other or both onto a new point in the middle.

Laplacian Smoothing

Color edges/elements into independent sets and run in parallel. When negative volume elements are created, remove them together with adjacent elements and remesh the hole.

For surface meshing (preprocessing) each surface patch is meshed in parallel.

Results

Shared memory.

Performance more than 50% efficiency in 16 cores

Unique cavity-based operator and hierarchical domain partitioning for fast parallel generation of anisotropic meshes, Loseille A. & Alauzet F & Menier V.

Computer-Aided Design 2017, [5]

Abstract

"Our strategy is based on typical domain splitting algorithm where the initial mesh is split in parts that are then meshed in parallel while the fictitious boundaries between parts are kept unchanged. Then we iterate the procedure to adapt previously unmodified parts of the domain, i.e., the interface mesh. Both the volume and the surface meshes are adapted simultaneously and the efficiency of the method is independent of the complexity of the geometry.

The originality of the method relies on

1. metric-based static load-balancing,
2. hierarchical mesh partitioning techniques to (re)split the (complex) interfaces meshes,
3. a fast, robust and generic sequential cavity-based mesh modification kernel.

In this paper, we follow the coarse-grained parallelization in an adaptive context within the metric-based framework."

Sequential Mesh Generation (essentially is a AF-based method)

Loop the steps :

1. Creation of unit mesh in metric space:
   1. Collapse small edges
   2. Point Creation
   3. Anisotropic Filtering
   4. Point Insertion
2. Mesh Optimization
   1. Edge/face flips using the cavity operator
      
      
3. Surface Approximation base on surrogate geometry ( it is not clear is this is on every loop or at the end)

Hierarchical Partitioning

To enable coarse-grain parallelism a hierarchical partitioning scheme is used.

"At the first level, the initial domain is split and considered for adaptation. From the set of constrained faces (at interface) of the previous level, a new volume mesh (domain) is deduced for the next level. This new domain is then split and adapted in parallel. This process is then applied until convergence."

The new volume is is evaluated using interface meshes (i.e. union of cavities of interface elements )

Domain Decomposition

At each step of the hierarchical partitioning domain decomposition is used to partition the current mesh.

How load is evaluated

"To handle non uniform refinements (in term of sizes and directions), a metric-based static load balancing formula is used to a priori equilibrate the work on each sub-domain."

The unique cavity framework offers constant speed whatever the considered operator.

"This feature allows us to derive an accurate metric-based work that is easily deduced from the input metric-field and input mesh only."

Mesh Partitioning

First Hilbert ordering of vertices is used.

Then BFS with restart and the work load as weight is used to partition the elements.

Load Balancing

Static since previous steps tried to make partition as well balanced as possible.

Performance Data

Start-to-End : speed-up of 20-33 on 120 cores