TCS -TR-A-10-45

TCS Technical Report

Dynamic Reconﬁgurable Bit-Parallel Architecture forLarge-Scale Regular Expression Matchingby

Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi
Minato, Hiroki Arimura, and Yoshikazu Miyanaga

Division of Computer Science
Report Series A
June 29, 2010

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arim@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7680+81-011-706-7680

Dynamic Reconfigurable Bit-Parallel Architecture
for Large-Scale Regular Expression Matching
Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, and Yoshikazu Miyanaga
Graduate School of Information Science and Technology, Hokkaido University
N14, W9, Sapporo 060-0814, Japan{y-kaneta,minato,arim,miya}@ist.hokudai.ac.jp
yosizawa@csm.ist.hokudai.ac.jp

Abstract—In this paper, we propose a novel FPGA-basedarchitecture for large-scale regular expression matching, called
dynamic reconfigurable bit-parallel NFA architecture (dynamic
BP-NFA) that allows dynamic reconfiguration of the patterns
using bit-parallel NFA-simulation approach. This is the first
dynamic reconfigurable FPGA-based hardware with guaranteedperformance for the class of extended patterns, where a extended
pattern is a restricted regular expression in linear form consistingof letters, classes of letters, don’t cares, optional letters, bounded
and unbounded length gaps and repeatable letters. The key of ourarchitecture is the use of bit-parallel pattern matching approachthat have been developed in string matching communities for the
decades. In this approach, the information of an input NFA is
compactly encoded in bit-masks stored in a collection of registers
and block RAMs. Then, the NFA is efficiently simulated bya fixed circuitry using a combination of bit- and arithmeticoperations on these bit-masks consuming one input letter per
clock. As compared with previous approaches of DFA-based
dynamic reconfigurable architectures, experimental results showthat the proposed architecture achieves higher throughput forthe class of exact string patterns and comparable for the classof extended patterns.

I. Introduction
A. Backgrounds
By rapid growth of network and sensor technologies, massive
data of new types, called data streams, and related applications
have emerged in various fields including networks and dataengineering. ESP (Event Stream Processing) [1] and NIDS
(Network Intrusion Detection System) [3] are example applications of data stream processing. Consequently, efficient data
stream processing technologies have been extensively studied
in theory and practice. The large-scale pattern matchingproblem is one of the most important problems in data stream
processing, where a pattern matching system has to work witha large number of complex regular expressions against highspeed data streams.
These problems are, however, quite CPU-intensive tasks andit is difficult for a software on CPU to efficiently process
massive data streams real time in wire-speed. Therefore,
researches on large-scale regular expression matching on reconfigurable hardwares such as FPGA have attracted muchattention recently.

B. Related works
A recent research trend to large-scale regular expression
matching hardwares is to simulate finite state automata for
a given class of regular expressions on a specially designed
hardware ([3], [4], [9], [11], [12], [14], [15], [16]). Then,
this approach is further classified into the static compilation
approach and the dynamic reconfiguration approach.
In the static compilation approach ([11], [12], [14], [15],[16]), a set of input regular expressions are transformed intoeither deterministic finite automata (DFA) or non-deterministic
finite automata (NFA), and then statically compiled into wired
logic on FPGA. However, the static compilation approach has
a drawback that modification of regular expressions is too
expensive to be done frequently.
In the dynamic reconfiguration approach ([3], [4], [9]),a universal control logic is statically compiled into FPGA
beforehand, a description of regular expressions is loaded to
the FPGA as data in preprocessing time, and then simulated inrun-time [3], [4], [9]. This approach is attractive in real world
applications such as EPS and NIDS where reconfiguration of
input patterns frequently occurs. However, classes of patterns
that can be dealt with in this approach are still limited, it
is a challenging task to design dynamically reconfigurable
hardwares that efficiently run for wider classes of regularexpressions.

C. Main result of this paper
In this paper, we propose a novel architecture based on
simulation of NFAs tailored for large-scale regular expression
matching on FPGA, called dynamic reconfigurable bit-parallelarchitecture (dynamic BP-NFA). The key of this architectureis the use of bit-parallel pattern matching approach developed
in string matching communities since 1990 [2], [10], [13].
As a main result, we present a hardware based on thisapproach for a subclass EXT of regular expressions, called
extended patterns, which are regular expressions in linear
form consisting of letters α, wildcards ’.’, classes of letters[ab · · · ], optional letters α?, bounded and unbounded repeats
α{x, y} and α∗ . For example, R = [AB]+ B.{1, 3}[BC]?.∗ C isan example of extended patterns.

In our approach, input extended patterns are translated into
an input NFA, and the information of the NFA is compactly
encoded in a set of bit-masks stored in 32-bit registers andblock RAMs, when the underlying register length is 32 bit.
Then, the NFA is efficiently simulated by a fixed circuitry
using a set of 32-bit Boolean operations and a 32-bit integer
addition on the registers and RAMs. As analysis, we showthat this hardware correctly matches a given set of extended
patterns against an input text consuming one input letter per
clock regardless of the contents of the input.
Compared with the previous dynamic reconfigurable DFAbased approaches, the throughput 2.9 Gbps of our hardware
is much higher for class STR and the throughput 1.6 Gbps iscomparable for class EXT, while it uses comparable hardware resources in FPGA implementation. An advantage of
our architecture is the worst performance guaranteed by thedesign compared with DFA-based architecture with microcontroller [3]. Another advantage is the potential extensibility
for more general pattern classes. For example, Kaneta et al. [7]recently extended the Extended SHIFT-AND method, usedin this paper, for a more general class of acyclic regularexpressions allowing union and Kleene-plus. Such method
can be incorporated into our architecture by extending theconstruction of masks and a circuitry.
This paper is organized as follows. In Section II, we givebasic definitions. In Section III, we propose our architecture,and in Section IV, we give the detailed description of eachpattern matching module. In Section V, we give experimental
results, and in Section VI, we conclude.

II. Preliminary
A. Regular expression matching
Let N = {0, 1, 2, . . .} be the set of all non-negative integers,and Σ = {a, b, . . .} be a finite alphabet of letters. A string on
Σ is a sequence S = s1 · · · sn of letters, where S[i] = si ∈ Σfor every 1 ≤ i ≤ n. We denote by S[i..j] the substringsi · · · sj for every i ≤ j, and by ε the empty string. If i > j,
we define S[i..j] = ε. For a set S ⊆ Σ∗ of strings, we denote
by |S| the cardinality and ||S|| = Σs∈S |s| the total size of S.
We denote by Σ∗ the set of all strings on Σ. For a letter a ∈ Σ
and a integers i ∈ N, we define by ai a string consisting ofi-consecutive a.
Let REG be the class of regular expressions on Σ. Moreprecisely, a regular expression R is either a letter a ∈ Σ,
concatenating R = R1 · R2 , union R = (R1 |R2 ), andthe Kleene-star R = (R1 )∗ , where R1 and R2 are regularexpressions [10]. For a regular expression R ∈ REG, wedenote by L(R) ⊆ Σ∗ its language. Let T = t1 · · · tn ∈ Σ∗ bean input text of length n ≥ 0, where ti ∈ Σ (1 ≤ i ≤ n).
A pattern is a regular expression on Σ. We say a regularexpression R = r1 · · · rm ∈ REG occurs at end position j
in T , if T [i..j] = ti · · · tj ∈ L(R). Our problem is stated asfollows.
Definition 1. The multiple pattern matching problem fora subclass of regular expressions REG is defined as follows. An input is an input pattern set P = { (i, Ri ) | i =1, . . . , N } (N ≥ 1), where for every i = 1, . . . , N , Ri is apattern and i is an integer, called an index. Then, the task is,given a stream T = t1 t2 · · · tp · · · (p ≥ 1) of input letters,
to output the pairs (p, i) such that p is an end position of apattern Ri in T for all p = 1, 2, . . . and i = 1, . . . , N .

B. Target pattern class: Extended patterns
The target subclass of regular expressions that our architecture
deals with is the class of extended patterns defined as follows.
In what follows, ≡ means the notational equivalence.
Definition 2. The class of extended patterns, denoted by EXT,
is a subclass of regular expressions defined as follows: anextended pattern R on Σ is a sequence of some components
R = r1 · · · rm (m ≥ 0), where for each 1 ≤ i ≤ m, ri is
an expression, called a component, with one of the following
forms:(1) A letter ri = a ∈ Σ is a component with the languageby L(a) = {a}.
(2) A don’t care ri = . is a component with the language
L(.) = Σ. This matches any letter in Σ.
(3) A class of letters ri = β is a component, where β ⊆Σ, with the language L(β) = β. As notation, we write[ab · · · ] for β = {a, b, . . .}. Note that a letter a ∈ Σ anda don’t care symbol ’.’ are a class of letters.
(4) An optional letter ri = β? is a component, where β ⊆ Σis a class of letters, and β? ≡ (β|ε).
(5) Bounded repeats ri = β{x, y}, ri = β{, y}, andri = β{x} are components with equivalence β{x, y} ≡(β?)y−x β x , β{, y} ≡ (β?)y , and β{x} ≡ β x , respectively, where β ⊆ Σ and x ≤ y (x, y ∈ N). If β is a
don’t care ’.’ then ri is called a bounded length gap.
(6) Unbounded repeats ri = β ∗ and ri = β + are components, where β ⊆ Σ is a class of letters, and β + = ββ ∗ .
If β is a don’t care ’.’ then ri is called a variable length
don’t care (VLDC).
For R = r1 · · · rm , we define its language by L(R) =L(r1 ) · · · L(rm ). If a component ri is one of the forms β?,β{x, y}, β ∗ , and β + , then β is called the matrix of ri .
Example 1. We show examples of extended patterns.
• R1 = ABABC.
+∗• R2 = [AB] B.{1, 3}[BC]?. C.
∗+• R3 = (A[BC] ).{, 4}((DE) ).
We say that R is an exact string patterns (also called astring pattern), denoted by STR, if every component ri of an
extended patterns R = r1 · · · rm is a letter in Σ such as R1 .

III. Proposed Architecture
In this section, we present our dynamic reconfigurable bitparallel architecture, dynamic BP-NFA, based on simulationof NFAs using bit-parallel pattern matching technique.

PMMN
PMM4
PMM3
PMM2

Bit-masks Block

Input Packet(Preprocessing or
Run-time packet)

Make α-Trans
Block
Mask
EpsEND register
ACCEPT
register
NFA
Data
State
EpsBLK register
ACCEPT
registerNFAREPPOS
Make ε-TransSTATE
registerStateBlock
block RAM
INITACCEPT
register register
NFA
STATE register
NFA State (updated)
State
ACCEPT
register
STATE register NFA
Test Match
Input Letter
NFA State (updated)
State
Block
STATE register
Input Letter
NFA State (updated)

N

OutputEncoder64

Output PacketϬ ϭControl
Signals
ModuleId
Comparators
Module Id
Comparators
Module Id
Input
Comparators
LetterModule Id
Comparators
PacketDecoderMatching Block

EpsBEG register

MOVE
block RAM

ϭ64

EmitMatchϬ

Input
Decoder

Ϭ ϭ

64

Ϭ ϭ

Control block
Input Packet

PMM1

Pattern Matching Module

Mask
Data

Input Letter

NFA State (updated)

Input Letter
Preprocessing mode

Fig. 1.

Run-time mode

N: the number of PMMs

The top-level architecture of our pattern matching hardware for extended patterns
TABLE IThe meaning of fields in a preprocessing packet

A. Top-level architecture
In Fig. 1, we show the top-level architecture of our patternmatching hardware. The hardware consists of the input decoder, a collection of pattern matching modules (PMM, forshort), and the output encoder as submodules.
The hardware runs with two different modes: the preprocessing mode and the run-time mode. It communicates theoutside environment (a host PC) through a sequence of I/O
packets of 64 bit length which are received and sent by the
input decoder and output encoder.

B. Preprocessing and Run-time packets
I/O packets in all types have 64 bit length and start with the
Opcode field of 4 bit length. I/O packets are classified into
the following types according to Opcode field: no-operation(0000), preprocessing (0001), and run-time (0010). In
Fig. 2, we show the bit layout of the preprocessing and runtime packets.
31

0
Opcode Mask Id Mask Address(4bit) (4 bit)
(8 bit)Module Id(16 bit)

63
Opdata(32 bit)31

0
OpCode(4bit)

Not used(28 bit)Fig. 2.

63
Not used(24 bit)

Input Letter(8bit)

The formats of the preprocessing and run-time packets

A preprocessing packet is an I/O packet with opcode 0001
(preprocessing) (Fig. 2). Then, the meaning of each field of apreprocessing packet is given by the following table.
A run-time packet is a packet with opcode 0010 (run-time)of the form shown in Fig. 2. Then, the first 32 bits containthe Opcode (4 bit) only and the remaining 32 bits containthe input letters in the Opdata field (32 bit). In present
implementation, just 8 bit (one letter) in the Opdata field
is used.
Received by the input decoder, an input packet is copies
and delivered to all pattern matching modules. Each module

Field
OpcodeMask Id
Mask Addr
Module Id
OpdataLength (bit)
4
4
8
16
32

Meaning
The type of a packet
The name of the destination bit-mask
An index of a line in a block RAM
The id of the destination pattern matchingmodule
The content of a single bit-mask to deliverP M Mi has its own decoder and decodes the fields of thereceived packet, where 1 ≤ i ≤ N .
In the preprocessing mode, a host sends to the hardware only preprocessing packets. If its ModuleId field isidentical to its own module id, namely i, then the module
P M Mi stores the contents of the Opdata field at a registerwith name MaskId or a line MaskAddress of a block
RAM with MaskId according to the values of MaskId and
MaskAddress.
In the run-time mode, a host send to the hardware only runtime packet to feed input letters of an input stream. Then, thereceived run-time packet is delivered to all pattern matchingmodules, and an input letter as Opdata is extracted andprocessed by each module P M Mi .

C. Emission of match results
The output-encoder is a module consisting of a priority
encoder [5] and a FIFO to keep the ids of matched patterns
that report the match information to the outside environment
using an output packet. An output packet is a packet of 64
bit length that contains two pairs of a ModuleId field (16bit) and a field (16bit) for additional information such as thecurrent time stamp. In the preprocessing mode, the outputencoder does nothing. In the run-time mode, if matching ofa pattern Pi is detected, an EmitMatch signal (1 bit) is
emitted from module P M Mi to the output-encoder. Then, thecorresponding pattern id i in binary is pushed into the FIFO,

8
Input
Letter

WE 32
WN
INIT
WD
RD

CLK

WE

A

RD
MOVE
(block RAM)WD
Bit-mask

Fig. 3.

32
32

E

CLK

Test Match Block

E

State
Init

Make α -transition Block
32
32
<<䠍
32
32
32
KZ

Ϭ ϭ

Runtime
En
32
CLK
32
WE 32
STATE
32
WD
RD

0

32
CLK

32

1

≠

Emit
Match

32

WE
ACCEPTWD
RD
Bit-mask

The circuit of a pattern matching module for exact string patterns

Σpacked into an output packet, and then sent to a host in eachclock.

0Fig. 4.

A

1

B

2

A

3

B

4

C

5

The pattern NFA of a string pattern R1 = ABABC.

IV. Pattern matching module
A pattern matching module, PMM, is a core of our patternmatching hardware, and is responsible for simulation of a
specified input pattern with fixed length, say, 32 letter length.
In what follows, we assume registers and block RAM of 32
bit length.

A. Components of a module
In the middle of Fig. 1, we show a single unit of a patternmatching module, PMM. A pattern matching module consistsof three subunits: a decoding unit for delivery of masks (thecontrol block), a memory unit for storing bit-masks (the bitmasks block), and a control logic for NFA-simulation (thematching block).
Before entering detailed description of a PMM, we giveassumptions. The precise parameters setting depends on theactual class of patterns we target. We assume that an input
alphabet is Σ = {0, . . . , 255}, and thus, the width of an input
letter is 8 (bit). We also assume that the register length is L =32, which typically varies from 32 to 128 (bit). Then, eachpattern matching module, PMM, has a number of registers
and block RAMs of the same bit-length L. For each bit-masks,
MSB (LSB, resp.) comes at the left end (at the right end, resp.).
A basic idea of bit-parallel pattern matching is to firstly
transform a given extended pattern into a special NFA having
linear shape, secondly to build a set of bit-masks from thetransition functions of the NFA, and finally, to make NFAsimulation on the bit-masks using by a fixed control logic
designed to the target class of patterns. In the followings, wegive the detailed description of our architecture step by step
starting from simpler to more complex classes of patterns.

B. Simulation: Exact string pattern
We start with explaining the construction for the simplest classof exact string patterns according to SHIFT-AND method [2],[13] as follows. It consists of the definition of a set of bitmasks and a control logic for NFA-simulation. An exact
string pattern (also called a string pattern) is just a string
P = r1 · · · rm of m letters, where m ≤ L and ri = ai ∈ Σ
is a constant letter for every i = 1, . . . , m. For example,
we consider the string pattern R1 = ABABC in the following
explanation.
Construction of NFA. Then, the corresponding NFA NR =N (R) for a string pattern, called a pattern NFA, consists onlyof the backbone consisting only of m letter transitions. For
example, we show in Fig. 4 the pattern NFA N1 = N (R1 ) corresponding to the exact string pattern R1 . Precisely speaking,the NFA is given by the tuple NR = (Σ, Q, δ, q0 , qf ), which
has the state set Q = {0, 1, . . . , m}, the initial state q0 = 0, thefinal state qf = m. The transition relation δ ⊆ Q×(Σ∪{ε})×Q
is the set of directed letter edges {(i−1, ai , i) | i = 1, . . . , m},called the backbone of NR .
Construction of bit-masks. To simulate the pattern NFA
for an exact string pattern, we use three types of L-bit masks
IN IT , ACCEP T and an array M OV E[a] ∈ {0, 1}L (a ∈Σ) of bit-masks defined as follows:• IN IT is the L-bit mask that sets 1 at the bit-position
corresponding to the initial state. That is, IN IT [i] = 1
if and only if i = 0.
• ACCEP T is the L-bit mask that sets 1 at the bit-position
corresponding to the final state. That is, ACCEP T [i] =1 if and only if i = m − 1.
• M OV E[a] is the L-bit mask that indicates all bitpositions of backbones labeled with a letter a in R. That

Feed back to STATE register
Make α -transition BlockWE
ACCEPT
WD
RD

32

RD
MOVE
(block RAM)32

bitmaskWE

RD

REPPOS(block RAM)

Fig. 5.

32

WD

EpsEND

WE
32
RD

WD

EpsBEG

WE
32
RD

1

Σ

[BC]

CLK

CLK

CLK
WE
32
EpsBLK
RD
WD

WD

Test Match
block

CLK

WD

A

32

32

E

32

32

KZ

A

CLK
8

32

32

CLK

Input
Letter

32

32

yKZ

32

32

KZ

WE

KZ

INIT

WE 32
RD

^h

WD
8

32

E

32

E

State
Init

KZ

<<䠍

32

CLK

Make ε-transition Block

32

Ϭ

ϭ

Runtime
EN
32
CLK
32
WE 32
STATE
32
WD
RD

Emit
Match

The circuit of a pattern matching module for extended patterns

is, M OV E[a][i] = 1 if and only if the state i has abackbone labeled with a ∈ Σ, or equivalently, ri = a.
We store the bit-masks IN IT and ACCEP T in L-bit
registers, and the array (M OV E[a])a∈Σ in a block RAM with
Σ L-bit entries each having a single read and write ports.
Control logic for NFA-simulation. Based on SHIFT-AND
method ([2], [10], [13]), the control logic in the matching
block is, then, given by the following code, where t ∈ Σis the current input letter:
ST AT E ← ((ST AT E << 1) | IN IT ) & M OV E[t];The acceptance test is given by the following code:
if (ST AT E & ACCEP T ) then EmitM atch ← 1;
By the above construction, we can implement the control
logic for the NFA-simulation by a circuit in Fig. 3 by using
five L-bit Boolean operations, three L-bit registers, and one
block RAMs with Σ L-bit entries each having a single read
and write ports.

C. Simulation: Extended patternNow, we show the construction of PMM for extended pattern matching according to Extended SHIFT-AND methods(Chap. 4, Navarro and Raffinot [10]) as follows.
Expanded form and bit-assignment. Let R be an extended
pattern. Then, recall that every component ri of R has one of
the following types: (i) ri = β, (ii) ri = β?, and (iii) ri = β ∗ ,(iv) ri = β + , and (v) ri = β{x, y}, where β ⊆ Σ. We expand
all occurrences of bounded repeats ri = β{x, y} of type (v)in R by using the equivalence β{x, y} ≡ (β?)y−x β x , wherex ≤ y. Let E XPAND(R) = r1 · · · r be the resulting extended
pattern consisting of m components, where  ≤ L. By construction, the resulting E XPAND(R) contains no occurrences ofcomponents of type (v). Then, we assign the unique numbers
1, · · · , , called the bit-positions, to all components r1 , . . . , r .

Σ

[AB]
[AB]
B
0
1

Fig. 6.

Σ
2

Σ
ε

3

ε

4

Σ

5

ε

6

Σ
ε

7

C

8

The extended pattern NFA of R2 = [AB]+ B.{1, 3}[BC]?.∗ C.

For example, let R2 = [AB]+ B.{1, 3}[BC]?.∗ C be
the target extended pattern consisting of six components. Then, by replacing the bounded gap .{1, 3} with(.?)(.?)(.), we obtain its expanded version E XPAND(R2 ) =([AB]+ )(B)(.?)(.?)(.)([BC]?)(.∗ )(C) consisting of eight components with assigned bit-positions from 1 to 8.
Construction of NFA. Then, we obtain the pattern NFA
N (R) for R from the expanded version E XPAND(R) as
follows. Let E XPAND(R) = r1 · · · rm for some m ≥ 1 andL be an positive integer larger than or equal to than m. L
is acturally the length of regsiters in an underlying hardware.
By construction, we can assume that E XPAND(R) contains
components of only type (i)–(iv). For every i = 1, . . . , m, we
add to the NFA N (R) the letter edges and ε-edges related tothe state i according to the type of the i-th component ri withmatrix β as follows:• For all types (i) – (iv) of ri , we add the backbone edge
ei = (i − 1, β, i) directed from the state i − 1 to the statei labeled with matrix β.
∗• Furthermore, if ri is either (ii) β? or (iii) β , then we
add an ε-edge directed from the previous state i − 1 tothe current state i.
∗+• Furthermore, if ri is either (iii) β or (iv) β , then we
add a self loop labeled with matrix β from the current
state i to itself.
For example, we show in Fig. 6 the extended pattern
NFA N1 = N (R2 ) corresponding to the extended pattern E XPAND(R2 ).
For the expanded version E XPAND(R) of an extended

pattern, an ε-block in E XPAND(R) is a maximal consecutive
subsequence ri · · · rj , where a component ri is ri = βi ? orri = βi∗ for some i ≤ j. Let us denote by B1 , . . . , Bh (h ≥ 0)
the ε-blocks of E XPAND(R), where Bj ⊆ {1, . . . , L} is the setof bit-positions of the j-th ε-block. For example, E XPAND(R2 )has two ε-blocks B1 = {3, 4} and B2 = {6, 7} corresponding
to r3 r4 = (.?)(.?) and r6 r7 = ([BC]?)(.∗ ), resp.
Construction of bit-masks. To simulate an extended pattern NFA NR = N (R) for an extended pattern, we use Lbit masks EpsBEG, EpsEN D, EpsBLK, and the array
REP P OS[a] ∈ {0, 1}L of bit-masks in addition to the bitmasks IN IT , ACCEP T , and M OV E[a] ∈ {0, 1}L (a ∈ Σ)
which are already defined in the previous subsection. For an
L-bit mask, we identify each ε-block and the corresponding
consecutive sequence of bit-positions in {1, . . . , L}.
EpsBLK is the L-bit mask that sets 1’s at all positions
in every ε-block. That is, EpsBLK[i] = 1 if and only if
i is contained by some ε-block Bk .
• EpsBEG is the L-bit mask that sets 1 at the previous
position of the lowest bit-position of every ε-block. That
is, EpsBEG[i] = 1 if and only if i = min(Bk ) − 1 forsome ε-block Bk .
• EpsEN D is the L-bit mask that sets 1 at the highest
bit-position of every ε-block. That is, EpsEN D[i] = 1
if and only if i = max(Bk ) for some ε-block Bk .
• REP P OS[a] is the L-bit mask that indicates all
bit-positions of self-loops labeled with a letter a in
E XPAND(R). That is, REP P OS[a][i] = 1 if and only
if the state i has a self-loop labeled with a ∈ β, or
equivalently, either ri = β ∗ or ri = β + with a ∈ β.
•

In Fig. 8, we show an example of the bit-masks for
R2 = [AB]+ B.{1, 3}[BC]?.∗ C. As in the previous case, we store
the bit-masks IN IT , ACCEP T , EpsBEG, EpsEN D, andEpsBLK in L-bit registers, and the arrays (M OV E[a])a∈Σ
and (REP P OS[a])a∈Σ in block RAMs.
Control logic for NFA-simulation. Based on bit-parallel
method, we finally give the control logic for NFA-simulation.
Fig. 5 shows the whole circuit of NFA-simulation for extended
pattern matching. In the following, we give the computer codefor the control logic this circuit for NFA-simulation, which is
the modified version of the code in Navarro and Raffinot [10].
we note that t = ti ∈ Σ is the current input letter in an input
text.
Firstly, the next code initializes the state mask at line(1), make a letter transition at line (2), and apply the lettertransitions by self-loops at line (3):ST AT E ←(((ST AT E << 1) | IN IT )& M OV E[ti ])| (ST AT E & REP P OS[ti ]);

(1)
(2)
(3)

Then, the sequence of the following codes simulate the ε-Bit-positions

1

2

3

R2

[AB]+
[AB]+

B
B

.{1, 3}.? .? .

E XPAND(R2 )

4

5

6

7

8

[BC]?
[BC]?

.∗
.∗

C
C

Fig. 7. The bit-position assignment for R2 = [AB]+ B.{1, 3}[BC]?.∗ C and
its expanded version E XPAND(R2 ).

Bit-position i

1

2

3

4

5

6

7

8

IN IT

1

0

0

0

0

0

0

0

ACCEP T

0

0

0

0

0

0

0

1

M OV E[A]M OV E[B]M OV E[C]M OV E[%]

1
1
0
0

0
1
0
0

1
1
1
1

1
1
1
1

1
1
1
1

0
1
1
0

1
1
1
1

0
0
1
0

REP P OS[A]REP P OS[B]REP P OS[C]REP P OS[%]

1
1
0
0

0
0
0
0

0
0
0
0

0
0
0
0

0
0
0
0

0
0
0
0

1
1
1
1

0
0
0
0

EpsBEG

0

1

0

0

1

0

0

0

EpsEN D

0

0

0

1

0

0

1

0

EpsBLK

0

0

1

1

0

1

1

0

Fig. 8. The set of masks for R2 = [AB]+ B.{1, 3}[BC]?.∗ C on alphabet
Σ = {A, B, C}, where the symbol ’%’ denotes any letter not in Σ.

transitions with the state mask:
HIGH ← ST AT E | EpsEN D;(4)

LOW ← HIGH − EpsBEG
ST AT E ← (EpsBLK & ((∼ LOW ) ⊕ HIGH))

(5)
(6)

| ST AT E;(7)

The meaning of the above code is explained as follows. At
line (4), we turn on the highest bit (the end bit) of each εblock of the mask ST AT E, and set it to HIGH. At line (5),for each ε-block in HIGH, we invert all bits lower than orequal to the lowest 1 bit in HIGH and set it to LOW . At line(6), the mask (EpsBLK & ((∼ LOW ) ⊕ HIGH)) has bit
1 at all bit positions properly higher than the lowest 1 bit in
ST AT E. Finally, we add the change to the mask ST AT E atline (7). The acceptance test ST AT E & ACCEP T is same
as exact pattern matching.
In Fig. 9, we show an example of NFA-simulation by theset of bit-masks for R2 = [AB]+ B.{1, 3}[BC]?.∗ C on an input
text T = ABCBBC. In the figure, we show the status of the
bit-mask ST AT E after the update in each cycle i (1 ≤ i ≤ 6).
By the above construction, we can implement the control
logic for the NFA-simulation by a circuit shown in Fig. 5 byusing eleven L-bit Boolean operations, one L-bit subtraction,
six L-bit registers, and two RAMs with Σ L-bit entries eachhaving a single read and write ports.
Theorem 1. For the class EXT of extended patterns, ourhardware consumes one input letter per clock regardless ofthe content of the input text T . Furthermore, its combinatorial

TABLE II
Summary of parameters of the proposed pattern matching hardwares, where #Op, #Add, #Reg, #BL, and #Slice, are the numbers of 32 bit operations, 32 bit
integer additions, registers, block RAM lines, resp., per PMM. #Patterns and #Chars Total are the number and the total size of input patterns, resp.

.

Class of Patterns
Exact string patterns
Extended patterns

Cycle
i

Input
letter ti

1
2
3
4
5
6

A
B
C
B
B
C

#Op #Add50111#Reg #BL #Slice
3 256
54
6 512
123

ST AT E after update in cycle i
1 2 3 4 5 6 7 8
1
1
0
1
1
0

0
1
0
0
1
0

0
1
1
0
1
1

0
1
1
1
1
1

0
0
1
1
1
1

0
0
1
1
1
1

0
0
1
1
1
1

0
0
0
0
0
1

Freq
363 MHz
202 MHzEmit
M atch000001Fig. 9. An example of extended pattern matching, given an extended pattern
R2 = [AB]+ B.{1, 3}[BC]?.∗ C and an input text T = ABCBBC.

circuit for state update in Fig. 5, excluding registers andRAMs, has O(log L) depth and O(L3 ) gates, where L is thelength of a register.
Proof: The circuit in Fig. 5 contains one L-bit adderand constant number of L-bit bitwise Boolean gates, a Lbit multiplexer and a L-bit comparator. It is well known thatan L-bit adder can be implemented in O(log L) depth using
O(L3 ) gates. Since the other L-bit gates can be implemented
in constant depth and O(L) 1-bit gates, we have the claimed
complexities. Since any cycle on the data paths contains at
most one register or a RAM, the result is prove.

V. Experimental results
To evaluate the time and area complexities, we implemented
our pattern matching hardwares in Verilog HDL for bothclasses of exact string patterns STR (Sec. IV-B) and extended
patterns EXT (Sec. IV-C), where the register length L is
set to L = 32 and the arrays M OV E and REP P OS are
implemented in block RAMs. We targeted the Virtex-5 LX330
with -1 speed grade, which has 51,840 slices and 288 block
RAMs with 36 Kbits. We use the Xilinx ISE Design Suite
10.1 and Synopsys VCS development tools.
Summary of our hardwares. In Table. II, we show thesummary of the experimental results of a single pattern matching module, PMM, in our pattern matching hardwares. The
number of block RAM lines (#BL) is given by the number ofblock RAMs times |Σ| = 256.
Resource usage. For the area complexity, in the experiments, we could implement up to 256 PMMs (8, 192 total
letters) and up to 128 PMMs (4, 096 total letters), for STR
and EXT, respectively. In this setting, the place-and-route tookaround one hour in both classes. For EXT, one PMM uses 123
slices (787 logic cells) and two block RAMs (512 = 2×256
lines are used). Consequently, the usage of block RAMs was

Throughput Load Time Total #Patterns #Chars Total
2.9 Gbps
0.182 msec
256 8,192 letters
1.6 Gbps
0.328 msec
128 4,096 letters

89%, while the usage of slices was only 24%. This meansthat the size of a hardware in our architecture is constrained
mainly by the amount of block RAMs and not by one of theslices. In Fig. 10, we show the dependency of the number ofslices against the number N of PMMs, where the number ofslices is proportional to N .
Performance evaluation. The maximum frequencies of ourhardwares were 363 MHz and 202 MHz, resp., for STR and
EXT. For the time complexity in run-time, we estimate thethroughput of matching by Throughput = Freq × 8 (bit/sec).
Thus, the throughputs were 2.9 Gbps and 1.6 Gbps since ourhardwares consume one letter (8 bit) per clock. In Fig. 11, we
observe that the throughputs for STR and EXT is constantregardless of N .
On dynamic reconfiguration, we estimate the total loading
time of input patterns by Load Time Total = #Patterns ×(#Reg + #BL)/Freq (sec). Thus, a PMM took 0.71 μsec and2.56 μsec to load an input pattern, and consequently, the totalloading times were 0.182 msec and 0.328 msec to load 256
and 128 patterns for PAT and EXT, resp. As comparison, we
implemented a hardware in the static compilation approachbased on SHIFT-AND method [2] for STR on Xilinx Virtex-5
LX50 with 7,200 slices. This hardware achieves frequency 216
MHz and throughput 1.7 Gbps using 2,925 slices and no block
RAMs. As the loading time, the compilation required 4.27×105
msec, approximately seven minutes, for 300 patterns with total
size 3,963 letters. Hence, the dynamic reconfiguration is 106
times faster than the static compilation in this case.
Comparison against other regular expression matching hardwares. In Table. III, we compared our hardware,dynamic BP-NFA, against the previous DFA-based dynamic
reconfigurable hardwares [3], [4], [6]. For the class of exact
string patterns, our hardware for STR achieves throughput
of 2.9 Gbps higher than 1.8 Gbps by Baker et al.’s KMPbased hardware [4] and 1.6 Gbps by Jung et al.’s Bitsplitbased hardware [6]. For more complex classes of regularexpressions, our hardware achieves 1.6 Gbps for the class EXTof extended patterns, while Baker et al.’s RegExp Controller
hardware [3] achieves 1.4 Gbps for their target subclassof regular expressions, which will be explained below. On
resource usage, it seems that our hardware uses ten times morelogic cells (slices) than RegExp Controller hardware, while theformer uses less block RAM lines than the latter.
Note that Baker et al.’s RegExp Controller hardware is ahybrid of DFA simulation and microcontroller [3] and has been
only dynamic reconfigurable architecture for a subclass ofregular expressions before ours, where each regular expression
can be expressed with a small DFA and a few number of un-

TABLE III
Results comparisons of regular expression matching hardwares based on various dynamic reconfigurable architectures, where Class is the target class of
input patterns, bRAM/char is the number of bytes used in block RAMs per letter, and Logic Cells/char is the number of logic cells used per letter. STR,
EXT, and REG stand for the classes of exact string patterns, extended patterns, and regular expression, resp.

DesignClass Device
Throughput bRAM/char Logic Cells/char #Chars Total Remarks
Dynamic BP-NFA for STR (ours) STR Virtex-5 LX300 2.9 Gbps 4 bytes/char
10.88192 54 slices
Dynamic BP-NFA for EXT (ours) EXT Virtex-5 LX300 1.6 Gbps 8 bytes/char
24.6
4096 123 slices
KMP-based hardware [4]STR Virtex-II Pro
1.8 Gbps 4 bytes/char
3.2
3200
NA
Bitsplit-based hardware [6]STR Virtex-4
1.6 Gbps 46 bytes/char
1.4
16715
NA
RegExp Controller hardware [3]
REG Virtex-4 FX100
1.4 Gbps 46 bytes/char
2.56
16715
NA

7KHQXPEHURIVOLFHV
QXPEHURIVOLFHVV

300VIRUH[DFWVWULQJSDWWHUQV
300VIRUH[WHQGHGSDWWHUQV







devices equipped with large number of block RAMs 1 since
it reduces not only the number of logic cells but also thecompilation and place-and-route times.
In this paper, we considered the class of extended patterns.
As future work, it is an interesting problem to extend ourarchitecture for more general classes of patterns, such as
acyclic regular expressions [7] and XPath queries [8].

             

7KHQXPEHURI300V

Fig. 10. Slice usages against the number of PMMs for exact string matchingand extended pattern matching.

7KURXJKSXWXW *ESV

300VIRUH[DFWVWULQJSDWWHUQV
300VIRUH[WHQGHGSDWWHUQV







             

7K
7KHQXPEHURI300V
E
I 300

Fig. 11. Throughputs against the number of PMMs for exact string matchingand extended pattern matching.

bounded and bounded repeats as delimiters. Although Baker etal.’s hardware achieves high throughput, it can be overflowed
when many matches of short segments occur. On the contrary,
our hardware, dynamic BP-NFA, consumes more logic, while
it achieves comparable high throughput regardless of the typeof input as shown in Theorem. 1. Hence, our hardware canbe an alternative choice for dynamic reconfigurable hardwares
for regular expression matching.

VI. Conclusion
In this paper, we presented a novel FPGA-based architecture,
called the dynamic reconfigurable bit-parallel architecture, forlarge-scale regular expression matching. For the subclass EXTof regular expressions, this architecture provides dynamic reconfiguration of the patterns using bit-parallel NFA simulation.
The use of block RAMs is attractive on modern FPGA

References[1] J. Agrawal, Y. Diao, D. Gyllstrom, N. Immerman. “Efficient patternmatching over event streams”. In Proc. SIGMOD’08, pp. 147–160, 2008.
[2] R. Baeza-Yates and G. H. Gonnet. “A new approach to text searching”.
CACM, 35(10), pp. 74–82, 1992.
[3] Z. K. Baker, H. Jung, and V. K. Prasanna. “Regular expression software
deceleration for intrusion detection systems”. In Proc. FPL’06, pp. 1–8,
2006.
[4] Z. K. Baker and V. K. Prasanna. “Time and area efficient patternmatching on FPGAs”. In Proc. FPGA’04, ACM, pp. 223–232, 2004.
[5] D. Harris and S. Harris. Digital Design and Computer Architecture.
Morgan Kaufmann Publishers Inc., 2007.
[6] H. J. Jung, Z. K. Baker and V. K. Prasanna. “Performance of FPGA
implementation of bit-split architecture for intrusion detection systems”.
In Proc. RAW’06, 2006.
[7] Y. Kaneta, S. Minato, and H. Arimura. “An efficient matching algorithm
for acyclic regular expressions with bounded depth”. TCS Technical
Report A, DCS, Hokkaido University, TCS-TR-A-10-40, Feb. 2010.
[8] Y. Kaneta and H. Arimura. “Faster bit-parallel algorithms for unorderedpseudo-tree matching and tree homeomorphism”. In Proc. IWOCA’10,
2010.
[9] Y. Kawanaka, S. Wakabayashi, and S. Nagayama. “A systolic regularexpression pattern matching engine and its application to network
intrusion detection” In Proc. FPT’08, pp. 297–300, 2008.
[10] G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings.
Cambridge University Press, 2002.
[11] H. Roan, W. Hwang, et al. “SHIFT-OR circuit for efficient network
intrusion detection pattern matching”. In Proc. FPL’06, pp. 1–6, 2006.
[12] R. Sidhu and V. K. Prasanna. “Fast regular expression matching using
FPGAs”. In Proc. the 9th Annual IEEE Symp. on Field-Programmable
Custom Computing Machines (FCCM), pp. 227–238, 2001.
[13] S. Wu and U. Manber. “Fast text searching: allowing errors”. CACM,
35(10), pp. 83–91, 1992.
[14] N. Yamagaki, R. Sidhu, and S. Kamiya. “High-speed regular expression
matching engine using multi-character NFA”. In Proc. FPL’08, pp. 131–
136, 2008.
[15] Y. E. Yang and V. K. Prasanna. “Memory-efficient pipelined architecture
for large-scale string matching”. In Proc. IEEE FCCM’09, pp. 104–111,
2009.
[16] Y. E. Yang, W. Jiang, and V. K. Prasanna. “Compact architecture
for high-throughput regular expression matching”. In Proc. ACM/IEEE
ANCS’09, pp. 30–39, 2009.
1 In the latest version of Xilinx Virtex series, the highend model Virtex-7
910T, released in June 2010, has 1,800 block RAMs, while Virtex-5 240T,
released in October 2006, has 516 block RAMs.