Hybrid CAM assisted deflate decompression accelerator

Patent metadata

Field	Value
Publication number	US-9306596-B2
Application number	US-201414317698-A
Country	US
Kind code	B2
Filing date	Jun 27, 2014
Priority date	Jun 27, 2014
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

Disclosed is an integrated circuit including a memory device including a first portion and a second portion. The first portion is a first type of content addressable memory (CAM) with a first set of cells and the second portion is a second type of CAM with a second set of cells. The first set of cells is smaller than the second set of cells. The integrated circuit further includes a decompression accelerator coupled to the memory device, the decompression accelerator to generate a plurality of length codes. Each of the plurality of length codes include at least one bit. The plurality of length codes are generated using a symbol received from an encoded data stream that includes a plurality of symbols. The decompression accelerator further to store the plurality of length codes in the first portion of the memory device in an order according to their respective number of bits.

First claim

What is claimed is:

1. An integrated circuit comprising:
a memory device comprising a first portion and a second portion, wherein the first portion is a first type of content addressable memory (CAM) with a first set of cells and the second portion is a second type of CAM with a second set of cells, wherein the first set of cells is smaller than the second set of cells;
a decompression accelerator coupled to the memory device, the decompression accelerator to:
generate a plurality of length codes, wherein each of the plurality of length codes comprise at least one bit, wherein the plurality of length codes are generated using a symbol received from an encoded data stream that includes a plurality of symbols; and
store the plurality of length codes in the first portion of the memory device in an order according to their respective number of bits; and

a core coupled to the decompression accelerator, the core to decode the plurality of length codes for a decoded data stream.

2. The integrated circuit of claim 1 , wherein the memory device comprises a 15-bit array, wherein the first portion comprises a 9-bit array and wherein the second portion comprises a 6-bit array.

3. The integrated circuit of claim 1 , wherein the first portion of the memory device comprises an array of a first length, wherein the second portion of the memory device comprises an array of a second length, wherein a total length of the memory device is equal to at least a sum of the first length and the second length.

4. The integrated circuit of claim 3 , wherein when decoding the plurality of length codes, the core is to:
identify a block of data of the encoded data stream;
cause a lookup operation for the block of data in the memory device; and
receive a decoded block of data from a register file that is associated with the memory device.

5. The integrated circuit of claim 4 , wherein the first portion of the memory device comprises a plurality of partitions, wherein the register file is divided into a number of parts equal to the number of the plurality of partitions, wherein each partition is to store one of the parts of the register file, wherein when causing the lookup operation for the block of data in the memory device, the core is to cause a lookup operation for the block of data in each of the plurality of partitions of the first portion of the memory device, wherein a match for the lookup operation corresponds to a row in a one of the parts of the register file.

6. The integrated circuit of claim 1 , wherein the first set of cells is smaller in physical size than the second set of cells.

7. The integrated circuit of claim 1 , wherein the first set of cells has a smaller data capacity than the second set of cells.

8. The integrated circuit of claim 7 , wherein the first set of first cells comprises a plurality of first cells and the second set of cells comprises a plurality of second cells, wherein each of the plurality of first cells is a binary cell and wherein each of the plurality of second cells is a ternary cell.

9. The integrated circuit of claim 1 , wherein the first portion of the memory device comprises a register file to store decompressed data associated with the encoded data stream.

10. The integrated circuit of claim 1 , wherein the memory device is to store a shift value to indicate a shift amount value, wherein the shift value is determined using a number of bits in a code length and a number of bits that were consumed by the decompression accelerator.

11. A method comprising:
receiving, by a processing device, a first data block of a compressed data stream, the first data block having an associated first header;
parsing the first header of the first data block to identify a first code length of the first data block;
generating, by the processing device, a first address for the first data block;
storing the first data block in a content addressable memory (CAM) in association with the first address, the CAM comprising a first portion that comprises a first set of cells and a second portion that comprises a second set of cells, wherein the first set of cells is smaller than the second set of cells;
receiving a second data block of the compressed data stream, the second data block having an associated second header;
generating, by the processing device, a second address for the second data block based on a second code length in the second header; and
storing the second data block in the first portion of the CAM in an order with respect to the first code length and the second code length.

12. The method of claim 11 , wherein the first code length and the second code length are stored in the first portion of the CAM in an increasing order of code length.

13. The method of claim 11 , wherein the first code length is stored in association with a first counter having a first counter length, wherein the second code length is stored in association with a second counter having a second counter length.

14. The method of claim 11 further comprising:
receiving a third data block of the compressed data stream, the third data block having an associated third header;
generating, by the processing device, a third address for the third data block based on a third code length in the third header; and
storing the third data block in the first portion of the CAM in an order with respect to the first code length, the second code length, and the third code length.

15. The method of claim 11 further comprising:
receiving a symbol associated with the data stream;
performing a lookup operation for a match to the symbol in the first portion of the CAM;
upon identifying a match to the symbol in the first portion of the CAM, identifying a corresponding row in a register file; and
providing data from the corresponding row in the register file in an output data stream.

16. The method of claim 11 further comprising:
receiving a symbol associated with the data stream;
performing a lookup operation for a match to the symbol in the first portion of the CAM; and
when the lookup operation does not yield a match to the symbol in the first portion of the CAM, performing the lookup operation in the second portion of the CAM.

17. A non-transitory machine-readable storage medium including data that, when accessed by a processing device, cause the processing device to perform operations comprising:
receiving, by the processing device, a first data block of a compressed data stream, the first data block having an associated first header;
parsing the first header of the first data block to identify a first code length of the first data block;
generating, by the processing device, a first address for the first data block;
storing the first data block in a content addressable memory (CAM) in association with the first address, the CAM comprising a first portion that comprises a first set of cells and a second portion that comprises a second set of cells, wherein the first set of cells are smaller than the second set of cells;
receiving a second data block of the compressed data stream, the second data block having an associated second header;
generating, by the processing device, a second address for the second data block based on a second code length in the second header; and
storing the second data block in the first portion of the CAM in an order with respect to the first code length and the second code length.

18. The non-transitory machine-readable storage medium of claim 17 , wherein the first code length and the second code length are stored in the first porti

Assignees

• Satpathy Sudhir K
• Mathew Sanu K
• Gopal Vinodh
• Krishnamurthy Ram K
• Intel Corp

Inventors

• Satpathy Sudhir K
• Mathew Sanu K
• Gopal Vinodh
• Krishnamurthy Ram K

Classifications

• G11C15/04 Primary

  using semiconductor elements · CPC title

• G06F12/0646 Primary

  Configuration or reconfiguration · CPC title

• G06F2212/401

  Compressed data · CPC title

• H03M7/425 Primary

  for the decoding process only · CPC title

• G11C15/00

  Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores · CPC title