Entropy Properties in Program Behaviors and Branch Predictors

T. Yokota, K. Ootsu, F. Furukawa, and T. Baba (Japan)


entropy, branch predictors, program behaviors, execution history, Markovian property


Modern microprocessors largely depend on prediction mechanisms. Particularly, branch predictors play important roles in the state-of-the-art microarchitecture. Most predic tors make efficient use of an imbalanced feature of the past events, i.e., extremely imbalanced situation yields signifi cantly good performance. However, real world programs may have wide variations in the imbalance level. Thus, predictors should handle such wide range of imbalances to enhance prediction performance. However, there are few qualitative and quantitative discussions on essential imbal ances in the program behavior. In this paper, we introduce an entropy concept to represent the imbalances properly. We define two types of entropy metrics; the reference en tropy that is based on imbalanced reference to a prediction table, and the source entropy that represents essential infor mation in the sequence of taken/not-taken branches. Sim ulation results on SPEC 2000 benchmarks reveal appropri ateness of our entropy metrics.

Important Links:

Go Back