Linnea: Automatic Generation of Efficient Linear Algebra Programs

Henrik Barthels
RWTH Aachen University

13 February 2019
13:30 - 14:30
G.45
Earl Mountbatten Building

Abstract

The evaluation of linear algebra expressions is a central part of both languages for scientific computing such as Julia and Matlab, and libraries such as Eigen, Blaze, and NumPy. However, the existing strategies are still rather primitive. At present, the only way to achieve high performance is by handcoding algorithms using libraries such as BLAS and LAPACK, a task that requires extensive knowledge in linear algebra, numerical linear algebra and high-performance computing. We present Linnea, a synthesis tool that automates the translation of the mathematical description of a linear algebra problem to an efficient sequence of calls to BLAS and LAPACK kernels. The main idea of Linnea is to construct a search graph that represents a large number of programs, taking into account knowledge about linear algebra. The algebraic nature of the domain is used to reduce the size of the search graph, without reducing the size of the search space that is explored. Experiments show that 1) the code generated by Linnea outperforms standard linear algebra languages and libraries, and 2) in contrast to the development time of human experts, the generation takes only few minutes.

Bio

Henrik Barthels is a PhD student in his 4th year in the High-Performance and Automatic Computing group at RWTH Aachen University. As part of his PhD studies, he works on code generation, linear algebra algorithms, and pattern matching on symbolic expression.

Host: Artem Shinkarov