Here we describe the partitioning interface provided by Isorropia. More...

Collaboration diagram for Isorropia Partitioning and Load Balancing Methods:

Modules
	Isorropia Partitioning and Load Balancing Methods with RCPs
	Here we describe the partitioning interface that uses RCPs.

	Isorropia Partitioning and Load Balancing Methods with Pointers
	Here we describe the partitioning interface that uses Pointers.

Classes
class	Isorropia::Epetra::Partitioner
	An implementation of the Partitioner interface that operates on Epetra matrices and linear systems. More...

class	Isorropia::Epetra::Redistributor
	Class which is constructed with a Partitioner instance, and provides several methods for redistributing Epetra objects given the partitioning computed by the Partitioner object. More...

Functions
virtual	Isorropia::Epetra::Partitioner::~Partitioner ()
	Destructor. More...

void	Isorropia::Epetra::Partitioner::partition (bool force_repartitioning=false)
	partition is the method that computes a rebalanced partitioning for the data in the object that this class was constructed with. More...

virtual void	Isorropia::Epetra::Partitioner::compute (bool forceRecomputing=false)
	Method which does the work of computing a new partitioning/coloring/ordering, depending on the child class used. More...

int	Isorropia::Epetra::Partitioner::numElemsInPart (int part) const
	Return the number of LOCAL elements in a given part. More...

void	Isorropia::Epetra::Partitioner::elemsInPart (int part, int *elementList, int len) const
	Fill user-allocated list (of length len) with the local element ids to be located in the given part. More...

void	Isorropia::Epetra::Redistributor::redistribute (const Epetra_SrcDistObject &src, Epetra_DistObject &target)
	Method to redistribute a Epetra_SrcDistObject into a Epetra_DistObject. More...

void	Isorropia::Epetra::Redistributor::redistribute_reverse (const Epetra_Vector &input_vector, Epetra_Vector &output_vector)
	Reverse redistribute an Epetra_Vector. More...

void	Isorropia::Epetra::Redistributor::redistribute_reverse (const Epetra_MultiVector &input_vector, Epetra_MultiVector &output_vector)
	Reverse redistribute an Epetra_MultiVector. More...

void	Isorropia::Epetra::Redistributor::create_importer (const Epetra_BlockMap &src_map)
	Create an importer object to be used in the redistribution. More...

Detailed Description

Here we describe the partitioning interface provided by Isorropia.

Partitioning and Load-balancing

Isorropia's load balancing user interface consists primarily of the Isorropia::Partitioner, Isorropia::Redistributor and Isorropia::CostDescriber classes, as well as the Isorropia::Epetra::createBalancedCopy functions.

The Isorropia::Epetra::createBalancedCopy functions are free-standing functions (not class members) which simply take an input object (Epetra_CrsGraph, Epetra_CrsMatrix, etc.) and return a copy which is balanced across processes (parts).

In many use cases, such as performing one partitioning and then using it to redistribute multiple objects, it is more efficient to use the Isorropia::Partitioner and Isorropia::Redistributor classes. The general usage model is to:

Create a Isorropia::Partitioner instance, providing the objects to be partitioned, and optionally weights for those objects. Weights can be defined with an Isorropia::CostDescriber for graphs and hypergraphs, or with an Epetra_MultiVector for geometric coordinates.
Create a Isorropia::Redistributor object (providing as input a Isorropia::Partitioner instance)
Use the Isorropia::Redistributor to redistribute one or more objects to the new partitioning.

Isorropia was designed such that these steps can usually be done in three lines of code. For example, the Partitioner will by default compute the partitioning at construction time.

Isorropia currently supports partitioning/redistributing of several Epetra objects, including Epetra_CrsGraph and Epetra_RowMatrix (which includes Epetra_CrsMatrix and Epetra_VbrMatrix). In addition to matrix/graph partitioning, Isorropia has the capability to partition 1, 2 or 3-dimensional real coordinates into balanced spatial regions. The coordinates are represented as an Epetra_MultiVector.

Load-balancing parameters

Isorropia has a fairly small number of parameters that control the partitioning methods. (Default values in all caps.) Note that Isorropia parameters are case insensitive.

STRUCTURALLY SYMMETRIC [NO/yes] (is symmetrization required?)
PARTITIONING METHOD [block/cyclic/random/rcb/rib/hsfc/graph/HYPERGRAPH]
NUM PARTS [int k] (global number of parts)
IMBALANCE TOL float tol
BALANCE OBJECTIVE [ROWS/nonzeros]
DISTANCE [1/2] (for coloring only; two is default)

These parameters are placed in a Teuchos::ParameterList object, which is passed as an argument to Isorropia. Here is an example of how the partitioning method would be set using the parameter list.

  Teuchos::ParameterList params;
  params.set("partitioning method", "graph"); // Corresponds to LB_METHOD in Zoltan

For more specific control of low-level features, you may set a Zoltan parameter. Isorropia can relay Zoltan parameters directly to Zoltan. Before passing a Teuchos::ParameterList to Isorropia, create a sublist in it named "Zoltan". Then, any parameters that should be passed to Zoltan itself, can be stored in the sublist exactly as they appear in the Zoltan users guide. Example:

  Teuchos::ParameterList params;
  Teuchos::ParameterList& sublist = params.sublist("Zoltan");
  sublist.set("phg_output_level", "5");

Refer to the Zoltan User's guide (available at the Zoltan web site) for available Zoltan parameters. In many cases, no parameters are necessary. Note that Isorropia will override a few default Zoltan settings: For graphs and matrices, the default method (LB_METHOD) is HYPERGRAPH. The default approach (LB_APPROACH) is PARTITION. For coordinates the default LB_METHOD is RCB (recursive coordinate bisection).

Partitioning with RCPs and pointers

With Isorropia, we provide two interfaces to the partitioning objects, a reference counting pointer (RCP) based interface and a pointer based interface. The safer interface to the partitioning is the RCP based interface, which a RCP to the Epetra object to the Isorropia partitioner. We suggest using interface in order to prevent memory leaks if you are familiar with RCPs and willing to learn the basics of Teuchos::RCP. However, we also provide a pointer interface for the convenience of those that are more familiar with this type of interface.

More information on these interfaces, as well as functions specific to the interface can be found here:

Example Programs

A number of example programs which demonstrate using Isorropia are provided in the 'packages/isorropia/example' subdirectory.

matrix_1 demonstrates creating a balanced copy of Epetra_CrsGraph and Epetra_CrsMatrix objects using Isorropia::Epetra::createBalancedCopy functions.

part_redist demonstrates repartitioning and redistributing the contents of an Epetra_LinearProblem object, using the Isorropia::Partitioner and Isorropia::Redistributor classes. This program does not use user-specified weights/costs.

Other programs in the example subdirectory demonstrate the use of weights/costs data to influence the partitioner. See vert_weights, graphedge_weights and hgedge_weights.

example_rcb demonstrates the use of Isorropia to partition spatial coordinates using Zoltan's Recursive Coordinate Bisection algorithm.

Function Documentation

virtual Isorropia::Epetra::Partitioner::~Partitioner ( )

virtual

Destructor.

Reimplemented from Isorropia::Partitioner.

void Isorropia::Epetra::Partitioner::partition ( bool force_repartitioning = false )

virtual

partition is the method that computes a rebalanced partitioning for the data in the object that this class was constructed with.

Parameters

force_repartitioning Optional argument defaults to false. By default, compute_partitioning() only does anything the first time it is called, and subsequent repeated calls are no-ops. If the user's intent is to re-compute the partitioning (e.g., if parameters or other inputs have been changed), then setting this flag to true will force a new partitioning to be computed.

Implements Isorropia::Partitioner.

virtual void Isorropia::Epetra::Partitioner::compute ( bool forceRecomputing = false )

virtual

Method which does the work of computing a new partitioning/coloring/ordering, depending on the child class used.

Parameters

forceRecomputing Optional argument defaults to false. Depending on the implementation, compute() should only perform a computation the first time it is called, and subsequent repeated calls are no-ops. If the user's intent is to re-compute the results (e.g., if parameters or other inputs have been changed), then setting this flag to true will force a new result to be computed.

Implements Isorropia::Epetra::Operator.

int Isorropia::Epetra::Partitioner::numElemsInPart ( int part ) const

inlinevirtual

Return the number of LOCAL elements in a given part.

Parameters

part	[in] the part ID we want to know the number of local elements.

Returns: number of local elements that belongs to the given part.

See Also: Isorropia::Operator::numElemsWithProperty()

Implements Isorropia::Partitioner.

void Isorropia::Epetra::Partitioner::elemsInPart	(	int	part,
		int *	elementList,
		int	len
	)		const

inlinevirtual

Fill user-allocated list (of length len) with the local element ids to be located in the given part.

Parameters

part	[in] the part ID we consider
elementList	[out] array of elements that belongs to this part ID, must be allocated by user with size at least `len`
len	[in] maximum number of elements we can put in the array. Usually, may be the result of Isorropia::Partitioner::numElemsInPart(). .

See Also: Isorropia::Operator::elemsWithProperty()

Implements Isorropia::Partitioner.

void Isorropia::Epetra::Redistributor::redistribute	(	const Epetra_SrcDistObject &	src,
		Epetra_DistObject &	target
	)

Method to redistribute a Epetra_SrcDistObject into a Epetra_DistObject.

The caller is required to have constructed the target object using the correct target map.

Examples:: geometric/example_rcb.cpp, and graphedge_weights.cpp.

void Isorropia::Epetra::Redistributor::redistribute_reverse	(	const Epetra_Vector &	input_vector,
		Epetra_Vector &	output_vector
	)

Reverse redistribute an Epetra_Vector.

Parameters

input_vector	(in) a vector that is distributed according to the partitioner that was used to create this Redistributor
output_vector	(out) a copy of the `input_vector` which has been redistributed according to the reverse of the partitioner that was used to create this Redistributor

void Isorropia::Epetra::Redistributor::redistribute_reverse	(	const Epetra_MultiVector &	input_vector,
		Epetra_MultiVector &	output_vector
	)

Reverse redistribute an Epetra_MultiVector.

Parameters

input_vector	(in) a multi vector that is distributed according to the partitioner that was used to create this Redistributor
output_vector	(out) a copy of the `input_vector` which has been redistributed according to the reverse of the partitioner that was used to create this Redistributor

void Isorropia::Epetra::Redistributor::create_importer ( const Epetra_BlockMap & src_map )

private

Create an importer object to be used in the redistribution.

Parameters

src_map (in) the map describing the pattern of the import operation

Modules

Classes

Functions

Detailed Description

Partitioning and Load-balancing

Load-balancing parameters

Partitioning with RCPs and pointers

Example Programs

Function Documentation