Aliasing and Anti-Aliasing in Branch History Table Prediction

摘要

Branch history table (BHT) prediction is a simple and effective method of predicting branch direction at run-time in a microprocessor. Unfortunately, this method suffers from performance limitations due to aliasing, which is when more than one branch uses a single entry in the branch history table. Theoretically, for programs that exhibit pseudo-random branch positioning, aliasing can be predicted and reduced, thereby improving performance. In this paper, we develop a probabilistic model for aliasing and "anti-aliasing", and we use SimpleScalar to explore the extent to which "anti-aliasing" is useful in real programs. Our results show that programs can be "anti-aliased" to some extent when using history tables of 256 entries or greater, and that for large enough history tables, a significant percentage of table entries are unused and available for "anti-aliasing."