Hardware-accelerated lossless data compression

• US 8,694,703 B2
• Filed: 06/09/2010
• Issued: 04/08/2014
• Est. Priority Date: 06/09/2010
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Hans, Madhsudan, Ko, Kung-Ling
• Primary Examiner(s): Wong, Titus
• Application Number:
  US12/796,812
• Publication Number:
  US 20110307659A1
• Time in Patent Office: 1,399 Days
• Field of Search: 710/65
• US Class Current: 710/65
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

Systems for hardware-accelerated lossless data compression are described. At least some embodiments include data compression apparatus that includes a plurality of hash memories each associated with a different lane of a plurality of lanes (each lane including data bytes of a data unit being received by the compression apparatus), an array including array elements each including a plurality of validity bits (each validity bit within an array element corresponding to a different lane of the plurality of lanes), control logic that initiates a read of a hash memory entry if a corresponding validity bit indicates that said entry is valid, and an encoder that compresses at least the data bytes for the lane associated with the hash memory comprising the valid entry if said valid entry comprises data that matches the lane data bytes.

Claims

1. A data compression apparatus, comprising:

a plurality of hash memories each associated with a different lane of a plurality of lanes, and each lane comprising data bytes of an incoming data stream being received by the data compression apparatus;

validity table comprising array elements each comprising a plurality of validity bits, wherein each validity bit within an array element corresponds to a different lane of the plurality of lanes;

control logic, coupled to the plurality of hash memories and the validity table, that initiates a read of a hash memory entry if a validity bit that corresponds to the lane associated with the hash memory entry indicates that said hash memory entry is valid; and

an encoder, coupled to the plurality of hash memories and the control logic, that compresses at least the data bytes for the lane associated with the hash memory comprising the valid hash entry if said valid hash entry comprises data that matches the data bytes for the lane.

2. The data compression apparatus of claim 1,

wherein at least some received data comprising the lane data bytes is compressed by replacing the at least some received data with a code word that points to a location within the data stream comprising previously received data;

and

wherein the valid hash memory entry further comprises the location of the previously received data.

3. The data compression apparatus of claim 2, wherein the encoder compresses the lane data bytes if a location within the data stream of the lane data bytes is offset from the location of the previously received data by no more than a maximum value.

4. The data compression apparatus of claim 1, wherein the control logic initiates concurrent hash memory entry reads for at least two of the plurality of hash memories if the validity bit corresponding to the hash memory entry and lane of each of the at least two hash memories indicates that each of said hash memory entries is valid in different lanes.

5. The data compression apparatus of claim 1, further comprising:

a plurality of index generators, each coupled to the array, each associated with a different lane of the plurality of lanes, and each producing a hash index for the associated lane based on the associated lane data bytes;

wherein each hash index operates as an address of one of a plurality of array elements read by the control logic, the plurality of array elements being read within a time needed for the data compression apparatus to receive a number of bytes equal to a number of the plurality of lanes; and

wherein if at least two array elements read each indicates a corresponding valid hash memory entry in one same lane, and a read of at least one hash memory entry corresponding to one of the at least two array elements is performed if data from a preceding read of a hash memory entry corresponding to another of the at least two array elements does not match the lane data bytes.

6. The data compression apparatus of claim 5,

wherein each of the at least two array elements further comprises a location within the data stream of previously received data;

and

wherein each read of a hash memory entry is performed in ascending location order based at least in part upon the locations stored within the at least two array elements.

7. The data compression apparatus of claim 5,

wherein each of the at least two array elements further comprises a location within the data stream of previously received data;

and

wherein each valid hash memory entry is read if a corresponding array element of the at least two array elements includes a location within the data stream associated with the same one lane that is offset from the location within the data stream of the lane data bytes by no more than a maximum value.

8. The data compression apparatus of claim 1, further comprising:

a plurality of index generators, each coupled to the array, each associated with a different lane of the plurality of lanes, and each producing a hash index for the associated lane based on the associated lane data bytes;

wherein each hash index operates as an address of a hash memory entry for the associated lane; and

wherein the data read from the valid hash memory entry comprises at least some of the bits of the previously received data.

9. The data compression apparatus of claim 8,

wherein each of the plurality of index generators implements an irreducible polynomial;

and

wherein the number of bits of data stored within the valid hash memory entry is equal to or greater than the bit-width of the associated lane minus the number of bits of the hash index.

10. The data compression apparatus of claim 1, wherein the array comprises one or more devices selected from the group consisting of a flip-flop, a random access memory and a field programmable gate array.

11. A data compression method performed by a compression engine, the data compression method comprising:

associating a plurality of hash memories each with a different lane of a plurality of lanes, each lane comprising data bytes of an incoming data stream being received by a compression apparatus;

storing a plurality of validity bits within each of a plurality of array elements, wherein each validity bit within an array element corresponds to a different lane of the plurality of lanes;

initiating a read of a hash memory entry if a validity bit that corresponds to the lane associated with the hash memory entry indicates that said hash memory entry is valid; and

compressing at least the data bytes for the lane associated with the hash memory comprising the valid hash memory entry if said valid hash memory entry comprises data that matches the data bytes for the lane.

12. The method of claim 11, further comprising compressing at least some received data comprising the lane data bytes by replacing the at least some received data with a code word that points to a location within the data stream comprising previously received data, wherein the valid hash memory entry further comprises the location of the previously received data.

13. The method of claim 12, further comprising compressing the lane data bytes if a location within the data stream of the lane data bytes is offset from the location of the previously received data by no more than a maximum value.

14. The method of claim 11, further comprising initiating concurrent hash memory entry reads for at least two of the plurality of hash memories if the validity bit corresponding to the hash memory entry and lane of each of the at least two hash memories indicates that each of said hash memory entries is valid in different lanes.

15. The method of claim 11, further comprising:

producing a hash index for each of the plurality of lanes based on the associated lane data bytes; and

reading an array element for each of the plurality of lanes using each hash index as an address of the array element within a corresponding lane;

wherein each of the plurality of array elements is read within the time needed for the data compression apparatus to receive a number of bytes equal to a number of the plurality of lanes; and

wherein if at least two array elements read each indicates a corresponding valid hash memory entry in one same lane, a read of at least one hash memory entry corresponding to one of the at least two array elements is performed if data from a preceding read of a hash memory entry corresponding to another of the at least two array elements does not match the lane data bytes.

16. The method of claim 15, further comprising performing each read of a hash memory entry in ascending location order based at least in part upon a location stored within each of the at least two array elements, wherein each location comprises a location within the data stream of previously received data.

17. The method of claim 15, further comprising reading each valid hash memory entry if a corresponding array element of the at least two array elements includes a location within the data stream associated with the same one lane that is offset from the location within the data stream of the lane data bytes by no more than a maximum value, wherein each location comprises a location within the data stream of previously received data.

18. The method of claim 11, further comprising:

producing a hash index for each of the plurality of lanes based on the associated lane data bytes; and

reading a hash memory entry for a corresponding lane using each hash index as an address of the entry, the data read from the valid hash memory entry comprising at least some of the bits of the previously received data.

19. The method of claim 18,

wherein each hash index is produced by an irreducible polynomial;

and

wherein the number of bits of data stored within the valid hash memory entry is equal to or greater than a bit-width of the associated lane minus the number of bits of the hash index.