A dynamically tuned sorting library

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Empirical search is a strategy used during the installation of library generators such as ATLAS, FFTW, and SPIRAL to identify the algorithm or the version of an algorithm that delivers the best performance. In the past, empirical search has been applied almost exclusively to scientific problems. In this paper, we discuss the application of empirical search to sorting, which is one of 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 part of a sorting library generator. The resulting routines dynamically adapt to the characteristics of the input data by selecting the best sorting algorithm from a small set of alternatives. To generate the run time selection mechanism our generator makes use of machine learning to predict the best algorithm as a function of the characteristics of the input data set and the performance of the different algorithms on the target machine. This prediction is based on the data obtained through empirical search at installation time. Our results show that our approach is quite effective. When sorting data inputs of 12M keys with various standard deviations, our adaptive approach selected the best algorithm for all the input data sets and all platforms that we tried in our experiments. The wrong decision could have introduced a performance degradation of up to 133%, with an average value of 44%.

Original languageEnglish (US)
Title of host publicationInternational Symposium on Code Generation and Optimization, CGO 2004
Pages111-122
Number of pages12
StatePublished - 2004
EventInternational Symposium on Code Generation and Optimization, CGO 2004 - San Jose, CA, United States
Duration: Mar 20 2004Mar 24 2004

Publication series

NameInternational Symposium on Code Generation and Optimization, CGO

Other

OtherInternational Symposium on Code Generation and Optimization, CGO 2004
CountryUnited States
CitySan Jose, CA
Period3/20/043/24/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A dynamically tuned sorting library'. Together they form a unique fingerprint.

Cite this