US5634103A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for minimizing branch misprediction penalties within a processor
Assignee: International Business Machines Corp
•
Filing: 1995-11-09
•
Granted: 1997-05-27
•
Expires: 2015-11-09
Abstract
Abstract A method and system within a processor are disclosed for executing selected instructions among a number of instructions stored within a memory, wherein the processor has a maximum of instructions that can dispatched for execution during each processor cycle. A subset of the instructions are fetched from the memory for execution. A determination is then made whether the set of instructions includes an unresolved branch instruction. In response to a determination that the set of instructions includes an unresolved branch instruction, a prediction is made whether a branch indicated by the branch instruction will be taken or will not be taken. In response to a prediction that the branch will be taken, a nonsequential target instruction indicated by the branch instruction is fetched from memory. A determination is made whether the maximum number of instructions can be dispatched for execution during a processor cycle subsequent to the branch prediction without dispatching instructions within the sequential execution path. In response to a determination that less than the maximum number of target instructions can be dispatched in the processor cycle subsequent to the branch prediction without dispatching instructions within the sequential execution path, an instruction within the sequential execution path is speculatively dispatched for execution. In response to refutation of the branch prediction, the fetch of the nonsequential target instruction is cancelled and the instruction within the sequential execution path is executed, thereby minimizing a performance penalty incurred by the processor due to the mispredicted branch.
Inventors
- 👤 Carl D. Dietz
- 👤 Robert T. Golla
- 👤 Christopher H. Olson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 22:28
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/32; G06F9/38; G06F9/3836; G06F9/3838; G06F9/384; G06F9/3842; G06F9/3861
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
319 words
A method for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said method comprising: fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; in response to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, predicting if a branch indicated by said branch instruction will be taken; in response to said prediction, fetching at least one nonsequential target instruction indicated by said branch instruction from said memory; determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; in response to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, dispatching said predetermined maximum number of instructions for execution; in response to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, speculatively dispatching a sequential instruction which follows said branch instruction for execution; in response to refutation of said branch prediction, cancelling said fetch of said target instruction; and executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 2
Independent Claim
319 words
A method for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said method comprising: fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; in response to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, predicting if a branch indicated by said branch instruction will be taken; in response to said prediction, fetching at least one nonsequential target instruction indicated by said branch instruction from said memory; determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; in response to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, dispatching said predetermined maximum number of instructions for execution; in response to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, speculatively dispatching a sequential instruction which follows said branch instruction for execution; in response to refutation of said branch prediction, cancelling said fetch of said target instruction; and executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 3
Dependent Claim
52 words
The method for executing instructions within a processor of claim 1, wherein each speculatively dispatched instruction is identified by a state of an associated speculative indicator, said method further comprising: in response to refutation of said branch prediction, resetting a speculative indicator associated with said sequential instruction which follows said branch instruction.
Claim 4
Dependent Claim
31 words
The method for executing instructions within a processor of claim 1, said method further comprising: in response to refutation of said branch, fetching additional sequential instructions according to said sequential order.
Claim 5
Dependent Claim
41 words
The method for executing instructions within a processor of claim 1, said method further comprising: in response to resolution of said branch as taken, cancelling said sequential instruction which follows said branch instruction path; and halting dispatch of subsequent sequential instructions.
Claim 6
Dependent Claim
55 words
The method for executing instructions within a processor of claim 1, said method further comprising: in response to a failure to resolve said branch prediction during a processor cycle in which said at least one target instruction is fetched, cancelling said sequential instruction which follows said branch instruction; and halting dispatch of subsequent sequential instructions.
Claim 7
Dependent Claim
20 words
The method for executing instructions within a processor of claim 1, wherein said step of predicting comprises dynamic branch prediction.
Claim 8
Independent Claim
332 words
A system for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a maximum number of instructions that can be dispatched for execution during each processor cycle, said system comprising: means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken; means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction; means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution; means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution; responsive to refutation of said branch prediction, means for cancelling said fetch of said target instruction; and means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 9
Independent Claim
332 words
A system for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a maximum number of instructions that can be dispatched for execution during each processor cycle, said system comprising: means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken; means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction; means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution; means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution; responsive to refutation of said branch prediction, means for cancelling said fetch of said target instruction; and means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 10
Dependent Claim
54 words
The system for executing instructions within a processor of claim 7, wherein each speculatively dispatched instruction is identified by a state of an associated speculative indicator, said system further comprising: means for resetting a speculative indicator associated with said sequential instruction which follows said branch instruction in response to refutation of said branch prediction.
Claim 11
Dependent Claim
26 words
The system for executing instructions within a processor of claim 7, said system further comprising means for fetching additional sequential instructions according to said sequential order.
Claim 12
Dependent Claim
44 words
The system for executing instructions within a processor of claim 7, said system further comprising: means for cancelling said sequential instruction which follows said branch instruction in response to resolution of said branch as taken; and means for halting dispatch of subsequent sequential instructions.
Claim 13
Dependent Claim
56 words
The system for executing instructions within a processor of claim 7, said system further comprising: means for cancelling said sequential instruction which follows said branch instruction in response to a failure to resolve said branch prediction during a processor cycle in which said target instruction is fetched; and means for halting dispatch of subsequent sequential instructions.
Claim 14
Dependent Claim
22 words
The system for executing instructions within a processor of claim 7, wherein said means for predicting comprises a dynamic branch prediction mechanism.
Claim 15
Dependent Claim
326 words
A data processing system, comprising: a memory which stores a plurality of instructions arranged in a sequential order; a processor having a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said processor including: means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken; means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction; means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution; means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution; responsive to refutation of said branch prediction, means for cancelling said fetch of said target instruction; and means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 16
Dependent Claim
326 words
A data processing system, comprising: a memory which stores a plurality of instructions arranged in a sequential order; a processor having a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said processor including: means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor; means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction; means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken; means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction; means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order; means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution; means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution; responsive to refutation of said branch prediction, means for cancelling said fetch of said target instruction; and means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.
Claim 17
Dependent Claim
52 words
The data processing system of claim 13, wherein each speculatively dispatched instruction is identified by a state of an associated speculative indicator, said data processing system further comprising: means for resetting a speculative indicator associated with said sequential instruction which follows said branch instruction in response to refutation of said branch prediction.
Claim 18
Dependent Claim
23 words
The data processing system of claim 13, said data processing system further comprising means for fetching additional instructions according to said sequential order.
Claim 19
Dependent Claim
42 words
The data processing system of claim 13, said data processing system further comprising: means for cancelling said sequential instruction which follows said branch instruction in response to resolution of said branch as taken; and means for halting dispatch of subsequent sequential instructions.
Claim 20
Dependent Claim
57 words
The data processing system of claim 13, said data processing system further comprising: means for cancelling said sequential instruction which follows said branch instruction in response to a failure to resolve said branch prediction during a processor cycle in which said at least one target instruction is fetched; and means for halting dispatch of subsequent sequential instructions.
Claim 21
Dependent Claim
18 words
The data processing system of claim 13, wherein said means for predicting comprises a dynamic branch prediction mechanism.
References Cited (Backward Citations)
US4777594A
Cited
US4833599A
Cited
US4881194A
Cited
US5165025A
Cited
US5127091A
Cited
US5072364A
Cited
US5230068A
Cited
US5283873A
Cited
US5394530A
Cited
US5287467A
Cited
US5381533A
Cited
EP0592125A1
Cited
US5519841A
Cited
US5553255A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-26 | 2000-11-25 | 2001-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-26 | 2004-11-25 | 2005-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-26 | 2008-11-25 | 2009-05-27 | $7700.00 | Window Closed / Lapsed |