Next: Using more Pattern Up: No Title Previous: Experimental Results

Aliasing Problem

Aliasing does not directly imply penalties to prediction accuracy. If two branches with different majority direction alias to the same counter, but executes 1000 times followed by the other executing 1000 times, the loss due the aliasing is negligible. However, if the two branches alternate in trace order, then aliasing may cause significant misprediction. Aliasing can be classified into three types. if an aliased counter predicts an execution correctly while the corresponding counter would have predict it incorrectly while there is no aliasing, this type of aliasing is called Constructive aliasing; because it improves the performance. Conversely, if the aliased counter predicts incorrectly but corresponding un-aliased counter would have predicted correctly then this type of aliasing is called Destructive aliasing since aliasing reduces prediction accuracy. Finally, if the aliased counter predicts an execution correctly (incorrectly) and the corresponding un-aliased counter would have predicted it correctly (incorrectly) too, it is called Harmless aliasing since the aliasing does not change the prediction accuracy.

  
Figure 6: Aliasing rates for branch address (pc), global history (history), xoring (xor) and concatenation (cnt) prediction schemes for different size PHT's

To see how common aliasing occur in these four prediction scheme, the number of aliased prediction is counted and shown in Fig.6. The aliasing occurrence frequency rate is given in this figure as percentage of aliased prediction out of total number of branches. For example, 23% aliasing rate means that 23% of prediction is made by using aliased counters.

  
Figure 5: Frequency of aliasing occurred in counters using (a) branch address, (b) global history, (c) xoring scheme using 1024 counters under xlisp benchmark. Gray scale from white to black indicates the more number of times that the corresponding counter is aliased

For large PHT's, the aliasing rate decreases by advantage of using more counters. Branch address schemes suffers less aliasing problem than global history and xoring schemes. Figure 5 contains different illustration of how often counters in PHT use aliased information. This figure plots the distribution of the number of branches that alias to each counter under xlisp benchmark with 1024 counters. White squares represents the unaliased counters and black one for counter with 25 or more aliasing occurred. As shown in Fig. 5 and Fig. 6, global history and xoring schemes suffers much more aliasing problem and this causes considerable decrease in their prediction performance. If we could remove the aliasing from prediction, they would give better performance results.

  
Figure 7: Comparison of branch prediction schemes with and without the aliasing. Als-free columns indicates the misprediction rates if the aliasing affect is removed from prediction.

To verify this idea, the hardware simulation of prediction schemes were modified and aliasing problem was removed from prediction. In Fig. 7, the aliased and aliased-free misprediction rates are given for each prediction scheme using 256 counters. If we can decrease the aliasing from prediction we can improve the prediction performance up to 50%. As mentioned above, aliasing can be classified into three type. The most performance loose in prediction comes from especially destructive aliasing. Harmless and constructive aliasing don't effect the results as much as destructive aliasing. In Fig. 8, the percentage of harmless, constructive and destructive aliasing is shown. For all schemes, 25% of total aliasing is destructive aliasing and this portion of aliasing cause the performance decrease. we can say that there is often a significant improvement in the prediction accuracy for removing aliasing effects. Better dynamic prediction schemes a theoretically possible if those schemes suffers less aliasing problems. Next section introduces new three branch prediction schemes trying to exploit this idea.

  
Figure 8: Percentage of aliasing types

Next: Using more Pattern Up: No Title Previous: Experimental Results