Heterogeneous hardware accelerator architecture for processing sparse matrix data with skewed non-zero distributions

Patent metadata

Field	Value
Publication number	US-10180928-B2
Application number	US-201615396513-A
Country	US
Kind code	B2
Filing date	Dec 31, 2016
Priority date	Dec 31, 2016
Publication date	Jan 15, 2019
Grant date	Jan 15, 2019

Abstract

Heterogeneous hardware accelerator architectures for processing sparse matrix data having skewed non-zero distributions are described. An accelerator includes sparse tiles to access data from a first memory over a high bandwidth interface and very/hyper sparse tiles to randomly access data from a second memory over a low-latency interface. The accelerator determines that one or more computational tasks involving a matrix are to be performed, partitions the matrix into a first plurality of blocks that includes one or more sparse sections of the matrix, and a second plurality of blocks that includes sections of the matrix that are very- or hyper-sparse. The accelerator causes the sparse tile(s) to perform one or more matrix operations for the computational task(s) using the first plurality of blocks and further causes the very/hyper sparse tile(s) to perform the one or more matrix operations for the computational task(s) using the second plurality of blocks.

First claim

What is claimed is:

1. A method in a hardware processor for processing sparse matrix data from a matrix having a skewed non-zero distribution comprising:
determining, by the hardware processor, that one or more computational tasks involving the matrix are to be performed;
partitioning, by the hardware processor, the matrix into a first plurality of blocks and a second plurality of blocks, wherein the first plurality of blocks includes one or more sections of the matrix that are sparse, and wherein the second plurality of blocks includes another one or more sections of the matrix that are very- or hyper-sparse; and
causing, by the hardware processor, one or more sparse tiles of the hardware processor to perform one or more matrix operations for the one or more computational tasks using the first plurality of blocks and further causing one or more very/hyper sparse tiles of the hardware processor to perform the one or more matrix operations for the one or more computational tasks using the second plurality of blocks, wherein the one or more sparse tiles access ones of the first plurality of blocks over a first interface that has a higher bandwidth than that of a second interface, and wherein the one or more very/hyper sparse tiles access ones of the second plurality of blocks over the second interface that has a lower latency than that of the first interface.

2. The method of claim 1 , further comprising:
after determining that the one or more computational tasks involving the matrix are to be performed, determining, by the hardware processor, that the matrix is sparse and has a skewed non-zero distribution, wherein said partitioning of the matrix into the first plurality of blocks and the second plurality of blocks occurs responsive to determining that the matrix is sparse and does have the skewed non-zero distribution.

3. The method of claim 1 , wherein said partitioning comprises:
determining a number of rows or columns of the matrix having only zero values.

4. The method of claim 3 , wherein said partitioning comprises:
determining whether the number satisfies a threshold criteria.

5. The method of claim 1 , further comprising converting a format of each of the second plurality of blocks into a doubly-compressed format.

6. The method of claim 1 , wherein said causing the one or more sparse tiles to perform the one or more matrix operations comprises storing the first plurality of blocks in a first memory unit, the first memory unit to stream data of the first plurality of blocks to the one or more sparse tiles over the first interface.

7. The method of claim 6 , wherein said causing the one or more very/hyper sparse tiles to perform the one or more matrix operations comprises storing the second plurality of blocks in a second memory unit, the second memory unit to provide data of the second plurality of blocks to the one or more very/hyper sparse tiles responsive to random access requests from the one or more very/hyper sparse tiles over the second interface.

8. A hardware processor comprising:
one or more sparse tiles comprising a first plurality of processing units to access data from a first memory unit over a high bandwidth interface;
one or more very/hyper sparse tiles comprising a second plurality of processing units to randomly access data from a second memory unit over a low-latency interface; and
a control unit to:
determine that one or more computational tasks involving a matrix are to be performed;
partition the matrix into a first plurality of blocks and a second plurality of blocks, wherein the first plurality of blocks includes one or more sections of the matrix that are sparse, and wherein the second plurality of blocks includes another one or more sections of the matrix that are very- or hyper-sparse; and
cause the one or more sparse tiles to perform one or more matrix operations for the one or more computational tasks using the first plurality of blocks and further cause the one or more very/hyper sparse tiles to perform the one or more matrix operations for the one or more computational tasks using the second plurality of blocks.

9. The hardware processor of claim 8 , wherein the control unit is further to determine whether the matrix is sparse and has a skewed non-zero distribution, wherein the control unit is to perform the partition responsive to a determination that the matrix is sparse and does have the skewed non-zero distribution.

10. The hardware processor of claim 8 , wherein, to partition the matrix into the first plurality of blocks and the second plurality of blocks, the control unit is to:
determine a number of rows or columns of the matrix having only zero values.

11. The hardware processor of claim 10 , wherein, to partition the matrix into the first plurality of blocks and the second plurality of blocks, the control unit is further to:
determine whether the number satisfies a threshold criteria.

12. The hardware processor of claim 8 , wherein the control unit is further to convert a format of each of the second plurality of blocks into a doubly-compressed format.

13. The hardware processor claim 8 , wherein, to cause the one or more sparse tiles to perform the one or more matrix operations, the control unit is to cause the first plurality of blocks to be stored in a first memory unit, the first memory unit to stream data of the first plurality of blocks to the one or more sparse tiles over a high-bandwidth interface.

14. The hardware processor of claim 13 , wherein, to cause the one or more very/hyper sparse tiles to perform the one or more matrix operations, the control unit is to store the second plurality of blocks in a second memory unit, the second memory unit to provide data of the second plurality of blocks to the one or more very/hyper sparse tiles responsive to random access requests from the one or more very/hyper sparse tiles over a low-latency interface.

15. A system comprising:
a first memory unit;
a second memory unit;
one or more sparse tiles comprising a first plurality of processing units to access data from the first memory unit over a high bandwidth interface;
one or more very/hyper sparse tiles comprising a second plurality of processing units to randomly access data from the second memory unit over a low-latency interface; and
a control unit to:
determine that one or more computational tasks involving a matrix are to be performed;
partition the matrix into a first plurality of blocks and a second plurality of blocks, wherein the first plurality of blocks includes one or more sections of the matrix that are sparse, and wherein the second plurality of blocks includes another one or more sections of the matrix that are very- or hyper-sparse; and
cause the one or more sparse tiles to perform one or more matrix operations for the one or more computational tasks using the first plurality of blocks and further cause the one or more very/hyper sparse tiles to perform the one or more matrix operations for the one or more computational tasks using the second plurality of blocks.

16. The system of claim 15 , wherein the control unit is further to determine whether the matrix is sparse and has a skewed non-zero distribution, wherein the control unit is to perform the partition responsive to a determination that the matrix is sparse and does have the skewed non-zero distribution.

17. The system of claim 15 , wherein, to partition the matrix into the first plurality of blocks and the second plurality of blocks, the control unit is to:
determine a number of rows or columns of the matrix having only zero values.

Assignees

• Intel Corp

Inventors

• Nurvitadhi Eriko
• Marr Deborah

Classifications

• G06F9/3001

  Arithmetic instructions · 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

• 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

• G06F9/30036

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

• G06F9/30038

  using a mask · CPC title