Hydra: Automatic algorithm exploration from linear algebra equations

Alexandre X. Duchateau; David Padua; Denis Barthou

doi:10.1109/CGO.2013.6494999

Hydra: Automatic algorithm exploration from linear algebra equations

Alexandre X. Duchateau, David Padua, Denis Barthou

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Hydra accepts an equation written in terms of operations on matrices and automatically produces highly efficient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with different locality behavior and/or different parallel execution profiles. Next, Hydra applies empirical search over this space of possible solvers to identify the most efficient version. In this way, Hydra enables the automatic production of efficient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intel's MKL.

Original language	English (US)
Title of host publication	Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013
DOIs	https://doi.org/10.1109/CGO.2013.6494999
State	Published - 2013
Event	11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013 - Shenzhen, China Duration: Feb 23 2013 → Feb 27 2013

Publication series

Name	Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013

Other

Other	11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013
Country/Territory	China
City	Shenzhen
Period	2/23/13 → 2/27/13

Keywords

Automatic Derivation
Linear Algebra

ASJC Scopus subject areas

Applied Mathematics
Control and Optimization

Online availability

10.1109/CGO.2013.6494999

Library availability

Discover UIUC Full Text

Cite this

Duchateau, A. X., Padua, D., & Barthou, D. (2013). Hydra: Automatic algorithm exploration from linear algebra equations. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013 Article 6494999 (Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013). https://doi.org/10.1109/CGO.2013.6494999

Hydra: Automatic algorithm exploration from linear algebra equations. / Duchateau, Alexandre X.; Padua, David; Barthou, Denis.
Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013. 2013. 6494999 (Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Duchateau, AX, Padua, D & Barthou, D 2013, Hydra: Automatic algorithm exploration from linear algebra equations. in Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013., 6494999, Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013, 11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013, Shenzhen, China, 2/23/13. https://doi.org/10.1109/CGO.2013.6494999

@inproceedings{d2f6c07f79b0418289691ec67628fcf3,

title = "Hydra: Automatic algorithm exploration from linear algebra equations",

abstract = "Hydra accepts an equation written in terms of operations on matrices and automatically produces highly efficient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with different locality behavior and/or different parallel execution profiles. Next, Hydra applies empirical search over this space of possible solvers to identify the most efficient version. In this way, Hydra enables the automatic production of efficient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intel's MKL.",

keywords = "Automatic Derivation, Linear Algebra",

author = "Duchateau, {Alexandre X.} and David Padua and Denis Barthou",

year = "2013",

doi = "10.1109/CGO.2013.6494999",

language = "English (US)",

isbn = "9781467355254",

series = "Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013",

booktitle = "Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013",

note = "11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013 ; Conference date: 23-02-2013 Through 27-02-2013",

}

TY - GEN

T1 - Hydra

T2 - 11th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013

AU - Duchateau, Alexandre X.

AU - Padua, David

AU - Barthou, Denis

PY - 2013

Y1 - 2013

N2 - Hydra accepts an equation written in terms of operations on matrices and automatically produces highly efficient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with different locality behavior and/or different parallel execution profiles. Next, Hydra applies empirical search over this space of possible solvers to identify the most efficient version. In this way, Hydra enables the automatic production of efficient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intel's MKL.

AB - Hydra accepts an equation written in terms of operations on matrices and automatically produces highly efficient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with different locality behavior and/or different parallel execution profiles. Next, Hydra applies empirical search over this space of possible solvers to identify the most efficient version. In this way, Hydra enables the automatic production of efficient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intel's MKL.

KW - Automatic Derivation

KW - Linear Algebra

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

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

U2 - 10.1109/CGO.2013.6494999

DO - 10.1109/CGO.2013.6494999

M3 - Conference contribution

AN - SCOPUS:84876913606

SN - 9781467355254

T3 - Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013

BT - Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2013

Y2 - 23 February 2013 through 27 February 2013

ER -

Hydra: Automatic algorithm exploration from linear algebra equations

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this