Zoltan User's Guide  |  Next  |  Previous

Octree Partitioning (OCTPART)

The Octree Partitioning algorithm is based upon work in load balancing for parallel mesh generation at Rensselaer Polytechnic Institute [Flaherty, Loy et al.]. It was implemented in Zoltan by Luis Gervasio, Department of Computer Science, Rensselaer Polytechnic Institute, as his summer project in 1998 [Gervasio]. An octree is a spatial decomposition of the computational domain in which the root of the tree, representing the entire domain, is recursively divided by two in each coordinate direction (producing eight or four "child" octants in 3D or 2D, respectively) until each subregion holds at most an application-specified number of objects. These subregions are represented by the leaves of the octree. The octree data structure is widely used in mesh generation and adaptive mesh refinement [Baehmann et al., Shephard and Georges]. The octree resulting from such a spatial decomposition of the domain can be used to partition an application's work [Edwards, Pilkington and Baden, Warren and Salmon]. To partition an octree, a traversal of the tree is used to define a global ordering on the leaves of the octree. This global ordering is often referred to as a Space-Filling Curve (SFC). The leaves of the octree can be easily assigned to processors in a manner which equally distributes work by assigning slices of the ordered list to processors. Different tree-traversal algorithms produce different global orderings or SFCs, with some SFCs having better connectivity and partition quality properties than others. Currently, Morton Indexing (i.e., Z-curve), Grey Code, and Hilbert SFCs are supported. Morton Indexing and Grey Code SFCs are the simplest (and currently, the fastest) of the SFC algorithms, but they produce lower-quality partitions than the Hilbert SFC.
 
Method String: OCTPART
Parameters:
    OCT_DIM Specifies whether the 2D or 3D Octree algorithms should be used. The 3D algorithms can be used for 2D problems, but much memory will be wasted to allow for a non-existent third dimension. Similarly, a 2D algorithm can be used for 3D surface meshes provided that the surface can be projected to the xy-plane without overlapping points. 
2 = use 2D algorithm; 3 = use 3D algorithm.
    OCT_METHOD The SFC to be used. 
0 = Morton Indexing; 1 = Grey Code; 2 = Hilbert.
    OCT_MINOBJECTS The minimum number of objects to allow in a leaf octant of the octree. These objects will be assigned as a group to a processor, so this parameter helps define the granularity of the load-balancing problem. Values greater than or equal to one are allowable.
    OCT_MAXOBJECTS The maximum number of objects to allow in a leaf octant of the octree. These objects will be assigned as a group to a processor, so this parameter helps define the granularity of the load-balancing problem. Values greater than or equal to one are allowable.
    OCT_OUTPUT_LEVEL Amount of output the load-balancing algorithm should produce. 
0 = no statistics; 1 = statistics summary; 2 = debugging information; 3 = data for generating plots.
Default:
OCT_DIM = 3
OCT_METHOD = 2
OCT_MINOBJECTS = 10
OCT_MAXOBJECTS = 40
OCT_OUTPUT_LEVEL = 0
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:  Ordering   |  Previous:   ParKway  |  Privacy and Security]