NFA Reduction for Regular Expressions Matching Using FPGA

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

NFA Reduction for Regular Expressions Matching Using FPGA

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

NFA Reduction for Regular Expressions Matching Using FPGA

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20206 - Computer hardware and architecture

Projekt

<a href="/cs/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: Centrum excelence IT4Innovations</a><br>

Návaznosti

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

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 2013 International Conference on Field Programmable Technology

ISBN

978-1-4799-2199-7

ISSN

—

e-ISSN

—

Počet stran výsledku

4

Strana od-do

338-341

Název nakladatele

IEEE Computer Society

Místo vydání

Kyoto

Místo konání akce

Kyoto

Datum konání akce

9. 12. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—