Technique for reduced-tag dynamic scheduling and reduced-tag prediction
AssigneeThe Regents of the University of Michigan
InventorsDaniel J. Ernst, Todd M. Austin
Life of this patent
Estimating the term…
Abstract
The present invention provides a dynamic scheduling scheme that uses reservation stations having at least one station that stores an at least two operand instruction. An allocator portion determines that the instruction, entering the pipeline, has one ready operand and one not-ready operand, and accordingly places it in a station having only one comparator. The one comparator then compares the not-ready operand with tags broadcasted on a result tag bus to determine when the not-ready operand becomes ready. Once ready, execution is requested to the corresponding functional unit.
Claims9
A reservation station comprising:
- a plurality of stations adapted to maintain an instruction having at least two source operands;
- a first subset of the plurality of stations includes two tag comparators, one for each of the at least two source operands, each of the two tag comparators is configured to snoop a result tag bus for a result tag that matches a tag for each of the respective source operands;
- a second subset of the plurality of stations includes one tag comparator assigned to one of the at least two source operands, the one tag comparator is configured to snoop the result tag bus for a result tag that matches a tag of the assigned source operand;
- and
- a third subset of the plurality of stations includes zero tag comparators.
A method for scheduling an instruction for execution, comprising:
- receiving an instruction having a first unavailable operand and a second unavailable operand;
- predicting that the second unavailable operand will become available after the first unavailable operand;
- positioning the instruction in a station having one tag comparator such that only the second unavailable operand is compared to tags broadcasted on a result tag bus by a tag comparator;
- executing the instruction when the tag comparator determines that the second unavailable operand is available.
A dynamic scheduler pipeline comprising:
- a reservation station having a plurality of stations for storing instructions;
- a first subset of the reservation stations, each of the first subset having two tag comparators to compare tags of respective operands in a two operand instruction in the first subset with tags broadcasted on the result tag bus;
- a second subset of the reservation stations, each of the second subset comprising one tag comparator that compares one tag of a two operand instruction in the second subset with tags broadcasted on the result tag bus;
- a third subset of the reservation stations, each of the third subset comprising no tag comparators;
- and
- an allocator that positions instructions into the stations based on a number of unavailable operands within the instructions;
- wherein at least one of the stations has less than two tag comparators for comparing an operand of an at least two operand instruction with tags broadcasted on a result tag bus.
A method for scheduling instructions for execution, comprising:
- receiving an instruction having at least two operands, wherein at least one of the at least two operands is unavailable;
- positioning the instruction in a station of a reservation station based on a number of unavailable operands within the instruction;
- predicting which of two unavailable operands of a two operand instruction will be the last available operand and wherein the last available operand is positioned in a station having only one tag comparator;
- comparing a tag of the at least one unavailable operand with tags broadcasted on a result tag bus to determine when the unavailable operand becomes available;
- not comparing a tag of an available operand with the tags broadcasted on the result tag bus;
- and
- requesting permission for execution of the instruction when the at least one unavailable operand is determined to be available.
Dependencies are inferred from the claim text.