Software Toolchain for Large-Scale RE-NFA Construction on FPGA. (3rd August 2009)

• Record Type: Journal Article
• Authors: Yang, Yi-Hua E.; Prasanna, Viktor K.
• Other Names: Torres Lionel Academic Editor.
• Is Part Of: International journal of reconfigurable computing. Volume 2009(2009)
• Publication Date: 2009-08-03
• Subjects: Adaptive computing systems -- Periodicals; Adaptive computing systems; Periodicals; 004
• DOI: 10.1155/2009/301512
• Languages: English
• ISSNs: 1687-7195

Abstract

Abstract : 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, 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-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.