PROGRAMMABLE REGULAR EXPRESSION AND CONTEXT FREE GRAMMAR MATCHER

• US 20130338998A1
• Filed: 06/13/2012
• Published: 12/19/2013
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Freitas, Richard F., Montoye, Robert K., Shinde, Rajendra
• Granted Patent: US 9,093,151 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G11C 13/0004 comprising amorphous/crystalline phase transition cells
• CPC Class Codes: G11C 15/046 using non-volatile storage elements

Abstract

A regular expression matcher system, including: a deterministic finite state machine (DFSM); a ternary content addressable memory (TCAM) matcher to compare a word stored at the TCAM matcher to an input stream, wherein the word determines a state-to-state transition of the DFSM from a comparison result; a programmable logic connected to an output of the TCAM matcher to identify a next state in the DFSM based on the comparison result; a state register to update a current state of the DFSM to the next state; and a collection data structure coupled to the TCAM matcher and the programmable logic to store a sequence of required state transitions for the DFSM, wherein the programmable logic determines a next required state transition to be matched from the sequence.

Claims

1. A computer program product, comprising:

a computer readable storage device to store a computer readable program, wherein the computer readable program, when executed by a processor within a computer, causes the computer to perform operations for expression matching, the operations comprising;

comparing data from an input stream to a word on a programmable ternary content addressable memory (TCAM) matcher to determine a state-to-state transition in an expression matcher from a comparison result;

identifying a next state in the expression matcher based on the comparison result using a programmable logic connected to an output of the programmable TCAM matcher;

updating the expression matcher to the next state; and

storing a sequence of required state transitions for the expression matcher in a collection data structure coupled to the TCAM matcher and the programmable logic, wherein the programmable logic determines a next required state transition to be matched from the sequence.

2. The computer program product of claim 1, wherein the computer program product, when executed on the computer, causes the computer to perform additional operations, comprising:

comparing the data from the input stream to words on a plurality of TCAM matchers for a plurality of expression matchers simultaneously.

3. The computer program product of claim 1, wherein the TCAM matcher is a phase change memory (PCM) TCAM matcher.

4. The computer program product of claim 1, wherein the programmable logic is phase change memory (PCM) based, wherein a programmable resistor is placed at an input to a logic gate of the programmable logic to control operation of the logic gate.

5. The computer program product of claim 1, wherein the computer program product, when executed on the computer, causes the computer to perform additional operations, comprising:

receiving data from a previous expression matcher at the TCAM matcher; and

programming the TCAM matcher using the data from the previous expression matcher.

6. The computer program product of claim 1, wherein the computer program product, when executed on the computer, causes the computer to perform additional operations, comprising:

maintaining a count for a specified data sequence from the input stream at a counter in the collection data structure.

7. The computer program product of claim 6, wherein the computer program product, when executed on the computer, causes the computer to perform additional operations, comprising:

setting an initial count for the counter using a preset register, wherein the counter counts down from the initial count in response to an occurrence of the specified data sequence.

8. A method for regular expression matching, comprising:

comparing data from an input stream to a word on a programmable ternary content addressable memory (TCAM) matcher to determine a state-to-state transition in an expression matcher from a comparison result;

identifying a next state in the expression matcher based on the comparison result using a programmable logic connected to an output of the programmable TCAM matcher;

updating the expression matcher to the next state; and

storing a sequence of required state transitions for the expression matcher in a collection data structure coupled to the TCAM matcher and the programmable logic, wherein the programmable logic determines a next required state transition to be matched from the sequence.

9. The method of claim 8, further comprising comparing the data from the input stream to words on a plurality of TCAM matchers for a plurality of expression matchers simultaneously.

10. The method of claim 8, wherein the TCAM matcher is a phase change memory (PCM) TCAM matcher.

11. The method of claim 8, wherein the programmable logic is phase change memory (PCM) based, wherein a programmable resistor is placed at an input to a logic gate of the programmable logic to control operation of the logic gate.

12. The method of claim 8, further comprising maintaining a count for a specified data sequence from the input stream at a counter in the collection data structure.

13. The method of claim 12, further comprising setting an initial count for the counter using a preset register, wherein the counter counts down from the initial count in response to an occurrence of the specified data sequence.

14. The method of claim 8, further comprising:

receiving data from a previous expression matcher at the TCAM matcher; and

programming the TCAM matcher using the data from the previous expression matcher.

15. A regular expression (regex) matcher system, comprising:

an expression matcher;

a ternary content addressable memory (TCAM) matcher to compare a word stored on the TCAM matcher to an input stream, wherein the word determines a state-to-state transition of the expression matcher from a comparison result;

a programmable logic connected to an output of the TCAM matcher to identify a next state in the expression matcher based on the comparison result;

a state register to update a current state of the expression matcher to the next state; and

a collection data structure coupled to the TCAM matcher and the programmable logic to store a sequence of required state transitions for the DFSM, wherein the programmable logic determines a next required state transition to be matched from the sequence.

16. The system of claim 15, further comprising a plurality of TCAM matchers to compare words stored on the TCAM matchers for a plurality of expression matchers simultaneously.

17. The system of claim 15, wherein the TCAM matcher is a phase change memory (PCM) TCAM matcher and the programmable logic is PCM based, wherein a programmable resistor is placed at an input to each logic gate of the TCAM matcher and the programmable logic to control operation of each logic gate.

18. The system of claim 15, further comprising a counter configured to maintain a count for a specified data sequence from the input stream.

19. The system of claim 18, further comprising a preset register to hold an initial count for the counter, wherein the counter counts down from the initial count in response to an occurrence of the specified data sequence.

20. The system of claim 15, wherein the TCAM matcher is configured to receive data from a previous expression matcher, wherein the data from the previous expression matcher is used to program the TCAM matcher.