PLEASE DO NOT DISTRIBUTE- SUBMITTED FOR PUBLICATION 6/2000 1 Dependence Based Value Prediction

This paper introduces dependence-based value prediction: prediction based on information that can be propagated through dependences. We propose an organization for a dependence-based value predictor and investigate how to use different types of dependence information to predict values produced by instructions. We consider first register dependences and then memory dependences. Memory dependence prediction is employed for propagating the history used for predicting output values. When considering only register dependences average prediction of 75 % is achieved with a 64K entry table. The use of memory dependence prediction increases average accuracy for a 64K entry table to 82%. Several benchmarks achieve value prediction accuracy over 90%. We provide evidence that the proposed predictor requires small amount of speculative state (for speculative updates) which may suggest its design feasibility.