The Predictability of Data Values

The predictability of data values is studied at a fnn-damental level. Two basic predictor models are defined: Computational predictors pelform an operation on pre-vious values to yield predicted next values. Examples we study are stride value prediction (which adds a delta to a previous value) and last value prediction (which peforms the trivial identity operation on the previous value); Context Based predictors match recent value history (con-text) with previous value history and predict values based entirely on previously observed patterns. To understand the potential of value prediction we per-form simulations with unboundedprediction tables that are immediately updated using correct data values. Simula-tions of integerSPEC95 benchmarks how that data values can be highly predictable. Best pe~onnance is obtained with context based predictors; overall prediction accura-cies are between 56 % and 91 o/o, The context based pre-dictor typically has an accuracy about 20 % better than the computational predictors (last value and stride). Compati-son of context based prediction and stride prediction shows that the higher accuracy of context based prediction is due to relatively few static instructions giving large improve-ments; this suggests the usefulness of hybrid predictors. Among different instruction types, predictability varies sig-nijicantly. In general, load and shift instructions are more dificult to predict correctly, whereas add instructions are more predictable.