Dynamic historylength fitting: A third level of adaptivity for branch prediction

Accurate branch prediction is essential for obtaining high performance in pipelined superscalar processors that execute instructions speculatively. Some of the best current predictors combine a part of the branch address with a fixed amount of global history of branch outcomes in order to make a prediction. These predictors cannot perform uni-formly well across all workloads because the best amount of history to be used depends on the code, the input data and the frequency of context switches. Consequently, all predic-tors that use a fixed history length are therefore unable to perform up to their maximum potential. We introduce a method —called DHLF — that dynami-cally determines the optimum history length during execu-tion, adapting to the specific requirements of any code, in-put data and system workload. Our proposal adds an extra level of adaptivity to two-level adaptive branch predictors. The DHLF method can be applied to any one of the predic-tors that combine global branch history with the branch ad-dress. We apply the DHLF method to gshare (dhlf-gshare) and obtain near-optimal results for all SPECint95 bench-marks, with and without context switches. Some results are also presented for gskewed (dhlf-gskewed), confirming that other predictors can benefit from our proposal. 1