Fakulta informačních technologií VUT v Brně

Detail publikace

Fast Regular Expression Matching Using FPGA

KOŘENEK Jan. Fast Regular Expression Matching Using FPGA. Information Sciences and Technologies Bulletin of the ACM Slovakia, roč. 2, č. 2, s. 103-111. ISSN 1338-1237.
Název česky
Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA
Typ
článek v časopise
Jazyk
angličtina
Autoři
Abstrakt
Č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 %.
Rok
2010
Strany
103-111
Časopis
Information Sciences and Technologies Bulletin of the ACM Slovakia, roč. 2, č. 2, ISSN 1338-1237
Vydavatel
Vydavateľstvo STU
BibTeX
@ARTICLE{FITPUB9511,
   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 = "https://www.fit.vut.cz/research/publication/9511"
}
Nahoru