Matrix processing apparatus

Patent metadata

Field	Value
Publication number	US-9898441-B2
Application number	US-201615016486-A
Country	US
Kind code	B2
Filing date	Feb 5, 2016
Priority date	Feb 5, 2016
Publication date	Feb 20, 2018
Grant date	Feb 20, 2018

Abstract

Methods, systems, and apparatus, including a system for transforming sparse elements into a dense matrix. The system includes a data fetch unit that includes a plurality of processors, the data fetch unit configured to determine, based on identifications of the subset of the particular sparse elements, a processor designation for fetching the subset of the particular sparse elements. The system includes a concatenation unit configured to generate an output dense matrix based on a transformation that is applied to the sparse elements fetched by the data fetch unit.

First claim

What is claimed is:

1. A system comprising a hardware sparse-dense transform unit for transforming sparse elements into a dense matrix, the system comprising:
a sparse element access unit in the sparse-dense transform unit and for accessing multiple sparse elements of a dense matrix, wherein the sparse element access unit includes:
a request identification unit configured to:
receive, over a node network, a request for particular sparse elements stored in one or more data shards;
determine that the sparse element access unit in which the request identification unit is located is assigned to handle a subset of the particular sparse elements; and
in response to determining that the sparse element access unit in which the request identification unit is located is assigned to handle the subset of the particular sparse elements, generate an indication for accessing the subset of the particular sparse elements;

at least one processor for fetching, based on the indication, one or more sparse elements of the subset of the particular sparse elements; and
a concatenation unit configured to:
generate an output dense matrix based on a transformation that is applied to at least the one or more sparse elements.

2. The system of claim 1 , wherein determining that the sparse element access unit in which the request identification unit is located is assigned to handle the subset of the particular sparse elements comprises determining that the sparse element access unit in which the request identification unit is located is assigned to handle a subset of the particular sparse elements based on a lookup table.

3. The system of claim 1 , the sparse element access unit further comprising:
a sparse reduce unit configured to:
receive a first matrix that includes a first sparse element from the at least one processor, the first matrix having a first dimension; and
generate a second matrix that includes the first sparse element, the second matrix having a second dimension that is smaller than the first dimension,

wherein the concatenation unit is further configured to:
receive the second matrix,
wherein generating the output dense matrix further comprises generating the output dense matrix based on the second matrix.

4. The system of claim 1 , wherein the concatenation unit is configured to:
receive a first sparse element at a first point of time;
receive a second sparse element at a second, different, point of time; and
determine an order of the first sparse element and the second sparse element for the output dense matrix,
wherein generating the output dense matrix further comprises generating the output dense matrix based on the order of the first sparse element and the second sparse element.

5. The system of claim 1 , the sparse element access unit further comprising:
a compress/decompress unit configured to:
compress the output dense matrix to generate a compressed output dense matrix; and
provide the compressed output dense matrix to a node network.

6. The system of claim 5 ,
wherein the concatenation unit is further configured to receive a first dense matrix representing a dense matrix sent over a node network, and
wherein generating the output dense matrix further comprises generating the output dense matrix based on the first dense matrix, a first sparse element, and a second sparse element.

7. The system of claim 6 , wherein the compress/decompress unit is configured to decompress a compressed first dense matrix to generate the first dense matrix.

8. The system of claim 1 , wherein one or more sparse elements of the particular sparse elements are multi-dimensional matrices, and wherein the output dense matrix is a vector.

9. A method for transforming sparse elements into a dense matrix, comprising:
receiving, by a sparse element access unit and from an external source, a request for particular sparse elements stored in one or more data shards, where the sparse element access unit is located in a sparse-dense transform unit;
determining, by a request identification unit located in the sparse element access unit and based on the request, that the sparse element access unit in which the request identification unit is located is assigned to handle a subset of the particular sparse elements;
in response to determining that the sparse element access unit in which the request identification unit is located is assigned to handle the subset of the particular sparse elements, generating, by the request identification unit, an indication for accessing the subset of the particular sparse elements;
fetching, based on the indication and by at least one processor of the sparse element access unit, one or more sparse elements of the subset of the particular sparse elements; and
generating, by a concatenation unit located in the sparse element access unit, an output dense matrix based on a transformation that is applied to at least the one or more sparse elements.

10. The method of claim 9 , further comprising:
receiving, by a sparse reduce unit, a first matrix that includes a first sparse element from the at least one processor, the first matrix having a first dimension;
generating, by the sparse reduce unit, a second matrix that includes the first sparse element, the second matrix having a second dimension that is smaller than the first dimension; and
receiving, by the concatenation unit, the second matrix,
wherein generating the output dense matrix further comprises generating the output dense matrix based on the second matrix.

11. The method of claim 9 , wherein generating the output dense matrix further comprises:
receiving a first sparse element at a first point of time;
receiving a second sparse element at a second, different, point of time;
determining an order of the first sparse element and the second sparse element for the output dense matrix; and
generating the output dense matrix based on the order of the first sparse element and the second sparse element.

12. The method of claim 9 , further comprising:
compressing the output dense matrix to generate a compressed output dense matrix; and
providing the compressed output dense matrix to a node network.

13. The method of claim 9 , wherein generating the output dense matrix further comprises:
receiving a first dense matrix representing a dense matrix sent over a node network; and
generating the output dense matrix based on the first dense matrix, a first sparse element, and a second sparse element.

14. The method of claim 9 , wherein determining that the sparse element access unit is assigned to handle the subset of the particular sparse elements comprises determining that the sparse element access unit is assigned to handle a subset of the particular sparse elements based on a lookup table.

15. A system comprising a hardware sparse-dense transform unit for transforming sparse elements to a dense matrix, the system comprising:
one or more processors configured to send a request for an output matrix based on particular sparse elements that are stored in one or more data shards;
a sparse element access unit in the sparse-dense transform unit and for accessing the particular sparse elements that are stored in the one or more data shards, the sparse element access unit comprising:
a request identification unit configured to:
receive, over a node network, the request for the output matrix based on the particular sparse elements that are stored in one or more data shards;
determine that the sparse element access unit in which the request identification unit is located is assigned to handle a subset of the particular sparse el

Assignees

• Google Inc
• Google Llc

Inventors

• Narayanaswami Ravi
• Nagarajan Rahul
• Woo Dong Hyuk
• Leary Christopher Daniel

Classifications

• H03M7/3059

  Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression · CPC title

• H03M7/3062

  Compressive sampling or sensing · CPC title

• H03M7/30

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• G06F17/14

  Fourier, Walsh or analogous domain transformations {, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms (for correlation function computation G06F17/156; spectrum analysers G01R23/16)} · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title