Daniele G. Spampinato and Markus Püschel (Proc. International Symposium on Code Generation and Optimization (CGO), pp. 23-32, 2014)
A Basic Linear Algebra Compiler
Comment: Best paper award nominee (4 out of 29)
Preprint (2.4 MB)
Published paper (link to publisher)

Many applications in media processing, control, graphics, and other domains require efficient small-scale linear algebra computations. However, most existing high performance libraries for linear algebra, such as ATLAS or Intel's MKL are more geared towards large-scale problems (matrix sizes in the hundreds and larger) and towards specific interfaces (e.g., BLAS). In this paper we present LGen: a compiler for small-scale, basic linear algebra computations. The input to LGen is a fixed-size linear algebra expression; the output is a corresponding C function optionally including intrinsics to efficiently use SIMD vector extensions. LGen 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. In addition, search is used to select among alternative generated implementations. We show benchmarks of code generated by LGen against Intel's MKL and IPP as well as against alternative generators, such as the C++ template-based Eigen and the BTO compiler. The achieved speed-up is typically about a factor of two to three.

SIMD vectorization, Numerical kernels we consider, Beyond transforms, Synthesis, Linear algebra