# Presentation: 504461

## Partitioning and Load-Balancing in Trilinos

**Erik Boman**
**Cedric Chevalier, Karen Devine, Lee Ann Riesen**
**Sandia National Laboratories, NM, USA**
**Trilinos User’s Group, Oct 21, 2008.**

## Partitioning and Load Balancing 

- Load Balancing
- Assign data/work to processors to distribute data/work evenly and minimize communication
- Static vs. dynamic
- Static: Partition once (pre-processing)
- Dynamic: May need to repartition and redistribute data (at run-time)

## Partitioning Methods 

- Block distribution
- Give n/p consecutive data elements (e.g. rows) to each proc.
- Good load balance, but possibly high communication
- Default distribution for Epetra maps!
- Graph partitioning
- Vertices (weighted) = computation
- Edge (weighted) = data dependence
- Minimize cut edges
- Hypergraph partitioning
- Generalizes graph partitioning
- Accurate model of communication volume
- Works for nonsymmetric and rectangular matrices

## Zoltan 

- Toolkit: Focus on partitioning and load-balancing
- Collection of many partitioning algorithms
- Also provides graph coloring, matrix ordering (Cedric)
- Mature (predates Trilinos); used in production codes
- New package in Trilinos 9.0
- May also be obtained and built separately
- No dependence on Trilinos packages

## Zoltan SupportsMany Applications

- SIERRA, ALEGRA, CHISELS, Presto, Chemcell, Xyce, Aleph, ...

## Zoltan Toolkit: Suite of Partitioning Algorithms

**Zoltan Toolkit: Suite of ****Partitioning Algorithms**

**Recursive Coordinate Bisection**** **
**Recursive Inertial Bisection**** **

**Space Filling Curves**
**Refinement-tree Partitioning**
**Octree Partitioning**

**Graph Partitioning**
**(ParMETIS**** , ****PHG )**

**Hypergraph Partitioning****             **

## Zoltan and Isorropia

- Isorropia is the primary user interface to Zoltan for Trilinos/Epetra users

- Zoltan

- Isorropia

- Trilinos
- application

## Isorropia

- Isorropia is a Trilinos package that provides a matrix-based interface to Zoltan
- Requires: Zoltan, Epetra, Teuchos
- Relies on Zoltan for most algorithms
- Focuses on sparse matrix partitioning
- Accepts Epetra matrices as input
- Supports block, graph, hypergraph partitioning
- Generates good Epetra maps
- Load-balanced to reduce communication

## Feature Overlap

- Isorropia only supports a subset of Zoltan
- Expanding to most features
- Isorropia will soon go beyond Zoltan
- 2d matrix partitioning

## Isorropia API

**Three primary user-interface classes:**
**Partitioner:**
- Constructed with distributed graph/matrix as input, calls Zoltan to compute ‘new’ partitioning (map).
**Redistributor:**
- Constructed with Partitioner instance. Can then be used to redistribute objects (matrices, vectors, matrix-graphs) from the old partitioning to the new partitioning.
**CostDescriber:**
- Interface which allows users to specify weights or costs associated with the vertices or edges of the object to be repartitioned.
- Allows user-specified vertex weights, graph edge weights,and hypergraph edge weights.

## Isorropia Example 

**// RCP is a smart pointer type in Teuchos.**
**RCP<const Epetra_CrsMatrix> matrix = ...**
**RCP<const Epetra_Vector> vec = ...**
**Teuchos::ParameterList paramlist; //Optionally set Zoltan parameters**
**// Create partitioner from matrix**
**Isorropia::Epetra::Partitioner partitioner(matrix, paramlist); **
**//partitioner->compute_partitioning();**
**// Create redistributor from partitioner**
**Isorropia::Redistributor rd(rcp(&partitioner)); **
**// Create a balanced matrix from redistributor**
**RCP<Epetra_CrsMatrix> balanced_matrix = rd.redistribute(*matrix);**
**RCP<Epetra_Vector> balanced_vec = rd.redistribute(*vec);**

## Load-balancing in Trilinos

- An application has two options:
- Call Zoltan directly
- Most flexible approach
- App must write Zoltan callback functions
- No support for Epetra data types
- Use Isorropia
- Highly recommended (easy!) for Epetra users
- Currently limited to sparse matrices (graphs)
- Geometric partitioning via Multivectors under development (not in 9.0)

## Comparison Chart

| Build system | Automake and manual | Automake |
| --- | --- | --- |
| Language | C (also C++ and F90 interfaces) | C++ |
| Interface
 | Callback functions (user must provide) | Epetra data types |
| Package dependencies | None | Zoltan, Epetra, Teuchos |
| Features | Partitioning,
Coloring,
Ordering,
Dist. data directory,
Unstr. Comm. Lib. | Partitioning,
Coloring,
Ordering,

Data redistribution |

**Zoltan**

**Isorropia**

## How to configure/build

- Simply enable the package you want:
- ../configure –enable-zoltan
- ../configure –enable-isorropia
- Note: Isorropia will enable Zoltan (required dep.)
- Both Zoltan and Isorropia can use select 3rd party partitioning libraries (optional)
- ParMetis
- PT-Scotch (new!)
- Patoh
- Specify TPL as configure option
- ../configure –enable-zoltan –with-parmetis

## Work in Progress (10.0)

- Geometric partitioning in Isorropia
- Support load-balancing for mesh and particles
- Interface: MultiVector
- 2D matrix partitioning
- Reduce communication by non-row-based partition
- Resulting matrix can still be stored as CrsMatrix
- Create 1-1 maps from overlapping maps
- Application: FEM code where assembly map is overlapping but we need 1-1 solver map
- Symmetrize matrix for graph partitioning

## The End

## Isorropia

- Tool to create better maps
- Produce maps for better load balance and optimized communication
- 4 different maps for 2D objects (graphs, matrices):
- RowMap, ColumnMap, RangeMap, DomainMap
- Currently Isorropia performs row partitioning
- Novel 2D partitioning in progress

## Isorropia Example 

**// RCP is a smart pointer type in Teuchos.**
**RCP<const Epetra_CrsMatrix> matrix = ...**
**RCP<const Epetra_Vector> vec = ...**
**Teuchos::ParameterList paramlist; //Optionally set Zoltan parameters**
**// Create partitioner from matrix**
**RCP<Isorropia::Partitioner> partitioner = **
**	****Isorropia::Epetra::create_partitioner(matrix, paramlist); **
**//partitioner->compute_partitioning();**
**// Create redistributor from partitioner**
**Isorropia::Redistributor rd(partitioner); **
**// Create a balanced matrix from redistributor**
**RCP<Epetra_CrsMatrix> balanced_matrix = rd.redistribute(*matrix);**
**RCP<Epetra_Vector> balanced_vec = rd.redistribute(*vec);**