Parallel MxN Repartitioning

I. Overview

This note outlines the algorithm for performing MxN repartitioning of mesh data as the time data is being loaded from a file. It's key features include:

1. The algorithm presented is to be replicated in each process of a parallelized program.
2. The algorithm is generalized to finite element or general polyhedral mesh forms and can support load balanced or h-adaptive mesh data. Structured mesh partitioning must be based on rectangles or the resulting partitioned mesh will have to be a finite element or general polyhedral form.
3. The algorithm is generalized to handle any partitioning description, such as those generated for minimizing communications, load balancing, or partitioning based on assembly parts.
4. The algorithm uses a partitioning form that can include ghost regions or the algorithm implementation can be easily varied to generate ghost regions.
5. By performing the repartitioning at file load time each time step may be easily load-balanced for optimum performance by simply adjusting the element partitioning description to reflect the desired load-balanced configuration.
6. By performing the repartitioning at file load time the algorithm may be easily adapted to use separate smart I/O processes which may then minimize the data transfer volumes to and from the compute processes with a minimal subset extraction being performed on the I/O processor. This also minimizes the communications overhead for streaming I/O from a running data source, such as from a running simulation, or to a running data sink, such as to a visualizer or other post-processing activity.

Variations on the MxN repartitioning have been implemented and are used for different tasks, and these variations are listed here:

• Single process forms --
  1. A global mesh to N parallel partitions
  2. M partition mesh files (or file sets) to one global mesh (commonly called a JOIN)
  3. M partitions to a single global mesh then to N partitions (JOIN, then partition, the common form of MxN repartitioning)
• N process forms (one partition per process) --
  1. A global mesh to 1 partition
  2. M partitions to a single global mesh then to 1 partition
  3. Only m (much smaller than M) partitions to a global mesh subset then to 1 partition (minimize JOIN sources per process)
  4. Only m (much smaller than M) partitions to a single partition (minimized computations)

Once the last form is implemented in a well-designed set of routines any of the other forms can be implemented using those routines.

The MxN repartitioning algorithm details are given, then the key algorithm for determining the minimal collection of sets needed to cover all the members of another set is presented.

Although references are made to structures and routines in the Data Object Library (DOL) this algorithm is by no means limited to use with the DOL.

II. MxN Repartitioning Algorithm for Each Process

This algorithm is broken into three parts. The first part is a sequence of one-time metadata generation steps with references to the DOL metadata structures involved. The second part is the collection of steps required to actually compute the detail data for data extraction, which may be done once for static mesh data, but must be repeated each time step for dynamic mesh forms. The third part is the data extraction that must be performed each time step.

A. Metadata Steps

Only one set of mesh metadata needs generated, and that is the metadata for the desired partition.

1. Read in the overall mesh metadata, getting the logical structure of sets, subsets, and relations. The DOL main structures included are:
   • The mesh
   • The sequence (time) set and its time field,
   • the mesh blocks,
   • the mesh cell sets and their connectivity, and
   • any other sets and their relations.
   This may be done by reading in a single partition file's metadata, then cloning its metadata, as each partition should mirror the overall mesh metadata structure of sets, subsets and relations.

2. Obtain the field metadata only for those fields which are to be represented in the end product, including all coordinate fields. This supports field subsetting.
3. Obtain the description of the desired time steps and build the time steps mapping from new to old instance indices.

4. Generate the set partitioning and communications maps metadata. The DOL main structures included are:
   • The mesh partitioning structures,
   • The partitioning structures for each mesh block, and
   • The partitioning structures for each cell set.
   This includes determining the subsets shared among the partitions, and calculating the sharing patterns.

5. Generate the partitioning crosslink structures. The DOL main structures included are:
   • The partitioning descriptions crosslinks context structure,
   • The crosslink base structure for each base cell set, and
   • The crosslink structures for each cell set.
   These structures are later used to store the set extraction and insertion (join) mappings so they can be applied to the relevant relations and fields.

B. Set and Relation Extraction

Each process must receive the data for one of the N partition domains (P_i) from the desired partitioning of B, where each P_i, for i=1,...,N is a subset of B. The file partition domains (F_j) for j=1,...,M reflect a preexisting partitioning of B as it exists in the M files or sets of files, where each F_j is a subset of B. Neither of the two sets of partitions (P_i's and F_j's) need be strict partitionings of B, as they may have non-empty intersections between (overlap among) their partition domain sets. However the set of all P_i's and the set of all F_j's each must include all the members of B (form a cover for B).

1. For the element cell type either read or calculate the subset descriptions for all of the desired partitions (P_i) of B. If this partitioning does not include the ghost regions to be included in each partition then this is where the desired number of ghost levels should be determined and the ghost level extensions to the partition extents calculated and included in (P_i).

2. Read in or calculate the communications maps for the current process's element cell set (P_i), including any ghost regions.

3. Propagate the element partitioning (P_i) for the current process to all the element cell set's subsets.

4. Propagate the element partitioning (P_i) to each the other cell type present and to their subsets. This may be complicated by convoluted connectivity storage approaches used for the various mesh representations and the available file format conventions:
   • All needed connectivity among the cell sets is in the domain block, and between the domain cell sets (the simplest form to partition).

   • The connectivity is from element subsets in element blocks to the node set in the domain block (a common finite elements form, and the domain cell set connectivity must be generated from the union of the element block subset connectivities for easy partitioning).

   • There is NO connectivity TO a given non-element cell set, only FROM that non-element cell set to nodes or elements. (This form is common for a set of external faces or edges with connectivity to element sets and/or node sets, and the easiest way to handle the deficiency is to calculate the inverse of either of the other connectivities).

   • Indirect connectivity, such as zones to faces, faces to edges, and edges to nodes, and missing the commonly needed zones to edges, zones to nodes, and faces to nodes connectivity (common in general polyhedral representations, and it may be handled by merely propagating the partitioning successively to each of the cell sets).

   • Implicit connectivity based on reference ordering, such as zones to nodes, where the faces to nodes and edges to nodes can be assumed because of a PATRAN ordering of each zone's node references (common to finite element representations, and must be handled by generating an "elements to faces" and/or "elements to edges" relation to propagate the partitioning to existing face sets or edge sets, other difficulties arise in finding matching faces or edges of adjacent elements).

   • Implicit connectivity based on index patterns, where adjacent element indices imply adjacent elements and adjacent node indices imply adjacent nodes, and where an element's indices and the element's indices plus one are the indices of the nodes for that element. Connectivity to faces or edges is more complex but similarly derived (common for structured mesh representations).