Parallel Prefix Computation in the Recursive Dual-Net

Description

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 ${(2n_0)^{2^k}/2}$ nodes and d0+k links per node, where n0 and d0 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 ${2^{k+1}-2+2^k*T_{comm}(0)}$ and ${2^{k+1}-2+2^k*T_{comp}(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.

Details 詳細情報について

Report a problem

Back to top