Ing. Martin Žádník, Ph.D.

KOŠAŘ Vlastimil, ŽÁDNÍK Martin and KOŘENEK Jan. NFA Reduction for Regular Expressions Matching Using FPGA. In: Proceedings of the 2013 International Conference on Field Programmable Technology. Kyoto: IEEE Computer Society, 2013, pp. 338-341. ISBN 978-1-4799-2199-7.

Publication language:

english

Original title:

NFA Reduction for Regular Expressions Matching Using FPGA

Title (cs):

Redukce NKA pro vyhledávání řetězců popsaných regulárními výrazy v FPGA

Pages:

338-341

Proceedings:

Proceedings of the 2013 International Conference on Field Programmable Technology

Conference:

The 2013 International Conference on Field-Programmable Technology

Place:

Kyoto, JP

Year:

2013

ISBN:

978-1-4799-2199-7

Publisher:

IEEE Computer Society

Files:

Keywords

FPGA, NFA, Reduction, Regular expressions matching

Annotation

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.

BibTeX:

@INPROCEEDINGS{
   author = {Vlastimil Ko{\v{s}}a{\v{r}} and Martin
	{\v{Z}}{\'{a}}dn{\'{i}}k and Jan Ko{\v{r}}enek},
   title = {NFA Reduction for Regular Expressions Matching Using FPGA},
   pages = {338--341},
   booktitle = {Proceedings of the 2013 International Conference on Field
	Programmable Technology},
   year = {2013},
   location = {Kyoto, JP},
   publisher = {IEEE Computer Society},
   ISBN = {978-1-4799-2199-7},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=10306}
}

Nacházíte se v sekcích

Main menu

Ing. Martin Žádník, Ph.D.