Aho-Corasickのアルゴリズムのハードウェア化

図３.４は，Aho-Corasickのアルゴリズムに対して，ハードウェアモジュール としてできるだけシンプルになるように，その構成を考えたものである．モジ ュールを構成する主要素は，文字比較を行う比較ブロック，状態セレクタ（図 では，セレクタと略記），出力生成器，データ用レジスタ，３つのファンクショ ンデータを格納するテーブル用メモリ（以下，３ファンクションテーブル，3FT） である．最後の３ファンクションテーブル以外の要素は，状態遷移を司る論理 であることから，状態遷移ロジック（STL : State Transition Logic）と呼ぶ．

ハードウェアは，基本的に Aho-Corasick アルゴリズムにおける 3 つのファ ンクションを実行すればよい．そのために，まず比較ブロックは，状態選択の 条件として使われる入力文字とパターン文字との一致判断を行う．状態セレク タは上記の一致判断に基づき goto，failure，other の中から適切な状態を選択 して現状態レジスタに挿入する．出力生成器は，output ファンションとしてキ ーワードが存在する状態に達した場合に，そのキーワードに対応するコードを 出力する．パターン文字や次状態候補群のデータは，全て３ファンクションテ ーブルからロードされる．

文字比較器

入力文字 パターン文字

現状態

次状態候補群 出力生成器

トークン 生成

比較ブロック セレクタ

r r

r

r

r

出力

入力

3FT STL

文字比較器

入力文字 パターン文字

現状態

次状態候補群 出力生成器

トークン 生成

比較ブロック セレクタ

r r

r

r

r

出力

入力

3FT STL

図３.４  ハードウェアAho-Corasickマシン

上記のようにして構成されるハードウェアAho-Corasickマシンにおいて，リ ソース群は，最終的にLSIとしてSoC，ASIC，FPGAなどに実装されうるもので ある．それらの一覧を表３.１に示す．レジスタや３ファンクションテーブル以 外の各機能（文字比較器，出力生成器，状態セレクタなど）は論理合成後に必 要なゲート数が決定する．このような回路規模については，第５章での実装に おいて詳しく述べる．しかしその特徴をここで述べれば，文字比較器は，サイ ズが8ビット幅（ASCIIコードの場合．２バイト文字では16ビット幅）で済む ため，回路規模も比較的小さくて済む．状態セレクタは状態数に依存するが，

256以下の状態ではやはり8bit幅（65536状態でも16bit幅）で済むため，やは

表３．１  リソース一覧（一階層）

処理幅(bits) 個数

コード比較器 8 N

入力コード

レジスタ 8 N

比較 ブロック

パターンコード

レジスタ 8 N

次状態セレクタ (8/16) N 1 出力生成器 M 1 現状態レジスタ 8/16 1

次状態候補レジスタ 8/16 N

３ファンクションテーブル 8(3+2M) 1

入力FIFO 8 1

全体制御回路 8（コード比較系）

8/16（状態操作系） 1

次状態セレクタ，出力生成器，状態レジスタは状態数Ns<=256 では 8bits，Ns>256 では16bitsとして，8/16と表記（厳密にはlog2Ns bitsで可能）

比較ブロックはASCIIで8bitsの場合

Nは並列度，Mはトークン及び文字の表現バイト数

り回路規模は小さい⁹．また，３ファンクションテーブルのサイズは，状態数に 依存するがやはり小さい．具体的なサイズについては，後述する．

なお，本方式では，Aho-Corasickのアルゴリズムにある状態遷移図に対して，

直接，状態遷移機械としてハードウェアマッピングを行うことはしていないが，

これには，複数の理由がある．まず，実際の応用で生成される状態遷移図の状 態数が，数百〜数千になることが想定されるため，そのままハードウェアとし て合成すると回路規模が非常に大きくなってしまうためである．さらに，対象

9 より厳密には，本エンジンの処理対象は必ずしも“テキスト”である必要はない．各種の タグなどが記号的に“バイナリ”化されたものであっても，そのバイナリの配置ルールさ え決まっていれば処理を行うことが可能である．後述するようなメッセージの構造解析に ついても同様である．

ごとにハードウェア規模が変化してしまうため，システム設計における回路規 模の見積もり等の取り扱いが容易でなくなるためでもある．状態遷移図が固定 されるまでハードウェア構成を決められないとすると，その他のモジュールと のチップ上の相対配置や接続に関しても決められないことになり，実設計にお いては大きな問題となる．

一方，本方式は，３ファンクションテーブルの内容を変えることで，同一の ハードウェアであっても，異なるメッセージルールを処理することが可能であ る．本方式は，回路規模が小さいだけでなく，その回路規模自体を応用に依存 せずに決定することが可能であるため，実設計において他モジュールとの配置 や接続関係等を早期に決定することが可能であるというメリットをもたらす．

これにより，接続される他モジュールとの並行開発を行うような場合にも都合 が良く，システム設計の短期化にも効果がある．