Patent US5641843A successfully refreshed from Google Patents.
US5434985A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simultaneous prediction of multiple branches for superscalar processing
Assignee: International Business Machines Corp
•
Filing: 1992-08-11
•
Granted: 1995-07-18
•
Expires: 2012-08-11
Abstract
Abstract System and method for predicting a multiplicity of future branches simultaneously (parallel) from an executing program, to enable the simultaneous fetching of multiple disjoint program segments. Additionally, the present invention detects divergence of incorrect branch predictions and provides correction for such divergence without penalty. By predicting an entire sequence of branches in parallel, the present invention removes restrictions that decoding of multiple instructions in a superscalar environment must be limited to a single branch group. As a result, the speed of today's superscalar processors can be significantly increased. The present invention includes three main embodiments: (1) the first embodiment is directed to a simplex multibranch prediction device, that can predict a plurality of branch groups in one cycle and provide early detection of wrong predictions; (2) the second embodiments is directed to a duplex multibranch prediction device that can detect divergence in a predicted stream, and provide redirection (correction) within the stream; and (3) the third embodiment is directed to an n-plex multibranch prediction device, that can predict n multiplicity of branch predictions simultaneously and provide an early detection of wrong predictions as well as correction of wrong predictions.
Inventors
- 👤 Philip G. Emma
- 👤 Joshua W. Knight
- 👤 James H. Pomerene
- 👤 Thomas R. Puzak
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:19
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
95 words
A system for simultaneously predicting a plurality of future branches based on an occurrence of a given branch instruction, comprising: a multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a plurality of branch instructions that executed sequentially after the given branch instruction; retrieving means for retrieving said stored branch and target addresses from said multibranch history table upon a next occurrence of the given branch instruction; and predicting means for simultaneously predicting the plurality of future branches based on said retrieved branch and target addresses.
Claim 2
Independent Claim
95 words
A system for simultaneously predicting a plurality of future branches based on an occurrence of a given branch instruction, comprising: a multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a plurality of branch instructions that executed sequentially after the given branch instruction; retrieving means for retrieving said stored branch and target addresses from said multibranch history table upon a next occurrence of the given branch instruction; and predicting means for simultaneously predicting the plurality of future branches based on said retrieved branch and target addresses.
Claim 3
Dependent Claim
30 words
The system of claim 1, further comprising: update means for updating said multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after the branch instruction.
Claim 4
Dependent Claim
84 words
The system of claim 2, wherein said update means comprises: a pending guess queue to hold said retrieved branch and target addresses from said multibranch history table as a pending guess; an update queue to hold branch addresses and target addresses from said subsequent plurality of sequentially executed branch instructions as a potential update sequence; and comparison means for comparing said potential update sequence with said pending guess to determine unstored branch and target addresses of said subsequent plurality of sequentially executed branch instructions.
Claim 5
Dependent Claim
33 words
The system of claim 1, wherein said stored branch and target addresses are stored beginning at a location in said multibranch history table corresponding to a branch address of the given branch instruction.
Claim 6
Dependent Claim
36 words
The system of claim 1, wherein said retrieving means comprises a prefetch address register for retrieving said stored branch and target addresses from said multibranch history table upon a next occurrence of the given branch instruction.
Claim 7
Independent Claim
86 words
A method for simultaneously predicting a plurality of future branches based on an occurrence of a given branch instruction, comprising the steps of: a) storing as an entry in a multibranch history table branch addresses and target addresses for a plurality of branch instructions that executed sequentially after the given branch instruction; b) retrieving said stored branch and target addresses upon a next occurrence of the given branch instruction; and c) simultaneously predicting the plurality of future branches based on said retrieved branch and target addresses.
Claim 8
Independent Claim
86 words
A method for simultaneously predicting a plurality of future branches based on an occurrence of a given branch instruction, comprising the steps of: a) storing as an entry in a multibranch history table branch addresses and target addresses for a plurality of branch instructions that executed sequentially after the given branch instruction; b) retrieving said stored branch and target addresses upon a next occurrence of the given branch instruction; and c) simultaneously predicting the plurality of future branches based on said retrieved branch and target addresses.
Claim 9
Dependent Claim
31 words
The method of claim 6, further comprising the step of: d) updating said multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after the branch instruction.
Claim 10
Dependent Claim
86 words
The method of claim 7, wherein said step of updating comprises the steps of: holding said retrieved branch and target addresses from said multibranch history table as in a pending guess queue as a pending guess; holding branch addresses and target addresses from said subsequent plurality of sequentially executed branch instructions in an update queue as a potential update sequence; and comparing said potential update sequence with said pending guess to determine unstored branch and target addresses of said subsequent plurality of sequentially executed branch instructions.
Claim 11
Dependent Claim
33 words
The method of claim 6, wherein said stored branch and target addresses are stored in a multibranch history table beginning at a location corresponding to a branch address of the given branch instruction.
Claim 12
Independent Claim
168 words
A system for simultaneously predicting a plurality of future branches based on an occurrence of a branch instruction, comprising: a primary multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a first plurality of branch instructions that executed sequentially after a first branch instruction; secondary multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a second plurality of branch instructions that executed sequentially after a second branch instruction; first retrieving means for retrieving said fast stored branch and target addresses from said primary multibranch history table based on a next occurrence of the branch instruction; second retrieving means for retrieving said second stored branch and target addresses from said secondary multibranch history table based on said next occurrence of the branch instruction; and predicting means for simultaneously predicting the plurality of future branches based on said first retrieved branch and target addresses and said second retrieved branch and target addresses.
Claim 13
Independent Claim
168 words
A system for simultaneously predicting a plurality of future branches based on an occurrence of a branch instruction, comprising: a primary multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a first plurality of branch instructions that executed sequentially after a first branch instruction; secondary multibranch history table having one or more entries, each entry for storing branch addresses and target addresses for a second plurality of branch instructions that executed sequentially after a second branch instruction; first retrieving means for retrieving said fast stored branch and target addresses from said primary multibranch history table based on a next occurrence of the branch instruction; second retrieving means for retrieving said second stored branch and target addresses from said secondary multibranch history table based on said next occurrence of the branch instruction; and predicting means for simultaneously predicting the plurality of future branches based on said first retrieved branch and target addresses and said second retrieved branch and target addresses.
Claim 14
Dependent Claim
72 words
The system of claim 10, further comprising comparison means for comparing said first retrieved branch and target addresses with said second retrieved branch and target addresses to detect divergence between said first plurality of branch instructions and said second plurality of branch instructions, wherein said predicting means predicts the plurality of future branches based on said first retrieved branch and target addresses, said second retrieved branch and target addresses, and said divergence.
Claim 15
Dependent Claim
30 words
The system of claim 11, wherein said secondary multibranch history table is offset at least one branch instruction from said primary multibranch history table for facilitating detection of said divergence.
Claim 16
Dependent Claim
40 words
The system of claim 11, further comprising a plurality of said secondary multibranch history tables, wherein each subsequent multibranch history table is offset at least one branch instruction from each prior multibranch history table to facilitate detection of said divergence.
Claim 17
Dependent Claim
56 words
The system of claim 10, further comprising update means for updating said primary multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after said first branch instruction and for updating said secondary multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after said second branch instruction.
Claim 18
Dependent Claim
120 words
The system of claim 14, wherein said update means comprises: a primary pending guess queue to hold said first retrieved branch and target addresses from said primary multibranch history table as a primary pending guess; a secondary pending guess queue to hold said second retrieved branch and target addresses from said secondary multibranch history table as a secondary pending guess; an update queue to hold branch addresses and target addresses from said subsequent plurality of sequentially executed branch instructions as a potential update sequence; and second comparison means for comparing said potential update sequence with said primary pending guess and said secondary pending guess to determine unstored branch and target addresses of said subsequent plurality of sequentially executed branch instructions.
Claim 19
Dependent Claim
81 words
The system of claim 10, wherein said first stored branch and target addresses for said tint plurality of branch instructions are stored beginning at a storage address in said primary multibranch history table corresponding to a branch address of said first branch instruction and said second stored branch and target addresses for said second plurality of branch instructions are stored beginning at a storage address in said secondary multibranch history table corresponding to a branch address of said second branch instruction.
Claim 20
Dependent Claim
102 words
The system of claim 10, wherein said primary multibranch history table stores branch addresses and target addresses for a first set of two branch instructions that executed sequentially after said first branch instruction, said branch and target addresses stored in said primary multibranch history table comprising a first and second primary predicted branch, and wherein said secondary multibranch history table stores branch addresses and target addresses for a second set of two branch instructions that executed sequentially after said second branch instruction, said branch and target addresses stored in said secondary multibranch history table comprising a first and second secondary predicted branch.
Claim 21
Dependent Claim
80 words
The system of claim 17, wherein said predicting means comprises: comparing means for comparing said second primary predicted branch with said first secondary predicted branch to detect divergence between said first set of two branch instructions and said second set of two branch instructions; and selecting means for selecting the plurality of future branches from said first and second primary predicted branches if said divergence does not exist and from said second secondary predicted branch if said divergence does exist.
Claim 22
Independent Claim
158 words
A method for simultaneously predicting a plurality of future branches based on an occurrence of a branch instruction, comprising the steps of: a) storing as an entry in a primary multibranch history table branch addresses and target addresses for a first plurality of branch instructions that executed sequentially after a first branch instruction; b) storing as an entry in a secondary multibranch history table branch addresses and target addresses for a second plurality of branch instructions that executed sequentially after a second branch instruction; c) retrieving said first stored branch and target addresses from said primary multibranch history table based on a next occurrence of the branch instruction; d) retrieving said second stored branch and target addresses from said secondary multibranch history table based on said next occurrence of the branch instruction; and e) simultaneously predicting the plurality of future branches based on said first retrieved branch and target addresses and said second retrieved branch and target addresses.
Claim 23
Independent Claim
158 words
A method for simultaneously predicting a plurality of future branches based on an occurrence of a branch instruction, comprising the steps of: a) storing as an entry in a primary multibranch history table branch addresses and target addresses for a first plurality of branch instructions that executed sequentially after a first branch instruction; b) storing as an entry in a secondary multibranch history table branch addresses and target addresses for a second plurality of branch instructions that executed sequentially after a second branch instruction; c) retrieving said first stored branch and target addresses from said primary multibranch history table based on a next occurrence of the branch instruction; d) retrieving said second stored branch and target addresses from said secondary multibranch history table based on said next occurrence of the branch instruction; and e) simultaneously predicting the plurality of future branches based on said first retrieved branch and target addresses and said second retrieved branch and target addresses.
Claim 24
Dependent Claim
73 words
The method of claim 19, further comprising the step of: f) comparing said first retrieved branch and target addresses with said second retrieved branch and target addresses to detect divergence between said first plurality of branch instructions and said second plurality of branch instructions, wherein said predicting means predicts the plurality of future branches based on said first retrieved branch and target addresses, said second retrieved branch and target addresses, and said divergence.
Claim 25
Dependent Claim
30 words
The method of claim 20, wherein said secondary multibranch history table is offset at least one branch instruction from said primary multibranch history table for facilitating detection of said divergence.
Claim 26
Dependent Claim
65 words
The method of claim 20, further comprising the step of: g) storing as entries in a plurality of secondary multibranch history tables branch addresses and target addresses for a plurality of branch instructions that executed sequentially after a branch instruction, wherein each subsequent multibranch history table is offset at least one branch instruction from each prior multibranch history table to facilitate detection of said divergence.
Claim 27
Dependent Claim
57 words
The method of claim 19, further comprising the steps of: f) updating said primary multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after said first branch instruction; and g) updating said secondary multibranch history table based on a subsequent plurality of branch instructions that executed sequentially after said second branch instruction.
Claim 28
Dependent Claim
120 words
The method of claim 23, wherein said steps of updating comprise the steps of: holding said first retrieved branch and target addresses from said primary multibranch history table in a primary pending guess queue as a primary pending guess; holding said second retrieved branch and target addresses from said secondary multibranch history table in a secondary pending guess queue as a secondary pending guess; holding branch addresses and target addresses from said subsequent plurality of sequentially executed branch instructions in an update queue as a potential update sequence; and comparing said potential update sequence with said primary pending guess and said secondary pending guess to determine unstored branch and target addresses of said subsequent plurality of sequentially executed branch instructions.
Claim 29
Dependent Claim
81 words
The method of claim 19, wherein said first stored branch and target addresses for said first plurality of branch instructions are stored beginning at a storage address in said primary multibranch history table corresponding to a branch address of said first branch instruction and said second stored branch and target addresses for said second plurality of branch instructions are stored beginning at a storage address in said secondary multibranch history table corresponding to a branch address of said second branch instruction.
Claim 30
Dependent Claim
100 words
The method of claim 19, wherein said primary multibranch history table stores branch addresses and target addresses for a first set of two branch instructions that executed sequentially after said first branch instruction, said branch and target addresses in said primary multibranch history table comprising a first and second primary predicted branch, and wherein said secondary multibranch history table stores branch addresses and target addresses for a second set of two branch instructions that executed sequentially after said second branch instruction, said branch and target addresses in said secondary multibranch history table comprising a first and second secondary predicted branch.
Claim 31
Dependent Claim
78 words
The method of claim 26, wherein said step of predicting comprises the steps of: comparing said second primary predicted branch with said first secondary predicted branch to detect divergence between said first set of two branch instructions and said second set of two branch instructions; and selecting the plurality of future branches from said first and second primary predicted branches if said divergence does not exist and from said second secondary predicted branch if said divergence does exist.
References Cited (Backward Citations)
US4430706A
Cited
US4477872A
Cited
US4984154A
Cited
US4764861A
Cited
US4691277A
Cited
US4679141A
Cited
US4763245A
Cited
US4853840A
Cited
US4881170A
Cited
US4991080A
Cited
US4974154A
Cited
US4858104A
Cited
US5175827A
Cited
US4901233A
Cited
US5297281A
Cited
US5317702A
Cited
JPH0342722A
Cited
US5345571A
Cited
US5163140A
Cited
US5276882A
Cited
US5353421A
Cited
US5287467A
Cited
US5333283A
Cited
US5367703A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-07-17 | 1999-01-16 | 1999-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-07-17 | 2003-01-16 | 2003-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-07-17 | 2007-01-16 | 2007-07-18 | $7700.00 | Window Closed / Lapsed |