Zoltan User's Guide  |  Next  |  Previous

## ParMETIS - Parallel Graph Partitioning

ParMETIS is a parallel library for graph partitioning (for static load balancing) and repartitioning (for dynamic load balancing) developed at the University of Minnesota by Karypis, Schloegel and Kumar [Karypis and Kumar]. Note that ParMetis must be obtained separately and has a different license than Zoltan (see page 31 of this manual). ParMETIS is strictly speaking not a method but rather a collection of methods. In the Zoltan context, ParMETIS is a method with many sub-methods. Zoltan provides an interface to all the ParMETIS (sub-)methods.  The user selects which ParMETIS method to use through the parameter PARMETIS_METHOD. Most of the ParMETIS methods are based on either multilevel Kernighan-Lin partitioning or a diffusion algorithm. The names of the ParMETIS methods used by Zoltan are identical to those in the ParMETIS library. For further information about the various ParMETIS methods and parameters, please consult the ParMETIS User's Guide.

Graph partitioning is a useful abstraction for load balancing. The main idea is to represent the computational application as a weighted graph. The nodes or vertices in the graph correspond to objects in Zoltan.  Each object may have a weight that normally represents the amount of computation. The edges or arcs in the graph usually correspond to communication costs. In graph partitioning, the problem is to find a partition of the graph (that is,  each vertex is assigned to one out of k possible sets called parts) that minimizes the cut size (weight) subject to the parts having approximately equal size (weight). In repartitioning, it is assumed that a partition already exists. The problem is to find a good partition that is also "similar" in some sense to the existing partition. This keeps the migration cost low. All the problems described above are NP-hard so no efficient exact algorithm is known, but heuristics work well in practice.

We give only a brief summary of the various ParMETIS methods here; for more details see the ParMETIS documentation. The methods fall into three categories:

1. Part* - Perform graph partitioning without consideration of the initial distribution. (LB_APPROACH=partition)
2. AdaptiveRepart - Incremental algorithms with small migration cost. (LB_APPROACH=repartition)
3. Refine* - Refines a given partition (balance).  Can be applied multiple times to reduce the communication cost (cut weight) if desired. (LB_APPROACH=refine)
As a rule of thumb, use one of the Part* methods if you have a poor initial balance and you are willing to spend some time doing migration. One such case is static load balancing; that is, you need to balance only once. Use AdaptiveRepart or the Repart* methods when you have a reasonably good load balance that you wish to update incrementally. These methods are well suited  for dynamic load balancing (for example,  adaptive mesh refinement). A reasonable strategy is to call PartKway once to obtain a good initial balance and  later update this balance using AdaptiveRepart.

Zoltan supports the multiconstraint partitioning feature of ParMETIS through multiple object weights (see OBJ_WEIGHT_DIM).

The graph given to Zoltan/ParMETIS must be symmetric. Any self edges (loops) will be ignored. Multiple edges between a pair of vertices is not allowed. All weights must be non-negative. The graph does not have to be connected.

Zoltan is currently compatible with ParMETIS version 3.1 and 4.0.x. The ParMETIS source code can be obtained from the ParMETIS home page. ParMETIS has a separate license: 'PARMETIS can be freely used for educational and research purposes by non-profit institutions and US government agencies only. Other organizations are allowed to use PARMETIS only for evaluation purposes, and any further uses will require prior approval from the technology transfer office at the University of Minnesota'
If you do not wish to install ParMETIS, it is possible to compile Zoltan without any references to ParMETIS; (when you 'make' Zoltan, comment out the PARMETIS_LIBPATH variable in the configuration file Utilities/Config/Config.<platform>).