US 2013/0086339 A1 · METHOD AND APPARATUS FOR HIGH BANDWIDTH DICTIONARY COMPRESSION TECHNIQUE USING DELAYED DICTIONARY UPDATE

Abstract

Method, apparatus, and systems employing novel delayed dictionary update schemes for 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.

Claims19

Dependent claims

A method comprising:

implementing a dictionary-based compression/decompression scheme using a first dictionary at a compressor and a second dictionary at a decompressor, each of the first and second dictionaries having a plurality of replaceable dictionary entries having data values comprising a first set of dictionary entries;
employing the first set of dictionary entries in the first and second dictionaries to compress and decompress data in a data stream using dictionary-based data compression and data decompression operations;
generating dictionary replacement entries in response to dictionary misses during data compression operations and storing the dictionary replacement entries apart from the first sets of dictionary entries;
in response to initiation of a delayed dictionary update, updating entries in the first and second dictionaries with corresponding dictionary replacement entries to produce an updated set of dictionary entries in each of the first and second dictionaries;
and
employing the updated set of dictionary entries in the first and second dictionaries to compress and decompress data in the data stream.

3 more elements

A system, comprising:

a compressor having a first dictionary with first dictionary entries including a plurality of replaceable entries and having logic configured to,
employ the first dictionary entries in dictionary-based data compression operations to convert a data stream into compressed data;
generate first dictionary replacement entries in response to dictionary misses during data compression operations, store the first dictionary replacement entries apart from the first dictionary entries, and encode data relating to dictionary misses in the compressed data;
and
in response to initiation of a delayed dictionary update, update replaceable entries in the first dictionary with corresponding first dictionary replacement entries to produce an updated set of first dictionary entries in the first dictionary;
and
a decompressor having a second dictionary with second dictionary entries including a plurality of replaceable entries and having logic configured to,
decompress compressed data generated by the compressor and extract data relating to dictionary misses encoded in the compressed data;
generate second dictionary replacement entries based on the data relating to dictionary misses and store the second dictionary replacement entries apart from the second dictionary entries;
and
in response to initiation of the delayed dictionary update, update replaceable entries in the second dictionary with corresponding second dictionary replacement entries to produce an updated set of second dictionary entries in the second dictionary.

8 more elements

Dependencies are inferred from the claim text.

Method and apparatus for high bandwidth dictionary compression technique using delayed dictionary update

Life of this patent

Method and apparatus for high bandwidth dictionary compression technique using delayed dictionary update

Life of this patent

Abstract

Claims19