Patent US3724735A successfully refreshed from Google Patents.
Patent US5758142A successfully refreshed from Google Patents.
US5758142A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Trainable apparatus for predicting instruction outcomes in pipelined processors
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-05-31
•
Granted: 1998-05-26
•
Expires: 2014-05-31
Abstract
Abstract A predictor which chooses between two or more predictors is described. The predictor includes a first component predictor which operates according to a first algorithm to produce a prediction of an action and a second component predictor which operates according to a second algorithm to produce a prediction of said action. The predictor also includes means, coupled to each of said first and second predictors, for choosing between predictions provided from said predictors to provide a prediction of the action from the predictor. The predictor can be used to predict outcomes of branches, cache hits, prefetched instruction sequences, and so forth.
Inventors
- 👤 Scott McFarling
- 👤 Simon C. Steely, Jr.
- 👤 Joel Emer
- 👤 Edward McLellan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 09:32
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3848; G06F9/32; G06F9/322; G06F9/323
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
95 words
A predictor for generating a prediction of an instruction outcome from prior instruction outcomes, comprising: a first component predictor which operates on said prior instruction outcomes according to a first algorithm to produce a prediction of said instruction outcome; a second component predictor which operates on said prior instruction outcomes according to a second algorithm to produce a prediction of said instruction outcome; and means, coupled to each of said first and second component predictors, for choosing between predictions provided from said component predictors to provide a prediction of said instruction outcome from said predictor.
Claim 2
Dependent Claim
95 words
A predictor for generating a prediction of an instruction outcome from prior instruction outcomes, comprising: a first component predictor which operates on said prior instruction outcomes according to a first algorithm to produce a prediction of said instruction outcome; a second component predictor which operates on said prior instruction outcomes according to a second algorithm to produce a prediction of said instruction outcome; and means, coupled to each of said first and second component predictors, for choosing between predictions provided from said component predictors to provide a prediction of said instruction outcome from said predictor.
Claim 3
Dependent Claim
54 words
The predictor of claim 1 wherein said means for choosing comprises: means for training said means for choosing, said means for training being responsive to predictions from each of said component predictors and to a signal indicating an actual outcome of the instruction for which an instruction outcome prediction was generated by said predictor.
Claim 4
Dependent Claim
21 words
The predictor of claim 2 wherein said means for choosing is a bank of counters responsive to the predicted instruction outcome.
Claim 5
Dependent Claim
26 words
The predictor of claim 3 wherein said means for choosing has a number of counters corresponding to a size of the first and second component predictors.
Claim 6
Dependent Claim
21 words
The predictor of claim 4 wherein said means for choosing is indexed by an index which addresses the first component predictor.
Claim 7
Dependent Claim
21 words
The predictor of claim 4 wherein said means for choosing is indexed by an index which addresses the second component predictor.
Claim 8
Dependent Claim
22 words
The predictor of claim 1 wherein said first component predictor is a local predictor and said second predictor is a global predictor.
Claim 9
Dependent Claim
24 words
The predictor of claim 7 wherein said first component predictor is responsive to an address of said instruction whose outcome is currently being predicted.
Claim 10
Dependent Claim
25 words
The predictor of claim 8 wherein said first component predictor produces a prediction based upon a history of outcomes of said instruction at the address.
Claim 11
Dependent Claim
32 words
The predictor of claim 1 wherein said second component predictor is a global path predictor and said means for choosing is indexed via a global path history of said global path predictor.
Claim 12
Dependent Claim
39 words
The predictor of claim 1 wherein said second component predictor is a global path predictor and said means for choosing is indexed via a global path history of said global path predictor and by bits of a program counter.
Claim 13
Dependent Claim
49 words
The predictor of claim 1 wherein said second component predictor is a global path predictor and said means for choosing is indexed via a global path history of said global path predictor and by bits of a program counter with said bits being exclusive-or'ed with said global path history.
Claim 14
Dependent Claim
99 words
A choosing branch predictor, comprising: a first component branch predictor which operates according to a past history branch algorithm to produce a prediction of whether an instruction will or will not take a branch; a second component branch predictor which operates according to a global path history algorithm to produce a prediction of whether said instruction will or will not take a branch; and means, coupled to each of said first and second component predictors, for choosing between predictions provided from said first and second component predictors to provide a prediction of the branch from the choosing branch predictor.
Claim 15
Dependent Claim
99 words
A choosing branch predictor, comprising: a first component branch predictor which operates according to a past history branch algorithm to produce a prediction of whether an instruction will or will not take a branch; a second component branch predictor which operates according to a global path history algorithm to produce a prediction of whether said instruction will or will not take a branch; and means, coupled to each of said first and second component predictors, for choosing between predictions provided from said first and second component predictors to provide a prediction of the branch from the choosing branch predictor.
Claim 16
Dependent Claim
57 words
The predictor of claim 13 wherein said means for choosing comprises: means for training said means for choosing, said means for training being responsive to predictions from each of said first and second component predictors and to a signal indicating an actual outcome of the instruction for which an instruction outcome prediction was generated by the predictor.
Claim 17
Dependent Claim
23 words
The predictor of claim 14 wherein said means for choosing is a bank of counters responsive to a resolution of the predicted action.
Claim 18
Dependent Claim
26 words
The predictor of claim 15 wherein said means for choosing has a number of counters corresponding to a size of the first and second component predictors.
Claim 19
Dependent Claim
21 words
The predictor of claim 16 wherein said means for choosing is indexed by an index which addresses the first component predictor.
Claim 20
Dependent Claim
21 words
The predictor of claim 15 wherein said means for choosing is indexed by an index which addresses the second component predictor.
Claim 21
Dependent Claim
24 words
The predictor of claim 15 wherein said first component predictor is responsive to an address of an instruction whose action is currently being predicted.
Claim 22
Dependent Claim
181 words
A tournament predictor, comprising: a first choosing predictor, comprising: a first component predictor which operates according to a first algorithm to produce a prediction of an action; a second component predictor which operates according to a second algorithm to produce a prediction of said action; and means, coupled to each of said first and second predictors, for choosing between predictions provided from said predictors to provide a prediction of the action from the first choosing predictor; a second choosing predictor, comprising: a third component predictor which operates according to a third algorithm to produce a prediction of an action; a fourth component predictor which operates according to a fourth algorithm to produce a prediction of said action; and means, coupled to each of said third and fourth predictors, for choosing between predictions provided from said predictors to provide a prediction of the action from the second choosing predictor; and means, coupled to each of said first and second choosing predictors, for choosing between predictions provided from said choosing predictors to provide a prediction of the action from said tournament choosing predictor.
Claim 23
Dependent Claim
181 words
A tournament predictor, comprising: a first choosing predictor, comprising: a first component predictor which operates according to a first algorithm to produce a prediction of an action; a second component predictor which operates according to a second algorithm to produce a prediction of said action; and means, coupled to each of said first and second predictors, for choosing between predictions provided from said predictors to provide a prediction of the action from the first choosing predictor; a second choosing predictor, comprising: a third component predictor which operates according to a third algorithm to produce a prediction of an action; a fourth component predictor which operates according to a fourth algorithm to produce a prediction of said action; and means, coupled to each of said third and fourth predictors, for choosing between predictions provided from said predictors to provide a prediction of the action from the second choosing predictor; and means, coupled to each of said first and second choosing predictors, for choosing between predictions provided from said choosing predictors to provide a prediction of the action from said tournament choosing predictor.
Claim 24
Dependent Claim
103 words
Trainable apparatus for predicting an outcome of an instruction in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to a previous outcome of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a previous outcome of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
Claim 25
Dependent Claim
103 words
Trainable apparatus for predicting an outcome of an instruction in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to a previous outcome of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a previous outcome of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
Claim 26
Dependent Claim
29 words
The apparatus of claim 21 wherein said first component predictor is responsive to a plurality of previous outcomes of said instruction for producing a prediction of said instruction outcome.
Claim 27
Dependent Claim
30 words
The apparatus of claim 21 wherein said second component predictor is responsive to a plurality of previous outcomes of said other instruction for producing a prediction of said instruction outcome.
Claim 28
Dependent Claim
15 words
The apparatus of claim 21 wherein said instruction is part of a prefetched instruction sequence.
Claim 29
Dependent Claim
97 words
A pipelined computer processor having a branch predictor for predicting whether a conditional branch will be taken as a result of a conditional branch instruction, said branch predictor comprising: a first component predictor which operates according to a first algorithm to produce a first prediction of whether said conditional branch will taken; a second component predictor which operates according to a second algorithm to produce a second prediction of whether said conditional branch will be taken; and means, coupled to each of said first and second component predictors, for choosing one of said first and second predictions.
Claim 30
Dependent Claim
97 words
A pipelined computer processor having a branch predictor for predicting whether a conditional branch will be taken as a result of a conditional branch instruction, said branch predictor comprising: a first component predictor which operates according to a first algorithm to produce a first prediction of whether said conditional branch will taken; a second component predictor which operates according to a second algorithm to produce a second prediction of whether said conditional branch will be taken; and means, coupled to each of said first and second component predictors, for choosing one of said first and second predictions.
Claim 31
Dependent Claim
34 words
The pipelined computer processor of claim 25, further comprising: means, responsive to the chosen one of said first and second predictions, for loading an instruction execution pipeline in said pipelined computer processor with instructions.
Claim 32
Dependent Claim
29 words
The pipelined computer processor of claim 25, wherein said first algorithm generates said first prediction based in part on whether said conditional branch had been taken in the past.
Claim 33
Dependent Claim
32 words
The pipelined computer processor of claim 25, wherein said second algorithm generates said second prediction based in part on whether at least one other conditional branch preceding said conditional branch was taken.
Claim 34
Dependent Claim
41 words
The pipelined computer processor of claim 25, wherein said choosing means is responsive to a prediction accuracy of said first component predictor and to a prediction accuracy of said second component predictor for choosing one of said first and second predictions.
Claim 35
Dependent Claim
113 words
Trainable apparatus for predicting an outcome of an instruction in an instruction stream in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to a location in said instruction stream of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a location in said instruction stream of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
Claim 36
Dependent Claim
113 words
Trainable apparatus for predicting an outcome of an instruction in an instruction stream in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to a location in said instruction stream of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a location in said instruction stream of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
Claim 37
Dependent Claim
109 words
Trainable apparatus for predicting an outcome of an instruction in an instruction stream in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to an outcome of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a location in said instruction stream of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
Claim 38
Dependent Claim
109 words
Trainable apparatus for predicting an outcome of an instruction in an instruction stream in a pipelined processor, said apparatus comprising: a first component predictor which is responsive to an outcome of said instruction for producing a prediction of said instruction outcome; a second component predictor which is responsive to a location in said instruction stream of an instruction other than said instruction for producing a prediction of said instruction outcome; and training means, coupled to each of said first and second component predictors and responsive to a plurality of previous instruction outcomes for choosing between predictions provided from said component predictors to provide a predicted outcome from said apparatus.
References Cited (Backward Citations)
US4559563A
Cited
US5136696A
Cited
US5179673A
Cited
US5515518A
Cited
US5394529A
Cited
US5276882A
Cited
US5353421A
Cited
US5434985A
Cited
US5504867A
Cited
US5454117A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |