A basic linear algebra compiler for structured matrices

Daniele G. Spampinato, Markus PüschelCGO 2016 · DOI

TL;DR

This paper introduces a compiler that generates highly optimized C code for basic linear algebra computations (BLACs) involving structured matrices (like triangular or symmetric). By combining existing compiler techniques with a novel way to represent matrix structures, they achieve performance competitive with highly optimized libraries like Intel MKL, especially for smaller, fixed-size computations.

What Problem Does This Paper Address?

Many scientific and engineering applications rely heavily on matrix computations. While optimized libraries like BLAS and LAPACK exist, they often struggle with:

  1. Limited Structure Support: They might not have specific functions for certain matrix structures (e.g., symmetric, triangular), forcing users to treat them as generic matrices, losing potential performance gains.
  2. Small Computations: Optimized libraries are often geared towards large-scale operations. Smaller, fixed-size computations, common in many algorithms, might not be as efficiently handled.
  3. Lack of Specialization: Fixed-size computations with specific structures could benefit from highly specialized, faster code, which is not typically generated by general-purpose libraries.

This paper aims to bridge this gap by creating a compiler that can automatically generate efficient code for these "structured BLACs" (sBLACs).

Methods

The core of the paper is an extension of the LGen compiler, which previously generated optimized code for generic BLACs. The key innovations are:

  • Structured Matrix Representation: They introduce a way to mathematically capture matrix structures (like lower/upper triangular, symmetric) using polyhedral sets and maps. This allows the compiler to reason about the inherent properties of these matrices.
  • E-CLooG Module: A new module, E-CLooG, is integrated into LGen. This module takes the structured BLAC and translates it into an intermediate representation (Σ-LL) that explicitly accounts for matrix structures. This involves:
  • Structure Inference: Automatically inferring the structure of intermediate results based on the input structures and the operation.
  • Redundancy Elimination: Exploiting structural properties to avoid unnecessary computations (e.g., multiplying by zero in triangular matrices).
  • Access Pattern Analysis: Using the structure information to optimize data access patterns.
  • Vectorization Integration: The approach is designed to work seamlessly with vectorization (SIMD instructions), generating tiled code where the structure information is propagated to the tiles.
  • Extensible Framework: The methodology is designed to be extensible to a wide range of matrix structures beyond triangular and symmetric, including banded and composite matrices.

Datasets

Not discussed in the paper. The evaluation uses synthetic benchmarks representing different categories of sBLACs (BLAS, BLAS-like, Non-BLAS composite).

Key Insights and Ideas

  • Structure is Key to Optimization: The paper strongly demonstrates that explicitly representing and exploiting matrix structure is crucial for achieving significant performance gains, even for small computations.
  • Polyhedral Model for Structure: Using polyhedral sets and maps provides a powerful and extensible mathematical framework to define and manipulate matrix structures within a compiler.
  • Generative Approach Pays Off: A compiler that can automatically generate specialized code for structured computations offers a flexible and efficient alternative to hand-tuned libraries, especially when dealing with a variety of structures.
  • Small Computations Matter: The work highlights that optimizing small, fixed-size computations is important and can be achieved through compiler-based specialization.

Key Results

The paper presents experimental results comparing their LGen-generated code against Intel MKL and a naive baseline implementation.

  • BLAS Category (dsyrk, dtrsv): LGen achieved up to 2.5x speedup over MKL for dsyrk when data fit in L1 cache, and was generally 1.6x faster than hand-optimized code. For dtrsv, LGen was competitive, and importantly, the old LGen (without structure support) couldn't handle it at all.
  • BLAS-like Category (dlusmm, dsylmm): LGen showed significant speedups, up to 3.5x faster than icc and 2x faster than MKL for dlusmm. For dsylmm, it was up to 7x faster than icc and 1.4x faster than MKL.
  • Non-BLAS Category: Performance profiles were similar to BLAS-like, indicating the approach effectively handles composite operations.

Limitations and Future Work

  • Limitations:
    • Currently, the approach doesn't exploit structure within the v-BLACs themselves (e.g., structured blocks on the diagonal after tiling). This could be a source of further optimization for larger v.
  • The current implementation assumes matrices are stored as full arrays, even if parts are redundant (e.g., upper triangle of a lower triangular matrix). More specialized storage formats (like for diagonal or tridiagonal matrices) are not yet fully utilized.
  • Future Work:
    • Include more matrix storage formats.
  • Exploit structures for generating higher-level linear algebra functions.
  • Further investigate optimizations within v-BLACs for structured blocks.

Summary updated

BibTeX
@inproceedings{spampinato2016basic,
  author = {Daniele G. Spampinato and Markus Püschel},
  title = {{A basic linear algebra compiler for structured matrices}},
  booktitle = {CGO},
  year = {2016},
  doi = {10.1145/2854038.2854060},
}
Figure