Parallel Prefix Computation in the Recursive Dual-Net

摘要

In this paper, we propose an efficient algorithm for parallel prefix computation in recursive dual-net, a newly proposed network. The recursive dual-net RDNk(B) for k > 0 has (2no)2k/2 nodes and do + k links per node, where no and do are the number of nodes and the node-degree of the base network B, respectively. Assume that each node holds one data item, the communication and computation time complexities of the algorithm for parallel prefix computation in RDNk(B), k > 0, are 2k+l - 2 + 2k * Tcomm(0) and 2k+1 - 2 + 2k * Tcomp(0), respectively, where Tcomm(0) and Tcomp(0) are the communication and computation time complexities of the algorithm for parallel prefix computation in the base network B, respectively.