cfaed Seminar Series

cfaed Seminar Series

Daniele Spampinato , ETH Zurich, CH

LGen: A Basic Linear Algebra compiler

06.10.2016 (Thursday) Andreas-Pfitzmann-Bau 1004 (Großes Ratszimmer) , Nöthnitzer Str. 46 , 01187 Dresden


Many problems in science and engineering are in practice modeled and solved through matrix computations. In particular, applications in media processing, control, graphics, and other domains may require efficient small-scale linear algebra computations. However, most existing high performance libraries for linear algebra, such as ATLAS or Intel MKL are more geared towards large-scale problems (matrix sizes in the hundreds and larger) and towards specific interfaces (e.g., BLAS). Furthermore, the matrices involved in a computation may have structures such as symmetric or triangular, which reduce the operations count needed to compute it. The BLAS interface provides a small set of structured matrix computations, chosen to serve a certain set of higher level functions (LAPACK). However, if a structured computation is not supported, a user might have to resort to a generic library, losing the benefits of the structures.

In this talk we present LGen: a compiler for small-scale, basic linear algebra computations. The input to LGen is a fixed-size linear algebra expression with structures; the output is a corresponding C function optionally including intrinsics to efficiently use SIMD vector extensions.  LGen is designed after Spiral and generates code using two levels of mathematical domain-specific languages (DSLs). The DSLs are used to perform tiling, loop fusion, and vectorization at a high level of abstraction, before the final code is generated. We capture matrix structures mathematically with techniques based on polyhedral compilation. In this talk we consider upper/lower triangular and symmetric matrices but the approach is extensible to a larger set including blocked structures. In addition, search is used to select among alternative generated implementations.

We run experiments on a modern Intel platform against the Intel MKL library and a baseline implementation showing competitive performance results for both BLAS and non-BLAS basic linear algebra computations.


Daniele Spampinato is a Ph.D. candidate in computer science at ETH Zurich, Switzerland, under the supervision of Prof. Markus Püschel. His research interests focus on the problem of representing mathematical expert knowledge for high-performance program synthesis. He graduated in computer engineering at NTNU, Norway, and at Politecnico di Milano, Italy.

Go back