   Next: 7 Graph algorithms Up: Communication-Efficient Parallel Algorithms Previous: 5 Tree contraction

# 6 Treefix computations

This section presents a generalization of the parallel prefix computation to binary trees. We present two kinds of treefix computations--rootfix and leaffix--and show how they can be implemented by an -step conservative algorithm that uses space, where n is the number of nodes in the input tree. As we shall see in Section 7, treefix computations can greatly simplify the description of many parallel graph algorithms in the literature, and moreover, treefix computations can be performed by conservative algorithms.

We begin with a definition of treefix computation. Definition. Let be a domain with a binary associative operation and an identity . Let T be a rooted, binary tree in which each vertex has an assigned input value . The rootfix problem is to compute for each vertex with parent j, the output value , where if i is the root. The leaffix problem is to compute for each vertex with left child j and right child k, the output value , where if i has no left child and if i has no right child. Simple examples of treefix problems are computing the depth of each vertex in a rooted binary tree and computing the size of each subtree. These and other examples appear in the next section.

Like the prefix computation on lists, treefix computations can be performed directly on the contraction tree. For simplicity, however, we describe a recursive version. Proof: Both treefix computations are performed by executing a single contraction step on the input tree T to produce a contracted tree . Each node in is assigned an input value, and the treefix computation is executed recursively on . The contracted tree is then expanded to yield T once again, and the output value of each node in T is computed from the input values of T and the output values of .

The algorithm for leaffix is based on each node i maintaining a value which has the form , where are elements of the domain, and the character `` '' represents symbolically a slot to be filled in with a value. The number of slots is equal to the number of children of the node, and each slot corresponds to a specific child. When a parent and child pair during the course of the leaffix algorithm, the value of the child is substituted into the corresponding slot in the value of its parent. For example, suppose node i pairs with its right child j, where the value of i is and the value of j is . The value of the merged node k is computed from and by substituting into the second slot in , yielding the value . The operations are carried out immediately so that has the proper form.

The leaffix algorithm initializes each node i by , , or depending on the number of children of node i. The algorithm then proceeds as follows. At the end of a contraction step, each node k in that results from the merging of parent i and child j computes its value by substituting into the appropriate slot of . The leaffix algorithm is then performed recursively on using the s values as inputs and yielding y values as output. (The y values contain no slots and are simply elements of the domain .) During the expansion step, the parent node i sets . Each child node j gets its output value by substituting the y values of its children into the slots of .

In the rootfix algorithm, each node i maintains a value , as in the leaffix algorithm, but each now has the general form , and the slot of a node corresponds to the node's parent. The rootfix algorithm initializes each node i by , except for the root r which performs . After the pairs have been determined for the contraction step, each node j that is the child in a pair, and which itself has a child, substitutes in the appropriate slot of its child's value. At the end of a contraction step, each node k in that resulted from the merging of parent i and child j computes its value by . The rootfix algorithm is then performed recursively on , yielding y values as output. During the expansion step, the parent node i sets . Each child node j gets its output value by substituting into the slot of .

The time and space bounds claimed in the theorem are apparent by inspection. Each step of a treefix algorithm adds only a constant amount of work to a corresponding step in the tree contraction and expansion algorithms. The additional space required by the treefix algorithms is the space per node for the x, y, and s values.

to .667emto .667em   Next: 7 Graph algorithms Up: Communication-Efficient Parallel Algorithms Previous: 5 Tree contraction

Bruce Maggs
Thu Jul 25 19:12:36 EDT 1996