Communication complexity for parallel divide-and-conquer

Abstract: "This paper studies the relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors. 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. A cross node is a node which is generated by one processor but expanded by another processor. A new scheduling algorithm is proposed, whose parallel computation cost and communication cost are at most [N/p] and pdh, respectively, for any D&C computation tree with N nodes, height h, and degree d.Also, lower bounds on the communication cost are derived. In particular, it is shown that for each scheduling algorithm and for each positive [epsiolon subscript C] < 1, which can be arbitrarily close to 0, there are values of N, h, d, p, and [epsilon subscript T] (>0), for which if the parallel computation cost is between N/p (the minimum) and (1 + [epsilon subscript T])N/p, then the communication cost must be at least (1 - [epsilon subscript C) [times] pdh. Therefore, the proposed scheduling algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal."