Multiple step non-deterministic finite automaton matching

Patent metadata

Field	Value
Publication number	US-9251440-B2
Application number	US-201213718948-A
Country	US
Kind code	B2
Filing date	Dec 18, 2012
Priority date	Dec 18, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

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.

First claim

What is claimed is:

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;…

Assignees

• Intel Corp

Inventors

• Ruehle Michael

Classifications

• H04L69/22

  Electricity · mapped topic

• G06F17/30

  Physics · mapped topic

• G06K9/6878 Primary

  Physics · mapped topic

• G06F16/90344 Primary

  Physics · mapped topic

• G06V30/1983 Primary

  Physics · mapped topic