Tight bounds on the complexity of parallel sorting
T Leighton - Proceedings of the sixteenth annual ACM symposium …, 1984 - dl.acm.org
T Leighton
Proceedings of the sixteenth annual ACM symposium on Theory of computing, 1984•dl.acm.orgIn 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≥ Ω (N2 log2 N), and 3) the construction of a “small-constant-factor” …
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≥ Ω (N2 log2 N), and 3) the construction of a “small-constant-factor” …
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≥ Ω(N2log2N), and
3) the construction of a “small-constant-factor” bounded-degree network that sorts N θ(log N)-bit numbers in T = θ(log N) bit steps with A = θ(N2) area.
ACM Digital Library