The HSFC partitioning algorithm seeks to divide [0,1] into P intervals each containing the same weight of objects associated to these intervals by their inverse Hilbert coordinates. N bins are created (where N > P) to partition [0,1]. The weights in each bin are summed across all processors. A greedy algorithm sums the bins (from left to right) placing a cut when the desired weight for current part interval is achieved. This process is repeated as needed to improve partitioning tolerance by a technique that maintains the same total number of bins but refines the bins previously containing a cut.
HSFC returns an warning if the final imbalance exceeds the user specified tolerance.
This code implements both the point assign and box assign functionality. The point assign determines an appropriate part (associated with a specific group of processors) for a new point. The box assign determines the list of processors whose associated subdomains intersect the given box. In order to use either of these routines, the user parameter KEEP_CUTS must be turned on. Both point assign and box assign now work for points or boxes anywhere in space even if they are exterior to the original bounding box. If a part is empty (due to the part being assigned zero work), it is not included in the list of parts returned by box assign. Note: the original box assign algorithm was not rigorous and may have missed parts. This version is both rigorous and fast.
The Zoltan implementation of HSFC has one parameter that can be modified by the Zoltan_Set_Param function.
This partitioning algorithm is loosely based on the 2D & 3D Hilbert tables used in the Octree partitioner and on the BSFC partitioning implementation by Andrew C. Bauer, Department of Engineering, State University of New York at Buffalo, as his summer project at SNL in 2001. The box assign algorithm is loosely based on the papers by Lawder referenced both in the developers guide and the code itself. NOTE: This code can be trivially extended to any space filling curve by providing the tables implementing the curve's state transition diagram. The only dependance on the curve is through the tables and the box assign algorithm will work for all space filling curves (if we have their tables.)
Please refer to the Zoltan Developers Guide,
Appendix: Hilbert Space Filling Curve (HSFC)
for more detailed information about these algorithms.
| Method String: | HSFC |
| Parameters: | |
| KEEP_CUTS | Information about cuts and bounding box is necessary
if the 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. |
| 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 HSFC 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 is very flat, or 1 dimensional if it very thin. And a 2 dimensional geometry will be treated as 1 dimensional if it is very thin. Turning this parameter on removes the possibility that disconnected parts will appear on the surface of a flat 3 dimensional object. |
| DEGENERATE_RATIO | If the REDUCE_DIMENSIONS parameter is set, then this parameter determines when a geometry is considered to be flat. 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: | |
| KEEP_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 |