Agenda

• Announcements
• Distributed Data Structures
  • Mesh structures

Announcements

• Computer Science Class of 60's speaker this week - with Allan Fisher from iCarnegie. Tonight 8 PM in TCL 123, the topic is "Unlocking the Clubhouse: Women in Computing," and Friday during the regular colloquium slot his topic is "iCarnegie: Collaborative Education of Software Developers."

Distributed Data Structures

We'll continue our discussion of distributed data structures with a detailed look at one particular implementation of a distributed mesh data structure.

We looked at the simple two-dimensional mesh examples at the end of the last class. Here are some examples of three-dimensional meshes:

• Mesh of the space about the wing of an Onera M6 airplane. Contains 85,567 tetrahedral elements.
  
• Mesh of a very fake airplane.
  
• Mesh of a simplified perforated shock tube (well, a half cylinder joined with a larger quarter cylinder). Contains about 35,000 tertrahedral elements.
  
• Mesh of human arteries, created from MRI data. Contains 1,103,018 tetrahedral elements.
  

Each of these is stored in memory using a hierarchical linked structure. These structures are implemented in a software library called the SCOREC Mesh Database (MDB).

The most recent versions of MDB are written mostly in C++, but we will look at it from a C interface only.

A version of this software is installed on the bullpen cluster in /dists/bullpen/terescoj/develop/model/scorecMesh/4.5. The public interface is given by the file MSops.h in the include subdirectory. The source code is in scorecMesh and its subdirectories.

The MDB interacts with a geometric modeler that is in /dists/bullpen/terescoj/develop/model/model/1.5. The geometric model defines the geometry of the entire domain represented by the mesh. It is used to allow mesh entities to determine if they are on domain boundaries, where boundary conditions may need to be applied when a solution is computed on the mesh. It is also useful if/when the mesh is modified to make sure the new mesh is consistent with the actual domain geometry. The association of a mesh entity with a geometric model entity is called its geometric model classification.

Both the mesh and model libraries make use of a utility library that is in /dists/bullpen/terescoj/develop/util/util/1.0.

The full mesh entity hierarchy is represented. All vertices, edges, faces, and regions are stored in lists. Each entity also maintains lists of its bounding sub- or super-entities.

You are unlikely to use any of the mesh operators directly in your progrtams, but it is worth looking at them to get an idea of what is possible.

Here are what some of the operators do (found in MSops.h):

• General library functionality: MS_init(), MS_exit()
• Meshes and geometric models (type pMesh)
  • Create model: GM_createFromFile(const char *)
  • Create mesh: MS_newMesh(pGModel), M_load(pMesh, const char *), M_delete(pMesh)
  • Create entities: M_createR(), M_createF(), M_createE(), M_createVP(),
  • Query entity counts: M_numRegions(pMesh), M_numFaces(pMesh), M_numEdges(pMesh), M_numVertices(pMesh)
  • Entity traversals: M_nextRegion(), M_nextFace(), M_nextEdge(), M_nextVertex()
• Mesh entities:
  • Region can query bounding faces, edges, vertices.
  • Face can query bounding edges, vertices; regions it bounds.
  • Edge can query bounding vertices; faces or regions it bounds.
  • Vertex can query edges, faces, regions it bounds, also coordinates.
• List operations

Mesh files can also be loaded, stored. They are in "sms" file format.

We could write programs to operate entirely on these meshes (and many have been written) but it is not yet parallel.

A second library, the Parallel Mesh Database (PMDB) is built on top of MDB and provides for distributed meshes.

PMDB is in /dists/bullpen/terescoj/parallel/pmdb/5.5 on bullpen. Its documentation is online

We would like our distributed meshes to provide all the functionality and flexibility that is provided by the regular MDB.

See description and figures in the Applied Numerical Mathematics reprint.

Each process gets a complete MDB mesh representing its subset of the overall mesh. The normal MDB operations are used to query, traverse, and update these. PMDB manages the interprocess boundary structures: interprocess links, local lists of entities on partition boundaries.

Interprocess links:

PMDB operators allow the interprocess links to be queried and updated.

Boundary entity lists:

Migration:

Migration is also provided that allows any top level entity to be sent from any process to any other process:

PMDB takes care of all of the message passing to migrate the mesh entities as appropriate and to update all of the partition boundary structures.

Somehow these distributed meshes have to be distributed. A variety of algorithms can be used for this and several of these algorithms will be topics for our discussions next week.

Adaptive mesh refinement is provided by the (very scary) refdref library.

• Refinement of tetrahedra:
  
• Coarsening of tetrahedra:
  

Rather than writing our own programs that use these tools, we will look at some existing programs. The first is called PMDBtool, the second is a discontinuous Galerkin solver called LocoParSolver.

The PMDBtool documentation is online.