Assigning confidence to conditional branch predictions
E. N. Jacobsen, Eric Rotenberg, James E. Smith · 1996
Many high performance processors predict condi-tional branches and consume processor resources based on the prediction. In some situations, resource allocation can be better optimized if a confidence level is assigned to a branch prediction; i.e. if the quantity of resources allo-cated is a function of the confidence level. To support such optimizations, we consider hardware mechanisms that partition conditional branch predictions into two sets: those which are accurate a relatively high percen-tage of the time, and those which are accurate a relatively low percentage of the time. The objective is to concen-trate as many of the mispredictions as practical into a relatively small set of low confidence dynamic branches. We first study an ideal method that pro$iles branch predictions and sorts static branches into high and low confidence sets, depending on the accuracy with which they are dynamically predicted. We find that about 63 percent of the mispredictions can be localized to a set of static branches that account for 20 percent of the dynamic branches. We then study idealized dynamic confidence methods using both one and two levels of branch correct-ness history. We find that the single level method per-forms at least as well as the more complex two level method and is able to isolate 89 percent of the mispredic-tions into a set containing 20 percent of the dynamic branches. Finally, we study practical, less expensive implementations and find that they achieve most of the performance of the idealized methods. 1.