Scalable High-Bandwidth Architecture for Lossless Compression

• US 20160285473A1
• Filed: 06/12/2015
• Published: 09/29/2016
• Est. Priority Date: 03/27/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kim, Joo-Young, Fowers, Jeremy Halden, Hauck, Scott A., Burger, Douglas C.
• Granted Patent: US 9,590,655 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H03M 7/6011 Encoder aspects
• CPC Class Codes: H03M 7/6023 Parallelization
• CPC Class Codes: H03M 7/6029 Pipelining

Abstract

A method of lossless data compression includes receiving a set of parallel data strings; determining compression hash values for each of the parallel data strings; determining bit matches among portions of each of the parallel data strings based, at least in part, on the compression hash values; selecting among literals and the bit matches for each of the parallel data strings; and applying Huffman encoding to the selected literals or the selected bit matches.

Claims

1. A system comprising:

hardware logic circuitry to perform data compression by;

generating a multiple hash table that comprises at least a first hash table that includes latest positions for hash indexes and a second hash table that includes second latest positions for hash indices;

reading hash values from the first hash table and the second hash table simultaneously at a first clock rate; and

routing the read hash values to respective banks that operate at a second clock rate that is different from the first clock rate.

2. The system of claim 1, further comprising:

a hardware accelerator portion that includes one or more Field-Programmable Gate Arrays (FPGAs).

4. The system of claim 1, further comprising an arbiter to discard conflicts among the requested hash values routed to the respective banks.

5. The system of claim 1, further comprising crossbar switches within the respective banks.

6. The system of claim 1, wherein

the second clock rate is an integer multiple of the first clock rate.

7. The system of claim 1, wherein generating the multiple hash table is based, at least in part, on Lempel-Ziv (LZ77) compression.

21. The system of claim 1, wherein the second clock rate is at least twice the first clock rate.

3. (canceled)

8. A computing device comprising:

a hardware data compression pipeline accelerator including;

a hash calculation module to receive a set of parallel data strings and to determine hash indexes for each of the parallel data strings;

a hash table update module to read latest positions for each hash index and update the read latest positions with current string positions;

a string match module to determine matches among portions of each of the parallel data strings based, at least in part, on the read latest positions; and

a match selection module to select among literals and the matches for each of the parallel data strings.

9. The computing device of claim 8, further comprising a bit-packing module to apply Huffman encoding to the selected literals or the selected matches.

10. The computing device of claim 8, further comprising a bit-packing module to apply arithmetic coding to the selected literals or the selected matches.

11. The computing device of claim 8, wherein the hardware data compression pipeline accelerator comprises one or more Field-Programmable Gate Arrays (FPGAs).

12. The computing device of claim 8, wherein the hardware data compression pipeline accelerator comprises multiple Field-Programmable Gate Arrays (FPGAs) configured in parallel with one another.

13. The computing device of claim 8, wherein the hardware data compression pipeline accelerator is incorporated in a data center and configured to losslessly compress data received by the data center.

14. The computing device of claim 13, wherein the data received by the data center comprises network data traffic via the Internet.

15. The computing device of claim 13, wherein the data is received by the data center at network speeds.

16. A computing device comprising:

a memory device to store data; and

a hardware data compression pipeline including;

a string match module to determine bit matches among positions of each of a set of parallel data strings of the data; and

a match selection module to choose among the bit matches that will be used to encode the data.

17. The computing device of claim 16, wherein the match selection module is configured to process windows of consecutive strings simultaneously.

18. The computing device of claim 17, wherein the match selection module comprises hardware logic to receive an incoming match from a previous window that overlaps positions in a current window.

19. The computing device of claim 17, wherein the match selection module comprises hardware logic to truncate matches within a particular window based, at least in part, on the incoming match from the previous window.

20. The computing device of claim 17, wherein the match selection module comprises hardware logic to complete the match selection process only after receiving the incoming match from the previous window.