Scale Use Example
The Scale compiler is being used successfully in branch prediction research to determine
- Does high level information allow better branch prediction?
- Can use-def information and control dependence information provide better branch prediction?
- Can easy modifications to Scale provide the information needed?
Branch Prediction Research
The hypothesis under test is whether branch prediction hardware
can be more accurate and space efficient if precise information is fed
to the predictor.
This method uses precise def-use information
relative to the branch conditional in conjunction with a control
dependence graph to determine the set of important junctures in the
program as a more meaningful and, thus, more predictive history.
Traditional Branch Prediction
Traditional branch prediction schemes input a non-selective history of the last N branches.
Typical branch analysis systems start with the object code and require a framework be built that mimics the information that was present during compilation.
This is a significant undertaking and, furthermore, not portable because it must be tailored to a machine's underlying instruction set.
Results
- Using Scale, the initial experimental analysis system was constructed in under a week.
- Scale allows easy manipulation of code at the source code level through its well-defined API and, thus, is machine independent.
- The system tagged each branch and generated the list of related branch points from the use-def chain provided by the SSA form of the Scribble CFG to use as history information.
- Since more precise information typically results in fewer history bits, the expected benefits are better predictions and faster warm-up of the branch prediction state.
Return to Scale home page.
(Last changed: March 21, 2007.)