Lower bounds for merging on the hypercube
作者： Christine Rüb
关键词: Hypercube 、 Combinatorics 、 Sorting 、 Mathematics
摘要: We show lower bounds for the problems of merging two sorted lists equal length and sorting by repeatedly pairs sequences on hypercube. These hold average any ordering processors
springer.com
mpg.de
sci-hub.st 参考文章(13)
Alok Aggarwal, Ming-Deh A. Huang, Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks (preliminary version) AWOC '88 Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures. pp. 339- 350 ,(1988) , 10.1007/BFB0040401
Florence Jessie MacWilliams, Neil James Alexander Sloane, The Theory of Error-Correcting Codes ,(1977)
C. Greg Plaxton, A hypercubic sorting network with nearly logarithmic depth symposium on the theory of computing. pp. 405- 416 ,(1992) , 10.1145/129712.129751
Richard Cole, Parallel merge sort SIAM Journal on Computing. ,vol. 17, pp. 770- 785 ,(1988) , 10.1137/0217049
Gianfranco Bilardi, Alexandru Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines SIAM Journal on Computing. ,vol. 18, pp. 216- 228 ,(1989) , 10.1137/0218014
Kruskal, Searching, Merging, and Sorting in Parallel Computation IEEE Transactions on Computers. ,vol. 32, pp. 942- 946 ,(1983) , 10.1109/TC.1983.1676138
Robert Cypher, Jorge L.C Sanz, Cubesort: A parallel algorithm for sorting N data items with S -sorters Journal of Algorithms. ,vol. 13, pp. 211- 234 ,(1992) , 10.1016/0196-6774(92)90016-6
Torben Hagerup, Christine Rüb, Optimal merging and sorting on the EREW PRAM Information Processing Letters. ,vol. 33, pp. 181- 185 ,(1989) , 10.1016/0020-0190(89)90138-5
F. Thomson Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes ,(1991)
R. Cypher, C. G. Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers symposium on the theory of computing. ,vol. 47, pp. 193- 203 ,(1990) , 10.1145/100216.100240