Internal:PDR AFLR Progress Report

Two implementations were created for PDR.AFLR. They both use similar methodologies but differ in that one focuses on the refinement of individual octree leaves (subdomains) while the other focuses on super leaf refinement (region of leaves). The former implementation is complete and the latter is still under development. The reason for having two implementations is explained further below.

Individual Leaf Refinement (ILR) Implementation

The following steps outline the general process of the data-decomposed AFLR, or the individual leaf refinement (ILR) implementation:

1. Accept an input geometry.

2. Generate an initial volume mesh.

3. Construct an octree.

4. Assign subdomains to octree leaves and insert leaves into refinement queue.

5. Remove a leaf from the queue. Create a temporary boundary for the leaf based on original element connectivity with neighboring subdomains.

6. Call AFLR to refine the leaf.

7. Merge all neighboring leaves, located within the buffer zone, with the newly refined leaf.

8. Call AFLR to perform local reconnection on the merged data.

9. Assign updated data to the necessary leaves.

10. Repeat steps 5-9 until there are no remaining leaves in the refinement queue.

11. Merge all data and call AFLR to perform final optimization.

12. Output the final mesh.

Figure 1 shows a 2-D example of PDR’s data decomposition and the assignment of data generated from the upper portion of a rocket geometry. Mathematical formulas are given for the different levels of neighboring leaves around the primary leaf under refinement (in red). The level 1 neighbors of a leaf are considered to be the buffer zone of that leaf (no leaf in the buffer zone may undergo refinement while the primary leaf undergoes refinement).

Figure 1. Shown is a 2-D example of the upper portion of a data-decomposed rocket mesh where the red-boxed leaf is the primary leaf under refinement. The level 1 neighbors are those inside the yellow box (excluding the red leaf) and the level 2 neighbors are those inside the orange box (excluding all leaves inside the yellow box). The formulas give mathematical representations that denote the tetrahedra within leaves and the sets of neighboring leaves (with matching colors showing what is contained within each surface).

One of the implementation challenges, caused by data decomposition, is allowing subdomain boundary elements to undergo refinement. If a boundary face, shared by two leaves, undergoes refinement, then the corresponding elements within both leaves must be updated (which adds dependencies and increases overall runtime due to the required communication between the corresponding processes). Otherwise, the connectivity between the subdomains will be incorrect and the final mesh will be non-conforming. Subdomain boundary refinement is preferred so that boundary elements do not retain poor quality by the end of refinement. To address this issue, AFLR was modified to not only accept a single set of data (points, triangles, and tetrahedra) for one leaf, but to also accept a second set of data – the set of all of its level 1 neighboring leaves. The faces of the primary leaf’s internal interface surface are kept frozen in step 6, meaning that point insertion is not allowed on the leaf boundary. AFLR refines the individual leaf (advancing front point placement/insertion and local reconnection) but does not make any optimizations/quality improvement as the serial AFLR would. Instead, the newly refined leaf is merged with its level 1 neighbors into a super-subdomain and local reconnection is performed over the super-subdomain (thereby allowing the optimization of the primary leaf’s boundary elements). The internal interface surface of the level 1 neighbor leaves remains frozen, so as to eliminate the need of updating level 2 neighbors during refinement (and maintaining PDR’s original method of concurrency). It is possible to have duplicate points when combining these sets of data because a neighboring leaf may contain a tetrahedron that has a point located in the primary leaf, or vice-versa. Each set of data will contain that same point, so the duplicate point is removed and any tetrahedron or triangle that references this point is updated to use the same index (all tetrahedra and faces use integer-based indices to denote which points they contain). The removal of duplicate points is necessary as they are not permitted by AFLR.

Issues were also encountered regarding the initial volume mesh. The data-decomposed AFLR requires an initial mesh that is dense enough to satisfy the boundary requirements of individual octree leaves for refinement. For example, the mesh cannot contain a tetrahedron that is so large that is spans multiple leaves (across numerous levels). There would be no possible boundary extraction for each individual leaf. For manifold, genus zero geometries (current focus as more advanced geometries will be utilized in the future as the robustness of the software is expanded), AFLR requires smooth, simply connected boundaries. The initial mesh generated by AFLR sometimes may contain a very large tetrahedron. An example of this is shown in figure 2. This scenario does not always occur but is possible. In order to avoid this problem, the octree level may be reduced (fewer leaves) but this will reduce end concurrency. Another solution is to further refine the initial mesh, but this is also a problem. If the initial mesh undergoes too much refinement, then more runtime will be spent at this stage rather than in parallel refinement (sometimes taking hours for larger geometries) and rendering the parallel refinement futile.

Figure 2. Octree leaf with volume, generated by AFLR, with tetrahedra spanning across numerous leaves. The left shows the lone volume while the right shows the volume inside the octree.

TetGen is temporarily being used to generate the initial mesh due to its quick runtime and because a volume constraint can be set directly (AFLR cannot read TetGen output files, so a script was written to convert TetGen file types into AFLR ugrid file types). AFLR contains parameters that affect initial mesh generation, such as seed point placement and point spacing. These options will be further explored to allow PDR.AFLR to maintain as much internal functionality as possible and to limit outside library dependencies.

Scalability Results

Scalability was achieved by fully integrating the data-decomposed AFLR onto a runtime system called PREMA 2.0. During run time, the PDR.AFLR method exposes data decomposition information (number of subdomains waiting to be refined) to the underlying run-time system. In turn, this system facilitates work-load balancing and guides the program’s execution towards the most efficient utilization of hardware resources. PREMA 2.0 is a parallel runtime system that supports asynchronous communication, global address space and load balancing for adaptive and irregular applications. The following table and figures show preliminary scalability results of the pseudo-constrained PDR.AFLR (the parallel data refinement methodology is considered to be constrained in this implementation due to the fact that it relies on a surface triangulation, in addition to the volume data, for refinement due to the nature and requirements of AFLR).

Serial AFLR data is in red.

Weak scalability was tested by starting with a number of surface elements and increasing them by approximately 1.5 for each increase in core count. This was also applied to the density of the initial volume mesh generated from TetGen in order to ensure that the octree leaves would contain approximately the same number of elements; and moreover, that the cores would each maintain the same amount of work as the meshes increased in size in conjunction with the increase in the number of cores. Good weak scalability is observed going up to 16 cores.

Stability (Dihedral Angle Quality) Results

Below are some stability statistics of the final three meshes – 343k surface elements, 518k, and 776k.

Overall, the quality of the meshes generated by the ILR PDR.AFLR are not as good as that of the meshes generated by serial AFLR. We believe that this is due to the fact that internal interface boundary elements do not undergo point insertion during refinement. These elements only undergo local reconnection, which is not enough to guarantee sufficient quality for the final mesh. The original steps of the data-decomposed AFLR have been modified to solve this issue, which can be seen in the super leaf refinement implementation.

Individual Leaf Refinement (ILR) Implementation Update

While the SLR implementation is still a viable solution that we believe will further increase stability, the ILR implementation has been updated to improve its stability. There are numerous AFLR parameters used to control the point spacing of the volume generated by AFLR. This affects the number of elements that are created, and in turn the density of the final mesh. Previously, the output volume mesh would contain elements that typically had larger faces than the external surface elements. Since PDR.AFLR uses tetrahedra to extract subdomain boundaries, the point spacing used by AFLR would be that of the tetrahedra point spacing (which is larger than the external surface point spacing), so the subdomain would not be refined to a higher density. It would maintain the same level of coarseness. This is because the initial mesh would be a coarse mesh generated by TetGen. I have found that if the mesh is refined to be denser, it will have better dihedral angle quality. If the point spacing for each subdomain is closer to that of the external surface (rather than that of the volume points from the TetGen mesh), more elements will be created within that domain (despite its boundary faces remaining frozen) and the final mesh will have an overall greater density/quality.

A list of AFLR parameters that affect the point spacing can be seen at AFLR Point Spacing/Distribution Function Parameters.

The ones that yield the best results without causing AFLR runtime errors are:

mdf = 1

cdfs = 0

cdfr = 1

Using this combination of parameters for each octree leaf refinement, the following quality results were achieved.

It should be noted that using the combination of dfmax = 0.1 and cdf = 3, even better quality results are achieved for the 343k cube mesh which can be seen below. Unfortunately, the runtime (1133 sec) becomes much longer than the serial runtime (444 sec) and many more volume elements are generated (7 million compared to PDR.AFLR's previous 900k and serial ALFR's 15 million). If this is tested with larger meshes, I believe that PDR.AFLR with some configuration of these parameters will outperform serial AFLR. The problem is that 0.1 is a specific value that I tested for dfmax. I do not currently know what might be more suitable for this particular mesh. These parameters with these settings cause numerous AFLR errors for the other two meshes that I've tested. I need to see if there is a way to determine a value for dfmax based on the input mesh that won't cause errors.

Further Parameter Update

Setting only dfmax to a value of 0.1 yields the following dihedral angle distribution results:

Super Leaf Refinement (SLR) Implementation

Instead of refining individual leaves, a leaf and its level 1 neighbors are merged into a super leaf which undergoes both point insertion and local reconnection so that the internal interface boundary elements undergo full refinement.

1. Accept an input geometry.

2. Generate an initial volume mesh.

3. Construct an octree.

4. Assign subdomains to octree leaves and insert leaves into refinement queue.

5. Remove a leaf from the queue. Merge all neighboring leaves, located within the buffer zone, with the leaf to form a super leaf.

6. Create a temporary boundary for the super leaf based on original element connectivity with neighboring subdomains (level 2 neighbors of leaf).

7. Call AFLR to refine the super leaf.

8. Assign updated data to the necessary leaves.

9. Repeat steps 5-8 until there are no remaining leaves in the refinement queue.

10. Merge all data and call AFLR to perform final optimization.

11. Output the final mesh.

The ILR implementation has been modified to accommodate these changes, but is still currently undergoing development and debugging. The duplicate point issue has arisen again and the root of its cause has yet to be determined. Scalability and quality results of this updated methodology will be attained soon.

Remaining Issues to be Addressed

- Duplicate Point Bug in Super Leaf Refinement Implementation

- Initialization: initial mesh generation that preferably needs to be handled by AFLR to reduce runtime and outside library dependencies

- The initial mesh must meet the proper density requirement (to ensure software concurrency) and must have an appropriate generation time.

- Parallelization of End Optimization for whole mesh

- To implement the true PDR.AFLR (not pseudo-constrained), AFLR must be modified to refine a volume without a specified surface triangulation.