Potentials of Branch Predictors: From Entropy Viewpoints.

Predictors essentially predicts the most recent events based on the record of past events, history. It is obvious that prediction performance largely relies on regularity–randomness level of the history. This paper concentrates on extracting effective information from branch history, and discusses expected performance of branch predictors. For this purpose, this paper introduces entropy point-of-views for quantitative characterization of both program behavior and prediction mechanism. This paper defines four new entropies from different viewpoints; two of them are independent of prediction methods and the others are dependent on predictor organization. These new entropies are useful tools for analyzing upper-bound of prediction performance. This paper shows some evaluation results of typical predictors. [ABSTRACT FROM AUTHOR]