Computer Science
ComputerScience,1970-2008-Computer Science-1991.jsonl.gz.gz
Computer Science
8f8a1e5c3927db60969bc8b580bbe9758aad8873
Communication complexity for parallel divide-and-conquer

The relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors is studied. The parallel computation cost is the maximal number of the D&C nodes that any processor in the parallel system may expand, whereas the communication cost is the total number of cross nodes (nodes generated by one processor but expanded by another processor). A scheduling algorithm is proposed, and lower bounds on the communication cost are derived. The proposed scheduling algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal.<<ETX>>


Introduction
Divide and conquer (D&C) is a common computation paradigm, in which the solution to a problem is obtained by solving subproblems recursively. Examples of D&C computations include various sorting methods such as quick sort [6], computational geometry procedures such as convex hull calculation [12], AI search heuristics such as constraint satisfaction techniques [5], adaptive data classification procedures such as generation and maintenance of quadtrees [13], and numerical methods such as multigrid algorithms [10] for solving partial differential equations.
A D&C computation can be viewed as a process of expanding and shrinking a tree. Each node in the tree corresponds to a problem instance, and children of the node correspond to its subproblems. During the computation, each internal (non-leaf) node goes through two phases. The first phase is the divide phase during which the problem instance associated with the node is divided into subproblems. The second phase is the combine phase during which the solution of the problem instance associated with the node is derived by combining solutions of the subproblems associated with the node's children. After its creation each leaf will perform some computation and return the results to its parent. At a given time, nodes on a wavefront that cuts across all paths from the root to leaves can be active in performing divide, combine, or compute operations. Along each path the wavefront first moves down from the root to its leaf and then up from the leaf to the root.
At first glance, one might think that it should be straightforward to perform D&C in parallel, because nodes on the wavefront can all be processed independently. However, if one wants to achieve good load balancing between the processors, then parallelizing D&C becomes nontrivial. In fact, doing efficient D&C on any real parallel machine has been a major challenge to researchers [3,4,9,14] for many years.
The difficulties are due to the fact that many D&C computations are highly dynamic in the sense that these computations are data-dependent. During computation, a problem instance can be expanded into any number of subproblems depending on the data that have been computed so far. In fact, the trees of many D&C computations can be expected to be sparse and irregular, and as a result, load balancing must be adaptive to the tree structure and must be done dynamically at run time. This implies that computation loads need to be moved around between processors during computation. The challenge is then to devise efficient scheduling algorithms which can achieve good load balancing while minimizing the communication cost for moving computations around.
In general there is a tradeoff between balancing computation loads and minimizing communication costs. The results of this paper quantify this tradeoff. In particular, the paper establishes lower bounds on the communication cost for any scheduling algorithm based on how well it performs load balancing.

Definitions and Notation
The tree of a D&C computation is called a (N,h,d)

-tree, if
• N is the number of nodes in the tree, • h is the height of the tree, and • d is the maximal number of children of a node. (We assume that d is at least 2, to allow parallel processing of the tree.) A node is said to be at tree level i if it is the z-th node on the path from the root to the node. Therefore, the root is at level 1, and the height of the tree is the maximal level number. For the parallel system which will carry out the D&C computation, we assume that • p is the number of processors in the system, and • it takes one time step for a processor to expand a node, i.e., to perform the divide operation for an internal node, or to perform the compute operation for a leaf node. For simplicity, we assume that a processor takes no time to perform a combine operation.
When a node is expanded, zero or more children may be generated. More precisely, if a node does not generate any children, the node is a leaf; If a node generates one or more (up to d) children, the node is an internal node. Each newly generated node will in turn be expanded by some processor in the future. A frontier node is a node which has been generated but has not been expanded.
A scheduling algorithm for a D&C computation schedules nodes (i.e., frontier nodes) on processors for expansion. We assume that scheduling algorithms cannot "lookahead". This non-lookahead assumption is reasonable when dealing with irregular D&C trees. In this type of tree, the number of children a parent may have (if any) is typically data-dependent and is therefore not known a priori.
The parallel computation cost T^(H) of a scheduling algorithm A for a D&C computation tree H is the maximum number of the nodes that any processor may expand. Since there are N nodes and p processors, a lower bound on TA(H) is T mtn = \N/p\.
The parallel computation cost T4 of algorithm A is defined as the maximum TA(H) for all (JV, h, d)-trees H.
The communication cost CA{H) of a scheduling algorithm A for a D&C computation tree H is the total number of cross nodes. A cross node is a node which is generated by one processor but expanded by another processor. Note that the processor expanding a cross node needs to receive information from the processor generating the node. Therefore, CA ( Many D&C computations are expected to satisfy restrictions SI and S2. Since TV is usually an exponential function of /i, restriction Si is easily satisfied in these cases. Restriction S2 roughly requires that N < d h~2 /ph. If a tree is perfectly balanced and each node has exactly d children, then TV would be Q(d h~1 ) instead. A perfectly balanced tree is easy for load balancing because the subtrees of each node have the same computation load. Restrictions SI and S2 basically capture those interesting D&C computations with irregular trees. This class of D&C computations are exactly those for which one finds it difficult to achieve good load balancing without paying much in communication overheads. The lower bound on CA{H), stated in P2 of the theorem, provides an explanation of why this must be the case.
The two properties PI and P2 in Theorem 1 can be expressed in terms of the quantities TV, A, d (associated with the D&C tree) and p (associated with the parallel system) as follows. ) From this and the fact that N' < N and h' < A, we note that A^and h 1 approach N and h respectively, when both e;v and e^ approach 0. Therefore, PI and P2 in Theorem 1 become TA(H) = Q(N/p) and C^{H) = Vt{pdh) for large /*, when p' is close to p. Furthermore, we can slightly change the theorem as Corollary 1. Thus, if ^ < T4 < (l + er)~ (< ^zi)? the communication cost must be at least (1 -ec)CU. • Theorem 1 also implies an important tradeoff result: if a scheduling algorithm wants to achieve a good load balancing by parallel processing, then it must pay a high price in communication cost. We can express the tradeoff between T4 and CU explicitly by showing a lower bound on their product: T A • (CA + K). If (p* -1)AC < CU < p*>c, where 0 < < p, then by Theorem 1, T A must be at least N'/p*. Therefore, T A • (CU + /c) > (W/p*) • p*K = N'-K. Note that because of T A > JV/p > N'/p this tradeoff is also satisfied when CA > p/c. This tradeoff result is summarized in the following corollary.
Corollary 2 For any scheduling algorithm A for a parallel system of p processors, for all N, h, and d with restrictions SI and S2 as defined in Theorem 1, where N F and K are defined in Theorem 1.
Theorem 2 A scheduling algorithm A can be devised to have the property that the parallel computation cost is T A = T mtn and the communication cost is C A < C u (= pdh) for any The algorithm satisfying Theorem 2 has the minimum parallel computation cost. By Corollary 1, the algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal. These results also imply that the lower bound on T A • (C A + K) in Corollary 2 is tight when both e^v and Ch are arbitrarily close to 0.
Note that Theorems 1 and 2 are so formulated that their results are system-independent That is, the results are independent from the interconnection topology of the processors and various control overheads such as data structure maintenance and reading/writing messages. Therefore, our upper and lower bounds on C A are intrinsic to any parallel system. These bounds give insights into actual communication cost in a real implementation, but exactly how they are related to the actual cost is a separate matter depending on the implementation (see [15]). Section 3 describes the algorithm of Theorem 2. Section 4 presents a simplified version of Theorem 1 and its proof to help the reading of this paper. A complete proof of Theorem 1 is given in Section 5.

Relation to Past Work
There have been several approaches in performing parallel D&C. A simple approach (e.g., in [2]) is to expand all the nodes above a fixed level on one processor and then distribute nodes at this level to other processors. Load balancing would be done poorly in this approach when the tree is irregular. Another approach [14] is to distribute generated nodes, and to have each processor perform load balancing based on load status information from its neighbor processors. For this scheme, the communication cost can be very high in the worst case.
Recently, some researchers have made efforts to reduce communication overhead. A popular approach [4,9,16] is based on the "donate-highest-subtree" strategy, in which an idle processor will be given frontier nodes as near to the root as possible. Since a subtree rooted near the top usually has many nodes and these nodes can all be expanded locally, this strategy tends to reduce the amount of interprocessor communication. Ferguson and Korf [3] presented a D&C scheme with several processors scheduled first to a node and then to their children. The idea behind their scheme is also that of distributing frontier nodes near the root to idle processors.
Although the methods described in the previous paragraph all attempt to reduce communication overhead, they do not use global information to balance the load. It turns out that the communication cost for these methods can still be high in the worst case. For example, we estimate that the communication cost is 0(dh logdP ) for Ferguson and Korf's scheme, and is 0(mm(p 2 h,pdh 2 )) for the scheme in [4] with round-robin scheduling. In contrast, the communication cost for the scheduling algorithm of this paper (Section 3) is as low as 0(pdh) (Theorem 2). This is partly due to the fact that our algorithm is able to make effective use of global information (i.e., "global pool" in Section 3).
Most importantly, we note that none of the previous work has any lower bound results on the communication cost for parallel D&C computations. It appears that our lower bounds in Theorem 1 and Corollaries 1 and 2 are the first lower bound results for those D&C computations whose tree structures are dynamic in the sense that the tree structure is determined only at run time. Previous results on computation and communication cost tradeoffs such as those in [7,8,11] deal with only static computation graphs, whose topologies are known before the computation starts.

A Scheduling Algorithm and Upper Bounds
This section describes a new scheduling algorithm which can achieve the upper bounds in Theorem 2 for both parallel computation cost and communication cost. The bounds hold for any D&C computation, i.e., for any (TV, h,d)-tree no matter how irregular it is.

Proposed Scheduling Algorithm
The scheduling algorithm uses a data structure, called a Global Pool (abbr. CP), to keep track of frontier nodes at a particular tree level which have not been taken by any processor for expansion. This level, identified by a variable gl, has the property that nodes at higher levels have all been taken by processors. Every processor will try to take a node from the GP to work on whenever it becomes idle. For the proof of Theorem 2, it suffices to assume that the GP is maintained by some single processor. (See [15] for a distributed scheme where the GP is maintained by multiple processors.) Initially, the GP contains only the root and the value of gl is one. The GP becomes empty when all of its nodes at level gl have been taken by the processors. At this moment, all the processors are requested to send in their frontier nodes at level gl+1 in the next time step when all the nodes at level gl + 1 have been generated. Then the GP is filled with this set of new nodes, and gl is increased by one. This process is repeated until all the nodes have been expanded.
The key idea of this algorithm is what each processor will do after it has taken a node from the GP. The processor will do a depth-first traversal. Consequently, the processor can exhaust all possible work locally before asking for a new node from the GP. As a result, we can prove (below) that the communication cost can be as low as C u . While not related to parallel computation cost and communication cost, an important advantage of this local depth-first strategy is that it uses the minimum amount of memory.
In essence the scheduling algorithm described here uses a breadth-first scheme to distribute big chunks of computations to processors, and has each processor after receiving a computation follow the depth-first strategy locally. Therefore; the algorithm is a hybrid method, which interestingly will do a purely depth-first traversal of the tree in the case that only one processor is used.
Suppose that we define the parallel computation time to be the time (in terms of number of time steps) when the last node is expanded by a processor. Then the parallel computation time of the algorithm described here is at most \N/p + h~\. To see this, we note that some processors may become idle only when the number of nodes in the GP is smaller than the number of idle processors. In the worst case all the p processors may become idle at the end of some time step, but at this time there is only one node in the GP. Thus, in the next time step, as many as p -1 processors may be idle. This situation can happen at most h times. Therefore, in the entire D&C computation, additional h(p-1) nodes could have been expanded if there were no idle processors at any time step. This implies that the parallel computation time is at most Note that parallel computation time defined in the previous paragraph is different from parallel computation cost defined in Section 2.1. Being able to take into account processor waiting time induced by inter-node dependency, parallel computation time may be of more practical interest than parallel computation cost.
However, to prove Theorem 2, we need to establish an upper bound on the parallel computation cost of the algorithm. We will do this and also establish an upper bound on the communication cost of the algorithm. Proof of Theorem 2. To achieve the \N/p\ upper bound on parallel computation cost, we will need to add some fair scheduling feature to the algorithm described above. Whenever the number of nodes in the GP is smaller than the number of idle processors, we will select the active processors for the next time step from all the p processors in a fair way. That is, processors take turn to become active using a round-robin scheme. This ensures at the end of any time step that the total number of nodes expanded by a processor so far will not exceed that expanded by any other processor by more than one. Thus when all the N 6 nodes are expanded, each processor will have expanded at most \N/p\. This proves that the parallel computation cost of the scheduling algorithm with the fair scheduling feature is at most \N/p\. The communication cost of the algorithm is at most the number of frontier nodes entering the GP, as this represents the only interprocessor communication activity for the entire algorithm. Since by using depth-first search each processor has at most d local nodes at each level (as illustrated in Figure 1), the GP can collect at most pd nodes each time that gl increases. This will happen at most h times, so the total number of nodes entering the GP is bounded above by C u = pdh. • Note that in a practical implementation, the fair scheduling feature may not be used since minimizing parallel computation cost may not be important. Without the fair scheduling feature, the parallel computation cost would become \N/p+h~\. However, the communication cost can be reduced to p(d -if a processor right after expanding a node will schedule one child, if any, of the node for expansion at the next time step.
The scheduling algorithm described in this section is being used as a basis for developing a parallel programming model for D&C computations. To obtain practical insights, we plan to implement a programming system based on the model on the 26-host Nectar network system [1] developed at Carnegie Mellon University.

A Simplified Version of Theorem 1
This section presents Theorem 3 (see below), which is a simplified version of Theorem 1 dealing with only two processors. A relatively simple proof of Theorem 3 is given. This simple proof captures the essence of a more complicated proof of Theorem 1 given in Section 5. It is advised that the reader read this simple proof first to understand the ideas. Note that restrictions SI and S2 correspond to those in Theorem 1. Restriction S3 is for a minor technical convenience, namely, ensuring that h! an integer.
Theorem 3 implies, for example, that if the communication cost is small (in the sense that Q2 does not hold), then the parallel computation cost must be large (in the sense that Ql holds). In particular, if C A {H) < h'(d -1) and if 3dh <C N, then the parallel computation cost will be close to TV.
Proof of Theorem 3. Suppose that we are given a scheduling algorithm A for performing a D&C computation on processors Pi and P 2 . For algorithm A, we will prove the existence of a (JV, A,d)-tree H for which at least one of Ql and Q2 must hold.
By playing an adversary game with algorithm A, we will construct the tree by growing it from the root one step at a time. A time step consists of two phases, node scheduling phase and node expansion phase. In the node scheduling phase, algorithm A schedules a node or no node for each processor to execute. Then, in the node expansion phase, these scheduled nodes are expanded. In this phase we will determine the number of children each scheduled node will generate.
We will first define a special class of subtrees which will be used to describe some sufficient conditions under which a tree can grow to a (N, /i, d)-tree. We will then give the main part of the proof including a description of the tree construction procedure.

Definition 1 At any given time during the tree construction, a High-and-Full-Degree subtree (abbv. HFD-subtree) is a subtree, which is rooted at a node at or above level h -[log d N]
, and which has been constructed using the following rules:

A2. nodes at level h generate no children.
Note that rules Al and A2 imply that a node which is above level h and has no children must be a frontier node.

the degree of any node is at most d; and
14. the tree contains an HFD-subtree, then a construction procedure can be devised to grow the tree to a (N,h,d)-tree: Proof. We first note that in the HFD-subtree of 14 there exist nodes which are above level h and have no children. Otherwise, the subtree would have been "fully grown" to level h, according to rules Al and A2. Since its root is at and above level h -\log d AT], this fully grown HFD-subtree would have at least d^o gdN^( > N) nodes. This contradicts II. As noted above, those nodes in the current HFD-subtree which are above level h and have no children must all be frontier nodes.
Let Hi be the current tree. We will identify a set of "padding nodes" which can be added to Hi to make it a (N, h, d)-tree.
If Hi has height less than h or degree less than d, we will grow it by extending the current HFD-subtree from one of its frontier nodes which are above level h. Let v be this frontier node, as shown in Figure 2. We generate d children for v and create a path from i?toa node at level as shown in Figure 2 (a). The resulting tree, called H 2 , has height /i, degree d, and no more than (N -h -d) + d+h = N nodes.
If H2 has less than N nodes, we will pad it with nodes in the fully grown HFD-subtree which are reachable from the current frontier nodes and other padding nodes, as illustrated in Figure 2 (b). Since the fully grown HFD-subtree has at least N nodes, it has sufficient nodes which can be added to H 2 to make it a (N, /i, d)-tree.
After having identified all these padding nodes, we now have a "blueprint" for a construction procedure to follow. More precisely, the construction procedure will just generate all those padding nodes in the dark region in Figure 2

Main Part of Proof of Theorem 3
The tree construction procedure consists of three stages. Each stage uses an independent set of rules in constructing the tree.
In stage 1, we expand each node with exactly d children. Stage 1 terminates at time T\ when a total of 2h' or 2h f +1 nodes have just been expanded. (Note that at this time the tree is completely inside area 1 of Figure 3.) Since the number of frontier nodes increases by d -1 each time when a node is expanded, there are exactly 2h'(d -1) + 1 or (2h* + l)(d -1) + 1 frontier nodes at time 7\.
Without loss of generality, we assume that processor Pi has generated at least h'(d -1) frontier nodes.
Stage 2 starts right after 7\. In this stage every node above level h expanded by processor Pi will have d children, while every node at level h or expanded by processor P2 will have no children. Stage 2 terminates at time T 2 when one of the following two conditions becomes true: CI At least h\d -1) cross nodes have been scheduled.
C2 At least N -h -2d nodes have been generated.
The following shows that CI or C2 must become true sometime, i.e., T 2 exists. Recall that by the end of stage 1 processor Pi has generated at least h\d -1) frontier nodes. In stage 2 processor Pi will generate nodes in the subtrees rooted at those frontier nodes which are still in Pi. For each of these subtrees, since its root is in area 1 of Figure 3, the subtree can have at least N -h -2d nodes unless some of these nodes are moved to processor P2 from processor Pi. If Cl does not hold, then fewer than h'(d -1) nodes can be moved from Pi to P 2 . Consequently, some subtree will have at least N -h -2d nodes, and thus C2 will be true.
Stage 3 starts right after time T^. Lemma 2 below shows that properties 11-14 of Lemma 1 hold for the tree at time T 2 . In stage 3, we follow the procedure described in the proof of Lemma 1 to grow the tree to a (TV, h, d)-tree. Proof, It is obvious from the descriptions of stages 1 and 2 that 12 and 13 are satisfied. For II, we note that the total number of nodes generated in stage 1 is at most (2h f + l)d + 1, and thus at most N -h -d by restriction SI of Theorem 3. In stage 2, II obviously holds when C2 is not true. Suppose that C2 becomes true at time JT 2 . Since the tree has no more than N -h -2d nodes in the previous time step and since at most d nodes can be generated (in processor Pi) in one time step, there are at most N -h -d nodes at time T 2 .
Property 14 clearly holds for stage 1 by examining its description. It remains to prove that 14 holds for stage 2. The proof is similar to the earlier proof of the fact that Cl or C2 must become true in stage 2. Recall that in stage 1 processor Pi has generated at least h'{d -1) frontier nodes. We note that any of these subtrees rooted at these nodes is an HFD-subtree if the subtree does not contain any expanded cross node. Since the number of cross nodes expanded (not just scheduled) through time T 2 is less than h'{d -1), one of these subtrees must be an HFD-subtree. Note that if C2 becomes true at time T 2 (in the node scheduling phase), the node scheduled has not been expanded.
• To complete the proof of Theorem 3, we observe that if Cl-becomes true at some time in stage 2 or 3, it will remain true for the rest of the tree construction process. Therefore property Q2 of Theorem 3 will hold for the final (TV, /i, d)-tree. Now assuming that Cl never holds at any time in stage 2 or 3, we want to show that property Ql of Theorem 3 will hold for the final (TV, h,d)-tree. We derive an upper bound on the total number of nodes expanded by processor P 2 . The upper bound is the sum of four terms Ui, U 2 , U3 and U4. In stage 1, processor P 2 has expanded at most U\ = 2h' + 1 nodes. At time 7i, processor P 2 can have generated up to {h' + l)(d -1) + 1 frontier nodes, each of which can be expanded at most once by processor P 2 in stage 2 or 3. It is also possible for processor P 2 to expand nodes which are generated by P\ but subsequently moved to P 2 . The total number of these nodes is at most CA(H) < U3 = h\d -1). Moreover, to take care of the nodes generated after T 2 in stage 3, processor P 2 may expand up to U4 < h + 2d nodes. Therefore the total number of nodes expanded by processor P 2 is at most U = U\ + U 2 + Us + U4 < 3dh. This implies that processor Pi has expanded at least TV -U = TV -3dh; that is, property Ql holds. •

Proof of Theorem 1
Suppose that we are given a scheduling algorithm A for performing a D&C computation on a parallel system of p processors. For algorithm A, we will prove the existence of a (TV, h, d)tree H for which either only p' processors are active for expanding most of nodes (at least TV' nodes) or at least C nodes are moved between processors to balance their computation loads. For the former, the parallel computation cost will be high, i.e., TA(H) > TV'jp 1 (property PI). For the latter, the number of cross nodes will be large, i.e., CA(H) > C (property P2).
By playing an adversary game with algorithm .4, we will construct the tree by growing it from the root one step at a time. The definition of time step is the same as that in the proof of Theorem 3.
We will give some more definitions in Section 5.1 and then give the main part of this proof in Section 5.2. All the related lemmas are in Section 5.3.

Definitions
To help derive a lower bound on the number of cross nodes, we introduce the following relation between subtrees.

Definition 2 A set of subtrees is processor-or-ancestry independent (abbr.
PA-independent) if for each pair of subtrees in the set at least one of the following two properties is satisfied: 1. Processor Independence: the roots of these two subtrees are generated on different processors; 2. Ancestry Independence: neither is a subtree of the other. That is, there is no ancestordescendant relationship between the two roots.

Stage 1 =^
Apply the following four rules: Rl. Nodes in area 1 (shown in Figure 5) will generate d children. Figure 5) will not generate any children. R3. Non-cross nodes in areas 2 and 3 (excluding level h) will generate d children.

R2. Cross nodes in areas 2 and 3 (shown in
R4. Nodes at level h will not generate any children. Repeat rules R1-R4 until time T\ when any of the following three conditions holds: Cl. For some p' processors, at least h' non-cross nodes have been expanded on each processor. C2. At least C cross nodes have been scheduled. N -(pd + d + h) nodes have been generated.

Stage 2 (continued from time T\ when Cl holds) =>
Find a set V of p' processors with the following two properties: Bl. There are at least C PA-independent HFDC-subtrees in T.

B2. There are at most h' non-cross nodes expanded on each of the other p -p' processors
in the set T. Apply the following three rules: R5. Nodes (excluding those at level h) in T will generate d children.
R6. Nodes in T will not generate any children. R7. Nodes at level h will not generate any children. Repeat rules R5-R7 until time T 2 when either of the following two conditions holds: C4. At least C cross nodes have been scheduled.

C5. At least N -(pd + d + h) nodes have been generated.
Stage 3 (continued from time T\ when C2 or C3 holds or from time T 2 when C4 or C5 holds.) Use the construction procedure described in the proof of Lemma 1 to grow the tree to a (TV, h, d)-tree. Figure 4: Tree construction procedure.
Note that for two PA-independent subtrees rooted at nodes r\ and r 2 , if node r\ is an ancestor of node r 2 , then both nodes must be generated on different processors. This implies that there must exist at least one cross node on the path from node ri (inclusive) to the parent (inclusive) of node r 2 . Therefore, from this property, if there are k PA-independent subtrees each of which has at least one expanded cross node, then there are at least k expanded cross nodes in the tree. This is shown in Lemma 3 (in Section 5.3).

Definition 3 An HFDC-subtree is an HFD-subtree (as defined in Definition 1) or a subtree
with at least one cross node already expanded. If the root of an HFDC-subtree is generated on processor P, the subtree is called an HFDC-subtree on processor P.
By Lemma 3 and Definition 3, if there are k PA-independent HFDC-subtrees and fewer than k expanded cross nodes, then there exists an HFD-subtree, as shown in Lemma 4. We will use this lemma to show the existence of an HFD-subtree during some periods of the tree construction procedure.

Main Part of Proof of Theorem 1
The tree construction procedure consists of three stages. Basically, this procedure, summarized in Figure 4, is similar to that in Section 4. The main difference is that in stage 1 of this In stage 1, we will repeatedly apply rules R1-R4 (in Figure 4) until time T\ when one of the conditions C1-C3 holds. Rules R1-R4 ensure that each subtree rooted in area 1 or 2 is always an HFDC-subtree because in constructing the subtree either rules Al and A2 are followed (using Rl, R3, and R4) or some cross nodes are expanded (using R2). Basically, the procedure in stage 1 attempts to produce at least C PA-independent HFDC-subtrees on some p' processors (property Bl) while preventing each of the other p -p' processors from expanding more than h' non-cross nodes (property B2). (Recall that in the proof of Theorem 3 subtrees rooted at frontier nodes at time T\ are PA-independent HFDC-subtrees.)
"2 :Each processor expands fewer than ti non-cross nodes.
-B2 andCl hold. t " \ Each processor expands exactly K non-cross nodes. If condition Cl holds at time 7\, then from Figure 6 we can find a set T of p f processors for which condition Cl and property B2 hold. According to Lemma 5, there are at least zc(= (d -l)h') PA-independent HFDC-subtrees on each processor which has expanded h! non-cross nodes. So there are at least C"(= p 1 K) PA-independent HFDC-subtrees in T at this time. Therefore, property Bl holds, and we are ready for stage 2.
In stage 2, we will repeatedly apply rules R5-R7 until time T 2 when condition C4 or C5 holds. (Note that these rules are exactly the same as those of stage 2 in Section 4.) According to property Bl, initially, there are at least C PA-independent HFDC-subtrees in T. In stage 2, these subtrees continue to be HFDC-subtrees, because either rules Al and A2 are followed (using R5 and R7) or some cross nodes are expanded (using R6). In addition, by rule R6, the set T of the other p -p' processors will not generate any new nodes. Now, we want to show that one of the conditions C2-C5 must become true at time T\ or T 2 . According to Lemma 6 (in Section 5.3), at any time in stage 1 or 2 properties 11-14 of Lemma 1 hold; so, at any time in stage 1 or 2 the tree will be able to grow to a (TV, /i, d)-tree by Lemma 1. Hence, if C2 or C4 never hold, C3 or C5 becomes true.
Stage 3 starts right after one of the conditions C2-C5 becomes true. (If C2 or C3 holds at Ti, this implies that stage 2 is empty.) Since Lemma 6 also shows that properties 11-14 of Lemma 1 hold for the tree at time T\ or T 2 , in stage 3 we will follow the procedure described in the proof of Lemma 1 to grow the tree to a (JV, h, d)-tree H.
To complete the proof, we observe that if CA(H) > C it will remain true for the rest of the tree construction process. Therefore property P2 of Theorem 3 will hold for H. Now, assuming that CA(H) < C", we want to prove that property PI holds for H. Since C2 and C4 never hold, either C3 will become true at time Ti or C5 will become true at time T 2 . First, suppose that condition C5 becomes true at time T 2 . To prove that property PI holds in this case, we will derive an upper bound on the total number of nodes expanded in T. The upper bound consists of five terms <7i, £/ 2 , C/ 3 , £/ 4 , and U 5 . Assume that there are Ci < U\ = C cross nodes expanded in T in stage 1. In stage 1, the processors in T have expanded at most U 2 = (p-p')h' non-cross nodes due to property B2. These nodes expanded in stage 1 will generate at most £/ 3 = ((p -p')h' + C\)d frontier nodes in T at time Ti, each of which can be expanded at most once in T. After time Ti, it is also possible for the processors in T to expand nodes moved from the processors in T. The total number of these nodes is UA < CA(H) -C\. Moreover, to take care of the nodes generated after T 2 , processors in T may expand up to Us < pd + d+h nodes. Therefore, the total number of nodes expanded in T is at most U = U\ + U 2 + U3 + U\ + Us < 3pd 2 h. This implies that the processors in T have expanded at least N -U = N -3pd 2 h nodes; therefore, TA(H) > (N -3pd 2 h)/p f > N'/p', i.e., property PI holds.
Suppose that condition C3 becomes true at time T\. Since condition Cl does not hold in stage 1, we can find a set T of p l processors with property B2 (see Figure 6 also). Since stage 2 is empty for this case, we can let time T 2 be the same as Ti. Thus, we can use the same technique as above to prove that property PI holds. •

Relevant Lemmas
Lemma 3 Suppose that there are k PA-independent subtrees at some time during the computation. If each of these subtrees has at least one expanded cross node, then the total number of expanded cross nodes in the whole tree constructed so far is at least k.
Proof. This proof is not trivial because among these subtrees those with ancestry relationship may contain the same expanded cross node.
In this proof, we will prune the k PA-independent subtrees one by one under the restriction that the subtree being pruned contains no other subtrees which have not been pruned yet. (For the example illustrated in Figure 7, we can prune the subtrees in the order: 7^, 73, 7^, and T\.) For this proof, it suffices to prove that each pruned subtree has at least one expanded cross node.  Initially, the first pruned subtree obviously has at least one expanded cross node by the assumption of the lemma. As mentioned in Section 5.1, for any two PA-independent subtrees T and T rooted at nodes r and r' respectively, if r is an ancestor of r', there must exist at least one expanded cross node on the path from r (inclusive) to the parent (inclusive) of r' due to processor independence. Therefore, if we prune T' at r', T still has at least one expanded cross node. Hence, after we prune each subtree under the above restriction, each of the remaining subtrees will still have at least one expanded cross node. This implies that the next pruned subtree also has at least one expanded cross node. So, each pruned subtree has at least one expanded cross node. • Lemma 4 At some time, if there are k PA-independent HFDC-subtrees and fewer than k expanded cross nodes, there exists an HFD-subtree. • Proof. Assume that there exists no HFD-subtree. Thus, each of these PA-independent HFDC-subtrees has at least one expanded cross node according to the definition of HFDCsubtree. By Lemma 3, there are at least k expanded cross nodes. This is contradictory to the assumption of the lemma. •

Lemma 5
In stage 1, if a processor has expanded h! non-cross nodes, then there are at least K PA-independent HFDC-subtrees on the processor.
Proof. As mentioned in Section 5.2, each subtree rooted in area 1 or 2 is always an HFDCsubtree in stage 1. Thus it suffices to prove that at least K nodes with ancestry independence in areas 1 and 2 will be generated on the processor after h' non-cross nodes have been expanded. By rules R1-R3, for any non-cross node, all of its ancestors in area 2 (with hi + 1 levels) must be non-cross nodes as shown in Figure 8. So, all the nodes generated by the first h 1 non-cross nodes must be in areas 1 and 2. Since each of the h f non-cross nodes will generate d children and can remove at most one ancestor, these non-cross nodes will, in total, generate at least {d -\)h'(= K) nodes with ancestry independence. • Proof. It is obvious from rules R1-R7 that 12 and 13 are satisfied. In addition, it is also obvious that II holds before condition C3 or C5 becomes true. Consider the first time step when at least N -(pd + h + d) nodes have been generated (i.e., condition C3 or C5 holds).
Since the tree has no more than N -(pd + h + d) nodes in the previous time step and since at most pd nodes will be generated in each time step, there are at most N -h -d nodes in the current time step. In the rest of this proof, we will show that 14 always holds (i.e., there always exists an HFD subtree) in each stage.
In stage 1, all the nodes in area 1 will generate d nodes by rule Rl. So, before all the nodes in area 1 have been expanded, there must exist one frontier node in area 1, of which the subtree (with only one node) is an HFD-subtree. After all the nodes in area 1 are expanded, there are at least d^°Z dPdh^ > pdh > C subtrees rooted at the top level of area 2. Obviously, these subtrees are PA-independent. They are also HFDC-subtrees because each subtree rooted in area 1 or 2 in stage 1 is always an HFDC-subtree as described in Section 5.2. Since the number of expanded cross nodes is always less than C (due to condition C2), there has always been an HFD-subtree up to time T\ by Lemma 4. Thus, we can conclude that there always exists an HFD-subtree in stage 1.
In stage 2, initially, there are at least C PA-independent HFDC-subtrees in T (property Bl). These subtrees will continue to be HFDC-subtrees in this stage as described in Section 5.2. In stage 2, due to condition C4 the number of expanded cross nodes is always less than C"; so, there always exists an HFD-subtree by Lemma 4. •