Run-time program generation and empirical optimization

The goal of this project is to use all the tools of run-time program generation and empirical optimization (a.k.a. auto-tuning) to get speed-ups on problems involving large amounts of data. It is well known that staging - dividing a computation into two parts, where the first part, based on some "early" portion of the data, produces code for the second part - can result in significant speed-ups. The jumping off point of this research is the observation that when the "early" data is voluminous, the most obvious methods of staging do not produce speed-ups, because the code gets too large. A further well-known fact is that the best code on one machine may not be the best on all machines; determining, at run time, the best method for solving a particular problem is know as "auto-tuning," or "empirical optimization."

We are currently focusing on one very well-known problem: matrix-vector multiplication:

Suppose we are given a matrix M (of the kind typically found in scientific computations - large, sparse, usually banded), which is to be multiplied by dense vectors repeatedly (hundreds or thousands of times). Can we generate code (and data) to optimize these multiplications?

In short, we are looking at staging matrix-vector multiplication.

The project has three broad components:

Finding the best methods. These methods may involve generating code specialized for M and/or building a new representation for M.
Determining, at run time, which of the available methods is best for a particular matrix one a particular machine.
Efficiently generating code for the chosen method (if necessary).

Details can be found in our publications and working papers.

This project is supported by the National Science Foundation under grant CCF 10-17077, "Run-time program generation and empirical optimization."

Last updated on Fri Jul 6 09:00:35 CDT 2012