Method for pipeline processing of instructions by controlling access to a reorder buffer using a register file outside the reorder buffer

• US 5,721,855 A
• Filed: 07/12/1996
• Issued: 02/24/1998
• Est. Priority Date: 03/01/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Glew, Andrew F., Fetterman, Michael A., Hinton, Glenn J., Colwell, Robert P., Papworth, David B.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/679,182
• Time in Patent Office: 592 Days
• Field of Search: 395/394, 395/393
• US Class Current: 712/218
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/30152 Determining start or end of instruction; determining instruction length
• CPC Class Codes: G06F 9/322 for non-sequential address
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3812 with instruction modification, e.g. store into instruction stream
• CPC Class Codes: G06F 9/3816 Instruction alignment, e.g. cache line crossing
• CPC Class Codes: G06F 9/3822 Parallel decoding, e.g. parallel decode units
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• 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/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques
• 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/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3877 using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3891 : organised in groups of units sharing resources, e.g. clusters
• CPC Class Codes: G09F 13/0472 : Traffic signs

Abstract

A pipelined method for executing instructions in a computer system. The present invention includes providing multiple instructions as a continuous stream of operations. This stream of operations is provided in program order. In one embodiment, the stream of operations is provided by performing an instruction cache memory lookup to fetch the multiple instructions, performing instruction length decoding on the instructions, rotating the instructions, and decoding the instructions. The present invention also performs register renaming, allocates resources and sends a portion of each of the operations to a buffering mechanism (e.g., a reservation station). The instruction cache memory lookup, instruction length decoding, rotation and decoding of the instructions, as well as the register renaming, are performed in consecutive pipestages.

The present invention provides for executing the instructions in an out-of-order pipeline. The execution produces results. In one embodiment, the instructions are executed by determining the data readiness of each of the operations and scheduling data ready operations. These scheduled data ready operations are dispatched to an execution unit and executed. The results are written back for use by other operations or as data output or indication. The determination of execution readiness, the dispatching and the execution, and writeback, are performed in consecutive pipestages.

The present invention also provides for retiring each of the continuous stream of operations in such a manner as to commit their results to architectural state and to reestablish sequential program order.

Claims

1. A pipelined method for executing a plurality of instructions in a computer system, said method comprising the steps of:

decoding the plurality of instructions in order in an in-order processing portion of a processor to produce a plurality of operations,

issuing the plurality of operations to an out-of-order execution core in the processor at the same time, wherein the step of issuing comprises writing the plurality of operations into a reservation station and simultaneously reading source data from a reorder buffer, separate from the reservation station, for use in execution of the plurality of operations only if indicated as ready in a register file maintained outside the reorder buffer in the first in-order portion of the processor;

executing the plurality of operations with at least one of said plurality of operations being executed out-of-order, wherein the step of executing includes the steps of

scheduling and dispatching individual operations as data required for execution is ready,

executing each of said individual operations, and

writing back results from execution,

wherein the step of writing back includes the steps of associatively writing data results directly into the reservation station for use by one or more individual operations in the reservation station during execution and writing data results into the reorder buffer;

and further wherein the steps of scheduling and dispatching, executing and writing back are performed in consecutive pipestages; and

committing results from execution of the plurality of operations to architectural state in order of issuance to the out-of-order execution core.

2. The method defined in claim 1 wherein the step of decoding further includes the steps of:

performing an instruction cache memory lookup to fetch the plurality of instructions,

performing instruction length decoding,

rotating the plurality of instructions, and

decoding the plurality of instructions in an instruction decoder to generate the plurality of operations,

performing register renaming, allocating resources and sending a portion of each of the plurality of operations to the reservation station,

wherein the steps of performing an instruction cache memory lookup, performing instruction length decoding, rotating the plurality of instructions, decoding the plurality of instructions, and performing register renaming are performed in consecutive pipestages to generate the plurality of instructions.

3. The method defined in claim 2 wherein the step of performing instruction length decoding includes marking the plurality of instructions to identify each of the plurality of instructions.

4. The method defined in claim 2 wherein the step of rotating is performed based on an instruction fetch pointer and a number of instructions consumed by the instruction decoder.

5. The method defined in claim 2 wherein the step of decoding the plurality of instructions is performed in two pipestages.

6. The method defined in claim 2 wherein the step of performing register renaming, allocating resources and sending each of the plurality of operations to the reservation station is performed in a single pipestage.

7. The method defined in claim 1 wherein the step of retiring is performed in two pipestages.

8. A pipelined method for executing a plurality of instructions in a computer system, said method comprising the steps of:

decoding the plurality of instructions in order to produce a plurality of operations, wherein the step of decoding includes the steps of

maintaining a readiness indication of source data for the plurality of operations in a storage area outside a reorder buffer in an in-order processing portion of a processor;

writing the plurality of operations into a reservation station in an out-of-order execution core of the processor at the same time and

reading data from the reorder buffer for use in execution of the plurality of operations, simultaneously to writing the plurality of operations into the reservation station, only if data is indicated as ready in the storage area;

executing the plurality of operations with at least one of the plurality of operations being executed out-of-order, wherein the step of executing includes the steps of

scheduling and dispatching individual operations as data required for execution of each of the individual operations is ready,

executing each of said individual operations, and

writing back results from execution including associatively writing at least one result to the reservation station,

wherein the steps of scheduling and dispatching, executing and writing back are performed in consecutive pipestages; and

committing results from execution of the plurality of operations to architectural state in order of issuance of the plurality of operations.

9. The method defined in claim 8 wherein the step of decoding further includes the steps of:

performing an instruction cache memory lookup to fetch the plurality of instructions,

performing instruction length decoding,

rotating the plurality of instructions, and

decoding the plurality of instructions in an instruction decoder to generate the plurality of operations,

performing register renaming, allocating resources and sending a portion of each of the plurality of operations to the reservation station,

wherein the steps of performing an instruction cache memory lookup, performing instruction length decoding, rotating the plurality of instructions, decoding the plurality of instructions, and performing register renaming are performed in consecutive pipestages to generate the plurality of instructions.

10. The method defined in claim 9 wherein the step of performing instruction length decoding includes marking the plurality of instructions to identify each of the plurality of instructions.

11. The method defined in claim 9 wherein the step of rotating is performed based on an instruction fetch pointer and a number of instructions consumed by the instruction decoder.

12. The method defined in claim 9 wherein the step of decoding the plurality of instructions is performed in two pipestages.

13. The method defined in claim 9 wherein the step of performing register renaming, allocating resources and sending each of the plurality of operations to the reservation station is performed in a single pipestage.

14. The method defined in claim 8 wherein the step of retiring is performed in two pipestages.

15. A method for executing a plurality of instructions in a computer system, said method comprising the steps of:

providing the plurality of instructions as a plurality of operations in an in-order pipeline, wherein the step of providing the plurality of instructions includes the steps of

performing an instruction cache memory lookup to fetch the plurality of instructions,

performing instruction length decoding,

rotating the plurality of instructions, and

decoding the plurality of instructions in an instruction decoder to generate the plurality of operations,

performing register renaming, allocating resources and maintaining a readiness indication of source data for the plurality of operations in a storage area outside a reorder buffer, issuing the plurality of operations including the steps sending a portion of each of the plurality of operations to a reservation station at the same time and reading source data from the reorder buffer if valid as indicated in the storage area,

wherein the steps of performing an instruction cache memory lookup, performing instruction length decoding, rotating the plurality of instructions, decoding the plurality of instructions, and performing register renaming are performed in consecutive pipestages;

executing the plurality of operations in an out-of-order pipeline to produce execution results, wherein the step of executing includes the steps of

determining execution readiness of each of the plurality of operations and scheduling individual operations in the plurality of operations that have source data available,

dispatching individual operations to an execution unit as data required for each said individual operation is ready,

executing said individual operations and writing back the results, including associatively writing at least one result to the reservation station,

wherein the steps of determining execution readiness, dispatching and executing are performed in consecutive pipestages; and

retiring each of the plurality of operations, wherein results from execution are committed to architectural state and order is reestablished.

16. The method defined in claim 15 wherein the step of performing instruction length decoding includes marking the plurality of instructions to identify each of the plurality of instructions.

17. The method defined in claim 15 wherein the step of rotating is performed based on an instruction fetch pointer and a number of instructions consumed by the instruction decoder.

18. The method defined in claim 15 wherein the step of decoding the plurality of instructions is performed in two pipestages.

19. The method defined in claim 15 wherein the step of performing register renaming, allocating resources and sending each of the plurality of operations to the reservation station is performed in a single pipestage.

20. The method defined in claim 15 wherein the step of executing operations determined to be data ready and writing back the results is performed in a single pipestage.

21. The method defined in claim 15 wherein the step of retiring is performed in two pipestages.

22. The method defined in claim 15 wherein the steps of performing an instruction cache memory lookup, performing instruction length decoding, rotating the plurality of instructions, decoding the plurality of instructions, and performing register renaming are performed in seven consecutive pipestages.

23. A pipeline method for executing a plurality of instructions in a computer system, said method comprising the steps of:

decoding the plurality of instructions in order into a plurality of micro-operations;

writing the plurality of operations into a reservation station at the same time;

reading source data, simultaneously to the step of writing the plurality of micro-operations into a reservation station, from a reorder buffer only if indicated as ready in a register file outside the reorder buffer;

executing the plurality of micro-operations with at least one of the plurality of micro-operations being executed out-of-order;

writing back results from execution of the plurality of operations including associatively writing at least one result to the reservation station;

committing results from execution of the plurality of operations to the out-of-order execution core.