Method and device for high performance regular expression pattern matching
First Claim
1. In a device for matching an input string to a pattern via a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state and a plurality of possible next states, the input string comprising a plurality of input symbols, the improvement comprising:
- the device comprising at least two parallel pipeline stages;
a first one of the pipeline stages being configured to retrieve a plurality of transitions to a possible next state of the DFA from a pre-populated memory; and
a second one of the pipeline stages that is configured to choose, based at least in part upon the DFA'"'"'s current state, one of said retrieved transitions from which the integrated circuit will determine the next state of the DFA, wherein the second one of the pipeline stages is downstream from the first one of the pipeline stages.
4 Assignments
0 Petitions
Accused Products
Abstract
Disclosed herein is an improved architecture for regular expression pattern matching. Improvements to pattern matching deterministic finite automatons (DFAs) that are described by the inventors include a pipelining strategy that pushes state-dependent feedback to a final pipeline stage to thereby enhance parallelism and throughput, augmented state transitions that track whether a transition is indicative of a pattern match occurring thereby reducing the number of necessary states for the DFA, augmented state transition that track whether a transition is indicative of a restart to the matching process, compression of the DFA'"'"'s transition table, alphabet encoding for input symbols to equivalence class identifiers, the use of an indirection table to allow for optimized transition table memory, and enhanced scalability to facilitate the ability of the improved DFA to process multiple input symbols per cycle.
331 Citations
16 Claims
-
1. In a device for matching an input string to a pattern via a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state and a plurality of possible next states, the input string comprising a plurality of input symbols, the improvement comprising:
-
the device comprising at least two parallel pipeline stages;
a first one of the pipeline stages being configured to retrieve a plurality of transitions to a possible next state of the DFA from a pre-populated memory; anda second one of the pipeline stages that is configured to choose, based at least in part upon the DFA'"'"'s current state, one of said retrieved transitions from which the integrated circuit will determine the next state of the DFA, wherein the second one of the pipeline stages is downstream from the first one of the pipeline stages. - View Dependent Claims (2, 3)
-
-
4. A method for matching an input string to a pattern in a device that realizes a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state and a plurality of possible next states, the input string comprising a plurality of input symbols, the device comprising at least two parallel pipeline stages, the method comprising:
-
within one of the pipeline stages, retrieving from a memory a plurality of stored transitions to a next possible state of the DFA; and within another of the pipeline stages that is downstream in the pipeline from the pipeline stage from which the plurality of transitions were retrieved, selecting one of the retrieved transitions to identify the next state of the DFA, wherein the selecting is based at least in part upon the current state of the DFA. - View Dependent Claims (5)
-
-
6. A device comprising:
a multi-stage pattern matching pipeline configured to receive an input data stream comprising a plurality of input symbols and process the received data stream, wherein the pipeline realizes a pattern matching deterministic finite automaton (DFA) that is configured to determine whether any string of input symbols within the data stream matches a pattern, the DFA having a plurality of states including a current state, the pipeline comprising a plurality of stages including a final stage, each stage having at least one stage input and at least one stage output, the final stage being configured to provide as outputs a next state for the DFA, wherein the only stage of the pipeline that receives a feedback loop based on a stage output is the final stage. - View Dependent Claims (7, 8, 9, 10, 11)
-
12. A device comprising:
a data processing pipeline configured to receive an input data stream comprising a plurality of input symbols and process the received data stream through a logic circuit to determine whether any input symbol string within the input data stream matches a pattern, the logic circuit being configured to realize a deterministic finite automaton (DFA), the DFA comprising a plurality of states, an alphabet of input symbols, an alphabet of equivalence class identifiers (ECIs), a set of functions that map groups of m input symbols to corresponding ECIs, and a set of functions that define transitions between states of the DFA, each state transition function being indexed by an ECI and comprising a next state identifier and a match flag, wherein m is an integer that is greater than or equal to one. - View Dependent Claims (13, 14, 15, 16)
Specification