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:
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 LB_METHOD: | GRAPH |
| Value of GRAPH_PACKAGE: | Parmetis |
| Parameters: | |
| LB_APPROACH |
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 | |
| PARMETIS_OUTPUT_LEVEL = 0 | |
| PARMETIS_COARSE_ALG = 2 | |
| PARMETIS_SEED = 15 | |
| PARMETIS_ITR = 100 | |
| USE_OBJ_SIZE = 1 | |
| CHECK_GRAPH = 1 | |
| SCATTER_GRAPH = 1 | |
| GRAPH_SYMMETRIZE = NONE | |
| GRAPH_SYM_WEIGHT = ADD | |
| Required Query Functions: | |
| For all submethods: | ZOLTAN_NUM_OBJ_FN |
| ZOLTAN_OBJ_LIST_FN | |
| Only PartGeom & PartGeomKway: | ZOLTAN_NUM_GEOM_FN |
| ZOLTAN_GEOM_MULTI_FN or ZOLTAN_GEOM_FN | |
| All but PartGeom: |
ZOLTAN_NUM_EDGES_MULTI_FN
or
ZOLTAN_NUM_EDGES_FN
ZOLTAN_EDGE_LIST_MULTI_FN or ZOLTAN_EDGE_LIST_FN |
| Optional Query Functions: | |
| ZOLTAN_OBJ_SIZE_MULTI_FN or ZOLTAN_OBJ_SIZE_FN for PARMETIS_METHOD=AdaptiveRepart | |
| ZOLTAN_PART_MULTI_FN or ZOLTAN_PART_FN for part remapping in ParMETIS. |