Partitioning

Local vs Global Partitioners

A local partitioner partitions the mesh elements assigned to each process independently of the other processes. For Zoltan, ParMETIS, and our geometric partitioners we run one instance of the partitioner per process using the MPI_COMM_SELF communicator; the partitioner runs in serial on each process. A global partitioner partitions the mesh elements assigned to all processes. For Zoltan, ParMETIS, and our geometric partitioners we run one instance of the partitioner across all processes; the partitioner runs in parallel.

zsplit is a local partitioner that calls the ParMETIS multi-level part k-way graph method. split is also a local partitioner; it uses a recursive inertial bisection method. When either is run on a serial mesh it is effectively operating a as global partitioner as it sees all the mesh elements.

A load balancer operates on existing parts to improve their balance; no additional parts are created.

Memory Usage

Global and local partitioners have a lower bound on memory cost that is N + N(1-1/T); N is the memory cost of a part on a given process and T is the split factor (i.e., the number of target parts each part will be divided into). This cost is due to the replication of mesh elements before they are sent to the destination processes. For example, to split a mesh from one part to four 3/4 of the mesh elements need to be copied then sent to the new processes; mesh elements are removed from the source/original part after they are copied. Note, global multi-level graph based partitioning methods (e.g., ParMETIS Part K-way) may hit peak memory usage during the partition computation (which precedes the element migration procedure) for process counts at or above 16 thousand.

Available Partitioning Tools in PUMI/core

• split - recursive inertial bisection local partitioner, requires that the split factor (F=T/S, where T and S are the target and source part counts, respectively) is a power of 2 (i.e., 2, 4, 8, ...)
• zsplit - ParMETIS Part K-way local partitioner
• ptnParma - combines partitioning with load balancing - see below for details
• zbalance - ParMETIS Part K-way global load balancer

ptnParma

The ptnParma tool from SCOREC/core provides a command line tool to partition and load balance a mesh using Zoltan and ParMA.

Running the ptnParma without arguments will output the following usage statement:

Usage: ptnParma <model> <mesh> <outMesh> <factor> <method> <approach> <0:global|1:local>

The factor argument is defined as the finalPartCount/initialPartCount. So, for example, to partition a serial (one part) mesh to eight parts set factor to eight. To partition the eight part mesh to 32 parts set factor to four.

The method argument sets Zoltan's partitioning algorithm. The following options are available:

• rib for recursive inertial bisection
• rcb for recursive coordinate bisection
• hg for hyper-graph
• pmetis for ParMETIS (see below for options)

The approach argument controls the application of the selected partitioning algorithm. The following options are available (see the Zoltan Manual):

• ptn partition without consideration of the initial distribution
• reptn limit the migration costs to build the new partition
• refine reduces the cut weight
• kway (pmetis only) multilevel Kernighan-Lin partitioning
• geomkway (pmetis only) hybrid method based on PartKway and space filling curves"
• refkway (pmetis only) refine the current partition (balance)

Setting the last argument, <0:global|1:local>, to 0 runs one instance of the selected partitioner that can use information about the entire partition to make 'global' decisions. Setting the argument to 1 runs one instance per-process ('local') that can only use the on-process partition information to make decisions.

When creating a partition with less than 16Ki parts, the recommended settings are pmetis for method and reptn for approach and 1 for <0:global|1:local>. Assuming the input partition is fairly well balanced, then pmetis, reptn, and 0 should be used local ParMETIS graph-based.

After partitioning ParMA Vertex>Element balancing runs to reduce the vertex and element imbalances.