NFA Reduction for Regular Expressions Matching Using FPGA
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F13%3APU107071" target="_blank" >RIV/00216305:26230/13:PU107071 - isvavai.cz</a>
Result on the web
<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=10306" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=10306</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
NFA Reduction for Regular Expressions Matching Using FPGA
Original language description
Many algorithms have been proposed to accelerate regular expression matching via mapping of a nondeterministic finite automaton into a circuit implemented in an FPGA. These algorithms exploit unique features of the FPGA to achieve high throughput. On the other hand the FPGA poses a limit on the number of regular expressions by its limited resources. In this paper, we investigate applicability of NFA reduction techniques - a formal aparatus to reduce the number of states and transitions in NFA prior to its mapping into FPGA. The paper presents several NFA reduction techniques, each with a different reduction power and time complexity. The evaluation utilizes regular expressions from Snort and L7 decoder. The best NFA reduction algorithms achieve more than 66% reduction in the number of states for a Snort ftp module. Such a reduction translates directly into 66% LUT and FF saving in the FPGA.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
20206 - Computer hardware and architecture
Result continuities
Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 2013 International Conference on Field Programmable Technology
ISBN
978-1-4799-2199-7
ISSN
—
e-ISSN
—
Number of pages
4
Pages from-to
338-341
Publisher name
IEEE Computer Society
Place of publication
Kyoto
Event location
Kyoto
Event date
Dec 9, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—