Parallel Prefix Computation and Sorting on a Recursive Dual-Net
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (18)
- S. G. Aki, "Parallel Computation, Models and Methods" (1997), Prentice-Hall
- F. T. Leighton, "Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes" (1992), Morgan Kaufmann
- A. Varma, "Interconnection Networks for Multiprocessors and Multicomputers: Theory and Practice" (1994), IEEE Computer Society Press
- K. Ghose, "Hierarchical cubic networks", IEEE Transactions on Parallel and Distributed Systems, 6(4), pp.427~435 (1995)
- Y. Li, "Dual-cubes: a new interconnection network for high-performance computer clusters", Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture, ChiaYi, Taiwan, pp.51~57 (2000)
- Y. Li, "Efficient collective communications in dual-cube", The Journal of Supercomputing, 28, pp.71~90 (2004)
- F. P. Preparata, "The cube-connected cycles: a versatile network for parallel computation", Commun. ACM, 24, pp.300~309 (1981)
- Y. Saad, "Topological properties of hypercubes", IEEE Transactions on Computers, 37(7), pp.867~872 (1988)
- G. H. Chen, "Topological properties, communication, and computation on wkrecursive networks", Networks, 24(6), pp.303~317 (1994)
- G. Vicchia, "A recursively scalable network vlsi implementation", Future Generation Computer Systems, 4(3), pp.235~243 (1988)
- "TOP500, Supercomputer Sites" (2010)[URL]
- P. Beckman, "Looking toward exascale computing, keynote speaker", International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'08), University of Otago, Dunedin, New Zealand (2008)
- R. Cypher, "Deterministic sorting in nearly logarithmic time on the hypercube and related computers", Proceedings of the 22dn Annual ACM Symposium on Theory of Computing, pp.193~203 (1990)
- N. R. Adiga, "Blue gene", l torus interconnection network, 2005, pp.49(2), 265~276
- Y. Li, "Recursive dual-net: A new universal network for supercomputers of the next generation", Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP'09), Taipei, Taiwan, Springer, Lecture Notes in Computer Science (LNCS), pp.809~820 (2009)
- A. Grama, "Introduction to Parallel Computing" (2003), Addison- Wesley
- W. D. Hillis, "Data parallel algorithms", Communications of the ACM, 29(12), pp.1170~1183 (1986)
- V. Kumar, "Introduction to parallel computing: design and analysis of algorithms", pp.1994, Benjamin