As a result of resource limitations, state in branch predictors is frequently shared between uncorrelated branches. This interference can significantly limit prediction accuracy. In current predictor designs, the branches sharing prediction information are determined by their branch addresses and thus branch groups are arbitrarily chosen during compilation. This feasibility study explores a more analytic and systematic approach to classify branches into "clusters" with similar behavioral characteristics, and we evaluate several ways to incorporate this additional source of information in branch predictors.
Our profile-based results illustrate the potential of using clustering information in various types of branch predictors. In particular for small predictor budgets, clustered indexing is a very cost effective solution, e.g. the misprediction rate in a 1KiB gshare predictor is reduced by 19% and 12.3% for SPECint2000 in a self and cross profiling setup respectively.