Detail publikace

Optimalizace architektury NFA-Split

KOŠAŘ, V.

Originální název

Optimalizace architektury NFA-Split

Anglický název

Optimization of the NFA-Split architecture

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

čeština

Originální abstrakt

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%.

Anglický abstrakt

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%.

Klíčová slova

NKA, FPGA, vyhledávání vzorů

Klíčová slova v angličtině

NFA, FPGA, regular expression matching

Autoři

KOŠAŘ, V.

Rok RIV

2013

Vydáno

9. 9. 2013

Nakladatel

Západočeská univerzita v Plzni

Místo

Plzeň

ISBN

978-80-261-0270-0

Kniha

Počítačové architektury a diagnostika PAD 2013

Strany od

81

Strany do

86

Strany počet

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"
}