Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
KOŘENEK, J.
Originální název
Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA
Anglický název
Fast Regular Expression Matching Using FPGA
Typ
dizertace
Jazyk
čeština
Originální abstrakt
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 %.
Anglický abstrakt
This thesis deals with fast regular expression matching using FPGA. Regular expression matching is time critical operation, which is used in network security and monitoring devices. Current processors are not able to achieve multi-gigabit speed even if they use the fastest algorithms. Therefore many hardware architectures have been proposed for a string or a regular expression matching. Unfortunately all these architectures are able to achieve a high throughput only for small sets of regular expressions. The capacity and the speed of available memories is a limitation for architectures based on a deterministic finite automaton and the capacity of available FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore the goal of this thesis is to reduce the amount of consumed FPGA logic for a high speed regular expression matching using a nondeterministic automaton. New algorithm is proposed to find a non-collision set of states which enables to map a part of the transition table to the memory instead of the FPGA logic cells. For all analysed sets of regular expressions, the algorithm was able to find a non-collision set with 61,4 % of states in average and a non-collision set with 83,6 % of states for the best case. The proposed algorithm was extended to find k non-collision sets, which enables for k=8 to increase the amount of states represented by non-collision sets to 84,7 % in average. Parallel Parts of Automaton model is introduced to represent a division of the nondeterministic automaton by sets of states. Every set of states is represented by a one part of the automaton. The model enables to optimize the mapping to the FPGA with respect to known characteristics of the automaton parts. It was proved that the created model has the same expressing power as finite automaton and can represent any set of regular expressions. New NFA Split and NFA k Split architectures were designed for mapping Parallel Parts of the Automaton to FPGA. As non-collision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flip-flop registers and look-up tables is is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flip-flops to 43,3 % and look-up tables to 66,8 % in average.
Klíčová slova
Regularní výraz, vyhledávání, nedeterministický automat, FPGA.
Klíčová slova v angličtině
Regular expression, matching, nondeterministic automaton, FPGA.
Autoři
Vydáno
7. 12. 2010
Nakladatel
Ústav počítačových systémů FIT VUT v Brně
Místo
Brno
Strany počet
105
URL
https://wis.fit.vutbr.cz/FIT/st/rp.php/rp/2010/PD/162.pdf
BibTex
@phdthesis{BUT192708, author="Jan {Kořenek}", title="Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA", publisher="Ústav počítačových systémů FIT VUT v Brně", address="Brno", pages="105", year="2010", url="https://wis.fit.vutbr.cz/FIT/st/rp.php/rp/2010/PD/162.pdf" }