Tight bounds on the complexity of parallel sorting

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 &thgr;(log N)-bit numbers in T &equil; &thgr;(log N) bit steps with A &equil; &thgr;(N2) area.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• 2: D. Angluin and C. Thompson, unpublished manuscript, 1982.
• 3: K. Batcher, "Sorting Networks and their Applications", Proc. AFIPS Spring Joint Computer Conf., Vol. 32, 1968, pp 307-314.
• 4: G. Bilardi and F. Preparata, "An Architecture for Bitonic Sorting with Optimal VLSI Performance", IEEE Transactions on Computers, to appear.
• 5: G. Bilardi , F. P. Preparata, A minimum area VLSI network for O(logn) time sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.64-70, December 1984 [doi>10.1145/800057.808666]
• 6: G. Bilardi and F. Preparata, "The VLSI Optimality of the AKS Sorting Network," in preparation.
• 7: 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, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• 8: A. El Gamal, personal communication, 1983.
• 9: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 10: F. T. Leighton, "New Lower Bound Techniques for VLSI," Proc. 22nd Conf. on Foundations of Computer Science, 1981, pp. 1-12.
• 11: Frank Thomson Leighton, Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks, MIT Press, Cambridge, MA, 1983
• 12: F. T. Leighton, "Parallel Computation Using Meshes of Trees", Proc. 1983 Workshop on Graphtheoretic Concepts in Computer Science, Osnabruck West Germany.
• 13: F. T. Leighton, "Simple o(log2N)-Depth Sorting Circuits", in preparation.
• 14: Richard J. Lipton , Robert Sedgewick, Lower bounds for VLSI, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.300-307, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802482]
• 15: D. S. Parker, "Notes on Shuffle/Exchange-Type Switching Networks", IEEE Transactions on Computers, Vol. C-29, No. 3, 1980, pp. 213-222.
• 16: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983 [doi>10.1145/800061.808727]
• 17: H. Stone, "Parallel Processing with the Perfect Shuffle", IEEE Transactions on Computers, Vol. C-20, No. 2, 1971.
• 18: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 19: C. Thompson, "The VLSI Complexity of Sorting", IEEE Transactions on Computers, Vol. C-32, No. 12, 1983.
• 20: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• 21: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Design, Performance, Theory