# US 2018/0321943 A1 · Data read-write scheduler and reservation station for vector operations

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

- Number: US 2018/0321943 A1
- Document ID: US20180321943A1
- Status: Published application
- Kind: A1
- Application number: 16/039,605
- Filed: 2018-07-19
- Published: 2018-11-08
- Earliest claimed: 2016-01-20
- Assignees: Cambricon Technologies Corporation Limited
- Applicants: Cambricon Technologies Corporation Limited
- Inventors: Dong HAN; Shaoli LIU; Yunji CHEN; Tianshi Chen
- Web page: https://patentgrep.com/patent/US20180321943A1

## CPC

- G06F 15/78: comprising a single central processing unit
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/3834: {Maintaining memory consistency}
- G06F 15/76: Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16)
- G06F 15/7842: {on one IC chip (single chip microcontrollers)}
- G06F 15/8053: {Vector processors}
- G06F 9/30043: {LOAD or STORE instructions; Clear instruction}
- G06F 9/3824: {Operand accessing}
- G06F 9/3826: {Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage}
- 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 15/7846: {On-chip cache and off-chip main memory}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present disclosure provides a data read-write scheduler and a reservation station for vector operations. The data read-write scheduler suspends the instruction execution by providing a read instruction cache module and a write instruction cache module and detecting conflict instructions based on the two modules. After the time is satisfied, instructions are re-executed, thereby solving the read-after-write conflict and the write-after-read conflict between instructions and guaranteeing that correct data are provided to a vector operations component. Therefore, the subject disclosure has more values for promotion and application.

## Claims

### Claim 1

A data read scheduler for vector operations, comprising:
a read instruction preprocessing module that includes a read instruction preprocessing unit, wherein the read instruction preprocessing unit is configured to:
receive a vector read instruction,
detect at least one write-after-read conflict between the vector read instruction and one or more vector write instructions stored in a data write scheduler, and
identify one of the vector write instructions that result the write-after-read conflict as a dependent vector write instruction that corresponds to the vector read instruction; and
a read control module that includes a read control unit, wherein the read control unit is configured to:
extract one or more read requests from the received vector read instruction,
sequentially submit the one or more read requests to an on-chip RAM based on an execution status of the dependent vector write instruction that corresponds to the received vector read instruction, and
receive input data from the on-chip RAM.

### Claim 2 (depends on 1)

The data read scheduler of claim 1, wherein the read instruction preprocessing unit is further configured to:
obtain a first pair of starting and ending addresses from the vector read instruction,
wherein the first pair of starting and ending addresses identify a target read range in the on-chip RAM, and
wherein each of the one or more read requests is configured to read data from a read address within the target read range,
obtain a second pair of starting and ending addresses of from each of the vector write instructions in the data write scheduler,
wherein each of the one or more second pairs of starting and ending addresses identifies a target write range in the on-chip RAM, and
wherein each of the vector write instructions includes one or more write requests respectively configured to write data to a write address within the target write range;
compare the target read range with each of the one or more target write ranges;
detect the write-after-read conflict based on a determination that the target read range overlaps at least one of the one or more target write ranges.

### Claim 3 (depends on 2)

The data read scheduler of claim 2, wherein the read instruction preprocessing unit is further configured to:
select one from the one or more vector write instructions that overlap with the vector read instruction as the dependent vector write instruction, wherein the dependent vector write instruction is stored nearest to the vector read instruction in an instruction queue, and
obtain an identification of the dependent vector write instruction, and
cache the vector read instruction, the first pair of the starting and ending addresses in the vector read instruction, and the identification of the dependent vector write instruction.

### Claim 4 (depends on 1)

The data read scheduler of claim 1, wherein the read instruction preprocessing module further includes multiple read instruction preprocessing units configured to parallelly preprocess multiple vector read instructions; and
wherein the read control module further includes multiple read control units configured to parallelly execute read requests of the multiple vector read instructions.

### Claim 5 (depends on 1)

The data read scheduler of claim 1, wherein the read control unit is further configured to:
execute one of the read requests based on a determination that the execution status indicates that the dependent vector write instruction is executed, that a data queue of the read control unit is not full, and that the on-chip RAM is able to receive the read request.

### Claim 6 (depends on 2)

The data read scheduler of claim 2, wherein the read control unit is further configured to execute one of the read requests based on a determination
that the execution status indicates that the dependent vector write instruction is being executed,
that a current write address of a current write request of the dependent vector write instruction has exceeded the ending address of the target read range of the vector read instruction,
that a data queue of the read control unit is not full, and
that the on-chip RAM is able to receive the read request.

### Claim 7 (depends on 2)

The data read scheduler of claim 2, wherein the read control unit is further configured to execute one of the read requests based on a determination
that the execution status indicates that the dependent vector write instruction is being executed,
that the ending address of the target write range of the dependent vector write instruction has been exceeded by a current read address of a current read request of the vector read instruction,
that a data queue of the read control unit is not full, and
that the on-chip RAM is able to receive the read request.

### Claim 8 (depends on 1)

The data read scheduler of claim 1, further comprising a read data cache module,
wherein the read control unit is further configured to store the received input data received from the on-chip RAM into the read data cache module, and
wherein the read data cache module is configured to transmit the input data to a vector operations component.

### Claim 9 (depends on 3)

The data read scheduler of claim 3, further comprising:
an instruction cache configured to receive and cache the vector read instruction, and
a read instruction cache module that interfaces with the read instruction preprocessing module and the read control module,
wherein the read instruction cache module includes one or more read instruction cache units, and
wherein each of the read instruction cache units is configured to
receive and cache the vector read instruction obtained from the read instruction preprocessing unit and the identification of the dependent vector write instruction, and
dynamically update status of the vector read instruction cached in the read instruction cache units and transmit the vector read instruction according to an execution status of the vector read instruction obtained from the read control module and the execution status of the dependent vector write instruction obtained from the data write scheduler.

### Claim 10 (depends on 9)

The data read scheduler of claim 9, wherein each of the read instruction cache units is configured to:
update the status of the vector read instruction to indicate that the vector read instruction has been transmitted based on a determination that a new vector read instruction enters a queue of the read instruction cache unit,
update the status of the vector read instruction to indicate that the vector read instruction is transmittable based on a determination that the dependent vector write instruction is being executed or has been executed,
transmit the vector read instruction and update the status of the vector read instruction to indicate that the vector read instruction is being executed based on a determination
that a previous status of the vector read instruction indicates that the vector read instruction is transmittable, and
that an immediately preceding vector read instruction has been transmitted,
update the status of the vector read instruction to indicate that the vector read instruction has been transmitted after the read requests of the vector read instruction have been transmitted by the read instruction cache unit, and
update the status of the vector read instruction to indicated that the vector read instruction is executed based on a determination that the read requests of the vector read instruction have been processed by the on-chip RAM, and that results of the read requests have been received from the on-chip RAM.

### Claim 11

A data write scheduler for vector operations, comprising:
a write instruction preprocessing unit configured to
receive a vector write instruction,
detect at least one read-after-write conflict between the vector write instruction and one or more vector read instructions stored in a data read scheduler, and
identify one of the vector read instructions that result the read-after-write conflict as a dependent vector read instruction that corresponds to the vector write instruction; and
a write control module configured to
extract one or more write requests from the received vector write instruction,
sequentially submit the one or more write requests and content data to an on-chip RAM based on an execution status of the dependent vector read instruction that corresponds to the receive vector write instruction, and
receive feedback from the on-chip RAM regarding the write requests.

### Claim 12 (depends on 11)

The data write scheduler of claim 11, wherein write instruction preprocessing unit is further configured to:
obtain a first pair of starting and ending addresses from the vector write instruction,
wherein the first pair of starting and ending addresses identify a target write range in the on-chip RAM, and
wherein each of the one or more write request is configured to write a portion of the content data to a write address within the target write range,
obtain a second pair of starting and ending addresses from each of the vector read instructions in the data read scheduler,
wherein each of the second pairs of starting and ending addresses identify a target read range in the on-chip RAM, and
wherein each of the vector read instructions includes one or more read requests respectively configured to read data from a read address within the target read range,
compare the target write range with each of the target read ranges, and
detect the read-after-write conflict based on a determination that the target write range overlaps at least one of the one or more target read ranges.

### Claim 13 (depends on 11)

The data write scheduler of claim 11, wherein the write instruction preprocessing unit is further configured to:
select one from the one or more of the vector read instructions that overlap with the vector write instruction as the dependent vector read instruction, wherein the dependent vector read instruction is nearest to the vector write instruction in an instruction queue, and
obtain an identification of the dependent vector read, and
cache the vector write instruction, the first pair of the starting and ending addresses in the vector write instruction, and the identification of the dependent vector read instruction.

### Claim 14 (depends on 11)

The data write scheduler of claim 11, wherein the write control module is further configured to:
execute one of the write requests based on a determination that the execution status indicates that the dependent vector read instruction is executed, that a data queue of the write control module includes data to be written, and that the on-chip RAM is able to receive the write request.

### Claim 15 (depends on 11)

The data write scheduler of claim 11, wherein the write control module is further configured to:
execute one of the write requests based on a determination
that a current read address of a current read request of the dependent vector read instruction has exceeded the ending address of the target write range,
that a data queue of the write control module includes data to be written, and
that the on-chip RAM is able to receive the write request.

### Claim 16 (depends on 11)

The data write schedule of claim 11, wherein the write control module is further configured to:
execute one of the write requests based on a determination
that the ending address of the target read range of the dependent vector read instruction has been exceeded a current write address of a current write request the target write range,
that a data queue of the write control module includes data to be written, and
that the on-chip RAM is able to receive the write request.

### Claim 17 (depends on 11)

The data write scheduler of claim 11, further comprising a written data cache configured to receive and cache the content data and to transmit the content data to the write control module.

### Claim 18 (depends on 11)

The data write scheduler of claim 11, further comprising:
an instruction cache configured to receive and cache the vector write instruction;
a write instruction cache unit that interfaces with the write instruction preprocessing unit and the write control module, wherein the write instruction cache unit is configured to
receive and cache the vector write instruction processed by the write instruction preprocessing unit and the identification of the dependent vector read instruction, and
dynamically update status of the vector write instruction cached in the write instruction cache unit and transmit the vector write instruction according to the execution status of the dependent vector read instruction obtained from the data read scheduler and an execution status of the vector write instruction obtained from the write control module.

### Claim 19 (depends on 18)

The data write scheduler of claim 18, wherein the write instruction cache unit is further configured to:
update the status of the vector write instruction to indicate that the vector write instruction is to be transmitted based on a determination that a new vector write instruction enters a queue of the write instruction cache unit,
update the status of the vector write instruction to indicate that the vector write instruction is transmittable based on a determination that the dependent vector read instruction is being executed or has been executed,
transmit the vector write instruction and update the status of the vector write instruction to indicate that the vector write instruction is being executed based on a determination
that an immediately preceding vector write instruction has been transmitted, and
that a previous status of the vector write instruction indicates that the vector write instruction is transmittable,
update the status of the vector write instruction to indicate that the vector write instruction is transmitted after the write requests of the vector write instruction have been transmitted by the write control module, and
update the status of the vector write instruction to indicate that the vector write instruction is executed based on a determination that all of the write requests of the vector write instruction have been processed by the on-chip RAM, and that the feedback is received from the on-chip RAM.

### Claim 20

A reservation station for vector operations, comprising: an I/O interface, an on-chip RAM, a data read-write scheduler, a decoder and a vector operations component,
wherein the on-chip RAM is configured to store the input data required for vector operations and store output data obtained through computation;
wherein the I/O interface is configured to perform read-write access to the on-chip RAM by devices outside of the reservation station, the read-write access including: loading the input data that need to be processed to the on-chip RAM, and moving the output data obtained after operations to external devices;
wherein the decoder is configured to read instructions from an external instruction cache queue, and decode the instructions into vector read instructions, vector write instructions and vector operations instructions, send the vector read instructions and vector write instructions to the data read-write scheduler, and send the vector operations instructions to the vector operations component;
wherein the vector operations component is configured to receive the input data from the data read-write scheduler for operations after receiving the vector operations instruction sent by the decoder, and then transmit the output data obtained from operations to the data read-write scheduler;
wherein the data read-write scheduler comprises a data read scheduler and a data write scheduler; wherein the data read scheduler comprises a read instruction preprocessing module and a read control module; the data write scheduler comprises a write instruction preprocessing unit and a write control module;
wherein the read instruction preprocessing module comprises a read instruction preprocessing unit; the read instruction preprocessing unit is configured to receive a vector read instruction and detect whether there is write-after-read conflict between the vector read instruction and the vector write instruction in the data write scheduler; if there is the conflict, the vector write instruction having the write-after-read conflict with the vector read instruction serves as the vector write instruction that the vector read instruction depends on; the read control module comprises a read control unit; the read control unit is configured to parse out one or multiple read requests according to the received vector read instruction and determine whether the time for executing the read request is satisfied according to the status of the vector write instruction that the vector read instruction depends on, and when the time for executing the read request is satisfied, send the read request to the on-chip RAM and receive input data from the on-chip RAM ; and
wherein the write instruction preprocessing unit is configured to receive a vector write instruction and detect whether there is a read-after-write conflict between the vector write instruction and the vector read instruction in the data read scheduler, if there is the conflict, the vector read instruction having the read-after-write conflict with the vector write instruction serves as the vector read instruction that the vector write instruction depends on; the write control module is configured to parse out a write request according to the received vector write instruction and determine the time for executing the write request according to the status of the vector read instruction that the vector write instruction depends on; when the time for executing the write request is satisfied, send the write request and written data to the on-chip RAM and receive feedback of writing result from the on-chip RAM.
