|
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