Přístupnostní navigace
E-application
Search Search Close
Publication detail
KOŠAŘ, V.
Original Title
Optimalizace architektury NFA-Split
English Title
Optimization of the NFA-Split architecture
Type
article in a collection out of WoS and Scopus
Language
Czech
Original Abstract
Počet signatur systémů pro detekci nebezpečného provozu se v souvislosti s rozvojem počítačových sítí stále zvyšuje. To s sebou přináší nutnost redukovat počet zabraných zdrojů FPGA potřebných pro reprezentaci nedeterministických konečných automatů používaných pro akceleraci vyhledávání řetězců popsaných regulárními výrazy. Článek pojednává o možnostech optimalizace architektury NFA-Split. Dvě optimalizace jsou detailněji popsány. První je nahrazení determinizace algoritmem s kvadratickou časovou složitostí. Dosažené zrychlení je 4 až 39 násobné. Druhou optimalizací je zavedení k vnitřních abeced v deterministické části architektury NFA-Split. Dosažená redukce potřebného počtu pamětí BRAM je v závislosti na množině regulárních výrazů až 98%.
English abstract
Number of signatures used in intrusion detection systems is steadily growing in connection with the development of computer networks. This entails the necessity of reduction of utilized FPGA resources for implementation of non-deterministic finite automata used to accelerate regular expressions matching. The article discusses possibilities of optimizing the NFA-Split architecture. Two optimization are described in detail. The first optimization is a replacement of determinization algorithm with an algorithm with quadratic time complexity. The achieved acceleration is 4-39 fold. The second optimization is the introduction of inner alphabets in deterministic part of the NFA-Split architecture. Reached reduction of the utilized BRAM memories is up to 98%.
Keywords
NKA, FPGA, vyhledávání vzorů
Key words in English
NFA, FPGA, regular expression matching
Authors
RIV year
2013
Released
9. 9. 2013
Publisher
Západočeská univerzita v Plzni
Location
Plzeň
ISBN
978-80-261-0270-0
Book
Počítačové architektury a diagnostika PAD 2013
Pages from
81
Pages to
86
Pages count
6
BibTex
@inproceedings{BUT104514, author="Vlastimil {Košař}", title="Optimalizace architektury NFA-Split", booktitle="Počítačové architektury a diagnostika PAD 2013", year="2013", pages="81--86", publisher="Západočeská univerzita v Plzni", address="Plzeň", isbn="978-80-261-0270-0" }