A Dynamically Tuned Sorting Library

ABSTRACT

Empirical search is a strategy used during the installation oflibrary generators such as ATLAS, FFTW, and SPIRAL to identify the algorithm or the version of an algorithm that delivers thebest performance. In the past, empirical search has been appliedalmost exclusively to scientific problems. In this paper, we discuss the application of empirical search to sorting, which is oneof the best understood symbolic computing problems. When contrasted with the dense numerical computations of ATLAS, FFTW,and SPIRAL, sorting presents a new challenge, namely that the relative performance of the algorithms depend not only on the characteristics of the target machine and the size of the input data but also on the distribution of values in the input data set.Empirical search is applied in the study reported here as partof a sorting library generator. The resulting routines dynamicallyadapt to the characteristics of the input data by selecting the bestsorting algorithm from a small set of alternatives. To generate therun time selection mechanism our generator makes use of machinelearning to predict the best algorithm as a function of the characteristics of the input data set and the performance of the differentalgorithms on the target machine. This prediction is based on thedata obtained through empirical search at installation time.Our results show that our approach is quite effective. Whensorting data inputs of 12M keys with various standard deviations,our adaptive approach selected the best algorithm for all the inputdata sets and all platforms that we tried in our experiments. Thewrong decision could have introduced a performance degradationof up to 133%, with an average value of 44%.

References

1. {1} TPC Benchmark H. Transaction Processing Performance Council (TPC), 2002.
2. {2} R. Allan and K. Kennedy. Optimizing Compilers for Modern Architectures . Morgan Kaufman Publishing, 2002.
3. {3} M. Frigo. A Fast Fourier transform Compiler. In Proc. of Programing Language Design and Implementation, 1999.
4. {4} D. Jiménez-González, J. Navarro, and J. Larriba-Pey. CC-Radix: A Cache Conscious Sorting Based on Radix Sort. In Euromicro Conference on Parallel Distributed and Network based Processing, pages 101-108, February 2003.
5. {5} P. Kisubi, P. Knijnenburg, and M. O'Boyle. The Effect of Cache Models on Iterative Compilation for Combined Tiling and Unrolling. In Proc. of the International Conference on Parallel Architectures and Compilation Techniques, pages 237-246, 2000.
6. {6} D. Knuth. The Art of Computer Programming; Volume3/Sorting and Searching. Addison-Wesley, 1973.
7. {7} A. LaMarca and R. Ladner. The Influence of Caches on the Performance of Sorting. In Proceeding of the ACM/SIAM Symposium on Discrete Algorithms, pages 370-379, January 1997.
8. {8} J. Larriba-Pey, D. Jiménez-González, and J. Navarro. An Analysis of Superscalar Sorting Algorithms on an R8000 processor. In International Conference of the Chilean Computer Science Society, pages 125-134, November 1997.
9. {9} T. Mitchell. Machine Learning. McGraw Hill, 1997.
10. {10} C. Nyberg, T. Barclay, Z. Cvetanovic, J. Gray, and D. Lomet. AlphaSort: A RISC Machine Sort. In Proc. of the Sigmod Conference, pages 233-242, 1994.
11. {11} R. Sedgewick. Implementing Quicksort Programs. Communications of the ACM, 21(10):847-857, October 1978.
12. {12} R. Whaley, A. Petitet, and J. Dongarra. Automated Empirical Optimizations of Sofware and the ATLAS Project. Parallel Computing, 27(1-2):3-35, 2001.
13. {13} J. Xiong, J. Johnson, R. Johnson, and D. Padua. SPL: A Language and a Compiler for DSP Algorithms. In Proc. of the International Conference on Programming Language Design and Implementation, pages 298-308, 2001.
14. {14} K. Yotov, X. Li, G. Ren, M. Cibulskis, G. DeJong, M. Garzaran, D. Padua, K. Pingali, P. Stodghill, and P. Wu. A Comparison of Empirical and Model-driven Optimization. In Proc. of Programing Language Design and Implementation, pages 63-76, June 2003.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Runtime environments

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching