期刊名称：International Journal of Reconfigurable Computing
印刷版ISSN：1687-7195
电子版ISSN：1687-7209
出版年度：2009
卷号：2009
DOI：10.1155/2009/301512
出版社：Hindawi Publishing Corporation
摘要：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.
