- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
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.
