US5553253A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Correlation-based branch prediction in digital computers
Assignee: International Business Machines Corp
•
Filing: 1994-03-30
•
Granted: 1996-09-03
•
Expires: 2014-03-30
Abstract
Abstract Method and apparatus for predicting the outcome of branch instructions subject to execution in a multiple processor digital computer. Pipelining is a popular technique to accelerate the data processing rate of modern computers, and in particular the RISC architecture class of workstations. Accurate prediction of branch instructions is exceptionally important to the efficient use of pipelines, in that erroneous predictions require both the purge and reload of all affected processor pipelines. According to the present invention, branch prediction is based upon a correlation between a history of successive prior branches and a specified branch instruction. In a preferred practice, a branch prediction table is created. The fields in the table are derived and thereafter updated based upon the correlated combination of outcomes from prior branches and the branch address under consideration.
Inventors
- 👤 Shien-Tai Pan
- 👤 Kimming So
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 16:12
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3848
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
81 words
A method for predicting an outcome of a branch instruction in a programmed computer, comprising the steps of: creating a branch prediction table in addressable memory of the computer; storing in the branch prediction table branch data which correlates branch instructions to a data sequence representing a succession of multiple prior branch outcomes; and selecting branch data from the table using an address created from a combination of a first branch instruction and a first data sequence of prior branch outcomes.
Claim 2
Independent Claim
81 words
A method for predicting an outcome of a branch instruction in a programmed computer, comprising the steps of: creating a branch prediction table in addressable memory of the computer; storing in the branch prediction table branch data which correlates branch instructions to a data sequence representing a succession of multiple prior branch outcomes; and selecting branch data from the table using an address created from a combination of a first branch instruction and a first data sequence of prior branch outcomes.
Claim 3
Dependent Claim
38 words
The method recited in claim 1, including the further step of: periodically updating the branch prediction table by increment or decrementing branch data based upon the taking or not taking of a branch specified in a branch instruction.
Claim 4
Dependent Claim
81 words
In a programmable workstation having an addressable memory and multiple processors, a branch processor comprising: means for storing branch prediction data in the memory; means for updating the branch prediction data in the memory; means for storing a data sequence representing a succession of multiple prior branch outcomes; and means for selecting branch prediction data stored in memory using an address created from a combination of a new branch instruction and the data sequence representing a succession of prior branch outcomes.
Claim 5
Dependent Claim
81 words
In a programmable workstation having an addressable memory and multiple processors, a branch processor comprising: means for storing branch prediction data in the memory; means for updating the branch prediction data in the memory; means for storing a data sequence representing a succession of multiple prior branch outcomes; and means for selecting branch prediction data stored in memory using an address created from a combination of a new branch instruction and the data sequence representing a succession of prior branch outcomes.
Claim 6
Dependent Claim
18 words
The apparatus recited in claim 3, wherein the means for storing data is a multiple field matrix memory.
Claim 7
Dependent Claim
22 words
The apparatus recited in claim 4, wherein the means for updating is an up/down counter which communicates with individual matrix memory fields.
Claim 8
Dependent Claim
25 words
The apparatus recited in claim 5, wherein the means for storing a data sequence representing a succession of prior branch outcomes is a shift register.
Claim 9
Dependent Claim
24 words
In the apparatus recited in claim 6, wherein the shift register stores a data sequence representing the taking or not taking of prior branches.
Claim 10
Dependent Claim
32 words
The apparatus recited in claim 7, wherein the new branch instruction and the data sequence representing a succession of prior branch outcomes uniquely select a field in the multiple field matrix memory.
References Cited (Backward Citations)
US4370711A
Cited
US4430706A
Cited
US4435756A
Cited
US4477872A
Cited
US4984154A
Cited
US4470711A
Cited
US4764861A
Cited
US4679141A
Cited
US4763245A
Cited
US4853840A
Cited
US4991080A
Cited
US4833599A
Cited
US4943908A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-03 | 2000-03-04 | 2000-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-03 | 2004-03-04 | 2004-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-03 | 2008-03-04 | 2008-09-03 | $7700.00 | Window Closed / Lapsed |