Non-deterministic finite state machine module for use in a regular expression matching system

Patent metadata

Field	Value
Publication number	US-9983876-B2
Application number	US-201414184751-A
Country	US
Kind code	B2
Filing date	Feb 20, 2014
Priority date	Feb 22, 2013
Publication date	May 29, 2018
Grant date	May 29, 2018

Abstract

A non-deterministic finite state machine module for use in a regular expression matching system. The system includes a computational unit implementing a non-deterministic finite state machine representing a regular expression, wherein the computational unit is configured to: receive an input data stream, wherein an occurrence of the regular expression is determined, and an activation signal; process the input data stream with respect to the non-deterministic finite state machine depending on the activation signal; and provide at least one branch data output for initializing an additional non-deterministic finite state machine module if the processing of an element of the input data stream according to the non-deterministic finite state machine results in a branching of a processing thread.

First claim

What is claimed is:

1. A non-deterministic finite state machine module for use in a regular expression matching system, comprising:
a computational unit implementing a non-deterministic finite state machine representing a regular expression, wherein the computational unit is configured to:
receive an input data stream, wherein an occurrence of the regular expression is determined, and an activation signal;
process the input data stream with respect to the non-deterministic finite state machine depending on the activation signal;
indicate a start offset in the input stream of the regular expression match; and
provide at least one branch data output for initializing an additional non-deterministic finite state machine module if the processing of an element of the input data stream according to the non-deterministic finite state machine results in a branching of a processing thread;
wherein the non-deterministic finite state machine module allows for a scalable regular expression matching system to be computed in parallel;
wherein the at least one branch data output includes a branch flag output to provide a branch flag information to activate the additional non-deterministic finite state machine module;
wherein the at least one branch data output includes a branch configuration output to provide a branch configuration information including at least one branch offset information to forward an indication about a start offset of the input data stream or at least one capturing group start and end offset outputs to forward an indication about the start and end offsets of the at least one capturing group in the input data stream;
wherein the at least one branch data output include a match output information to indicate when a regular expression match occurs; and
wherein the at least one branch data output include a branch state information to provide an indication of a state to be processed next in the additional non-deterministic finite state machine module to be activated.

2. The non-deterministic finite state machine module according to claim 1 , wherein the computational unit is configured to provide a plurality of active data outputs for maintaining the processing thread of the computational unit, wherein the plurality of active data outputs comprise:
an active flag output to provide an active flag information to activate the additional non-deterministic finite state machine module;
an active configuration output to provide an active configuration information including at least one active offset information to forward an indication about a start offset of the input data stream and at least one capturing group start and end offset outputs to forward an indication about the start and end offsets of the at least one capturing group in the input data stream;
a match information to indicate when a regular expression match occurs; and
an active state information to retain an indication of a state to be processed next in the computational unit.

3. The non-deterministic finite state machine module according to claim 2 , wherein at least one of the following units is provided:
a logic gate receiving the active flag information and a load flag information at its input, so that the computational unit is or remains activated if at least one of the active flag information and the load flag information is set; and
a configuration register either to retain an active configuration output stored for the processing thread performed in the computational unit or to store an externally provided branch configuration output, depending on the load flag information.

4. A routing network for use with a plurality of non-deterministic finite state machine modules in a regular expression matching system, comprising:
a plurality of input ports, each associated with one of the plurality of non-deterministic finite state machine modules;
a plurality of output ports, each associated with one of the plurality non-deterministic finite state machine modules;
wherein the plurality of input ports are configured to receive a branch data output from the associated one of the plurality of non-deterministic finite state machine modules, respectively;
wherein the plurality of input ports each include a branch flag input to receive the branch flag information indicating that one of the plurality of non-deterministic finite state machine modules is activated;
wherein the plurality of input ports each include a branch configuration input to receive a branch configuration output;
wherein the plurality of output ports are configured to activate the associated one of the plurality of non-deterministic finite state machine modules and forward the branch data output thereto depending on a branch flag information;
wherein the non-deterministic finite state machine module allows for a scalable regular expression matching system to be computed in parallel;
wherein the branch configuration output provides a branch configuration information including at least one branch offset information to forward an indication about a start offset of the input data stream or at least one capturing group start and end offset outputs to forward an indication about the start and end offsets of the at least one capturing group in the input data stream; and
wherein the routing network is configured to select, for each received branch data output indicating that an inactive non-deterministic finite state machine module is activated, one of the plurality of non-deterministic finite state machine modules which is inactive; and to forward the respective branch data output to the respective output port associated with the selected one of the plurality of non-deterministic finite state machine modules.

5. The routing network according to claim 4 , comprising a first network which is configured to perform a pack operation and a second network which is configured to perform an unpack operation.

6. The routing network according to claim 5 , wherein the first network is a reverse butterfly network or wherein the second network is a butterfly network.

7. The routing network according to claim 4 , wherein the routing network is configured to perform a routing operation using a reverse butterfly processing, and wherein according to a given packing scheme one of the plurality of non-deterministic finite state machine modules is selected for each active and each to be activated one of the plurality of non-deterministic finite state machine modules wherein configuration information of each of the active and each of the to be activated ones of the plurality of non-deterministic finite state machine modules are copied into the associated one of the plurality of non-deterministic finite state machine.

8. The routing network according to claim 4 , wherein the plurality of output ports each comprise:
a load flag output to output a load flag information to the one of the plurality of non-deterministic finite state machine modules associated with the respective output port; and
a load configuration output to output a load configuration information.

9. A regular expression matching system, comprising:
a plurality of non-deterministic finite state machine modules for use in a regular expression matching system, comprising:
a computational unit implementing a non-deterministic finite state machine representing a regular expression, wherein the computational unit is configured to:
receive an input data stream, wherein an occurrence of the regular expression is determined, and an activation signal;
process the input data stream with respect to the non-deterministic finite state machine depending on the activation signal; and
provide at least one branch data output for initializing an additional non-determinis

Assignees

• IBM

Inventors

• Atasu Kubilay
• Hagleitner Christoph
• Polig Raphael
• Reiss Frederick R

Classifications

• G06F9/444

  Physics · mapped topic

• G06F9/38 Primary

  Concurrent instruction execution, e.g. pipeline or look ahead · CPC title

• G06F9/4498 Primary

  Finite state machines · CPC title

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title