Inproceedings,

Tight Bounds on the Complexity of Parallel Sorting

.
Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, page 71--80. New York, NY, USA, ACM, (1984)
DOI: 10.1145/800057.808667

Abstract

In this paper, we prove tight upper and lower bounds on the number or processors, information transfer, wire area and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) the construction of an O(N))-node bounded-degree network capable of sorting N numbers in O(log N) word steps, 2) a proof that any network capable of sorting N(7 log N)-bit numbers in T bit-steps requires area A where AT2≥ &Ohgr;(N2log2N), and 3) the construction of a “small-constant-factor” bounded-degree network that sorts $N \Theta(N)$-bit numbers in T &equil; &thgr;(log N) bit steps with A &equil; &thgr;(N2) area.

Tags

Users

  • @ytyoun

Comments and Reviews