Leveraging Strength-Based Dynamic Information Flow Analysis to Enhance Data Value Prediction

Value prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local, that is, future outputs of an instruction are predicted based on outputs from previous executions of the same instruction.

In this article, we investigate leveraging strength-based dynamic information flow analysis to enhance data value prediction. We use dynamic information flow analysis (DIFA) to determine when a specific value predictor can perform well and even outperform other predictors. We apply information theory to mathematically prove the validity and benefits of correlating value predictors. We also introduce the concept of the linear value predictors, a new technique that predicts a new value from another one using a linear relation. We finally present a variant of stride predictor that we call update stride.

We then conduct an empirical analysis using Pin, a dynamic binary instrumentation tool, and DynFlow, a dynamic information flow analysis tool, that we apply to programs from the SPECjvm2008 and Siemens benchmarks. Our empirical measurements support our mathematical theory and allow us to make important observations on the relation between predictability of data values and information flow. Our analysis and empirical results show that the values of a set of selected variables can be predicted with a very high accuracy, up to 100%. Such prediction is based on the previous history and/or the values of one or more other source variables that have strong information flow into the predicted variable. Using our selection criteria, we show that a DIFA-directed predictor outperforms hardware value prediction for all subject programs, and sometimes by a significant margin. This was observed even when using an ideal tagged hardware value prediction table that does not suffer from aliasing or capacity misses.