Publication detail

Optimalizace architektury NFA-Split

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

KOŠAŘ, V.

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