Circuit and method for scheduling instructions by predicting future availability of resources required for execution

• US 5,842,036 A
• Filed: 10/20/1997
• Issued: 11/24/1998
• Est. Priority Date: 08/19/1994
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Fetterman, Michael A., Hinton, Glenn J., Martell, Robert W., Papworth, David B., Schwartz, James L.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US08/954,444
• Time in Patent Office: 400 Days
• Field of Search: 395/392, 395/391, 395/393, 395/394, 395/382, 395/800.23, 395/800.24
• US Class Current: 712/23
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3875 Pipelining a single stage, e.g. superpipelining
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3889 controlled by multiple instructions, e.g. MIMD, decoupled access or execute
• CPC Class Codes: G06F 9/3891 organised in groups of units sharing resources, e.g. clusters

Abstract

An out-of-order execution processor comprising an execution unit, a storage unit and a scheduler is disclosed. The storage unit stores instructions awaiting availability of resources required for execution. The scheduler periodically determines whether resources required for executing each instruction are available, and if so, dispatches that instruction to the execution unit. The execution unit indicates future availability of hardware resources such as functional units and write back ports a number of clock cycles before actual availability of the hardware resources. The scheduler determines availability of resources required for execution of an instruction based on the indication of future availability of the hardware resources, and dispatched the instruction for execution. The out-of-order execution processor also includes means to determine future completion of execution of source instructions a number of clock cycles before actual completion of execution. The scheduler dispatches for execution a data-dependent instruction that requires an execution result of one of such source instructions for an operand. Once the execution result of the source instruction is available, a bypass multiplexor bypasses the execution result into the dispatched data-dependent instruction. The bypass multiplexor sends the data dependent instruction with fully assembled operands to the execution unit for execution.

Claims

1. A method of instruction execution in a processor, said method comprising the steps of:

generating an indication of availability of an execution result of a first instruction, completion of execution of said first instruction generating said execution result;

generating an n-cycle inhibit signal when completion of said first instruction will take more than n cycles;

determining whether said execution result provides an operand for a second instruction; and

dispatching said second instruction to an execution unit through a bypass multiplexor prior to completion of execution of said first instruction if said execution result provides said operand for said second instruction and said n-cycle inhibit signal is not asserted, said dispatching step being performed according to said indication of availability such that said execution result is generated before said second instruction is received at said execution unit.

2. The method of claim 1 further comprising the steps of:

completing execution of said first instruction to generate said execution result;

bypassing said execution result into said bypass multiplexor with said dispatched second instruction; and

executing said second instruction in said execution unit.

3. The method of claim 2 wherein said step of generating an indication of availability comprises sending a result tag of said first instruction, said result tag identifying a destination register for storing said execution result.

4. The method of claim 3 wherein said step of generating an indication of availability is performed by said execution unit executing said first instruction.

5. The method of claim 1 further comprising the step of buffering said second instruction before said step of generating an indication.

6. The method of claim 5 wherein said step of generating an indication of availability further comprises the steps of:

determining if said first instruction is ready for execution;

determining an execution time of said first instruction; and

indicating future completion of execution of said first instruction according to said execution time, said step of indicating future completion sending said indication.

7. The method of claim 6 further comprising the steps of:

completing execution of said first instruction to generate said execution result;

bypassing said execution result into said dispatched second instruction; and

executing said second instruction in said execution unit.