Fully pipelined hardware engine design for fast and efficient inline lossless data compression

• US 10,454,498 B1
• Filed: 10/18/2018
• Issued: 10/22/2019
• Est. Priority Date: 10/18/2018
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Mao, Yuhong
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US16/164,663
• Time in Patent Office: 369 Days
• Field of Search: 341 51- 71
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/6023 Parallelization
• CPC Class Codes: H03M 7/6029 Pipelining

Abstract

A hardware compression system is provided. The system includes a hardware pipeline having a plurality of stages arranged to receive pre-compression data into a data buffer, populate a first hash table and a second hash table, supply the pre-compression data to a hash lookup module to access the first hash table and the second hash table in parallel, supply a string match module with results from the hash lookup module so that the string match module compares pre-compression data from multiple locations in the data buffer in parallel, supply a match merge module with results from the string match module so that the match merge module generates literals and metadata for compression data, and supply an output encoding module with results from the match merge module so that the output encoding module encodes the compression data.

Claims

1. A hardware compression system, comprising:

a hardware pipeline having a plurality of stages arranged to;

receive pre-compression data into a data buffer;

populate a first hash table and a second hash table;

supply the pre-compression data to a hash lookup module to access the first hash table and the second hash table in parallel;

supply a string match module with results from the hash lookup module so that the string match module compares pre-compression data from multiple locations in the data buffer in parallel;

supply a match merge module with results from the string match module so that the match merge module generates literals and metadata for compression data; and

supply an output encoding module with results from the match merge module so that the output encoding module encodes the compression data.

2. The hardware compression system of claim 1, wherein:

the first hash table comprises a first plurality of blocks of RAM (random access memory) arranged for parallel access of a plurality of hash table entries;

the second hash table comprises a second plurality of blocks of RAM arranged for parallel access of a further plurality of hash table entries; and

the data buffer comprises a third plurality of blocks of RAM arranged for parallel access of pre-compression data for the string match module.

3. The hardware compression system of claim 1, wherein the output encoding module comprises:

a literal FIFO (first in first out buffer);

a metadata FIFO; and

formatting logic arranged to output the compression data based on literals from the literal FIFO and metadata from the metadata FIFO.

4. The hardware compression system of claim 1, further comprising a plurality of such hardware pipelines.

5. The hardware compression system of claim 1, wherein:

the hash lookup module is to form hashes of a first length of pre-compression data for the first hash table and hashes of a second, greater length of the pre-compression data for the second hash table; and

each hash table entry in the first hash table and the second hash table comprises a portion of a hash result and a position of the pre-compression data.

6. The hardware compression system of claim 1, wherein the hash lookup module is arranged to form a hash result from a sequence number and a plurality of bytes of the pre-compression data and look up a hash entry in the first hash table or the second hash table based on the hash result, for a plurality of hashes in parallel and for the first hash table and the second hash table in parallel.

7. The hardware compression system of claim 1, wherein the merge match module is arranged to determine in a first stage a longest string match of a plurality of matches from the string match module for a local optimal merge, and perform in a second stage a global optimal merge to form an outstanding match based on tracking matches of a previous cycle.

8. The hardware compression system of claim 1, wherein:

each stage of the hardware pipeline has fixed latency, resulting in fixed latency of the hardware pipeline; and

the string match module is arranged to search to a fixed maximum length of string, for the fixed latency of the stage comprising the string match module.

9. The hardware compression system of claim 1, wherein:

for each subsequent data block of the pre-compression data, a sequence number is to seed hash keys for the first hash table and the second hash table, to eliminate hash table re-initialization between different data blocks.

10. A hardware pipeline data compression system, comprising:

a data buffer;

a first hash table, implemented across a first plurality of blocks of RAM (random access memory) arranged for parallel access of a plurality of hash table entries;

a second hash table, implemented across a second plurality of blocks of RAM arranged for parallel access of a further plurality of hash table entries;

a string match module comprising a plurality of comparators and counters each to compare and count a number of consecutive byte matches of pre-compression data of one location and pre-compression data of another location, for a plurality of comparisons in parallel;

a hash lookup module, implemented in hardware logic, to perform multiple hash operations in parallel on the pre-compression data, perform the parallel access of the plurality of hash table entries in the first hash table, and perform the parallel access of the further plurality of hash table entries in the second hash table; and

a hardware pipeline arranged to receive the pre-compression data into the data buffer, populate the first hash table and the second hash table, supply the hash lookup module and the string match module, and generate compression data based on results from the string match module.

11. The hardware pipeline data compression system of claim 10, wherein the data buffer comprises a third plurality of blocks of RAM arranged for parallel access of pre-compression data for the comparators of the string match module.

12. The hardware pipeline data compression system of claim 10, further comprising:

a literal FIFO (first in first out buffer);

a metadata FIFO; and

a match merge module, implemented in hardware logic, arranged to determine an optimal longest string match according to the plurality of comparators and counters of the string match module, write literals according to the optimal longest string match into the literal FIFO, and write metadata according to the optimal longest string match into the metadata FIFO, wherein the compression data comprises a formatted version of the literals and the metadata.

13. The hardware pipeline data compression system of claim 10, further comprising a plurality of such hardware pipelines to operate in parallel.

14. The hardware pipeline data compression system of claim 10, wherein:

the first hash table is to receive hashes of a first length of pre-compression data and store or look up the plurality of hash table entries each comprising a portion of a hash result and a position of pre-compression data; and

the second hash table is to receive hashes of a second, greater length of pre-compression data and store or look up the further plurality of hash table entries each comprising a portion of a further hash result and a further position of pre-compression data.

15. The hardware pipeline data compression system of claim 10, wherein the hash lookup module is arranged to operate a hash function on a sequence number and a plurality of bytes of the pre-compression data, and look up a hash entry in the first hash table or the second hash table based on a hash result, for a plurality of hashes in parallel and for a plurality of accesses to the first hash table and a plurality of accesses to the second hash table in parallel.

16. The hardware pipeline data compression system of claim 10, further comprising:

a match merge module, implemented in hardware logic, arranged to determine in a first stage a longest string match of a plurality of matches from the string match module for a local optimal merge, and perform in a second stage a global optimal merge to form an outstanding match based on tracking matches of a previous cycle of the hardware pipeline.

17. A method of data compression, practiced by a hardware compression system, the method comprising:

writing pre-compression data into a data buffer;

populating a first hash table and a second hash table;

supplying the pre-compression data to a hash lookup module to form hash results and make a plurality of accesses to the first hash table and a plurality of accesses to the second hash table, in parallel;

supplying a string match module with results from the hash lookup module so that the string match module compares pre-compression data from multiple locations in the data buffer in parallel;

generating, in a match merge module, literals and metadata for compression data based on results from the string match module; and

encoding the compression data according to a data compression format, based on the literals and the metadata from the match merge module.

18. The method of claim 17, further comprising:

performing actions of the hardware compression system in each of a plurality of hardware pipelines, in parallel.

19. The method of claim 17, further comprising:

forming a hash result from a sequence number and a first amount of the pre-compression data, for each of the plurality of accesses to the first hash table, in parallel; and

forming a hash result from the sequence number and a second, greater amount of the pre-compression data, for each of the plurality of accesses to the second hash table, in parallel.

20. The method of claim 17, wherein the populating each of the first hash table and the second hash table comprises:

forming a hash result from a hash table specific amount of the pre-compression data;

using a first portion of the hash result as a pointer to an entry in a hash table; and

writing a second portion of the hash result and a pointer to the pre-compression data as the entry in the hash table.