HYBRID COMPRESSION FOR LARGE HISTORY COMPRESSORS

• US 20170192708A1
• Filed: 12/31/2015
• Published: 07/06/2017
• Est. Priority Date: 12/31/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Abali, Bulent, Lastras, Luis A., Franaszek, Peter A.
• Granted Patent: US 9,836,238 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/65 Details of virtual memory and virtual address translation
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0656 Data buffering 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: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 2207/102 Compression or decompression of data before storage
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/6076 Selection between compressors of the same type

Abstract

A compression engine and method for optimizing the high compression of a content addressable memory (CAM) and the efficiency of a static random access memory (SRAM) by synchronizing a CAM with a relatively small near history buffer and an SRAM with a larger far history buffer. An input stream is processed in parallel through the near history and far history components and an encoder selects for the compressed output the longest matching strings from matching strings provided by each of the near history and far history components.

Claims

1. A compression engine for large history compressors, comprising:

a near history component implemented in first type of memory;

a far history component implemented in second type of memory,

wherein matching in the near history is synchronized with matching in the far history to generate a compressed output.

2. A compression engine as in claim 1, wherein the near history component is implemented in content addressable memory (CAM) and the far history component is implemented in static random access memory (SRAM).

3. A compression engine as in claim 1, wherein an input stream is processed in parallel by both the near history component and the far history component, the near history component providing all possible matches between current input and a near history buffer and the far history component detecting matches between current input and a far history buffer via a hash table of tokens of current input.

4. A compression engine as in claim 3, further comprising an encoder, the encoder selecting for the compressed output a longest matching string from among matching strings provided by the near history component and the far history component.

5. A compression engine as in claim 4, wherein the encoder sends a reset signal to the near history component if the longest matching string is selected from the far history component and the encoder sends a reset signal to the far history component if the longest matching string is selected from the near history component.

6. A compression engine as in claim 3, wherein the far history component further comprises:

a far history buffer for storing an input string at a next buffer address;

a hash table for storing said next buffer address at a hash of a token of said input string.

7. A compression engine as in claim 6, wherein the hash table contains a set of entries for each hash value.

8. A compression engine as in claim 7, wherein a token for a current input is matched to a prior location in the far history buffer.

9. A compression engine as in claim 8, wherein the match of the token is extended to include a next input.

10. A compression engine as in claim 9, wherein a longest matching string is sent to the encoder when the match cannot be extended to a next input.

11. A compression method for large history compressors, comprising:

processing an input stream in parallel through a near history component and a far history component, the near history component being implemented in first type of memory and the far history component being implemented in second type of memory;

synchronizing matching by the near history component with matching by the far history component;

generating a compressed output from the synchronized matching.

12. A compression method as in claim 11, wherein the near history component is implemented in content addressable memory (CAM) and the far history component is implemented in static random access memory (SRAM).

13. A compression method as in claim 11, wherein the near history component provides all possible matches between current input and a near history buffer and the far history component detects matches between current input and a far history buffer via a hash table of tokens of current input.

14. A compression method as in claim 13, further comprising selecting for the compressed output a longest matching string from among matching strings provided by the near history component and the far history component.

15. A compression method as in claim 14, further comprising sending a reset signal to the near history component if the longest matching string is selected from the far history component and sending a reset signal to the far history component if the longest matching string is selected from the near history component.

16. A compression method as in claim 13, further comprising:

storing an input string at a next buffer address in a far history buffer; and

storing said next buffer address at a hash of a token of said input string.

17. A compression method as in claim 16, wherein the hash table contains a set of entries for each hash value.

18. A compression method as in claim 17, further comprising matching a token for a current input to a prior location in the far history buffer.

19. A compression method as in claim 18, further comprising extending the match of the token to include a next input.

20. A compression method as in claim 19, wherein a longest matching string is sent to an encoder when the match cannot be extended to a next input.