Multiple step non-deterministic finite automaton matching
View Patent ↗Disclosed is a hardware NFA cell array used to find matches to regular expressions or other rules in an input symbol stream. The cell array scans multiple symbols per clock cycle by comparing multiple symbol classes against multiple input symbols per cycle in parallel, signaling bundles of multiple transitions from parent cells to child cells and updating NFA state status by multiple steps. To retain high frequency operation, the cell array will not resolve transition chains from a first cell to a second cell to a third cell in a single cycle. When a chain is required, the cell array takes fewer steps in one cycle to break the chain into separate cycles. To detect multi-transition chains, each cell compares symbol classes to future symbols in advance and back-communicates future match positions to parent cells in the array as launch hazards.
1. A method of multiple step non-deterministic finite automaton (NFA) matching of input symbols in an NFA cell array having a plurality of cells, the method comprising:
consuming at least two successive input symbols in a first clock cycle of a clock signal at each cell in the plurality of cells;
comparing at least one symbol class in a cell of the plurality of cells in a second clock cycle of the clock signal with the at least two successive input symbols;
emitting at least two output transitions from the cell of the plurality of cells in a third clock cycle of the clock signal corresponding to successive symbol positions, said output transitions being destined to a same destination cell;
performing status updates in the cell of the plurality of cells in the third clock cycle; and
receiving at least two input transitions in the cell of the plurality of cells in the third clock cycle corresponding to successive symbol positions, said input transitions being received by the cell and from a same emitting cell.
2. The method of claim 1 , wherein said NFA cell array is a dynamically configurable cell array.
3. The method of claim 1 , wherein no state transition chain occurs from a first cell of the plurality of cells to a second cell of the plurality of cells to a third cell of the plurality of cells in any clock cycle.
4. The method of claim 1 , wherein:
said NFA cell array is a dynamically configurable cell array; and
no state transition chain occurs from a first cell of the plurality of cells to a second cell of the plurality of cells to a third cell in any clock cycle.
5. The method of claim 1 , wherein the step of emitting the at least two output transitions is independent of the step of receiving at least two input symbols.
6. The method of claim 5 , wherein said NFA cell array is a dynamically configurable cell array.
7. The method of claim 6 , wherein the step of emitting at least two output transitions occurs earlier in the third clock cycle than the step of receiving at least two input transitions.
8. The method of claim 1 , wherein the step of emitting at least two output transitions occurs earlier in the third clock cycle than the step of receiving at least two input transitions.
9. The method of claim 8 , wherein said NFA cell array is a dynamically configurable cell array.
10. The method of claim 1 , said method further comprising:
detecting in the cell array whether a match of a first symbol in a first state will cause a transition from a second state to a third state on a consecutive second symbol; and
if said transition from a second state to a third state would occur, preventing consumption of the first and second symbol in the same clock cycle.
11. The method of claim 1 , further comprising:
comparing a symbol class in an NFA child cell with a future input symbol in advance;
communicating a successful comparison of the future symbol to a parent cell, said parent cell detecting whether it matches a current input symbol, said match causing a transition to the child cell; and
if the parent cell receives the signal indicating a match of the future symbol and matches the current symbol causing a transition to the child cell, preventing the future symbol from being consumed during the same clock cycle as the current symbol is consumed.
12. The method of claim 11 , wherein said NFA cell array is a dynamically configurable cell array.
13. A system for multiple step matching of input symbols, comprising:
a non-deterministic finite automaton (NFA) cell array, comprising a plurality of cells, enabled to:
transmit bundles of multiple transition signals from a first set of cells of the plurality of cells to a second set of cells of the plurality of cells,
compare character classes in each cell of the plurality of cells against multiple input symbols in parallel,
generate out-transitions from each cell of the plurality of cells for multiple symbol steps in one clock cycle of a clock signal, and
receive in-transitions into each cell of the plurality of cells for multiple symbol steps in one clock cycle of the clock signal; and
a step size selector enabled to receive slow down requests from each cell of the plurality of cells to determine a proper step size for each clock cycle in the NFA cell array.
14. The system of claim 13 , wherein said NFA cell array is a dynamically configurable cell array.
15. The system of claim 13 , wherein:
said NFA cell array is further enabled to compare future character classes early in the second set of cells to determine launch hazards, communicate the launch hazards to the first set of cells and generate the slow-down requests when the launch hazards correspond to out-transitions.
16. The system of claim 13 , wherein:
said step size selector is enabled to determine the proper step size by gathering all slow-down requests generated by each cell of the plurality of cells and signaling the proper step size to each cell of the plurality of cells, wherein each slow-down request comprises a maximum step size and the selector taking the smallest received step size and signaling said smallest received step size to each cell of the plurality of cells.
17. The system of claim 16 , wherein the NFA cell array generates slow-down requests by comparison of received launch hazards with generated out-transitions in the first set of cells.
18. The system of claim 13 , wherein the NFA cell array if further enabled to generate slow-down requests by comparison of received launch hazards with generated out-transitions in the first set of cells.
19. The system of claim 18 , wherein each slow-down request comprises a maximum step size and the selector taking the smallest received step size and signaling said smallest received step size to each cell of the plurality of cells.