Software Toolchain for Large-Scale RE-NFA Construction on FPGA
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 matc...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2009-01-01
|
| Series: | International Journal of Reconfigurable Computing |
| Online Access: | http://dx.doi.org/10.1155/2009/301512 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850235669100625920 |
|---|---|
| author | Yi-Hua E. Yang Viktor K. Prasanna |
| author_facet | Yi-Hua E. Yang Viktor K. Prasanna |
| author_sort | Yi-Hua E. Yang |
| collection | DOAJ |
| description | 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 n-state m-bytes-per-cycle RE-NFA can be constructed in O(n×m) time
and O(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. |
| format | Article |
| id | doaj-art-12ee7ed0d9db4ae2b56d7d2eef8a8001 |
| institution | OA Journals |
| issn | 1687-7195 1687-7209 |
| language | English |
| publishDate | 2009-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Reconfigurable Computing |
| spelling | doaj-art-12ee7ed0d9db4ae2b56d7d2eef8a80012025-08-20T02:02:10ZengWileyInternational Journal of Reconfigurable Computing1687-71951687-72092009-01-01200910.1155/2009/301512301512Software Toolchain for Large-Scale RE-NFA Construction on FPGAYi-Hua E. Yang0Viktor K. Prasanna1Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089-0911, USADepartment of Electrical Engineering, University of Southern California, Los Angeles, CA 90089-0911, USAWe 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 n-state m-bytes-per-cycle RE-NFA can be constructed in O(n×m) time and O(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.http://dx.doi.org/10.1155/2009/301512 |
| spellingShingle | Yi-Hua E. Yang Viktor K. Prasanna Software Toolchain for Large-Scale RE-NFA Construction on FPGA International Journal of Reconfigurable Computing |
| title | Software Toolchain for Large-Scale RE-NFA Construction on FPGA |
| title_full | Software Toolchain for Large-Scale RE-NFA Construction on FPGA |
| title_fullStr | Software Toolchain for Large-Scale RE-NFA Construction on FPGA |
| title_full_unstemmed | Software Toolchain for Large-Scale RE-NFA Construction on FPGA |
| title_short | Software Toolchain for Large-Scale RE-NFA Construction on FPGA |
| title_sort | software toolchain for large scale re nfa construction on fpga |
| url | http://dx.doi.org/10.1155/2009/301512 |
| work_keys_str_mv | AT yihuaeyang softwaretoolchainforlargescalerenfaconstructiononfpga AT viktorkprasanna softwaretoolchainforlargescalerenfaconstructiononfpga |