Dynamic feature selection for hardware prediction

It is often possible to greatly improve the performance of a hardware system via the use of predictive (speculative) techniques. For example, the performance of out-of-order microprocessors is greatly enhanced by predicting the outcomes of conditional branch instructions. Most hardware predictors are table based (e.g., two-level branch predictors)—maintaining predictive information for each combination of values of a set of features (e.g., a set of previous branch outcomes). Table-based approaches suffer from the fact that the predictor sizes grow exponentially in the number of features considered by the predictor—this severely limits the amount of predictive information that can be effectively utilized by tablebased predictors. For example, most table-based branch predictors use a feature set containing only a small number of recent branch outcomes, despite the fact that other bits of processor state contain predictive information (e.g., register values and target addresses). In this research we propose a dynamic feature selection framework for building hardware predictors. A predictor using dynamic feature selection selects the most predictive features from a potentially large feature set and uses only the selected features to make predictions. We design and evaluate a dynamic decision tree (DDT) predictor, an on-line adaptation of the decision trees that are widely used in machine learning research. Through the use of feature selection the predictor storage requirement grows only linearly with the number of features considered. This opens up the possibility o