Zoltan User's Guide: Jostle Interface

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 LB_METHOD: GRAPH

Value of GRAPH_PACKAGE: Jostle

Parameters:

    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:

ZOLTAN_NUM_OBJ_FN

ZOLTAN_OBJ_LIST_FN

ZOLTAN_NUM_EDGES_MULTI_FN or ZOLTAN_NUM_EDGES_FN
ZOLTAN_EDGE_LIST_MULTI_FN or ZOLTAN_EDGE_LIST_FN

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

Value of LB_METHOD:	GRAPH
Value of GRAPH_PACKAGE:	Jostle
Parameters:
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:
	ZOLTAN_NUM_OBJ_FN
	ZOLTAN_OBJ_LIST_FN
	ZOLTAN_NUM_EDGES_MULTI_FN or ZOLTAN_NUM_EDGES_FN ZOLTAN_EDGE_LIST_MULTI_FN or ZOLTAN_EDGE_LIST_FN