Trilinos Meshes, Geometry and Load Balancing Capabilities

Introduction

Meshes and Geometry
PAMGEN: Inline Meshing
phdMesh: Unstructured Mesh Database
ABMesh: Array-Based Mesh Database
TUCASA: Parallel Mesh File Interface
Load Balancing Capabilities
Isorropia: Matrix Partitioning, Ordering and Coloring
Zoltan: Dynamic load balancing, partitioning, ordering and coloring

Introduction

The goal of the Meshes, Geometry and Load-Balancing Capability Area is to provide libraries, tools, and common interfaces for creating, accessing and manipulating mesh and matrix data within applications. This capability area was created in FY08; several related packages were released in Trilinos v9. Geometry and mesh efforts include in-application meshing tools for simple geometries, mesh databases, and mesh I/O and redistribution libraries. Load-balancing capabilities include partitioning and repartitioning for matrices and meshes, as well as other types of data (particles, circuits, etc.). The following activities are planned for this capability area:

Meshes and Geometry

Generation, management and manipulation of mesh-based data play key roles in many scientific simulations. Finite difference, volume, and element methods require efficient mesh generation and management. Adaptive mesh refinement methods require even more sophisticated mesh management, along with the ability to modify, manipulate, and redistribute mesh and geometry data. The effectiveness of such tools directly impacts almost every phase of an application, from the discretization (e.g., Intrepid) to the solution methods to the parallel efficiency.

Trilinos' initial efforts in geometry and meshing capabilities will address three key components of mesh use in applications. Inline meshing (PAMGEN) allows simple geometries to be meshed on-the-fly within a parallel application, rather than requiring mesh generation as a file-based preprocessing step. More complex meshes stored in files must be efficiently read in parallel and initially distributed to processors (TUCASA). And databases to efficiently store and manage mesh data greatly simply the bookkeeping burden of parallel applications (phdMesh).

PAMGEN: Inline Meshing Library

Point of Contact: D. Hensinger (SNL)
Status: PAMGEN was released in Trilinos 9.0 in September 2008.

Serial generation of large finite-element meshes is a serious bottleneck for large parallel simulations. PAMGEN, a parallel mesh generation library, surmounts this barrier by allowing on-the-fly scalable generation of simple finite element meshes. It has been used to generate more than 1.1 billion elements on 17,576 processors. Each processor is given a complete specification of the geometry, and creates a full representation of only the elements that are local to the processor. The resulting mesh data structure can be queried through a C interface to determine local mesh geometry and topology as well as inter-processor connections. Currently, the library generates meshes of domains with cylindrical, tubular, and block shapes. Substantial control is allowed over the distribution of elements within those shapes. Boundary condition regions, as node and element face lists, can be specified on the surfaces and interior of the mesh.

phdMesh: Unstructured Mesh Database

Point of Contact: H.C. Edwards (SNL)
Status: phdMesh was released in Trilinos 9.0 in September 2008.

Multiphysics parallel applications with mixed discretization schemes, adaptive unstructured meshes and parallel distributed data sets have inherent complexity that must be managed. phdMesh is a compact, flexible software component designed to manage parallel, heterogeneous and dynamic unstructured meshes. phdMesh was developed as part of the Mantevo project as a mini-application that approximates and assesses the performance of much larger mesh-based applications. The formal mesh model in phdMesh accommodates problem specifications through application-defined parts and fields; heterogeneous discretizations are accommodated through application-defined entities and connections. Computational efficiency is achieved by partitioning data into homogeneous kernels that may be operated on through a contiguous block of memory.

ABMesh: Array-Based Mesh Database

Point of Contact: R. Drake (SNL)
Status: ABMesh will be included in Trilinos 10.0 in September 2009.

ABMesh provides a mesh database with efficient parallel array-based data structures compatible with many mesh file formats (e.g., Exodus, Nemesis). ABMesh supports a large number of element types in two and three dimensions, element blocking for multi-material simulations, and nodal and elemental boundary conditions. It will provide convenient native interfaces as well as ITAPS-compatible iterfaces for greater interoperability within applications.

TUCASA: Parallel Mesh File Interface

Point of Contact: R. Drake (SNL)
Status: TUCASA will be included in Trilinos 10.0 in September 2009.


Load Balancing Capabilities

Load balancing is the distribution of data (e.g., matrix rows, matrix nonzeros, mesh elements, particles) to processors. Its goal is to eliminate processor idle time (by assigning equal amount of work to each processor) while attempting to minimize interprocessor communication (by minimizing the amount of off-processor data each processor needs). Static partitioning provides an initial distribution of data to processors; it can be done once as a preprocessor to a simulation. Repartitioning (a.k.a. dynamic load balancing) redistributes data to adjust for changing work loads or data dependencies within a simulation. Repartitioning has the additional goal of minimizing the cost of moving from the old distribution to the new one (a.k.a. data migration cost).

The capabilities to be provided in Trilinos include matrix partitioning for row-based, column-based, and nonzero-based distributions of matrix data (Isorropia), as well as general partitioning and repartitioning capabilities for a wide variety of data, including mesh entities (Zoltan).

Isorropia: Matrix Partitioning

Point of Contact: E. Boman (SNL)
Isorropia Page: http://trilinos.sandia.gov/packages/isorropia/
Status: Isorropia was enhanced and released in Trilinos v9.0.

Isorropia is a repartitioning/rebalancing package that redistributes matrices and matrix-graphs in a parallel execution setting to enable more efficient matrix computations. Isorropia is the package to use for distributing EPetra data structures. Through an interface to the Zoltan library, it computes parallel matrix distributions that have balanced computational work and low interprocessor communication costs for common matrix operations. It also creates Epetra maps for redistributing matrices according to the computed data distributions, and migrates matrix data to the new distribution. Current development efforts include matrix ordering and two-dimensional matrix partitioning interfaces.

Isorropia also contains interfaces to Zoltan's parallel coloring and matrix ordering capabilities. Parallel matrix ordering can reduce matrix fill during direct factorizations. The interface provides access to both the matrix permutation vector and the separator trees used in reordering. Parallel coloring is an important capability for some preconditioners. Colors are assigned to matrix rows depending on the connectivity of rows through nonzero entries in the matrix. The interface provides both distance-one and distance-two coloring. See below for more details on coloring and ordering.

Zoltan: Dynamic load balancing, partitioning, coloring and ordering

Point of Contact: K. Devine (SNL)
Zoltan Page: http://www.cs.sandia.gov/Zoltan
Status: Zoltan is currently available for download from the Zoltan home page. It is also released in Trilinos 9.0 in September 2008.

The Zoltan library includes a suite of partitioning and repartitioning algorithms for general applications. It can be used for distributing matrices, meshes, particles, agents, or any objects within a simulation. The partitioning and repartitioning algorithms include geometric methods (useful for particle- and mesh-based applications), and connectivity-base methods (such as graph- and hypergraph-partitioning). Three interfaces to Zoltan exist (in order of decreasing maturity): the native Zoltan interface the Isorropia Epetra matrix interface, and the ITAPS mesh interface. The native Zoltan interface is data-structure neutral, so an application does not have to build or use specific data structures to use Zoltan. This design allows Zoltan to be used by a wide range of applications. Zoltan is widely used in the ASC community, and is a key component of the SciDAC CSCAPES and ITAPS projects. Current research efforts include scalable partitioning strategies for multicore architectures, matrix ordering algorithms, and two-dimensional matrix partitioning.

Using essentially the same interfaces, Zoltan also enables parallel matrix ordering and coloring. Zoltan provides consistent interfaces to the graph ordering algorithms in PT-Scotch and ParMETIS; using the same interface, users can switch between ordering methods to compare their effectiveness. Zoltan also provides native parallel distance-one and distance-two graph coloring using the same graph-based interface. These algorithms are state-of-the-art distributed memory implementations, as described in the following JPDC article: A Framework for Scalable Parallel Greedy Coloring on Distributed Memory Computers.