Method and apparatus for high bandwidth dictionary compression technique using set update dictionary update policy

Patent metadata

Field	Value
Publication number	US-9514085-B2
Application number	US-201113638132-A
Country	US
Kind code	B2
Filing date	Oct 1, 2011
Priority date	Oct 1, 2011
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

Method, apparatus, and systems employing novel dictionary entry replacement 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.

First claim

What is claimed is:

1. A method comprising:
implementing a dictionary-based compression scheme using a dictionary having a plurality of dictionary entries;
configuring a compressor to compress blocks of original data, each block comprising a plurality of portions of original data, each portion having a respective data index,
implementing a dictionary entry replacement policy under which each data index is associated with a corresponding replacement set of dictionary entries,
for each of the plurality of portions of original data in a block,
performing a dictionary match operation on multiple replacement sets of dictionary entries in parallel to determine whether a match or non-matching condition exists; and
for a non-matching condition,
selecting a dictionary entry to replace from among the replacement set of dictionary entries associated with the data index for the portion of original data,

wherein the dictionary comprises a first dictionary implemented at a transmitter that sends compressed data encoded using the first dictionary to a receiver, the method further comprising maintaining dictionary entries in a second dictionary at the receiver such that the dictionary entries in the first and second dictionaries are synchronized.

2. The method of claim 1 , further comprising implementing one of a FIFO (First-in, First-out) or Least Recently Used (LRU) replacement policy to select a dictionary entry from among the replacement set of dictionary entries to replace.

3. The method of claim 1 , wherein the dictionary replacement policy comprises an N-way set associative replacement policy.

4. The method of claim 1 , further comprising employing the dictionary entry replacement policy to replace dictionary entries corresponding to non-matching conditions for a plurality of portions of data in parallel.

5. The method of claim 1 , further comprising employing the dictionary entry replacement policy to replace dictionary entries corresponding to non-matching conditions for all of the plurality of portions of data in a block in parallel.

6. A method comprising:
implementing a dictionary-based compression scheme using a dictionary having a plurality of dictionary entries;
configuring a compressor to compress blocks of original data, each block comprising a plurality of portions of original data, each portion having a respective data index,
implementing a dictionary entry replacement policy under which each data index is associated with a corresponding replacement set of dictionary entries,
for each of the plurality of portions of original data in a block,
performing a dictionary match operation on multiple replacement sets of dictionary entries in parallel to determine whether a match or non-matching condition exists; and
for a non-matching condition,

selecting a dictionary entry to replace from among the replacement set of dictionary entries associated with the data index for the portion of original data,
wherein the dictionary replacement policy comprises an N-way set associative replacement policy, and wherein each portion of original data has a data index j, the number of portions of data in a block is N, and the number of dictionary entries in the dictionary is k, and the dictionary replacement policy defines the replacement set for a given data index to include dictionary indexes having values defined by the equation,
U i=0 k/N−1 j+N*i.

7. A method comprising:
implementing a dictionary-based compression scheme using a dictionary having a plurality of dictionary entries;
configuring a compressor to compress blocks of original data, each block comprising a plurality of portions of original data, each portion having a respective data index,
implementing a dictionary entry replacement policy under which each data index is associated with a corresponding replacement set of dictionary entries,
for each of the plurality of portions of original data in a block,
performing a dictionary match operation on multiple replacement sets of dictionary entries in parallel to determine whether a match or non-matching condition exists; and
for a non-matching condition,

selecting a dictionary entry to replace from among the replacement set of dictionary entries associated with the data index for the portion of original data,
wherein the dictionary replacement policy comprises an N-way set associative replacement policy, and
wherein the N-way set associate replacement policy is implemented such that dictionary entry replacements corresponding to any combination of non-matching conditions for all of the plurality of portions of original data in a block are processed in parallel.

8. The method of claim 7 , wherein the dictionary comprises a first dictionary implemented at a transmitter that sends compressed data encoded using the first dictionary to a receiver, the method further comprising maintaining dictionary entries in a second dictionary at the receiver such that the dictionary entries in the first and second dictionaries are synchronized.

9. A method comprising:
implementing a dictionary-based compression scheme using a dictionary having a plurality of dictionary entries;
configuring a compressor to compress blocks of original data, each block comprising a plurality of portions of original data, each portion having a respective data index,
implementing a dictionary entry replacement policy under which each data index is associated with a corresponding replacement set of dictionary entries,
for each of the plurality of portions of original data in a block,
performing a dictionary match operation on multiple replacement sets of dictionary entries in parallel to determine whether a match or non-matching condition exists; and
for a non-matching condition,

selecting a dictionary entry to replace from among the replacement set of dictionary entries associated with the data index for the portion of original data, wherein each portion of data comprises a double word having four bytes of data, and each dictionary entry comprises four bytes of data, and a matching condition exists if two or more bytes of at least one dictionary entry match corresponding bytes in a double word.

10. A device, comprising:
a compressor having a dictionary with a plurality of replaceable entries and having logic configured to,
compress blocks of original data into compressed data via use of a dictionary-based compression/decompression scheme employing the dictionary, each block of original data comprising a plurality of words of data, each word of data having a respective data index;
implement a dictionary entry replacement policy under which each data index is associated with a corresponding set of replacement dictionary entries;
for each of the plurality of words of data in a block,
performing a dictionary match operation on multiple replacement sets of dictionary entries in parallel to determine whether a match or non-matching condition exists; and
for a dictionary miss,
select a dictionary entry to replace from among the set of replacement dictionary entries associated with the data index of the word of data corresponding to the dictionary miss,

wherein the compressor logic is further configured to perform dictionary entry replacement operations for multiple words of data in parallel,
wherein the words of data comprise four byte double words.

11. The device of claim 10 , wherein the dictionary replacement policy comprises an N-way set associative replacement policy.

12. A device, comprising:
a compressor having a dictionary with a plurality of replaceable entries and having logic configured to,
compress blocks of original data into compressed data via u

Assignees

• Pardo Ilan
• Soffair Ido Y
• Reif Dror
• Das Sharma Debendra
• Pethe Akshay G
• 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

• G06F13/42 Primary

  Bus transfer protocol, e.g. handshake; Synchronisation · CPC title

• H03M7/00

  Conversion of a code where information is represented by a given sequence or number of digits to a code where the same {, similar or subset of} information is represented by a different sequence or number of digits · CPC title

• G06F13/00

  Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units (interface circuits for specific input/output devices G06F3/00 {; multiprogram control therefor  G06F9/46}; multiprocessor systems  G06F15/16 ) · CPC title