Advanced regular-expression matching with very high storage efficiency
Publication Date: 2014-Mar-24
The IP.com Prior Art Database
A method for exploiting default transitions to improve the storage efficiency of a programmable state machine
Page 01 of 3
Advanced regular -expression matching with very high storage efficiency
Disclosed is a method to reduce the storage requirements of a B-FSM engine, which is a programmable state engine that is described in . The B-FSM engine executes a specification of a deterministic finite automaton (DFA) that is compiled into a compressed structure composed of transition rules. For each input value, the B-FSM engine applies a hash function to select a transition rule whose conditions match the current state and input values, and which is used to select the next state to which the engine branches. In the original B-FSM scheme, the transition rules are stored in a so called transition-rule memory. If no matching transition rule is found after accessing the transition-rule memory using the above mentioned hash function, then a default rule is used that is obtained by a lookup on a so called default-rule table that is indexed by the current input value. In a typical implementation, the default-rule table can store up to 256 different default rules. For a detailed description is referred to .
Typical DFAs, that have been created for pattern matching functions, contain many groups of states that share a set of transition rules, i.e., those transition rules involve the same input conditions and branch to the same next state. These `shared' or `common' transition rules can be regarded as a kind of local default transitions that apply to a given group of states. This in contrast to the conventional default-rule table, which contains default rules that can be regarded as `global' default rules that apply to the entire DFA. The presented idea allows to improve the storage efficiency by extending the B-FSM engine with a mechanism that exploits the local default rules by storing those only once instead of storing those separately for each state. Application of this new idea results in an extended B-FSM engine for which a block diagram is shown in Figure 1. In this figure, an additional transition-rule memory is added, which is denoted as default-rule memory, and which stores multiple sets of default rules that are compressed and accessed in the same way as the regular transition rules. The original default-rule table is now denoted as global default-rule table.
The default-rule memory is accessed in the same way as the regular transition-rule memory, based on a state vector, mask and table address (see ), which, in this case, are denoted as default state, mask and table address, and which are processed by a second address generator to generate the address at which the default-rule memory is accessed as shown in Figure 1. The data retrieved from the default-rule memory at the given address, is processed by the rule selector, which
Page 02 of 3
simultaneously compares all transition rules that are retrieved in parallel from the regular transition-rule memory and from the default-rule memory to select the...