Optimizing sorting with machine learning algorithms

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

Abstract

The growing complexity of modern processors has made the development of highly efficient code increasingly difficult. Manually developing highly efficient code is usually expensive but necessary due to the limitations of today's compilers. A promising automatic code generation strategy, implemented by library generators such as ATLAS, FFTW, and SPIRAL, relies on empirical search to identify, for each target machine, the code characteristics, such as the tile size and instruction schedules, that deliver the best performance. This approach has mainly been applied to scientific codes which can be optimized by identifying code characteristics that depend only on the target machine. In this paper, we study the generation of sorting routines whose performance also depends on the characteristics of the input data. We present two approaches to generate efficient sorting routines. First, we consider the problem of selecting the best "pure" sorting algorithm as a function of the characteristics of the input data. We show that the relative performance of "pure" sorting algorithms can be encoded as a function of the entropy of the input data set. We used machine learning algorithms to compute a function for each target machine that, at runtime, is used to select the best algorithm. Our second approach generalizes the first approach and can build new sorting algorithms from a few primitive operations. We use genetic algorithms and a classifier system to build hierarchically-organized hybrid sorting algorithms capable of adapting to the input data. Our results show that the algorithms generated using this second approach are quite effective and perform significantly better than the many conventional sorting implementations we tested. In particular, the routines generated using the second approach perform better than the most popular libraries available today: IBM ESSL, INTEL MKL and the C++ STL The best algorithm we have been able to generate is on the average 26% and 62% faster than the IBM ESSL in an IBM Power 3 and IBM Power 4, respectively.

Original languageEnglish (US)
Title of host publicationProceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
DOIs
StatePublished - 2007
Event21st International Parallel and Distributed Processing Symposium, IPDPS 2007 - Long Beach, CA, United States
Duration: Mar 26 2007Mar 30 2007

Publication series

NameProceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM

Other

Other21st International Parallel and Distributed Processing Symposium, IPDPS 2007
CountryUnited States
CityLong Beach, CA
Period3/26/073/30/07

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Optimizing sorting with machine learning algorithms'. Together they form a unique fingerprint.

  • Cite this

    Li, X., Garzarán, M. J., & Padua, D. (2007). Optimizing sorting with machine learning algorithms. In Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM [4228227] (Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM). https://doi.org/10.1109/IPDPS.2007.370499