Superscalar RISC instruction scheduling

• US 6,289,433 B1
• Filed: 06/10/1999
• Issued: 09/11/2001
• Est. Priority Date: 03/31/1992
• Status: Expired due to Fees

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Transmeta Corporation (Novafora, Inc.)
• Inventors: Iadonato, Kevin Ray, Wang, Johannes, Nguyen, Le Trong, Garg, Sanjiv
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US09/329,354
• Time in Patent Office: 824 Days
• Field of Search: 712/23, 712/24, 712/216, 712/217, 712/218, 712/215
• US Class Current: 712/23
• CPC Class Codes: G06F 9/3013 according to data content, e.g. floating-point registers, address registers
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags

Abstract

A register renaming system for out-of-order execution of a set of reduced instruction set computer instructions having addressable source and destination register fields, adapted for use in a computer having an instruction execution unit with a register file accessed by read address ports and for storing instruction operands. A data dependence check circuit is included for determining data dependencies between the instructions. A tag assignment circuit generates one of more tags to specify the location of operands, based on the data dependencies determined by the data dependence check circuit. A set of register file port multiplexers select the tags generated by the tag assignment circuit and pass the tags onto the read address ports of the register file for storing execution results.

Claims

1. A system for register renaming in a computer system capable of out-of-order instruction execution, comprising:

a temporary buffer comprising a plurality of storage locations for storing execution results, wherein an execution result for an instruction in an instruction window is stored at one of said plurality of storage locations, said one of said plurality of storage locations being assigned to said instruction in said instruction window; and

tag assignment logic for receiving data dependency results from a data dependency checker and for outputting a tag comprising a temporary buffer storage location address in place of a register address for an operand of a first instruction, wherein said temporary buffer storage location address is an address of said operand in one of said plurality of storage locations if said first instruction is dependent on a previous one of said plurality of instructions in said instruction window for said operand.

2. The register renaming system of claim 1, further comprising termination logic that transfers the execution results in said plurality of storage locations in said temporary buffer to register file locations in-order based on the order of instructions in said instruction window.

3. The register renaming system of claim 2, wherein said termination logic transfers a plurality of execution results from said temporary buffer to said register file simultaneously.

4. The register renaming system of claim 3, wherein said termination logic transfers an execution result for an instruction from said temporary buffer to said register file when all execution results for all prior instructions are retirable.

5. The register renaming system of claim 1, wherein said tag further comprises a 1-bit identifier that indicates whether said address within said tag is an address within a register file or within said plurality of storage locations.

6. The register renaming system of claim 1, further comprising register file port MUXes that pass said tags to read address ports of said temporary buffer for accessing said instruction execution results.

7. A computer system, comprising:

a memory unit for storing program instructions;

a bus coupled to said memory unit for retrieving said program instructions; and

a processor coupled to said bus, wherein said processor comprises a register renaming system, comprising;

a temporary buffer comprising a plurality of storage locations for storing execution results, wherein an execution result for an instruction in an instruction window is stored at one of said plurality of storage locations, said one of said plurality of storage locations being assigned to said instruction in said instruction window; and

tag assignment logic that receives data dependency results from a data dependency checker and outputs a temporary buffer storage location address in place of a register address for an operand of a first instruction if said first instruction is dependent on a previous one of said plurality of instructions in said instruction window for said operand, wherein said temporary buffer storage location address is an address of said operand in one of said plurality of storage locations.

8. The computer system of claim 7, wherein said processor further comprises termination logic that transfers the execution results in said plurality of storage locations in said temporary buffer to register file locations in-order based on the order of instructions in said instruction window.

9. The computer system of claim 8, wherein said termination logic transfers a plurality of execution results from said temporary buffer to said register file simultaneously.

10. The computer system of claim 9, wherein said termination logic transfers an execution result for an instruction from said temporary buffer to said register file when all execution results for all prior instructions are retirable.

11. The computer system of claim 7, wherein said tag comprises an address and a 1-bit identifier that indicates whether said address within said tag is an address within a register file or said plurality of storage locations.

12. The computer system of claim 7, wherein said processor further comprises register file port MUXes that pass said tag to read address ports of said temporary buffer for accessing said execution results.

13. A register renaming method, comprising the steps of:

(1) storing, in a temporary buffer, out-of-order execution results in storage locations assigned to instructions in an instruction window;

(2) generating at least one tag to specify an address in said temporary buffer at which said out-of-order execution results are temporarily stored; and

(3) outputting one of said at least one tag comprising an address in place of a register address for an operand of a first instruction if a data dependency result indicates that said first instruction is dependent on a previous instruction in said instruction window, wherein said tag comprises an address of said operand in said temporary buffer.

14. The register renaming method of claim 13, further comprising the step of transferring said out-of-order execution results in said temporary buffer to a register file in-order based on the order of instructions in said instruction window.

15. The register renaming method of claim 14, further comprising the step of transferring a plurality of execution results from said temporary buffer to said register file simultaneously.

16. The register renaming method of claim 15, further comprising the step of transferring an out-of-order execution result from said temporary buffer to said register file when all execution results for all prior instructions are retirable.

17. The register renaming method of claim 13, further comprising the step of determining data dependencies between the instructions in said instruction window to produce said data dependency results.

18. The register renaming method of claim 13, wherein said step (2) further comprises the step of generating tags that comprise an address and a 1-bit identifier that indicates whether said address within said tags is an address within a register file or said temporary buffer.

19. The register renaming method of claim 13, further comprising the step of passing said tags to read address ports of said temporary buffer for accessing said out-of-order execution results.