[View PDF]

Tom Peterka, Juliana Kwan, Adrian Pope, Hal Finkel, Katrin Heitmann, Salman Habib, ANL
George Zagaris, Berk Geveci, Kitware
Wei-keng Liao, NU

Objectives

• Parallelize computational geometry algorithms and deploy in cosmology simulations at scale
• Transform sparse point cloud data into a continuous field (tessellation) that can be interpolated everywhere
• Use tessellations to extract knowledge about features
• Enable improved regular grid sampling

Impact

• Identification of large-scale structures such as halos and voids
• Quantification of structures via Minkowski functionals
• Time-varying statistics of structures
• Improved accuracy of regular grid density estimation
• In situ performance

Accomplishments

• Developed open-source parallel tess library
• Deployed tess in cosmotools framework with Kitware including plugin to Paraview
• Included parallel netCDF file format reader and writer in collaboration with Northwestern University
• Published in situ scalability in HACC cosmology code
• Developed parallel regular grid 3D and 2D density estimator

Three representations of the same halo. Left: original raw particle data. Middle: Voronoi tessellation. Right: regular grid density

Notes:

Executive Summary

N-body computational codes, for example the HACC cosmology code, act on particles and store their results as particles. Particle datasets are essentially sparse point samples of a continuous field, but many analysis operations, such as computing derivatives, integrals, or interpolants act on a continuous field that has values everywhere, which is not the case for particles. The normal way to compute a continuous field is to count the number of particles in the vicinity of each regular grid point and assign a density value there. However, such methods break down when there are large void regions in the data or when the range of densities is very high. This is exactly the case in cosmology, where the densest region is often one million times more populated than the sparsest region. In such cases, a better way to compute a field that self-adapts to the density everywhere is to compute a Voronoi or Delaunay tessellation. These are unstructured meshes where the size of each cell is determined by the particle spacing. The problem is to compute such tessellations in parallel and at the full scale of the simulation so that this operation can be done in situ with the simulation. This has never been done until now. We wrote a parallel tessellation library that cosmologists, materials scientists, and anyone dealing with large particle data can use, and the details of this work are outlined below.

Objectives

• With our technique, we are able to take existing serial algorithms for Voronoi and Delaunay tessellations implemented in open source libraries such as QHULL and CGAL and parallelize them over our DIY framework.
• This allows us to take particle data from N-body simulation codes and treat the data as a continuous field that is able to be integrated, differentiated, interpolated, in short, treated as a dense geometric field. This is especially useful in regions where the particles are sparse, because the original data representation contains large void areas of missing data.
• Once we have a field, many operations are possible. For example, we can apply a threshold and compute statistics about connected components. These correspond to physical structures such as halos or voids in the cosmology.
• For some applications such as lensing in astronomy or some visualization algorithms, a regular grid is needed. We can use the tessellation to improve the accuracy of sampling onto a regular grid, especially in under-dense (sparse) regions where traditional particle-counting methods such as cloud-in-cell (CIC) fail.

Impact

• Cosmologists can identify structures using this technique. While many halo-finders exist, void-finding is still challenging because of the lack of particles in under-dense regions. Tessellations help solve this problem by “filling in” the empty areas.
• We can compute total surface area, total volume, genus, and concavity on the connected components of Voronoi cells. These quantities, called Minkowski functionals, are recognized by cosmologists as being useful shape descriptors.
• We can compute tessellations in situ at as high a temporal frequency as we wish, in order to see how statistics (for example density distribution) change over time.
• Regular grid estimation for lensing applications are another use case for tessellations in cosmology and astrophysics.
• We demonstrated  in situ execution inside cosmology applications such as HACC, avoiding I/O bottlenecks to read and write particle and tessellation data.

Accomplishments

Our library, tess, is open source and available for others to use. Through a collaboration with Kitware, it is being deployed in the cosmotools framework of in situ cosmology analysis tools. We also developed a plugin for ParaView so that tess output can be read in and visualized. The plugin exists in the production release of ParaView. We included parallel netCDF I/O for high-peformance parallel I/O on HPC platforms. We developed a 3D and 2D grid density estimator using the Voronoi tessellation to accurately resample particle data onto regular grids.

Our work is published in:

Peterka, T., Kwan, J., Pope, A., Finkel, H., Heitmann, K., Habib, S., Wang, J., Zagaris, G.: "Meshing the Universe: Integrating Analysis in Cosmological Simulations". Proceedings of the SC12 Ultrascale Visualization Workshop, Salt Lake City, UT.