Pattern matching 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 apparatus for performing pattern matching on an input character stream, comprising:
a state register operative to store a current state of one or more state machines; a character classifier having a class lookup table (LUT), said character classifier operative to characterize each character in said input stream and generate a class vector therefrom, said class LUT initialized and uploaded by an upload manager in communication therewith; a rules selector operative to perform a comparison among a plurality of rule candidates read from a transition rules memory and a default rules memory in an attempt to find a rule matching said current state, input character and class vector, said transition rules stored in compressed form in said transition rules memory and said default rules stored in compressed form in said default rules memory; an address generator operative to generate addresses corresponding to a next plurality of transition rules in accordance with input characters and current state, said next plurality of transition rules to be matched against said input character stream and the output of said rules selector; wherein said rules selector is operative to test the generated class vector information associated with an input character rather than the actual input character thereby substantially reducing the number of rules required for certain patterns and wherein the address generator is to generate, based at least in part on a global local address translation table, global addresses and local addresses corresponding to the next plurality of transition rules; and an upload manager to monitor search engine performance counters and determine the transition rules to store in local memory from main memory based in part on the search engine performance counters.