Browse Prior Art Database

Advanced regular-expression matching with very high storage efficiency Disclosure Number: IPCOM000235721D
Publication Date: 2014-Mar-24
Document File: 3 page(s) / 53K

Publishing Venue

The Prior Art Database


A method for exploiting default transitions to improve the storage efficiency of a programmable state machine

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

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 [1]. 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 [1].

    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 [1]), 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...