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 conferencePaper

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 compete 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)
Pages63-76
Number of pages14
StatePublished - Jul 28 2003
EventACM SIGPLAN Conference on Programming Language Design and Implementation - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Other

OtherACM SIGPLAN Conference on Programming Language Design and Implementation
CountryUnited States
CitySan Diego, CA
Period6/9/036/11/03

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

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. 63-76. Paper presented at ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, United States.

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.

2003. 63-76 Paper presented at ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, United States.

Research output: Contribution to conferencePaper

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', Paper presented at ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, United States, 6/9/03 - 6/11/03 pp. 63-76.
Yotov K, Li X, Ren G, Cibulskis M, DeJong G, Garzaran M et al. A comparison of empirical and model-driven optimization. 2003. Paper presented at ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, United States.
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. Paper presented at ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, United States.14 p.
@conference{52671a8394bf49cf8f0b01714f79d5ee,
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 compete 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 = "7",
day = "28",
language = "English (US)",
pages = "63--76",
note = "ACM SIGPLAN Conference on Programming Language Design and Implementation ; Conference date: 09-06-2003 Through 11-06-2003",

}

TY - CONF

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/7/28

Y1 - 2003/7/28

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 compete 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 compete 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=0038378242&partnerID=8YFLogxK

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

M3 - Paper

AN - SCOPUS:0038378242

SP - 63

EP - 76

ER -