US5577217A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for a branch target buffer with shared branch pattern tables for associated branch predictions
Assignee: Intel Corp
•
Filing: 1996-05-07
•
Granted: 1996-11-19
•
Expires: 2016-05-07
Abstract
Abstract A two level adaptive branch prediction mechanism for a computer processor. The branch prediction mechanism comprises a branch target buffer in which the branch prediction entries are partitioned into "sets" of branch prediction entries. Each set of branch prediction entries is provided with a branch pattern table such that only the branch prediction entries in the same set share a branch pattern table thereby reducing branch pattern table interference.
Inventors
- 👤 Bradley D. Hoyt
- 👤 Subramanian Natarajan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:37
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3848
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
171 words
In a computer processor, said computer processor coupled to a memory, a branch prediction apparatus for predicting a stream of processor instructions to fetch, said branch prediction apparatus comprising the elements of: a branch target buffer comprising M branch prediction entries, each of said branch prediction entries comprising a target address tag, said target address tag specifying a target address for said branch prediction entry, and a K bit branch history, said K bit branch history comprising a series of K bits used as an index into a branch pattern table, a precalculated prediction bit, said precalculated prediction bit based upon said K bit branch history; said M branch prediction entries divided into N sets of branch prediction entries wherein N is less than M; and N branch pattern tables, each of said N branch pattern tables associated with one of said N sets of branch prediction entries such that each branch prediction entry shares one of said N branch pattern tables with other branch prediction entries in the same set.
Claim 2
Dependent Claim
171 words
In a computer processor, said computer processor coupled to a memory, a branch prediction apparatus for predicting a stream of processor instructions to fetch, said branch prediction apparatus comprising the elements of: a branch target buffer comprising M branch prediction entries, each of said branch prediction entries comprising a target address tag, said target address tag specifying a target address for said branch prediction entry, and a K bit branch history, said K bit branch history comprising a series of K bits used as an index into a branch pattern table, a precalculated prediction bit, said precalculated prediction bit based upon said K bit branch history; said M branch prediction entries divided into N sets of branch prediction entries wherein N is less than M; and N branch pattern tables, each of said N branch pattern tables associated with one of said N sets of branch prediction entries such that each branch prediction entry shares one of said N branch pattern tables with other branch prediction entries in the same set.
Claim 3
Dependent Claim
29 words
The branch prediction apparatus as claimed in claim 1, wherein said branch prediction apparatus predicts said stream of processor instructions by predicting a subsequent memory block to be fetched.
Claim 4
Dependent Claim
52 words
The branch prediction apparatus as claimed in claim 2, wherein each set of branch prediction entries are grouped together into a single branch target buffer row such that said branch target buffer comprises N rows wherein each branch target buffer row comprises a set of M divided by N branch prediction entries.
Claim 5
Dependent Claim
33 words
The branch prediction apparatus as claimed in claim 3, wherein each said branch pattern table associated with each of said N branch target buffer entries is concatenated to said branch target buffer row.
Claim 6
Dependent Claim
166 words
In a computer processor, said computer processor coupled to a memory containing processor instructions, a method for predicting a stream of processor instructions to fetch, said method comprising the steps of: constructing a branch target buffer, said branch target buffer comprising M branch prediction entries, each of said branch prediction entries comprising a target address tag, said target address tag specifying a target address for said branch prediction entry, and a K bit branch history, said K bit branch history comprising a series of K bits used as an index into a branch pattern table; a precalculated prediction bit, said precalculated prediction bit based upon said K bit branch history; dividing said M branch prediction entries into N sets of branch prediction entries wherein N is less than M; and appending a branch pattern table to each set of branch prediction entries such that each branch prediction entry within a set shares a branch pattern table with the other branch prediction entries in the same set.
Claim 7
Dependent Claim
166 words
In a computer processor, said computer processor coupled to a memory containing processor instructions, a method for predicting a stream of processor instructions to fetch, said method comprising the steps of: constructing a branch target buffer, said branch target buffer comprising M branch prediction entries, each of said branch prediction entries comprising a target address tag, said target address tag specifying a target address for said branch prediction entry, and a K bit branch history, said K bit branch history comprising a series of K bits used as an index into a branch pattern table; a precalculated prediction bit, said precalculated prediction bit based upon said K bit branch history; dividing said M branch prediction entries into N sets of branch prediction entries wherein N is less than M; and appending a branch pattern table to each set of branch prediction entries such that each branch prediction entry within a set shares a branch pattern table with the other branch prediction entries in the same set.
Claim 8
Dependent Claim
36 words
The method for predicting a stream of processor instructions to fetch as claimed in claim 5, wherein said method predicts said stream of processor instructions to fetch by predicting a subsequent memory block to be fetched.
Claim 9
Dependent Claim
59 words
The method for predicting a stream of processor instructions to fetch as claimed in claim 6, wherein each set of branch predictions entries are grouped together into a single branch target buffer row such that said branch target buffer comprises N rows wherein each branch target buffer row comprises a set of M divided by N branch predictions entries.
Claim 10
Dependent Claim
41 words
The method for predicting a stream of processor instructions to fetch as claimed in claim 7, wherein each of said branch pattern tables associated with each of said N branch target buffer sets is concatenated to said branch target buffer row.
Claim 11
Dependent Claim
121 words
In a computer processor, said computer processor coupled to a memory, a branch prediction apparatus for predicting a stream of processor instructions to fetch, said branch prediction apparatus comprising the elements of: a branch target buffer comprising S branch prediction sets, each of said branch prediction sets comprising E branch prediction entries wherein each branch prediction entry contains a precalculated prediction bit for making a branch prediction, S branch pattern tables, each of said S branch pattern tables associated with one of said S branch prediction sets such that each branch prediction set has an associated branch pattern table, wherein each branch prediction entry shares one of said S branch pattern tables with other branch prediction entries in the same set.
Claim 12
Dependent Claim
121 words
In a computer processor, said computer processor coupled to a memory, a branch prediction apparatus for predicting a stream of processor instructions to fetch, said branch prediction apparatus comprising the elements of: a branch target buffer comprising S branch prediction sets, each of said branch prediction sets comprising E branch prediction entries wherein each branch prediction entry contains a precalculated prediction bit for making a branch prediction, S branch pattern tables, each of said S branch pattern tables associated with one of said S branch prediction sets such that each branch prediction set has an associated branch pattern table, wherein each branch prediction entry shares one of said S branch pattern tables with other branch prediction entries in the same set.
Claim 13
Dependent Claim
72 words
The branch prediction apparatus as claimed in claim 9, wherein each branch prediction entry further comprises: a target address tag, said target address tag specifying a target address for said branch prediction entry, and a K bit branch history, said K bit branch history comprising a series of K bits used as an index into said branch pattern table associated with the branch prediction set that said branch prediction entry is in.
References Cited (Backward Citations)
US4477872A
Cited
US4679141A
Cited
US4763245A
Cited
US5237666A
Cited
US5142634A
Cited
US5226130A
Cited
US5163140A
Cited
US5155843A
Cited
US5276882A
Cited
US5265213A
Cited
US5313134A
Cited
US5507028A
Cited
US5423011A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-19 | 2000-05-20 | 2000-11-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-19 | 2004-05-20 | 2004-11-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-19 | 2008-05-20 | 2008-11-19 | $7700.00 | Window Closed / Lapsed |