In computer science, parallel tree contraction is a broadly applicable technique for the parallel solution of a large number of tree problems, and is used as an algorithm design technique for the design of a large number of parallel graph algorithms. Parallel tree contraction was introduced by Gary L. Miller and John H. Reif, and has subsequently been modified to improve efficiency by X. He and Y. Yesha, Hillel Gazit, Gary L. Miller and Shang-Hua Teng and many others. Tree contraction has been used in designing many efficient parallel algorithms, including expression evaluation, finding lowest common ancestors, tree isomorphism, graph isomorphism, maximal subtree isomorphism, common subexpression elimination, computing the 3-connected components of a graph, and finding an explicit planar embedding of a planar graph Based on the research and work on parallel tree contraction, various algorithms have been proposed targeting to improve the efficiency or simplicity of this topic. This article hereby focuses on a particular solution, which is a variant of the algorithm by Miller and Reif, and its application.
Introduction Over the past several decades there has been significant research on deriving new parallel algorithms for a variety of problems, with the goal of designing highly parallel (polylogarithmic depth), work-efficient (linear in the sequential running time) algorithms. For some problems, tree turns out to be a nice solution. Addressing these problems, we can sometimes get more parallelism simply by representing our problem as a tree. Considering a generic definition of a tree, there is a root vertex, and several child vertices attached to the root. And the child vertices might have children themselves, and so on so forth. Eventually, the paths come down to leaves, which are defined to be the terminal of a tree. Then based on this generic tree, we can further come up with some special cases: (1) balanced binary tree; (2) linked list. A balanced binary tree has exactly two branches for each vertex except for leaves. This gives a O(log n) bound on the depth of the tree. A linked list is also a tree where every vertex has only one child. We can also achieve O(log n) depth using symmetry breaking. Given the general case of a tree, we would like to keep the bound at O(log n) no matter it is unbalanced or list-like or a mix of both. To address this problem, we make use of an algorithm called prefix sum by using the Euler tour technique. With the Euler tour technique, a tree could be represented in a flat style, and thus prefix sum could be applied to an arbitrary tree in this format. In fact, prefix sum can be used on any set of values and binary operation which form a group: the binary operation must be associative, every value must have an inverse, and there exists an identity value. With a bit of thought, we can find some exceptional cases where prefix sum becomes incapable or inefficient. Consider the example of multiplication when the set of values includes 0. Or there are some commonly desired operations are max() and min() which do not have inverses. The goal is to seek an algorithm which works on all trees, in expected O(n) work and O(log n) depth. In the following sections, a Rake/Compress algorithm will be proposed to fulfill this goal.
Definitions
Before going into the algorithm itself, we first look at a few terminologies that will be used later.
Rake – Rake step joins every left leaf of binary nodes to the parent. By join, we mean that it undergoes a functional process which achieves the operation we want to make. An example of rake is given in Figure 1. Compress – Compress step is actually a sequence of several events: (1) Find an independent set of unary nodes. (Independence here is defined such that no two are neighbors, meaning no parent to child relation) (2) Join each node in independent set with its child (Note that independent set is not unique). An example of compress is given in Figure 2. And in order to solve actual problems using tree contraction, the algorithm has a structure:
Repeat until tree becomes a unary node { Rake; Compress; }
Analysis For the moment, let us assume that all nodes have less than three children, namely binary. Generally speaking, as long as the degree is bounded, the bounds will hold. But we will analyze the binary case for simplicity. In the two “degenerate” cases listed above, the rake is the best tool for dealing with balanced binary trees, and compress is the best for linked lists. However, arbitrary trees will have to require a combination of these operations. By this combination, we claim a theorem that
Theorem: After O(log n) expected rake and compress steps, a tree is reduced to a single node. Now rephrase the tree contraction algorithm as follows:
Input: A binary tree rooted at r Output: A single node Operation: A sequence of contraction steps, each consisting of a rake operation and a compress operation (in any order). The rake operation removes all the leaf nodes in parallel. The compress operation finds an independent set of unary nodes and splice out the selected nodes. To approach the theorem, we first take a look at a property of a binary tree. Given a binary tree T, we can partition the nodes of T into 3 groups: T 0 {\displaystyle T_{0}} contains all leaf nodes, T 1 {\displaystyle T_{1}} contains all nodes with 1 child, and T 2 {\displaystyle T_{2}} contains all nodes with 2 children. It is easy to see that: V ( T ) = T 0 ∪ T 1 ∪ T 2 {\displaystyle V(T)=T_{0}\cup T_{1}\cup T_{2}} . Now we propose:
… excerpt ends here. Continue reading the full article.
