AlphaSort: a RISC machine sort

ABSTRACT

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using Alpha AXP processors, commodity memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-cpu 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in a minute.AlphaSort is a cache-sensitive memory-intensive sort algorithm. It uses file striping to get high disk bandwidth. It uses QuickSort to generate runs and uses replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores.Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) Minutesort: how much can you sort in a minute, and (2) DollarSort: how much can you sort for a dollar.

REFERENCES

• 1: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 2: Jean-Loup Baer , Yi-Bing Lin, Improving Quicksort Performance with a Codeword Data Structure, IEEE Transactions on Software Engineering, v.15 n.5, p.622-631, May 1989 [doi>10.1109/32.24711]
• 3: B. A. Baugsto:.KC / , J. F. Greipsland, Parallel sorting methods for large data volumes on a hypercube database computer, Database Machines Sixth International Workshop, IWDM '89, Springer-Verlag New York, Inc., New York, NY, 1989
• 4: B. A. W. Baugstø , J. F. Greipsland , J. Kamerbeek, Sorting large data files on POOMA, Proceedings of the joint international conference on Vector and parallel processing, p.536-547, September 1990, Zurich, Switzerland
• 5: Z. Cvetanovic , D. Bhandarkar, Characterization of alpha AXP performance using TP and SPEC workloads, Proceedings of the 21ST annual international symposium on Computer architecture, p.60-70, April 18-21, 1994, Chicago, Illinois, United States
• 6: Bitton, D., Design, Analysis and Implementation of Parallel External Sorting Algorithms, Ph.D. Thesis, U. Wisconsin, Madison, WI, 1981
• 7: 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]
• 8: Conner, W.M., Offset Value Coding, IBM Technical Disclosure Bulletin, V 20(7), Dec. 1977, pp. 2832-2837
• 9: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• 10: Filgate, Bruce, "SCSI 3.5" 1.05 GB Disk Comparative Performance", Digital Storage Labs, Nov. 10 1992
• 11: Graefe, G., "Parallel external sorting in Volcano," U. Colorado Comp. Sci. Tech. Report 459, June 1990.
• 12: Goetz Graefe , Shreekant S. Thakkar, Tuning a parallel database algorithm on a shared-memory multiprocessor, Software—Practice & Experience, v.22 n.7, p.495-517, July 1992 [doi>10.1002/spe.4380220702]
• 13: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 14: Kaivalya, D., The SPEC Benchmark Suite, Chapter 6 of The Benchmark Handbook for Database and Transaction Processing Systems, Second Edition, Chapter 6, Morgan Kaufmann, San Mateo, 1993.
• 15: M. Kitsuregawa , W. Yang, Evaluation of 18-stage pipeline hardware sorter, Database Machines Sixth International Workshop, IWDM '89, Springer-Verlag New York, Inc., New York, NY, 1989
• 16: M Y Kim, Synchronized disk interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, Nov. 1986 [doi>10.1109/TC.1986.1676699]
• 17: Knuth, E.E., Sorting and Searching, The Art of Computer Programming, Addison Wesley, Reading, Ma., 1973.
• 18: 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
• 19: Lorin, H. Sorting, Addison Wesley, Englewood Cliffs, NJ, 1974.
• 20: Salzberg, B., et al., "FastSort- An External Sort Using Parallel Processing", Proc. SIGMOD 1990, pp. 88-101.
• 21: Tsukerman, A., "FastSort- An External Sort Using Parallel Processing" Tandem Systems Review, V 3(4), Dec. 1986, pp. 57-72.
• 22: Weinberger, PJ., Private communication 1986.
• 23: Yamane, Y., Take, R. "Parallel Partition Sort for Database Machines", Database Machines and Knowledge Based Machines, Kitsuregawa and Tanaka eds., pp.: 1117-130. Klwar Academic Publishers, 1988.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Measurement, Performance