Index based memory access using single instruction multiple data unit

Patent metadata

Field	Value
Publication number	US-10776118-B2
Application number	US-201615261216-A
Country	US
Kind code	B2
Filing date	Sep 9, 2016
Priority date	Sep 9, 2016
Publication date	Sep 15, 2020
Grant date	Sep 15, 2020

Abstract

A computing system comprising a central processing unit (CPU), a memory processor and a memory device comprising a data array and an index array. The computing system is configured to store data lines comprising data elements in the data array and to store index lines comprising a plurality of memory indices in the index array. The memory indices indicate memory positions of data elements in the data array with respect to a start address of the data array. There is further provided a related computer implemented method and a related computer program product.

First claim

What is claimed is:

1. A computing system comprising:
a memory comprising a data array and an index array, wherein:
the data array comprises at least one data line, each data line comprises a set of data fields, each data field is configured to hold a data element, and each data field is indexed by a memory index;
the index array comprises at least one index line, each index line comprises a set of memory indices indicating memory positions of data elements in the data array with respect to a start data field of the data array, wherein the start data field is one particular data field in the data array;
when the computing system is in a burst mode of operation, data elements in the data array are accessed on a line-by-line basis, such that a read operation results in reading a complete data line, and a write operation results in writing to a complete data line;

a memory processor configured to be in communication with the memory, the memory processor comprising a buffer and a cache;
a hardware processor configured to be in communication with the memory processor, the hardware processor configured to send a read request for a set of requested data elements to the memory processor, wherein:
the read request includes an index line address and an address of the start data field of the data array, the index line address is an address of a requested index line among the index array; and
the requested index line includes memory indices of data fields that hold the set of requested data elements among the data array;

the memory processor is configured to:
receive the read request;
use the memory indices among the requested index line to identify a number of data lines that include the data fields holding the set of requested data elements, the identification comprises computing the memory positions of the set of requested data elements using the memory indices among the requested index line and the address of the start data field in the read request;
perform a number of read operations on the data array, that is equal to the number of identified data lines, to retrieve the number of identified data lines from the data array, wherein each identified data line includes at least one of the set of requested data elements, and includes unwanted data elements that are not requested in the read request;
store the retrieved data lines in the buffer;
discard the unwanted data elements among the retrieved data lines from the buffer, such that the set of requested data elements remain in the buffer;
assemble the remaining requested data elements in the buffer into an assembled data line;
store the assembled data line including the requested data elements in the cache; and
send the assembled data line to the hardware processor, wherein the memory processor is configured to send the assembled data line from the cache to the hardware processor in response to a subsequent read request for the requested data elements by the hardware processor.

2. The computing system according to claim 1 , wherein the memory processor is configured to:
assemble the data elements by sorting the data elements in accordance with the memory indices of the requested index line of the index line address; and
discard the unwanted data elements by discarding data elements of the data lines that do not correspond to the memory indices of the requested index line of the index line address.

3. The computing system according to claim 1 , wherein the hardware processor is further configured to:
send one or more mask bits to the memory processor, wherein the one or more mask bits indicate that data elements corresponding to the one or more mask bits shall be skipped.

4. The computing system according to claim 1 , wherein the index line address in the read request is a first index line address, and the hardware processor is further configured to:
send a write request comprising a set of data elements, a second index line address and the start address to the memory processor;
wherein the memory processor is further configured to:
retrieve memory indices of the second index line address from the memory;
disassemble the data elements; and
write the disassembled data elements into the data array.

5. The computing system according to claim 4 , wherein the memory processor is configured to write the data elements by:
sending a write burst request to the memory; and
write one or more data lines as data bursts to the memory.

6. The computing system according to claim 5 , wherein the memory processor is configured to disassemble the data elements by:
sorting the data elements in accordance with the memory indices of an index line of the second index line address into one or more data lines.

7. The computing system according to claim 1 , wherein a write request and the read request have an instruction format comprising:
operation code bits indicating whether a read operation or a write operation shall be performed;
index mask bits indicating which data elements corresponding to an index row shall be read and written respectively;
index address bits indicating the index line address; and
start address bits indicating the start address.

8. A computer implemented method for operating a computing system, the method comprising:
receiving, by a memory processor, a read request from a hardware processor, wherein the read request is for a set of data elements stored in a memory, and wherein:
the memory comprises a data array and an index array;
the data array comprises at least one data line, each data line comprises a set of data fields, each data field is configured to hold a data element, and each data field is indexed by a memory index;
the index array comprises at least one index line, each index line comprises a set of memory indices indicating memory positions of data elements in the data array with respect to a start data field of the data array, wherein the start data field is one particular data field in the data array;
in a burst mode of operation, data elements in the data array are accessed on a line-by-line basis, such that a read operation results in reading a complete data line, and a write operation results in writing to a complete data line;
the read request includes an index line address and an address of the start data field of the data array, the index line address is an address of a requested index line among the index array;
the requested index line includes memory indices of data fields that hold requested data elements among the data array;

using, by the memory processor, the memory indices among the requested index line to identify a number of data lines that include the data fields holding the requested data element, the identification comprises computing the memory positions of the set of requested data elements using the memory indices among the requested index line and the address of the start data field in the read request;
performing, by the memory processor, a number of read operations on the data array, that is equal to the number of identified data lines, to retrieve the number of identified data lines from the data array, wherein each identified data line includes at least one of the requested data elements, and includes unwanted data elements that are not requested in the read request;
storing, by the memory processor, the retrieved data lines in a buffer of the memory processor;
discarding, by the memory processor, the unwanted data elements among the retrieved data lines from the buffer, such that the requested data elements remain in the buffer;
assembling, by the memory processor, the remaining requested data elements in the buffer into an assembled data line;
storing, by the memory processor, the assembled data line includin

Assignees

• IBM

Inventors

• Giefers Heiner
• Polig Raphael
• Van Lunteren Jan

Classifications

• G06F9/30038

  using a mask · CPC title

• G06F9/30036

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06F12/0879

  Burst mode · CPC title

• G06F9/345 Primary

  of multiple operands or results {(addressing multiple banks G06F12/06)} · CPC title

• G11C5/02

  Disposition of storage elements, e.g. in the form of a matrix array · CPC title