US5802386A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Latency-based scheduling of instructions in a superscalar processor
Assignee: International Business Machines Corp
•
Filing: 1996-11-19
•
Granted: 1998-09-01
•
Expires: 2016-11-19
Abstract
Abstract Instructions are efficiently scheduled for execution based on a stored identification of the first processor cycle when a result of a previous instruction required as an operand for the instruction to be scheduled will become available. Examination of stored processor cycle identifications for the operands of an instruction reveals the earliest processor cycle when the instruction may be executed. By selecting the greater of the largest stored processor cycle identification for an operand of the instruction and the earliest available processor cycle for an execution unit required to execute the instruction, the instruction is efficiently scheduled for the earliest possible execution. Latency of previous instructions in generating an operand of the instruction being scheduled is automatically accommodated.
Inventors
- 👤 James A. Kahle
- 👤 Soummya Mallick
- 👤 Robert G. McDonald
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:32
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3838; G06F9/384; G06F9/3854; G06F9/3856
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
120 words
A method of efficiently scheduling instructions for execution by a processor, comprising: identifying, utilizing a register dependence and an instruction latency, a first available cycle in which an operand of an instruction is predicted to become available; scheduling said instruction for execution during said identified first available cycle; predicting a cycle in which a result of said instruction will be available utilizing a latency of said instruction; and storing a cycle identification for said cycle in which said result of said instruction is predicted be available in a scheduling map position associated with a target register for said result of said instruction, such that said instruction is efficiently scheduled for execution by a processor utilizing register dependence and instruction latency.
Claim 2
Independent Claim
120 words
A method of efficiently scheduling instructions for execution by a processor, comprising: identifying, utilizing a register dependence and an instruction latency, a first available cycle in which an operand of an instruction is predicted to become available; scheduling said instruction for execution during said identified first available cycle; predicting a cycle in which a result of said instruction will be available utilizing a latency of said instruction; and storing a cycle identification for said cycle in which said result of said instruction is predicted be available in a scheduling map position associated with a target register for said result of said instruction, such that said instruction is efficiently scheduled for execution by a processor utilizing register dependence and instruction latency.
Claim 3
Dependent Claim
21 words
The method of claim 1 further comprising repeating said scheduling and storing steps for each instruction in a plurality of instructions.
Claim 4
Dependent Claim
51 words
The method of claim 1 wherein said step of scheduling an instruction for execution further comprises: examining a stored cycle identification in a scheduling map position corresponding to a register containing an operand of said instruction; and scheduling said instruction for execution during a cycle corresponding to said stored cycle identification.
Claim 5
Dependent Claim
74 words
The method of claim 1 wherein said step of scheduling an instruction for execution further comprises: comparing a stored cycle identification in a scheduling map position corresponding to a register containing a first operand of said instruction with a stored cycle identification in a scheduling map position corresponding to a register containing a second operand of said instruction; and scheduling said instruction for execution during a cycle corresponding to a largest stored cycle identification.
Claim 6
Dependent Claim
79 words
The method of claim 4 wherein said instruction comprises a first instruction, said method further comprising: scheduling a second instruction for execution during an earliest available cycle in which an operand of said second instruction is predicted to become available; and storing a cycle identification for an earliest cycle in which a result of said second instruction is predicted to be available in a scheduling map position associated with a target register for said result of said second instruction.
Claim 7
Dependent Claim
52 words
The method of claim 5 wherein said step of scheduling a second instruction further comprises: examining a stored cycle identification in a scheduling map position corresponding to a register containing an operand of said second instruction; and scheduling said second instruction for execution during a cycle corresponding to said stored cycle identification.
Claim 8
Dependent Claim
41 words
The method of claim 1 wherein said step of scheduling an instruction for execution further comprises: determining an earliest available cycle for an execution unit required to execute said instruction; and scheduling said instruction for execution during said earliest available cycle.
Claim 9
Dependent Claim
96 words
The method of claim 1 wherein said step of storing a processor cycle identification further comprises: adding a number of cycles required to execute said instruction to a cycle identification for said first available cycle during which said instruction is scheduled to execute; and storing a sum of said addition of said number of cycles with said first available cycle identification as said cycle identification for said cycle in which said result of said instruction is predicted to be available in a scheduling map position associated with a target register for said result of said instruction.
Claim 10
Independent Claim
132 words
An apparatus for efficiently scheduling instructions for execution by a processor, comprising: identification means for identifying, utilizing a register dependence and an instruction latency, a first available cycle in which an operand of an instruction is predicted to become available; scheduling means for scheduling said instruction for execution during said identified first available cycle; prediction means for predicting a cycle in which a result of said instruction will be available utilizing a latency of said instruction; and memory means for storing a cycle identification for said cycle in which said result of said instruction is predicted be available in a scheduling map position associated with a target register for said result of said instruction, such that said instruction is efficiently scheduled for execution by a processor utilizing register dependence and instruction latency.
Claim 11
Independent Claim
132 words
An apparatus for efficiently scheduling instructions for execution by a processor, comprising: identification means for identifying, utilizing a register dependence and an instruction latency, a first available cycle in which an operand of an instruction is predicted to become available; scheduling means for scheduling said instruction for execution during said identified first available cycle; prediction means for predicting a cycle in which a result of said instruction will be available utilizing a latency of said instruction; and memory means for storing a cycle identification for said cycle in which said result of said instruction is predicted be available in a scheduling map position associated with a target register for said result of said instruction, such that said instruction is efficiently scheduled for execution by a processor utilizing register dependence and instruction latency.
Claim 12
Dependent Claim
56 words
The apparatus of claim 9 wherein said scheduling means further comprises: examination means for examining a stored cycle identification in a scheduling map position corresponding to a register containing an operand of said instruction; and said scheduling means further comprising means for scheduling said instruction for execution during a cycle corresponding to said stored cycle identification.
Claim 13
Dependent Claim
79 words
The method of claim 9 wherein said scheduling means further comprises: comparing means for comparing a stored cycle identification in a scheduling map position corresponding to a register containing a first operand of said instruction with a stored cycle identification in a scheduling map position corresponding to a register containing a second operand of said instruction; and said scheduling means further comprising means for scheduling said instruction for execution during a cycle corresponding to a largest stored cycle identification.
Claim 14
Dependent Claim
90 words
The apparatus of claim 11 wherein said instruction comprises a first instruction, and: said scheduling means further comprises means for scheduling a second instruction for execution during an earliest available cycle in which an operand of said second instruction is predicted to become available; and said memory means further comprises means for storing a cycle identification for an earliest cycle in which a result of said second instruction is predicted to be available in a scheduling map position associated with a target register for said result of said second instruction.
Claim 15
Dependent Claim
58 words
The apparatus of claim 12 wherein said scheduling means further comprises: examination means for examining a stored cycle identification in a scheduling map position corresponding to a register containing an operand of said second instruction; and said scheduling means further comprising means for scheduling said second instruction for execution during a cycle corresponding to said stored cycle identification.
Claim 16
Dependent Claim
40 words
The apparatus of claim 9 wherein said scheduling means further comprises: means for determining an earliest available cycle for an execution unit required to execute said instruction; and means for scheduling said instruction for execution during said earliest available cycle.
Claim 17
Dependent Claim
96 words
The apparatus of claim 9 wherein said memory means further comprises: adding means for adding a number of cycles required to execute said instruction to a cycle identification for said first available cycle during which said instruction is scheduled to execute; and means for storing a result of said addition of said number of cycles with said first available cycle identification as said cycle identification for said cycle in which said result of said instruction is predicted to be available in a scheduling map position associated with a target register for said result of said instruction.
Claim 18
Independent Claim
110 words
A method of efficiently scheduling instructions in a superscalar processor: reading a cycle identification within a scheduling map position corresponding to an operand register for an instruction; scheduling the instruction for execution during a cycle identified by the cycle identification; adding a latency of the instruction to a cycle identification for a cycle during which the instruction is schedule to execute to predict a cycle in which a result of the instruction will be available; and storing a cycle identification for the predicting cycle in which the result of the instruction will be available in a scheduling map position associated with a target register for the result of the instruction.
Claim 19
Independent Claim
110 words
A method of efficiently scheduling instructions in a superscalar processor: reading a cycle identification within a scheduling map position corresponding to an operand register for an instruction; scheduling the instruction for execution during a cycle identified by the cycle identification; adding a latency of the instruction to a cycle identification for a cycle during which the instruction is schedule to execute to predict a cycle in which a result of the instruction will be available; and storing a cycle identification for the predicting cycle in which the result of the instruction will be available in a scheduling map position associated with a target register for the result of the instruction.
Claim 20
Dependent Claim
74 words
The method of claim 16, further comprising: reading a cycle identification within a scheduling map position corresponding to a second operand register for the instruction; comparing the cycle identification within the scheduling map position corresponding to the operand register to the cycle identification within the scheduling map position corresponding to the second operand register to determine a larger cycle identification; scheduling the instruction for execution during a cycle identified by the larger cycle identification.
Claim 21
Dependent Claim
96 words
The method of claim 16, further comprising: comparing the cycle identification within the scheduling map position corresponding to the operand register to a cycle identification for a first available cycle for an execution unit for the instruction; responsive to determining that the cycle identification within the scheduling map position corresponding to the operand register is larger than the cycle identification for the first available cycle for the execution unit, scheduling the instruction for execution during a cycle identified by the cycle identification within the scheduling map position corresponding to the operand register to a cycle identification.
Claim 22
Dependent Claim
61 words
The method of claim 18, further comprising: responsive to determining that the cycle identification within the scheduling map position corresponding to the operand register is smaller than the cycle identification for the first available cycle for the execution unit, scheduling the instruction for execution during a cycle identified by the cycle identification for the first available cycle for the execution unit.
Claim 23
Dependent Claim
42 words
The method of claim 16, further comprising: responsive to determining that the scheduling map position corresponding to the operand register contains a null cycle identification, scheduling the instruction for execution during a first available cycle for the execution unit for the instruction.
References Cited (Backward Citations)
US5287466A
Cited
US5640588A
Cited
US5636353A
Cited
US5638526A
Cited
US5404470A
Cited
US5475824A
Cited
US5497499A
Cited
US5371684A
Cited
US5416913A
Cited
US5619668A
Cited
US5519891A
Cited
US5560028A
Cited
US5615385A
Cited
US5625789A
Cited
US5692170A
Cited
US5634026A
Cited
US5699537A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-31 | 2002-03-02 | 2002-09-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-31 | 2006-03-02 | 2006-09-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-31 | 2010-03-02 | 2010-09-01 | $7700.00 | Window Closed / Lapsed |