ＮＦＡ回路
【課題】検索パターン長・検索ルール数が増加しても、高速かつ低消費電力にてパケット中の文字列を検索可能なＮＦＡ回路を実現する。
【解決手段】ＮＦＡ回路は、文字列比較器１０２〜１０４、フリップフロップ１０５〜１０８、論理積回路１０９〜１１１、ゲーテッドバッファ１１２〜１１４を含み、入力データ端子１０１に正規表現/abc/で表される文字列が含まれているかを検出する。文字「a」がマッチした場合、フリップフロップ１０６は比較結果「1」を保持する。フリップフロップ１０６の出力が「1」の場合にのみ、入力データが２段目の文字列比較器１０３に入力される。次のクロックタイミングで、入力データが「b」にマッチした場合、「1」がフリップフロップ１０７に保持される。前段と同様に、フリップフロップ１０７の出力が「1」の場合にのみ、ゲーテッドバッファ１１４がON状態となり、文字列比較器１０４が動作する。
【解決手段】ＮＦＡ回路は、文字列比較器１０２〜１０４、フリップフロップ１０５〜１０８、論理積回路１０９〜１１１、ゲーテッドバッファ１１２〜１１４を含み、入力データ端子１０１に正規表現/abc/で表される文字列が含まれているかを検出する。文字「a」がマッチした場合、フリップフロップ１０６は比較結果「1」を保持する。フリップフロップ１０６の出力が「1」の場合にのみ、入力データが２段目の文字列比較器１０３に入力される。次のクロックタイミングで、入力データが「b」にマッチした場合、「1」がフリップフロップ１０７に保持される。前段と同様に、フリップフロップ１０７の出力が「1」の場合にのみ、ゲーテッドバッファ１１４がON状態となり、文字列比較器１０４が動作する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力された文字列に対してパターンマッチングを行うハードウェアエンジンに関する。
【背景技術】
【０００２】
負荷分散、QoS（Quality of Service）制御、セキュリティといったサービスの高度化に伴い、ネットワーク上のパケットを高速に制御する技術が求められている。このような高速パケット制御を実現するためのキー技術の一つに、パケットのヘッダ部分だけでなく、ペイロード部分の情報を高速に検索するDeep Packet Inspection (DPI)技術がある。DPIを実現するために、これまでは検索ルールをメモリ上に配置し、汎用CPUを用いて検索を行う方式を用いていたが、メモリへのアクセス性能がボトルネックとなり、高速な検索を行うことができなかった。
【０００３】
この問題を解決する技術として、非決定性有限オートマトン(ＮＦＡ：Nondeterministic Finite Automaton)をハードウェアに実装することで高速な文字列検索を実現するＮＦＡ型ハードウェアエンジン回路（以下、ＮＦＡ回路と呼ぶ）がある。ＮＦＡ回路はステートマシンの各ステートが文字比較回路を備えた構成となっており、各ステート間を適切に接続することで期待する文字列検索が実現される。
【０００４】
図６にＮＦＡ回路の一例を示す。このＮＦＡ回路は入力データ端子６０１、文字列比較器６０２〜６０４、フリップフロップ６０５〜６０８、論理積(AND)回路６０９〜６１１、検索結果出力端子６１２で構成される。
【０００５】
ここでは、入力データ端子６０１に正規表現/abc/で表される文字列、すなわち連続した文字列「abc」が存在するか否かを検出するものとする。入力された８bitのデータが文字列比較器６０２において文字「a」にマッチした場合、フリップフロップ６０６は文字列比較器６０２の比較結果「１」(HIGH：ハイレベル)を保持する。次のタイミングで入力されたデータが文字列比較器６０３において文字「b」にマッチした場合は、文字列比較器６０３の出力「１」と前段の文字「a」に対する比較結果「１」との論理和「１」がフリップフロップ６０７に保持される。さらに次のタイミングで入力されたデータが文字列比較器６０４において文字「ｃ」にマッチすると、文字列比較器６０４の出力「１」と前段からの入力「１」との論理和「１」がフリップフロップ６０８に保持され、検索結果出力端子６１２に検索結果が得られる。
【０００６】
このような仕組みにより、連続した文字列「abc」という信号が入力された場合にのみ検索結果出力端子６１２の検索結果が「１」となるため、目的とする文字列の検索が実現できる（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−１４２７６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ネットワークノードの増加やサービスの高度化に伴って検索パターン長・検索ルール数が増えると、それに伴ってＮＦＡの回路規模が増加し、消費電力の増大や動作速度の劣化が問題となる。
【０００９】
本発明は、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力にてパケット中の文字列を検索可能なＮＦＡ回路を実現しようとするものである。
【課題を解決するための手段】
【００１０】
本発明の態様によるＮＦＡ回路は、ＮＦＡ型ハードウェアエンジン回路として実現され、論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させる構成を持つことを特徴とする。
【００１１】
本発明の態様によるＮＦＡ型ハードウェアエンジン回路の好ましい例を挙げると以下の通りである。
【００１２】
回路ブロックの停止が該当回路ブロックに含まれる文字列比較器への入力信号の入力を制御することで行われるＮＦＡ型ハードウェアエンジン回路。
【００１３】
回路ブロックの停止が該当回路ブロックに含まれるフリップフロップにクロック信号を供給するクロックバッファを制御することで行われるＮＦＡ型ハードウェアエンジン回路。
【００１４】
回路ブロックの停止が該当回路ブロックに電源を供給する電源スイッチを制御することで行われることを特徴とするＮＦＡ型ハードウェアエンジン回路。
【発明の効果】
【００１５】
本発明によるＮＦＡ回路は、論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させることで、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力でパケット中の文字列を検索可能である。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施例によるＮＦＡ回路を示すブロック図である。
【図２】本発明の第２の実施例によるＮＦＡ回路を示すブロック図である。
【図３】本発明の第３の実施例によるＮＦＡ回路を示すブロック図である。
【図４】図３に示したＮＦＡ回路の動作を示すタイミングチャートである。
【図５】本発明の第４の実施例によるＮＦＡ回路を示すブロック図である。
【図６】これまでのＮＦＡ回路の一例を示すブロック図である。
【発明を実施するための形態】
【００１７】
［実施例］
以下、図面を参照して本発明の実施例を説明する。
【００１８】
図１は本発明の第１の実施例によるＮＦＡ回路を示すブロック図である。第１の実施例にかかるＮＦＡ回路は入力データ端子１０１、文字列比較器１０２〜１０４、フリップフロップ１０５〜１０８、論理積(AND)回路１０９〜１１１、ゲーテッドバッファ１１２〜１１４、検索結果出力端子１１５で構成される。図１のＮＦＡ回路は、説明を簡単にするために、最小限の段数の文字列比較器による構成を示しているにすぎず、これは以降で説明される第２の実施例以降も同様である。
【００１９】
ここでは、入力データ端子１０１からの入力データに正規表現/abc/で表される文字列が含まれているかを検出するものとする。
【００２０】
ここで、文字「c」に着目すると、入力データが文字列「ab」にマッチするまで、入力データと文字「c」を比較する回路動作は不要である。また文字「b」に着目すると、文字「a」にマッチするまで、入力データと文字「b」を比較する回路動作は不要である。つまり、論理積(AND)で接続される前段の回路ブロックの状態に応じて回路動作を制御することで、不要な回路動作を停止し、回路の消費電力を低減することが可能になる。
【００２１】
このような回路動作を実現するために、第１の実施例にかかるＮＦＡ回路は、縦列接続された第１〜第３の文字列検出回路（回路ブロック）１００−１〜１００−３を備え、第２、第３の文字列検出回路１００−２、１００−３の回路動作をそれぞれ第１、第２の文字列検出回路１００−１、１００−２の検出結果に応じて制御するようにしている。第１の文字列検出回路１００−１について言えば、入力データが入力されるゲーテッドバッファ１１２、その出力を入力とする「ａ」用の文字列比較器１０２、文字列比較器１０２の比較結果とフリップフロップ１０５の出力をAND入力とする論理積回路１０９、その出力を保持するフリップフロップ１０６から成る。ゲーテッドバッファ１１２は、その制御端子に接続された前段の出力、ここではフリップフロップ１０５の出力レベルが「１」の時にON状態となり、入力データを文字列比較器１０２に与える。
【００２２】
第２の文字列検出回路１００−２は、ゲーテッドバッファ１１３の制御端子に前段の出力として第１の文字列検出回路１００−１の出力が入力される点を除いて第１の文字列検出回路１００−１と同様の構成を持つ。すなわち、入力データが入力されるゲーテッドバッファ１１３、その出力を入力とする「ｂ」用の文字列比較器１０３、文字列比較器１０３の比較結果と前段のフリップフロップ１０６の出力をAND入力とする論理積回路１１０、その出力を保持するフリップフロップ１０７から成る。ゲーテッドバッファ１１３は、その制御端子に接続された前段の出力、ここではフリップフロップ１０６の出力レベルが「１」の時にON状態となり、入力データを文字列比較器１０３に与える。
【００２３】
第３の文字列検出回路１００−３は、ゲーテッドバッファ１１４の制御端子に前段の出力として第２の文字列検出回路１００−２の出力が入力される点を除いて第１の文字列検出回路１００−１と同様の構成を持つ。
【００２４】
なお、図１の回路では、各フリップフロップのクロック端子に与えられるクロックの配線は図示を省略している。これは、後述される図２、図５の回路でも同様である。
【００２５】
第１の実施例にかかるＮＦＡ回路では、フリップフロップ１０５から論理積回路１０９の一方の入力及びゲーテッドバッファ１１２の制御端子に出力レベル「１」が与えられており、まず、入力された８bitデータが文字列比較器１０２において文字「a」としてマッチした場合、文字列比較器１０２は出力レベル「１」を出力することにより、フリップフロップ１０６は比較結果「１」(HIGH)を保持する。
【００２６】
フリップフロップ１０６の出力は第２の文字列検出回路１００−２におけるゲーテッドバッファ１１３の制御端子に入力される。フリップフロップ１０６の出力がHIGHの場合にのみ、ゲーテッドバッファ１１３はON状態となり、入力データ１０１が文字列比較器１０３に入力される。次のクロックタイミングで、文字列比較器１０３で入力データが「b」にマッチした場合、文字列比較器１０３の出力とフリップフロップ１０６の出力との論理積である「１」(HIGH)がフリップフロップ１０７に保持される。
【００２７】
第３の文字列検出回路１００−３においては、第２の文字列検出回路１００−２と同様に、フリップフロップ１０７の出力がHIGHの場合にのみ、ゲーテッドバッファ１１４がON状態となり、文字列比較器１０４が動作する。このような仕組みにより、フリップフロップ１０６／１０７の出力がHIGHの時にのみ文字列比較器１０３／１０４は動作可能となる。
【００２８】
例えば、「an apple」といった文字が順番に入力された場合は、下線で示すタイミングでのみ文字列比較器１０３は動作し、文字列比較器１０４は全く動作しない。仮に、入力される文字を「a」、「b」、「c」に限定し、３文字のうちいずれかがランダムに入力される場合（例：acbbcacacabcccabca…）を想定すると、「a」、「b」、「c」３つの文字列比較器の動作率は、第１の実施例の制御を行わない場合と比較して、全体で約１/２に低減される。
【００２９】
図２は本発明の第２の実施例を示すブロック図である。第２の実施例にかかるＮＦＡ回路は入力データ端子２０１、文字列比較器２０２〜２０４、フリップフロップ２０５〜２０８、論理積(AND)回路２０９〜２１１、論理和(OR)回路２１２、ゲーテッドバッファ２１３、２１４、検索結果出力端子２１５で構成されている。ここでは、入力データ端子２０１からの入力データに、正規表現/a(b|c)/で表される文字列が含まれているかを検出するものとする。
【００３０】
このために、第２の実施例によるＮＦＡ回路は、第１の実施例における第２、第３の文字列検出回路が１つの文字列検出ブロック２００−２にまとめられてなる。フリップフロップ２０５と文字列検出回路２００−１は、第１の実施例におけるフリップフロップ１０５と文字列検出回路１００−１と同じである。
【００３１】
一方、文字列検出ブロック２００−２においては、前段の出力、すなわち第１の文字列検出回路２００−１におけるフリップフロップ２０６の出力がゲーテッドバッファ２１４の制御端子に与えられ、ゲーテッドバッファ２１４の出力が「ｂ」用（第２）の文字列比較器２０３、「ｃ」用（第３）の文字列比較器２０４のそれぞれに与えられるように接続構成されている。加えて、「ｂ」用の文字列検出回路における論理積回路２１０には、第１の実施例と同様、第１の文字列検出回路２００−１におけるフリップフロップ２０６の出力と「ｂ」用の文字列比較器２０３の出力が入力されるが、以下の接続構成が異なる。すなわち、「ｂ」用の文字列検出回路におけるフリップフロップ２０７の出力を次段の「ｃ」用の文字列検出回路における論理積回路２１１の一方の入力ではなく、「ｃ」用の文字列検出回路におけるフリップフロップ２０８の出力を一方の入力とする２入力論理和回路２１２の他方の入力に与えるように接続構成されている。代わりに、「ｃ」用の文字列検出回路における論理積回路２１１の一方の入力には、論理積回路２１０と同様に、第１の文字列検出回路２００−１の出力を与えるように接続構成されている。論理積回路２１１の他方の入力は「ｃ」用の文字列比較器２０４の出力である。また、論理和回路２１２の出力は検索結果出力端子２１５に接続されている。
【００３２】
以上のような構成による第２の実施例では、入力された８bitデータが文字列比較器２０２において文字「a」とマッチした場合、フリップフロップ２０６は比較結果「１」(HIGH)を保持する。フリップフロップ２０６の出力はゲーテッドバッファ２１４の制御端子に入力されているので、フリップフロップ２０６の出力がHIGHの場合にのみ、ゲーテッドバッファ２１４はON状態となり、文字列入力データが文字列比較器２０３及び文字列比較器２０４に入力される。このような仕組みにより、入力データが文字「a」とマッチして、フリップフロップ２０６の出力がHIGHになった時にのみ、文字列比較器２０３及び文字列比較器２０４は動作可能となる。これにより、文字列比較器２０３、２０４の動作率は、第２の実施例の制御を行わない場合と比較して低減される。
【００３３】
図３は本発明の第３の実施例を示すブロック図である。第３の実施例にかかるＮＦＡ回路は、入力データ端子３０１、文字列比較器３０２〜３０４、フリップフロップ３０５〜３０８、論理積(AND)回路３０９〜３１１、論理和(OR)回路３１２、クロック入力端子３１３、ゲーテッドバッファ３１４、３１５、クロック制御回路３１６、検索結果出力端子３１７で構成されている。ここでも、入力データ端子３０１からの入力データに、正規表現/a(b|c)/で表される文字列が含まれているかを検出するものとする。
【００３４】
図３では、第１、第２の実施例では簡便のため図示を省略したクロック配線及びクロックバッファの一部が明示されている。
【００３５】
第３の実施例によるＮＦＡ回路は、第２の実施例と同様に、第１の実施例における第２、第３の文字列検出回路が１つの文字列検出ブロック３００−２にまとめられてなる。フリップフロップ３０５は、第１の実施例におけるフリップフロップ１０５と同じであるが、文字列検出回路３００−１においては、入力データ端子３０１からの入力データが直接、文字列比較器３０２に入力される。また、ゲーテッドバッファ３１４は、クロック入力端子３１３とフリップフロップ３０６のクロック端子の間に接続され、フリップフロップ３０５の出力が制御端子に与えられることにより、フリップフロップ３０６に対するクロック入力端子３１３からのクロックをON,OFFする手段として作用する。
【００３６】
クロック入力端子３１３はまた、共通のゲーテッドバッファ３１５を経由して第２の文字列検出回路におけるフリップフロップ３０７、第３の文字列検出回路におけるフリップフロップ３０７に接続されている。ゲーテッドバッファ３１５は、その制御端子に、クロック制御回路３１６を介して第１の文字列検出回路３００−１におけるフリップフロップ３０６の出力が入力される。このことから、ゲーテッドバッファ３１４、３１５は、クロックバッファと呼ばれても良い。
【００３７】
第２の文字列検出回路における「ｂ」用（第２）の文字列比較器３０３、第３の文字列検出回路における「ｃ」用（第３）の文字列比較器３０４にはそれぞれ、入力データ端子３０１からの入力データが直接、入力される。「ｂ」用の文字列検出回路における論理積回路３１０には、第２の実施例と同様、第１の文字列検出回路３００−１におけるフリップフロップ３０６の出力と「ｂ」用の文字列比較器３０３の出力が入力される。また、「ｂ」用の文字列検出回路におけるフリップフロップ３０７の出力が、「ｃ」用の文字列検出回路におけるフリップフロップ３０８の出力を一方の入力とする２入力論理和回路３１２の他方の入力に与えるように接続構成されている。「ｃ」用の文字列検出回路における論理積回路３１１の一方の入力には、論理積回路３１０と同様に、第１の文字列検出回路３００−１の出力を与えるように接続構成されている。論理積回路３１１の他方の入力は「ｃ」用の文字列比較器２０４の出力である。また、論理和回路３１２の出力は検索結果出力端子３１７に接続されている。
【００３８】
このような接続構成による第３の実施例のＮＦＡ回路のタイミングチャートを図４に示す。入力された８bitデータが文字列比較器３１４において文字「a」がマッチした場合、ゲーテッドバッファ３１４がフリップフロップ３０５の出力でON状態にあるので、フリップフロップ３０６はクロック入力端子３１３からのクロックの立ち上がりタイミングで比較結果「１」(HIGH)を保持する。フリップフロップ３０６の出力はゲーテッドバッファ３１５の動作を制御するクロック制御回路３１６に入力される。クロック制御回路３１６はフリップフロップ３０６の出力がHIGH状態にある時クロック入力端子３１３からのクロックの立下りタイミングで動作し、フリップフロップ３０６の出力がHIGHに変化した後クロック制御回路３１６の出力HIGHでゲーテッドバッファ３１５が導通状態になってフリップフロップ３０７、３０８にクロックを入力させる。一方、フリップフロップ３０６が２クロック区間連続してLOW（「0」）を出力した場合、クロック制御回路３１６はゲーテッドバッファ３１５の動作を停止する。
【００３９】
このような仕組みにより、入力データ端子３０１からの入力データが文字「a」とマッチして、文字「b|c」検出回路ブロック３００−２の動作が必要な場合にのみ、クロック入力端子３１３からのクロックがフリップフロップ３０７及びフリップフロップ３０８に供給される。一方、回路動作が不要なタイミングでは、フリップフロップ３０７、３０８及びゲーテッドバッファ３１５が動作を停止する。
【００４０】
図５は本発明の第４の実施例を示すブロック図である。第４の実施例にかかるＮＦＡ回路は、入力データ端子５０１、文字列比較器５０２〜５０４、フリップフロップ５０５〜５０８、論理積(AND)回路５０９〜５１１、電源スイッチ制御回路５１２、電源スイッチ５１３、検索結果出力端子５１４で構成されている。ここでは、入力データ端子５０１からの入力データに正規表現/abc/で表される文字列が含まれているかを検出するものとする。
【００４１】
第４の実施例によるＮＦＡ回路は、第１（「ａ」用）、第２（「ｂ」用）、第３（「ｃ」用）の文字列検出回路５００−１、５００−２、５００−３を備え、それぞれの文字列比較器５０２、５０３、５０４に直接、入力データ端子５０１が接続されている。第１、第２の実施例と同様、クロック系統の配線については図示を省略している。
【００４２】
フリップフロップ５０５は、第１の実施例におけるフリップフロップ１０５と同じであるが、文字列検出回路５００−１においては、入力データ端子５０１からの入力データが直接、文字列比較器５０２に入力される。フリップフロップ５０５の出力と文字列比較器５０２の出力が論理積回路５０９に入力され、論理積回路５０９の出力はフリップフロップ５０６で保持される。同様にして、文字列検出回路５００−２においては、入力データ端子５０１からの入力データが直接、文字列比較器５０３に入力され、フリップフロップ５０６の出力と文字列比較器５０３の出力が論理積回路５１０に入力され、論理積回路５１０の出力はフリップフロップ５０７で保持される。文字列検出回路５００−３においても、入力データ端子５０１からの入力データが直接、文字列比較器５０４に入力され、フリップフロップ５０７の出力と文字列比較器５０４の出力が論理積回路５１１に入力され、論理積回路５１１の出力はフリップフロップ５０８で保持される。フリップフロップ５０８の出力は検索結果出力端子５１４に接続されている。
【００４３】
第４の実施例においては、第３（「ｃ」用）の文字列検出回路５００−３と電源Vddの間に文字列検出回路５００−３の動作を規定する電源スイッチ５１３が設けられ、この電源スイッチ５１３のON、OFF制御を、第１（「ａ」用）の文字列検出回路５００−１におけるフリップフロップ５０６の出力を入力とする電源スイッチ制御回路５１２で行なうように接続構成されている。なお、図示は省略しているが、第１、第２の文字列検出回路にも電源Vddが接続されていることは言うまでも無い。これは、前述した第１〜第３の実施例でも同様である。
【００４４】
第４の実施例では、入力された８bitデータが文字列比較器５０２において文字「a」がマッチした場合、フリップフロップ５０５の出力がHIGH状態にあるので、論理積回路５０９の２つの入力がHIGH状態になり、フリップフロップ５０６は比較結果「１」(HIGH)を保持する。フリップフロップ５０６の出力は第２の文字列検出回路５００−２に加えて、電源スイッチ５１３のON/OFFを制御する電源スイッチ制御回路５１２に入力されている。それゆえ、フリップフロップ５０６の出力がHIGHに変化すると、電源スイッチ制御回路５１２は電源スイッチ５１３をONにし、第３（「c」用）の文字列検出回路５００−３に電源を供給する。一方、フリップフロップ５０６が２クロック区間連続してLOW（「0」）を出力した場合、電源スイッチ制御回路５１２は電源スイッチ５１３をOFFにして第３の文字列検出回路５００−３の動作を停止する。
【００４５】
このような仕組みにより、回路動作が不要なタイミングで、第３の文字列検出回路５００−３は動作を停止する。
【００４６】
第３の文字列検出回路５００−３に対する制御を第２の文字列検出回路５００−２におけるフリップフロップ５０７の出力を基に行うことも可能であるが、一般に電源スイッチによる電源の制御はON/OFFを完了するまでに比較的長い時間を要するため、動作タイミングの検出は直前のデータではなく、それ以前のデータを用いて十分な余裕を持って行うことが好ましい。
【００４７】
以上説明した、本発明の実施例によれば、論理積で互いに縦列接続される複数の回路ブロック（あるいは回路）のうち一部の回路ブロックを、該当回路ブロックの前段の回路ブロックの状態に応じて選択的に停止させることで、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力でパケット中の文字列を検索可能であるという効果が得られる。
【００４８】
なお、前にも説明した通り、第１〜第４の実施例のいずれも、説明を簡単にするために３つの文字列について例示したが、文字列の文字数に応じて文字数に対応した文字列検出回路が縦列接続される構成となることは言うまでも無い。
【符号の説明】
【００４９】
１０１、２０１、３０１、５０１ 入力データ端子
１０２〜１０４、２０２〜２０４、３０２〜３０４、５０２〜５０４ 文字列比較器
１０５〜１０８、２０５〜２０８、３０５〜３０８、５０５〜５０８ フリップフロップ
１０９〜１１１、２０９〜２１１、３０９〜３１１、５０９〜５１１ 論理積回路
１１２〜１１４、２１３、２１４、３１４、３１５ ゲーテッドバッファ
１１５、２１５、３１７、５１４ 検索結果出力端子
２１２、３１２ 論理和回路
３１３ クロック入力端子
３１６ クロック制御回路
５１２ 電源スイッチ制御回路
５１３ 電源スイッチ
【技術分野】
【０００１】
本発明は、入力された文字列に対してパターンマッチングを行うハードウェアエンジンに関する。
【背景技術】
【０００２】
負荷分散、QoS（Quality of Service）制御、セキュリティといったサービスの高度化に伴い、ネットワーク上のパケットを高速に制御する技術が求められている。このような高速パケット制御を実現するためのキー技術の一つに、パケットのヘッダ部分だけでなく、ペイロード部分の情報を高速に検索するDeep Packet Inspection (DPI)技術がある。DPIを実現するために、これまでは検索ルールをメモリ上に配置し、汎用CPUを用いて検索を行う方式を用いていたが、メモリへのアクセス性能がボトルネックとなり、高速な検索を行うことができなかった。
【０００３】
この問題を解決する技術として、非決定性有限オートマトン(ＮＦＡ：Nondeterministic Finite Automaton)をハードウェアに実装することで高速な文字列検索を実現するＮＦＡ型ハードウェアエンジン回路（以下、ＮＦＡ回路と呼ぶ）がある。ＮＦＡ回路はステートマシンの各ステートが文字比較回路を備えた構成となっており、各ステート間を適切に接続することで期待する文字列検索が実現される。
【０００４】
図６にＮＦＡ回路の一例を示す。このＮＦＡ回路は入力データ端子６０１、文字列比較器６０２〜６０４、フリップフロップ６０５〜６０８、論理積(AND)回路６０９〜６１１、検索結果出力端子６１２で構成される。
【０００５】
ここでは、入力データ端子６０１に正規表現/abc/で表される文字列、すなわち連続した文字列「abc」が存在するか否かを検出するものとする。入力された８bitのデータが文字列比較器６０２において文字「a」にマッチした場合、フリップフロップ６０６は文字列比較器６０２の比較結果「１」(HIGH：ハイレベル)を保持する。次のタイミングで入力されたデータが文字列比較器６０３において文字「b」にマッチした場合は、文字列比較器６０３の出力「１」と前段の文字「a」に対する比較結果「１」との論理和「１」がフリップフロップ６０７に保持される。さらに次のタイミングで入力されたデータが文字列比較器６０４において文字「ｃ」にマッチすると、文字列比較器６０４の出力「１」と前段からの入力「１」との論理和「１」がフリップフロップ６０８に保持され、検索結果出力端子６１２に検索結果が得られる。
【０００６】
このような仕組みにより、連続した文字列「abc」という信号が入力された場合にのみ検索結果出力端子６１２の検索結果が「１」となるため、目的とする文字列の検索が実現できる（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−１４２７６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ネットワークノードの増加やサービスの高度化に伴って検索パターン長・検索ルール数が増えると、それに伴ってＮＦＡの回路規模が増加し、消費電力の増大や動作速度の劣化が問題となる。
【０００９】
本発明は、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力にてパケット中の文字列を検索可能なＮＦＡ回路を実現しようとするものである。
【課題を解決するための手段】
【００１０】
本発明の態様によるＮＦＡ回路は、ＮＦＡ型ハードウェアエンジン回路として実現され、論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させる構成を持つことを特徴とする。
【００１１】
本発明の態様によるＮＦＡ型ハードウェアエンジン回路の好ましい例を挙げると以下の通りである。
【００１２】
回路ブロックの停止が該当回路ブロックに含まれる文字列比較器への入力信号の入力を制御することで行われるＮＦＡ型ハードウェアエンジン回路。
【００１３】
回路ブロックの停止が該当回路ブロックに含まれるフリップフロップにクロック信号を供給するクロックバッファを制御することで行われるＮＦＡ型ハードウェアエンジン回路。
【００１４】
回路ブロックの停止が該当回路ブロックに電源を供給する電源スイッチを制御することで行われることを特徴とするＮＦＡ型ハードウェアエンジン回路。
【発明の効果】
【００１５】
本発明によるＮＦＡ回路は、論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させることで、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力でパケット中の文字列を検索可能である。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施例によるＮＦＡ回路を示すブロック図である。
【図２】本発明の第２の実施例によるＮＦＡ回路を示すブロック図である。
【図３】本発明の第３の実施例によるＮＦＡ回路を示すブロック図である。
【図４】図３に示したＮＦＡ回路の動作を示すタイミングチャートである。
【図５】本発明の第４の実施例によるＮＦＡ回路を示すブロック図である。
【図６】これまでのＮＦＡ回路の一例を示すブロック図である。
【発明を実施するための形態】
【００１７】
［実施例］
以下、図面を参照して本発明の実施例を説明する。
【００１８】
図１は本発明の第１の実施例によるＮＦＡ回路を示すブロック図である。第１の実施例にかかるＮＦＡ回路は入力データ端子１０１、文字列比較器１０２〜１０４、フリップフロップ１０５〜１０８、論理積(AND)回路１０９〜１１１、ゲーテッドバッファ１１２〜１１４、検索結果出力端子１１５で構成される。図１のＮＦＡ回路は、説明を簡単にするために、最小限の段数の文字列比較器による構成を示しているにすぎず、これは以降で説明される第２の実施例以降も同様である。
【００１９】
ここでは、入力データ端子１０１からの入力データに正規表現/abc/で表される文字列が含まれているかを検出するものとする。
【００２０】
ここで、文字「c」に着目すると、入力データが文字列「ab」にマッチするまで、入力データと文字「c」を比較する回路動作は不要である。また文字「b」に着目すると、文字「a」にマッチするまで、入力データと文字「b」を比較する回路動作は不要である。つまり、論理積(AND)で接続される前段の回路ブロックの状態に応じて回路動作を制御することで、不要な回路動作を停止し、回路の消費電力を低減することが可能になる。
【００２１】
このような回路動作を実現するために、第１の実施例にかかるＮＦＡ回路は、縦列接続された第１〜第３の文字列検出回路（回路ブロック）１００−１〜１００−３を備え、第２、第３の文字列検出回路１００−２、１００−３の回路動作をそれぞれ第１、第２の文字列検出回路１００−１、１００−２の検出結果に応じて制御するようにしている。第１の文字列検出回路１００−１について言えば、入力データが入力されるゲーテッドバッファ１１２、その出力を入力とする「ａ」用の文字列比較器１０２、文字列比較器１０２の比較結果とフリップフロップ１０５の出力をAND入力とする論理積回路１０９、その出力を保持するフリップフロップ１０６から成る。ゲーテッドバッファ１１２は、その制御端子に接続された前段の出力、ここではフリップフロップ１０５の出力レベルが「１」の時にON状態となり、入力データを文字列比較器１０２に与える。
【００２２】
第２の文字列検出回路１００−２は、ゲーテッドバッファ１１３の制御端子に前段の出力として第１の文字列検出回路１００−１の出力が入力される点を除いて第１の文字列検出回路１００−１と同様の構成を持つ。すなわち、入力データが入力されるゲーテッドバッファ１１３、その出力を入力とする「ｂ」用の文字列比較器１０３、文字列比較器１０３の比較結果と前段のフリップフロップ１０６の出力をAND入力とする論理積回路１１０、その出力を保持するフリップフロップ１０７から成る。ゲーテッドバッファ１１３は、その制御端子に接続された前段の出力、ここではフリップフロップ１０６の出力レベルが「１」の時にON状態となり、入力データを文字列比較器１０３に与える。
【００２３】
第３の文字列検出回路１００−３は、ゲーテッドバッファ１１４の制御端子に前段の出力として第２の文字列検出回路１００−２の出力が入力される点を除いて第１の文字列検出回路１００−１と同様の構成を持つ。
【００２４】
なお、図１の回路では、各フリップフロップのクロック端子に与えられるクロックの配線は図示を省略している。これは、後述される図２、図５の回路でも同様である。
【００２５】
第１の実施例にかかるＮＦＡ回路では、フリップフロップ１０５から論理積回路１０９の一方の入力及びゲーテッドバッファ１１２の制御端子に出力レベル「１」が与えられており、まず、入力された８bitデータが文字列比較器１０２において文字「a」としてマッチした場合、文字列比較器１０２は出力レベル「１」を出力することにより、フリップフロップ１０６は比較結果「１」(HIGH)を保持する。
【００２６】
フリップフロップ１０６の出力は第２の文字列検出回路１００−２におけるゲーテッドバッファ１１３の制御端子に入力される。フリップフロップ１０６の出力がHIGHの場合にのみ、ゲーテッドバッファ１１３はON状態となり、入力データ１０１が文字列比較器１０３に入力される。次のクロックタイミングで、文字列比較器１０３で入力データが「b」にマッチした場合、文字列比較器１０３の出力とフリップフロップ１０６の出力との論理積である「１」(HIGH)がフリップフロップ１０７に保持される。
【００２７】
第３の文字列検出回路１００−３においては、第２の文字列検出回路１００−２と同様に、フリップフロップ１０７の出力がHIGHの場合にのみ、ゲーテッドバッファ１１４がON状態となり、文字列比較器１０４が動作する。このような仕組みにより、フリップフロップ１０６／１０７の出力がHIGHの時にのみ文字列比較器１０３／１０４は動作可能となる。
【００２８】
例えば、「an apple」といった文字が順番に入力された場合は、下線で示すタイミングでのみ文字列比較器１０３は動作し、文字列比較器１０４は全く動作しない。仮に、入力される文字を「a」、「b」、「c」に限定し、３文字のうちいずれかがランダムに入力される場合（例：acbbcacacabcccabca…）を想定すると、「a」、「b」、「c」３つの文字列比較器の動作率は、第１の実施例の制御を行わない場合と比較して、全体で約１/２に低減される。
【００２９】
図２は本発明の第２の実施例を示すブロック図である。第２の実施例にかかるＮＦＡ回路は入力データ端子２０１、文字列比較器２０２〜２０４、フリップフロップ２０５〜２０８、論理積(AND)回路２０９〜２１１、論理和(OR)回路２１２、ゲーテッドバッファ２１３、２１４、検索結果出力端子２１５で構成されている。ここでは、入力データ端子２０１からの入力データに、正規表現/a(b|c)/で表される文字列が含まれているかを検出するものとする。
【００３０】
このために、第２の実施例によるＮＦＡ回路は、第１の実施例における第２、第３の文字列検出回路が１つの文字列検出ブロック２００−２にまとめられてなる。フリップフロップ２０５と文字列検出回路２００−１は、第１の実施例におけるフリップフロップ１０５と文字列検出回路１００−１と同じである。
【００３１】
一方、文字列検出ブロック２００−２においては、前段の出力、すなわち第１の文字列検出回路２００−１におけるフリップフロップ２０６の出力がゲーテッドバッファ２１４の制御端子に与えられ、ゲーテッドバッファ２１４の出力が「ｂ」用（第２）の文字列比較器２０３、「ｃ」用（第３）の文字列比較器２０４のそれぞれに与えられるように接続構成されている。加えて、「ｂ」用の文字列検出回路における論理積回路２１０には、第１の実施例と同様、第１の文字列検出回路２００−１におけるフリップフロップ２０６の出力と「ｂ」用の文字列比較器２０３の出力が入力されるが、以下の接続構成が異なる。すなわち、「ｂ」用の文字列検出回路におけるフリップフロップ２０７の出力を次段の「ｃ」用の文字列検出回路における論理積回路２１１の一方の入力ではなく、「ｃ」用の文字列検出回路におけるフリップフロップ２０８の出力を一方の入力とする２入力論理和回路２１２の他方の入力に与えるように接続構成されている。代わりに、「ｃ」用の文字列検出回路における論理積回路２１１の一方の入力には、論理積回路２１０と同様に、第１の文字列検出回路２００−１の出力を与えるように接続構成されている。論理積回路２１１の他方の入力は「ｃ」用の文字列比較器２０４の出力である。また、論理和回路２１２の出力は検索結果出力端子２１５に接続されている。
【００３２】
以上のような構成による第２の実施例では、入力された８bitデータが文字列比較器２０２において文字「a」とマッチした場合、フリップフロップ２０６は比較結果「１」(HIGH)を保持する。フリップフロップ２０６の出力はゲーテッドバッファ２１４の制御端子に入力されているので、フリップフロップ２０６の出力がHIGHの場合にのみ、ゲーテッドバッファ２１４はON状態となり、文字列入力データが文字列比較器２０３及び文字列比較器２０４に入力される。このような仕組みにより、入力データが文字「a」とマッチして、フリップフロップ２０６の出力がHIGHになった時にのみ、文字列比較器２０３及び文字列比較器２０４は動作可能となる。これにより、文字列比較器２０３、２０４の動作率は、第２の実施例の制御を行わない場合と比較して低減される。
【００３３】
図３は本発明の第３の実施例を示すブロック図である。第３の実施例にかかるＮＦＡ回路は、入力データ端子３０１、文字列比較器３０２〜３０４、フリップフロップ３０５〜３０８、論理積(AND)回路３０９〜３１１、論理和(OR)回路３１２、クロック入力端子３１３、ゲーテッドバッファ３１４、３１５、クロック制御回路３１６、検索結果出力端子３１７で構成されている。ここでも、入力データ端子３０１からの入力データに、正規表現/a(b|c)/で表される文字列が含まれているかを検出するものとする。
【００３４】
図３では、第１、第２の実施例では簡便のため図示を省略したクロック配線及びクロックバッファの一部が明示されている。
【００３５】
第３の実施例によるＮＦＡ回路は、第２の実施例と同様に、第１の実施例における第２、第３の文字列検出回路が１つの文字列検出ブロック３００−２にまとめられてなる。フリップフロップ３０５は、第１の実施例におけるフリップフロップ１０５と同じであるが、文字列検出回路３００−１においては、入力データ端子３０１からの入力データが直接、文字列比較器３０２に入力される。また、ゲーテッドバッファ３１４は、クロック入力端子３１３とフリップフロップ３０６のクロック端子の間に接続され、フリップフロップ３０５の出力が制御端子に与えられることにより、フリップフロップ３０６に対するクロック入力端子３１３からのクロックをON,OFFする手段として作用する。
【００３６】
クロック入力端子３１３はまた、共通のゲーテッドバッファ３１５を経由して第２の文字列検出回路におけるフリップフロップ３０７、第３の文字列検出回路におけるフリップフロップ３０７に接続されている。ゲーテッドバッファ３１５は、その制御端子に、クロック制御回路３１６を介して第１の文字列検出回路３００−１におけるフリップフロップ３０６の出力が入力される。このことから、ゲーテッドバッファ３１４、３１５は、クロックバッファと呼ばれても良い。
【００３７】
第２の文字列検出回路における「ｂ」用（第２）の文字列比較器３０３、第３の文字列検出回路における「ｃ」用（第３）の文字列比較器３０４にはそれぞれ、入力データ端子３０１からの入力データが直接、入力される。「ｂ」用の文字列検出回路における論理積回路３１０には、第２の実施例と同様、第１の文字列検出回路３００−１におけるフリップフロップ３０６の出力と「ｂ」用の文字列比較器３０３の出力が入力される。また、「ｂ」用の文字列検出回路におけるフリップフロップ３０７の出力が、「ｃ」用の文字列検出回路におけるフリップフロップ３０８の出力を一方の入力とする２入力論理和回路３１２の他方の入力に与えるように接続構成されている。「ｃ」用の文字列検出回路における論理積回路３１１の一方の入力には、論理積回路３１０と同様に、第１の文字列検出回路３００−１の出力を与えるように接続構成されている。論理積回路３１１の他方の入力は「ｃ」用の文字列比較器２０４の出力である。また、論理和回路３１２の出力は検索結果出力端子３１７に接続されている。
【００３８】
このような接続構成による第３の実施例のＮＦＡ回路のタイミングチャートを図４に示す。入力された８bitデータが文字列比較器３１４において文字「a」がマッチした場合、ゲーテッドバッファ３１４がフリップフロップ３０５の出力でON状態にあるので、フリップフロップ３０６はクロック入力端子３１３からのクロックの立ち上がりタイミングで比較結果「１」(HIGH)を保持する。フリップフロップ３０６の出力はゲーテッドバッファ３１５の動作を制御するクロック制御回路３１６に入力される。クロック制御回路３１６はフリップフロップ３０６の出力がHIGH状態にある時クロック入力端子３１３からのクロックの立下りタイミングで動作し、フリップフロップ３０６の出力がHIGHに変化した後クロック制御回路３１６の出力HIGHでゲーテッドバッファ３１５が導通状態になってフリップフロップ３０７、３０８にクロックを入力させる。一方、フリップフロップ３０６が２クロック区間連続してLOW（「0」）を出力した場合、クロック制御回路３１６はゲーテッドバッファ３１５の動作を停止する。
【００３９】
このような仕組みにより、入力データ端子３０１からの入力データが文字「a」とマッチして、文字「b|c」検出回路ブロック３００−２の動作が必要な場合にのみ、クロック入力端子３１３からのクロックがフリップフロップ３０７及びフリップフロップ３０８に供給される。一方、回路動作が不要なタイミングでは、フリップフロップ３０７、３０８及びゲーテッドバッファ３１５が動作を停止する。
【００４０】
図５は本発明の第４の実施例を示すブロック図である。第４の実施例にかかるＮＦＡ回路は、入力データ端子５０１、文字列比較器５０２〜５０４、フリップフロップ５０５〜５０８、論理積(AND)回路５０９〜５１１、電源スイッチ制御回路５１２、電源スイッチ５１３、検索結果出力端子５１４で構成されている。ここでは、入力データ端子５０１からの入力データに正規表現/abc/で表される文字列が含まれているかを検出するものとする。
【００４１】
第４の実施例によるＮＦＡ回路は、第１（「ａ」用）、第２（「ｂ」用）、第３（「ｃ」用）の文字列検出回路５００−１、５００−２、５００−３を備え、それぞれの文字列比較器５０２、５０３、５０４に直接、入力データ端子５０１が接続されている。第１、第２の実施例と同様、クロック系統の配線については図示を省略している。
【００４２】
フリップフロップ５０５は、第１の実施例におけるフリップフロップ１０５と同じであるが、文字列検出回路５００−１においては、入力データ端子５０１からの入力データが直接、文字列比較器５０２に入力される。フリップフロップ５０５の出力と文字列比較器５０２の出力が論理積回路５０９に入力され、論理積回路５０９の出力はフリップフロップ５０６で保持される。同様にして、文字列検出回路５００−２においては、入力データ端子５０１からの入力データが直接、文字列比較器５０３に入力され、フリップフロップ５０６の出力と文字列比較器５０３の出力が論理積回路５１０に入力され、論理積回路５１０の出力はフリップフロップ５０７で保持される。文字列検出回路５００−３においても、入力データ端子５０１からの入力データが直接、文字列比較器５０４に入力され、フリップフロップ５０７の出力と文字列比較器５０４の出力が論理積回路５１１に入力され、論理積回路５１１の出力はフリップフロップ５０８で保持される。フリップフロップ５０８の出力は検索結果出力端子５１４に接続されている。
【００４３】
第４の実施例においては、第３（「ｃ」用）の文字列検出回路５００−３と電源Vddの間に文字列検出回路５００−３の動作を規定する電源スイッチ５１３が設けられ、この電源スイッチ５１３のON、OFF制御を、第１（「ａ」用）の文字列検出回路５００−１におけるフリップフロップ５０６の出力を入力とする電源スイッチ制御回路５１２で行なうように接続構成されている。なお、図示は省略しているが、第１、第２の文字列検出回路にも電源Vddが接続されていることは言うまでも無い。これは、前述した第１〜第３の実施例でも同様である。
【００４４】
第４の実施例では、入力された８bitデータが文字列比較器５０２において文字「a」がマッチした場合、フリップフロップ５０５の出力がHIGH状態にあるので、論理積回路５０９の２つの入力がHIGH状態になり、フリップフロップ５０６は比較結果「１」(HIGH)を保持する。フリップフロップ５０６の出力は第２の文字列検出回路５００−２に加えて、電源スイッチ５１３のON/OFFを制御する電源スイッチ制御回路５１２に入力されている。それゆえ、フリップフロップ５０６の出力がHIGHに変化すると、電源スイッチ制御回路５１２は電源スイッチ５１３をONにし、第３（「c」用）の文字列検出回路５００−３に電源を供給する。一方、フリップフロップ５０６が２クロック区間連続してLOW（「0」）を出力した場合、電源スイッチ制御回路５１２は電源スイッチ５１３をOFFにして第３の文字列検出回路５００−３の動作を停止する。
【００４５】
このような仕組みにより、回路動作が不要なタイミングで、第３の文字列検出回路５００−３は動作を停止する。
【００４６】
第３の文字列検出回路５００−３に対する制御を第２の文字列検出回路５００−２におけるフリップフロップ５０７の出力を基に行うことも可能であるが、一般に電源スイッチによる電源の制御はON/OFFを完了するまでに比較的長い時間を要するため、動作タイミングの検出は直前のデータではなく、それ以前のデータを用いて十分な余裕を持って行うことが好ましい。
【００４７】
以上説明した、本発明の実施例によれば、論理積で互いに縦列接続される複数の回路ブロック（あるいは回路）のうち一部の回路ブロックを、該当回路ブロックの前段の回路ブロックの状態に応じて選択的に停止させることで、検索パターン長・検索ルール数が増加しても、高速かつ低消費電力でパケット中の文字列を検索可能であるという効果が得られる。
【００４８】
なお、前にも説明した通り、第１〜第４の実施例のいずれも、説明を簡単にするために３つの文字列について例示したが、文字列の文字数に応じて文字数に対応した文字列検出回路が縦列接続される構成となることは言うまでも無い。
【符号の説明】
【００４９】
１０１、２０１、３０１、５０１ 入力データ端子
１０２〜１０４、２０２〜２０４、３０２〜３０４、５０２〜５０４ 文字列比較器
１０５〜１０８、２０５〜２０８、３０５〜３０８、５０５〜５０８ フリップフロップ
１０９〜１１１、２０９〜２１１、３０９〜３１１、５０９〜５１１ 論理積回路
１１２〜１１４、２１３、２１４、３１４、３１５ ゲーテッドバッファ
１１５、２１５、３１７、５１４ 検索結果出力端子
２１２、３１２ 論理和回路
３１３ クロック入力端子
３１６ クロック制御回路
５１２ 電源スイッチ制御回路
５１３ 電源スイッチ
【特許請求の範囲】
【請求項１】
論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させる構成を持つことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項２】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに含まれる文字列比較器への入力信号の入力を制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項３】
請求項２に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、文字列比較器にはゲーテッドバッファを介して入力信号を入力するようにし、該当ゲーテッドバッファを該当回路ブロックの前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項４】
請求項２に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、２段目以降の連続する複数段の文字列比較器に、共通のゲーテッドバッファを介して入力信号を入力するようにし、該共通のゲーテッドバッファのON、OFFを、前記連続する複数段の最初の段の前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項５】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに含まれるフリップフロップにクロック信号を供給するクロックバッファを制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項６】
請求項５に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、２段目以降の連続する複数段のフリップフロップのクロック端子に、共通のクロックバッファを介してクロックを入力するようにし、該共通のクロックバッファのON、OFFを、前記連続する複数段の最初の段の前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項７】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに電源を供給する電源スイッチを制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項８】
請求項７に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、３段目以降の少なくとも１つの回路ブロックについては前記電源スイッチを介して動作用の電源を接続し、該当電源スイッチのON、OFFを、前記少なくとも１つの回路ブロックの最初の段の前々段あるいは前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項１】
論理積で互いに縦列接続される複数の回路ブロックのうち一部の回路ブロックを、該当回路ブロックより前の段の回路ブロックの状態に応じて選択的に停止させる構成を持つことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項２】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに含まれる文字列比較器への入力信号の入力を制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項３】
請求項２に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、文字列比較器にはゲーテッドバッファを介して入力信号を入力するようにし、該当ゲーテッドバッファを該当回路ブロックの前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項４】
請求項２に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、２段目以降の連続する複数段の文字列比較器に、共通のゲーテッドバッファを介して入力信号を入力するようにし、該共通のゲーテッドバッファのON、OFFを、前記連続する複数段の最初の段の前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項５】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに含まれるフリップフロップにクロック信号を供給するクロックバッファを制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項６】
請求項５に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、２段目以降の連続する複数段のフリップフロップのクロック端子に、共通のクロックバッファを介してクロックを入力するようにし、該共通のクロックバッファのON、OFFを、前記連続する複数段の最初の段の前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項７】
請求項１に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、回路ブロックの停止が該当回路ブロックに電源を供給する電源スイッチを制御することで行われることを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【請求項８】
請求項７に記載の非決定性有限オートマトン型ハードウェアエンジン回路において、複数の回路ブロックはそれぞれ文字列比較器とその比較結果を保持するフリップフロップを含み、３段目以降の少なくとも１つの回路ブロックについては前記電源スイッチを介して動作用の電源を接続し、該当電源スイッチのON、OFFを、前記少なくとも１つの回路ブロックの最初の段の前々段あるいは前段のフリップフロップの出力で制御する構成としたことを特徴とする非決定性有限オートマトン型ハードウェアエンジン回路。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−９６０７５（Ｐ２０１１−９６０７５Ａ）
【公開日】平成２３年５月１２日（２０１１．５．１２）
【国際特許分類】
【出願番号】特願２００９−２５０６２５（Ｐ２００９−２５０６２５）
【出願日】平成２１年１０月３０日（２００９．１０．３０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年５月１２日（２０１１．５．１２）
【国際特許分類】
【出願日】平成２１年１０月３０日（２００９．１０．３０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]