Recursive Coordinate Bisection (RCB)

RCB Algorithm Overview

Recursive coordinate bisection (RCB) is a parallel geometric partitioning algorithm. Geometric coordinates are first partitioned into two balanced parts. Partitioning continues recursively in each part until the desired number of balanced parts has been created.

Coordinates can be weighted, in which case the total weight in each part is balanced, rather than the number of coordinates in each part.

Relative part sizes may be specified. If part sizes are specified, then the total weight or total number of objects in each part instead of being evenly balanced will respect the relative part sizes required.

Input

RCB expects a Zoltan2::CoordinateInput object. This class supports geometric coordinates of arbitrary dimension, with weights of arbritrary dimension. If weights are not provided, RCB assumes coordinates are equally weighted.

If weights of dimension greater than one are provided, then the partitioning_objective parameter must be set to specify how the multiple weights per coordinate should be interpreted.

Parameters

The following parameters are used by the RCB algorithm:

• partitioning_objective (default is balance_object_weights )
• imbalance_tolerance (default is 1.1 )
• rectilinear_blocks (default is no )
• average_cuts (default is no )
• bisection_num_test_cuts (default is 1 )

The parameter bisection_num_test_cuts determines how many cuts are made at each step when seeking the bisector. For very irregularly distributed data, a high value may speed the time to find the bisector. For uniformly distributed coordinates, this value should be set to one. For high values, larger messages are exchanged at each step to find the bisector, but there are fewer total steps.

Solution

An RCB solution is a list of global IDs with a corresponding list of part numbers and process ranks.

Quality measures

RCB quality is measured with an imbalance measure. Use the parameter compute_metrics if you want the Zoltan2::PartitioningProblem to compute imbalance metrics for the solution.

Examples

See rcb_C.cpp for and example of using the RCB algorithm.

Source

Zoltan2_AlgRCB.hpp is the source file for RCB.