Department of Computer Science & Engineering

Predicated Execution can be used to alleviate the costs associated with frequently mispredicted branches. This is accomplished by trading the cost of a mispredicted branch for execution of both paths following the conditional branch. In this paper we concentrate on using predicated execution to aggressively reduce a program's branch misprediction rate. We examine an aggressive region formation algorithm focused on removing hard-to-predict branches. This region formation algorithm allows the inclusion of unbiased, but predictable, branches within a region. This was essential in order to predicate the hard-to-predict branches for the programs we examined. The branches left in the predicated region will now need to be predicted during fetch with greater frequency. Using a traditional branch prediction architecture, these region-based branches can end up having a similar miss rate to the hard-to-predict branches that were removed. We propose the Predicate Update Branch Predictor architecture to aid the prediction of these region-based branches. Region-based branches are heavily correlated with the outcome of the predicate with which they are guarded. A branch predicated on false should always predict that the branch should not be taken. Our predicate update predictor updates the global history with the result of the predicate defining instruction. This allows the region branches guarded by those predicates to benefit from this correlation history when making their prediction. For codes predicated with our hard-to-predict region formation algorithm, our results show that a Predicate Update Branch Predictor reduces the mispredict rate from an average of 7% to 5% for the benchmarks we studied.

Pre-2018 CSE ID: CS2001-0677