A super scalar sort algorithm for RISC processors

ABSTRACT

The compare and branch sequences required in a traditional sort algorithm can not efficiently exploit multiple execution units present in currently available high performance RISC processors. This is because of the long latency of the compare instructions and the sequential algorithm used in sorting. With the increased level of integration on a chip, this trend is expected to continue. We have developed new sort algorithms which eliminate almost all the compares, provide functional parallelism which can be exploited by multiple execution units, significantly reduce the number of passes through keys, and improve data locality. These new algorithms outperform traditional sort algorithms by a large factor.For the Datamation disk to disk sort benchmark (one million 100-byte records), at SIGMOD'94, Chris Nyberg et al presented several new performance records using DEC alpha processor based systems.We have implemented the Datamation sort benchmark using our new sort algorithm on a desktop IBM RS/6000 model 39H (66.6 MHz) with 8 IBM SSA 7133 disk drives (total cost $73K). The total elapsed time for the 100 MB sort was 5.1 seconds (vs the old uni-processor record of 9.1 seconds). We have also established a new price performance record (0.2¢ vs the old record of 0.9¢, as the cost of the sort). The entire sort processing was overlapped with I/O. During the read phase, we achieved a sustained BW of 47 MB/sec and during the write phase, we achieved a sustained BW of 39 MB/sec. Key extraction and sorting of one million 10-byte keys took only 0.6 second of CPU time. The rest of the CPU time was used in moving records, servicing I/O, and other overheads.Algorithmic details leading to this level of performance are described in this paper. A detailed analysis of the CPU time spent during various phases of the sort algorithm and I/O is also provided.

REFERENCES

• 1: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 2: 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
• 3: 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
• 4: 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
• 5: 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
• 6: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 7: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 8: Tsukerman, A., "FastSort - An External Sort Using Parallel Processing", Proc. SIGMOD 1990, pp. 88- 101.
• 9: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a cache-sensitive parallel external sort, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, October 1995
• 11: SGI Media Brief dated May 22, 1995.
• 12: Barley, D., Barszcz, E., Barton, J. Browning, D., Carter, R., Dagum, L., Fatoohi, R., Fineberg, S., Frederickson, P., Lasinski, T., Schereiber, P~., Simon, H., Venkatakrishnan, V., Weerantunga, S., The NAS Parallel Benchmarks, Technical Report RNR-94-007, NASA Ames Research Center, March, 1994.
• 13: Agarwal R. C., Gustavson F. G., Zubair M., "A Scalable Parallel Implementation of the NAS Integer Sort Benchmark", Proc. int. Workshop on Parallel Processing, Bangalore, India, pp. 463-477, December, 1994.
• 14: R. C. Agarwal , B. Alpern , L. Carter , F. G. Gustavson , D. J. Klepacki , R. Lawrence , M. Zubair, High-performance parallel implementations of the NAS kernel benchmarks on the IBM SP2, IBM Systems Journal, v.34 n.2, p.263-272, 1995
• 15: R. C. Agarwal , F. G. Gustavson , M. Zubair, Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms, IBM Journal of Research and Development, v.38 n.5, p.563-576, Sept. 1994

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

General Terms:
Algorithms, Measurement, Performance, Theory