A comparison of empirical and model-driven optimization

Kamen Yotov, Xiaoming Li, Gang Ren, Michael Cibulskis, Gerald DeJong, Maria Garzaran, David Padua, Keshav Pingali, Paul Stodghill, Peng Wu

Research output: Contribution to journalConference article

Abstract

Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not complete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.

Original languageEnglish (US)
Pages (from-to)63-76
Number of pages14
JournalACM SIGPLAN Notices
Volume38
Issue number5
DOIs
StatePublished - May 2003
EventProceedings of the ACM Sigplan 2003 Conference on Programming Language Design and Implementation - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Fingerprint

Engines
Hardware
Linear algebra
Experiments

Keywords

  • BLAS
  • Blocking
  • Code generation
  • Compilers
  • Empirical optimization
  • Memory hierarchy
  • Model-driven optimization
  • Program transformation
  • Tiling
  • Unrolling

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Cite this

Yotov, K., Li, X., Ren, G., Cibulskis, M., DeJong, G., Garzaran, M., ... Wu, P. (2003). A comparison of empirical and model-driven optimization. ACM SIGPLAN Notices, 38(5), 63-76. https://doi.org/10.1145/780822.781140

A comparison of empirical and model-driven optimization. / Yotov, Kamen; Li, Xiaoming; Ren, Gang; Cibulskis, Michael; DeJong, Gerald; Garzaran, Maria; Padua, David; Pingali, Keshav; Stodghill, Paul; Wu, Peng.

In: ACM SIGPLAN Notices, Vol. 38, No. 5, 05.2003, p. 63-76.

Research output: Contribution to journalConference article

Yotov, K, Li, X, Ren, G, Cibulskis, M, DeJong, G, Garzaran, M, Padua, D, Pingali, K, Stodghill, P & Wu, P 2003, 'A comparison of empirical and model-driven optimization', ACM SIGPLAN Notices, vol. 38, no. 5, pp. 63-76. https://doi.org/10.1145/780822.781140
Yotov, Kamen ; Li, Xiaoming ; Ren, Gang ; Cibulskis, Michael ; DeJong, Gerald ; Garzaran, Maria ; Padua, David ; Pingali, Keshav ; Stodghill, Paul ; Wu, Peng. / A comparison of empirical and model-driven optimization. In: ACM SIGPLAN Notices. 2003 ; Vol. 38, No. 5. pp. 63-76.
@article{561b96b77e9b47b6adb3323200aa8933,
title = "A comparison of empirical and model-driven optimization",
abstract = "Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not complete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.",
keywords = "BLAS, Blocking, Code generation, Compilers, Empirical optimization, Memory hierarchy, Model-driven optimization, Program transformation, Tiling, Unrolling",
author = "Kamen Yotov and Xiaoming Li and Gang Ren and Michael Cibulskis and Gerald DeJong and Maria Garzaran and David Padua and Keshav Pingali and Paul Stodghill and Peng Wu",
year = "2003",
month = "5",
doi = "10.1145/780822.781140",
language = "English (US)",
volume = "38",
pages = "63--76",
journal = "ACM SIGPLAN Notices",
issn = "1523-2867",
publisher = "Association for Computing Machinery (ACM)",
number = "5",

}

TY - JOUR

T1 - A comparison of empirical and model-driven optimization

AU - Yotov, Kamen

AU - Li, Xiaoming

AU - Ren, Gang

AU - Cibulskis, Michael

AU - DeJong, Gerald

AU - Garzaran, Maria

AU - Padua, David

AU - Pingali, Keshav

AU - Stodghill, Paul

AU - Wu, Peng

PY - 2003/5

Y1 - 2003/5

N2 - Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not complete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.

AB - Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not complete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.

KW - BLAS

KW - Blocking

KW - Code generation

KW - Compilers

KW - Empirical optimization

KW - Memory hierarchy

KW - Model-driven optimization

KW - Program transformation

KW - Tiling

KW - Unrolling

UR - http://www.scopus.com/inward/record.url?scp=10744232785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10744232785&partnerID=8YFLogxK

U2 - 10.1145/780822.781140

DO - 10.1145/780822.781140

M3 - Conference article

AN - SCOPUS:10744232785

VL - 38

SP - 63

EP - 76

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

SN - 1523-2867

IS - 5

ER -