Methods for accelerating hash-based compression and apparatuses using the same

• US 9,912,351 B1
• Filed: 08/10/2017
• Issued: 03/06/2018
• Est. Priority Date: 05/17/2017
• Status: Active Grant

• Current Assignee: Via Alliance Semiconductor Co., Ltd.
• Original Assignee: Via Alliance Semiconductor Co., Ltd.
• Inventors: Li, Xiaoyang, Qi, Zongpu, Wang, Zheng, Yang, Mengchen, Wu, Fangfang, Luo, Shican, Meng, Lei, Yu, Jin, Ho, Kuan-Jui, Li, Lin
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US15/673,649
• Time in Patent Office: 208 Days
• Field of Search: 341 51- 75
• CPC Class Codes: G06F 12/0215 with look ahead addressing means
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/654 Look-ahead translation
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's
• CPC Class Codes: G06F 9/4498 Finite state machines
• 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/6011 Encoder aspects
• CPC Class Codes: H03M 7/6017 Methods or arrangements to increase the throughput
• CPC Class Codes: H03M 7/6023 Parallelization

Abstract

The invention introduces a method for accelerating hash-based compression, performed in a compression accelerator, comprising: receiving, by a plurality of hash functions, a plurality of substrings from an FSM (Finite-State Machine) in parallel; mapping, by each hash function, the received substring to a hash index and directing a selector to connect to one of a plurality of match paths according to the hash index; transmitting, by a matcher of each connected match path, a no-match message to the FSM when determining that a hash table does not contain the received substring; and transmitting, by the matcher of each connected match path, a match message and a match offset of the hash table to the FSM when determining that the hash table contains the received substring, wherein the match offset corresponds to the received substring.

Claims

1. A method for accelerating hash-based compression, performed in a compression accelerator of a microprocessor, comprising:

receiving, by a plurality of hash functions, a plurality of sub strings from an FSM (Finite-State Machine) in parallel;

mapping, by each hash function, the received substring to a hash index and directing a selector to connect to one of a plurality of match paths according to the hash index;

transmitting, by a matcher of each connected match path, a no-match message to the FSM when determining that a hash table does not contain the received sub string; and

transmitting, by the matcher of each connected match path, a match message and a match offset of the hash table to the FSM when determining that the hash table contains the received substring, wherein the match offset corresponds to the received substring.

2. The method of claim 1, wherein a memory bank of each connected match path stores a portion of the hash table,

the method comprising:

transmitting, by the matcher of each connected match path, the no-match message to the FSM when determining that the corresponding portion of the hash table does not contain the received substring,

transmitting, by the matcher of each connected match path, the match message and the match offset of the corresponding portion of the hash table to the FSM when determining that the corresponding portion of the hash table contains the received substring.

3. The method of claim 2, wherein the portion of the hash table comprises a plurality of entries and each entry comprises a plurality of hash keys together with the same hash index.

4. The method of claim 2, wherein the portion of the hash table comprises a plurality of entries, each entry comprises a plurality of hash keys and a plurality of hash offsets, each of which corresponds to one hash key, the method comprising:

when determining that one hash key of the portion of the hash table is the same as the received sub string, transmitting, by the matcher of each connected match path, the match message and the hash offset corresponding to the hash key of the portion of the hash table to the FSM.

5. The method of claim 2, wherein the portion of the hash table comprises a plurality of entries, each entry comprises a first hash key and a first hash offset corresponding to the first hash key, a second hash key and a second hash offset corresponding to the second hash key, and a third hash key and a third hash offset corresponding to the third hash key.

6. The method of claim 5, comprising:

comparing, by the matcher of each connected hash path, the first hash key with the received sub string;

comparing, by the matcher of each connected hash path, the second hash key with the received sub string; and

comparing, by the matcher of each connected hash path, the third hash key with the received substring.

7. The method of claim 5, comprising:

when determining that one of the first to third hash keys is the same as the received sub string, transmitting, by the matcher of each connected match path, the match message and the hash offset corresponding to the matched hash key of the portion of the hash table to the FSM.

8. The method of claim 5, comprising:

when determining that at least two of the first to third hash keys are the same as the received sub string, transmitting, by the matcher of each connected match path, the match message and the minimum of the hash offsets corresponding to the matched hash keys of the portion of the hash table to the FSM.

9. The method of claim 1, wherein a length of the hash index is shorter than a length of the substring.

10. The method of claim 1, wherein the FSM outputs the substrings simultaneously at the same clock cycle.

11. An apparatus for accelerating hash-based compression, comprising:

an FSM (Finite-State Machine); and

a hash matcher, coupled to the FSM, comprising;

a plurality of hash functions;

a selector, coupled to the hash functions; and

a plurality of match paths, coupled to the selector,

wherein the hash functions receives the substrings from the FSM, each hash function maps the received substring to a hash index and directs the selector to connect to one of the match paths according to the hash index,

wherein a matcher of each connected match path, transmits a no-match message to the FSM when determining that a hash table does not contain the received substring,

wherein the matcher of each connected match path transmits a match message and a match offset of the hash table to the FSM when determining that the hash table contains the received sub string, and

wherein the match offset corresponds to the received substring.

12. The apparatus of claim 11, wherein each connected match path comprises:

a memory bank storing a portion of the hash table;

a FIFO (First-In-First-Out) queue, coupled to the selector, wherein one hash function directs the selector to connect to the FIFO queue according to hash index for pushing the received sub string into the FIFO queue; and

the matcher, coupled between the memory bank and the FIFO queue, obtaining the received substring from the FIFO queue, transmitting the no-match message to the FSM when determining that the portion of the hash table does not contain the received sub string, and transmitting the match message and the match offset of the portion of the hash table to the FSM when determining that the portion of the hash table contains the received sub string.

13. The apparatus of claim 12, wherein the portion of the hash table comprises a plurality of entries and each entry comprises a plurality of hash keys together with the same hash index.

14. The apparatus of claim 12, wherein the portion of the hash table comprises a plurality of entries, each entry comprises a plurality of hash keys and a plurality of hash offsets, each of which corresponds to one hash key, and when determining that one hash key of the portion of the hash table is the same as the received substring, the matcher transmits the match message and the hash offset corresponding to the hash key of the portion of the hash table to the FSM.

15. The apparatus of claim 12, wherein the portion of the hash table comprises a plurality of entries, each entry comprises a first hash key and a first hash offset corresponding to the first hash key, a second hash key and a second hash offset corresponding to the second hash key, and a third hash key and a third hash offset corresponding to the third hash key.

16. The apparatus of claim 15, wherein the matcher comprises:

a first comparator determining whether the first hash key is the same as the received sub string and, if so, outputting the first hash offset;

a second comparator determining whether the second hash key is the same as the received sub string and, if so, outputting the second hash offset;

a third comparator determining whether the third hash key is the same as the received sub string and, if so, outputting the third hash offset; and

an arbiter, coupled to the first to third comparators, replying to the FSM with the no-match message when no hash offset has been received from the first to third comparators, and replying to the FSM with the match message and the received hash offset when at least one hash offset has been received from the first to third comparators.

17. The apparatus of claim 16, wherein the arbiter replies to the FSM with the match message and the minimum of the received hash offsets when at least two hash offsets have been received from the first to third comparators.

18. The apparatus of claim 11, wherein the FSM and the hash matcher are disposed in a compression accelerator and the compression accelerator is disposed outside of a processor core.

19. The apparatus of claim 11, wherein a length of the hash index is shorter than a length of the substring.

20. The apparatus of claim 11, wherein the FSM outputs the substrings simultaneously at the same clock cycle.