| Modern microprocessors increasingly apply aggressive speculation techniques to overcome performance barriers. Two such speculation techniques of particular interest are branch prediction and data value prediction, which attempt to overcome the effects of control dependencies and true data dependencies, respectively. These speculation schemes collect a part of the processor state from different points of time and blend these histories, creating a prediction history for predictor table lookup. Existing schemes mostly use local histories, global histories or their combinations as the prediction history. For generating an accurate prediction, the prediction history has to be highly correlated to the outcome being predicted; it is not straightforward to choose the best state components from the voluminous amount of processor state. We present an analysis and characterization of unpredictability for data values; we also overview the unpredictability of branches. We show that data flow and control flow interact in various ways that result in predictability loss for many instructions.;We propose a novel framework for deriving the prediction histories. Our framework uses a class of processor state that we call computation histories. We propose several novel predictors---branch predictors as well as value predictors---that are based on the computation history concept. We introduce a novel prediction algorithm called Dynamic Dataflow-inherited Speculative Context (DDISC) predictor, based on computation history, and show how to build DDISC branch predictors and value predictors. We also present branch predictors that derive their prediction histories using another class of computation history that we term affectors. We show how to identify a subset of correlated branches from a large global history, based on the affector concept. Finally, we present the OPSHIFT branch predictor---another computation history based predictor that uses the affector concept at instruction granularity. |
