Compiler support for practical value prediction in high-performance processors

True data dependences are a serious limitation to exploit sufficient ILP and therefore restrict the performance of superscalar processors. Value prediction has been previously proposed to break true data dependences to increase the ILP available in programs. However, there are several potential difficulties in building practical cost-effective value predictors.; One of the potential difficulties is efficiently utilizing the limited hardware resources to provide the greatest benefit, including how to select the proper type of predictor for a given instruction and how to choose critical instructions for prediction. We proposed a compiler directed scheme that statically partitions all of the instructions in a program into several groups with different value predictability patterns and assigns priority information to each instruction. Both the value predictability pattern and the priority information are encoded into the instructions. The hardware utilize them to identify the type of value predictor that will be best suited for each instruction and to choose critical instructions for prediction at run-time.; The other problem is that the delay inherent in updating the value prediction table could introduce a substantial number of wrong value predictions, which then can decrease the overall processor performance. We proposed a technique called hyperprediction to compensate for the delayed updates. This approach accurately computes and records the number of outstanding instances of an instruction. The value predictor can provide reliable predictions for an instruction based on both the currently stored value and the number of outstanding instances.; Our simulations indicate that the static classification, the priority assignment and the hyperprediction can more efficiently utilize the limited hardware resources and well resolve the delayed update problem of value predictors, therefore consistently improve practical value predictors and then the overall processor performance. This thesis also makes the following additional contributions. Firstly, it further demonstrates the connection between value locality behavior and source-level program structures thereby leading to a deeper understanding of the causes of this behavior. Secondly, it implements both the ideal and practical compiler algorithms of the static classification and priority assignment schemes. Finally, it implements simple and efficient hardware technique—hyperprediction in various value predictors.