Tiled compressed sparse matrix format
Approaches in accordance with various embodiments provide for the processing of sparse matrices for mathematical and programmatic operations. In particular, various embodiments utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities. These empty tiles can be ignored, and only the tiles with non-zero entries processed, which reduces resource and time requirements for the processing. An indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix. The tiles can be processed in parallel and the results accumulated to generate a matrix product. The matrix product can then be passed to the next step in a process or operation, such as to a next layer in a deep neural network.
1 . A computer-implemented method, comprising: causing one or more processors to:
access, from at least one first L1 cache of one or more L1 caches of the one or more processors, one or more matrix operands of one or more matrix operations to be performed by the one or more processors, wherein the one or more matrix operands comprise one or more indices to indicate one or more locations, within at least one other L1 cache of the one or more L1, of one or more separately compressed multi-element portions of the one or more matrix operands comprising one or more non-zero values; and
perform the one or more matrix operations on the one or more matrix operands indicated by the one or more indices.
2 . The computer-implemented method of claim 1 , wherein the one or more indices indicate one or more tiled format matrices generated from one or more sparse matrices of data, and further comprising:
generating the one or more tiled format matrices in a compressed sparse row (CSR) format or a compressed sparse column (CSC) format.
3 . The computer-implemented method of claim 1 , wherein the one or more indices indicate one or more tiled format matrices generated from one or more sparse matrices of data, and further comprising:
generating, using a respective tile identifier and a positional offset in a tile, tile-specific indices for non-zero value elements.
4 . The computer-implemented method of claim 1 , wherein the one or more indices indicate one or more tiled format matrices generated from one or more sparse matrices of data, and further comprising:
multiplying the one or more tiled format matrices having removed zero value data by a dense matrix of data in parallel using a plurality of streaming multiprocessors (SMs) of a second processing unit, wherein the second processing unit is a graphics processing unit (GPU).
5 . The computer-implemented method of claim 4 , wherein the one or more indices indicate one or more tiled format matrices generated from one or more sparse matrices of data, and further comprising:
storing data for the one or more tiled format matrices to a Level 1 (LI) cache for the plurality of streaming multiprocessors.
6 . A system, comprising:
one or more processors; and
memory including instructions that, when executed by the one or more processors,
cause the system to:
access, from at least one first L1 cache of one or more L1 caches of the one or more processors, one or more matrix operands of one or more matrix operations to be performed by the one or more processors, wherein the one or more matrix operands comprise one or more indices to indicate one or more locations, within at least one other L1 cache of the one or more L1 caches, of one or more separately compressed multi-element portions of the one or more matrix operands comprising one or more non-zero values; and
perform the one or more matrix operations on the one or more matrix operands indicated by the one or more indices.
7 . The system of claim 6 , wherein the one or more indices indicate one or more tiled format matrices from one or more sparse matrices of data, and wherein the instructions when executed further cause the system to:
multiply the one or more sparse matrices of data by a dense matrix of data, the one or more sparse matrices of data having a higher ratio of zero-value elements to non-zero elements than the dense matrix of data.
8 . The system of claim 7 , wherein the instructions when executed further cause the system to:
multiply the one or more tiled format matrices having removed zero value data by a dense matrix of data; and
accumulate results from multiplying the one or more tiled format matrices to generate a product of the one or more sparse matrices of data and the dense matrix of data.
9 . The system of claim 8 , wherein the instructions when executed further cause the system to:
multiply the one or more tiled format matrices having the removed zero value data by the dense matrix of data in parallel using a plurality of streaming multiprocessors (SMs) of a graphics processing unit GPU.
10 . The system of claim 7 , wherein the instructions when executed further cause the system to:
format the one or more tiled format matrices, having removed zero value data, in a compressed sparse row (CSR) format or a compressed sparse column (CSC) format according to a nested matrix format.
11 . One or more processors, comprising:
one or more circuits to cause the one or more processors to:
access, from at least one first L1 cache of one or more L1 caches of the one or more processors, one or more matrix operands of one or more matrix operations to be performed by the one or more processors, wherein the one or more matrix operands comprise one or more indices to indicate one or more locations, within at least one other L1 cache of the one or more L1 caches, of one or more separately compressed multi-element portions of the one or more matrix operands comprising one or more non-zero values; and
perform the one or more matrix operations on the one or more matrix operands indicated by the one or more indices.
12 . The one or more processors of claim 11 , wherein the one or more indices indicate one or more tiled format matrices from one or more sparse matrices of data, and wherein the one or more circuits are configured to multiply the one or more sparse matrices of data by a dense matrix of data, the one or more sparse matrices of data having a higher ratio of zero-value elements to non-zero elements than the dense matrix of data.
13 . The one or more processors of claim 12 , wherein the one or more circuits are configured to:
multiply the one or more tiled format matrices by a dense matrix of data; and accumulate results from multiplying the one or more tiled format matrices to generate a product of the one or more sparse matrices of data and the dense matrix of data.
14 . The one or more processors of claim 13 , wherein the multiplying of the one or more tiled format matrices by the dense matrix of data is performed in parallel using a plurality of streaming multiprocessors (SMs) of a graphics processing unit (GPU).
15 . The one or more processors of claim 12 , wherein the one or more circuits are configured to:
obtain the one or more sparse matrices of data and a second matrix of data for a first layer of a deep neural network; and
pass a product of the one or more sparse matrices of data and the second matrix of data to a second layer of the deep neural network.
16 . The one or more processors of claim 15 , wherein the deep neural network is a generative adversarial network (GAN), a convolutional neural network (CNN), or a recurrent neural network (RNN).
17 . The one or more processors of claim 12 , wherein the one or more circuits are configured to generate the one or more tiled format matrices in a compressed sparse row (CSR) format or a compressed sparse column (CSC) format.
18 . The one or more processors of claim 17 , wherein the one or more tiled format matrices, having removed zero value data, are matrices in the CSR or CSC format according to a nested matrix format.
19 . The one or more processors of claim 12 , wherein the one or more circuits are configured to generate, using a respective tile identifier and a positional offset in tile, tile-specific indices for non-zero elements in the one or more tiled format matrices.
20 . The one or more processors of claim 12 , wherein the one or more circuits are configured to determine a single aspect ratio to use for the one or more tiled format matrices using a density of the one or more sparse matrices of data and a size of a cache to store the one or more tiled format matrices.