HIERARCHICAL INSTRUCTION SCHEDULER

• US 20080133889A1
• Filed: 10/31/2007
• Published: 06/05/2008
• Est. Priority Date: 08/29/2005
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Centaurus Data LLC (Intellectual Ventures LLC)
• Inventors: Glew, Andrew Forsyth
• Granted Patent: US 8,275,976 B2
• Time in Patent Office: Days
• US Class Current: 712/214
• CPC Class Codes: G06F 9/3012 Organisation of register space, e.g. banked or distributed register file
• CPC Class Codes: G06F 9/30138 Extension of register space, e.g. register cache
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• 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/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
• CPC Class Codes: G06F 9/3875 Pipelining a single stage, e.g. superpipelining
• 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

Abstract

A hierarchical instruction scheduler included in a hierarchical microprocessor comprising a plurality of execution clusters. In one embodiment, a hierarchical instruction scheduler comprises a first-level instruction scheduler configured to receive instructions for execution; store first operand status information for respective operands of the instructions; and dispatch the instructions to respective execution clusters based on the instructions'"'"' respective first operand status information. The instruction scheduler also includes a plurality of second-level instruction schedulers, each operatively coupled with the first-level instruction scheduler, each second-level instruction scheduler being included in a respective execution cluster The second-level instruction schedulers are each configured to receive instructions for execution from the first-level instruction scheduler; store second operand status information for respective operands of the instructions received from the first-level instruction scheduler; and dispatch instructions, for execution, to respective execution units of the execution clusters based on the instructions'"'"' respective second operand status information.

Claims

1. A hierarchical instruction scheduler included in a hierarchical microprocessor including a plurality of execution clusters, the hierarchical instruction scheduler comprising:

a first-level instruction scheduler configured to;

receive instructions for execution;

store first operand status information for respective operands of the instructions; and

dispatch the instructions to respective execution clusters based on the instructions'"'"' respective first operand status information; and

a plurality of second-level instruction schedulers each operatively coupled with the first-level instruction scheduler, each second-level instruction scheduler being included in a respective execution cluster, the second-level instruction schedulers each being configured to;

receive instructions for execution from the first-level instruction scheduler;

store second operand status information for respective operands of the instructions received from the first-level instruction scheduler; and

dispatch instructions, for execution, to respective execution units of the execution clusters based on the instructions'"'"' respective second operand status information.

2. The instruction scheduler of claim 1, wherein the first-level instruction scheduler includes:

a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer; and

a picker circuit configured to notify the first-level instruction scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available,

wherein the instructions are processed by the timing wheel circuit prior to being processed by the picker circuit.

3. The instruction scheduler of claim 1, wherein each second-level instruction scheduler includes:

a picker circuit configured to notify the associated second-level scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available; and

a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer,

wherein the instructions are processed by the picker circuit prior to being processed by the timing wheel circuit.

4. The hierarchical instruction scheduler of claim 1, wherein the second-level instruction schedulers are substantially operationally identical.

5. The hierarchical instruction scheduler of claim 1, wherein a first second-level instruction scheduler is substantially operationally different than a second second-level instruction scheduler.

6. The hierarchical instruction scheduler of claim 1, wherein the first-level instruction scheduler is configured to:

assign execution threads to respective execution clusters, including dispatching instructions associated with a common execution thread to a single execution cluster;

implement a load balancing policy; and

assign a spawned thread to an execution cluster different than an execution cluster executing an associated spawning thread.

7. The hierarchical instruction scheduler of claim 1, wherein the instructions are dispatched from the first-level instruction scheduler and the second level-instruction schedulers based on respective logic functions, wherein the respective logic functions are evaluated based on operand availability.

8. The hierarchical instruction scheduler of claim 1, wherein:

the first-level instruction scheduler is physically partitioned in a plurality of partitions; and

the plurality of partitions are dynamically allocated to respective execution clusters.

9. A method for processing instructions in a microprocessor, the method comprising:

receiving instructions for execution at a first-level instruction scheduler;

storing first operand status information for respective operands of the instructions;

dispatching, based on the first operand status information, the instructions to respective execution clusters of the microprocessor, wherein each of the respective execution clusters includes a corresponding second-level instruction scheduler, the second-level instruction schedulers being operatively coupled with the first-level instruction scheduler;

receiving, at the second-level instruction schedulers, the instructions from the first-level instruction scheduler;

storing second operand status information for respective operands of the instructions;

dispatching, based on the second operand status information, the instructions to respective execution units of the execution clusters; and

executing one of more of the instructions.

10. The method of claim 9, further comprising:

assigning an execution thread to a single execution cluster; and

dispatching instructions associated with the execution thread to the single execution cluster.

11. The method of claim 9, wherein dispatching the instructions from the first-level instruction scheduler includes dispatching the instructions in accordance with a load balancing policy.

12. The method of claim 9, further comprising assigning a spawned thread to an execution cluster different than an execution cluster executing an associated spawning thread.

13. A microprocessor comprising:

a plurality of execution clusters;

a plurality of first-level architectural elements for processing instructions in the microprocessor, the plurality of first-level architectural elements being configured to act as shared resources for the plurality of execution clusters, wherein the plurality of first-level architectural elements includes a first-level instruction scheduler configured to;

receive instructions for execution;

store first operand status information for respective operands of the instructions; and

dispatch the instructions to respective execution clusters of the plurality of execution clusters based on the first operand status information; and

a plurality of second-level instruction schedulers, each of the second level instruction schedulers being included in a respective execution cluster of the plurality of execution clusters, wherein each of the second-level instructions schedulers is configured to;

receive the instructions for execution from the first-level instruction scheduler;

store second operand status information for respective operands of the instructions received from the first-level instruction scheduler; and

dispatch the instructions, for execution, to respective execution units of the execution clusters based on the respective second operand status information.

14. The microprocessor of claim 13, wherein the first-level instruction scheduler includes a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer.

15. The microprocessor of claim 14, wherein the first-level instruction scheduler further includes a picker circuit configured to notify the first-level instruction scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available,

wherein the instructions are processed by the timing wheel circuit prior to being processed by the picker circuit.

16. The microprocessor of claim 13, wherein the first-level instruction scheduler includes a picker circuit configured to notify the first-level instruction scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available.

17. The microprocessor of claim 13, wherein each second-level instruction scheduler includes a picker circuit configured to notify the associated second-level scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available.

18. The microprocessor of claim 17, wherein each second-level instruction scheduler further includes a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer,

wherein the instructions are processed by the picker circuit prior to being processed by the timing wheel circuit.

19. The microprocessor of claim 13, wherein each second-level instruction scheduler includes a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer.

20. The microprocessor of claim 13, wherein the second-level instruction schedulers are substantially operationally identical.

21. The microprocessor of claim 13, wherein a first second-level instruction scheduler is substantially operationally different than a second second-level instruction scheduler.

22. The microprocessor of claim 13, wherein the first-level instruction scheduler is configured to perform at least one of:

assigning execution threads to respective execution clusters, including dispatching instructions associated with a common execution thread to a single execution cluster;

implementing load balancing in accordance with a load balancing policy; and

assigning a spawned thread to an execution cluster different than an execution cluster executing an associated spawning thread.

23. A hierarchical instruction scheduler included in a hierarchical microprocessor including a plurality of execution clusters, the hierarchical instruction scheduler comprising:

a first-level instruction scheduler configured to;

receive instructions for execution;

store first operand status information for respective operands of the instructions; and

dispatch the instructions to respective execution clusters based on the instructions'"'"' respective first operand status information; and

a plurality of second-level instruction schedulers each operatively coupled with the first-level instruction scheduler, each second-level instruction scheduler being included in a respective execution cluster, the second-level instruction schedulers each being configured to;

receive instructions for execution from the first-level instruction scheduler;

store second operand status information for respective operands of the instructions received from the first-level instruction scheduler; and

dispatch instructions, for execution, to respective execution units of the execution clusters based on the instructions'"'"' respective second operand status information, wherein the first-level instruction scheduler includes;

a timing wheel circuit configured to schedule the instructions based on respective predictions as to when one or more of the respective operands of the instructions will be available, the timing wheel circuit including a circular instruction buffer; and

a picker circuit configured to notify the first-level instruction scheduler when one or more operands of a respective instruction become available, the picker circuit including a comparison circuit configured to determine when the one or more operands become available.

24. The hierarchical instruction scheduler of claim 23, wherein the instructions are processed by the timing wheel circuit prior to being processed by the picker circuit.

25. A method for processing instructions in a microprocessor, the method comprising:

receiving instructions for execution at a first-level instruction scheduler;

storing first operand status information for respective operands of the instructions;

dispatching, based on the first operand status information, the instructions to respective execution clusters of the microprocessor, wherein each of the respective execution clusters includes a corresponding second-level instruction scheduler, the second-level instruction schedulers being operatively coupled with the first-level instruction scheduler;

receiving, at the second-level instruction schedulers, the instructions from the first-level instruction scheduler;

storing second operand status information for respective operands of the instructions;

dispatching, based on the second operand status information, the instructions to respective execution units of the execution clusters;

executing one of more of the instructions; and

at least one of;

(i) assigning an execution thread to a single execution cluster; and

dispatching instructions associated with the execution thread to the single execution cluster;

(ii) dispatching the instructions from the first-level instruction scheduler in accordance with a load balancing policy; and

(iii) assigning a spawned thread to an execution cluster different than an execution cluster executing an associated spawning thread.