Scalable High-Bandwidth Architecture for Lossless Compression

Patent metadata

Field	Value
Publication number	US-2016285473-A1
Application number	US-201514738778-A
Country	US
Kind code	A1
Filing date	Jun 12, 2015
Priority date	Mar 27, 2015
Publication date	Sep 29, 2016
Grant date	—

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.

First claim

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).

3 . (canceled)

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.

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.

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

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kim Joo-Young
• Burger Douglas C
• Fowers Jeremy Halden
• Hauck Scott A

Classifications

• H03M7/6023

  Parallelization · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/6029

  Pipelining · CPC title

• H03M7/40

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

• H03M7/3086 Primary

  employing a sliding window, e.g. LZ77 · CPC title