Improving branch prediction by considering affectors and affectees correlations
Date
2011Author
Sazeides, YiannakisMoustakas, Andreas
Constantinides, Kypros
Kleanthous, Marios M.
ISSN
0302-9743Source
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Volume
6590Pages
69-88Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
This work investigates the potential of direction-correlations to improve branch prediction. There are two types of direction-correlation: affectors and affectees. This work considers for the first time their implications at a basic level. These correlations are determined based on dataflow graph information and are used to select the subset of global branch history bits used for prediction. If this subset is small then affectors and affectees can be useful to cut down learning time, and reduce aliasing in prediction tables. This paper extends previous work explaining why and how correlation-based predictors work by analyzing the properties of direction-correlations. It also shows that branch history selected based on direction-correlations improves the accuracy of the limit and realistic conditional branch predictors, that won at the recent branch prediction contest, by up to 30% and 17% respectively. The findings in this paper call for the investigation of predictors that can efficiently learn correlations that may be non-consecutive (i.e. with holes between them) from long branch history. © 2011 Springer-Verlag Berlin Heidelberg.