An Investigation of Value Prediction
What is value prediction?
In class, we have studied many transformations for improving program
locality. All of these transformations attempt to improve the
probability of finding a given memory location in cache by reducing
the distance between successive accesses to that location.
A very different approach to tackling the "memory wall" is value
prediction. The basic idea is to have the processor guess what value
will be returned by a load instruction, and have it compute
speculatively with this value. When the load completes, the actual
value returned by the memory system is compared with the guess; if the
guess is correct, the processor simply notes that fact and continues,
but if the guess is incorrect, the processor rolls back the
computation and recomputes with the actual value.
Schemes for predicting values range from simple to fairly complex. A
simple scheme is for the processor to guess that the value is zero. A
more sophisticated approach is to use the address of the load
instruction to determine the predicted value; for example, the
processor can guess that the value will be the same as the value that
was last returned by that load instruction. This latter scheme
requires the processor to maintain a table of (key,value) pairs in
which the key is the address of a load instruction, and the value is
the data value that was last returned by that load.
At first sight, value prediction seems like a weird idea, but some
studies have shown that upto 80% of load values in some codes can be
predicted using relatively simple schemes. However, we are not aware
of any careful studies that explain why value prediction works so well
on such codes. One possibility is that many of these values are
floating-point constants; since most instruction sets do not permit
immediate floating-point constants in instructions, these constants
must be loaded from memory. Another possibility is that some of these
are runtime constants whose values are not known till program
execution begins, but are invariant while the program executes. Yet
another possibility is that the compiler is doing a poor job of
lifting out loop-invariant computations.
The goal of this project is to understand why value prediction works,
by relating load instructions to source-level constructs,
understanding why the load value is predictable, and why the compiler
could not replace the load with an immediate constant, or a single
load.
How to proceed
- You will first need to collect a set of papers on value
prediction and read what has been done. To get you started, we are
giving you two documents to read. You should also look at the
Wisconsin Multiscalar project. Search engines like Google and
Altavista are also useful.
You will find that most of these papers describe variations on the
basic load value prediction ideas described earlier in this page.
Many of them are experimental studies that try to determine for
example how large the table of (address,value) pairs should be in
practice, and so on. While it is useful for you to read these papers,
remember that that is not the primary focus of this project.
- What experimental setup will you need to do this study?
You will need to be able to (i) compile programs to some instruction
set, (ii) execute the compiled code, (iii) implement a load value
predictor of your choice, (iv) figure out which load values are
predictable, and trace those instructions back to the source code.
The Berkeley team whose project report is linked below used the
Wisconsin SimpleScalar toolset. You may want to download this toolset
and see if you can use it for your study.
- What benchmarks will you use? Some mix of integer and
floating-point benchmarks will be good. We can help you with these.
- What instruction set will you use? If you want access to a Sparc
machine, we can get you an account int the CS department.
- How will you trace load instructions back to the source?
- What categories of load value constants will you look for?
Reading list to get you started