Criticality based port scheduling

Patent metadata

Field	Value
Publication number	US-10719355-B2
Application number	US-201815890984-A
Country	US
Kind code	B2
Filing date	Feb 7, 2018
Priority date	Feb 7, 2018
Publication date	Jul 21, 2020
Grant date	Jul 21, 2020

Abstract

A processor including an execution unit, an instruction scheduler circuit to identify a first instruction of an instruction stream, identify a second instruction on which execution of the first instruction depends, and assign a first dispatch priority value to the first instruction and the second instruction, and a dispatch circuit to dispatch, based on the first dispatch priority value, the first instruction and the second instruction to an instruction execution circuit.

First claim

What is claimed is:

1. A processor, comprising:
an execution circuit;
an instruction scheduler circuit to:
identify a first instruction of an instruction stream via construction of a bitmap table, wherein the bitmap table comprises:
a plurality of rows, wherein each row of the plurality of rows represents a source register;
a plurality of columns, wherein each column of the plurality of columns represents an instruction received by the instruction scheduler circuit; and
a plurality of cells comprising a first cell identified by a corresponding row and a corresponding column, the first cell to store a logical value indicating that the first instruction represented by the corresponding column references a first source register represented by the corresponding row, wherein the first source register is to receive an input value for the first instruction;

identify a second instruction on which execution of the first instruction depends via identification of the logical value in a second cell that precedes the first cell in order of execution along the corresponding row; and
assign a first dispatch priority value to the first instruction and to the second instruction; and

a dispatch circuit to dispatch, based on the first dispatch priority value, the first instruction and the second instruction to the execution circuit.

2. The processor of claim 1 , wherein the instruction scheduler circuit is to identify the first instruction as a critical instruction that causes an execution latency that exceeds a pre-determined period of time, and wherein the critical instruction is one of a branch instruction or a load instruction.

3. The processor of claim 1 , wherein the instruction scheduler circuit is further to, prior to identifying the first instruction, identify the second instruction as a non-critical instruction and assign a second dispatch priority value to the second instruction, wherein the second dispatch priority value is lower than the first dispatch priority value.

4. The processor of claim 1 , further comprising a reserve station, associated with the dispatch circuit, to store a plurality of instructions to be dispatched, wherein the instruction scheduler circuit is further to:
responsive to identifying the first instruction, determine a first time of receiving the first instruction by the instruction scheduler circuit;
assign the first time as a first age value to the first instruction; and
store the first instruction in the reserve station.

5. The processor of claim 4 , wherein the instruction scheduler circuit is further to:
identify a third instruction of the instruction stream;
assign the third instruction the first dispatch priority value;
determine a third time of the third instruction received by the instruction scheduler circuit; and
assign the third time as a third age value to the third instruction,
wherein responsive to determining that the third age value is greater than the first age value, dispatch the third instruction to the execution circuit prior to dispatching the first instruction.

6. The processor of claim 4 , wherein the instruction scheduler circuit is further to assign the first dispatch priority value to a fourth instruction responsive to determining that the fourth instruction in the reserve station is associated with a second dispatch priority value that is lower than the first dispatch priority value and that the fourth instruction is associated with a fourth age value exceeding a pre-determined value.

7. The processor of claim 1 , wherein the instruction scheduler circuit is further to:
identify instructions on which the execution of the first instruction depends, wherein the instructions are in a reserve station; and
assign the first dispatch priority value to the instructions.

8. The processor of claim 1 , wherein the execution circuit comprises:
a first execution unit to execute instructions with the first dispatch priority value; and
a second execution unit to execute instructions with a second dispatch priority value, wherein the dispatch circuit is to dispatch the second instruction to the second execution unit prior to dispatching the first instruction to the first execution unit.

9. A system comprising:
a memory to store an instruction stream; and
a processor, communicatively coupled to the memory, comprising:
an execution circuit;
an instruction scheduler circuit to:
identify a first instruction of the instruction stream via construction of a bitmap table, wherein the bitmap table comprises:
a plurality of columns, wherein each column of the plurality of columns represents a source register;
a plurality of rows, wherein each row of the plurality of rows represents an instruction received by the instruction scheduler circuit and
a plurality of cells comprising a first cell identified by a corresponding column and a corresponding row, the first cell to store a logical value indicating that the first instruction represented by the corresponding row references a first source register represented by the corresponding column, wherein the first source register is to receive an input value for the first instruction;

identify a second instruction on which execution of the first instruction depends via identification of the logical value in a second cell that precedes the first cell in order of execution along the corresponding column; and
assign a first dispatch priority value to the first instruction and to the second instruction; and

a dispatch circuit to dispatch, based on the first dispatch priority value, the first instruction and the second instruction to the execution circuit.

10. The system of claim 9 , wherein the instruction scheduler circuit is to identify the first instruction as a critical instruction that causes an execution latency that exceeds a pre-determined period of time, and wherein the critical instruction is one of a branch instruction or a load instruction.

11. The system of claim 9 , wherein the instruction scheduler circuit is further to, prior to identifying the first instruction, identify the second instruction as a non-critical instruction and assign a second dispatch priority value to the second instruction, wherein the second dispatch priority value is lower than the first dispatch priority value.

12. The system of claim 9 , wherein the processor further comprises a reserve station, associated with the dispatch circuit, to store a plurality of instructions to be dispatched, wherein the instruction scheduler circuit is further to:
responsive to identifying the first instruction, determine a first time of the first instruction received by the instruction scheduler circuit;
assign the first time as a first age value to the first instruction; and
store the first instruction in the reserve station.

13. The system of claim 12 , wherein the instruction scheduler circuit is further to:
identify a third instruction of the instruction stream;
assign the third instruction a first dispatch priority value;
determine a third time of the third instruction received by the instruction scheduler circuit; and
assign the third time as a third age value to the third instruction,
wherein responsive to determining that the third age value is greater than the first age value, dispatch the third instruction to the execution circuit prior to dispatching the first instruction.

14. The system of claim 12 , wherein the instruction scheduler circuit is further to assign the first dispatch priority value to a fourth instruction responsive to determining that the fourth instruction in the reserve station is associated with a second dispatch priority

Assignees

• Intel Corp

Inventors

• Roy Pooja
• Gaur Jayesh
• Subramoney Sreenivas
• Sperber Zeev
• Titov Alexandr
• Rappoport Lihu
• Shwartsman Stanislav
• Wang Hong
• Yoaz Adi
• Singhal Ronak
• Chappell Robert S

Classifications

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• G06F9/384

  Register renaming · CPC title

• G06F9/3838

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F9/4818 Primary

  Priority circuits therefor · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title