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. Please contact the Zoltan developers if you have a parallel partitioning or load-balancing code and would like assistance with interfacing it to Zoltan.
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.
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.