Method and apparatus for compressing and decompressing sparse data sets
Embodiments of the present disclosure include a digital circuit and method for multi-stage compression. Digital data values are compressed using a multi-stage compression algorithm and stored in a memory. A decompression circuit receives the values and performs a partial decompression. The partially compressed values are provided to a processor, which performs the final decompression. In one embodiment, a vector of N length compressed values are decompressed using a first bit mask into two N length sets having non-zero values. The two N length sets are further decompressed using two M length bit masks into M length sparse vectors, each having non-zero values.
1. A digital circuit comprising:
memory, the memory storing data comprising a plurality of digital values, wherein N non-zero digital values are stored in a block, where N is a first integer, the N non-zero digital values being associated with a first bit mask specifying positions of the N non-zero digital values;
a decompression circuit to receive the N non-zero digital values and the first bit mask and produce two N length sets of digital values from the N non-zero digital values, wherein positions of the non-zero digital values in each of the two N length sets of digital values are set based on the first bit mask; and
a processor to receive the two N length sets of digital values and two second bit masks, and process the two N length sets of digital values using the two second bit masks.
2. The circuit of claim 1 , wherein the processor further decompresses the two N length sets of digital values using the two second bit masks into two M length sets of digital values, where M is a second integer greater than N.
3. The circuit of claim 1 , wherein the data stored in the memory comprising the plurality of digital values is compressed using a multi-stage compression algorithm.
4. The circuit of claim 1 , wherein M divided by N is a power of 2.
5. The circuit of claim 1 , wherein the first bit mask is at least of length 2*N and the two N length sets of digital values each comprise N/2 non-zero digital values.
6. The circuit of claim 5 , wherein the two M length bit masks are stored in said memory with the N non-zero digital values and the bit mask of length 2*N.
7. The circuit of claim 5 , wherein the first bit mask comprises 2*N bits.
8. The circuit of claim 1 , wherein the two second bit masks each comprise M bits.
9. The circuit of claim 1 , wherein the N non-zero digital values are stored in the memory as pairs of values.
10. The circuit of claim 9 , wherein the two second bit masks each comprise M/2 bits.
11. A method of decompressing data comprising:
receiving, from a memory, N non-zero digital values and a first bit mask specifying positions of the N non-zero digital values, where N is a first integer, and wherein the N non-zero digital values are stored in a block associated with the first bit mask;
decompressing the N non-zero digital values using the first bit mask to produce two N length sets of digital values each comprising non-zero digital values from the N non-zero digital values, wherein positions of the non-zero digital values in each of the two N length sets of digital values are set based on the first bit mask; and
receiving the two N length sets of digital values and two second bit masks in a processor, where M is a second integer greater than N, and processing, by the processor, the two N length sets of digital values using the second bits masks.
12. The method of claim 11 , wherein the processor further decompresses the two N length sets of digital values using the two second bit masks into two M length sets of digital values, where M is a second integer greater than N.
13. The method of claim 11 , wherein the N non-zero digital values are stored in the memory as pairs of values.
14. The method of claim 11 , wherein the data stored in the memory comprising the plurality of digital values is compressed using a multi-stage compression algorithm.
15. The method of claim 11 , wherein the two M length bit masks are stored in said memory with the N non-zero digital values and the bit mask.
16. The method of claim 11 , wherein M divided by N is a power of 2.
17. The method of claim 11 , wherein the first bit mask comprises 2*N bits.
18. The method of claim 11 , wherein the two second bit masks each comprise M bits.
19. The method of claim 11 , wherein the N non-zero digital values are stored in the memory as pairs of values.
20. A non-transitory machine-readable medium storing a program executable by a computer, the program comprising sets of instructions for:
receiving, from a memory, N non-zero digital values and a first bit mask specifying positions of the N non-zero digital values, where N is a first integer, and wherein the N non-zero digital values are stored in a block associated with the first bit mask;
decompressing the N non-zero digital values using the first bit mask to produce two N length sets of digital values each comprising non-zero digital values from the N non-zero digital values, wherein positions of the non-zero digital values in each of the two N length sets of digital values are set based on the first bit mask; and
receiving the two N length sets of digital values and two second bit masks in a processor, where M is a second integer greater than N, and processing, by the processor, the two N length sets of digital values using the second bits masks.