US5574871A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for implementing a set-associative branch target buffer
Assignee: Intel Corp
•
Filing: 1994-01-04
•
Granted: 1996-11-12
•
Expires: 2014-01-04
Abstract
Abstract A Branch Target Buffer Circuit in a computer processor that predicts branch instructions with a stream of computer instructions is disclosed. The Branch Target Buffer Circuit uses a Branch Target Buffer Cache that stores branch information about previously executed branch instructions. The branch information stored in the Branch Target Buffer Cache is addressed by the last byte of each branch instruction. When an Instruction Fetch Unit in the computer processor fetches a block of instructions it sends the Branch Target Buffer Circuit an instruction pointer. Based on the instruction pointer, the Branch Target Buffer Circuit looks in the Branch Target Buffer Cache to see if any of the instructions in the block being fetched is a branch instruction. When the Branch Target Buffer Circuit finds an upcoming branch instruction in the Branch Target Buffer Cache, the Branch Target Buffer Circuit informs an Instruction Fetch Unit about the upcoming branch instruction.
Inventors
- 👤 Bradley D. Hoyt
- 👤 Glenn J. Hinton
- 👤 David B. Papworth
- 👤 Ashwani K. Gupta
- 👤 Michael A. Fetterman
- 👤 Subramanian Natarajan
- 👤 Sunil Shenoy
- 👤 Reynold V. D'Sa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:17
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/30003; G06F9/3005; G06F9/30054
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
207 words
A branch instruction prediction mechanism, said branch instruction prediction mechanism predicting a plurality of branch instructions within a stream of computer instructions, said branch instruction prediction mechanism comprising: an instruction pointer for identifying an instruction address in a memory, said instruction pointer having a set of branch target buffer set address bits and a set of branch target buffer tag address bits; a branch target buffer cache, said branch target buffer cache comprising a plurality of branch set entries, each of said branch set entries comprising a set of branch instruction entries, each branch instruction entry storing information about an associated branch instruction including a position with a memory block, all branch instruction entries within a particular branch set entry storing branch instructions having identical branch target buffer set address bits; and a branch target buffer circuit, said branch target buffer circuit receiving said instruction pointer, said branch target buffer circuit indexing into said branch target buffer cache with said set of branch target buffer set address bits of said instruction pointer to select a branch set entry, said branch target buffer circuit selecting at least one branch instruction entry in said branch set entry using said branch target buffer tag address bits of said instruction pointer.
Claim 2
Dependent Claim
207 words
A branch instruction prediction mechanism, said branch instruction prediction mechanism predicting a plurality of branch instructions within a stream of computer instructions, said branch instruction prediction mechanism comprising: an instruction pointer for identifying an instruction address in a memory, said instruction pointer having a set of branch target buffer set address bits and a set of branch target buffer tag address bits; a branch target buffer cache, said branch target buffer cache comprising a plurality of branch set entries, each of said branch set entries comprising a set of branch instruction entries, each branch instruction entry storing information about an associated branch instruction including a position with a memory block, all branch instruction entries within a particular branch set entry storing branch instructions having identical branch target buffer set address bits; and a branch target buffer circuit, said branch target buffer circuit receiving said instruction pointer, said branch target buffer circuit indexing into said branch target buffer cache with said set of branch target buffer set address bits of said instruction pointer to select a branch set entry, said branch target buffer circuit selecting at least one branch instruction entry in said branch set entry using said branch target buffer tag address bits of said instruction pointer.
Claim 3
Dependent Claim
44 words
The branch instruction prediction mechanism as claimed in claim 1 wherein said instruction pointer points to a block of memory and said branch target buffer circuit searches for a first upcoming branch instruction in said block of memory pointed to by said instruction pointer.
Claim 4
Dependent Claim
24 words
The branch instruction prediction mechanism as claimed in claim 1 wherein each branch set entry further comprises a set of Least Recently Replaced Bits.
Claim 5
Dependent Claim
42 words
The branch instruction prediction mechanism as claimed in claim 1 wherein each said associated branch instruction stored into said branch target buffer cache is stored in said branch target buffer using an address of a last byte of each associated branch instruction.
Claim 6
Dependent Claim
20 words
The branch instruction prediction mechanism as claimed in claim 1 wherein each branch set entry comprises four branch instruction entries.
Claim 7
Dependent Claim
21 words
The branch instruction prediction mechanism as claimed in claim 1 wherein each branch set entry further comprises a branch pattern table.
Claim 8
Dependent Claim
35 words
The branch instruction prediction mechanism as claimed in claim 1 wherein each said branch instruction entry in said branch target buffer cache comprises: a tag address field; a branch target address; and a valid bit.
Claim 9
Dependent Claim
29 words
The branch instruction prediction mechanism as claimed in claim 7 wherein said tag address field comprises a compressed tag address field that is smaller than a full tag address.
Claim 10
Dependent Claim
42 words
The branch instruction prediction mechanism as claimed in claim 7 wherein said a compressed tag address field comprises a subset of most significant bits from said full tag address concatenated with a subset of least significant bits from said full tag address.
Claim 11
Dependent Claim
58 words
The branch instruction prediction mechanism as claimed in claim 7 wherein said a compressed tag address field comprises a first subset of most significant bits from said full tag address, an exclusive or combination of a second subset of bits from said full tag address, and a third subset of least significant bits from said full tag address.
Claim 12
Dependent Claim
28 words
The branch instruction prediction mechanism as claimed in claim 7 wherein each said branch instruction entry in said branch target buffer cache further comprises a branch type field.
Claim 13
Dependent Claim
41 words
The branch instruction prediction mechanism as claimed in claim 11 wherein each said branch instruction entry in said branch target buffer cache further comprises a block offset field that identifies an offset of a last byte of said associated branch instruction.
Claim 14
Dependent Claim
28 words
The branch instruction prediction mechanism as claimed in claim 12 wherein each said branch instruction entry in said branch target buffer cache further comprises a branch history field.
Claim 15
Dependent Claim
33 words
The branch instruction prediction mechanism as claimed in claim 13 wherein each said branch instruction entry in said branch target buffer cache further comprises a speculation bit and a speculative branch history field.
Claim 16
Independent Claim
170 words
A method of updating a branch target buffer cache, said method comprising the steps of: executing a branch instruction to determine a final branch outcome and a final branch target address for said branch instruction; finding a branch set entry in said branch target buffer cache by indexing into said branch target buffer using an address of a last byte of said branch instruction; finding a branch instruction entry associated with said branch instruction in said branch set entry; updating a branch target address in said branch instruction entry associated with said branch instruction using said final branch target address; updating a branch pattern table associated with said branch set entry in said branch target buffer if said branch instruction is a conditional branch instruction; updating a branch history associated with said branch instruction entry if said branch instruction is a conditional branch instruction; matching a subset of most significant bits from said address of a last byte of said branch instruction with a tag field in said branch entry.
Claim 17
Independent Claim
170 words
A method of updating a branch target buffer cache, said method comprising the steps of: executing a branch instruction to determine a final branch outcome and a final branch target address for said branch instruction; finding a branch set entry in said branch target buffer cache by indexing into said branch target buffer using an address of a last byte of said branch instruction; finding a branch instruction entry associated with said branch instruction in said branch set entry; updating a branch target address in said branch instruction entry associated with said branch instruction using said final branch target address; updating a branch pattern table associated with said branch set entry in said branch target buffer if said branch instruction is a conditional branch instruction; updating a branch history associated with said branch instruction entry if said branch instruction is a conditional branch instruction; matching a subset of most significant bits from said address of a last byte of said branch instruction with a tag field in said branch entry.
Claim 18
Dependent Claim
92 words
The method of updating a branch target buffer cache as claimed in claim 15 wherein said step of matching a subset of most significant bits from said address of a last byte of said branch instruction further comprises generating a hashed version of said subset of most significant bits from said address of a last byte of said branch instruction; and matching said hashed version of said subset of most significant bits from said address of a last byte of said branch instruction with a hashed tag field in said branch entry.
Claim 19
Independent Claim
250 words
A method of creating a branch instruction entry in a branch target buffer cache to store information about a discovered branch instruction, said branch target buffer cache organized into a plurality of branch set entries, each branch set entry comprising a set of branch instruction entries, said method comprising the steps of: executing said discovered branch instruction to determine a final branch outcome and a final branch target address for said discovered branch instruction; determining if said discovered branch instruction was mispredicted by comparing said final branch outcome and said final branch target address to a predicted branch outcome and a predicted branch target address; allocating a branch instruction entry in said branch target buffer cache if said discovered branch instruction was mispredicted or if said final branch outcome of said discovered branch instruction was taken, said step of allocating a branch instruction entry comprising the substeps of: reading a least recently replaced value from a least recently replaced field associated branch set entry; replacing a branch instruction entry indicated by said least recently replaced value if said first branch entry does not have a matching tag address field; incrementing said least recently replaced value and repeating said step until all branch instruction entries have been examined if said branch entry has a matching tag address field; and replacing a branch instruction entry pointed to by said least recently replaced value as originally read from said least recently replaced field if all branch instruction entries have matching tag address fields.
Claim 20
Independent Claim
250 words
A method of creating a branch instruction entry in a branch target buffer cache to store information about a discovered branch instruction, said branch target buffer cache organized into a plurality of branch set entries, each branch set entry comprising a set of branch instruction entries, said method comprising the steps of: executing said discovered branch instruction to determine a final branch outcome and a final branch target address for said discovered branch instruction; determining if said discovered branch instruction was mispredicted by comparing said final branch outcome and said final branch target address to a predicted branch outcome and a predicted branch target address; allocating a branch instruction entry in said branch target buffer cache if said discovered branch instruction was mispredicted or if said final branch outcome of said discovered branch instruction was taken, said step of allocating a branch instruction entry comprising the substeps of: reading a least recently replaced value from a least recently replaced field associated branch set entry; replacing a branch instruction entry indicated by said least recently replaced value if said first branch entry does not have a matching tag address field; incrementing said least recently replaced value and repeating said step until all branch instruction entries have been examined if said branch entry has a matching tag address field; and replacing a branch instruction entry pointed to by said least recently replaced value as originally read from said least recently replaced field if all branch instruction entries have matching tag address fields.
References Cited (Backward Citations)
EP0109655A2
Cited
EP0199947A2
Cited
US4679141A
Cited
EP0227892A2
Cited
WO1987005417A1
Cited
US4860197A
Cited
US5142634A
Cited
US5210831A
Cited
US5283873A
Cited
US5265213A
Cited
US5414822A
Cited
WO1993017385A1
Cited
US5266130A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-12 | 2000-05-13 | 2000-11-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-12 | 2004-05-13 | 2004-11-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-12 | 2008-05-13 | 2008-11-12 | $7700.00 | Window Closed / Lapsed |