Algorithm engine for use in a pattern matching accelerator

摘要

A pattern matching accelerator (PMA) for assisting software threads to find the presence and location of strings in an input data stream that match a given pattern. The patterns are defined using regular expressions that are compiled into a data structure comprised of rules subsequently processed by the PMA. The patterns to be searched in the input stream are defined by the user as a set of regular expressions. The patterns to be searched are grouped in pattern context sets. The sets of regular expressions which define the pattern context sets are compiled to generate a rules structure used by the PMA hardware. The rules are compiled before search run time and stored in main memory, in rule cache memory within the PMA or a combination thereof. For each input character, the PMA executes the search and returns the search results.

主权项

1. An algorithm engine for searching and scanning for regular expression based pattern contexts in an input character stream, comprising:
control logic operative to receive pattern context search commands from a data engine; one or more physical pattern search lanes, each physical pattern search lane comprising:
a memory store operative to store a plurality of local rules and a plurality of temporary rules;one or more pattern search engines, each pattern search engine coupled to its corresponding memory store and operative to execute said pattern context search commands;wherein each physical pattern search lane is time multiplexed to create a plurality of logical pattern search lanes, each logical pattern search lane operative to execute independently of other logical pattern search lanes a search command received from a command unit, whereby said command unit operating on two searches may be connected to two logical lanes at the same time; and a local results processor (LRP) associated with each pattern search lane for assisting said pattern search engines in searching complex pattern contexts; and wherein a local results processor is associated with each logical pattern search lane and is operative to receive a set of commands from a corresponding logical pattern search engine on partial matches during a search operation and analyze match results to assist in processing complex regular expression pattern contexts.