Data compression accelerator methods, apparatus and design structure with improved resource utilization

• US 9,971,704 B2
• Filed: 03/27/2015
• Issued: 05/15/2018
• Est. Priority Date: 03/27/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Abali, Bulent, Blaner, Bartholomew, Sinharoy, Balaram
• Primary Examiner(s): THAI, TUAN V
• Application Number:
  US14/670,605
• Publication Number:
  US 20160283398A1
• Time in Patent Office: 1,145 Days
• Field of Search: 711100, 711154, 711216
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's
• 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/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/6058 Saving memory space in the encoder or decoder

Abstract

Methods, apparatus and design structures are provided for improving resource utilization by data compression accelerators. An exemplary apparatus for compressing data comprises a plurality of hardware data compression accelerators and a hash table shared by the plurality of hardware data compression accelerators. Each of the plurality of hardware data compression accelerators optionally comprises a first-in-first-out buffer that stores one or more input phrases. The hash table optionally records a location in the first-in-first-out buffers where a previous instance of an input phrase is stored. The plurality of hardware data compression accelerators can simultaneously access the hash table. For example, the hash table optionally comprises a plurality of input ports for simultaneous access of the hash table by the plurality of hardware data compression accelerators. A design structure for a data compression accelerator system is also disclosed.

Claims

1. An apparatus for compressing data, comprising:

a plurality of hardware data compression accelerators that each process a respective stream of input phrases of said data during one or more of a write operation and a read operation of said data; and

a hash table shared by said plurality of hardware data compression accelerators during said one or more of said write operation and said read operation of said data, wherein said shared hash table records a location where a previous instance of a given input phrase of said data from said respective stream of input phrases of said data is stored and wherein multiple instances of said given input phrase are stored in said shared hash table as a single instance of said given input phrase to compress said data, wherein at least two of said plurality of hardware data compression accelerators substantially simultaneously share access to said shared hash table.

2. The apparatus of claim 1, wherein said hash table records said location in a first-in-first-out buffer where most recently entered input phrases will overwrite the older phrases.

3. The apparatus of claim 1, wherein each of said plurality of hardware data compression accelerators comprise a first-in-first-out buffer that stores one or more input phrases.

4. The apparatus of claim 1, wherein each of said plurality of hardware data compression accelerators comprise one or more of a hash function, a Lempel-Ziv (LZ) encoder and a Huffman encoder.

5. The apparatus of claim 1, wherein said plurality of hardware data compression accelerators simultaneously access said hash table.

6. The apparatus of claim 1, wherein said hash table comprises a plurality of input ports for simultaneous access of said hash table by said plurality of hardware data compression accelerators.

7. The apparatus of claim 1, wherein said hash table is partitioned into a plurality of logical arrays.

8. The apparatus of claim 7, wherein said partitioning of said hash table is performed dynamically for each compression operation.

9. The apparatus of claim 1, wherein values stored in said hash table have an associated identifier to indicate a corresponding one of said plurality of hardware data compression accelerators.

10. The apparatus of claim 1, wherein said apparatus is embodied on an integrated circuit.

11. A hardware description language (HDL) design structure encoded on a non-transitory machine-readable data storage medium, said HDL design structure comprising elements that when processed in a computer-aided design system generates a machine-executable representation of a data compression accelerator system, wherein said HDL design structure comprises:

a plurality of hardware data compression accelerators that each process a respective stream of input phrases of said data during one or more of a write operation and a read operation of said data; and

a hash table shared by said plurality of hardware data compression accelerators during said one or more of said write operation and said read operation of said data, wherein said shared hash table records a location where a previous instance of a given input phrase of said data from said respective stream of input phrases of said data is stored and wherein multiple instances of said given input phrase are stored in said shared hash table as a single instance of said given input phrase to compress said data, wherein at least two of said plurality of hardware data compression accelerators substantially simultaneously share access to said shared hash table.

12. The HDL design structure of claim 11, wherein said hash table records said location in a first-in-first-out buffer where most recently entered input phrases will overwrite the older phrases.

13. The HDL design structure of claim 11, wherein each of said plurality of hardware data compression accelerators comprise a first-in-first-out buffer that stores one or more input phrases.

14. The HDL design structure of claim 11, wherein each of said plurality of hardware data compression accelerators comprise one or more of a hash function, a Lempel-Ziv (LZ) encoder and a Huffman encoder.

15. The HDL design structure of claim 11, wherein said plurality of hardware data compression accelerators simultaneously access said hash table.

16. The HDL design structure of claim 11, wherein said hash table comprises a plurality of input ports for simultaneous access of said hash table by said plurality of hardware data compression accelerators.

17. The HDL design structure of claim 11, wherein said hash table is partitioned into a plurality of logical arrays.

18. The HDL design structure of claim 17, wherein said partitioning of said hash table is performed dynamically for each compression operation.

19. The HDL design structure of claim 11, wherein values stored in said hash table have an associated identifier to indicate a corresponding one of said plurality of hardware data compression accelerators.

20. The HDL design structure of claim 11, wherein said plurality of hardware data compression accelerators and said hash table are embodied on an integrated circuit.