Compression format for high bandwidth dictionary compression

Patent metadata

Field	Value
Publication number	US-9306598-B2
Application number	US-201414193427-A
Country	US
Kind code	B2
Filing date	Feb 28, 2014
Priority date	Oct 1, 2011
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

Method, apparatus, and systems employing dictionary-based high-bandwidth lossless compression. A pair of dictionaries having entries that are synchronized and encoded to support compression and decompression operations are implemented via logic at a compressor and decompressor. The compressor/decompressor logic operatives in a cooperative manner, including implementing the same dictionary update schemes, resulting in the data in the respective dictionaries being synchronized. The dictionaries are also configured with replaceable entries, and replacement policies are implemented based on matching bytes of data within sets of data being transferred over the link. Various schemes are disclosed for entry replacement, as well as a delayed dictionary update technique. The techniques support line-speed compression and decompression using parallel operations resulting in substantially no latency overhead.

First claim

What is claimed is:

1. An apparatus comprising:
a transmitter, configured to be communicatively coupled to a receiver of a peer apparatus via a bi-directional link;
a receiver, configured to be communicatively coupled to a transmitter of the peer apparatus via the bi-directional,
a compressor implemented in the transmitter, configured to generate first compressed data from first original data to be transmitted over the bi-directional to the receiver of the peer apparatus using a dictionary-based compression/decompression scheme under which the first original data are processed as blocks of multiple data values that are encoded in parallel to generate compressed blocks comprising a fixed format portion and a variable format portion; and
a decompressor implemented in the receiver, configured to decompress second compressed data received from the transmitter of the peer apparatus using the dictionary-based compression/decompression scheme to extract second original data by decompressing the compressed data in parallel, wherein the second compressed data was generated using a dictionary-based compression/decompression scheme under which the second original data are processed as blocks of multiple data values that are encoded in parallel to generate compressed blocks comprising a fixed format portion and a variable format portion.

2. The apparatus of claim 1 , wherein the bi-directional employs a physical layer, data link layer, and transaction layer, and wherein compression and decompression operations are performed in a layer above the transaction layer.

3. The apparatus of claim 1 , wherein each of the compressor on the apparatus and the decompressor on the peer apparatus maintain respective copies of a dictionary used for compression and decompression operations having replaceable entries that are updated in a synchronized manner.

4. The apparatus of claim 3 , wherein the compressor on the apparatus is configured to replace a dictionary entry on a dictionary miss with a corresponding portion of first original data and generate compressed data encoded in a manner that identifies the dictionary entry that was replaced and the corresponding portion of first original data.

5. The apparatus of claim 4 , wherein the decompressor on the peer apparatus is configured to decode the first compressed data and replace the same dictionary entry in its copy of the dictionary with the corresponding portion of first original data, and wherein each of the compressor on the apparatus and decompressor on the peer apparatus are configured to replace multiple dictionary entries in parallel.

6. The apparatus of claim 4 , wherein the compressor on the peer apparatus is configured to replace a dictionary entry on a dictionary miss with a corresponding portion of second original data and generate compressed data encoded in a manner that identifies the dictionary entry that was replaced and the corresponding portion of second original data, and wherein the decompressor is configured to decode the second compressed data and replace the same dictionary entry in its copy of the dictionary with the corresponding portion of second original data.

7. The apparatus of claim 6 , wherein the decompressor is configured to replace an entire set of replaceable entries in its dictionary or a subset of multiple entries of the replaceable entries in its dictionary at one time.

8. The apparatus of claim 1 , wherein the bi-directional comprises a PCI Express link.

9. The apparatus of claim 1 , wherein the first original data comprises a plurality of double words that are encoded in parallel into a compressed block comprising the first compressed data.

10. The apparatus of claim 1 , wherein the second original data comprises a plurality of double words that are encoded in parallel into a compressed block comprising the second compressed data, and wherein the decompressor is configured to extract the plurality of double words in parallel.

11. A method, comprising:
receiving compressed data comprising original data compressed into the compressed data and encoded in accordance with a dictionary-based compression/decompression scheme; and
decompressing the compressed data to extract the original data,
wherein the original data comprises a plurality of blocks containing a plurality of words and compression and decompression of the original data is implemented by performing parallel operations on the plurality of words on a block-wise basis to generate compressed blocks comprising a fixed format portion and a variable format portion.

12. The method of claim 10 , wherein the compressed data is received from a transmitter coupled to the receiver via a serial link and the transmitter maintains a first dictionary used in conjunction with compression operations performed at the transmitter to generate the compressed data, the method further comprising:
maintaining a second dictionary at the receiver, the second dictionary used in conjunction with decompression operations;
receiving encoded data over the serial link from the transmitter at the receiver containing information identifying entries in the first dictionary that have been replaced; and
replacing the same plurality of entries in the second dictionary.

13. The method of claim 12 , further comprising replacing entries in the first and second dictionaries in a synchronized manner.

14. The method of claim 12 , further comprising delaying replacement of entries in the second dictionary under which one of an entire set of replaceable entries in the second dictionary or a subset of multiple entries of the replaceable entries in the second dictionary are replaced at one time.

15. The method of claim 11 , further comprising:
receiving the compressed data over a serial link having a line rate; and
performing the decompressing operations in real time to support an average transfer rate of the original data at the line rate.

16. The method of claim 15 , wherein the serial link comprises a PCI Express link.

17. A device, comprising:
a decompressor having a dictionary with a plurality of replaceable entries and having logic configured to decompress data in an input stream of compressed data to obtain original data via use of a dictionary-based compression/decompression scheme employing the dictionary, wherein the original data comprises a plurality of double words that are compressed in parallel on a block-wise basis to generate compressed blocks of data comprising a fixed format portion and a variable format portion, and the decompressor employs dictionary entries to generate an output stream of data comprising the original data.

18. The device of claim 17 , wherein the compressed data is encoded to identify a dictionary match or miss condition for each of the plurality of double words.

19. The device of claim 17 , wherein the plurality of words comprise eight 32-bit double words.

20. The device of claim 17 , wherein the decompressor is configured to:
decode the stream of compressed data to detect data associated with dictionary match conditions and dictionary miss conditions as identified by corresponding dictionary match indicia and dictionary miss indicia;
in response to detecting dictionary match indicia,
extract data in the stream of compressed data associated with the dictionary match indicia and employ the extracted data as a lookup into the dictionary to identify a matching dictionary entry and add data in the matching dictionary entry to the output stream of original data; and
in response to detecting dictiona

Assignees

• Intel Corp

Inventors

• Pardo Ilan
• Soffair Ido Y
• Reif Dror
• Das Sharma Debendra
• Pethe Akshay G

Classifications

• H03M7/3088

  employing the use of a dictionary, e.g. LZ78 · CPC title

• H03M7/6023 Primary

  Parallelization · CPC title