Zoltan Developer's Guide  |  Next   |  Previous

Appendix: Refinement Tree

Overview of structure (algorithm)

The refinement tree based partitioning algorithm was developed and implemented by William Mitchell of the National Institute of Standards and Technology. It is similar to the Octree method except that it uses a tree representation of the refinement history instead of a geometry based octree. The method generates a space filling curve which is cut into K appropriately-sized pieces to define contiguous parts, where the size of a piece is the sum of the weights of the elements in that piece. K, the number of parts, is not necessarily equal to P, the number of processors. It is an appropriate load balancing method for grids that are generated by adaptive refinement when the refinement history is available. This implementation consists of two phases: the construction of the refinement tree, and the definition of the parts.

Refinement Tree Construction

The refinement tree consists of a root node and one node for each element in the refinement history. The children of the root node are the elements of the initial coarse grid. The children of all other nodes are the elements that were formed when the parent element was refined. Upon first invocation, the refinement tree is initialized. This creates the root node and initializes a hash table that maps global IDs into nodes of the refinement tree. It also queries the user for the elements of the initial grid and creates the children of the root node. Unless the user provides the order through which to traverse the elements of the initial grid, a path is determined through the initial elements along with the "in" vertex and "out" vertex of each element, i.e., the vertices through which the path passes to move from one element to the next. This path can be determined by a Hilbert space filling curve, Sierpinski space filling curve (triangles only), or an algorithm that attempts to make connected parts (connectivity is guaranteed for triangles and tetrahedra). The refinement tree is required to have all initial coarse grid elements, not just those that reside on the processor. However, this requirement is not imposed on the user; a communication step fills in the elements from other processors. This much of the tree persists throughout execution of the program. The remainder of the tree is reconstructed on each invocation of the refinement tree partitioner. The remainder of the tree is built through a tree traversal. At each node, the user is queried for the children of the corresponding element. If there are no children, the user is queried for the weight of the element. If there are children, the order of the children is determined such that a tree traversal produces a space filling curve. The user indicates what type of refinement was used to produce the children (bisection of triangles, quadrasection of quadrilaterals, etc.). For each supported type of refinement, a template based ordering is imposed. The template also maintains an "in" and "out" vertex for each element which are used by the template to determine the beginning and end of the space filling curve through the children. If the refinement is not among the types supported by templates, an exhaustive search is performed to find an appropriate order, unless the user provides the order.

Partition algorithm

The algorithm that determines the parts uses four traversals of the refinement tree. The first two traversals sum the weights in the tree. In the first traversal, each node gets the sum of the weights of all the descendant nodes that are assigned to this processor. The processors then exchange information to fill in the partial sums for the leaf elements that are not owned by this processor. (Note that an unowned leaf on one processor may be the root of a large subtree on another processor.) The second traversal completes the summation of the weights. The root now has the sum of all the weights, which, in conjunction with an array of relative part sizes, determines the desired weight of each part. Currently the array of part sizes are all equal, but in the future the array will be input to reflect heterogeneity in the system. The third traversal computes the partition by adding subtrees to a part until the size of the part meets the desired weight, and counts the number of elements to be exported. Finally, the fourth traversal constructs the export list.

Data structures

The implementation of the refinement tree algorithm uses three data structures which are contained in reftree/reftree.h. Zoltan_Reftree_data_struct is the structure pointed to by zz->LB.Data_Structure. It contains a pointer to the refinement tree root and a pointer to the hash table. Zoltan_Reftree_hash_node is an entry in the hash table. It consists of a global ID, a pointer to a refinement tree node, and a "next" pointer from which linked lists at each table entry are constructed to handle collisions. Zoltan_Reftree_Struct is a node of the refinement tree. It contains the global ID, local ID, pointers to the children, weight and summed weights, vertices of the element, "in" and "out" vertex, a flag to indicate if this element is assigned to this processor, and the new part number.


There are two parameters. REFTREE_HASH_SIZE determines the size of the hash table. REFTREE_INITPATH determines which algorithm to use to find a path through the initial elements. Both are set by Zoltan_Reftree_Set_Param in the file reftree/reftree_build.c.

Main routine

The main routine is Zoltan_Reftree_Part in file reftree/reftree_part.c.

[Table of Contents  |  Next:   Hilbert Space-Filling Curve (HSFC)Previous:  Hypergraph Partitioning  |  Privacy and Security]