A COST EFFECTIVE CACHED CORRELATED TWO-LEVEL ADAPTIVE BRANCH PREDICTOR

摘要

High-performance superscalar processors rely on accurate branch prediction to sustain high instruction issue rates. During the last few years a new class of branch predictors, termed two-level adaptive branch predictors, has been developed to meet the requirement for more accurate branch prediction. However, while two-level adaptive predictors achieve very high prediction rates, they tend to be very costly. In particular, the size of the second-level Pattern History Table (PHT) increases exponentially as a function of history register length. Furthermore, predictions are routinely made using uninitialised PHT entries, and prediction information acquired to predict one branch can corrupt information previously saved to predict other unrelated branches. In this paper, we propose a Cached Two-Level Predictor in which the PHT is implemented as a cache. As a result the PHT only saves relevant branch prediction information. Furthermore, predictions are never based on uninitialised entries, and branch interference is completely eliminated. We simulate two versions of our cached predictors, the first based on global history information and the second based on local history information. We demonstrate that our predictors deliver higher prediction accuracy than conventional predictors at a significantly lower cost.