EFFICIENT PARALLEL DIVIDE-AND-CONQUER FOR A CLASS OF INTERCONNECTION TOPOLOGIES

In this paper, we propose an efficient scheduling algorithm for expanding any divide-and-conquer (D&C) computation tree on k-dimensional mesh, hypercube, and perfect shuffle networks with p processors. Assume that it takes t(n) time steps to expand one node of the tree and t(c) time steps to transmit one datum or convey one node. For any D&C computation tree with N nodes, height h, and degree d (maximal number of children of any node), our algorithm requires at most (N/p + h)t(n) + phidht(c) time steps, where phi is O(log2 p) on a hypercube or perfect shuffle network and is O(k square-root p on a n(k-1) x ... x n0 mesh network, where n(k-1) = ... = n0 = k square-root p. This algorithm is general in the sense that it does not know the values of N, h, and d, and the shape of the computation tree as well, a priori. Most importantly, we can easily obtain a linear speedup by nearly a factor of p, especially when N much greater than ph(1 + phidt(c)/t(n)).