Parallel Prefix Computation and Sorting on a Recursive Dual-Net

• Published in: Journal of information processing systems 2011, 7(2), 20, pp.271-286
• Main Authors: Yamin Li, Shietung Peng, Wanming Chu
• Format: Article
• Language: English
• Subjects: 컴퓨터학
• ISSN: 1976-913X; 2092-805X
• DOI: 10.3745/JIPS.2011.7.2.271

In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k > 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 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 on RDN^k(B), k > 0, are 2^(k+1)-2+2^kT_(comm)(0) and 2^(k+1)-2+2^kT_(comp)(0), respectively, where T_(comm)(0) and T_(comp)(0) are the communication and computation time complexities of the algorithm for parallel prefix computation on the base-network B, respectively. The algorithm for parallel sorting on RDN^k(B) is restricted on B = Q_m where Q_m is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)^2) computation steps and O((km2^k)^2) communication steps, respectively. KCI Citation Count: 0