Zoltan Developer's Guide  |  Next  |  Previous

Appendix: ParMETIS and Jostle

Overview of structure (algorithm)

This part of Zoltan provides an interface to various graph-based load-balancing algorithms. Currently two libraries are supported: ParMETIS and Jostle. Each of these libraries contain several algorithms.

Interface algorithm

The structure of the code is as follows: Each package (ParMETIS, Jostle) has its own wrapper routine that performs initialization and sets parameters. The main routine is Zoltan_ParMetis_Jostle, which constructs an appropriate graph data structure using Zoltan's query functions. After the graph structure has been constructed, the appropriate library is called and the import/export list is created and returned.

Please note that ParMETIS and Jostle are not integral parts of Zoltan. These libraries must be obtained and installed separately. (ParMETIS may be bundled with Zoltan, but it is an independent package developed at Univ. of Minnesota.) Zoltan merely provides an interface to these libraries.

The most complex task in the interface code is the construction of the graph data structure. This structure is described in the next section. The routine uses the Zoltan query functions to get a list of objects and edges on each processor. Each object has a unique global ID which is mapped into a unique (global) number between 1 and n, where n is the total number of objects. The construction of the local (on-processor) part of the graph is straightforward. When an edge goes between objects that reside on different processors, global communication is required. We use Zoltan's unstructured communication library for this. A hash function (Zoltan_Hash) is used to efficiently map global IDs to integers. The graph construction algorithm has parallel complexity O(maxj {nj+mj+p}), where nj is the number of objects on processor j, mj is the number of edges on processor j, and p is the number of processors.

One other feature of the interface code should be mentioned.  While Zoltan allows objects and edges to have real (float) weights, both ParMETIS and Jostle currently require integer weights. Therefore, Zoltan first checks if the object weights are integers. If not, the weights are automatically scaled and rounded to integers. The scaling is performed such that the weights become large integers, subject to the constraint that the sum of (any component of) the weights is less than a large constant MAX_WGT_SUM < INT_MAX. The scaled weights are rounded up to the nearest integer to ensure that nonzero weights never become zero. Note that for multidimensional weights, each weight component is scaled independently. (The source code is written such that this scaling is simple to change.)

Currently Zoltan constructs and discards the entire graph structure every time a graph-based method (ParMETIS or Jostle) is called. Incremental update of the graph structure may be supported in the future.

The graph construction code in Zoltan_ParMetis_Jostle can also be used to interface with other graph-based algorithms.

Algorithms used in ParMETIS and Jostle libraries

There are two main types of algorithms used in ParMETIS and Jostle. The first is multilevel graph partitioning. The main idea is to take a large graph and  construct a sequence of smaller and simpler graphs that in some sense approximate the original graph. When the graph is sufficiently small it is partitioned using some other method. This smallest graph and the corresponding partition is then propagated back through all the levels to the original graph. A popular local refinement strategy known as Kernighan-Lin is employed at some or every level.

The second main strategy is diffusion. This method assumes that an initial partition (balance) is given, and load balance is achieved by repeatedly moving objects (nodes) from parts (processors) that have too heavy load to neighboring parts (processors) with too small load.

For further details about the algorithms in a specific library, please refer to the documentation that is distributed with that library.

Data structures

We use the ParMETIS parallel graph structure. This is implemented using 5 arrays:
  1. vtxdist: gives the distribution of the objects (vertices) to processors
  2. xadj: indices (pointers) to the adjncy array
  3. adjncy: neighbor lists
  4. adjwgt: edge weights
  5. vwgt: vertex (object) weights
The vtxdist array is duplicated on all processors, while the other arrays are local.
For more details, see the ParMETIS User's Guide.

Parameters

Zoltan supports the most common parameters in ParMETIS and Jostle. These parameters are parsed in the package-specific wrapper routine (Zoltan_ParMetis or Zoltan_Jostle) and later passed on to the desired library via Zoltan_ParMetis_Jostle.

In addition, Zoltan has one graph parameter of its own: CHECK_GRAPH. This parameter is set in Zoltan_ParMetis_Jostle and specifies the amount of verification that is performed on the constructed graph. For example, it is required that the graph is symmetric and that the weights are non-negative.

Main routine

The main routine is Zoltan_ParMetis_Jostle but it should always be accessed through either Zoltan_ParMetis or Zoltan_Jostle.



[Table of Contents  |  Next:  Hypergraph Partitioning  |  Previous:  Recursive Inertial Bisection (RIB)  |  Privacy and Security]