Patent US6334182B2 successfully refreshed from Google Patents.
US6334182B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scheduling operations using a dependency matrix
Assignee: Intel Corp
•
Filing: 1998-08-18
•
Granted: 2001-12-25
•
Expires: 2018-08-18
Abstract
Abstract A method and apparatus for scheduling operations using a dependency matrix. A child operation, such as a micro-operation, is received for scheduling. The child operation is dependent on the completion of a parent operation, such as when one of the child operation's sources is the parent operations's destination. An entry corresponding to the child operation is placed in a scheduling queue and the child operation is compared with other entries in the scheduling queue. The result of this comparison is stored in a dependency matrix. Each row in the dependency matrix corresponds to an entry in the scheduling queue, and each column corresponds to a dependency on an entry in the scheduling queue. Entries in the scheduling queue can then be scheduled based on the information in the dependency matrix, such as when the entire row associated with an entry is clear.
Inventors
- 👤 Amit A. Merchant
- 👤 David J. Sager
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 13:11
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3838
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
73 words
A method of scheduling an operation in a processor, comprising: receiving an operation to be scheduled; determining if the received operation is dependent on a parent operation; storing the results of said determination; scheduling the received operation based at least in part upon the results; using a ready determination unit for determining if the received operation is ready for dispatch; and scheduling dispatch of the received operation according to a priority logic unit.
Claim 2
Independent Claim
73 words
A method of scheduling an operation in a processor, comprising: receiving an operation to be scheduled; determining if the received operation is dependent on a parent operation; storing the results of said determination; scheduling the received operation based at least in part upon the results; using a ready determination unit for determining if the received operation is ready for dispatch; and scheduling dispatch of the received operation according to a priority logic unit.
Claim 3
Dependent Claim
35 words
The method of claim 1 , wherein said storing further comprises: storing the results of said determination in a dependency matrix; and wherein said scheduling is performed based on information stored in the dependency matrix.
Claim 4
Independent Claim
113 words
A method of scheduling an operation in a processor, comprising: receiving a first operation to be scheduled; placing an entry corresponding to the first operation in a scheduling queue; comparing the first operation with other entries in the scheduling queue to determine if another entry corresponds to a parent operation of the first operation; storing the result of said comparison in a dependency matrix; scheduling the entry in the scheduling queue based at least in part upon on the information stored in the dependency matrix; using a ready determination unit for determining if the scheduled entry is ready for dispatch; and scheduling dispatch of the scheduled entry according to a priority logic unit.
Claim 5
Independent Claim
113 words
A method of scheduling an operation in a processor, comprising: receiving a first operation to be scheduled; placing an entry corresponding to the first operation in a scheduling queue; comparing the first operation with other entries in the scheduling queue to determine if another entry corresponds to a parent operation of the first operation; storing the result of said comparison in a dependency matrix; scheduling the entry in the scheduling queue based at least in part upon on the information stored in the dependency matrix; using a ready determination unit for determining if the scheduled entry is ready for dispatch; and scheduling dispatch of the scheduled entry according to a priority logic unit.
Claim 6
Dependent Claim
41 words
The method of claim 3 , wherein the dependency matrix has rows and columns, each row corresponding to an entry in the scheduling queue and each element in each column corresponding to a dependency on an entry in the scheduling queue.
Claim 7
Dependent Claim
31 words
The method of claim 4 , wherein said storing comprises storing an indication of dependency in the row associated with the first operation and the column associated with the parent operation.
Claim 8
Dependent Claim
29 words
The method of claim 5 , wherein said scheduling comprises scheduling an entry in the scheduling queue if the row associated with the entry contains no element indicating dependency.
Claim 9
Dependent Claim
40 words
The method of claim 3 , further comprising: removing a dispatched entry from the scheduling queue when the operation associated with the dispatched entry has been performed; and clearing the column in the dependency matrix associated with the dispatched operation.
Claim 10
Dependent Claim
11 words
The method of claim 3 , wherein the operations are micro-operations.
Claim 11
Dependent Claim
25 words
The method of claim 3 , further comprising: prioritizing ready entries in the scheduling queue when more than one entry is ready to be scheduled.
Claim 12
Independent Claim
124 words
A method of scheduling a micro-operation in a processor, the newly issued micro-operation having a source and a destination, comprising: allocating the micro-operation to an entry in a scheduling queue; comparing the source of the allocated micro-operation with destinations of pending microoperations in the scheduling queue; setting up a dependency matrix row associated with the entry ofthe allocated micro-operation based on the results of said comparison, each column in the dependency matrix being associated with an entry in the scheduling queue; and using a ready determination unit for determining if the allocated micro-operation is ready for dispatch based on the information in the dependency matrix row associated with that entry; and scheduling a dispatch order forthe allocated micro-operation according to a priority logic unit.
Claim 13
Independent Claim
124 words
A method of scheduling a micro-operation in a processor, the newly issued micro-operation having a source and a destination, comprising: allocating the micro-operation to an entry in a scheduling queue; comparing the source of the allocated micro-operation with destinations of pending microoperations in the scheduling queue; setting up a dependency matrix row associated with the entry ofthe allocated micro-operation based on the results of said comparison, each column in the dependency matrix being associated with an entry in the scheduling queue; and using a ready determination unit for determining if the allocated micro-operation is ready for dispatch based on the information in the dependency matrix row associated with that entry; and scheduling a dispatch order forthe allocated micro-operation according to a priority logic unit.
Claim 14
Dependent Claim
58 words
The method of claim 10 , further comprising: dispatching the allocated micro-operation for execution if said determination determines that the allocated micro-operation is ready for dispatch; clearing the column in the dependency matrix associated with the dispatched operation when the dispatched operation has been performed; and deallocating the entry in the scheduling queue associated with the dispatched operation.
Claim 15
Dependent Claim
22 words
The method of claim 10 , wherein said determining and dispatching are repeated when any operation is removed from the scheduling queue.
Claim 16
Dependent Claim
92 words
An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, cause the processor to schedule an operation by: receiving an operation to be scheduled; determining that the received operation is dependent on the completion of a parent operation; scheduling the received operation based at least in part upon said determining; using a ready determination unit for determining if the received operation is ready for dispatch; and scheduling dispatch of the received operation according to a priority logic unit.
Claim 17
Dependent Claim
92 words
An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, cause the processor to schedule an operation by: receiving an operation to be scheduled; determining that the received operation is dependent on the completion of a parent operation; scheduling the received operation based at least in part upon said determining; using a ready determination unit for determining if the received operation is ready for dispatch; and scheduling dispatch of the received operation according to a priority logic unit.
Claim 18
Dependent Claim
34 words
The article of claim 13 , wherein determining further comprises: storing the results of said determination in a dependency matrix; and wherein said scheduling is performed based on information stored in the dependency matrix.
Claim 19
Dependent Claim
130 words
An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, cause the processor to schedule an operation by: receiving a first operation to be scheduled; placing an entry corresponding to the first operation in a scheduling queue; comparing the first operation with other entries in the scheduling queue to determine if another entry corresponds to a parent operation of the first operation; storing the result of said comparison in a dependency matrix; scheduling an entry in the scheduling queue based on the information stored in the dependency matrix; using a ready determination unit for determining if the scheduled entry is ready for dispatch; and scheduling dispatch of the scheduled entry according to a priority logic unit.
Claim 20
Dependent Claim
130 words
An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, cause the processor to schedule an operation by: receiving a first operation to be scheduled; placing an entry corresponding to the first operation in a scheduling queue; comparing the first operation with other entries in the scheduling queue to determine if another entry corresponds to a parent operation of the first operation; storing the result of said comparison in a dependency matrix; scheduling an entry in the scheduling queue based on the information stored in the dependency matrix; using a ready determination unit for determining if the scheduled entry is ready for dispatch; and scheduling dispatch of the scheduled entry according to a priority logic unit.
References Cited (Backward Citations)
US5655096A
Cited
US5546597A
Cited
US6216200B1
Cited
US5710902A
Cited
US5737758A
Cited
US5737759A
Cited
US5884059A
Cited
US5796975A
Cited
US5913925A
Cited
US6016540A
Cited
US5923862A
Cited
US5850533A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-24 | 2005-06-25 | 2005-12-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-24 | 2009-06-25 | 2009-12-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-24 | 2013-06-25 | 2013-12-25 | $7700.00 | Window Closed / Lapsed |