Analytic models and empirical search: A hybrid approach to code optimization

Arkady Epshteyn, María Jesús Garzaran, Gerald DeJong, David Padua, Gang Ren, Xiaoming Li, Kamen Yotov, Keshav Pingali

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

Abstract

Compilers employ system models, sometimes implicitly, to make code optimization decisions. These models are analytic; they reflect their implementor's understanding and beliefs of the system. While their decisions can be made almost instantaneously, unless the model is perfect their decisions may be flawed. To avoid exercising unique characteristics of a particular machine, such models are necessarily general and conservative. An alternative is to construct an empirical model. Building an empirical model involves extensive search of a parameter space to determine optimal settings. But this search is performed on the actual machine on which the compiler is to be deployed so that, once constructed, its decisions automatically reflect any eccentricities of the target system. Unfortunately, constructing accurate empirical models is expensive and, therefore, their applicability is limited to library generators such as ATLAS and FFTW. Here the high up-front installation cost can amortized over many future uses. In this paper we examine a hybrid approach. Active learning in an Explanation-Based paradigm allows the hybrid system to greatly increase the search range while drastically reducing the search time. Individual search points are analyzed for their information content using an known-imprecise qualitative analytic model. Next-search-points are chosen which have the highest expected information content with respect to refinement of the empirical model being constructed. To evaluate our approach we compare it with a leading analytic model and a leading empirical model. Our results show that the performance of the libraries generated using the hybrid approach is comparable to the performance of libraries generated via extensive search techniques and much better than that of the libraries generated by optimization based solely on an analytic model.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers
Pages259-273
Number of pages15
DOIs
StatePublished - 2006
Event18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005 - Hawthorne, NY, United States
Duration: Oct 20 2005Oct 22 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4339 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005
CountryUnited States
CityHawthorne, NY
Period10/20/0510/22/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Analytic models and empirical search: A hybrid approach to code optimization'. Together they form a unique fingerprint.

  • Cite this

    Epshteyn, A., Garzaran, M. J., DeJong, G., Padua, D., Ren, G., Li, X., Yotov, K., & Pingali, K. (2006). Analytic models and empirical search: A hybrid approach to code optimization. In Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers (pp. 259-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4339 LNCS). https://doi.org/10.1007/978-3-540-69330-7_18