System and method for register renaming

• US 7,979,678 B2
• Filed: 05/26/2009
• Issued: 07/12/2011
• Est. Priority Date: 12/31/1992
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Iadonato, Kevin R., Deosaran, Trevor A., Garg, Sanjiv
• Primary Examiner(s): Treat; William M
• Application Number:
  US12/472,052
• Publication Number:
  US 20090235053A1
• Time in Patent Office: 777 Days
• Field of Search: 712/217
• US Class Current: 712/217
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• 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/3854 Instruction completion, e.g. retiring, committing or graduating

Abstract

A system and method for performing register renaming of source registers in a processor having a variable advance instruction window for storing a group of instructions to be executed by the processor, wherein a new instruction is added to the variable advance instruction window when a location becomes available. A tag is assigned to each instruction in the variable advance instruction window. The tag of each instruction to leave the window is assigned to the next new instruction to be added to it. The results of instructions executed by the processor are stored in a temp buffer according to their corresponding tags to avoid output and anti-dependencies. The temp buffer therefore permits the processor to execute instructions out of order and in parallel. Data dependency checks for input dependencies are performed only for each new instruction added to the variable advance instruction window and register renaming is performed to avoid input dependencies.

Claims

1. A method for improving instruction parallelism in a microprocessor, comprising:

fetching an instruction;

adding the fetched instruction into an instruction window;

assigning a tag to the fetched instruction, wherein the assigned tag includes bits uniquely identifying an address of a storage location in a temporary buffer where a result of the instruction in the instruction window is to be stored;

determining whether an original source register address of the fetched instruction depends upon a destination register address of a prior-fetched instruction previously stored in the instruction window;

if such dependency is determined, setting the original source register address of the fetched instruction to be a different tag, the different tag being associated with the prior-fetched instruction;

executing the fetched instruction to generate a result; and

storing the result of the fetched instruction at the storage location in the temporary buffer that corresponds to the assigned tag.

2. The method of claim 1, further comprising:

determining, a retirement unit, that the prior-fetched instruction is a retired prior-fetch instruction; and

restoring the source register address of the retired prior-fetch instruction to the original source register address.

3. The method of claim 1, further comprising, after the setting of the original source register address of the instruction to be the different tag, storing the address of the original source register in a rename register file.

4. The method of claim 3, wherein the address of the original source register is stored in the rename register file at an address indexed by the tag assigned to the fetched instruction.

5. The method of claim 3, wherein the rename register file has one read port and one write port.

6. The method of claim 1, wherein the instruction window has at least one other instruction, each other instruction having an associated tag, and wherein determining whether an original source register address of the fetched instruction depends upon a destination register address of a prior-fetched instruction previously stored in the instruction window comprises:

comparing the original source register address of the fetched instruction to each tag associated with each other instruction in the instruction window; and

setting a bit corresponding to a specific tag associated with a particular other instruction that matches the source register address.

7. The method of claim 1, further comprising:

fetching a plurality of instructions;

assigning a tag to each instruction, each tag including bits corresponding to an address of a different location in the temporary buffer where a result of the instruction to which the tag is assigned is to be stored;

performing the inserting, determining, and setting on each of the fetched plurality of instructions; and

storing a result of each instruction in the temporary buffer at the location corresponding to the tag assigned to the instruction.

8. The method of claim 7, wherein the inserting, determining, and setting are performed simultaneously.

9. The method of claim 1, further comprising storing the assigned tag in a tag FIFO.

10. The method of claim 9, further comprising:

retrieving the assigned tag from a head of the tag FIFO.

11. The method of claim 9, further comprising placing the assigned tag at the head of the tag FIFO when the fetched instruction retires.

12. The method of claim 1, wherein the result of the fetched instruction is used by another instruction prior to retirement of the fetched instruction.

13. The method of claim 11, further comprising determining whether the result to be used is in the temporary buffer or stored in a main register.

14. The method of claim 10, wherein the retrieving of the assigned tag is always from the head of the tag FIFO.

15. The method of claim 11, wherein the placing of the assigned tag is always at the head of the tag FIFO.

16. A register renaming apparatus in a microprocessor, comprising:

an instruction window to store instructions;

logic to assign one of a plurality of tags to each of the instructions as the instruction enters the instruction window, each of the plurality of tags uniquely identifying a register in a temporary buffer for storing a result of a corresponding one of the instructions in the instruction window;

a data dependency checker to determine whether an instruction entering the instruction window has an input dependency on another instruction in the instruction window; and

a register rename circuit to set an original source register address of an instruction having an input dependency to the tag assigned to the instruction causing the input dependency.

17. The register renaming apparatus of claim 16, further comprising a temporary buffer to store a result of a particular instruction in the instruction window at a storage location corresponding to the tag assigned to the particular instruction.

18. The register renaming apparatus of claim 17, further comprising:

monitoring logic to determine when the instruction causing the input dependency retires; and

logic to determine whether to obtain source input data from the temporary buffer or a main register.

19. The register renaming apparatus of claim 16, further comprising a rename register file to store the original source register address at an address indexed by the tag assigned to the instruction having the input dependency.

20. The register renaming apparatus of claim 19, wherein the rename register file has one read port and one write port.

21. The register renaming apparatus of claim 16, wherein the data dependency checker includes at least one comparator to compare the original source register address to each tag associated with each other instruction in the instruction window and detect whether a match exists.

22. The register renaming apparatus of claim 21, wherein the data dependency checker sets a bit corresponding to each tag for which a match is detected using the comparator.

23. The register renaming apparatus of claim 16, further comprising a tag FIFO to store the assigned tags.

24. The register renaming apparatus of claim 23, wherein a tag assigned to an instruction is retrieved from a head of the tag FIFO.

25. The register renaming apparatus of claim 23, wherein when the instruction retires its tag is placed at the head of the tag FIFO.

26. The register renaming apparatus of claim 18, wherein the result of the instruction is used by another instruction prior to retirement of the instruction whose result is being used.

27. The register renaming apparatus of claim 16, further comprising an inputs register file to hold source and destination register addresses for each instruction in the instruction window.

28. The register renaming apparatus of claim 24, wherein the tag assigned to the instruction is always retrieved from the head of the tag FIFO.

29. The register renaming apparatus of claim 25, wherein when the instruction retires its tag is always placed at the head of the tag FIFO.

30. A register renaming circuit for a microprocessor, comprising:

one or more comparators to compare a source register address of a new instruction in an instruction window with one or more destination register addresses of one or more old instructions in the instruction window; and

a selector to select a tag associated with a one of the old instructions whose destination register address matches the source register address of the new instruction, the tag uniquely identifying a register of a temp buffer for storing a result corresponding to the new instruction in the instruction window.

31. The register renaming circuit of claim 30, further comprising a result register file to store the selected tag at a location corresponding to a tag associated with the new instruction.

32. The register renaming circuit of claim 31, wherein the result register file has one read port and one write port.

33. The register renaming circuit of claim 30, further comprising the instruction window to store instructions including the new and old instructions, and wherein the one or more comparators and the selector are configured such that comparison and selection are performed when the new instruction enters the instruction window.

34. The register renaming circuit of claim 33, wherein the one or more comparators and the selector are configured to perform the comparison and selection only one time for each new instruction that enters the instruction window.