Multiple step non-deterministic finite automaton matching

摘要

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.