Efficient matrix data format applicable for artificial neural network
Many computing systems process data organized in a matrix format. For example, artificial neural networks (ANNs) perform numerous computations on data organized into matrices using conventional matrix arithmetic operations. One such operation, which is commonly performed, is the transpose operation. Additionally, many such systems need to process many matrices and/or matrices that are large in size. For sparse matrices that hold few significant values and many values that can be ignored, transmitting and processing all the values in such matrices is wasteful. Thus, techniques are introduced for storing a sparse matrix in a compressed format that allows for a matrix transpose operation to be performed on the compressed matrix without having to first decompress the compressed matrix. By utilizing the introduced techniques, more matrix operations can be performed than conventional systems.
1. A method of transposing a compressed sparse matrix, comprising:
loading said compressed sparse matrix as a plurality of compressed sparse submatrices; and
generating a transpose of said compressed sparse matrix without decompressing said compressed sparse matrix;
wherein said generating includes:
transposing said compressed sparse submatrices using pattern numbers of said compressed sparse submatrices, wherein each different pattern of said compressed sparse submatrices is assigned with a different pattern number; and
switching positions of some of said compressed sparse submatrices.
2. The method of claim 1 , wherein said transposing includes using a transpose information for each of said compressed sparse submatrices from a look up table (LUT).
3. The method of claim 2 , wherein each of said pattern numbers serves as an index of said LUT for each of said compressed sparse submatrices.
4. The method of claim 3 , wherein said LUT includes locations of non-zero elements in said each different pattern, and locations of non-zero elements in a transpose of said each different pattern.
5. The method of claim 1 , further comprising generating said compressed sparse matrix by applying to a matrix a sparsity restriction that restricts a number of non-zero elements in at least one dimension of said matrix and compressing said matrix along one of said at least one dimension.
6. The method of claim 1 , further comprising decompressing said compressed sparse matrix without decompressing said compressed sparse matrix while said compressed sparse matrix is stored in a destination storage, said decompressing includes:
loading metadata of said compressed sparse submatrices, said metadata being said pattern numbers of said compressed sparse submatrices;
reading locations of non-zero elements in said patterns of said compressed sparse submatrices in a logical space from a LUT by using said metadata as indices of said LUT; and
writing values of said non-zero elements to said destination storage according to said locations.
7. The method of claim 1 , wherein each of said pattern numbers is metadata of each of said compressed sparse matrices, and said metadata is smaller than data representing locations of non-zero elements in each of said patterns.
8. The method of claim 1 , further comprising loading each of said pattern numbers as metadata of each of said compressed sparse submatrices.
9. The method of claim 1 , wherein each of said compressed sparse submatrices is a 4×4 matrix having two non-zero elements in a row and a column.
10. The method of claim 1 , wherein said generating includes replicating some non-zero elements of said compressed sparse submatrices, and wherein said some non-zero elements are accessed during said transposing.
11. A processor for transposing a compressed sparse matrix, comprising:
an arithmetic logic unit (ALU) configured to load said compressed sparse matrix as a plurality of compressed sparse submatrices, and generate a transpose of said compressed sparse matrix without decompressing said compressed sparse matrix;
wherein said ALU is configured to generate said transpose of said compressed sparse matrix by transposing said compressed sparse submatrices using pattern numbers of said compressed sparse submatrices, wherein each different pattern of said compressed sparse submatrices is assigned with a different pattern number, and switching locations of some of said compressed sparse submatrices.
12. The processor of claim 11 , wherein said transposing includes using a transpose information for each of said compressed sparse submatrices in a look up table (LUT).
13. The processor of claim 12 , wherein each of said pattern numbers serves as an index of said LUT for each of said compressed sparse submatrices.
14. The processor of claim 13 , wherein said LUT includes locations of non-zero elements in said each different pattern, and locations of non-zero elements in a transpose of said each different pattern.
15. The processor of claim 11 , wherein said ALU is further configured to generate said compressed sparse matrix by applying to a matrix a sparsity restriction that restricts a number of non-zero elements in at least one dimension of said matrix and compressing said matrix along one of said at least one dimension.
16. The processor of claim 11 , wherein said ALU is configured to decompress said compressed sparse matrix without decompressing said compressed sparse matrix before said compressed sparse matrix is stored in a destination storage by:
loading metadata of said compressed sparse submatrices, said metadata being said pattern numbers of said compressed sparse submatrices;
reading locations of non-zero elements in said patterns of said compressed sparse submatrices in a logical space from a LUT by using said metadata as indices of said LUT; and
writing values of said non-zero elements to said destination storage according to said locations.
17. The processor of claim 11 , wherein each of said pattern numbers is metadata of each of said compressed sparse matrices, and said metadata is smaller than data representing locations of non-zero elements in each of said patterns.
18. The processor of claim 11 , further comprising a memory management unit (MMU) configured to load each of said pattern numbers as metadata of each of said compressed sparse submatrices.
19. The processor of claim 11 , wherein each of said compressed sparse submatrices is a 4×4 matrix having two non-zero elements in a row and a column.
20. The processor of claim 11 , wherein some non-zero elements of said compressed sparse submatrices are replicated, and said some non-zero elements are accessed during said transposing.