Limits of data value predictability

Abstract

The predictability of data values is studied at a fundamental level. Two basic predictor models are defined: Computational predictors perform an operation on previous values to yield predicted next values. Examples we study are stride value prediction and last value prediction

Context-Based predictors match recent value history (context) with previous value history and predict values based entirely on previously observed patterns. To understand the potential of value prediction we perform simulations with unbounded prediction tables that are immediately updated using correct data values. Simulations of integer SPEC95 benchmarks show that data values can be highly predictable. Best performance is obtained with context-based predictors

overall prediction accuracies are between 56% and 92%. The context based predictor typically has an accuracy about 20% better than the computational predictors (last value and stride). Results with bounded tables suggest the feasibility of context-based predictors that approximate the performance with unbounded tables.