Zoltan User's Guide  |  Next  |  Previous

Recursive Inertial Bisection (RIB)

An implementation of Recursive Inertial Bisection (RIB) is included in Zoltan. RIB was proposed as a load-balancing algorithm by Williams and later studied by Taylor and Nour-Omid, but its origin is unclear. RIB is similar to RCB in that it divides the domain based on the location of the objects being partitioned by use of cutting planes. In RIB, the computational domain is first divided into two regions by a cutting plane orthogonal to the longest direction of the domain so that half the work load is in each of the sub-regions. 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 RIB has several parameters which can be modified by the Zoltan_Set_Param function.

RIB currently does not support multiple vertex weights. For such cases, use RCB instead.


 
Method String: RIB
Parameters:
    RIB_OVERALLOC The amount by which to over-allocate temporary storage arrays for objects within the RIB algorithm when additional storage is due to changes in processor assignments. 
1.0 = no extra storage allocated; 1.5 = 50% extra storage; etc.
   RIB_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 RIB 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 RIB 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.
   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 RIB algorithm. (Coordinate values in the omitted direction are ignored for the purposes of partitioning.) 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.
Default:
RIB_OVERALLOC = 1.2
RIB_OUTPUT_LEVEL = 0
CHECK_GEOM = 1
KEEP_CUTS = 0
AVERAGE_CUTS = 0
REDUCE_DIMENSIONS = 0
DEGENERATE_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

[Table of Contents  | Next:  Hilbert Space-Filling Curve Partitioning |  Previous:  Recursive Coordinate Bisection (RCB)  |  Privacy and Security]