Software Toolchain for Large‐Scale RE‐NFA Construction on FPGA
Yi-Hua Edward Yang, Viktor K. Prasanna · International Journal of Reconfigurable Computing · 2009
We present a software toolchain for constructing large‐scaleregular 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, ann‐statem‐bytes‐per‐cycle RE‐NFA can be constructed inO(n×m) time andO(n×m) memory by our software. A large number of RE‐NFAs are placed onto a two‐dimensionalstaged 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.