Automatically Tuned Linear Algebra Software - Optimization Approach

Optimization Approach

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. Parameterization -- searching over the parameter space of a function, used for blocking factor, cache edge, ...
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 data and 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:

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

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

Since we have ops with only data, many opportunities for optimization