多文字遷移を行うNFAに基づく正規表現マッチング回路について(カスタムプロセッシング)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,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で高性能なシステムが実現可能である.
- 2010-09-09
著者
-
中原 啓貴
九州工業大学情報工学部
-
笹尾 勤
九州工業大学情報工学部
-
松浦 宗寛
九州工業大学情報工学部
-
笹尾 勤
九州工業大学 情報工学部 マイクロ化総合技術センター
-
笹尾 勤
九州工業大学情報工学部電子情報工学科
-
松浦 宗寛
九州工業大学大学院情報工学府情報創成工学専攻
-
笹尾 勤
九州工業大学 大学院 情報工学府 情報創成工学専攻
-
松浦 宗寛
九州工業大学 大学院 情報工学府 情報創成工学専攻
-
松浦 宗寛
九州工業大学情報工学部電子情報工学科
関連論文
- 並列ブランチング・プログラム・マシンを用いた順序回路の模擬について(ネットワークオンチップ,システムオンシリコンを支える設計技術)
- 不完全定義インデックス生成関数の変数最小化について(高位・論理合成,システムオンシリコンを支える設計技術)
- EVBDDを用いた数値計算回路の構成(演算手法,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 二次近似法に基づくプログラマブル数値計算回路の構成とその合成法(FPGAとその応用及び一般)
- プログラマブル数値計算回路のアーキテクチャとその合成法(設計手法と高性能化)
- 算術分解を用いた基数変換回路の構成法(3)(再構成可能デバイス/キャリブレーション,システムオンシリコン設計技術並びにこれを活用したVLSI)
- LUTカスケードを用いたCAMエミュレータについて(再構成可能デバイス/キャリブレーション,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 算術分解を用いた基数変換回路の構成法(3)(再構成可能デバイス/キャリブレーション,システムオンシリコン設計技術並びにこれを活用したVLSI)
- FPGA上に実現した二つの近似文字列マッチングアルゴリズムの比較(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 書換え可能な二変数関数の数値計算回路について(リコンフィギャラブル応用,デザインガイア2008-VLSI設計の新しい大地)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- TK-2-2 メモリ構造をしたプログラム可能論理素子とその応用(TK-2. 北九州での知的クラスター創成事業(第1期)の概要と成果・課題と展望,大会委員会企画)
- ハイブリッド法を用いたアドレス生成関数の構成法と更新法について(FPGAの応用)
- ハイブリッド法を用いたアドレス生成関数の構成法と更新法について(FPGAの応用)
- ハイブリッド法を用いたアドレス生成関数の構成法と更新法について(FPGAの応用)
- ハイブリッド法を用いたアドレス生成関数の構成法と更新法について(FPGAの応用)
- 基数変換回路の構成法(4) : RNSの場合(符号化と演算,デザインガイア2007-VLSI設計の新しい大地を考える研究会)
- 決定グラフに基づく論理関数の評価のメモリパッキングを用いた高速化について(上流設計技術(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 決定グラフに基づく論理関数の評価のメモリパッキングを用いた高速化について(上流設計技術(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 並列ブランチング・プログラム・マシンを用いたパケット分類器について(アプリケーション2,FPGA応用及び一般)
- 並列ブランチング・プログラム・マシンを用いたパケット分類器について(アプリケーション2,FPGA応用及び一般)
- 並列ブランチング・プログラム・マシンを用いたパケット分類器について(アプリケーション2,FPGA応用及び一般)
- 多文字遷移を行うNFAに基づく正規表現マッチング回路について(カスタムプロセッシング)
- オートマトンの分解に基づく正規表現マッチング回路について (リコンフィギャラブルシステム)
- オートマトンの分解に基づく正規表現マッチング回路について (コンピュータシステム)
- オートマトンの分解に基づく正規表現マッチング回路について (VLSI設計技術)
- 算術分解を用いた基数変換回路の構成法(2)(演算手法,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 先読みヘテロジニアスMDDマシンについて(デザインガイア2010 : VLSI設計の新しい大地)
- 並列ふるい法とMPUを用いたウイルス検出エンジンについて(セキュリティ応用,デザインガイア2009 VLSI設計の新しい大地)
- パス遅延故障におけるパス選択とテスト生成について
- パス遅延故障におけるパス選択とテスト生成について
- パス遅延故障におけるパス選択とテスト生成について
- パス遅延故障のテストにおけるパス選択手法について
- パス遅延故障のテストにおけるパス選択手法について
- 関数分解を用いたFPGAの設計法
- 関数分解を用いたFPGAの設計法
- 3アドレスQDDマシン用コードの最適アルゴリズムについて(アプリケーションとシミュレーション,デザインガイア2009 VLSI設計の新しい大地)
- レイル数に制限のあるLUTカスケードの論理合成法 : 多出力論理関数の直接実現
- レイル数に制限のあるLUTカスケードの論理合成法 : 多出力論理関数の直接実現
- レイル数に制限のあるLUTカスケードの論理合成法 : 多出力論理関数の直接実現
- 論理関数のBi-decompositionについて
- 順序回路型LUTカスケードによる多出力論理関数の実現(FPGAとその応用及び一般)
- 順序回路型LUTカスケードによる多出力論理関数の実現(FPGAとその応用及び一般)
- 順序回路型LUTカスケードによる多出力論理関数の実現(FPGAとその応用及び一般)
- FIRフィルタの算術分解を用いたLUTカスケードによる実現(デバイスアーキテクチャI)
- FIR フィルタの LUT カスケードによる実現について(論理設計-1, システムオンシリコン設計技術並びにこれを活用した VLSI)
- FIR フィルタの LUT カスケードによる実現について(論理設計-1, システムオンシリコン設計技術並びにこれを活用した VLSI)
- FIRフィルタのLUTカスケードによる実現について
- FIRフィルタのLUTカスケードによる実現について
- 多端子EXOR三分決定グラフを用いたAND-EXOR論理式の最小化法について
- LUTカスケードを用いたCAMエミュレータについて(再構成可能デバイス/キャリブレーション,システムオンシリコン設計技術並びにこれを活用したVLSI)
- ソフトエラーを回避するLUTカスケード・エミュレータについて(耐過度故障,SWoPP2006)
- 耐故障性を有するLUTカスケード・エミュレータについて(システムオンシリコン設計技術並びにこれを活用したVLSI)
- 耐故障性を有するLUTカスケード・エミュレータについて(システムオンシリコン設計技術並びにこれを活用したVLSI)
- LUTカスケード・エミュレータを用いた論理シミュレーションについて(VLSIの設計/検証/テスト及び一般(デザインガイア))
- LUTカスケード・エミュレータを用いた論理シミュレーションについて(VLSIの設計/検証/テスト及び一般(デザインガイア))
- LUTカスケード・エミュレータを用いた論理シミュレーションについて(VLSIの設計/検証/テスト及び一般(デザインガイア))
- LUTカスケード・エミュレータを用いた論理シミュレーションについて(VLSIの設計/検証/テスト及び一般(デザインガイア))
- LUTリングを用いた順序回路の合成アルゴリズムについて(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- LUTリングを用いた順序回路の合成アルゴリズムについて(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- LUTリングを用いた順序回路の合成アルゴリズムについて(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- LUTリングを用いた順序回路の合成アルゴリズムについて(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 4IGUエミュレータとMPUを用いたウイルス検出エンジンについて (リコンフィギャラブルシステム)
- 並列ブランチング・プログラム・マシンを用いたパケット分類器について
- オートマトンの分割に基づく正規表現マッチング回路について(FPGA応用,FPGA応用及び一般)
- オートマトンの分割に基づく正規表現マッチング回路について(FPGA応用,FPGA応用及び一般)
- オートマトンの分割に基づく正規表現マッチング回路について(FPGA応用,FPGA応用及び一般)
- 4IGUエミュレータとMPUを用いたウイルス検出エンジンについて(FPGA応用)
- 先読みヘテロジニアスMDDマシンについて
- 分割MTMDDs for CFマシンについて (リコンフィギャラブルシステム)
- 分割MTMDDs for CFマシンについて (コンピュータシステム)
- 分割MTMDDs for CFマシンについて (VLSI設計技術)
- ヘテロジニアスMDD for ECFNマシンの消費電力遅延時間積に関する一考察 (リコンフィギャラブルシステム)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用 (システム数理と応用)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用 (信号処理)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用 (VLSI設計技術)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用 (回路とシステム)
- ヘテロジニアスMDD for ECFNマシンの消費電力遅延時間積に関する一考察(最適化技術・高信頼化技術,デザインガイア2011-VLSI設計の新しい大地-)
- 分割MTMDDs for CFマシンについて(再構成処理とリアルタイム処理,FPGA応用及び一般)
- 分割MTMDDs for CFマシンについて(再構成処理とリアルタイム処理,FPGA応用及び一般)
- 分割MTMDDs for CFマシンについて(再構成処理とリアルタイム処理,FPGA応用及び一般)
- MPUとROWシフト法に基づくインデックス生成器を用いたウイルス検出エンジンについて (リコンフィギャラブルシステム)
- 電波望遠鏡用小型分光器のエクステンシブル・プロセッシング・プラットフォームへの実装に関して (リコンフィギャラブルシステム)
- AS-1-3 分割MTMDDs for CFに基づく多値プロセッサに関して(AS-1.環境・社会に優しい回路とシステム,シンポジウムセツション)
- RC-005 ポリフェーズ・フィルタ・バンクを用いた基数2^kFFTに関して電波望遠鏡用分光器への適用 : 電波望遠鏡用分光器への適用(船井ベストペーパー賞受賞論文,リコンフィギャラブルシステムと応用,C分野:ハードウェア・アーキテクチャ)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用(システムと信号処理及び一般)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用(システムと信号処理及び一般)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用(システムと信号処理及び一般)
- 区分線形近似回路を用いた広帯域高速フーリエ変換器に関して : 電波望遠鏡用分光器への適用(システムと信号処理及び一般)
- 電波望遠鏡用小型分光器のエクステンシブル・プロセッシング・プラットフォームへの実装に関して(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-)
- 並列インデックス生成器を用いたIPv6検索アーキテクチャに関して(FPGA回路, FPGA応用及び一般)
- 並列インデックス生成器を用いたIPv6検索アーキテクチャに関して(FPGA回路, FPGA応用及び一般)
- 並列インデックス生成器を用いたIPv6検索アーキテクチャに関して(FPGA回路, FPGA応用及び一般)
- MPUとROWシフト法に基づくインデックス生成器を用いたウイルス検出エンジンについて
- 並列EVMDD(k)マシンを用いたパケット分類器に関して(FPGA応用,リコンフィギャラブルシステム,一般)