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>).

Value of GRAPH_PACKAGE: Parmetis
The load balancing approach:.
PARTITION  - partition from scratch, not taking the current data distribution into account
REPARTITION  - partition but try to stay close to the current partition/distribution
REFINE  - refine the current partition/distribution; assumes only small changes
    PARMETIS_METHOD The specific ParMETIS method to be used (see below). Note: See also LB_APPROACH, which is a simpler way to specify the overall load balance approach. Only use PARMETIS_METHOD if you really need a specific implementation.
PartKway - multilevel Kernighan-Lin partitioning 
PartGeom - space filling curves (coordinate based) 
PartGeomKway - hybrid method based on PartKway and PartGeom (needs both  graph data and coordinates) 
AdaptiveRepart - adaptive repartitioning (only in ParMETIS 3.0 and higher)
RefineKway - refine the current partition (balance)

The method names are case insensitive.
    PARMETIS_OUTPUT_LEVEL Amount of output the load-balancing algorithm should produce. 
0 = no output, 1 = print timing info. Turning on more bits displays more information (for example, 3=1+2, 5=1+4, 7=1+2+4).
    PARMETIS_COARSE_ALG Coarse algorithm for PartKway. 1 = serial, 2 = parallel. (ParMETIS 2 only)
    PARMETIS_SEED Random seed for ParMETIS.
    PARMETIS_ITR Ratio of interprocessor communication time to redistribution time. A high value will emphasize reducing the edge cut, while a small value will try to keep the change in the new partition (distribution) small. This parameter is used only by AdaptiveRepart. A value of between 100 and 1000 is good for most problems.
    CHECK_GRAPH Level of error checking for graph input: 0 = no checking, 1 = on-processor checking, 2 = full checking. (CHECK_GRAPH==2 is very slow and should be used only during debugging).
    SCATTER_GRAPH Scatter graph data by distributing contiguous chunks of objects (vertices) of roughly equal size to each processor before calling the partitioner. 0 = don't scatter; 1 = scatter only if all objects are on a single processor; 2 = scatter if at least one processor owns no objects; 3 = always scatter. 
    GRAPH_SYMMETRIZE How to symmetrize the graph: NONE = graph is symmetric and no symmetrization is needed
TRANSPOSE = if M is adjacency matrix of the input graph, output will be the graph representation of M+MT
BIPARTITE = graph is symmetrized in a bipartite way : [[ 0 M ][Mt 0]]
    GRAPH_SYM_WEIGHT How edge weights are handled during symmetrization: ADD = weights of each arc are added
MAX = only the heaviest arc weight is kept

See more informations about graph build options on this page

Default values:

LB_APPROACH = Repartition

PARMETIS_METHOD = AdaptiveRepart









Required Query Functions:
For all submethods: ZOLTAN_NUM_OBJ_FN

Only PartGeom & PartGeomKway: ZOLTAN_NUM_GEOM_FN

Optional Query Functions:


ZOLTAN_PART_MULTI_FN or ZOLTAN_PART_FN for part remapping in ParMETIS.

[Table of Contents  | Next:  PT-Scotch  |  Previous:  Graph vs. Hypergraph Partitioning  |  Privacy and Security]