A hypercubic sorting network with nearly logarithmic depth

作者: C. Greg Plaxton

DOI: 10.1145/129712.129751

关键词:

摘要: A natural class of “hypercubic” sorting networks is defined. The regular structure these allows for elegant and efficient implementations on any the so-called hypercubic (e.g., hypercube, shuffle-exchange, butterfly, cube-connected cycles). This contains Batcher's O(lg2n)-depth bitonic sort, but not O(lg n)-depth network Ajtai, Komlo´s, Szemere´di. In fact, no o(lg2n)-depth compare-interchange sort was previously known networks. this paper, we prove existence a family 2O((lg lg n)1/2) n-depth Note that depth o(lg1+en) constant e > 0.

参考文章(8)
Robert Cypher, Theoretical aspects of VLSI pin limitations conference on advanced research in vlsi. pp. 314- 327 ,(1990)
M. Ajtai, J. Komlós, E. Szemerédi, Sorting inc logn parallel steps Combinatorica. ,vol. 3, pp. 1- 19 ,(1983) , 10.1007/BF02579338
C. Greg Plaxton, Torsten Suel, A lower bound for sorting networks based on the shuffle permutation Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures - SPAA '92. ,vol. 27, pp. 70- 79 ,(1992) , 10.1145/140901.140909
M. S. Paterson, Improved Sorting Networks with O(log n) Depth Algorithmica. ,vol. 5, pp. 75- 92 ,(1987) , 10.1007/BF01840378
V. E. Beneš, Optimal Rearrangeable Multistage Connecting Networks Bell System Technical Journal. ,vol. 43, pp. 1641- 1656 ,(1964) , 10.1002/J.1538-7305.1964.TB04103.X
K. E. Batcher, Sorting networks and their applications Proceedings of the April 30--May 2, 1968, spring joint computer conference on - AFIPS '68 (Spring). pp. 307- 314 ,(1968) , 10.1145/1468075.1468121
T. Leighton, C.G. Plaxton, A (fairly) simple circuit that (usually) sorts foundations of computer science. pp. 264- 274 ,(1990) , 10.1109/FSCS.1990.89545
Donald Ervin Knuth, The Art of Computer Programming ,(1968)