Multi-cycle scheduler with speculative picking of micro-operations
A multi-cycle scheduler for a processor includes early wake circuitry, late wake circuitry, and picker circuitry. In a first cycle of a clock, the early wake circuitry speculatively identifies child micro-operations as ready whose dependencies are satisfied by a set of ready parent micro-operations. In a second cycle of the clock, the picker circuitry picks at least one of the child micro-operations identified as ready for issue to execution circuitry. In addition, the late wake circuitry blocks from issue at least one picked child micro-operation speculatively identified as ready upon determining that a respective parent micro-operation did not issue to execution circuitry.
1 . A scheduler for a processor, comprising:
early wake circuitry;
late wake circuitry;
picker circuitry;
blocking circuitry; wherein:
in a first cycle of a clock:
the early wake circuitry speculatively identifies child micro-operations as ready whose dependencies are satisfied by a set of ready parent micro-operations which are ready to issue to execution circuitry; and
in a second cycle of the clock:
the picker circuitry picks at least one of the child micro-operations speculatively identified as ready for issue to execution circuitry;
the late wake circuitry generates an updated late ready signal that identifies ready child micro-operations based on parent micro-operations that issued for execution in the first cycle of the clock and forwards the updated late ready signal to the blocking circuitry; and
the blocking circuitry blocks from issue at least one picked child micro-operation speculatively identified as ready based on the updated late ready signal.
2 . The scheduler of claim 1 , further comprising:
scheduler entry circuitry including a set of scheduler entries for storing micro-operations to be picked by the picker circuitry for issue to execution circuitry; and
dependency matrix circuitry including a dependency record for each scheduler entry, each dependency record including storage elements for storing information identifying dependencies of micro-operations stored in that scheduler entry on micro-operations in other scheduler entries, wherein:
for speculatively identifying the child micro-operations as ready, the early wake circuitry:
receives a late ready signal generated by the late wake circuitry, the late ready signal identifying ready parent micro-operations based on micro-operations that issued for execution in a prior cycle of the clock;
based on the late ready signal, searches the dependency record to find the child micro-operations whose dependencies are satisfied by the set of ready parent micro-operations; and
provides, to the picker circuitry, an early ready signal that identifies the child micro-operations.
3 . The scheduler of claim 2 , further comprising:
broadcast circuitry including a respective signal line associated each scheduler entry, the broadcast circuitry asserting a signal on a respective signal line for a scheduler entry from where each micro-operation was issued for execution;
wherein:
the broadcast circuitry asserts a signal on a respective signal line associated with a scheduler entry for each parent micro-operation issued for execution in the first cycle of the clock; and
the late wake circuitry generates the updated late ready signal by searching the dependency record based on asserted respective signal lines to find ready child micro-operations whose dependencies are satisfied by parent micro-operations that issued for execution in the first cycle of the clock.
4 . The scheduler of claim 1 , wherein:
the late wake circuitry forwards the updated late ready signal to the early wake circuitry to be used for speculatively identifying grandchild micro-operations as ready whose dependencies are satisfied by the ready child micro-operations.
5 . The scheduler of claim 1 , wherein picked child micro-operations speculatively identified as ready that are blocked from issue are again picked for execution in a subsequent cycle of the clock and permitted to issue to execution units when their parent micro-operations have issued.
6 . The scheduler of claim 1 , wherein the late wake circuitry permits picked child micro-operations speculatively identified as ready to issue to execution circuitry upon determining that respective parent micro-operations issued to execution circuitry.
7 . The scheduler of claim 1 , wherein, when picking for issue the at least one of the child micro-operations that are speculatively identified as ready:
the picker circuitry picks child micro-operations in an age order, with an oldest child micro-operation being picked first.
8 . The scheduler of claim 7 , further comprising:
age matrix circuitry that includes an age matrix with information about relative ages of micro-operations stored in scheduler entries, wherein:
the picker circuitry determines an age order for the child micro-operations based on information in the age matrix.
9 . The scheduler of claim 1 , further comprising:
a specified number of execution units for executing micro-operations, wherein:
when picking for issue to execution circuitry the at least one of the child micro-operations speculatively identified as ready, the picker circuitry picks a maximum of the specified number of the child micro-operations speculatively identified as ready and others of the child micro-operations speculatively identified as ready are not picked.
10 . The scheduler of claim 1 , wherein a micro-operation is ready when all scheduler entries upon which the micro-operation depends have been picked and issued to the execution circuitry.
11 . The scheduler of claim 1 , wherein the blocking circuitry blocks from issue the at least one picked child micro-operation speculatively identified as ready by determining, based on the updated late ready signal, that the at least one picked child micro-operation was not ready due to a respective parent micro-operation not having issued to execution circuitry.
12 . A method for handling micro-operations in a scheduler in a processor, the method comprising:
in a first cycle of a clock:
speculatively identifying child micro-operations as ready whose dependencies are satisfied by a set of ready parent micro-operations which are ready to issue to execution circuitry; and
in a second cycle of the clock:
picking at least one of the child micro-operations speculatively identified as ready for issue to execution circuitry;
generating an updated late ready signal that identifies ready child micro-operations based on parent micro-operations that issued for execution in the first cycle of the clock; and
blocking from issue at least one picked child micro-operation speculatively identified as ready based on the updated late ready signal.
13 . The method of claim 12 , wherein speculatively identifying the child micro-operations as ready includes:
receiving a previous late ready signal, the previous late ready signal identifying ready parent micro-operations based on micro-operations that issued for execution in a prior cycle of the clock;
based on the previous late ready signal, searching a dependency matrix to find the child micro-operations whose dependencies are satisfied by the set of ready parent micro-operations; and
providing an early ready signal that identifies the child micro-operations.
14 . The method of claim 12 , further comprising:
using the updated late ready signal for speculatively identifying grandchild micro-operations as ready whose dependencies are satisfied by the ready child micro-operations.
15 . The method of claim 12 , further comprising:
asserting a signal on a respective signal line associated with a scheduler entry for each parent micro-operation issued for execution in the first cycle of the clock; and
generating the updated late ready signal by searching a dependency record based on asserted respective signal lines to find ready child micro-operations whose dependencies are satisfied by parent micro-operations that issued for execution in the first cycle of the clock.
16 . The method of claim 12 , further comprising:
in a subsequent cycle of the clock, again picking for execution picked child micro-operations speculatively identified as ready that are blocked from issue and permitting the child micro-operations to issue to execution units when their parent micro-operations have issued.
17 . The method of claim 12 , wherein picking for issue the at least one of the child micro-operations speculatively identified as ready includes:
picking child micro-operations in an age order, with an oldest child micro-operation being picked first.
18 . The method of claim 12 , further comprising, when picking for issue to execution circuitry the at least one of the child micro-operations speculatively identified as ready:
picking a maximum of a specified number of the child micro-operations speculatively identified as ready, the specified number being equal to a number of execution units; and
not picking others of the child micro-operations speculatively identified as ready.
19 . A system comprising:
a processor; and
a scheduler for the processor, the scheduler configured to:
speculatively identify, in a first cycle of a clock, child micro-operations as ready whose dependencies are satisfied by a set of ready parent micro-operations which are ready to issue to execution circuitry; and
in a second cycle of the clock:
pick at least one of the child micro-operations speculatively identified as ready for issue to execution circuitry;
generate an updated late ready signal that identifies ready child micro-operations based on parent micro-operations that issued for execution in the first cycle of the clock; and
block from issue at least one picked child micro-operation speculatively identified as ready based on the updated late ready signal.
20 . The system of claim 19 , wherein the scheduler is further configured to use the updated late ready signal to speculatively identify grandchild micro-operations as ready whose dependencies are satisfied by the ready child micro-operations.