# US 12,118,357 B2 · Encoded data dependency matrix for power efficiency scheduling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,118,357 B2
- Document ID: US12118357B2
- Status: Granted
- Kind: B2
- Application number: 17/855,621
- Filed: 2022-06-30
- Published: 2024-01-04
- Granted: 2024-10-15
- Earliest claimed: 2022-06-30
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: Rajesh Kumar Arunachalam; Manivannan Bhoopathy; Hon-Hin Wong; Scott Thomas Bingham
- Web page: https://patentgrep.com/patent/US12118357B2

## CPC

- G06F 9/30145: {Instruction analysis, e.g. decoding, instruction word fields}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The disclosed system may include a processor configured to encode, using an encoding scheme that reduces a number of bits needed to represent one or more instructions from a set of instructions in an instruction buffer represented by a dependency matrix, a dependency indicating that a child instruction represented in the dependency matrix depends on a parent instruction represented in the dependency matrix. The processor may also be configured to store the encoded dependency in the dependency matrix and dispatch instructions in the instruction buffer based at least on decoding one or more dependencies stored in the dependency matrix for the instructions. Various other methods, systems, and computer-readable media are also disclosed.

## Claims

### Claim 1

A method comprising:
encoding, using an encoding scheme that encodes index locations into values, a first dependency indicating that a first instruction represented in a dependency matrix depends on a second instruction represented in the dependency matrix;
storing the encoded first dependency in the dependency matrix; and
dispatching the first instruction based at least on decoding one or more dependencies stored in the dependency matrix for the first instruction.

### Claim 2 (depends on 1)

The method of claim 1, wherein the encoding scheme corresponds to a partial encoding scheme comprising dividing a set of instructions represented by the dependency matrix into groups and representing a source instruction of a dependency using a group value corresponding to a group containing the source instruction and an index value corresponding to the source instruction within the group.

### Claim 3 (depends on 2)

The method of claim 2, wherein the decoding, in the partial encoding scheme, comprises:
identifying, using the group value, the group that contains the source instruction; and
identifying, using the index value, which instruction in the identified group corresponds to the source instruction.

### Claim 4 (depends on 1)

The method of claim 1, wherein the encoding scheme corresponds to a full encoding scheme comprising representing a source instruction of a dependency using a location value corresponding to an index location of the source instruction in the dependency matrix.

### Claim 5 (depends on 4)

The method of claim 4, wherein the decoding, in the full encoding scheme, comprises identifying, using the location value, the source instruction.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
encoding a second dependency indicating that the first instruction depends on a third instruction represented in the dependency matrix; and
storing the encoded second dependency in the dependency matrix.

### Claim 7 (depends on 6)

The method of claim 6, wherein the second dependency is encoded with a second encoding scheme different from the encoding scheme.

### Claim 8 (depends on 1)

The method of claim 1, wherein the encoding scheme includes a special value indicating no dependency.

### Claim 9 (depends on 1)

The method of claim 1, wherein dispatching the first instruction is further based on identifying a readiness of each of the decoded one or more dependencies.

### Claim 10

A method comprising:
storing a first instruction in a buffer for queueing instructions, wherein the first instruction depends on a second instruction in the buffer;
encoding, using an encoding scheme that reduces a number of bits needed to represent one or more instructions from a set of instructions in the buffer by encoding index locations of the buffer into values, a first dependency indicating that the first instruction depends on the second instruction;
storing the encoded first dependency in a dependency matrix; and
dispatching the first instruction based at least on decoding one or more dependencies stored in the dependency matrix for the first instruction.

### Claim 11 (depends on 10)

The method of claim 10, wherein the encoding scheme corresponds to a partial encoding scheme comprising dividing the set of instructions into groups and representing a source instruction of a dependency using a group value corresponding to a group containing the source instruction and an index value corresponding to the source instruction within the group.

### Claim 12 (depends on 11)

The method of claim 11, wherein the decoding, in the partial encoding scheme, comprises:
identifying, using the group value, the group that contains the source instruction; and
identifying, using the index value, which instruction in the identified group corresponds to the source instruction.

### Claim 13 (depends on 10)

The method of claim 10, wherein the encoding scheme corresponds to a full encoding scheme comprising representing a source instruction of a dependency using a location value corresponding to a buffer location of the source instruction in the buffer.

### Claim 14 (depends on 13)

The method of claim 13, wherein the decoding, in the full encoding scheme, comprises identifying, using the location value, the source instruction.

### Claim 15 (depends on 10)

The method of claim 10, further comprising:
encoding a second dependency indicating that the first instruction depends on a third instruction in the buffer; and
storing the encoded second dependency in the dependency matrix.

### Claim 16 (depends on 10)

The method of claim 10, wherein the encoding scheme includes a special value indicating no dependency.

### Claim 17 (depends on 10)

The method of claim 10, wherein an index location in the dependency matrix corresponds to a buffer location in the buffer.

### Claim 18

A system comprising:
a physical memory; and
at least one physical processor comprising:
a buffer for queueing instructions;
a dependency matrix for tracking dependencies between instructions in the buffer; and
a control circuit for identifying ready instructions in the buffer using the dependency matrix, the control circuit configured to:
encode, using an encoding scheme that reduces a number of bits needed to represent one or more instructions from a set of instructions in the buffer by encoding index locations of the buffer into values, a first dependency indicating that a first instruction in the buffer depends on a second instruction in the buffer;
store the encoded first dependency in the dependency matrix in an index location corresponding to a buffer location of the first instruction in the buffer; and
dispatch the first instruction based at least on decoding one or more dependencies stored in the dependency matrix for the first instruction.

### Claim 19 (depends on 18)

The system of claim 18, wherein:
the encoding scheme corresponds to a partial encoding scheme comprising dividing the set of instructions into groups and representing a source instruction of a dependency using a group value corresponding to a group containing the source instruction and an index value corresponding to the source instruction within the group; and
the decoding, in the partial encoding scheme, comprises:
identifying, using the group value, the group that contains the source instruction; and
identifying, using the index value, which instruction in the identified group corresponds to the source instruction.

### Claim 20 (depends on 18)

The system of claim 18, wherein:
the encoding scheme corresponds to a full encoding scheme comprising representing a source instruction of a dependency using a location value corresponding to a buffer location of the source instruction in the buffer; and
the decoding, in the full encoding scheme, comprises identifying, using the location value, the source instruction.