cfaed Seminar Series

Abstract:

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.