An analysis of value predictability and its application to a superscalar processor
Yiannakis Sazeides, James E. Smith · 1999
The central theme of this thesis is the predictability of data-dependence values. Value predictability is studied first at a fundamental level. The analysis shows for SPEC95 programs that: (1) Values are amenable to prediction and that predictors that capture repeated behavior are necessary for high prediction accuracy. (2) Value predictability is mainly dependent on the program internal structure and immediate values, not input data. Value prediction and speculation is then applied to a superscalar processor to (a) determine its consequences on processor and value predictor design, and (b) evaluate its performance potential. Speculative execution and timing models are defined to describe concisely the design space of a superscalar processor influenced by value prediction. It is shown that invalidation and verification of dependent chains of instructions can be performed in “parallel”, contingent on technology constraints. For predictor implementations, emphasis is given to the design of a context-based predictor capable of predicting repeated value sequences, and a hybrid predictor that combines context-based and stride prediction. The following issues are also discussed: (a) delayed updates, speculative updates, and the use of old versus current information for deterministic updates, (b) removal on branch mispredictions of the side-effects due to speculative updates, and (c) high bandwidth value prediction. Performance simulations suggest that: (1) Value prediction can reduce the instruction window size required to achieve a given level of parallelism. (2) Value prediction has potential to improve performance on the average 3%–20% depending on the predictor, timing and confidence model used. (3) Hybrid predictors are the most cost effective predictors for achieving a given prediction accuracy. (4) There is a correlation between prediction accuracy and performance for a given predictor, i.e. improved accuracy translates to better performance. (5) When comparing different predictors, accuracy is not a good indication of their performance relation. (6) The predictors with the best performance are context-based and hybrid. (7) Delayed-updating a context-based predictor does not affect significantly its correct prediction accuracy, it increases however the number of incorrect predictions with high confidence (i.e. misspeculations). (8) Fast verification latency and accurate confidence are very critical to value prediction.