| 講演名 | 2010-09-16 多文字遷移を行うNFAに基づく正規表現マッチング回路について(カスタムプロセッシング) 中原 啓貴, 笹尾 勤, 松浦 宗寛, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文では,NFA(Non-deterministic finite automaton)に基づく正規表現回路の実現法について述べる.正規表現の長さと個数から,NFAの面積複雑度と時間複雑度を求め,NFAに基づく回路がDFAに基づく回路よりも優れていることを示す.提案手法は以下の手順で正規表現回路を生成する.まず,与えられた正規表現をNFAに変換する.次に,NFAの状態数を削減するために,p文字遷移するMNFA(p)(Modular NFA with p-character-consuming transition)に変換する.最後に,p文字を検出するFIMMと,MNFA(p)の状態を模擬するマッチングエレメント(ME)を生成する.オープンソースの侵入検知ソフトウェアであるSNORTの正規表現の一部をXilinx社FPGAに実装し,効率よく実現するMNFA(p)を実験的に求めた.面積当りの性能で比較した結果,提案手法はDFAに基づく手法よりも6.2-18.6倍優れており,通常のNFAに基づく手法よりも1.8倍優れていることがわかった.提案手法ではFPGAのリソース(LUTと組込みメモリ)の使用効率が良いため,安価なFPGAで高性能なシステムが実現可能である. |
| 抄録(英) | This paper shows an implementation of a regular expression circuit based on an NFA (Non-deterministic finite automaton). Also, it shows that the NFA based one is superior to the DFA (Deterministic finite automaton) based one, with respect to the area complexity and the time complexity. A regular expression matching circuit is produced as follows: First, the given regular expressions are converted into a non-deterministic finite automaton (NFA). Then, to reduce the number of states, the NFA is converted to a modular non-deterministic finite automaton (MNFA(p)) with p-character-consuming transition. Finally, a finite-input memory machine (FIMM) to detect p-characters is generated, and the matching elements (MEs) realizing the states for the MNFA(p) are generated. We designed MNFA(p) for different p on Xilinx FPGA. As for the performance per area, our method is 6.2-18.6 times better than the DFA-based methods, and is 1.8 times better than the NFA-based method. Then, we derive an optimal value p that efficiently uses both LUTs and embedded memories of the FPGA. |
| キーワード(和) | |
| キーワード(英) | |
| 資料番号 | RECONF2010-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2010/9/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多文字遷移を行うNFAに基づく正規表現マッチング回路について(カスタムプロセッシング) |
| サブタイトル（和） | |
| タイトル（英） | A Regular Expression Matching Circuit Based on an NFA with Multi-Character Consuming |
| サブタイトル（和） | |
| キーワード(1)（和/英） | |
| 第 1 著者 氏名（和/英） | 中原 啓貴 / Hiroki NAKAHARA |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 笹尾 勤 / Tsutomu SASAO |
| 第 2 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 第 3 著者 氏名（和/英） | 松浦 宗寛 / Munehiro MATSUURA |
| 第 3 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 発表年月日 | 2010-09-16 |
| 資料番号 | RECONF2010-20 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 204 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |