BRANCH HISTORY TABLE WITH GREY CODED ENTRY BITCELL
Original Publication Date: 1999-Jan-01
Included in the Prior Art Database: 2002-Jul-22
Microprocessors which incorporate dynamic branch-prediction are aided with the use of a branch-prediction buffer. This buffer is well known in some circles as a Branch History Table (BHT). A BHT is a small memory typically indexed by a lower portion of the branch instruction address that contains information on whether the branch was recently taken or not. This information is used to predict a current branch instruction. If one bit is used to tell if the branch is taken or not, when a branch is predicted incorrectly the prediction bit is inverted. To increase prediction accuracy, a two-bit scheme is used. The branch-prediction must miss twice before the prediction is changed. This two-bit scheme gives rise to four states: Strong Taken, Weak Taken, Weak Not Taken and Strong Not Taken. In normal operation the entry can only change as shown in Figure 1. As the figure shows if a grey- code scheme is used to encode the four states in the system, only one bit of the entry can change per state change. Therefore, the BHT array can be updated by writing one bit rather than writing both bits of the entry.