Studying new ways for improving adaptive history length branch predictors

Abstract

Pipeline stalls due to branches limit processor performance significantly. This paper provides an in depth evaluation of Dynamic History Length Fitting, a technique that changes the history length of a two-level branch predictor during the execution, trying to adapt to its different phases. We analyse the behaviour of DHLF compared with fixed history length gshare predictors, and contribute showing two factors that explain DHLF behaviour: Opportunity Cost and Warm-up Cost. Additionally, we evaluate the use of profiling for detecting future improvements. Using this information, we show that new heuristics that minimise both opportunity cost and warm-up cost could outperform significantly current variable history length techniques. Especially at program start-up, where the algorithm tries to learn the behaviour of the program to better predict future branches, the use of profiling reduces considerably the cost produced by continuous history length changes.