High-Performance and Compact Architecture for Regular Expression Matching on FPGA
Authors:
- 22 July 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 61 (7) , 1013-1025
Abstract
We present the design, implementation and evaluation of a high-performance architecture for regular expression matching (REM) on field-programmable gate array (FPGA). Each regular expression (regex) is first parsed into a concise token list representation, then compiled to a modular nondeterministic finite automaton (RE-NFA) using a modified version of the McNaughton-Yamada algorithm. The RE-NFA can be mapped directly onto a compact register-transistor level (RTL) circuit. A number of optimizations are applied to improve the circuit performance: 1) spatial stacking is used to construct an REM circuit processing m ≥ 1 input characters per clock cycle; 2) single-character constrained repetitions are matched efficiently by parallel shift-register lookup tables; 3) complex character classes are matched by a BRAM-based classifier shared across regexes; 4) a multipipeline architecture is used to organize a large number of RE-NFAs into priority groups to limit the I/O size of the circuit. We implemented 2,630 unique PCRE regexes from Snort rules (February 2010) in the proposed REM architecture. Based on the place-and-route results from Xilinx ISE 11.1 targeting Virtex5 LX-220 FPGAs, the proposed REM architecture achieved up to 11 Gbps concurrent throughput for various regex sets and up to 2.67× the throughput efficiency of other state-of-the-art designs.Keywords
This publication has 12 references indexed in Scilit:
- Deflating the big bang2008
- Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia2007
- Compiling PCRE to FPGA for accelerating SNORT IDS2007
- An improved algorithm to accelerate regular expression evaluation2007
- Fast and memory-efficient regular expression matching for deep packet inspection2006
- Regular expression matching for reconfigurable packet inspection2006
- Algorithms to accelerate multiple regular expressions matching for deep packet inspectionACM SIGCOMM Computer Communication Review, 2006
- The Compilation of Regular Expressions into Integrated CircuitsJournal of the ACM, 1982
- Economy of description by automata, grammars, and formal systems1971
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960