Abstract:

Dynamic branch prediction in high-performance processors is a
specific instance of a general Time Series Prediction problem that occurs
in many areas of science. Most branch prediction research focuses on
Two-Level Adaptive Branch Prediction techniques, a very specific solution
to the branch prediction problem. However, two-level predictors suffer from
several major problems: high cost, branch interference (aliasing) and a
high number of initialisation mispredictions.

At the University of Hertfordshire we have developed two contrasting
predictors that redress the three major problems of two-level predictors.

In the first alternative we introduce the concept of multiple-stages of
predictors based on the Prediction by Partial Matching (PPM)algorithm. Our
multiple-stage predictors retain the first-level history register of
conventional two-level predictors and replaces the second-level PHT with a
Prediction Cache. The Prediction Cache saves only relevant branch
prediction information, predictions are never based on uninitialised
entries and interference between branches is eliminated. In the case of a
Prediction Cache miss, our predictor uses a default two-bit prediction
counter stored with each branch in the Branch Target Table.

A further alternative approach is to look to other application areas and
fields for novel solutions to the problem. We have examined the application
of neural networks to dynamic branch prediction. Again, we retain the
first-level history register of conventional two-level predictors and
replace the second level PHT with a neural network. We have considered two
neural networks: a Learning Vector Quantisation (LVQ) Network and a
Backpropagation Network. We demonstrate that a neural predictor can achieve
misprediction rates comparable to conventional Two-level Adaptive
Predictors and suggest that neural predictors merit further investigation.