Method to Exclude Bad Patterns From A Pattern History Table Branch Predictor (19-Jan-2010)

Method to Exclude Bad Patterns From A Pattern History Table Branch Predictor

Accurate branch prediction is a technique used in modern microprocessors to achieve adequate performance. In microprocessor pipelines (which are often deep and wide in modern machines to achieve high frequency operation and exploit instruction-level parallelism) the outcome of branch instructions is unknown until the branch is executed near the end of the pipeline. The outcome of each branch is predicted and acted upon near the beginning of the pipeline such that there is little or no penalty when the branch is correctly predicted. When a branch is mispredicted, wrong path instructions that had been speculatively sent into the pipeline are flushed. The front end is redirected based on the then-known outcome of the branch.

     The bimodal predictor (2-bit saturating counter) provides high accuracy on most branches, particularly those that are dominant. Dominant branches are those that always or often repeatedly exhibit the same direction: taken vs. not-taken. The bimodal predictor often mispredicts non-dominant branches.

     Pattern-based prediction algorithms provide high accuracy on non-dominant branches but are costly in terms of area and power consumption. One effective pattern-based algorithm based on global branch history is gshare where the global history is combined with a branch address to form an index into a Pattern History Table (PHT).

     Hybrid predictors allow for the dynamic selection among different predictors. A traditional hybrid predictor selects between predictors based on a per-branch indication of which predictor is best.

     A global selection counter can be used instead of a per-branch selection table to achieve good performance with less overhead than a traditional hybrid scheme. However each component predictor still needs to be big enough to support all branches being tracked.

     State machine based filtering uses a pattern-history-based predictor only on non-dominant branches. This allows the pattern-based predictor to be implemented with a much smaller pattern history table (PHT) that would otherwise be possible.

     Filtering can also be achieved by maintaining a branch address tag along with PHT entries. A branch address tag is maintained with each PHT entry and that PHT entry is only used to make a prediction upon a tag match. Entries are installed upon a misprediction from a less accurate predictor in a hybrid configuration. Tagged PHT's have been described previously in the literature.

     A Pattern History Table (PHT) is indexed as a function of the outcomes (taken vs. not-taken) of previous branches. Either global or local history can be employed. A fixed number of such previous branch outcomes are used. A limitation of this approach is that there are cases where different outcomes of the same branch will have the same PHT index. Often this is due to limited history length. In such cases the PHT is not abl...