Scheduler implementing dependency matrix having restricted entries

Patent metadata

Field	Value
Publication number	US-10235180-B2
Application number	US-201213723684-A
Country	US
Kind code	B2
Filing date	Dec 21, 2012
Priority date	Dec 21, 2012
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

A scheduler implementing a dependency matrix having restricted entries is disclosed. A processing device of the disclosure includes a decode unit to decode an instruction and a scheduler communicably coupled to the decode unit. In one embodiment, the scheduler is configured to receive the decoded instruction, determine that the decoded instruction qualifies for allocation as a restricted reservation station (RS) entry type in a dependency matrix maintained by the scheduler, identify RS entries in the dependency matrix that are free for allocation, allocate one of the identified free RS entries with information of the decoded instruction in the dependency matrix, and update a row of the dependency matrix corresponding to the claimed RS entry with source dependency information of the decoded instruction.

First claim

What is claimed is:

1. A processing device comprising:
a decode unit to decode an instruction;
a scheduler communicably coupled to the decode unit, the scheduler to:
receive the decoded instruction;
determine that the decoded instruction qualifies as a restricted reservation station entry type in a dependency matrix maintained by the scheduler, wherein to qualify, the decoded instruction is restricted from having one or more dependent instructions in the dependency matrix;
responsive to determining that the decoded instruction qualifies as the restricted reservation station entry type, allocate a restricted reservation station entry in the dependency matrix; and
update the restricted reservation station entry in the dependency matrix with information from the decoded instruction, wherein the restricted reservation station entry comprising the information from the decoded instruction is prevented from being updated to reference a dependent instruction in the dependency matrix.

2. A computer-implemented method, comprising:
receiving, by a scheduler of a processing device, a decoded instruction to be decoded by the processing device;
determining, by the scheduler, that the decoded instruction qualifies as a restricted reservation station entry type in a dependency matrix maintained by the scheduler, wherein to qualify, the decoded instruction is restricted from having one or more dependent instructions in the dependency matrix;
responsive to determining that the decoded instruction qualifies as the restricted reservation station entry type, allocating, by the scheduler, a restricted reservation station entry in the dependency matrix; and
updating, by the scheduler, the restricted reservation station entry in the dependency matrix with information from the decoded instruction, wherein the restricted reservation station entry comprising the information from the decoded instruction is prevented from being updated to reference a dependent instruction in the dependency matrix.

3. The method of claim 2 , wherein the decoded instruction is at least one of a store instruction, a load instruction, or a branch instruction.

4. A system, comprising:
a memory to store a dependency matrix comprising entries indicative of a dependency status of a plurality of instructions, wherein the dependency matrix comprises one or more restricted entries having at least one of a row entry in the dependency matrix and without a corresponding column entry in the dependency matrix or a column entry in the dependency matrix and without a corresponding row entry in the dependency matrix; and
a scheduler executed by a processing device communicably coupled to the memory, the scheduler to:
broadcast an identifier (ID) of an instruction that is scheduled to one or more instructions awaiting scheduling and tracked by the scheduler using the dependency matrix;
determine that the instruction qualifies as a restricted reservation station entry type in the dependency matrix, wherein to qualify, the decoded instruction is restricted from having one or more dependent instructions in the dependency matrix;
responsive to determining that the decoded instruction qualifies as the restricted reservation station entry type, allocating a restricted reservation station entry in the dependency matrix; and
update the restricted reservation station entry in the dependency matrix with information from the instruction, wherein the restricted reservation station entry comprising the information from the decoded instruction is prevented from being updated to reference a dependent instruction in the dependency matrix.

5. A non-transitory machine-readable storage medium including executable instructions that, when executed by a processing device, cause the processing device to:
receive, by the processing device, a decoded instruction;
determine that the decoded instruction qualifies as a restricted reservation station entry type in a dependency matrix maintained by a scheduler, wherein to qualify, the decoded instruction is restricted from having one or more dependent instructions in the dependency matrix;
responsive to determining that the decoded instruction qualifies as the restricted reservation station entry type, allocate a restricted reservation station entry in the dependency matrix; and
update the restricted reservation station entry in the dependency matrix with information from the decoded instruction, wherein the restricted reservation station entry comprising the information from the decoded instruction is prevented from being updated to reference a dependent instruction in the dependency matrix.

6. The processing device of claim 1 , wherein the allocated restricted reservation station entry in the dependency matrix comprises at least one column in the dependency matrix without a corresponding row in the dependency matrix.

7. The processing device of claim 1 , wherein the allocated restricted reservation station entry in the dependency matrix comprises a row in the dependency matrix without a corresponding column in the dependency matrix.

Assignees

• Srinivasan Srikanth T
• Merten Matthew C
• Sutanto Bambang
• Kulkarni Rahul R
• Deinlein Justin M
• Hadley James D
• Intel Corp

Inventors

• Srinivasan Srikanth T
• Merten Matthew C
• Sutanto Bambang
• Kulkarni Rahul R
• Deinlein Justin M
• Hadley James D

Classifications

• G06F9/3838 Primary

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