The Cascaded Predictor:
Economical and Adaptive Branch Target Prediction
Karel Driesen, Urs Hölzle
Abstract:
Two-level predictors improve branch prediction accuracy by allowing
predictor tables to hold multiple predictions per
branch. Unfortunately, the accuracy of such predictors is impaired
by two detrimental effects. Capacity misses increase since each
branch may occupies entries proportional to the number of
different path histories leading up to the branch. The working set
of a given program therefore increases with history
length. Similarly, cold start misses increase with history length
since the predictor must initially store a prediction separately
for each history pattern.
We describe a new predictor architecture, cascaded branch prediction,
which can alleviate both of these effects while retaining the
superior accuracy of two-level predictors. Cascaded predictors
dynamically classify and predict easily predicted branches using
an inexpensive predictor, preventing insertion of these branches
into a more powerful second stage predictor. We show that for
path-based indirect branch predictors, cascaded prediction obtains
prediction rates equivalent to that of two-level predictors at
approximately one fourth the cost. For example, a cascaded
predictor with 64+1024 entries achieves the same prediction
accuracy as a 4096-entry two-level predictor. Although we have
evaluated cascaded prediction only on indirect branches, we
believe that it could also improve conditional branch prediction
and value prediction.
To be presented at MICRO-31, Dallas, TX, December 1998 (PostScript, PDF).
An earlier version was published as
Technical Report TRCS98-17, Computer Science Department, University of California, Santa Barbara, 22 June 1998
(Postscript, PDF).