講演名 2007-09-21
NFA埋め込み型パターンマッチング回路におけるマルチバイト処理化に関する検討(リコンフィギャラブルデバイス応用)
山垣 則夫, 神谷 聡史,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 近年,FPGAのようなReconfigurable Deviceに,非決定性有限オートマトン(NFA : Non-deterministic Finite Automaton)と呼ばれる汎用性の高い状態遷移アルゴリズムを回路化し,直接埋め込むことで,高速なパターンマッチを実現する研究がなされている.このようなNFA埋め込み型パターンマッチング回路は,ネットワーク侵入検知システム(NIDS : Network Intrusion Detection System)等の高速検索が求められる装置内に組み込まれることが想定されるため,その検索スループットと回路規模が重要な課題である.そこで,本稿では,これらの課題に対し,行列演算を利用することで1 byte処理のNFAを,その状態数を増加させることなく,任意のバイト数で処理を行うNFAへ容易に変換するマルチバイトNFA生成手法を提案する.本手法を用いることで,処理バイト数に応じた検索スループットの向上と,利用レジスタ数を抑制することによる回路規模の削減が期待できる.本手法を用いて生成したNFAをFPGAに実装し,その検索スループット・回路規模について評価,考察を行ったので報告する.
抄録(英) Recently, some studies about NFA (Non-deterministic Finite Automaton) implementation in logic have been undertaken to achieve high-speed pattern matching. In such NFA-based pattern matching circuits, NFA logic is placed directly into a reconfigurable hardware device like FPGA. In particular, both search throughput and logic size are important features because it is assumed that this kind of pattern matching hardware is used in systems requiring high-speed operation, such as NIDS (Network Intrusion Detection System). In this paper, a generation method of NFA with multibyte transitions without increasing the number of states is proposed in order to address the above issues. This proposed method can transform NFA with 1-byte transitions into one with multibyte transitions by using matrix operations. In addition, this method enables to improve search throughput according to the number of processing bytes and to reduce its logic size by constraining the register utilization. Moreover, this paper shows the results of performance evaluations by implementing generated NFA into FPGA.
キーワード(和) NFA / パターンマッチング / マルチバイト処理 / FPGA
キーワード(英) NFA / Pattern Matching / Multibyte Processing / FPGA
資料番号 RECONF2007-26
発行日

研究会情報
研究会 RECONF
開催期間 2007/9/13(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Reconfigurable Systems (RECONF)
本文の言語 JPN
タイトル(和) NFA埋め込み型パターンマッチング回路におけるマルチバイト処理化に関する検討(リコンフィギャラブルデバイス応用)
サブタイトル(和)
タイトル(英) A Study on Multibyte Processing for NFA-based Pattern Matching Circuits
サブタイトル(和)
キーワード(1)(和/英) NFA / NFA
キーワード(2)(和/英) パターンマッチング / Pattern Matching
キーワード(3)(和/英) マルチバイト処理 / Multibyte Processing
キーワード(4)(和/英) FPGA / FPGA
第 1 著者 氏名(和/英) 山垣 則夫 / Norio YAMAGAKI
第 1 著者 所属(和/英) NECシステムIPコア研究所
System IP Core Research Laboratories, NEC Corporation
第 2 著者 氏名(和/英) 神谷 聡史 / Satoshi KAMIYA
第 2 著者 所属(和/英) NECシステムIPコア研究所
System IP Core Research Laboratories, NEC Corporation
発表年月日 2007-09-21
資料番号 RECONF2007-26
巻番号(vol) vol.107
号番号(no) 225
ページ範囲 pp.-
ページ数 6
発行日