Zoltan User's Guide  |  Next  |  Previous

Graph partitioning: Jostle

Jostle is a library for graph (mesh) partitioning and load balancing developed at the University of Greenwich, London, UK, by Chris Walshaw [Jostle, Walshaw]. The parallel version of Jostle is sometimes called pjostle. In the Zoltan context, the name Jostle always refers to the parallel version of the library. The main algorithm used in Jostle is based on multilevel graph partitioning, and a diffusion-type method is available for repartitioning. Hence the Jostle library is very similar to ParMETIS. See the ParMETIS section for a brief description of graph partitioning as a model for load balancing.

At present, only the most common Jostle options are supported by Zoltan. These are briefly described below. For further details, see the documentation available from the Jostle home page. Other options may be added to Zoltan upon request.

Note that Jostle is not distributed with Zoltan. If you wish to use Jostle within Zoltan, you must first obtain a license for Parallel Jostle and install it on your system. The license is currently free for academic use.  Zoltan has been tested only with parallel Jostle version 1.2.* and may be incompatible with other versions. Zoltan offers only limited support for Jostle and this may be discontinued in the future.
Value of GRAPH_PACKAGE: Jostle
    JOSTLE_OUTPUT_LEVEL Amount of output Jostle should produce.  (integer)
    JOSTLE_THRESHOLD Threshold at which the graph contraction phase is stopped. (integer)
    JOSTLE_GATHER_THRESHOLD Duplicate coarse graph on all processors when there are fewer than this number of nodes. (integer)
    JOSTLE_MATCHING Matching algorithm for graph contraction. (Valid values are "local" and "global".)
    JOSTLE_REDUCTION When reduction is turned off, Jostle performs a diffusion-type algorithm instead of multilevel graph partitioning. (Valid values are "on" and "off".)
    JOSTLE_CONNECT Make a disconnected graph connected before partitioning. (Valid values are "on" and "off".)
    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. 
Default values: See the Jostle  documentation.  See our ParMETIS section for the last two parameters.
Required Query Functions:

[Table of Contents  | Next:  Hybrid Hierarchical Partitioning  |  Previous:  ParMETIS  |  Privacy and Security]