Browse Prior Art Database

BRANCH HISTORY TABLE WITH GREY CODED ENTRY BITCELL

IP.com Disclosure Number: IPCOM000008890D
Original Publication Date: 1999-Jan-01
Included in the Prior Art Database: 2002-Jul-22
Document File: 2 page(s) / 92K

Publishing Venue

Motorola

Related People

Brandon T. Waldo: AUTHOR [+2]

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

0 M

MOTOROlA Technical Developments

BRANCH HISTORY TABLE WITH GREY CODED ENTRY BITCELL

by Brandon T. Waldo and Jeff Rupley II

  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.

To show how a grey coding scheme can prove useful, an example will be used. The BHT being dis-

cussed in this example has two write ports and one

read port. The bit-cell of a standard two entry BHT memory cell with two write ports and one read port is shown in Figure 2. This configuration requires six bit l...