Disertace

 
Kořenek, J.: Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA, Brno, CZ, UPSY FIT VUT, 2010, s. 105
Jazyk publikace:čeština
Název publikace:Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA
Název (en):Fast Regular Expression Matching Using FPGA
Strany:105
Místo vydání:Brno, CZ
Rok:2010
Vydavatel:Ústav počítačových systémů FIT VUT v Brně
URL:https://wis.fit.vutbr.cz/FIT/st/rp.php/rp/2010/PD/162.pdf [PDF]
Klíčová slova
Regularní výraz, vyhledávání, nedeterministický automat, FPGA.

Anotace
Disertační práce se zabývá rychlým vyhledáváním regulárních výrazů s využitím tech nologie 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. Disertační práce 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 automatu 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ý reflektuje 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. Pro vytvořený model bylo dokázáno, že má stejnou vyjadřovací sílu jako konečný automat a je tak možné jej použít pro reprezentaci libovolného regulárního výrazu. 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:
@PHDTHESIS{
   author = {Jan Kořenek},
   title = {Rychlé vyhledávání regulárních výrazů s využitím technologie
	FPGA},
   pages = {105},
   year = {2010},
   location = {Brno, CZ},
   publisher = {Department of Computer Systems FIT BUT},
   language = {czech},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9415}
}