Methods and apparatus for matrix and vector storage and operations
Methods and apparatus for matrix and vector storage and operations are disclosed. Exemplary embodiments include a multicore processor, where each core includes processing hardware, local weights, global weights, working memory, and accumulator. Exemplary embodiments compress sparse neural network data structures based on actual, non-null, connectivity (rather than all possible connections). In some variants, the compression and reduction in complexity is sized to fit within the memory footprint and processing capabilities of a core. The exemplary compression schemes represent sparse matrices with links to compressed column data structures, where each compressed column data structure only stores non-null entries to optimize column-based lookups of non-null entries. Similarly, sparse vector addressing skips nulled entries when performing vector-specific non-null multiply-accumulate operations.
1 . A neural network processing apparatus, comprising:
processing hardware and a memory; and
a non-transitory computer-readable medium comprising one or more instructions which when executed by the processing hardware, causes the processing hardware to:
generate a first compressed representation of a sparse vector the first compressed representation comprising a plurality of non-null values and at least one address offset to a next non-null value of the plurality of non-null values;
obtain a second compressed representation of a second sparse data structure, the second compressed representation comprises a plurality of non-null data structures, each of the plurality of non-null data structures comprising a same number of values, the same number is greater than one;
determine the plurality of non-null values and a plurality of addresses associated with the plurality of non-null values from the first compressed representation;
for each non-null address of the plurality of addresses of the first compressed representation:
read a parameter column address table for a corresponding parameter column address;
read a parameter column from a parameter memory of the second sparse data structure at the corresponding parameter column address;
decode non-null data and addresses from the parameter column; and
for each of the non-null data and the addresses compute a product of the non-null data and a corresponding non-null value of the plurality of non-null values to calculate a plurality of intermediate element-wise products of the sparse vector and the second sparse data structure; and
calculate a result of the sparse vector and the second sparse data structure based on the plurality of intermediate element-wise products.
2 . The neural network processing apparatus of claim 1 , where:
the first compressed representation comprises a plurality of words of data, and
each word of the plurality of words of data comprises a control bit and a plurality of value bits, the control bit indicating that the plurality of value bits comprise a non-null value or the at least one address offset.
3 . The neural network processing apparatus of claim 1 , where the second sparse data structure exceeds a parameter memory dimension associated with the memory of the neural network processing apparatus; and
where the second compressed representation fits within the parameter memory dimension.
4 . The neural network processing apparatus of claim 1 , where the second sparse data structure comprises a sparse matrix.
5 . The neural network processing apparatus of claim 4 , where the second compressed representation comprises a pointer to a compressed column of the sparse matrix, where the compressed column comprises one or more non-null data structures of the plurality of non-null data structures.
6 . The neural network processing apparatus of claim 5 , where the compressed column of the sparse matrix does not include null values.
7 . The neural network processing apparatus of claim 6 , where a memory address of the compressed column comprises a base address and an offset.
8 . The neural network processing apparatus of claim 1 , where the second sparse data structure comprises a plurality of columns characterized by a fixed size and where each column of the plurality of columns is identified by a column offset.
9 . The neural network processing apparatus of claim 1 , where at least one dimension of the first compressed representation of the sparse vector is selected based on access efficiency.
10 . The neural network processing apparatus of claim 1 , where at least one dimension of the first compressed representation of the sparse vector is selected based on neural network training.
11 . The neural network processing apparatus of claim 1 , where at least one non-null data structure of the plurality of non-null data structures comprises a zero value.
12 . A neural network processing apparatus, comprising:
processing hardware;
a working memory;
a parameter memory; and
a non-transitory computer-readable medium comprising one or more instructions which when executed by the processing hardware, causes the processing hardware to:
generate a first compressed representation of a sparse vector the first compressed representation comprising a plurality of words of data, each word of the plurality of words of data comprises a control bit and a plurality of value bits, the control bit indicating that the plurality of value bits comprise a non-null value or at least one address offset to a next non-null value;
obtain a second compressed representation of a second sparse data structure; and
for each non-null address of the first compressed representation:
read a parameter column address table for a corresponding parameter column address;
read a parameter column from the parameter memory of the second sparse data structure at the corresponding parameter column address;
decode non-null data and addresses from the parameter column; and
for each of the non-null data and the addresses compute a product of the non-null data and a corresponding non-null value of the plurality of words of data.
13 . The neural network processing apparatus of claim 12 , where the one or more instructions further cause the processing hardware to accumulate non-null results in the working memory.
14 . The neural network processing apparatus of claim 13 , where the working memory stores a last known state of a plurality of intermediate results and where unrelated operations can access the working memory concurrently.
15 . The neural network processing apparatus of claim 13 , where the second sparse data structure comprises a sparse matrix and the non-null results are a plurality of intermediate results of element-wise multiplications between non-null elements of the sparse vector and the sparse matrix.
16 . A method of performing a matrix operation, comprising:
generating a first representation of a vector, the first representation comprising a plurality of words of data, each word of the plurality of words of data comprises a control bit and a plurality of value bits, the control bit indicating that the plurality of value bits comprise a non-null value or at least one address offset to a next non-null value;
obtaining a second representation of a matrix; and
for each non-null address of the first representation:
reading a parameter column address table for a corresponding parameter column address;
reading a parameter column from a parameter memory of the second representation of the matrix at the corresponding parameter column address;
decoding non-null data and addresses from the parameter column; and
for each of the non-null data and the addresses computing a product of the non-null data and a corresponding non-null value of the plurality of words of data.
17 . The method of claim 16 , where the second representation comprises a plurality of consecutive non-null elements of the matrix.
18 . The method of claim 16 , further comprising calculating a result of the vector and the matrix based on the product for each of the non-null data and the addresses, where the result comprises a sparse global vector for a global neural network state of a multicore neural network.
19 . The method of claim 16 , further comprising calculating a result of the vector and the matrix based on the product for each of the non-null data and the addresses, where the result comprises a dense local vector for a local neural network state of a core of a multicore neural network.