Hierarchical instruction scheduler facilitating instruction replay

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

• virtualizing one or more execution threads to create a plurality of virtual threads;
• receiving instructions for execution at a second-level instruction scheduler;
• storing second-level operand status information for respective operands of the instructions;
• dispatching, based at least partly on respective second-level operand status information of one or more but fewer than all instructions of an instruction group, the instructions at a granularity corresponding to the instruction group to respective execution clusters of a plurality of execution clusters of the microprocessor, wherein each of the respective execution clusters includes a corresponding first-level instruction scheduler, the first-level instruction schedulers being operatively coupled with the second-level instruction scheduler;
• assigning respective virtual threads of the plurality of virtual threads to respective execution clusters of the plurality of execution clusters;
• dispatching instructions associated with a given respective virtual thread to a single execution cluster of the plurality of execution clusters;
• scheduling, by at least one timing wheel circuit of the second-level instruction scheduler using at least one circular instruction buffer, the instructions based at least partly on respective predictions as to when one or more of respective operands of the instructions will be available;
• notifying, by at least one picker circuit using at least one comparison circuit, the second-level instruction scheduler when one or more operands of a respective instruction become available;
• receiving, at the first-level instruction schedulers, the instructions from the second-level instruction scheduler;
• storing first-level operand status information for respective operands of the instructions;
• dispatching, based at least partly on the first-level operand status information, the instructions at a granularity corresponding to an individual instruction to respective execution units of the respective execution clusters of the plurality of execution clusters;
• returning at least one instruction of a particular instruction group from at least one first-level instruction scheduler to the second-level instruction scheduler for re-scheduling;
• replaying the returned at least one instruction of the particular instruction group to re-schedule the returned at least one instruction at the second-level instruction scheduler;
• and
• executing one of more of the instructions.

A microprocessor comprising:

• a plurality of execution clusters;
• logic configured to:
• virtualize one or more execution threads to create a plurality of virtual threads;
• at least one replay loop configured to:
• receive at least one instruction of a particular instruction group for re-scheduling;
• a plurality of second-level architectural elements for processing instructions in the microprocessor, the plurality of second-level architectural elements being configured to act as shared resources for the plurality of execution clusters, wherein the plurality of second-level architectural elements includes a second-level instruction scheduler configured to:
• receive instructions for execution;
• store second-level operand status information for respective operands of the instructions;
• dispatch the instructions at a granularity corresponding to an instruction group to respective execution clusters of the plurality of execution clusters based at least partly on the second-level operand status information of one or more but fewer than all instructions of the instruction group;
• assign respective virtual threads of the plurality of virtual threads to respective execution clusters of the plurality of execution clusters;
• and
• dispatch instructions associated with a given respective virtual thread to a single execution cluster of the plurality of execution clusters;
• and
• a plurality of first-level instruction schedulers, each of the first-level instruction schedulers being included in a respective execution cluster of the plurality of execution clusters, wherein each of the first-level instruction schedulers is configured to:
• receive the instructions for execution from the second-level instruction scheduler;
• store first-level operand status information for respective operands of the instructions received from the second-level instruction scheduler;
• dispatch for execution the instructions at a granularity corresponding to an individual instruction to respective execution units of the execution clusters based at least partly on the first-level operand status information for respective operands of a respective individual instruction;
• and
• return at least one instruction of a particular instruction group to the at least one replay loop for re-scheduling,
• wherein the second-level instruction scheduler includes:
• a timing wheel circuit configured to schedule the instructions based at least partly 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 second-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.

A hierarchical instruction scheduler included in a hierarchical microprocessor including a plurality of execution clusters and configured to virtualize one or more execution threads to create a plurality of virtual threads, the hierarchical instruction scheduler comprising:

• a second-level instruction scheduler configured to:
• receive instructions for execution;
• store second-level operand status information for respective operands of the instructions;
• dispatch the instructions at a granularity corresponding to an instruction group to respective execution clusters of the plurality of execution clusters based at least partly on respective second-level operand status information of one or more but fewer than all instructions of the instruction group;
• assign respective virtual threads of the plurality of virtual threads to respective execution clusters of the plurality of execution clusters;
• and
• dispatch instructions associated with a given respective virtual thread to a single execution cluster of the plurality of execution clusters;
• and
• a plurality of first-level instruction schedulers each operatively coupled with the second-level instruction scheduler, each first-level instruction scheduler being included in a respective execution cluster, wherein the first-level instruction schedulers are each configured to:
• receive instructions for execution from the second-level instruction scheduler;
• store first-level operand status information for respective operands of the instructions received from the second-level instruction scheduler;
• and
• dispatch instructions for execution at a granularity corresponding to an individual instruction to respective execution units of the execution clusters based at least partly on the first-level operand status information for respective operands of a respective individual instruction,
• wherein the second-level instruction scheduler includes:
• a timing wheel circuit configured to schedule the instructions based at least partly 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;
• a picker circuit configured to notify the second-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;
• and
• at least one replay loop configured to receive from at least one first-level instruction scheduler of the plurality of first-level instruction schedulers at least one instruction of a particular instruction group for re-scheduling.

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

• virtualizing one or more execution threads to create a plurality of virtual threads;
• assigning respective virtual threads of the plurality of virtual threads to respective execution clusters of a plurality of execution clusters of the microprocessor;
• dispatching instructions associated with a given respective virtual thread to a single execution cluster of the plurality of execution clusters;
• receiving instructions for execution at a second-level instruction scheduler;
• storing second-level operand status information for respective operands of the instructions;
• dispatching, based at least partly on respective second-level operand status information of one or more but fewer than all instructions of an instruction group, the instructions at a granularity corresponding to the instruction group to respective execution clusters of the plurality of execution clusters, wherein each of the respective execution clusters includes a corresponding first-level instruction scheduler, the first-level instruction schedulers being operatively coupled with the second-level instruction scheduler;
• scheduling, by the second-level instruction scheduler using at least one timing wheel circuit, the instructions based at least partly on respective predictions as to when one or more of respective operands of the instructions will be available;
• notifying the second-level instruction scheduler using at least one picker circuit when one or more operands of a respective instruction become available;
• receiving, at the first-level instruction schedulers, the instructions from the second-level instruction scheduler;
• storing first-level operand status information for respective operands of the instructions;
• dispatching, based at least partly on the first-level operand status information, the instructions at a granularity corresponding to an individual instruction to respective execution units of the respective execution clusters of the plurality of execution clusters;
• returning at least one instruction from at least one first-level instruction scheduler to the second-level instruction scheduler for re-scheduling;
• replaying the returned at least one instruction to re-schedule the returned at least one instruction for dispatching to a respective execution cluster of the plurality of 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 second-level instruction scheduler in accordance with a load balancing policy;
• or
• (iii) assigning a spawned thread to an execution cluster different from an execution cluster executing an associated spawning thread.