Clak: An Automatic Environment for Linear Algebra Equations
Final Report Abstract
With this project, we made several lasting contributions. • Linear algebra compilers. As we set out to do, we built Linnea, a linear algebra compiler for matrix expressions that arise in end applications. Linnea offers a high-level input language, enabling domain scientists to code at the same level of abstraction as they reason. Linnea was designed with extensibility in mind, to make it possible for follow-up projects to focus on issues such as parallelism, memory consumption, and performance modeling. In collaboration with ETH Zürich, we also developed the prototype of a second compiler, SLinGen, specifically designed for small operations, that is, for matrices that fit in cache. Even though SLinGen did not reach the same level of maturity and generality of Linnea, it clearly demonstrated that in the small-scale regime there are wide margins for gains over current state-of-the-art libraries. • GMC algorithm. One the most important building blocks for Linnea is the Generalized Matrix Chain algorithm which we developed. The standard version of the problem (Matrix Chain) is only concerned with the optimal parentesisation of a sequence of matrix products. We tackled the more general problem in which matrices can be transposed, inverted, re-used, and have properties. In constrast to a time-consuming exhaustive search, with the GMC algorithm, the optimal solution is found constructively. The GMC algorithm should become an integral part in any high-level language and compiler for linear algebra. • Pattern matching. The algorithm-generation process in Linnea is based on symbolic manipulation of a target linear algebra expression. Since linear algebra has both commutative and non-commutative operators, we developed and released MatchPy, a pattern-matching library that offers functionality similar to that provided by Mathematica, but as an opensource and extensible package. MatchPy is now widely adopted. • Benchmarks. In order to assess the quality of any language and compiler for high-level matrix expressions, we created two benchmarks, for a total of 125 target linear algebra expressions. These benchmarks are meant both as a stress test (with corner cases), and as representative use cases, as they arise in practice.
Publications
- Large-Scale Linear Regression: Development of High-Performance Routines. Applied Mathematics and Computation, Vol. 275, 411–421, 2016
A. Frank, D. Fabregat-Traver and P. Bientinesi
(See online at https://doi.org/10.1016/j.amc.2015.11.078) - Efficient Pattern Matching in Python. Proceedings of the 7th Workshop on Python for High-Performance and Scientific Computing (PyHPC 2017), November 2017
M. Krebber, H. Barthels and P. Bientinesi
(See online at https://doi.org/10.1145/3149869.3149871) - Linnea: Compiling Linear Algebra Expressions to High-Performance Code. Proceedings of the 8th International Workshop on Parallel Symbolic Computation (PASCO 17), 2017
H. Barthels and P. Bientinesi
(See online at https://doi.org/10.1145/3115936.3115937) - MatchPy: A Pattern Matching Library. Proceedings of the 15th Python in Science Conference (SciPy 2017), July 2017
M. Krebber, H. Barthels and P. Bientinesi
(See online at https://doi.org/10.25080/shinma-7f4c6e7-00b) - MatchPy: Pattern Matching in Python. Journal of Open Source Software, Volume 3(26), pp.2, June 2018
M. Krebber and H. Barthels
(See online at https://doi.org/10.21105/joss.00670) - Program Generation for Small-Scale Linear Algebra Applications. Proceedings of the International Symposium on Code Generation and Optimization (CGO 18), 2018
D. Spampinato, D. Fabregat-Traver, M. Püschel and P. Bientinesi
(See online at https://doi.org/10.1145/3168812) - The Generalized Matrix Chain Algorithm. Proceedings of the International Symposium on Code Generation and Optimization (CGO 18), 2018
H. Barthels, M. Copik and P. Bientinesi
(See online at https://doi.org/10.1145/3168804)
