Analytical Performance Modeling and Prediction for Linear Algebra Algorithms

Team

• Roman Iakymchuk (graduated)
• Paolo Bientinesi (supervisor)

Linear Algebra libraries provide the building blocks for virtually every scientific application. They contain a variety of algorithms and routines to solve a fairly limited number of operations. It is well known that performance for these algorithms is affected by a range of parameters, including features of the computing platform and properties of the problem at hand. The algorithm of choice, in terms of metrics like speed or accuracy, depends on the specific combination of parameters.

Given a number of mathematically equivalent algorithms and a target computing system, we wish to select the best performing algorithm with a limited use of resources. The standard practice is to run hundreds of experiments, timing all the algorithms for each different computing configuration.

In sharp contrast, we aim at a compositional analysis. We will investigate how performance of algorithms can be expressed in terms of performance of BLAS routines, and we will study the problem of building models by running a limited number of sampling tests. The ultimate goal is to be able to predict performance without even executing the algorithm.