Linnea

ACM Transactions on Mathematical Software, vol. 47, pp. 1–26

Abstract

The translation of linear algebra computations into efficient sequences of library calls is a non-trivial task that requires expertise in both linear algebra and high-performance computing. Almost all high-level languages and libraries for matrix computations (e.g., Matlab, Eigen) internally use optimized kernels such as those provided by BLAS and LAPACK; however, their translation algorithms are often too simplistic and thus lead to a suboptimal use of said kernels, resulting in significant performance losses. To combine the productivity offered by high-level languages, and the performance of low-level kernels, we are developing Linnea, a code generator for linear algebra problems. As input, Linnea takes a high-level description of a linear algebra problem; as output, it returns an efficient sequence of calls to high-performance kernels. Linnea uses a custom best-first search algorithm to find a first solution in less than a second, and increasingly better solutions when given more time. In 125 test problems, the code generated by Linnea almost always outperforms Matlab, Julia, Eigen, and Armadillo, with speedups up to and exceeding 10×.

Authors 3

1. Henrik Barthels Aachen

   RWTH Aachen University · Aachen Institute for Advanced Study in Computational Engineering Science

   Affiliation as printed

   AICES, RWTH Aachen University, Germany

2. Christos Psarras Aachen

   RWTH Aachen University · Aachen Institute for Advanced Study in Computational Engineering Science

   Affiliation as printed

   AICES, RWTH Aachen University, Germany

3. Paolo Bientinesi

   Umeå University

   Affiliation as printed

   Umeå Universitet, Umeå, Sweden