High speed large scale dictionary matching

• US 8,830,714 B2
• Filed: 06/07/2012
• Issued: 09/09/2014
• Est. Priority Date: 06/07/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agarwal, Kanak B., Hofstee, Harm P.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/490,832
• Publication Number:
  US 20130332146A1
• Time in Patent Office: 824 Days
• Field of Search: 707/747, 707/758, 711/100, 711/216, 711/108, 704/10, 365/189, 365/49
• US Class Current: 365/49.17
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

A mechanism is provided for dictionary matching. The mechanism loads a plurality of dictionary memory arrays with a set of dictionary words and updates a plurality of status arrays. Each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays. Each entry of a given status array stores a status bit, which indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word. The mechanism receives an input data word and generates a hash value based on the input data word. The mechanism reads a dictionary word from each of the dictionary memory arrays and a status bit from each of the status arrays using the hash value as a read address. The mechanism determines whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word.

Claims

1. A method, in a data processing system, for dictionary matching, the method comprising:

loading a plurality of dictionary memory arrays with a set of dictionary words and updating a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word;

receiving an input data word;

generating a hash value based on the input data word;

reading a dictionary word from each of the dictionary memory arrays and a status bit from each of the status arrays using the hash value as a read address; and

determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word.

2. The method of claim 1, wherein the set of dictionary words comprises 2^N dictionary words, wherein the plurality of dictionary memory arrays comprises N dictionary memory arrays, and wherein the plurality of status arrays comprises N status arrays.

3. The method of claim 2, wherein generating a hash value based on the input data word comprises generating an N-bit hash.

4. The method of claim 3, wherein each dictionary memory array, DMA_i, where i=0 . . . N−

1, stores 2^N-i entries and is addressed by N−

i bits of the hash value; and

wherein each status array, SA_i, stores 2^N-i status bits and is addressed by N−

i bits of the hash value.

5. The method of claim 4, wherein determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word comprises:

for each dictionary memory array, DMA_i, reading DMA using N−

i bits of the hash value as a read address to generate a read word, reading SA_i using N−

i bits of the hash value as a read address to generate a read status, comparing the read word to the input data word, and asserting an output signal if the read word matches the input data word and the read status indicates the read word is valid,

wherein the plurality of dictionary memory arrays generate a plurality of output signals.

6. The method of claim 5, wherein determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word further comprises:

performing an OR operation on the plurality of output signals.

7. The method of claim 1, wherein loading the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays comprises:

for a given input dictionary word, generating a corresponding hash value based on the input dictionary word, reading each status array at a target address based on the corresponding hash value to generate a read status, asserting a write enable signal to a target dictionary memory array having a largest size and a read status indicating that a valid dictionary word is not stored in the target dictionary memory array at the target address, and writing the given input dictionary word to the target dictionary memory array at the target address.

8. The method of claim 7, wherein loading the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays further comprises:

writing a valid bit to a target status array corresponding to the target dictionary memory array.

9. The method of claim 7, wherein loading the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays further comprises:

responsive to all hash-indexed dictionary memory arrays having a read status indicating that a valid dictionary word is stored in the target dictionary memory array at the target address, writing the given input dictionary word to a non-hash-indexed register.

10. The method of claim 1, wherein the plurality of dictionary memory arrays comprise at least one non-hash-indexed register.

11. An apparatus for dictionary matching, the apparatus comprising:

a plurality of dictionary memory arrays loaded with a set of dictionary words;

a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word;

hash logic configured to receive an input data word and generate a hash value based on the input data word; and

a plurality of comparators, wherein each comparator within the plurality of comparators is configured to receive a dictionary word from a respective one of the plurality of dictionary memory arrays and a status bit from a respective one of the plurality of status arrays using the hash value as a read address and to determine whether the dictionary memory array stores a valid dictionary word that matches the input data word.

12. The apparatus of claim 11, wherein the set of dictionary words comprises 2^N dictionary words, wherein the plurality of dictionary memory arrays comprises N dictionary memory arrays, and wherein the plurality of status arrays comprises N status arrays.

13. The apparatus of claim 12, wherein the hash logic generates an N-bit hash.

14. The apparatus of claim 13, wherein each dictionary memory array, DMA_i, where i=0 . . . N−

1, stores 2^N-i entries and is addressed by N−

i bits of the hash value; and

wherein each status array, SA_i, stores 2^N-i status bits and is addressed by N−

i bits of the hash value.

15. The apparatus of claim 14, wherein the apparatus determines whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word, comprising:

for each dictionary memory array, DMA_i, reading DMA, using N−

i bits of the hash value as a read address to generate a read word, reading SA_i using N−

i bits of the hash value as a read address to generate a read status, comparing the read word to the input data word, and asserting an output signal if the read word matches the input data word and the read status indicates the read word is valid,

wherein the plurality of dictionary memory arrays generate a plurality of output signals.

16. The apparatus of claim 15, wherein determining whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word further comprises:

performing an OR operation on the plurality of output signals.

17. The apparatus of claim 11, wherein the apparatus loads the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays, comprising:

for a given input dictionary word, generating a corresponding hash value based on the input dictionary word, reading each status array at a target address based on the corresponding hash value to generate a read status, asserting a write enable signal to a target dictionary memory array having a largest size and a read status indicating that a valid dictionary word is not stored in the target dictionary memory array at the target address, and writing the given input dictionary word to the target dictionary memory array at the target address.

18. The apparatus of claim 17, wherein loading the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays further comprises:

writing a valid bit to a target status array corresponding to the target dictionary memory array.

19. The apparatus of claim 17, wherein loading the plurality of dictionary memory arrays with the set of dictionary words and updating the plurality of status arrays further comprises:

responsive to all hash-indexed dictionary memory arrays having a read status indicating that a valid dictionary word is stored in the target dictionary memory array at the target address, writing the given input dictionary word to a non-hash-indexed register.

20. The apparatus of claim 11, wherein the plurality of dictionary memory arrays comprise at least one non-hash-indexed register.

21. A dictionary matching apparatus comprising:

an input buffer, wherein the input buffer is configured to receive a stream of input words;

a tokenizer, wherein the tokenizer is configured to identify whitespace and punctuation characters in the stream of input words in the input buffer to generate a tokenized stream of input words;

extraction logic, wherein the extraction logic is configured to extract a next input data word from the tokenized stream of input words;

hash logic, wherein the hash logic is configured to generate a hash value based on the next input data word; and

a plurality of dictionary memory arrays loaded with a set of dictionary words and a plurality of status arrays, wherein each status array of the plurality of status arrays corresponds to a respective one of the plurality of dictionary memory arrays and wherein each entry of a given status array stores a status bit that indicates whether a corresponding entry of the corresponding dictionary memory array stores a valid dictionary word, wherein the plurality of dictionary memory arrays and the plurality of status arrays generate a match signal indicating whether a dictionary memory array within the plurality of dictionary memory arrays stores a valid dictionary word that matches the input data word.

22. The dictionary matching apparatus of claim 21, further comprising:

a multiplexer, wherein the multiplexer is configured to select between the next input data word and a dictionary word to be loaded into the plurality of dictionary memory arrays based on a load word signal,

wherein the hash logic is further configured to generate a corresponding hash value based on the dictionary word and wherein the plurality of dictionary memory arrays are configured to write the dictionary word to a target dictionary memory array within the plurality of dictionary memory arrays at a target address based on the corresponding hash value.