US6016540A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for scheduling instructions in waves
Assignee: Intel Corp
•
Filing: 1997-01-08
•
Granted: 2000-01-18
•
Expires: 2017-01-08
Abstract
Abstract In a microprocessor, an Instruction scheduler 30 includes a dependency matrix 36 and a waiting buffer 34. A dependency determination unit 32 receives instructions to be executed, forwards the instructions to the waiting buffer 34, determines if any dependency exists between the instructions, and forwards the dependency information to the dependency matrix 36 in the form of a dependency vector 40. Dependency matrix 36 periodically determines whether any of the instructions contained in the waiting buffer 34 are ready to be executed, that is, no dependencies exist for that instruction. All identified instructions are then assigned to a current wave to be dispatched. The identified instructions are then dispatched for execution as execution resources become available. As each instruction is dispatched for execution in the waiting buffer 34, the dependency vector 40 for all dependent instructions is cleared for subsequent execution. However, until all instructions in the current wave are dispatched, no instructions in a subsequent wave may be dispatched. In this manner, an out-of-order processing scheme is implemented that efficiently accounts for data dependency between processed instructions.
Inventors
- 👤 Nazar Zaidi
- 👤 Gary Hammond
- 👤 Ken Shoemaker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 13:05
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3838; G06F9/384
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
121 words
A method for scheduling instructions for dispatch to an execution unit, said method comprising the steps of: a) receiving a plurality of instructions; b) generating a dependency vector for each instruction, wherein the dependency vector has a bit set that indicates each instruction on which the instruction is dependent; c) determining the instructions that are ready for execution by identifying each instruction that has no bits set in its corresponding dependency vector; d) clearing the bits in each of the dependency vectors that correspond to the instructions ready for execution; e) periodically dispatching at least some of the instructions ready for execution until all instructions identified in step c) have been dispatched; and f) repeating at least steps c) through e).
Claim 2
Independent Claim
121 words
A method for scheduling instructions for dispatch to an execution unit, said method comprising the steps of: a) receiving a plurality of instructions; b) generating a dependency vector for each instruction, wherein the dependency vector has a bit set that indicates each instruction on which the instruction is dependent; c) determining the instructions that are ready for execution by identifying each instruction that has no bits set in its corresponding dependency vector; d) clearing the bits in each of the dependency vectors that correspond to the instructions ready for execution; e) periodically dispatching at least some of the instructions ready for execution until all instructions identified in step c) have been dispatched; and f) repeating at least steps c) through e).
Claim 3
Dependent Claim
65 words
The method, as set forth in claim 1, wherein the step of periodically dispatching includes: g) dispatching at least a portion of the instructions ready for execution; h) comparing the instructions dispatched with the instructions ready for execution; i) proceeding to step f in the event that a match is detected; and j) proceeding to step g in the event that no match is detected.
Claim 4
Dependent Claim
46 words
A method, as set forth in claim 1, wherein the step of clearing the bits includes delaying the clearing of the bits by a preselected period of time corresponding to a length of time estimated for execution of the instruction determined to be ready for execution.
Claim 5
Dependent Claim
57 words
A method, as set forth in claim 3, wherein the step of delaying the clearing of the bits includes the steps of: loading a shift register with a value corresponding to the preselected period of time; and periodically clocking said shift registers so that said shift register delivers a clear signal after said preselected period of time.
Claim 6
Independent Claim
231 words
An apparatus for scheduling instructions for dispatch to an execution unit, comprising: a waiting buffer adapted to receive a plurality of instructions; a dependency matrix adapted to receive a plurality of dependency vectors associated with the instructions received in said waiting buffer, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent; a zero detect circuit coupled to said dependency matrix and adapted to deliver a wave vector indicative of an absence of bits being set in each dependency vector, said wave vector being delivered to a clear input of said dependency matrix to clear the bits set in each of said dependency vectors indicating a dependency on the instructions identified in the wave vector; port assignment logic coupled to said zero detect circuit and adapted to receive said wave vector, determine the instructions identified in said wave vector that are currently executable, and provide a dispatch wave vector indicative of the instructions that are currently executable; and an incomplete wave detector coupled to said port assignment logic and adapted to compare said wave vector and said dispatch wave vector, controllably deliver the output of the zero detect circuit as the next wave vector in response to detecting a match, and deliver an incomplete wave vector as the next wave vector in response to the wave vector and dispatch wave vector not matching.
Claim 7
Independent Claim
231 words
An apparatus for scheduling instructions for dispatch to an execution unit, comprising: a waiting buffer adapted to receive a plurality of instructions; a dependency matrix adapted to receive a plurality of dependency vectors associated with the instructions received in said waiting buffer, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent; a zero detect circuit coupled to said dependency matrix and adapted to deliver a wave vector indicative of an absence of bits being set in each dependency vector, said wave vector being delivered to a clear input of said dependency matrix to clear the bits set in each of said dependency vectors indicating a dependency on the instructions identified in the wave vector; port assignment logic coupled to said zero detect circuit and adapted to receive said wave vector, determine the instructions identified in said wave vector that are currently executable, and provide a dispatch wave vector indicative of the instructions that are currently executable; and an incomplete wave detector coupled to said port assignment logic and adapted to compare said wave vector and said dispatch wave vector, controllably deliver the output of the zero detect circuit as the next wave vector in response to detecting a match, and deliver an incomplete wave vector as the next wave vector in response to the wave vector and dispatch wave vector not matching.
Claim 8
Dependent Claim
81 words
An apparatus, as set forth in claim 5, including a multiplexer having a first input connected to receive said wave vector, a second input connected to receive said incomplete wave vector, and a select input connected to receive a control signal from said incomplete wave detector, said incomplete wave detector delivering a control signal having a first value in response to a match being detected and delivering a control signal having a second value in response to no match being detected.
Claim 9
Dependent Claim
38 words
An apparatus, as set forth in claim 5, wherein said incomplete wave detector generates an incomplete wave vector that has bits set corresponding to the instructions identified in the wave vector but not in the dispatch wave vector.
Claim 10
Dependent Claim
60 words
An apparatus, as set forth in claim 5, wherein said dependency matrix includes a latency counter coupled to the zero detect circuit and adapted to receive the clear signal and delay its delivery to the dependency vector by a period of time corresponding to a length of time estimated for execution of the instruction identified as being ready for execution.
Claim 11
Dependent Claim
72 words
An apparatus, as set forth in claim 8, wherein said latency counter includes a multi-bit shift register having its output coupled to a clear input of the dependency matrix, and an enable input coupled to the zero detect circuit, said latency counter adapted for being loaded with a value corresponding to the length of time estimated for execution of the first one of the instructions in response to receiving the clear signal.
Claim 12
Independent Claim
133 words
An apparatus for scheduling instructions for dispatch to an execution unit in waves, comprising: means for receiving a plurality of instructions; means for determining dependencies for received instructions by use of dependency vectors associated with the instructions, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent; means for generating a wave vector indicative of instructions ready for execution by identifying each instruction that has no bits set in its corresponding dependency vector; means for clearing the bits in each dependency vector that correspond to the instructions ready for execution; and means for scheduling and dispatching instructions in a series of waves in relation to the wave vector and not accepting a next wave of instructions until a previous group of instructions has been dispatched.
Claim 13
Independent Claim
133 words
An apparatus for scheduling instructions for dispatch to an execution unit in waves, comprising: means for receiving a plurality of instructions; means for determining dependencies for received instructions by use of dependency vectors associated with the instructions, wherein each dependency vector has a bit set that indicates each instruction on which the instruction is dependent; means for generating a wave vector indicative of instructions ready for execution by identifying each instruction that has no bits set in its corresponding dependency vector; means for clearing the bits in each dependency vector that correspond to the instructions ready for execution; and means for scheduling and dispatching instructions in a series of waves in relation to the wave vector and not accepting a next wave of instructions until a previous group of instructions has been dispatched.
Claim 14
Dependent Claim
36 words
The apparatus of claim 10, wherein the means for dispatching and scheduling said plurality of instructions is adapted to dispatch all of the instructions in one wave for execution before dispatching instructions in a subsequent wave.
Claim 15
Dependent Claim
25 words
The apparatus of claim 10, wherein the means for receiving a plurality of instructions includes a micro-op waiting buffer to store said plurality of instructions.
Claim 16
Dependent Claim
23 words
The apparatus of claim 10, wherein the means for determining dependencies includes a dependency matrix to store the dependency vector for each instruction.
Claim 17
Dependent Claim
33 words
The apparatus of claim 13, wherein the dependency matrix further includes a plurality of latency counters being associated with instructions received and to count down estimated delay times for the execution of instructions.
Claim 18
Independent Claim
155 words
An apparatus for scheduling instructions for dispatch, comprising: a buffer to store a plurality of instructions; a dependency matrix to store a plurality of dependency vectors, each dependency vector to indicate dependencies of one instruction in the buffer, a component of the dependency vector being set to a first logic value to indicate a dependency on an instruction corresponding to the component; a zero detect circuit to generate a wave vector of ready instructions in response to finding one or more dependency vectors without components set to the first logic value, the dependency matrix to clear a particular component of the stored dependency vectors in response to the instruction corresponding to the particular component being dispatched for execution, and a port assignment unit coupled to said zero detect circuit to receive said wave vector and to provide a dispatch wave vector comprising a portion of the instructions from the wave vector to dispatch for execution.
Claim 19
Independent Claim
155 words
An apparatus for scheduling instructions for dispatch, comprising: a buffer to store a plurality of instructions; a dependency matrix to store a plurality of dependency vectors, each dependency vector to indicate dependencies of one instruction in the buffer, a component of the dependency vector being set to a first logic value to indicate a dependency on an instruction corresponding to the component; a zero detect circuit to generate a wave vector of ready instructions in response to finding one or more dependency vectors without components set to the first logic value, the dependency matrix to clear a particular component of the stored dependency vectors in response to the instruction corresponding to the particular component being dispatched for execution, and a port assignment unit coupled to said zero detect circuit to receive said wave vector and to provide a dispatch wave vector comprising a portion of the instructions from the wave vector to dispatch for execution.
Claim 20
Dependent Claim
69 words
The apparatus of claim 15, wherein said dependency matrix further comprises a plurality of latency counters to countdown estimated times for executing corresponding instructions, the zero detect circuit to send signals that instructions are ready to corresponding latency counters, and the dependency matrix to delay clearing components of latency vectors corresponding to a particular instruction while a latency detector counts down the estimated time for the ready particular instruction.
Claim 21
Dependent Claim
77 words
The apparatus of claim 15, further comprising an incomplete wave detector to transmit a new wave vector from the zero detect circuit in response to determining that a present wave vector and a dispatched portion thereof match and to transmit an incomplete wave vector in response to a present wave vector and the dispatched portion thereof not matching, the incomplete wave vector including instructions belonging to the present wave vector and absent from the dispatched portion thereof.
Claim 22
Dependent Claim
33 words
The apparatus of claim 15, further comprising a dependency determination unit to generate a dependency vector in response to receiving an instruction and to send the generated dependency vector to the dependency matrix.
References Cited (Backward Citations)
US5479622A
Cited
US5560032A
Cited
US5345569A
Cited
US5560025A
Cited
US5546597A
Cited
US5555432A
Cited
US5822556A
Cited
US5812812A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-17 | 2003-07-19 | 2004-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-17 | 2007-07-19 | 2008-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-17 | 2011-07-19 | 2012-01-18 | $7700.00 | Window Closed / Lapsed |