System and method for scheduling operations using speculative data operands

• US 7,937,569 B1
• Filed: 05/05/2004
• Issued: 05/03/2011
• Est. Priority Date: 05/05/2004
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: McMinn, Brian D., Sander, Benjamin T.
• Primary Examiner(s): FENNEMA, ROBERT E
• Application Number:
  US10/839,471
• Time in Patent Office: 2,554 Days
• Field of Search: 712/225
• US Class Current: 712/225
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• 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/3842 Speculative instruction execution
• 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/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A system and method for scheduling operations using speculative data operands. In one embodiment, a system may include a scheduler configured to store a speculative source tag and a non-speculative source tag for an operand of an operation and an execution core configured to execute operations issued by the scheduler and to output result tags identifying operands generated by executing the operations. The scheduler may be configured to determine whether the operation is ready to issue by comparing the speculative source tag, but not the non-speculative source tag, to the result tags output by the execution core unless an incorrect speculation has been detected. If an incorrect speculation has been detected, the scheduler may be configured to determine whether the operation is ready to issue by comparing the non-speculative source tag, but not the speculative source tag, to the result tags output by the execution core.

Claims

1. A system, comprising:

a scheduler configured to store a speculative source tag and a non-speculative source tag for an operand of an operation; and

an execution core configured to execute operations issued by the scheduler and to output result tags identifying operands generated by executing the operations;

wherein the scheduler comprises circuitry with a first input port and a second input port configured to receive the speculative source tag and the non-speculative source tag, respectively, and an output port coupled to a third input port of a comparator, the output port configured to convey an output value corresponding to either the first or the second input port at any given time, wherein a fourth input port of the comparator is configured to receive result tags output by the execution core, wherein the scheduler is configured to;

determine whether the operation is ready to issue by;

comparing the speculative source tag, but not the non-speculative source tag, to the result tags output by the execution core unless an incorrect speculation has been detected; and

comparing the non-speculative source tag, but not the speculative source tag, to the result tags output by the execution core if the incorrect speculation has been detected; and

wherein the scheduler is further configured to issue the operation to the execution core subsequent to determining the operation is ready to issue.

2. The system of claim 1, further comprising a memory file including an entry configured to store a first addressing pattern and a first tag, wherein the memory file is configured to compare the first addressing pattern included in the entry to a second addressing pattern of a load operation, wherein if the second addressing pattern matches the first addressing pattern stored in the entry, the memory file is configured to link a data value identified by the first tag to a speculative result tag of the load operation, wherein the speculative result tag corresponds to the speculative source tag.

3. The system of claim 1, further comprising a load store unit configured to indicate the detection of the incorrect speculation to the scheduler in response to detecting that a speculative result of a load operation was incorrectly linked to a data value operated on by a memory operation.

4. The system of claim 1, wherein the scheduler is further configured to detect the incorrect speculation if the execution core outputs a result tag matching the speculative source tag and if a result color associated with the result tag does not match the color associated with the speculative source tag.

5. The system of claim 4, further comprising a register map, wherein the register map is configured to associate a color with each of a plurality of physical registers, wherein in response to one of the plurality of physical registers being reassigned to a different logical register, the register map is configured to update the color associated with that one of the plurality of physical registers.

6. The system of claim 1, further comprising a speculative register map configured to speculatively map a given logical register to a given physical register, wherein the given physical register corresponds to the speculative source tag.

7. The system of claim 6, wherein the speculative register map is further configured to speculatively map the given logical register to the given physical register in response to detecting an indication that a link exists between a data value associated with the given physical register and a speculative result of a load operation corresponding to the given logical register.

8. The system of claim 1, further comprising an operation converter configured to convert a load operation into a register-to-register move operation in response to detecting an indication that a link exists between a data value associated with a given physical register and a speculative result tag of the load operation, wherein a source operand of the register-to-register move operation corresponds to the given physical register, a destination operand of the register-to-register move operation corresponds to the speculative result tag, and the given physical register corresponds to the speculative source tag.

9. The system of claim 8, wherein the operation converter is further configured to issue the load operation in addition to the register-to-register move operation, wherein the load operation and the register-to-register move operation each occupy an entry in the scheduler.

10. The system of claim 8, wherein the register-to-register move operation is a dual-nature operation configured to occupy a single entry in the scheduler and to perform a data move operation and an address calculation operation, wherein the address calculation operation corresponds to the load operation.

11. The system of claim 1, wherein the scheduler is further configured to store an indication of a color with the speculative source tag, wherein the color comprises one or more bits of information that indicate whether a register linked to a tag has been reassigned.

12. A method, comprising:

storing a speculative source tag and a non-speculative source tag for an operand of an operation;

generating output result tags identifying operands produced by executing operations;

providing circuitry with a first input port and a second input port configured to receive the speculative source tag and the non-speculative source tag, respectively, and an output port coupled to a third input port of a comparator, the output port configured to convey an output value corresponding to either the first or the second input port at any given time, wherein a fourth input port of the comparator is configured to receive result tags output by the execution core;

determining whether the operation is ready to issue by;

comparing the speculative source tag, but not the non-speculative source tag, to the result tags in response to generating the output result tags if no incorrect speculation has been detected; and

comparing the non-speculative source tag, but not the speculative source tag, to the result tags in response to generating the output result tags if an incorrect speculation has been detected; and

issuing the operation to the execution core subsequent to determining the operation is ready to issue.

13. The method of claim 12, further comprising:

storing an entry including a first addressing pattern and a first tag;

comparing the first addressing pattern included in the entry to a second addressing pattern of a load operation subsequent to storing the entry; and

if the second addressing pattern matches the first addressing pattern stored in the entry, linking a data value identified by the first tag to a speculative result tag of the load operation in response to comparing the first addressing pattern, wherein the speculative result tag corresponds to the speculative source tag.

14. The method of claim 12, further comprising indicating the detection of the incorrect speculation in response to detecting that a speculative result of a load operation was incorrectly linked to a data value operated on by a memory operation.

15. The method of claim 12, further comprising detecting the incorrect speculation in response to generating a result tag matching the speculative source tag if a result color associated with the result tag does not match the color associated with the speculative source tag.

16. The method of claim 15, further comprising:

associating a color with each of a plurality of physical registers; and

in response to one of the plurality of physical registers being reassigned to a different logical register, updating the color associated with that one of the plurality of physical registers.

17. The method of claim 12, further comprising speculatively mapping a given logical register to a given physical register, wherein the given physical register corresponds to the speculative source tag.

18. The method of claim 17, wherein the speculative mapping occurs in response to detecting an indication that a link exists between a data value associated with the given physical register and a speculative result of a load operation corresponding to the given logical register.

19. The method of claim 12, further comprising converting a load operation into a register-to-register move operation in response to detecting an indication that a link exists between a data value associated with a given physical register and a speculative result tag of the load operation, wherein a source operand of the register-to-register move operation corresponds to the given physical register, a destination operand of the register-to-register move operation corresponds to the speculative result tag, and the given physical register corresponds to the speculative source tag.

20. The method of claim 19, wherein converting the load operation further comprises issuing the load operation in addition to the register-to-register move operation, wherein the load operation and the register-to-register move operation each occupy an entry in a scheduler.

21. The method of claim 19, wherein the register-to-register move operation is a dual-nature operation configured to occupy a single entry in a scheduler and to perform a data move operation and an address calculation operation, wherein the address calculation operation corresponds to the load operation.

22. The method of claim 12, further comprising storing an indication of a color with the speculative source tag, wherein the color comprises one or more bits of information that indicate whether a register linked to a tag has been reassigned.