Multithreaded DFA architecture for finding rules match by concurrently performing at varying input stream positions and sorting result tokens

摘要

Disclosed is an architecture, system and method for performing multi-thread DFA descents on a single input stream. An executer performs DFA transitions from a plurality of threads each starting at a different point in an input stream. A plurality of executers may operate in parallel to each other and a plurality of thread contexts operate concurrently within each executer to maintain the context of each thread which is state transitioning. A scheduler in each executer arbitrates instructions for the thread into an at least one pipeline where the instructions are executed. Tokens may be output from each of the plurality of executers to a token processor which sorts and filters the tokens into dispatch order.

主权项

1. An architecture for finding rule matches within an input stream, comprising:
a symbol buffer; a dispatcher operably connected to said symbol buffer and operably enabled to dispatch deterministic finite automata (DFA) descent starting positions; an instruction memory which holds instructions for transitions from DFA states; at least one executer which receives DFA descent starting positions from the dispatcher, retrieves instructions from the instruction memory and symbols from the symbol buffer, executes said instructions and performs parallel DFA descents starting in root states at varying positions in an input stream, and outputs a plurality of tokens from a plurality of the parallel DFA descents, wherein each token of the plurality of tokens includes information for a rule match; and a token processor which receives the plurality of tokens and sorts the plurality of tokens into dispatch order.