Zoltan User's Guide: RCB

Zoltan User's Guide | Next | Previous

Recursive Coordinate Bisection (RCB)

An implementation of Recursive Coordinate Bisection (RCB) due to Steve Plimpton of Sandia National Laboratories is included in Zoltan. RCB was first proposed as a static load-balancing algorithm by Berger and Bokhari, but is attractive as a dynamic load-balancing algorithm because it implicitly produces incremental partitions. In RCB, the computational domain is first divided into two regions by a cutting plane orthogonal to one of the coordinate axes so that half the work load is in each of the sub-regions. The splitting direction is determined by computing in which coordinate direction the set of objects is most elongated, based upon the geometric locations of the objects. The sub-regions are then further divided by recursive application of the same splitting algorithm until the number of sub-regions equals the number of processors. Although this algorithm was first devised to cut into a number of sets which is a power of two, the set sizes in a particular cut needn't be equal. By adjusting the part sizes appropriately, any number of equally-sized sets can be created. If the parallel machine has processors with different speeds, sets with nonuniform sizes can also be easily generated. The Zoltan implementation of RCB has several parameters which can be modified by the Zoltan_Set_Param function. A recent feature is that RCB allows multiple weights; that is, one can balance with respect to several load criteria simultaneously. Note that there is no guarantee that a desired load balance tolerance can be achieved using RCB, especially in the multiconstraint case.

Information about the sub-regions generated by RCB can be obtained by an application through calls to Zoltan_RCB_Box. This function is not required to perform load balancing; it only provides auxiliary information to an application.

Method String: RCB

Parameters:

    RCB_OVERALLOC The amount by which to over-allocate temporary storage arrays for objects within the RCB algorithm when additional storage is due to changes in processor assignments.
1.0 = no extra storage allocated; 1.5 = 50% extra storage; etc.

    RCB_REUSE Flag to indicate whether to use previous cuts as initial guesses for the current RCB invocation.
0 = don't use previous cuts; 1 = use previous cuts.

   RCB_OUTPUT_LEVEL Flag controlling the amount of timing and diagnostic output the routine produces.
0 = no output; 1 = print summary; 2 = print data for each processor.

   CHECK_GEOM Flag controlling the invocation of input and output error checking.
0 = don't do checking; 1 = do checking.

   KEEP_CUTS Should information about the cuts determining the RCB decomposition be retained? It costs a bit of time to do so, but this information is necessary if application wants to add more objects to the decomposition via calls to Zoltan_LB_Point_PP_Assign or to Zoltan_LB_Box_PP_Assign.
0 = don't keep cuts; 1 = keep cuts.

   AVERAGE_CUTS When set to one, coordinates of RCB cutting planes are computed to be the average of the coordinates of the closest object on each side of the cut. Otherwise, coordinates of cutting planes may equal those of one of the closest objects.
0 = don't average cuts; 1 = average cuts.

   RCB_LOCK_DIRECTIONS Flag that determines whether the order of the directions of the cuts is kept constant after they are determined the first time RCB is called.
0 = don't lock directions; 1 = lock directions.

   RCB_SET_DIRECTIONS If this flag is set, the order of cuts is changed so that all of the cuts in any direction are done as a group. The number of cuts in each direction is determined and then the value of the parameter is used to determine the order that those cuts are made in. When 1D and 2D problems are partitioned, the directions corresponding to unused dimensions are ignored.
0 = don't order cuts; 1 = xyz; 2 = xzy; 3 = yzx; 4 = yxz; 5 = zxy; 6 = zyx;

   RCB_RECTILINEAR_BLOCKS Flag controlling the shape of the resulting regions. If this option is specified, then when a cut is made, all of the dots located on the cut are moved to the same side of the cut. The resulting regions are then rectilinear. When these dots are treated as a group, then the resulting load balance may not be as good as when the group of dots is split by the cut.
0 = move dots individually; 1 = move dots in groups.

   REDUCE_DIMENSIONS When a 3 dimensional geometry is almost flat, it may make more sense to treat it as a 2 dimensional geometry when applying the RCB algorithm. In this case, a 2 dimensional RCB calculation is applied to a plane that corresponds with the geometry. (This results in cuts that, while still orthogonal, may no longer be axis aligned.) If this parameter is set to 1, a 3 dimensional geometry will be treated as 2 dimensional if it is very flat, or 1 dimensional if it is very thin. A 2 dimensional geometry will be treated as 1 dimensional if it is very thin.

   DEGENERATE_RATIO If the REDUCE_DIMENSIONS parameter is set, then this parameter determines when a geometry is considered to be degenerate. A bounding box which is oriented to the geometry is constructed, and the lengths of its sides are tested against a ratio of 1 : DEGENERATE_RATIO.

   RCB_RECOMPUTE_BOX Flag indicating whether the bounding box of set of parts is recomputed at each level of recursion. By default, the longest direction of the bounding box is cut during bisection. Recomputing the bounding box at each level of recursion can produce more effective cut directions for unusually shaped geometries; the computation does, however, take additional time and communication, and may cause cut directions to vary from one invocation of RCB to the next.
0 = don't recompute the bounding box; 1 = recompute the box.

   OBJ_WEIGHTS_COMPARABLE
In the multiconstraint case, are the object weights comparable? Do they have the same units and is the scaling meaningful? For example, if the jth weight corresponds to the expected time in phase j (measured in seconds), set this parameter to 1. (0 = incomparable, 1 = comparable)

   RCB_MULTICRITERIA_NORM
Norm used in multicriteria algorithm; this determines how to balance the different weight constraints. Valid values are 1,2, and 3. Roughly, if the weights correspond to different phases, then the value 1 (1-norm) tries to minimize the total time (sum over all phases) while the value 3 (max-norm) attempts to minimize the worst imbalance in any phase. The 2-norm does something in between. Try a different value if you're not happy with the balance.

   RCB_MAX_ASPECT_RATIO
Maximum allowed ratio between the largest and smallest side of a subdomain. Must be > 1.

Default:

RCB_OVERALLOC = 1.2

RCB_REUSE = 0

RCB_OUTPUT_LEVEL = 0

CHECK_GEOM = 1

KEEP_CUTS = 0

AVERAGE_CUTS = 0

RCB_LOCK_DIRECTIONS = 0

REDUCE_DIMENSIONS = 0

DEGENERATE_RATIO = 10

RCB_SET_DIRECTIONS = 0

RCB_RECTILINEAR_BLOCKS = 0

RCB_RECOMPUTE_BOX = 0

OBJ_WEIGHTS_COMPARABLE = 0

RCB_MULTICRITERIA_NORM = 1

RCB_MAX_ASPECT_RATIO = 10

Required Query Functions:

ZOLTAN_NUM_OBJ_FN

ZOLTAN_OBJ_LIST_FN

ZOLTAN_NUM_GEOM_FN

ZOLTAN_GEOM_MULTI_FN or ZOLTAN_GEOM_FN

C:	int Zoltan_RCB_Box ( struct Zoltan_Struct * zz, int part, int ndim, double xmin, double ymin, double zmin, double xmax, double ymax, double *zmax);
FORTRAN:	FUNCTION Zoltan_RCB_Box(zz, part,ndim, xmin, ymin, zmin, xmax, ymax, zmax) INTEGER(Zoltan_INT) :: Zoltan_RCB_Box TYPE(Zoltan_Struct), INTENT(IN) :: zz INTEGER(Zoltan_INT), INTENT(IN) :: part INTEGER(Zoltan_INT), INTENT(OUT) :: ndim REAL(Zoltan_DOUBLE), INTENT(OUT) :: xmin, ymin, zmin, xmax, ymax, zmax

In many settings, it is useful to know a part's bounding box generated by RCB. This bounding box describes the region of space assigned to a given part. Given an RCB decomposition of space and a part number, Zoltan_RCB_Box returns the lower and upper corners of the region of space assigned to the part. To use this routine, the parameter KEEP_CUTS must be set to TRUE when the decomposition is generated. This parameter will cause the sequence of geometric cuts to be saved, which is necessary for Zoltan_RCB_Box to do its job.

Arguments:
zz	Pointer to the Zoltan structure created by Zoltan_Create.
part	Part number of part for which the bounding box should be returned.
ndim	Upon return, the number of dimensions in the partitioned geometry.
xmin, ymin, zmin	Upon return, the coordinates of the lower extent of bounding box for the part. If the geometry is two-dimensional, zmin is -DBL_MAX. If the geometry is one-dimensional, ymin is -DBL_MAX.
xmax, ymax, zmax	Upon return, the coordinates of the upper extent of bounding box for the part. If the geometry is two-dimensional, zmax is DBL_MAX. If the geometry is one-dimensional, ymax is DBL_MAX.
Returned Value:
int	Error code.

[Table of Contents | Next: Recursive Inertial Bisection (RIB) | Previous: Geometric (Coordinate-based) Partitioners | Privacy and Security]

Method String:	RCB
Parameters:
RCB_OVERALLOC	The amount by which to over-allocate temporary storage arrays for objects within the RCB algorithm when additional storage is due to changes in processor assignments. 1.0 = no extra storage allocated; 1.5 = 50% extra storage; etc.
RCB_REUSE	Flag to indicate whether to use previous cuts as initial guesses for the current RCB invocation. 0 = don't use previous cuts; 1 = use previous cuts.
RCB_OUTPUT_LEVEL	Flag controlling the amount of timing and diagnostic output the routine produces. 0 = no output; 1 = print summary; 2 = print data for each processor.
CHECK_GEOM	Flag controlling the invocation of input and output error checking. 0 = don't do checking; 1 = do checking.
KEEP_CUTS	Should information about the cuts determining the RCB decomposition be retained? It costs a bit of time to do so, but this information is necessary if application wants to add more objects to the decomposition via calls to Zoltan_LB_Point_PP_Assign or to Zoltan_LB_Box_PP_Assign. 0 = don't keep cuts; 1 = keep cuts.
AVERAGE_CUTS	When set to one, coordinates of RCB cutting planes are computed to be the average of the coordinates of the closest object on each side of the cut. Otherwise, coordinates of cutting planes may equal those of one of the closest objects. 0 = don't average cuts; 1 = average cuts.
RCB_LOCK_DIRECTIONS	Flag that determines whether the order of the directions of the cuts is kept constant after they are determined the first time RCB is called. 0 = don't lock directions; 1 = lock directions.
RCB_SET_DIRECTIONS	If this flag is set, the order of cuts is changed so that all of the cuts in any direction are done as a group. The number of cuts in each direction is determined and then the value of the parameter is used to determine the order that those cuts are made in. When 1D and 2D problems are partitioned, the directions corresponding to unused dimensions are ignored. 0 = don't order cuts; 1 = xyz; 2 = xzy; 3 = yzx; 4 = yxz; 5 = zxy; 6 = zyx;
RCB_RECTILINEAR_BLOCKS	Flag controlling the shape of the resulting regions. If this option is specified, then when a cut is made, all of the dots located on the cut are moved to the same side of the cut. The resulting regions are then rectilinear. When these dots are treated as a group, then the resulting load balance may not be as good as when the group of dots is split by the cut. 0 = move dots individually; 1 = move dots in groups.
REDUCE_DIMENSIONS	When a 3 dimensional geometry is almost flat, it may make more sense to treat it as a 2 dimensional geometry when applying the RCB algorithm. In this case, a 2 dimensional RCB calculation is applied to a plane that corresponds with the geometry. (This results in cuts that, while still orthogonal, may no longer be axis aligned.) If this parameter is set to 1, a 3 dimensional geometry will be treated as 2 dimensional if it is very flat, or 1 dimensional if it is very thin. A 2 dimensional geometry will be treated as 1 dimensional if it is very thin.
DEGENERATE_RATIO	If the REDUCE_DIMENSIONS parameter is set, then this parameter determines when a geometry is considered to be degenerate. A bounding box which is oriented to the geometry is constructed, and the lengths of its sides are tested against a ratio of 1 : DEGENERATE_RATIO.
RCB_RECOMPUTE_BOX	Flag indicating whether the bounding box of set of parts is recomputed at each level of recursion. By default, the longest direction of the bounding box is cut during bisection. Recomputing the bounding box at each level of recursion can produce more effective cut directions for unusually shaped geometries; the computation does, however, take additional time and communication, and may cause cut directions to vary from one invocation of RCB to the next. 0 = don't recompute the bounding box; 1 = recompute the box.
OBJ_WEIGHTS_COMPARABLE	In the multiconstraint case, are the object weights comparable? Do they have the same units and is the scaling meaningful? For example, if the jth weight corresponds to the expected time in phase j (measured in seconds), set this parameter to 1. (0 = incomparable, 1 = comparable)
RCB_MULTICRITERIA_NORM	Norm used in multicriteria algorithm; this determines how to balance the different weight constraints. Valid values are 1,2, and 3. Roughly, if the weights correspond to different phases, then the value 1 (1-norm) tries to minimize the total time (sum over all phases) while the value 3 (max-norm) attempts to minimize the worst imbalance in any phase. The 2-norm does something in between. Try a different value if you're not happy with the balance.
RCB_MAX_ASPECT_RATIO	Maximum allowed ratio between the largest and smallest side of a subdomain. Must be > 1.
Default:
	RCB_OVERALLOC = 1.2
	RCB_REUSE = 0
	RCB_OUTPUT_LEVEL = 0
	CHECK_GEOM = 1
	KEEP_CUTS = 0
	AVERAGE_CUTS = 0
	RCB_LOCK_DIRECTIONS = 0
	REDUCE_DIMENSIONS = 0
	DEGENERATE_RATIO = 10
	RCB_SET_DIRECTIONS = 0
	RCB_RECTILINEAR_BLOCKS = 0
	RCB_RECOMPUTE_BOX = 0
	OBJ_WEIGHTS_COMPARABLE = 0
	RCB_MULTICRITERIA_NORM = 1
	RCB_MAX_ASPECT_RATIO = 10
Required Query Functions:
	ZOLTAN_NUM_OBJ_FN
	ZOLTAN_OBJ_LIST_FN
	ZOLTAN_NUM_GEOM_FN
	ZOLTAN_GEOM_MULTI_FN or ZOLTAN_GEOM_FN