Patent US5655096A successfully refreshed from Google Patents.
US5655096A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dynamic scheduling of instructions to ensure sequentially coherent data in a processor employing out-of-order execution
Assignee: Individual
•
Filing: 1993-08-25
•
Granted: 1997-08-05
•
Expires: 2013-08-25
Abstract
Abstract A computer processor employing parallelism through pipelining and/or multiple functional units improved by Sequential Coherency Instruction Scheduling and/or Sequential Coherency Exception Handling. Sequential Coherency Instruction Scheduling establishes dependencies based on the sequential order of instructions, to execute those instructions in an order that may differ from that sequential order. Instructions are permitted to execute when all needed source operands will be available by the time required by the instruction and when all logically previous reads and writes of the destination will be accomplished before the time that the instruction will overwrite the destination. Sequential Coherency Exception Handling does not use checkpointing or in-order commit. Instead it permits out-of-order execution to actually update the permanent state of the machine out-of-order. It maintains and saves, when an exception is recognized, sequential flow information and completion information about the program execution. To resume the exception causing program after the exception is handled, the saved state is used to re-establish the program flow that was determined prior to the exception and to re-establish which instructions in that flow should not be executed, because they were completed before the exception occurred.
Inventors
- 👤 Michael H. Branigin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 16:49
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3838; G06F9/3854; G06F9/3856; G06F9/3858; G06F9/3861; G06F9/3863
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
321 words
A method of executing a program in a processor; said program comprising instructions in sequential program order with each of said instructions logically previous to all subsequent instructions; the instructions comprising source operand specifiers and destination operand specifiers; said source operand specifiers specifying source locations for reading source operands; and said destination operand specifiers specifying destination locations for writing results of the instruction; said processor including at least one execution unit for instruction execution; said method comprising the steps of: obtaining the instructions in said sequential program order; for each of the instructions dynamically, at run-time, determining an execution-point defining when said instruction execution is to begin, such that: all logically previous writes to said source locations will be accomplished before the instruction execution reads said source locations; all logically previous reads of said destination locations will be accomplished before the instruction execution causes said destination locations to be overwritten; and all logically previous writes to the destination locations will be accomplished before the instruction execution causes the destination locations to be overwritten; and beginning use of said execution unit by the instruction only when said execution-point has been reached; whereby the processor, when appropriate, executes the instructions in an order that differs from the sequential program order; program execution results are identical to said program execution results obtained by executing the instructions, one at a time, in the sequential program order; each of the instructions is executed as early as possible with foreknowledge of when all logically previous writes of the source locations and all logically previous reads and writes of the destination locations will be completed, instead of waiting until after said logically previous reads and writes have been completed before beginning execution; and the execution unit is utilized by the instruction only during the instruction's active execution, thus maximizing the execution unit availabilty for other instructions, rather than monopolizing the execution unit while waiting for execution to begin.
Claim 2
Independent Claim
321 words
A method of executing a program in a processor; said program comprising instructions in sequential program order with each of said instructions logically previous to all subsequent instructions; the instructions comprising source operand specifiers and destination operand specifiers; said source operand specifiers specifying source locations for reading source operands; and said destination operand specifiers specifying destination locations for writing results of the instruction; said processor including at least one execution unit for instruction execution; said method comprising the steps of: obtaining the instructions in said sequential program order; for each of the instructions dynamically, at run-time, determining an execution-point defining when said instruction execution is to begin, such that: all logically previous writes to said source locations will be accomplished before the instruction execution reads said source locations; all logically previous reads of said destination locations will be accomplished before the instruction execution causes said destination locations to be overwritten; and all logically previous writes to the destination locations will be accomplished before the instruction execution causes the destination locations to be overwritten; and beginning use of said execution unit by the instruction only when said execution-point has been reached; whereby the processor, when appropriate, executes the instructions in an order that differs from the sequential program order; program execution results are identical to said program execution results obtained by executing the instructions, one at a time, in the sequential program order; each of the instructions is executed as early as possible with foreknowledge of when all logically previous writes of the source locations and all logically previous reads and writes of the destination locations will be completed, instead of waiting until after said logically previous reads and writes have been completed before beginning execution; and the execution unit is utilized by the instruction only during the instruction's active execution, thus maximizing the execution unit availabilty for other instructions, rather than monopolizing the execution unit while waiting for execution to begin.
Claim 3
Dependent Claim
315 words
A processor for executing a program; said program comprising instructions in sequential program order with each of said instructions logically previous to all subsequent instructions; the instructions comprising source operand specifiers and destination operand specifiers; said source operand specifiers specifying source locations for reading source operands; and said destination operand specifiers specifying destination locations for writing results of the instruction; said processor including at least one execution unit for instruction execution; the processor further: obtaining the instructions in said sequential program order; for each of the instructions dynamically, at run-time, determining an execution-point defining when said instruction execution is to begin, such that: all logically previous writes to said source locations will be accomplished before the instruction execution reads said source locations; all logically previous reads of said destination locations will be accomplished before the instruction execution causes said destination locations to be overwritten; and all logically previous writes to the destination locations will be accomplished before the instruction execution causes the destination locations to be overwritten; and beginning use of said execution unit by the instruction only when said execution-point has been reached; whereby the processor, when appropriate, executes the instructions in an order that differs from the sequential program order; program execution results are identical to said program execution results obtained by executing the instructions, one at a time, in the sequential program order; each of the instructions is executed as early as possible with foreknowledge of when all logically previous writes of the source locations and all logically previous reads and writes of the destination locations will be completed, instead of waiting until after said logically previous reads and writes have been completed before beginning execution; and the execution unit is utilized by the instruction only during the instruction's active execution, thus maximizing the execution unit availabilty for other instructions, rather than monopolizing the execution unit while waiting for execution to begin.
Claim 4
Dependent Claim
315 words
A processor for executing a program; said program comprising instructions in sequential program order with each of said instructions logically previous to all subsequent instructions; the instructions comprising source operand specifiers and destination operand specifiers; said source operand specifiers specifying source locations for reading source operands; and said destination operand specifiers specifying destination locations for writing results of the instruction; said processor including at least one execution unit for instruction execution; the processor further: obtaining the instructions in said sequential program order; for each of the instructions dynamically, at run-time, determining an execution-point defining when said instruction execution is to begin, such that: all logically previous writes to said source locations will be accomplished before the instruction execution reads said source locations; all logically previous reads of said destination locations will be accomplished before the instruction execution causes said destination locations to be overwritten; and all logically previous writes to the destination locations will be accomplished before the instruction execution causes the destination locations to be overwritten; and beginning use of said execution unit by the instruction only when said execution-point has been reached; whereby the processor, when appropriate, executes the instructions in an order that differs from the sequential program order; program execution results are identical to said program execution results obtained by executing the instructions, one at a time, in the sequential program order; each of the instructions is executed as early as possible with foreknowledge of when all logically previous writes of the source locations and all logically previous reads and writes of the destination locations will be completed, instead of waiting until after said logically previous reads and writes have been completed before beginning execution; and the execution unit is utilized by the instruction only during the instruction's active execution, thus maximizing the execution unit availabilty for other instructions, rather than monopolizing the execution unit while waiting for execution to begin.
References Cited (Backward Citations)
US3346851A
Cited
US3462744A
Cited
US4399507A
Cited
US4468736A
Cited
US4553203A
Cited
US4594660A
Cited
US4498136A
Cited
US4847755A
Cited
US4858105A
Cited
US4903196A
Cited
US4773041A
Cited
US4891753A
Cited
US5063497A
Cited
US5050008A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-04 | 2001-02-03 | 2001-08-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-04 | 2005-02-03 | 2005-08-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-04 | 2009-02-03 | 2009-08-05 | $7700.00 | Window Closed / Lapsed |