Original title: Hledání regulárních výrazů s využitím technologie FPGA
Translated title: Fast Regular Expression Matching Using FPGA
Authors: Kubiš, Juraj ; Fukač, Tomáš (referee) ; Matoušek, Denis (advisor)
Document type: Bachelor's theses
Year: 2018
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Bakalárska práca sa zaoberá možnosťami hardvérovej akcelerácie vyhľadávania regulárnych výrazov. Obsahom práce je analýza už existujúcich hardvérových architektúr a zhodnotenie ich pozitívnych a negatívnych vlastností. Na základe týchto poznatkov je navrhnutá architektúra. Tá je založená na deterministických konečných automatoch s implicitnými prechodmi (D2FA), je implementovaná v jazyku VHDL a je vykonaná jej syntéza. Výsledky syntézy sú analyzované za účelom zistenia celkovej priepustnosti architektúry. Je navrhnuté programové vybavenie na prevod regulárnych výrazov do podoby D2FA a na optimalizovanie tohoto automatu s cieľom minimalizovania pamäťových nárokov. Implementácia je overená a je zhodnotený prínos jednotlivých optimalizačných techník na redukciu pamäťových nárokov. Bachelor thesis deals with the possibility of hardware acceleration of regular expression matches. The content of the thesis is to analyze existing hardware architectures and evaluate their positive and negative properties. Based on this knowledge, the architecture is designed. It is based on deterministic finite automata with implicit transitions (D2FA), is implemented in VHDL and is synthesized. The synthesis results are analyzed to determine the overall throughput of the architecture. It is designed software to convert regular expressions into a D2FA and to optimize this automaton in order to minimize memory requirements. The implementation is verified and the benefits of individual optimization techniques to reduce memory requirements are evaluated.
Keywords: D2FA; DFA; finite automata; finite automata with default transitions; FPGA; FSM; NFA; regular expressions; D2FA; DFA; FPGA; FSM; konečné automaty; konečné automaty s implicitnými prechodmi; NFA; regulárne výrazy

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/85169

Permalink: http://www.nusl.cz/ntk/nusl-567735


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses