Merging techniques in data compression accelerator of a data processing unit

Patent metadata

Field	Value
Publication number	US-2020162584-A1
Application number	US-201816195644-A
Country	US
Kind code	A1
Filing date	Nov 19, 2018
Priority date	Nov 19, 2018
Publication date	May 21, 2020
Grant date	—

Abstract

A highly programmable device, referred to generally as a data processing unit, having multiple processing units for processing streams of information, such as network packets or storage packets, is described. The data processing unit includes one or more specialized hardware accelerators configured to perform acceleration for various data-processing functions. This disclosure describes a hardware-based programmable data compression accelerator for the data processing unit including a pipeline for performing string substitution. The disclosed string substitution pipeline, referred to herein as a “search block,” is configured to perform string search and replacement functions to compress an input data stream. In some examples, the search block is a part of a compression process performed by the data compression accelerator. The search block may support single and multi-thread processing, and multiple levels of compression effort. In order to achieve high-throughput, the search block processes multiple input bytes per clock cycle per thread.

First claim

What is claimed is:

1 . A method comprising:
receiving, by a path block of a search engine of a processing device, an indication of whether at least one match occurs between a current byte string beginning at a current byte position in an input data stream and one or more history addresses of one or more previous occurrences of byte strings; when the at least one match occurs for the current byte string, determining, by the path block, a best match for the current byte position; selecting, by the path block, an output for the current byte position, wherein the output for the current byte position comprises one of a reference to the best match for the current byte string or a literal of original data at the current byte position; and transmitting the selected output for the current byte position in an output data stream.

2 . The method of claim 1 , wherein determining the best match for the current byte position comprises:
determining a longest match for the current byte position from among forward matches from the current byte position, backward matches from subsequent byte positions, and carry forward matches from previous byte positions; and if two or more matches are tied for the longest match, selecting the one of the two or more matches that has the closest byte position to the current byte position as the best match for the current byte position.

3 . The method of claim 2 , further comprising determining, by the path block, the carry forward matches, including:
identifying at least one match from the previous byte positions that overlaps the current byte position; and determining a truncated length of the at least one match at the current byte position.

4 . The method of claim 1 , wherein determining the best match for the current byte position comprises extending match lengths at previous byte positions in the input data stream based on lengths of backward matches from the current byte position.

5 . The method of claim 1 , wherein determining the best match for the current byte position comprises:
applying a best match from among previous byte positions in the input data stream to the current byte position with a truncated match length; and comparing the truncated match length at the current byte position to lengths of forward matches from the current byte position to determine a longest match for the current byte position.

6 . The method of claim 1 , wherein determining the best match for the current byte position comprises determining a best match for each of one or more byte positions within a window of the input data stream that includes the current byte position, and wherein selecting the output for the current byte position comprises one of:
if the best match for the current byte position is a best match among the byte positions within the window, selecting as the output a length-distance pair identifying the best match for the current byte position; or if the best match for the current byte position is not the best match among the byte positions within the window, selecting as the output the literal of the original data at the current byte position.

7 . The method of claim 6 , wherein the window comprises a moving window, and wherein determining the best match for each of the byte positions within the moving window comprises:
updating match lengths of matches for the current byte position based on matches for any of the other byte positions within a current window that affect the matches for the current byte position; and determining the best match for the current byte position from the updated match lengths of the matches for the current byte position within the current window.

8 . The method of claim 1 , wherein the output for the current byte position comprises a reference to an initial match for the current byte string, the method further comprising:
determining that the initial match for the current byte string beginning at the current byte position reaches a maximum match length without detecting an end of the initial match; determining whether an additional match occurs beginning one byte subsequent to the maximum match length of the initial match and having a same relative distance as the initial match; when the additional match occurs, extending the maximum match length of the initial match beginning at the current byte position with the length of the additional match; and selecting as the output a length-distance pair identifying the extended match length beginning at the current byte position.

9 . The method of claim 8 , wherein determining that the initial match reaches the maximum match length without detecting the end of the initial match comprises:
determining that the initial match has a length equal to the maximum match length; and determining that the initial match does not include either a match byte defined as a first non-matching byte after the initial match or a previous byte defined as a last byte of the initial match.

10 . The method of claim 8 , wherein the history addresses comprise byte positions of the previous occurrences of byte strings stored in a history buffer configured to include multiple memory banks, and wherein the maximum match length depends on a size of the memory banks within the history buffer.

11 . The method of claim 1 , wherein the output data stream comprises a byte aligned format including:
a header configured to hold a number of bits of header data; and a payload configured to hold the same number of bytes of compressed data, wherein one or more bits of the header data within the header indicate whether a literal or a length-distance pair is held at one or more corresponding bytes of the compressed data within the payload.

12 . The method of claim 1 , wherein transmitting the selected output for the current byte position in the output data stream comprises:
sending, by the path block and to a transmitter block of the search engine, the selected output for the current byte position; and packing, by the transmitter block, the selected output for the current byte position into the output data stream.

13 . A processing device comprising:
a memory; and a path block of a search engine of the processing device, the path block configured to:
receive an indication of whether at least one match occurs between a current byte string beginning at a current byte position in an input data stream and one or more history addresses of one or more previous occurrences of byte strings;
when the at least one match occurs for the current byte string, determine a best match for the current byte position;
select an output for the current byte position, wherein the output for the current byte position comprises one of a reference to the best match for the current byte string or a literal of original data at the current byte position; and
transmit the selected output for the current byte position in an output data stream.

14 . The device of claim 13 , wherein, to determine the best match for the current byte position, the path block is configured to:
determine a longest match for the current byte position from among forward matches from the current byte position, backward matches from subsequent byte positions, and carry forward matches from previous byte positions; and if two or more matches are tied for the longest match, select the one of the two or more matches that has the closest byte position to the current byte position as the best match for the current byte position.

15 . The device of claim 14 , wherein the path block is configured to determine the carry forward matches, including:
identifying a

Assignees

• Fungible Inc

Inventors

• Beckman Edward David
• Billa Satyanarayana Lakshmipathi
• Goyal Rajan

Classifications

• G06F16/9532

  Query formulation · CPC title

• H04L47/27

  Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L69/04 Primary

  Protocols for data compression, e.g. ROHC · CPC title

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title