Linnea: a compiler for mapping linear algebra problems onto high-performance kernel libraries

Barthels, Henrik; Bientinesi, Paolo (Thesis advisor); Naumann, Uwe (Thesis advisor); Püschel, Markus (Thesis advisor)

Aachen : RWTH Aachen University (2022, 2023)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2022

Abstract

The translation of linear algebra computations to efficient code consisting of kernels as provided by libraries such as BLAS and LAPACK is a frequently encountered problem in different areas of science and engineering. Since the manual translation is a tedious, error-prone and time consuming process that requires a lot of expertise, several high-level languages and libraries have been developed that solve this problem automatically. Example include Matlab, Julia, Eigen, and Armadillo. These languages and libraries allow users to describe linear algebra computations in code which closely resembles the mathematical description of the problem; this high-level code is then internally translated to sequences of kernel calls. Unfortunately, while those languages and libraries increase the productivity of the user, it has been shown that this automatic translation frequently results in suboptimal code. In this thesis, we present Linnea, a domain-specific compiler that automatically translates the high-level description of linear algebra problems to efficient sequences of kernel calls. Linnea aims to combine the ease-of-use of high-level languages with the performance of low-level code written by an expert. Unlike other languages and libraries, Linnea extensively makes use of knowledge about linear algebra: Algebraic identities such as associativity, commutativity, and distributivity are used to rewrite the input problem. In addition, Linnea is able to infer matrix properties and detect common subexpressions. To explore the large space of candidate solutions, Linnea uses a custom best-first search algorithm that quickly finds a first solution, and increasingly better solutions when given more time. This thesis concludes with an extensive experimental evaluation of Linnea on 25 application and 100 synthetic test problems, both with sequential and parallel execution. The results show that Linnea almost always outperforms Matlab, Julia, Eigen and Armadillo, with speedups up to and exceeding 10x. For all test problems, Linnea finds a first solution in less than one second; finding a close to optimal solution rarely takes longer than a few minutes.

Institutions

• Department of Computer Science [120000]
• Informatik 12 (Software and Tools for Computational Engineering Group) [123120]