FastSort: a distributed single-input single-output external sort

ABSTRACT

External single-input single-output sorts can use multiple processors each with a large tournament replacement-selection in memory, and each with private disks to sort an input stream in linear elapsed time. Of course, increased numbers of processors, memories, and disks are required as the input file size grows. This paper analyzes the algorithm and reports the performance of an implementation.

REFERENCES

• Anon: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• Beck: Micah Beck , Dina Bitton , W. Kevin Wilkinson, Sorting Large Files on a Backend Multiprocessor, IEEE Transactions on Computers, v.37 n.7, p.769-778, July 1988 [doi>10.1109/12.2222]
• DeWitt: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• Graefe: Graefe, G, "Parallel external sorlang m Volcano," Oregon Graduate Center TR No CS/E 89-008, June 1989
• Knuth: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• Lorie: R. A. Lorie , H. C. Young, A low communication sort algorithm for a parallel database machine, Proceedings of the 15th international conference on Very large data bases, p.125-134, July 1989, Amsterdam, The Netherlands
• Salzberg 88: Betty Salzberg, File structures: an analytic approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• Salzberg 89: B. Salzberg, Merging sorted runs using large main memory, Acta Informatica, v.27 n.3, p.195-215, Dec. 1989 [doi>10.1007/BF00572988]
• Tsukerman: Tsukerman, A, et al, FastSort, An External Sort Ustng Parallel Processmg, Tandem Techmcal Report TR 86 3, Part No PN87617, Tandem Computers, Cuperuno CA April 1986
• Uren: Uren, S Message System Performance Tests, Tandem Systems Review, Tandem Computers In, Cuperuno, CA, V 2 3, pp 27-31, Dec 1986

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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Performance