Ing. Jan Kořenek, Ph.D.

KOŘENEK Jan. Fast Regular Expression Matching Using FPGA. Information Sciences and Technologies Bulletin of the ACM Slovakia. Bratislava: Vydavateľstvo STU, 2010, roč. 2, č. 2, s. 103-111. ISSN 1338-1237.
Jazyk publikace:angličtina
Název publikace:Fast Regular Expression Matching Using FPGA
Název (cs):Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA
Strany:103-111
Místo vydání:SK
Rok:2010
Časopis:Information Sciences and Technologies Bulletin of the ACM Slovakia, roč. 2, č. 2, Bratislava, SK
ISSN:1338-1237
Klíčová slova
Regular expression, matching, nondeterministic automaton, FPGA
Anotace
Článek se zabývá rychlým vyhledáváním regulárních výrazů s využitím technologie FPGA. Hledání regulárních výrazů je klíčovou a zároveň nejvíce výpočetně náročnou operací používanou v oblasti monitorování a bezpečnosti počítačových sítí. Současné algoritmy neumožňují konvenčním procesorům dosáhnout u této operace dostatečnou propustnost pro dnes již běžné multi-gigabitové sítě. Vznikla proto řada hardwarových architektur, které umožňují hledání řetězců nebo regulárních výrazů na gigabitových rychlostech. Vysoká rychlost vyhledávání je ale přímo spojena s omezením velikosti množiny hledaných regulárních výrazů. U přístupů založených na deterministických automatech je problém
splnit požadavky na velikost a rychlost pamětí, u přístupů založených na nedeterministických automatech je problém s velikostí obvodu a kapacitou FPGA. Článek se proto zabývá redukcí hardwarových zdrojů potřebných pro mapování nedeterministických automatů do technologie FPGA s cílem umožnit hledat větší množiny regulárních výrazů než poskytují současné způsoby mapování. Byl proto navržen algoritmus, který hledá v automatu bezkolizní množiny stavů s cílem mapovat část přechodové tabulky auto-
matu do paměti a redukovat tak množství spotřebovaných zdrojů FPGA v počtu look-up tabulek a flip-flop registrů. S navrženým algoritmem byly pro všechny analyzované množiny regulárních výrazů nalezeny bezkolizní množiny stavů, které tvořily v průměru 61,4 % a v jednom případě dokonce 83,6 % všech stavů automatu. Algoritmus byl dále rozšířen pro hledání obecně k bezkolizních množin, což umožnilo pro k=8 pokrýt bezkolizními množinami v průměru 84,7 % stavů u všech automatů vytvořených z analyzovaných množin regulárních výrazů. Dále byl vytvořen formální model systému paralelních částí automatu, který
respektuje rozdělení automat na části podle množin stavů a umožňuje na základě vlastností jednotlivých částí optimalizovat proces mapování do FPGA. K formálnímu modelu systému paralelních částí automatu byly vytvořeny architektury NFA Split a NFA k Split, které mapují jednotlivé části automatu do samostatných jednotek s ohledem na jejich vlastnosti. S využitím architektury NFA Split byl u analyzovaných množin regulárních výrazů v průměru redukován počet flip-flop registrů na 43,3 % a počet look-up tabulek 66,8 %.
BibTeX:
@ARTICLE{
   author = {Jan Ko{\v{r}}enek},
   title = {Fast Regular Expression Matching Using FPGA},
   pages = {103--111},
   journal = {Information Sciences and Technologies Bulletin of the ACM
	Slovakia},
   volume = {2},
   number = {2},
   year = {2010},
   ISSN = {1338-1237},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9511}
}

Vaše IPv4 adresa: 54.224.155.169
Přepnout na IPv6 spojení

DNSSEC [dnssec]