Automatically Tuned Linear Algebra Software

ATLAS provides a full implementation of the BLAS APIs as well as some additional functions from LAPACK, a higher-level library built on top of BLAS. In BLAS, functionality is divided into three groups called levels 1, 2 and 3.

• Level 1 contains vector operations of the form

${\displaystyle \mathbf {y} \leftarrow \alpha \mathbf {x} +\mathbf {y} \!}$

as well as scalar dot products and vector norms, among other things.

• Level 2 contains matrix-vector operations of the form

${\displaystyle \mathbf {y} \leftarrow \alpha A\mathbf {x} +\beta \mathbf {y} \!}$

as well as solving ${\displaystyle T\mathbf {x} =\mathbf {y} }$ for ${\displaystyle \mathbf {x} }$ with ${\displaystyle T}$ being triangular, among other things.

• Level 3 contains matrix-matrix operations such as the widely used General Matrix Multiply (GEMM) operation

${\displaystyle C\leftarrow \alpha AB+\beta C\!}$

as well as solving ${\displaystyle B\leftarrow \alpha T^{-1}B}$ for triangular matrices ${\displaystyle T}$, among other things.

The optimization approach is called Automated Empirical Optimization of Software (AEOS), which identifies four fundamental approaches to computer assisted optimization of which ATLAS employs three:[1]

1. Parameterization—searching over the parameter space of a function, used for blocking factor, cache edge, etc.
2. Multiple implementation—searching through various approaches to implementing the same function, e.g., for SSE support before intrinsics made them available in C code
3. Code generation—programs that write programs incorporating what knowledge they can about what will produce the best performance for the system

• Optimization of the level 1 BLAS uses parameterization and multiple implementation

Every ATLAS level 1 BLAS function has its own kernel. Since it would be difficult to maintain thousands of cases in ATLAS there is little architecture specific optimization for Level 1 BLAS. Instead multiple implementation is relied upon to allow for compiler optimization to produce high performance implementation for the system.

• Optimization of the level 2 BLAS uses parameterization and multiple implementation

With ${\displaystyle N^{2}}$ data and ${\displaystyle N^{2}}$ operations to perform the function is usually limited by bandwidth to memory, and thus there is not much opportunity for optimization

All routines in the ATLAS level 2 BLAS are built from two Level 2 BLAS kernels:

• • GEMV—matrix by vector multiply update:

${\displaystyle \mathbf {y} \leftarrow \alpha A\mathbf {x} +\beta \mathbf {y} \!}$

• • GER—general rank 1 update from an outer product:

${\displaystyle A\leftarrow \alpha \mathbf {x} \mathbf {y} ^{T}+A\!}$

• Optimization of the level 3 BLAS uses code generation and the other two techniques

Since we have ${\displaystyle N^{3}}$ ops with only ${\displaystyle N^{2}}$ data, there are many opportunities for optimization

Most of the Level 3 BLAS is derived from GEMM, so that is the primary focus of the optimization.

${\displaystyle O(n^{3})}$ operations vs. ${\displaystyle O(n^{2})}$ data

The intuition that the ${\displaystyle n^{3}}$ operations will dominate over the ${\displaystyle n^{2}}$ data accesses only works for roughly square matrices. The real measure should be some kind of surface area to volume. The difference becomes important for very non-square matrices.

When integrating the ATLAS BLAS with LAPACK an important consideration is the choice of blocking factor for LAPACK. If the ATLAS blocking factor is small enough the blocking factor of LAPACK could be set to match that of ATLAS.

To take advantage of recursive factorization, ATLAS provides replacement routines for some LAPACK routines. These simply overwrite the corresponding LAPACK routines from Netlib.

Installing ATLAS on a particular platform is a challenging process which is typically done by a system vendor or a local expert and made available to a wider audience.

For many systems, architectural default parameters are available; these are essentially saved searches plus the results of hand tuning. If the arch defaults work they will likely get 10-15% better performance than the install search. On such systems the installation process is greatly simplified.

• Automatically Tuned Linear Algebra Software on SourceForge.net
• User contribution to ATLAS
• A Collaborative guide to ATLAS Development
• The FAQ has links to the Quick reference guide to BLAS and Quick reference to ATLAS LAPACK API reference
• Microsoft Visual C++ Howto for ATLAS