Tight bounds on the complexity of parallel sorting
作者： Tom Leighton
关键词: Parallel sorting 、 Information transfer 、 sort 、 Sorting 、 Binary logarithm 、 Mathematics 、 Upper and lower bounds 、 Word (computer architecture) 、 Combinatorics
摘要: In this paper, we prove tight upper and lower bounds on the number or processors, information transfer, wire area time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) construction of an O(N))-node network capable sorting O(log N) word steps, 2) proof that any N(7 log N)-bit T bit-steps requires A where AT2≥ Ω(N2log2N), 3) “small-constant-factor” sorts θ(log = bit steps with θ(N2) area.
acm.org
sci-hub.se 参考文章(17)
H.S. Stone, Parallel Processing with the Perfect Shuffle IEEE Transactions on Computers. ,vol. C-20, pp. 153- 161 ,(1971) , 10.1109/T-C.1971.223205
L. G. Valiant, G. J. Brebner, Universal schemes for parallel communication Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 263- 277 ,(1981) , 10.1145/800076.802479
John H. Reif, Leslie G. Valiant, A logarithmic time sort for linear size networks symposium on the theory of computing. pp. 10- 16 ,(1983) , 10.1145/800061.808727
G. Bilardi, F.P. Preparata, The VLSI optimality of the AKS sorting network Information Processing Letters. ,vol. 20, pp. 55- 59 ,(1985) , 10.1016/0020-0190(85)90062-6
Richard J. Lipton, Robert Sedgewick, Lower bounds for VLSI Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 300- 307 ,(1981) , 10.1145/800076.802482
G. Bilardi, F. P. Preparata, A minimum area VLSI network for O(logn) time sorting symposium on the theory of computing. pp. 64- 70 ,(1984) , 10.1145/800057.808666
Clark D Thompson, Area-time complexity for VLSI symposium on the theory of computing. pp. 81- 88 ,(1979) , 10.1145/800135.804401
A. Borodin, J. E. Hopcroft, Routing, merging and sorting on parallel models of computation Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 338- 344 ,(1982) , 10.1145/800070.802209
Gianfranco Bilardi, Franco P. Preparata, An Architecture for Bitonic Sorting with Optimal VLSI Performnance IEEE Transactions on Computers. ,vol. 33, pp. 646- 651 ,(1984) , 10.1109/TC.1984.5009338
M. Ajtai, J. Komlós, E. Szemerédi, An 0(n log n) sorting network symposium on the theory of computing. pp. 1- 9 ,(1983) , 10.1145/800061.808726