Efficient Parallel Extraction of Crack-free Isosurfaces from Adaptive Mesh Refinement Data

Problem Statement and Goals

There are many forms of physical phenomena, like star formation, that occupy vast regions of space. These areas have extreme variances in spatiotemporal scales, i.e., some areas are fairly homogeneous while other areas may change rapidly. To represent these domains efficiently, simulations must vary the resolutions to adapt to local features. The block-structured adaptive mesh refinement (AMR) approach addresses this challenge by creating a hierarchy of axis-aligned rectilinear grids, which are commonly referred to as boxes. This representation requires less storage overhead than unstructured grids—it is only necessary to store the layout of all grids with respect to each other since connectivity within each rectilinear grid is implicit—and makes it possible to represent different parts of the domain at varying resolutions. Due to its effectiveness, an increasing number of application domains use this simulation technique. The hierarchical representation of AMR data makes data analysis particularly challenging. It is necessary to take into account that a finer box may invalidate and replace the value of a given grid cell. A greater challenge is in handling transitions between hierarchy levels such that no discontinuities appear at the boundaries between refinement levels. Like in many hierarchical data representations, cracks in an extracted isosurface arise due to T-junctions between levels. These cracks distract from a visualization's exploration- or communication-oriented objective and introduce questions of correctness. Furthermore, they affect the accuracy of quantities—such as surface area—derived from an isosurface. Our goal was to design an algorithm for crack-free isosurface extraction that works in a distributed-memory setting. We view the ability to run analysis on the system that generates the data as a key requirement. Although some sufficiently high-memory systems do exist to handle large data sets, the transfer time from the distributed-memory supercomputer to this remote shared-memory system is generally prohibitive.

Implementation and Results

Our new approach [1] extends from prior work using dual grids and stitch cells to define continuous interpolation and isosurface extraction simplifying its implementation by using a case table. The main design goals for improving this approach were: (i) enabling data parallel stitch cell generation and isosurface extraction that operate on individual AMR boxes separately, and (ii) maintaining a rectilinear grid representation as long as possible.

Figure 1: Extraction of crack-free isosurfaces from a 2D AMR data set. (Left) Extracting contours using the standard marching cubes approach after re-sampling cell centered AMR data to grid vertices (grid shown as light gray lines). The resulting contours show clear discontinuities at the boundaries between levels. (Right) Using original simulation data by using the dual grid connecting cell centers and filling resulting gaps between levels with procedurally generated stitch cells yields contours continuous at level boundaries.

Like in the previous approach, we use dual grids---connecting the cell centered values produced by the simulation---and stitch cells filling the gaps between those dual grids---see Figure 1. Stitch cells correspond to linear VTK cells (hexahedron, pyramid, wedge and tetrahedron) with values specified at the defining vertices. Our work uses a single case table to create stitch cells, which improves the original approach by making it easier to implement and maintain in visualization software. Stitch cells connect a box to its neighboring boxes in the same level, or containing/adjacent boxes in the coarser parent level. To construct stitch cells and assign values to their vertices, we require access to adjacent samples in these boxes. To facilitate parallelization, we utilize ghost cells, a concept originating from simulation. By extending grids with a one-cell wide layer of cells and filling these cells with values from adjacent grids or the next coarser level, all data required to construct stitch cells are available locally, and it becomes possible to process AMR data on a per-box basis. In simulations, ghost data is normally used at the boundaries to support, e.g., the computation of gradients using only data locally available. For visualization purposes, these cells are typically blanked out, or any generated geometry corresponding to them is removed. It is possible to use a similar concept to handle cells in a box that are invalidated by a finer resolution box. Instead of removing individual cells from a box, by either converting boxes to unstructured meshes or a set of boxes that leaves out refined regions, it is more computationally and storage efficient to keep values in these cells and mark them as “ghost.” This gives rise to a new type of “ghost cell,” i.e., one ghost cell marked as invalid because there is a more accurate data representation available. We handle ghost data at the boundaries as well as ghost data due to invalidation by finer grids, by using an array of flags that specify for each grid cell whether it is a ghost cell or not. If a cell is flagged as ghost, the flag also specifies its type. All visualization algorithms operate on the original rectilinear grids and use the ghost array information to blank out ghost cells. This is the standard implementation in VisIt. In the dual grid, a cell is marked as ghost if any of the cells in the original grid corresponding to its vertices is labeled as a ghost cell, i.e., if it connects any samples that are flagged as invalid.

Figure 2: Isosurface (temperature of 1225K) for the hydrogen flame data set. (i) Close-up view of the isosurface extracted via re-sampling to a vertex-centered format. Cracks are easily visible. (ii) Close-up view of the same region extracted using our new method. There are no discontinuities in the isosurface. (iii) View of the entire crack-free isosurface extracted using our new approach. The isosurface consists of approximately 2.2 million triangles.

To test our algorithm we examined results from two data sets on the Hopper system at the National Energy Research Scientific Computing Center (NERSC). The first data set is a relatively small 3D BoxLib AMR simulation of a hydrogen flame. It consists of 2,581 boxes in three hierarchy levels containing a total of 48,531,968 grid cells. The simulation data size for all 22 scalar variables is 8.1GB, which is approximately 377MB per scalar variable. Figure 2 highlights the difference between an isosurface extracted from a re-sampled data set and the continuous isosurface provided by our new approach. We stored this data set on the local scratch file system. The second data set is a larger 3D BoxLib AMR simulation of a methane flame. This data set consists of 7,747 boxes in 3 levels containing a total of 1,525,420,032 grid cells. The data set has a total size of 592GB for 52 scalar variables, which corresponds to a size of approximately 11.4GB per scalar variable. We stored this data set on the global NERSC file system. Both data sets were provided by the Center for Computational Sciences and Engineering (CCSE) at the Lawrence Berkeley National Laboratory (LBNL). In these experiments, we saw excellent scaling of the stitch cell algorithm, as well as of the following contouring operation, even on the small data set. Unfortunately, we reached the best overall performance with this visualization pipeline at only 120 cores. Although disk I/O is one factor limiting the scaling in this example, the main bottleneck is the ghost data generation phase, as we see its runtime increase with core count. Using a simple model that assumes two fixed transfer rates for intra- and inter-node communication time, we found that the increased amount of ghost data duplicated in the distributed-memory setting explains the increase in ghost communication time. We also examined performance of this same visualization pipeline on the larger methane flame data set. The results showed a significantly better scaling performance for total runtime on this larger data set than on the smaller hydrogen flame data set.

Impact

Our approach extracts crack-free isosurfaces in a distributed-memory setting encountered on many DOE high-performance computing platforms. It is deployed as part of the VisIt visualization tool, which makes it easily available on these platforms. AMR is used for a wide range of DOE relevant application domains (fusion, astrophysics, climate, carbon sequestration), and the ability to extract “correct” isosurfaces benefits data analysis in all these areas. Furthermore, our dual grid and stitch-cell based approach can be used to improve other visualization algorithms (e.g., volume rendering) as well. Finally, this approach could form the basis for deriving topological structures like the contour tree from AMR data.

References

Gunther H. Weber, Hank Childs, and Jeremy S. Meredith. Efficient Parallel Extraction of Crack- free Isosurfaces from Adaptive Mesh Refinement (AMR) Data. In Proceedings of IEEE Symposium on Large Data Analysis and Visualization (LDAV), pages 31-38, October 2012. LBNL-5799E.

Contact

Gunther H. Weber, Hank Childs

Collaborators

Jeremy Meredith, ORNL