Parallel Prefix Computation and Sorting on a Recursive Dual-Net


Yamin Li, Shietung Peng, Wanming Chu, Journal of Information Processing Systems Vol. 7, No. 2, pp. 271-286, Jun. 2011  

https://doi.org/10.3745/JIPS.2011.7.2.271
Keywords: Interconnection Networks, Algorithm, Parallel Prefix Computation, Sorting
Fulltext:

Abstract

In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDNk(B) for k > 0 has (2no)2K/2 nodes and d0 + k links per node, where n0 and d0 are the number of nod es 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 RDNk(B), k > 0, are 2k+1-2+2kTcomm(0) and 2 k+1-2+2kTcomp(0), respectively, where Tcomm(0) and Tcomp(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 RDNk(B) is restricted on B = Qm where Qm is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2k)2) computation steps and O((km2k)2) communication steps, respectively.


Statistics
Show / Hide Statistics

Statistics (Past 3 Years)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Li, Y., Peng, S., & Chu, W. (2011). Parallel Prefix Computation and Sorting on a Recursive Dual-Net. Journal of Information Processing Systems, 7(2), 271-286. DOI: 10.3745/JIPS.2011.7.2.271.

[IEEE Style]
Y. Li, S. Peng, W. Chu, "Parallel Prefix Computation and Sorting on a Recursive Dual-Net," Journal of Information Processing Systems, vol. 7, no. 2, pp. 271-286, 2011. DOI: 10.3745/JIPS.2011.7.2.271.

[ACM Style]
Yamin Li, Shietung Peng, and Wanming Chu. 2011. Parallel Prefix Computation and Sorting on a Recursive Dual-Net. Journal of Information Processing Systems, 7, 2, (2011), 271-286. DOI: 10.3745/JIPS.2011.7.2.271.