UNIFIED HIGH-FREQUENCY OUT-OF-ORDER PICK QUEUE WITH SUPPORT FOR SPECULATIVE INSTRUCTIONS

• US 20100332804A1
• Filed: 06/29/2009
• Published: 12/30/2010
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Li, Xiang Shan, Smittle, Matthew B., Golla, Robert T., Luttrell, Mark A.
• Granted Patent: US 9,058,180 B2
• Time in Patent Office: Days
• US Class Current: 712/214
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• 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

Abstract

Systems and methods for efficient picking of instructions for out-of-order issue and execution in a processor. In one embodiment, a processor comprises a unified pick queue that is dynamically allocated. Each entry is configured to store age and dependency information relative to other decoded instructions. Also, each entry stores a picked field, which when asserted indicates the decoded instruction has already been picked for out-of-order issue and execution. When asserted, a trigger field indicates a result of a corresponding decoded instruction will be available a predetermined number of clock cycles afterward. A younger instruction dependent on a result of an older instruction is ready to be picked before the result of the older instruction is available. In this case, the older instruction has asserted picked and trigger fields.

Claims

1. A unified microprocessor pick queue comprising:

control circuitry; and

an array configured to dynamically allocate an entry of a plurality of entries for an instruction, wherein each entry of said entries includes a picked field and a trigger field, wherein the picked field indicates a corresponding instruction is eligible to be picked for issue, and the trigger field indicates a result of the instruction will be available in M clock cycles;

wherein for a first instruction dependent upon a second instruction whose results are not yet available, the circuitry is configured to determine the first instruction is eligible to be picked for issue responsive to detecting the second instruction has associated picked and trigger fields have a designated state.

2. The unified pick queue as recited in claim 1, wherein the circuitry is further configured to determine a trigger field corresponding to the second instruction will be asserted R clock cycles after being picked for issue, wherein R is a nonzero integer.

3. The unified pick queue as recited in claim 2, wherein the first instruction takes M clock cycles to produce results, said second instruction takes T clock cycles to produce results, and R=T−

M, wherein T and M are nonzero integers.

4. The unified pick queue as recited in claim 3, wherein the first instruction corresponds to a first type of instruction within a first class of instructions, and wherein the circuitry is configured to determine a third instruction of a second type within the first class of instructions is eligible to be picked for issue responsive to detecting N cycles have elapsed since picked and trigger fields of the second instruction have been asserted, wherein the third instruction is dependent upon the second instruction and N is a nonzero integer.

5. The unified pick queue as recited in claim 1, wherein the circuitry is further configured to:

determine a trigger field corresponding to the second instruction will be asserted R clock cycles after being picked for issue, wherein the second instruction corresponds to a second class of instructions; and

responsive to a determination that the first instruction corresponds to a first class of instructions different from the second class, disable the assertion of the trigger field of the second instruction for N clock cycles after the R clock cycles have elapsed, wherein N and R are nonzero integers.

6. The unified pick queue as recited in claim 5, wherein the second class of instructions corresponds to cryptographic operations.

7. The unified pick queue as recited in claim 1, wherein each entry of said entries further comprises age information, wherein for a given instruction the age information comprises a separate age bit for each other instruction in the array, wherein an asserted age bit indicates a corresponding other instruction is both older in program order than the given instruction and is assigned to a same hardware resource as the given instruction.

8. The unified pick queue as recited in claim 7, wherein the circuitry is further configured to set a picked bit for a particular instruction, in response to determining the particular instruction is eligible to be picked and no other instruction has an asserted age bit.

9. A method comprising:

dynamically allocating an entry of a plurality of entries for an instruction, wherein each entry of said entries includes a picked field and a trigger field, wherein the picked field indicates a corresponding instruction is eligible to be picked for issue, and the trigger field indicates a result of the instruction will be available in M clock cycles;

determining, for a first instruction dependent upon a second instruction whose results are not yet available, that the first instruction is eligible to be picked for issue responsive to detecting the second instruction has associated picked and trigger fields with a designated state.

10. The method as recited in claim 9, further comprising determining a trigger field corresponding to the second instruction will be asserted R clock cycles after being picked for issue, wherein R is a nonzero integer.

11. The method as recited in claim 10, wherein the first instruction takes M clock cycles to produce results, said second instruction takes T clock cycles to produce results, and R=T−

M, wherein T and M are nonzero integers.

12. The method as recited in claim 11, wherein the first instruction corresponds to a first type of instruction within a first class of instructions, and wherein the method further comprises determining a third instruction of a second type within the first class of instructions is eligible to be picked for issue responsive to detecting N cycles have elapsed since picked and trigger fields of the second instruction have been asserted, wherein the third instruction is dependent upon the second instruction and N is a nonzero integer.

13. The method as recited in claim 9, further comprising:

determining a trigger field corresponding to the second instruction will be asserted R clock cycles after being picked for issue, wherein the second instruction corresponds to a second class of instructions; and

responsive to determining the first instruction corresponds to a first class of instructions different from the second class, disabling the assertion of the trigger field of the second instruction for N clock cycles after the R clock cycles have elapsed, wherein N and R are nonzero integers.

14. The method as recited in claim 13, wherein the second class of instructions correspond to cryptographic operations.

15. The method as recited in claim 9, wherein each entry of said entries further comprises age information, wherein for a given instruction the age information comprises a separate age bit for each other instruction in the array, wherein an asserted age bit indicates a corresponding other instruction is both older in program order than the given instruction and is assigned to a same hardware resource as the given instruction.

16. The method as recited in claim 13, further comprising setting a picked bit for a particular instruction, in response to determining the particular instruction is eligible to be picked and no other instruction has an asserted age bit.

17. A computer readable storage medium storing program instructions operable to efficiently pick out-of-order computer program instructions, wherein the program instructions are executable to:

dynamically allocate an entry of a plurality of entries for an instruction, wherein each entry of said entries includes a picked field and a trigger field, wherein the picked field indicates a corresponding instruction is eligible to be picked for issue, and the trigger field indicates a result of the instruction will be available in M clock cycles;

determine, for a first instruction dependent upon a second instruction whose results are not yet available, that the first instruction is eligible to be picked for issue responsive to detecting the second instruction has associated picked and trigger fields with a designated state.

18. The storage medium as recited in claim 17, wherein the program instructions are further executable to determine a trigger field corresponding to the second instruction will be asserted R clock cycles after being picked for issue, wherein R is a nonzero integer.

19. The storage medium as recited in claim 18, wherein the first instruction takes M clock cycles to produce results, said second instruction takes T clock cycles to produce results, and R=T−

M, wherein T and M are nonzero integers.

20. The storage medium as recited in claim 19, wherein the first instruction corresponds to a first type of instruction within a first class of instructions, and wherein the program instructions are further executable to determine a third instruction of a second type within the first class of instructions is eligible to be picked for issue responsive to detecting N cycles have elapsed since picked and trigger fields of the second instruction have been asserted, wherein the third instruction is dependent upon the second instruction and N is a nonzero integer.