%0 Journal Article
%T Software Toolchain for Large-Scale RE-NFA Construction on FPGA
%A Yi-Hua E. Yang
%A Viktor K. Prasanna
%J International Journal of Reconfigurable Computing
%D 2009
%I Hindawi Publishing Corporation
%R 10.1155/2009/301512
%X We present a software toolchain for constructing large-scale regular expression matching (REM) on FPGA. The software automates the conversion of regular expressions into compact and high-performance nondeterministic finite automata (RE-NFA). Each RE-NFA is described as an RTL regular expression matching engine (REME) in VHDL for FPGA implementation. Assuming a fixed number of fan-out transitions per state, an -state -bytes-per-cycle RE-NFA can be constructed in (กม) time and (กม) memory by our software. A large number of RE-NFAs are placed onto a two-dimensional staged pipeline, allowing scalability to thousands of RE-NFAs with linear area increase and little clock rate penalty due to scaling. On a PC with a 2 GHz Athlon64 processor and 2 GB memory, our prototype software constructs hundreds of RE-NFAs used by Snort in less than 10 seconds. We also designed a benchmark generator which can produce RE-NFAs with configurable pattern complexity parameters, including state count, state fan-in, loop-back and feed-forward distances. Several regular expressions with various complexities are used to test the performance of our RE-NFA construction software.
%U http://www.hindawi.com/journals/ijrc/2009/301512/