US5561776A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Processor architecture supporting multiple speculative branching
Assignee: SK Hynix America Inc
•
Filing: 1995-06-06
•
Granted: 1996-10-01
•
Expires: 2015-06-06
Abstract
Abstract A processor architecture is described which operates with improved computational efficiency using instruction fetching functions that are decoupled from instruction execution functions by a dynamic register file. The instruction fetching function operates in free-running mode which does not stop if a fetched instruction cannot be executed due to data being unavailable or due to other instruction dependencies. Branch instructions are taken in a predicted direction and the results of execution of all instructions are provisionally stored pending validation or invalidation on the basis of the dependencies becoming available later. For branches of executed instructions that are later invalidated, the results of the executed instructions are flushed from provisional storage and the initial instruction which previously executed at the beginning of a branch on predicted dependencies is re-executed on the actual data that subsequently became available, and all subsequent instructions in such branch are also re-executed on the basis of dependencies actually available from execution of previous instructions in such branch.
Inventors
- 👤 Valeri Popescu
- 👤 Merle A. Schultz
- 👤 Gary A. Gibson
- 👤 John E. Spracklen
- 👤 Bruce D. Lightner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3854; G06F9/3856; G06F9/3802; G06F9/3836; G06F9/3838; G06F9/384; G06F9/3842; G06F9/3844; G06F9/3858; G06F9/3861; G06F9/3863; G06F9/3865; G06F9/3885
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
326 words
A data processing system that performs operations responsive to a program including a plurality of instructions, the instructions including arithmetic instructions at least a first and second test instruction and at least a first and second branch instruction that determine an intended sequence of execution of the instructions within the program responsive to results of the first and second test instructions respectively, the system comprising: an operation unit that executes the instructions by performing operations responsive to the instructions, the operation unit being capable of executing instructions out of order in which they appear in the program; a branch prediction unit that speculates a first intended sequence of execution of the instructions responsive to the first branch instruction and speculates a second intended sequence of execution of the instructions responsive to the second branch instruction, the first and second intended sequences affecting sequence of execution of instructions by the operation unit; an evaluation unit that determines, responsive to execution of the first test instruction by the operation unit, whether the branch prediction unit has speculated the first intended sequence correctly, wherein the branch prediction unit speculates the second intended sequence prior to execution of the first test instruction; a repair unit that, upon a determination by the evaluation unit that the branch unit has speculated either the first intended sequence or the second intended sequence incorrectly, nullifies the effects of instructions of the incorrectly speculated intended sequence; a register unit that stores data on which to operate; a temporary storage unit that stores the results of operations performed responsive to arithmetic instructions and for storing each result in a unique location; and a retirement unit that retires each unnullified instruction in the order it appears in the program, the retirement unit retiring an arithmetic instruction after the result of an operation performed responsive to the instruction are stored in the temporary storage unit, by removing the result therefrom and updating the register unit with the result.
Claim 2
Dependent Claim
326 words
A data processing system that performs operations responsive to a program including a plurality of instructions, the instructions including arithmetic instructions at least a first and second test instruction and at least a first and second branch instruction that determine an intended sequence of execution of the instructions within the program responsive to results of the first and second test instructions respectively, the system comprising: an operation unit that executes the instructions by performing operations responsive to the instructions, the operation unit being capable of executing instructions out of order in which they appear in the program; a branch prediction unit that speculates a first intended sequence of execution of the instructions responsive to the first branch instruction and speculates a second intended sequence of execution of the instructions responsive to the second branch instruction, the first and second intended sequences affecting sequence of execution of instructions by the operation unit; an evaluation unit that determines, responsive to execution of the first test instruction by the operation unit, whether the branch prediction unit has speculated the first intended sequence correctly, wherein the branch prediction unit speculates the second intended sequence prior to execution of the first test instruction; a repair unit that, upon a determination by the evaluation unit that the branch unit has speculated either the first intended sequence or the second intended sequence incorrectly, nullifies the effects of instructions of the incorrectly speculated intended sequence; a register unit that stores data on which to operate; a temporary storage unit that stores the results of operations performed responsive to arithmetic instructions and for storing each result in a unique location; and a retirement unit that retires each unnullified instruction in the order it appears in the program, the retirement unit retiring an arithmetic instruction after the result of an operation performed responsive to the instruction are stored in the temporary storage unit, by removing the result therefrom and updating the register unit with the result.
Claim 3
Dependent Claim
54 words
The data processing system according to claim 1 wherein the repair unit nullifies an instruction by reversing any update of results to the temporary storage unit affected by the nullified instruction and preventing any further update of results to the temporary storage unit by any future performance of operations responsive to the nullified instruction.
Claim 4
Dependent Claim
35 words
The data processing system according to claim 1 further comprising a branch shelving unit that stores the first and second branch instructions from the branch predicting unit speculates the first and second intended sequences respectively.
Claim 5
Dependent Claim
42 words
The data processing system according to claim 3 wherein the repair unit removes the first branch instructions and the second branch instructions from the branch instructions shelving unit when the evaluation unit determines the first intended sequence to have been speculated incorrectly.
Claim 6
Dependent Claim
34 words
The data processing system according to claim 1 wherein the retirement unit retires the first branch instruction after the first intended sequence has been determined to have been correctly speculated by the predicting unit.
Claim 7
Dependent Claim
35 words
The data processing system according to claim 1 wherein the repair unit nullifies an arithmetic instruction by removing results of a result of an operation performed responsive to the instruction from the temporary storage unit.
Claim 8
Dependent Claim
61 words
The data processing system according to claim 6 wherein, when the evaluating unit determines the first intended sequence to have been speculated incorrectly, the repairing unit preserves results of operations performed responsive to instructions preceding the first branch instruction stored in the temporary storage unit and removes the results of operations performed responsive to instructions that follow the first branch instruction.
Claim 9
Dependent Claim
31 words
The data processing system according to claim 7 wherein the temporary storage unit further associates a result identifier with each operation performed responsive to an instruction in the first intended sequence.
Claim 10
Dependent Claim
21 words
The data processing system according to claim 8 wherein the association between the result identifier and each operation performed is one-to-one.
Claim 11
Dependent Claim
45 words
The data processing system according to claim 9 wherein each result identifier is associated with each operation performed responsive to an instruction in the first intended sequence such that the relative position of any two such operations can be determined from their associated result identifiers.
Claim 12
Dependent Claim
25 words
The data processing system according to claim 10 wherein one of the two operations corresponds to a branch instruction stored in the branch shelving unit.
Claim 13
Dependent Claim
23 words
The data processing system according to claim 10 wherein one of the two operations has a result stored in the temporary storage unit.
Claim 14
Dependent Claim
16 words
The data processing system according to claim 9 wherein the number of result identifiers is finite.
Claim 15
Dependent Claim
58 words
The data processing system according to claim 8 wherein the repair unit determines the removal of an operation's result from the temporary storage unit based on the relationship between the operation's result identifier and the result identifier of the first branch instruction regardless of the temporal order in which operation results were placed into the temporary storage unit.
Claim 16
Dependent Claim
46 words
The data processing system according to claim 8 wherein the repair unit repairs the first branch instruction even though there are results of operations performed responsive to instructions preceding the first branch instruction stored in the temporary storage unit not yet transferred to the register unit.
Claim 17
Dependent Claim
28 words
The data processing system according to claim 8 wherein the repair unit preserves the results in the temporary storage unit and nullifies instructions following the first branch instruction.
Claim 18
Dependent Claim
22 words
The data processing system according to claim 1 wherein the repair unit nullifies only the instructions of the incorrectly speculated intended sequence.
Claim 19
Dependent Claim
280 words
A data processing system that performs operations responsive to a program including a plurality of instructions, the instructions including at least a first and second test instruction and at least a first and second branch instruction that determine an intended sequence of execution of the instructions within the program responsive to results of the first and second test instructions respectively, the system comprising: an operation unit that executes the instructions by performing operations responsive to the instructions; a branch prediction unit that speculates a first intended sequence of execution of the instructions responsive to the first branch instruction and speculates a second intended sequence of execution of the instructions responsive to the second branch instruction, the first and second intended sequences affecting sequence of execution of instructions by the operation unit; an evaluation unit that determines, responsive to execution of the first test instruction by the operation unit, whether the branch prediction unit has speculated the first intended sequence correctly, wherein the branch prediction unit speculates the second intended sequence prior to execution of the first test instruction; a repair unit that, upon a determination by the evaluation unit that the branch unit has speculated either the first intended sequence or the second intended sequence incorrectly, nullifies the effects of instructions of the incorrectly speculated intended sequence; and a result storage unit that stores results of the operations performed responsive to the instructions, and wherein the repair unit nullifies an instruction by reversing any update of results to the result storage unit affected by the nullified instruction and preventing any further update of results to the result storage unit by any future performance of operations responsive to the nullified instruction.
Claim 20
Dependent Claim
280 words
A data processing system that performs operations responsive to a program including a plurality of instructions, the instructions including at least a first and second test instruction and at least a first and second branch instruction that determine an intended sequence of execution of the instructions within the program responsive to results of the first and second test instructions respectively, the system comprising: an operation unit that executes the instructions by performing operations responsive to the instructions; a branch prediction unit that speculates a first intended sequence of execution of the instructions responsive to the first branch instruction and speculates a second intended sequence of execution of the instructions responsive to the second branch instruction, the first and second intended sequences affecting sequence of execution of instructions by the operation unit; an evaluation unit that determines, responsive to execution of the first test instruction by the operation unit, whether the branch prediction unit has speculated the first intended sequence correctly, wherein the branch prediction unit speculates the second intended sequence prior to execution of the first test instruction; a repair unit that, upon a determination by the evaluation unit that the branch unit has speculated either the first intended sequence or the second intended sequence incorrectly, nullifies the effects of instructions of the incorrectly speculated intended sequence; and a result storage unit that stores results of the operations performed responsive to the instructions, and wherein the repair unit nullifies an instruction by reversing any update of results to the result storage unit affected by the nullified instruction and preventing any further update of results to the result storage unit by any future performance of operations responsive to the nullified instruction.
Claim 21
Dependent Claim
27 words
The data processing system according to claim 18 wherein the operation unit is capable of executing instructions out of order in which they appear in the program.
Claim 22
Dependent Claim
35 words
The data processing system according to claim 18 further comprising a branch shelving unit that stores the first and second branch instructions when the branch predicting unit speculates the first and second intended sequences respectively.
Claim 23
Dependent Claim
22 words
The data processing system according to claim 18 wherein said repair unit nullifies only the instructions of the incorrectly speculated intended sequence.
Claim 24
Dependent Claim
42 words
The data processing system according to claim 20 wherein the repair unit removes the first branch instruction and the second branch instruction from the branch instruction shelving unit when the evaluation unit determines the first intended sequence to have been speculated incorrectly.
Claim 25
Dependent Claim
115 words
The data processing system according to claim 20 wherein the program includes arithmetic instructions to control arithmetic operations on data, the result storing unit further comprising: a register unit that stores data on which to operate; a temporary storage unit that stores the results of operations performed responsive to arithmetic instructions and for storing each result in a unique location; and a retirement unit that retires each unnullified instruction in the order it appears in the program, the retirement unit retiring an arithmetic instruction after the result of an operation performed responsive to the instruction are stored in the temporary storage unit, by removing the result therefrom and updating the register unit with the result.
Claim 26
Dependent Claim
34 words
The data processing system according to claim 23 wherein the retirement unit retires the first branch instruction after the first intended sequence has been determined to have been correctly speculated by the predicting unit.
Claim 27
Dependent Claim
34 words
The data processing system according to claim 23 wherein the repair unit nullifies an arithmetic instruction by removing results of a result of an operation performed responsive the instruction from the temporary storage unit.
Claim 28
Dependent Claim
61 words
The data processing system according to claim 25 wherein, when the evaluating unit determines the first intended sequence to have been speculated incorrectly, the repairing unit preserves results of operations performed responsive to instructions preceding the first branch instruction stored in the temporary storage unit and removes the results of operations performed responsive to instructions that follow the first branch instruction.
Claim 29
Dependent Claim
31 words
The data processing system according to claim 25 wherein the temporary storage unit further associates a result identifier with each operation performed responsive to an instruction in the first intended sequence.
Claim 30
Dependent Claim
21 words
The data processing system according to claim 27 wherein the association between the result identifier and each operation performed is one-to-one.
Claim 31
Dependent Claim
58 words
The data processing system according to claim 27 wherein the repair unit determines the removal of an operation's result from the temporary storage unit based on the relationship between the operation's result identifier and the result identifier of the first branch instruction regardless of the temporal order in which operation results were placed into the temporary storage unit.
Claim 32
Dependent Claim
46 words
The data processing system according to claim 27 wherein the repair unit repairs the first branch instruction even though there are results of operations performed responsive to instructions preceding the first branch instruction stored in the temporary storage unit not yet transferred to the register unit.
Claim 33
Dependent Claim
28 words
The data processing system according to claim 27 wherein the repair unit preserves the results in the temporary storage unit and nullifies instructions following the first branch instruction.
Claim 34
Dependent Claim
45 words
The data processing system according to claim 28 wherein each result identifier is associated with each operation performed responsive to an instruction in the first intended sequence such that the relative position of any two such operations can be determined from their associated result identifiers.
Claim 35
Dependent Claim
16 words
The data processing system according to claim 28 wherein the number of result identifiers is finite.
Claim 36
Dependent Claim
25 words
The data processing system according to claim 32 wherein one of the two operations corresponds to a branch instruction stored in the branch shelving unit.
Claim 37
Dependent Claim
23 words
The data processing system according to claim 32 wherein one of the two operations has a result stored in the temporary storage unit.
Claim 38
Dependent Claim
228 words
A data processing system capable of executing a sequence of instructions, the sequence including a plurality of branch instructions, each branch instruction of the plurality associated with a test instruction, the data processing system comprising: means for predicting speculative sequences of instructions following each branch instruction within the sequence of instructions; means for fetching the speculative sequences of instructions from an instruction memory; means for performing operations responsive to instructions in the instruction sequence, including the speculative sequences; means for shelving the plurality of branch instructions; means for evaluating each branch instruction stored in the shelving means subsequent to performance of an operation responsive to the test instruction associated with the branch instruction to determine based on a result of the operation performed responsive to the test instruction whether the branch instruction associated with the test instruction was correctly predicted; and means, upon detection of an incorrectly predicted branch instruction by the evaluating means, for repairing the incorrectly predicted branch instruction and instructions of the speculative sequence following the branch instruction predicted by the predicting means; wherein the predicting means is capable of predicting a speculative sequence of instructions following a later branch instruction while an earlier branch instruction remains unevaluated and the repairing means is capable of repairing the either the later branch instruction of the earlier branch instruction if they are determined to be incorrectly predicted.
Claim 39
Dependent Claim
228 words
A data processing system capable of executing a sequence of instructions, the sequence including a plurality of branch instructions, each branch instruction of the plurality associated with a test instruction, the data processing system comprising: means for predicting speculative sequences of instructions following each branch instruction within the sequence of instructions; means for fetching the speculative sequences of instructions from an instruction memory; means for performing operations responsive to instructions in the instruction sequence, including the speculative sequences; means for shelving the plurality of branch instructions; means for evaluating each branch instruction stored in the shelving means subsequent to performance of an operation responsive to the test instruction associated with the branch instruction to determine based on a result of the operation performed responsive to the test instruction whether the branch instruction associated with the test instruction was correctly predicted; and means, upon detection of an incorrectly predicted branch instruction by the evaluating means, for repairing the incorrectly predicted branch instruction and instructions of the speculative sequence following the branch instruction predicted by the predicting means; wherein the predicting means is capable of predicting a speculative sequence of instructions following a later branch instruction while an earlier branch instruction remains unevaluated and the repairing means is capable of repairing the either the later branch instruction of the earlier branch instruction if they are determined to be incorrectly predicted.
Claim 40
Dependent Claim
41 words
The data processing system according to claim 36 wherein the repairing means nullifies effects of the incorrectly-predicted branch instruction and all the instructions in the speculative sequence following the branch instruction and causes the fetching means to re-fetch the branch instruction.
Claim 41
Dependent Claim
78 words
The data processing system according to claim 37 further comprising means for storing results of the operations performed responsive to the instructions in the speculative sequences, and wherein the repairing means nullifies an instruction by reversing any update of results to the storage means effected by the performance of any operation responsive to the nullified instruction and preventing any further update of results to the storage means by any future performance of operations responsive to the nullified instruction.
Claim 42
Dependent Claim
33 words
The data processing system according to claim 36 wherein the operation performing means is capable of performing operations responsive to instructions out of order in which the instructions appear in the instruction sequence.
Claim 43
Dependent Claim
36 words
The data processing system according to claim 36 wherein the repairing means removes an incorrectly-predicted branch instruction and all branch instructions in the speculative sequence following the incorrectly-predicted branch instruction from the branch instruction shelving means.
Claim 44
Dependent Claim
36 words
The data processing system according to claim 40 wherein the repairing means repairs the incorrectly-predicted branch instruction even if another branch instruction preceding the incorrectly-predicted branch instruction has not yet been evaluated by the evaluating means.
Claim 45
Dependent Claim
111 words
The data processing system according to claim 36 wherein the sequence of instructions includes instructions to control arithmetic operations on data, the storing means further comprising: register means for storing data on which to operate; temporary storage means for receiving the results of operations performed responsive to arithmetic instructions and for storing each result in a unique location; and means for retiring each unnullified instruction in the order it appeared in the speculative sequence, the means retiring an arithmetic instruction after the results of an operation performed responsive to the instruction are stored in the temporary storage means, by removing the results therefrom and updating the register means with the results.
Claim 46
Dependent Claim
43 words
The data processing system according to claim 42 wherein the retiring means retires a branch instruction after the branch instruction has been determined not to have been incorrectly predicted by the evaluating means, and has been removed from the branch instruction shelving means.
Claim 47
Dependent Claim
32 words
The data processing system according to claim 43 wherein the repairing means nullifies an arithmetic instruction by removing results of an operation performed responsive to the instruction from the temporary storage means.
Claim 48
Dependent Claim
48 words
The data processing system according to claim 44 wherein the repairing means preserves results of operations performed responsive to instructions preceding an incorrectly predicted branch instruction stored in the temporary storage means and removes the results of operations performed responsive to instructions that follow the incorrectly-predicted branch instruction.
Claim 49
Dependent Claim
30 words
The data processing system according to claim 42 wherein the temporary storage means further associates a result identifier with each operation performed responsive to an instruction in a speculative sequence.
Claim 50
Dependent Claim
20 words
The data processing system according to claim 46 wherein the association between the result identifier and each instruction is one-to-one.
Claim 51
Dependent Claim
38 words
The data processing system according to claim 47 wherein each result identifier is associated with each instruction in the speculative sequence such that the relative position of any two instructions can be determined from their associated result identifiers.
Claim 52
Dependent Claim
24 words
The data processing system according to claim 48 wherein one of the two instructions is a branch instruction stored in the branch shelving means.
Claim 53
Dependent Claim
28 words
The data processing system according to claim 49 wherein one of the two instructions has results of operations performed responsive to it stored in the temporary storage means.
Claim 54
Dependent Claim
16 words
The data processing system according to claim 48 wherein the number of result identifiers is finite.
Claim 55
Dependent Claim
65 words
The data processing system according to claim 46 wherein the repairing means determines the removal of a result of an operation performed responsive to an instruction from the temporary storage means based on the relationship between the instruction's result identifier and the result identifier of the incorrectly-predicted branch instruction regardless of the temporal order in which instruction results were placed into the temporary storage means.
Claim 56
Dependent Claim
41 words
The data processing system according to claim 46 wherein the repairing means repairs an incorrectly-predicted branch instruction even though-there are results of instructions preceding the incorrectly-predicted branch instruction stored in the temporary storage means not yet transferred to the register means.
Claim 57
Dependent Claim
28 words
The data processing system according to claim 46 wherein the repairing means preserves the results in the temporary storage means and nullifies instructions following the incorrectly-predicted branch instruction.
Claim 58
Dependent Claim
42 words
The data processing system according to claim 36 wherein said repairing means, upon detection of an incorrectly predicted branch instruction, repairs only the incorrectly predicted branch instruction and instructions of the speculative sequence following the branch instruction predicted by the predicting means.
References Cited (Backward Citations)
US4325121A
Cited
US4338661A
Cited
US4342078A
Cited
US4402042A
Cited
US4807113A
Cited
US4675806A
Cited
US4626989A
Cited
US4807115A
Cited
US4803615A
Cited
US5146570A
Cited
US4722049A
Cited
US4811215A
Cited
US4926323A
Cited
US5226126A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-01 | 2000-04-01 | 2000-10-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-01 | 2004-04-01 | 2004-10-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-01 | 2008-04-01 | 2008-10-01 | $7700.00 | Window Closed / Lapsed |