Dynamic history-length fitting: a third level of adaptivity for branch prediction

Abstract

Accurate branch prediction is essential for obtaining high pegormance in pipelined superscalar processors that execute instructions speculatively. Some of the best current predictors combine a part of the branch address with a$xed amount of global history of branch outcomes in order to make a prediction. These predictors cannot per$orm 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$xed history length are therefore unable to pe$orm 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) andobtain near-optimal resultsforall ~P~~int95 bench-marks, with and without context switches. Some results are also presentedfor gskewed (dhlf-gskewed), confirming that other predictors can beneJitfrom our proposal. 1.