Auto-tuning

Automatic Performance Tuning or “Auto-tuning,” is an empirical, feedback-driven performance optimization technique designed to maximize performance across a wide variety of architectures without sacrificing portability or productivity. Over the years, auto-tuning has expanded from simple loop tiling and unroll-and-jam to encompass transformations to data structures, parallelization, and algorithmic parameters. 

Perhaps the genesis of auto-tuning was PHiPAC (Portable High Performance ANSI C) and eventually ATLAS. When optimizing Matrix-Matrix multiplication, one often cache-blocks the computation to maximize locality in each level of the cache hierarchy. This transforms the reference three-nested loop example into a 6-deep loop nest. Rather than hard coding the tiling, researchers observed they could simply leverage the compute capabilities of modern processors to search over all possibilities to automatically find the fastest configuration for the target machine.

Subsequently, auto-tuning was applied to sparse linear algebra, principally Sparse Matrix-Vector Multiplication (SpMV).  Unlike dense matrices, most elements of a sparse matrix are zero.  As such, most data structures only encode the nonzeros.  Indexing into this data structure can impair in-core performance and increase data movement.  As a result, SpMV performance often falls below its Roofline bound.  To ameliorate this, one can select alternate data structures on a matrix by matrix or cache block by cache block basis.  Alternate data structures can amortize metadata, and increase instruction- and data-level parallelism.  As a result, one can improve performance.  Rather than requiring the user to select and implement a format, the Optimized Sparse Kernel Interface (OSKI) attempted to auto-tune the process.

Research Topics

Broadly speaking, auto-tuning is premised on three fundamental research topics:

• creating novel application- and architecture-relevant optimizations and their associated parameter space
• automating the generation of code for this optimization space
• efficiently searching this optimization space (a mathematical optimization problem).

At LBL, our research has primarily focused on researching and prototyping novel optimizations and automating the code generation process. This has been applied in several projects beginning with an LDRD, followed by our original X-Stack auto-tuning project, and finally SUPER and our current X-Stack project: X-Tune.

Researchers

• Samuel Williams 

Publications