Method and apparatus for dynamic scheduling of instructions to ensure sequentially coherent data in a processor employing out-of-order execution

• US 5,655,096 A
• Filed: 08/25/1993
• Issued: 08/05/1997
• Est. Priority Date: 10/12/1990
• Status: Expired due to Term

• Current Assignee: Michael H Branigin
• Original Assignee: Michael H Branigin
• Inventors: Branigin, Michael H.
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US08/112,212
• Time in Patent Office: 1,441 Days
• Field of Search: 395/375, 395/800
• US Class Current: 712/200
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

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.

Claims

1. 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.

2. 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.