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.
Parameters
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]