(57)【要約】状態機械と有限状態オートマトンの効率的な実装と評価の方法と装置を説明する。一実施形態で、状態機械アーキテクチャに、複数のノード要素が含まれ、この複数のノード要素のそれぞれは、制御フロー・グラフのノードを表す。状態機械アーキテクチャには、ノード要素を接続する複数の相互接続と、複数のノード要素を用いて制御フロー・グラフを形成するために複数の相互接続内の接続をイネーブル及びディスエーブルする複数の状態遷移接続性コントロール論理と、相互接続に結合され、判断基準に対して入力データを評価するように動作し、制御フロー・グラフ内のノード要素の間の１つ又は複数の状態遷移を制御する複数の状態遷移評価論理も含まれる。
2005537550.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが制御フロー・グラフのノードを表す、複数のノード要素と、
ノード要素を接続する複数の相互接続と、
前記複数のノード要素を用いて前記制御フロー・グラフを形成するために、前記複数の相互接続内の接続をイネーブルし、ディスエーブルする複数の状態遷移接続性コントロール論理と、
前記相互接続に結合され、判断基準に対して入力データを評価するように動作し、前記制御フロー・グラフ内のノード要素の間の１つ又は複数の状態遷移を制御する複数の状態遷移評価論理と
を含む状態機械アーキテクチャ。
【請求項２】
前記判断基準が、オペレーションとデータからなる１つ又は複数のグループの指定を含む評価シンボルを含む請求項１に記載の状態機械アーキテクチャ。
【請求項３】
前記評価シンボルがプログラム可能である請求項２に記載の状態機械アーキテクチャ。
【請求項４】
ダイナミックに計算されるデータを前記状態遷移接続性コントロール論理に送るデータ転送用ニットをさらに含む請求項１に記載の状態機械アーキテクチャ。
【請求項５】
前記複数の相互接続の各相互接続が、前記制御フロー・グラフの別個の状態遷移を表す請求項１に記載の状態機械アーキテクチャ。
【請求項６】
前記状態遷移接続性コントロール論理が複数のストレージ要素を含み、前記複数のストレージ要素の各ストレージ要素が、前記複数の相互接続のノード要素の間の相互接続をイネーブル又はディスエーブルするのに使用される値をストレージする請求項１に記載の状態機械アーキテクチャ。
【請求項７】
前記状態遷移接続性コントロール論理が、プログラム可能である請求項１に記載の状態機械アーキテクチャ。
【請求項８】
状態遷移評価判断基準が、プログラム可能である請求項１に記載の状態機械アーキテクチャ。
【請求項９】
前記状態遷移接続性コントロール論理と前記状態遷移評価シンボルが、プログラム可能である請求項１に記載の状態機械アーキテクチャ。
【請求項１０】
前記複数の相互接続の相互接続相互にわたって状態遷移をゲーティングするために前記複数の相互接続に結合された少なくとも１つのトリガ信号をさらに含む請求項１に記載の状態機械アーキテクチャ。
【請求項１１】
前記少なくとも１つのトリガ信号が、状態遷移評価論理の組に応答して生成される請求項１０に記載の状態機械アーキテクチャ。
【請求項１２】
前記複数のノード要素のそれぞれが、前記制御フロー・グラフの状態を表す値をストレージするストレージ要素を含む請求項１に記載の状態機械アーキテクチャ。
【請求項１３】
状態遷移評価論理の前記組が、前記入力データを前記判断基準と比較する複数の比較器を含む請求項１に記載の状態機械アーキテクチャ。
【請求項１４】
前記状態機械アーキテクチャが、アクティブに初期化されるプログラム可能開始状態の組を用いて評価を開始するように構成される請求項１に記載の状態機械アーキテクチャ。
【請求項１５】
前記状態機械アーキテクチャが、それに達した時に評価を終了するために定義される受入状態に関する認識を実行するように構成される請求項１に記載の状態機械アーキテクチャ。
【請求項１６】
前記複数の相互接続が複数のワイヤを含む請求項１に記載の状態機械アーキテクチャ。
【請求項１７】
前記状態遷移接続性コントロール論理が複数のスイッチを含む請求項１に記載の状態機械アーキテクチャ。
【請求項１８】
前記複数のスイッチのスイッチが論理ゲートを用いて実装される請求項１に記載の状態機械アーキテクチャ。
【請求項１９】
前記制御フロー・グラフが、Ｍ個のノード、Ｍ2個のアーク遷移、Ｍ2個の評価に関するシンボルを含み、Ｍが整数である請求項１に記載の状態機械アーキテクチャ。
【請求項２０】
Ｍが１６と３２からなる群の１つである請求項１９に記載の状態機械アーキテクチャ。
【請求項２１】
前記制御フロー・グラフが、Ｍ個のノード、Ｍ2個のアーク遷移、Ｍ個の評価に関するシンボルを含み、Ｍが整数である請求項１に記載の状態機械アーキテクチャ。
【請求項２２】
Ｍが１６と３２からなる群の１つである請求項２０に記載の状態機械アーキテクチャ。
【請求項２３】
複数のノード要素と、
前記複数のノード要素に結合された、状態遷移相互接続及び次の状態評価論理と、
前記状態遷移相互接続と次の状態評価論理に結合された状態遷移接続性コントロールと、
複数の状態遷移評価シンボルと、
入力データ及び状態遷移評価シンボル出力を受け取り、前記状態遷移相互接続と次の状態評価論理に結合された複数の計算出力を生成するように結合された状態遷移ダイナミック・トリガ計算論理と
を含む有限状態オートマトン。
【請求項２４】
制御フロー・グラフの接続性制御及び状態遷移判断基準をプログラムすることと、
プログラム可能判断基準に対して入力データを評価することと、
前記入力データの評価の結果に応答して、前記制御フロー・グラフのノード要素間の１つ又は複数の状態遷移を制御することと
を含む方法。
【請求項２５】
複数のスーパーノードと、
スーパーノード要素を接続する複数の相互接続と、
複数のノード要素を用いて第１制御フロー・グラフを形成するために前記複数の相互接続内の接続をイネーブルし、ディスエーブルする、複数の状態遷移接続性コントロール論理と、
前記相互接続に結合され、判断基準に対して入力データを評価するように動作し、前記第１制御フロー・グラフ内のスーパーノード要素の間の１つ又は複数の状態遷移を制御する複数の状態遷移評価論理と
を含む状態機械アーキテクチャであって、
前記複数のスーパーノードの１つが、状態機械を含み、前記状態機械が、
それぞれが第２制御フロー・グラフのノードを表す複数のノード要素と、
ノード要素を接続する複数の相互接続と、
前記複数のノード要素を用いて前記第２制御フロー・グラフを形成するために前記複数の相互接続内の接続をイネーブルし、ディスエーブルする、複数の状態遷移接続性コントロール論理と、
前記相互接続に結合され、判断基準に対して入力データを評価するように動作し、前記第２制御フロー・グラフ内のノード要素の間の１つ又は複数の状態遷移を制御する複数の状態遷移評価論理と
を含む、状態機械アーキテクチャ。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は、２００２年８月２８日出願の米国特許出願第６０／４０６８３５号の非仮出願である。
【技術分野】
【０００２】
本発明は、情報処理の分野に関し、具体的には、コンテンツ解析及びコンテンツ処理の分野に関する。
【背景技術】
【０００３】
コンピューティング及び通信の重要な傾向が、コンテンツ解析及びコンテンツ処理に富む環境の出現につながっている。これらの環境は、メッセージ、ドキュメント、又はパケットのコンテンツのサーチ、構文解析、解析、解釈、変換などのファクションのクラスに関して高い性能とプログラム可能性を必要とする。そのような豊富なコンテンツの解析と処理を重視する顕著な分野に、コンテンツ対応ネットワーキング、コンテンツベース・セキュリティ・システム、監視、分散コンピューティング、無線通信、コンピュータへのヒューマン・インターフェース、情報ストレージや検索のシステム、セマンティック・ウェブでのコンテンツサーチ、バイオ情報科学などが含まれる。
【０００４】
コンテンツ認知ネットワーキングの分野は、パケットとメッセージをどこに経路指定又は転送するかを決定するために、パケット又はメッセージ内部にあるコンテンツのサーチと検査を必要とする。このような検査は、ネットワーク接続のデータ転送速度である「ワイヤ・スピード」で伝送中のメッセージに対して実行される必要がある。最近のネットワークのワイヤ・レートが１００Ｍｂｉｔ／秒から４０Ｇｂｉｔ／秒までの範囲であるとするならば、コンテンツ検査ファンクションが実行されなければならない速度に対しては、甚大な重圧が掛かる。
【０００５】
コンテンツベースのセキュリティ・システムや調査と監視システムは、セキュリティ違反又は侵入の可能性があるかどうかを判定するために、メッセージ又はパケットのコンテンツを解析し、一組の規則を適用する必要がある。通常、現代のネットワーク侵入検出システム（ＮＩＤＳ）では、すべての潜在的なシステム脆弱性が発見されることを保証するために、多数のパターン、規則、式を、ワイヤ速度で入力ペイロードに適用しなければならない。そのような規則とパターンは、ネットワークの状態及び進行中のトランザクションの文脈で適用され、解析される必要がある。したがって、適切な判断を行うために、洗練された状態機械を評価する必要がある。ネットワークとコンピューティング・インフラストラクチャが継続的に発展すると、新しい脆弱性が生じ続ける。さらに、検出をかわすために、侵入者はますます洗練された攻撃を使用する。侵入検出システムは、システムに対するすべての既知の攻撃を検出できる必要があり、新しい攻撃を示す普通でない疑わしい挙動を検出するのに十分に知的でなければならない。これらの要因のすべてが、コンテンツの解析と処理に対するプログラム可能性及び極端に高い性能の両方に関する要件につながる。
【０００６】
分散型のクラスタ化されたコンピュータの出現により、タスクは、現在、複合ジョブを完了するために相互に共同し通信する、複数のコンピュータ又はサーバに分散されている。この分散は、コンピュータ通信の急速な増加をもたらし、したがってこのようなメッセージ処理に対して高性能が要求される。汎用データ交換に対する新しい標準としてＸＭＬ（拡張マークアップ言語）が登場したことにより、アプリケーションは、「アプリケーション層データ転送」としてＸＭＬを使用して相互に通信する。メッセージとドキュメントは、現在、ＸＭＬマークアップに埋め込まれている。すべてのメッセージ処理は、まずＸＭＬドキュメントを構文解析し、関連コンテンツを抽出し、解釈することを必要とし、次いであらゆる変換とフィルタリングを必要とする。これらのファンクションは高速メッセージで実行される必要があるので、これらはコンピュータ処理にとって非常に要求が厳しくなる。
【０００７】
解放された通信及び無線ネットワークの成長により、無線デバイスからの情報のアクセスが増加した。クライアント・デバイスの軽量という要因を考えれば、このデバイスに配信されるデータはフィルタリングされ、そのペイロードは小さく維持されることが重要である。将来の環境は、回線インフラストラクチャからのＸＭＬコンテンツを無線インフラストラクチャの軽量なコンテンツ（無線マークアップ言語又はＷＭＬを使用して）に変換することになるであろう。無線ネットワークの使用が増加するに伴い、このコンテンツ変換ファンクションが、その取り扱いのための効率的なソルーションが必要となるほどに一般的になるであろう。
【０００８】
もう一つの重要な新たに発生する必要性は、スピーチのようなヒューマン・インターフェースを使用してコンピュータと通信し、対話する能力である。スピーチ処理や自然言語処理は、コンテンツ・サーチ、字句解析、コンテンツ構文解析、文法処理に極度に集約している。ボイス・ストリームが一度テキストに変換されると、スピーチ・システムは、そのスピーチを理解するために、多量の語彙や構文・意味論規則を、着信テキスト・ストリームに適用する必要がある。
【０００９】
世界中に広まったウェブの登場と成長は、甚大なコンピュータの負荷を情報検索（ＩＲ）システムに課した。情報は、高速でこのウェブに追加され続ける。この情報は、通常、ワードの網羅的語彙に対して完全に索引が付けられ、サーチ・エンジンとＩＲシステムのデータベースに追加される。情報が継続的に作成され、追加されるので、インデクサは「常時オン」である必要がある。効率的なリアルタイムの文脈サーチを行うために、索引付けファンクション用の高性能パターン照合・システムがある必要がある。
【００１０】
豊富なコンテンツの解析と処理を重視する別の分野は、バイオ情報科学の分野である。遺伝子解析とプロテオミクスは、遺伝子配列と構造に対する複合サーチや解析アルゴリズムのアプリケーションを必然的に伴う。ここでもまた、このような計算は、高性能のサーチ、解析、解釈の能力を必要とする。
【００１１】
したがって、将来現れるコンピュータ環境と通信環境は、コンテンツの豊富な解析と処理を重視する。そのような環境は、ドキュメント、メッセージ、又はパケット内のコンテンツのステートフル・コンテキスト検査、サーチ、字句解析、構文解析、特徴付け、解釈、フィルタリング、変換などに関する効率的でプログラム可能な解決策を必要とする。この豊富なコンテンツ処理ファンクションの中心にあるのが、入力データ・ストリームに対して状態機械を効率的に評価する能力である。
【００１２】
状態機械の歴史は、初期の計算機科学にさかのぼる。最も単純な定式化で、状態機械は、状態、状態の間の遷移、入力表現からなる形式的モデルである。チューリングのアルゴリズム計算のモデル（１９３６）から始まって、状態機械は計算理論の中心であった。１９５０年代に、正規表現が、ストリングの集合を記述し、その特徴を表す形式的表記としてクリーンによって開発された。有限状態オートマトンが、状態機械モデルとして開発され、正規表現と同等であることがわかった。その後、非決定性オートマトンが開発され、決定性オートマトンと同等であることが証明された。トンプソン他による後続の研究が、正規表現を評価する有限状態オートマトンを構成する構成アルゴリズムの本体につながった。多数の文献が、正規表現や有限状態オートマトンの記述に関して入手可能である。この材料に関する参考文献として、「Ｓｐｅｅｃｈ  ａｎｄ  Ｌａｎｇｕａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ」、Ｄａｎｉｅｌ  Ｊｕｒａｆｓｋｙ及びＪａｍｅｓ  Ｈ．  Ｍａｒｔｉｎ著、Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ  Ｉｎｃ、２００年を参照されたい。正規表現は、パターン・マッチングと認識の強力なツールに進化し、有限オートマトンは、それを評価する機械を実装する標準的な技術になった。
【００１３】
従来技術で使用可能な技法を使用することによって、状態機械や有限状態オートマトンの処理を、３つの形の１つで実行することができる。第１に、そのような処理は、先験的に既知の固定され選択された状態機械を直接に実施する固定された特定用途向け集積回路（ＡＳＩＣ）ソリューションを使用して実行された。固定されたＡＳＩＣ手法は、性能を高めることができるが、プログラム可能性に欠け、したがって、その応用は、強く制限される。さらに、各ターゲットのソリューションに関する特定のチップの設計や調整に関連する出費は、極端に多い。
【００１４】
第２に、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）を使用して、プログラム可能な形で状態機械を実現することができる。本質的に、ＦＰＧＡアーキテクチャは、状態機械の実装に特に最適化されるのではなく、広い範囲の応用に対して構成された一般化されたプログラム可能論理を提供する。この手法を使用すると、チップに少数の状態機械を収納することだけができ、さらに、評価を進める速度が限られる。実装の密度や性能特性によって、このソリューションの選択肢が、広い範囲の現れつつある応用例に関して不適切になる。
【００１５】
第３に、伝統的な汎用マイクロプロセッサが、さまざまな状態機械の実装に使用されてきた。マイクロプロセッサは、完全にプログラム可能なデバイスであり、問題の進化する必要に対処することができ、ソフトウェアを単純に再プログラムすることによって、新しい機能性を再展開することができる。しかし、伝統的なマイクロプロセッサは、状態機械を実装し、評価できる効率において制限されている。この制限を、これから説明する。
【００１６】
図１（ａ）に、有限状態オートマトンを実装する時のマイクロプロセッサ・ベース・パラダイムの制限を要約する。２つの実装オプションすなわち、第１に、決定的有限状態オートマトン手法（ＤＦＡ）、第２に、非決定的有限状態オートマトン手法が存在する。２つのオプションを、Ｒ文字の正規表現を実装し、入力データ・ストリームのＮバイトに対してこれを評価する能力について比較する。どちらの手法でも、正規表現は、ある数の状態を有する状態機械又は有限状態オートマトンにマッピングされる。マイクロプロセッサ・ベースのソリューションについて、これらの状態を収容するのに必要なストレージの量は、手法に関する良さのメトリックスである。第２のキー・メトリックスは、Ｎバイト入力データ・ストリームを評価するのに必要な時間の総量である。
【００１７】
ＤＦＡ手法では、Ｒ文字の正規表現の状態に必要なストレージの限界が、２Rである。したがって、状態を収容するために非常に大量のストレージが必要になる。ＤＦＡを実装する一般的な形は、状態遷移表を作り、入力データを漸進的に評価する時にこの表を通るマイクロプロセッサ・シーケンスを持つことである。状態推移表はメモリ内に作られる。表のサイズが大きいくなり、市販マイクロプロセッサのキャッシュ・サブシステムを非効率的にし、マイクロプロセッサが、次の状態を判定するために入力データの新しいバイトのたびにこの表をルックアップするために外部メモリにアクセスすることを必要とする。したがって、この状態機械が入力データを評価できる速度は、メモリ・アクセス・ループによって制限される。これを、図１（ｂ）に示す。入力ストリームのＮバイトに対して、状態機械を評価するのに要する時間は、メモリのＮ回のアクセスに比例する。２００３年現在に入手可能な通常の市販コンピュータ・システムでは、メモリ・アクセス待ち時間は１００ナノ秒程度である。したがって、状態機械評価の待ち時間は、Ｎ×１００ｎｓ程度である。これによって、状態機械に対して評価できるデータ・レートが、１００Ｍｂｐｓまでに制限される。複数の正規表現を並列に評価することが望まれる場合に、１つのオプションは、これらの表現をメモリ内の別個の表に実装し、マイクロプロセッサが、これらをかわるがわる順次評価することである。Ｋ個の並列正規表現に対して、評価時間は、Ｋ＊Ｎ＊１００ｎｓまで悪化するが、ストレージに対する限界は、Ｋ＊２Rまで増える。他の代替案は、すべての正規表現を単一のモノリシックＤＦＡにコンパイルし、マイクロプロセッサに、単一パスでこの表を通るようにシーケンスさせることである。Ｋ個の並列正規表現について、ストレージに対する限界は、２（K＊R）まで増えるが、評価時間はＮ＊１００ｎｓのままになる。そのような手法に必要なストレージは、極端に多くなる可能性がある。数千個の正規表現を実装するために、必要なストレージは、市販システムで使用可能なメモリの物理的限度を超える可能性がある。
【００１８】
ＮＦＡ手法では、Ｒ文字の正規表現に必要なストレージの限度がＲに比例する。したがって、ストレージは問題にならない。しかし、ＮＦＡでは、複数のノードが、同時に独立の状態遷移を行い、この遷移のそれぞれが独立の評価判断基準に基づく。マイクロプロセッサが、シーケンシャル順に制御の単一のスレッドを実行するスカラ・エンジンであるならば、ＮＦＡの複数の状態遷移は、マイクロプロセッサが各状態の評価をシーケンシャルに繰り返すことを必要とする。したがって、データの入力バイトごとに、評価をＲ回繰り返さなければならない。この方式のストレージ要件が適度であるならば、すべての処理が、オンチップ・リソースの使用に局所化され、したがって、メモリ・ボトルネックがないままになる。各状態遷移計算は、オンチップ評価によって達成されるが、このオンチップ評価の性能は、キャッシュからのデータのアクセスの待ち時間と分岐の待ち時間によって制限される。現代のマイクロプロセッサは、非常にパイプライン化されている（米国カリフォルニア州サンタ・クララのＩｎｔｅｌ  Ｃｏｒｐ．社のＰｅｎｔｉｕｍ（登録商標）−IIIとＰｅｎｔｉｕｍ−IVプロセッサなどの製品で２０から３０ステージ程度）ので、分岐に起因してこうむる性能ペナルティは、大きい。４ＧＨｚで動作する市販マイクロプロセッサについて１６サイクル・ループを仮定すると、単一の状態遷移の評価は、４ナノ秒程度を要する可能性がある。したがって、Ｒ文字の正規表現についてＲ状態ＮＦＡに対してＮバイト入力ストリームを評価するには、Ｎ＊Ｒ＊４ナノ秒が必要である。Ｋ個の並列正規表現について、マイクロプロセッサは、それぞれをシーケンスし、Ｋ＊Ｎ＊Ｒ＊４ナノ秒を要する。たとえばそれぞれ８状態の４つの並列正規表現だけでも、データ・レートが、やはり約１００Ｍｂｐｓに制限されることに留意されたい。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
これらのデータ・ポイントは、２００３年又は２００４年の普通のマイクロプロセッサが、１００Ｍｂｐｓ範囲程度の速度で入力データに対するプログラム可能状態機械評価を行えることを示している。しかし、この時間枠で、１Ｇｂｐｓから１０Ｇｂｐｓの間のデータ・レートは、企業ネットワークや企業環境ではめずらしくない。明らかに、普通のマイクロプロセッサによって与えることができる性能と、環境によって要求される性能の間に、１桁又は２桁の深刻な不一致がある。複数の並列マイクロプロセッサ・システムを使用して、所望の機能のいくつかをターゲット速度で実行することが可能であるが、これによって、システムのコストが大幅に増える。明らかに、このターゲット機能に関するより効率的な解決策の必要がある。
【課題を解決するための手段】
【００２０】
状態機械とプログラム可能有限状態オートマトンの効率的な実装と評価の方法及びシステムを説明する。一実施態様で、状態機械アーキテクチャは、それぞれが制御フロー・グラフのノードを表す複数のノード要素を含む。さらに、状態機械アーキテクチャは、ノード要素を接続する複数の相互接続と、複数のノード要素を用いて制御フロー・グラフを形成するために複数の相互接続内の接続をイネーブルし、ディスエーブルする複数の状態遷移接続性コントロール論理と、相互接続に結合され、判断基準に対して入力データを評価するように動作し、制御グラフ内のノード要素の間の１つ又は複数の状態遷移を制御する複数の状態遷移評価論理も含む。
【発明を実装するための最良の形態】
【００２１】
本発明は、本発明のさまざまな実施形態の下で与える詳細な説明及び添付図面からより完全に理解されるが、この詳細な説明及び添付図面は、本発明を特定の実施形態に制限するものと解釈されてはならず、説明及び理解のみのためのものである。
【００２２】
本明細書で、状態機械と有限状態オートマトンを実装し、評価するプログラム可能装置を開示する。この装置は、プログラム可能な形で、ハードウェアでのほとんどすべての任意の制御フロー・グラフの物理的実現を可能にする形で回路を使用してグラフを作るという技法を使用する。この装置の実施形態は、複数の複雑な状態機械の評価に関する高い性能とコンパクトなソリューションを提供する。この装置の実施形態は、データに対する数千個のルール木の階層的適用を介するデータの効率的な構文解析と評価に使用でき、さらにドキュメント、メッセージ、又は他のコンテンツの任意の長さのパターンの高速コンテキスト・サーチの実行に使用することができる。
【００２３】
一実施形態で、このハードウェアは、状態機械の制御フロー・グラフ又は状態のノードを表す値を保持するのに使用される一組にストレージ要素すなわちノード要素と、状態機械の制御フロー・グラフのアーク又は状態遷移を表すのに使用される、ノードの間の一組のワイヤすなわち相互接続と、任意のノードの間の相互接続のいずれかをイネーブル又はディスエーブルするのに使用する一組のプログラム可能接続性コントロールと、ノード要素の間の値の転送又はノード要素の間の状態遷移をトリガするのに使用されている結果を、入力データに対して適用する一組のプログラム可能評価シンボルとを含む。一実施形態には、状態機械評価の初期化、評価、終了に使用される追加のコントロールが含まれる。コントロールとシンボルをプログラムすることによって、この装置を、任意の所与の状態機械を実装するように構成することができる。
【００２４】
一実施形態では、評価サイクルごとに、新しいデータがこの装置にストリーミングされ、評価シンボルに対して与えられ、ノード要素にまたがる状態遷移がトリガされる。一実施形態で、複数のノード要素のそれぞれは、複数の他のノード要素への並列状態遷移を独立に行う。この装置は、有限状態オートマトンの高速で効率的な実施形態を実現するのに使用することができる。非決定的有限状態オートマトン（ＮＦＳＡ又はＮＦＡ）の仕様は、この装置に自然にマッピングされる。
【００２５】
一実施形態で、制御フロー・グラフのすべてのノード又は状態機械の状態のすべてが、ハードウェアのストレージ要素又はノード要素にインスタンス化され、アーク又は状態機械の状態遷移のすべてが、ノードの間のワイヤすなわち相互接続にインスタンス化される。ノードの間の接続性は、完全に行われる（完全に接続される）か部分的に接続されるのいずれかになる。接続性は、さらに、既存の接続を選択的にオン又はオフにすることができるイネーブル／ディスエーブル・コントロールによって機能強化される。一実施形態では、これらのコントロールがプログラム可能である。コントロール値の特定の組においてプログラミングすることによって、選択された相互接続をイネーブルすることができ、したがって、すべての任意の制御フロー・グラフの実現につながる。この基本的セットアップでは、イネーブルされたワイヤすなわち相互接続を介して移動し、有効な状態遷移につなげることによって、値をあるノード要素から別のノード要素に転送することができる。一実施形態で、ワイヤすなわち相互接続を介する状態遷移がトリガ信号によってゲーティングされるように、装置をさらに強化することができる。その場合に、相互接続ごとに、特定の判断基準に対して入力データを評価することによって、トリガ信号が計算される。一実施形態で、これらの判断基準（本明細書では評価シンボルと称する）が、プログラム可能である。評価シンボルの特定の組でのプログラミングによって、多数の任意の状態機械を実現することができる。
【００２６】
一実施形態で、単純なフリップフロップが、ストレージ要素の実装に使用され、論理ゲートとして実現される単純なスイッチが、接続性コントロールの実装に使用される。一実施形態においては、装置の実装が、非常に密にすることができる単純で規則的な構造にマッピングされる。
【００２７】
多数のノードをハードウェアにすることによって、本明細書に記載の技法を使用して、大きく複雑な状態機械を実装することができる。その代わりに、階層的実装戦略を使用して、制御フロー・グラフ全体のまばらさをさらに活用することができる。ターゲット状態機械の全体的な制御フロー・グラフを、密なサブグループ又はより小さい状態機械の疎結合されたグループに分割することができる。この手法を使用すると、規則又はより小さい状態機械の階層的に編成された木を、チップ上でインスタンス化することができる。
【００２８】
便利な実装のオプションが、まず所与のサイズの基本構成要素（複数のノード）を開発し、それを複数回複製し、複数のより小さい状態機械を作ることである。これらのより小さい状態機械は、独立の状態機械のプールとして使用するか、一緒に組み合わせてより大きい機械を構成することができる。後者は、相互接続ファブリックを使用してより小さい状態機械を接続することによって達成することができる。そのようなファブリックは、各小さい状態機械自体をより大きいグラフのノードとして扱うことによって、基本的な装置を作成するのに使用されるものと同一の手法に従うことができる。そのような手法は、改善されたソリューションを引き渡す際に非常に有効である。選択されたターゲット領域のために適切に働くサイズ（ノードの個数に関する）を選択することによって、その実装に焦点を合わせ、コンパクトにすることができる。相互接続ファブリックと結合される時に、より大きくより複雑な機械、したがって強力な状態機械評価機能を、単一のチップに収容することができる。たとえば、０．１３μシリコン・プロセス技術を使用することによって、一実施形態の最初の実装は、単一のチップに数千個の状態機械（それぞれが、たとえば１６個の非決定的有限状態オートマトンからなる）を収容することができる。
【００２９】
図２に、３ノードを有する状態機械の状態機械評価装置の例の実施形態を示す。このアーキテクチャの実用的実現に、より多数のノードを有する機械が含まれるが、３ノードは、例示を単純にするために選択された。状態機械評価アーキテクチャの主要な要素を、これから説明する。
【００３０】
（１）要素Ｎ１、Ｎ２、Ｎ３は、ノード要素と称するストレージ要素の組（たとえば、ノード要素Ｎ１、Ｎ２、Ｎ３）を表す。各ストレージ要素又は要素のグループは、状態機械の状態又は制御フロー・グラフのノードを表す値を保持するのに使用することができる。複数のノードを、所与の時に同時にアクティブにすることができる。
【００３１】
（２）ワイヤすなわち相互接続２０１の組が、ノード要素Ｎ１、Ｎ２、Ｎ３を完全に又は部分的に相互接続し、ノード要素Ｎ１、Ｎ２、Ｎ３相互にわたって値を読み取り、書き込み、転送するのに使用される。各ワイヤすなわち相互接続２０１を、制御フロー・グラフの個々のアークを表すのに使用して、２つのノード要素の間の相互接続を、その２つのノードを接続するアークとして扱うことができる。その代わりに、各ワイヤすなわち相互接続２０１を、状態機械の異なる状態遷移を表すのに使用することができる。２つのノード要素又は状態の間の相互接続２０１の存在を、その２つの状態の間の可能な状態遷移として扱うことができる。あるノード要素から別のノード要素への相互接続を介する値の実際の転送を、実際の状態遷移として扱うことができる。複数の状態遷移を、任意の所与の時に同時に行うことができる。図２では、ノード要素Ｎ１、Ｎ２、Ｎ３が、互いに完全に接続されている。
【００３２】
（３）一組のストレージ要素が、本明細書で状態遷移接続性コントロール２０２と称する値を含む。状態遷移接続性コントロール２０２のこれらの値は、ノード要素（たとえばノード要素Ｎ１、Ｎ２、Ｎ３）の間の特定の相互接続をイネーブル又はディスエーブルするのに使用される。このコントロールに付随するのが、下で詳細に説明する、状態遷移接続性コントロールによってノード要素の間の相互接続をイネーブル又はディスエーブルすることができる機構である。
【００３３】
（４）一組のストレージ要素が、オペレーションとデータの指定を含む。この指定を、本明細書では状態遷移評価シンボル２０３と称する。このシンボルに付随するのが、状態遷移評価シンボルを入力データに結合できる機構である。この機構を介して、シンボルが入力データに適用されて、本明細書で状態遷移ダイナミック・トリガ２０４と称する出力が計算される。一実施形態で、シンボルに、比較オペレーションと単一の８ビット文字値が含まれ、その結果、入力データが、その８ビット文字値との比較に対して指定されて、状態遷移ダイナミック・トリガ２０４が計算される。もう１つの実施形態では、より豊かで複雑な演算子をデータセットと組み合わせて、より豊かな評価シンボルを提供する。たとえば、シンボルに、減算又は範囲計算などの算術オペレーションを含めることができる。
【００３４】
（５）状態遷移ダイナミック・トリガ２０４は、値の更新と状態遷移接続性コントロール２０２によってイネーブルされている相互接続を介するノード要素間の値の転送を制御する。
【００３５】
（６）データ転送ユニット２０５が設けられ、これを介して、データ（たとえばダイナミックに計算されるデータ）を、状態遷移接続性コントロール２０２を含むストレージに供給することができる。これによって、状態遷移接続性コントロール２０２をダイナミックにプログラムし、構成することができ、ある範囲の制御フロー・グラフ構造又は構成のダイナミックな実現が可能になる。一実施形態で、データ転送ユニット２０５は、状態遷移評価シンボル２０３を含むストレージにデータ（たとえばダイナミックに計算されるデータ）を供給できる機構も提供する。これによって、状態遷移評価シンボル２０３と状態遷移ダイナミック・トリガ２０４の計算をダイナミックにプログラムし、構成することができる。データ転送ユニット２０５は、ノード要素にアクセスし、サンプリングし、初期値を用いてこれらをプログラムする機構も提供する。データ転送ユニット２０５は、この装置を他の類似する装置に結合して、より大きい状態機械又はグラフを構成する機構も提供する。
【００３６】
（７）さらに、この装置は、リセット線２０７など、この装置全体をリセットする専用の機構を有する。
【００３７】
（８）入力データ・ストリーマ２０６は、この装置全体に入力ストリームを供給する機構を提供する。各評価サイクルに、新しいデータが装置に提示され、評価シンボルに対して適用され、ノード要素にまたがる状態遷移をトリガする。一実施形態で、入力データ・ストリーマ２０６は、クロック２０８に基づいて状態機械アーキテクチャにデータの入力ストリームを供給し、クロック２０８は、状態機械アーキテクチャもクロッキングする。
【００３８】
（９）任意選択として、この機械は状態機械評価の進行を制御する追加機構を有している。開始状態選択コントロール２０９と受入状態選択コントロール２１０は、特定のノード要素を開始状態ノードと受入状態ノードとして指定するビット・ベクトルである。指定された開始状態は、機械の初期化の後にアクティブになる。機械が受入状態のいずれかに入ったならば、その機械はさらなる評価を停止する。受入状態は、状態機械がそれに関して構成されたタスクの完了を示す。たとえば、コンテキスト・サーチの場合に、受入状態は、入力ストリーム内のパターンの一致を示す。
【００３９】
図２からわかるように、Ｒ個のノードを有する状態機械装置は、Ｒ＾２のアーク及びＲ＾２のシンボルを有する。図２では、Ｒ＝３である。
【００４０】
正規表現の評価のための本アーキテクチャの使用
本明細書に記載の状態機械アーキテクチャは、正規表現を評価するプログラム可能有限状態オートマトンの実装に特に有用である。正規表現は、有限状態オートマトンと同等である。
【００４１】
図３（ａ）に、正規表現の例と、有限状態機械仕様へのその正規表現のマッピングを示す。従来技術に、そのようなマッピングよ有限状態オートマトンの構成に関する多数のアルゴリズムが存在する。［この題材に関する複数のソースとテキストが存在する。さまざまなアルゴリズムの詳細な扱いについて、文献「Ｃｏｍｐｉｌｅｒｓ：  Ｐｒｉｎｃｉｐｌｅｓ，  Ｔｅｃｈｎｉｑｕｅｓ，  ａｎｄ  Ｔｏｏｌｓ」、Ａｌｆｒｅｄ  Ｖ．  Ａｈｏ、Ｒａｖｉ  Ｓｅｔｈｉ、Ｊｅｆｆｒｅｙ  Ｄ．  Ｕｌｌｍａｎ著を参照されたい］。特筆すべきアルゴリズムに、Ｔｈｏｍｐｓｏｎの構成とＢｅｒｒｙ−Ｓｅｔｈｉ構成が含まれる。これらのアルゴリズムは、所与の数の文字と演算子からなる正規表現を有限状態オートマトンにマッピングする。これらのアルゴリズムに関する良さのメトリックスに、構成される有限状態オートマトンの重要な特性が含まれる。この特性には、状態の個数、状態遷移アークの個数、状態機械を実装するのに必要な状態遷移評価シンボルの個数が含まれる。あるクラスの構成アルゴリズム（一般に、左バイアス構成（Left-biased construction）、右バイアス構成（Right-Biased construction）、又はＢｅｒｒｙ−Ｓｅｔｈｉ様構成と称する）が、Ｒ＋１の状態、最大Ｒ＾２のアーク、及びＲ個のシンボルを有する有限状態オートマトンへのＲ文字の正規表現のマッピングにつながることを指摘することが重要である。そのような構成を用いると、正規表現処理のための装置の設計のハードウェアでのさらなる節約が可能になる。Ｒ＾２の評価シンボル（アークごとに１シンボル）を有するＲノード状態機械を作る代わりに、Ｒの評価シンボル（ノードごとに１つ）を提供するだけでよい。したがって、ノードごとに、１つの評価シンボルと関連するダイナミック・トリガ計算ハードウェアを提供するだけでよい。ノードから発するか、ノードに供給されるすべてのアークが、このトリガによってゲーティングされる。１つのノードに供給されるすべてのアークのトリガと１つのノードから発するすべてのアークのトリガの間の設計選択は、左バイアス構成アルゴリズムと右バイアス構成アルゴリズムの間の選択の判断につながる。この特性を活用することによって、保管される必要があるシンボルの個数及び入力ストリームに対してこれらのシンボルを評価するのに必要なハードウェアの数の減少がある。状態遷移ダイナミック・トリガ（たとえば２０４）を相互接続２０１に結合するのに必要なハードウェアの、付随する減少もある。
【００４２】
図３（ｂ）に、状態機械が、どのようにしてノード要素ごとに１つのシンボルを有するＲノード状態機械を実装する特定の構成アルゴリズムを利用できるかを示す。これは、Ｒの評価シンボルとＲ＾２のアークを有するＲのノードの状態機械を暗示する。図３（ｂ）に示された例では、Ｒ＝３である。したがって、図３（ｂ）には、どのように状態機械アーキテクチャを合理化して、正規表現を評価する非決定的有限状態オートマトンを実装するかが示されている。
【００４３】
次の説明では、本発明の完全な理解を提供するために、多数の詳細を示す。しかし、当業者には、これらの特定の詳細なしで本発明を実践できることが明白である。他の場合には、本発明を不明瞭にしないようにするために、周知の構造及びデバイスを、詳細にではなくブロック図形式で示す。
【００４４】
これに続く詳細な説明のある部分は、コンピュータ・メモリ内のデータ・ビットに対するオペレーションのアルゴリズム及び記号表現に関して提示される。これらのアルゴリズム的な記述と表現は、データ処理技術分野の当業者によって、その作品の実質を他の当業者に最も効果的に伝えるのに使用される手段である。アルゴリズムは、本明細書で及び一般的に、所望の結果につながるステップの首尾一貫したシーケンスと考えられる。これらのステップは、物理的量の物理的操作を必要とするステップである。通常、必ずではないが、これらの量は、保管され、転送され、組み合わされ、比較され、他の形で操作されることができる電気信号又は磁気信号の形をとる。時々、主に共通の使用のために、これらの信号を、ビット、値、要素、シンボル、文字、項、数などと称することが便利であることがわかっている。
【００４５】
しかし、これら及び類似する用語のすべてが、適切な物理的量に関連付けられねばならず、これらの量に適用される短に便利なラベルであることを念頭におかれたい。次の議論から明白なように、他の形で特に指定されない限り、この説明全体を通じて、「処理」、「コンピューティング」、「計算」、「判定」、「表示」、又は類似語などの用語を使用する議論が、コンピュータ・システムのレジスタ及びメモリ内の物理的（電子的）量として表されるデータを操作し、これをコンピュータ・システム・メモリもしくはレジスタあるいは他のそのような情報保管デバイス、情報伝送デバイス、もしくは情報表示デバイス内の物理的量として同様に表される他のデータに変換する、コンピュータ・システム又は類似する電子コンピューティング・デバイスの動作及び処理を指すことを諒解されたい。
【００４６】
本発明は、本明細書に記載のオペレーションを実行する装置にも関する。この装置は、必要な目的のために特に構成することができ、あるいは、コンピュータに保管されたコンピュータ・プログラムによって選択的にアクティブ化され又は再構成される汎用コンピュータを含めることができる。そのようなコンピュータ・プログラムは、フロッピ・ディスク、光ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクを含むすべてのタイプのディスク、読取専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード、光カード、又は電子情報をストレージするのに適切な、それぞれがコンピュータ・システム・バスに結合されるすべてのタイプの媒体など（これに制限はされない）のコンピュータ可読記憶媒体にストレージすることができる。
【００４７】
本明細書に記載のアルゴリズム及びディスプレイは、特定のコンピュータ又は他の装置に固有に関連はしない。さまざまな汎用システムを、本明細書の教示によるプログラムと共に使用することができ、必要な方法ステップを実行するためにより特殊化された装置を構成することが便利であるとわかる場合がある。さまざまなこれらのシステムの必要な構造は、下の説明から明白になる。さらに、本発明は、特定のプログラミング言語に関して説明されない。さまざまなプログラミング言語を使用して、本明細書に記載の発明の教示を実装できることを諒解されたい。
【００４８】
機械可読媒体に、機械（たとえばコンピュータ）によって可読の形で情報を保管又は伝送するすべての機構が含まれる。たとえば、機械可読媒体に、読取専用メモリ（「ＲＯＭ」）；ランダム・アクセス・メモリ（「ＲＡＭ」）；磁気ディスク記憶媒体；光記憶媒体；フラッシュ・メモリ・デバイス；電気、光、音響、又は他の形の伝搬される信号（たとえば、搬送波、赤外線信号、ディジタル信号など）などが含まれる。
【００４９】
例示的な状態機械評価アーキテクチャ
状態機械と有限状態オートマトンの効率的な実装と評価を可能にする状態機械評価アーキテクチャを説明する。一実施形態で、この装置は、プログラム可能な形で任意の制御フロー・グラフのハードウエアにおける物理的実現を可能にする形で回路を使用してグラフを作成する技法を使用する。この装置は、複数の状態機械や大きく複雑な状態機械の実装に関する高い性能とコンパクトなソリューションを提供する。この装置は、入ってくるデータ・ストリームに対する数千個の正規表現の階層的適用を介するデータの効率的な構文解析と評価に使用することができる。そのような装置を、正規表現プロセッサ用の中央評価エンジンとすることができる。
【００５０】
図４に、非決定的有限状態オートマトンの実現と入力データに対する複数の正規表現の並列適用に合わせて調整された状態機械アーキテクチャの一実施形態を示す。図４に、基本的な状態機械評価基本構成要素を示す。図５は、単純化され抽象化された形で状態機械アーキテクチャの一実施形態を示す高水準ブロック図である。複数の基本構成ブロックを組み合わせて、複数の正規表現の並列評価を達成することができる。
【００５１】
図３（ｂ）に、Ｒのノード、Ｒのシンボル、及びＲ＾２のアークを有する非決定的有限状態オートマトンの状態機械の実現のアーキテクチャの実施形態が示されていることに留意されたい。図３（ｂ）では、Ｒ＝３である。例示のためにＲに３ノードがセットされたことに留意されたい。図３（ｂ）では、ノード要素Ｎ１、Ｎ２、Ｎ３ごとに１つの評価シンボルがあることにも留意されたい。図４に、Ｒのノード、Ｒのシンボル、及びＲ＾２のアークを有する非決定的有限状態オートマトンの実現の状態機械アーキテクチャの例示的な論理実施形態を示す。図４では、Ｒに変数Ｍがセットされており、このハードウェア編成は、任意のＭにスケーリング可能になるように設計され、レイアウトされている。Ｍの値を固定し、適切なレベルのハードウェアを提供することによって、特にＭ個のインスタンス化されたノードを有する機械を実現することができる。
【００５２】
図４によって説明される実施形態では、Ｍに、１６又は３２のいずれかの値がセットされる。ノード要素Ｎ１からＮＭは、フリップ−フロップとして実装される。Ｍ＝３２の場合に、３２個のノード要素があり、これによって、３２状態を有する状態機械が可能になる。
【００５３】
ノード要素Ｎ１からＮＭは、相互接続４０１によって完全に接続される。各ノード要素は、それ自体へ及び他のノード要素のそれぞれへのアーク又は相互接続を有する。したがって、Ｍ＝３２の場合に、３２×３２又は１０２４個の相互接続４０１がある。同様に、Ｍ＝１６の場合に、１６×１６又は２５６個の相互接続４０１がある。
【００５４】
Ｍ＝３２の場合に、状態遷移接続性コントロール４０２に、３２ビット×３２ビットのマトリックスとして編成された１０２４ビットが含まれる。同様に、Ｍ＝１６の場合に、状態遷移接続性コントロール４０２に、１６ビット×１６ビットのマトリックスとして編成された２５６ビットが含まれる。Ｙ行Ｚ列のビットは、ノード要素ＮYとノード要素ＮZの間の相互接続をイネーブル又はディスエーブルするコントロールを表す。ノード要素Ｎ１からＮＭの間の相互接続４０１を状態遷移接続性コントロール４０２によってイネーブル又はディスエーブルできるようにする機構は、相互接続（たとえばワイヤ）４０１上のスイッチとして実装され、このスイッチは、その相互接続に関連する制御ビットによってゲーティングされる。これは、ＡＮＤゲート論理を使用して実装することもできる。
【００５５】
この実施形態には、機械の状態と同一の個数の状態遷移評価シンボル４０３がある。Ｍ＝３２の場合に、３２個のシンボルがある。Ｍ＝１６の場合に、１６個のシンボルがある。各シンボルに、単一の８ビット文字値と比較演算子を含めることができ、その結果、入力データが、状態遷移ダイナミック・トリガ４０４を計算するために８ビット文字値との比較について指定される。この実施形態では、状態遷移ダイナミック・トリガ４０４計算の論理が単純であり、入力データの新しいバイトが、Ｍ個のすべての比較器に同時に供給される。Ｍ本の一致線の組が、状態遷移ダイナミック・トリガとして働く。やはり、Ｍは１６又は３２のいずれかである。
【００５６】
状態遷移ダイナミック・トリガ４０４が値の更新とノード要素Ｎ１からＮＭの間の値の転送（イネーブルされている相互接続４０１を介する）を制御する機構は、この実施形態では単純なＡＮＤゲート論理として実装される。すなわち、ＯＲゲートと協力するＡＮＤゲートが、相互接続４０１をイネーブルし、かつ／又はディスエーブルするように働く。
【００５７】
データ転送ユニット４０５は、状態遷移接続性コントロール４０２と状態遷移評価シンボル４０３をダイナミックに構成し、プログラムする。これによって、ある範囲の制御フロー・グラフ構造又は制御フロー・グラフ構成のダイナミック実現が可能になる。この実施形態では、Ｍ＝３２の場合に、状態遷移接続性コントロール４０２のビット・マトリックスを、それぞれ３２ビットの３２個のレジスタとして実装することができる。同様に、Ｍ＝１６の場合に、状態遷移接続性コントロール４０２のビット・マトリックスを、それぞれ１６ビットの１６個のレジスタとして実装することができる。この実施形態では、Ｍ＝３２の場合に、状態遷移評価シンボル４０３のストレージを、それぞれ８ビットの３２個のレジスタとして実装することができる。同様に、Ｍ＝１６の場合に、状態遷移評価シンボル４０３のストレージを、それぞれ８ビットの１６個のレジスタとして実装することができる。
【００５８】
データ転送ユニット４０５は、ノード要素Ｎ１からＮＭを読み取り、これに書き込むアクセスも提供する。Ｍ＝３２の場合に、ノード要素を、３２ビットの論理レジスタとみなすことができる。同様に、Ｍ＝１６の場合に、ノード要素を、１６ビットの論理レジスタとみなすことができる。データ転送ユニット４０５は、ロード・オペレーション及びストア・オペレーションを実行して、これらのすべてのレジスタから値を読み取り、それらに値を書き込む。ノード要素Ｎ１からＮＭを読み取り、書き込むこの能力を使用して、データ転送ユニット４０５が外部相互接続ファブリックと通信することを可能にして、より大きい状態機械又はグラフを構成するために状態機械基本構成ブロックを他のそのような基本構成ブロックに接続することができる。データ転送ユニット４０５は、選択されたノード要素から専用信号ワイヤで値を出力し、この値を、たとえば他の状態機械又は外部相互接続ファブリックに送ることができる。同様に、データ転送ユニット４０５は、外部接続ファブリックから専用の信号ワイヤで値を受け取る。これらの値を、選択されたノード要素に転送することができる。
【００５９】
単一のリセット信号４０７が、この装置のさまざまな要素に供給されて、値を０にクリアする。
【００６０】
状態機械評価の開始の前に、状態遷移接続性コントロール４０２と状態遷移評価シンボル４０３を、所望の構成値を用いてプログラムしなければならない。したがって、これらのコントロールに割り当てられたストレージ内の信号値は、状態機械評価が開始される前に安定する。
【００６１】
一実施形態に、状態機械評価の開始を制御する機構がある。一実施形態で、Ｍ＝３２の場合に、開始状態選択コントロール４０９が、３２ビットのレジスタからなる。一実施形態で、Ｍ＝１６の場合に、開始状態選択コントロール４０９が１６ビットのレジスタからなる。このレジスタの各ビットは、１つのノード要素に対応する。このレジスタの任意の個数のビットに、１（アクティブ）をセットすることができる。状態機械の初期化時に、開始状態選択コントロール４０９レジスタのアクティブ・ビットに対応するノード要素が、アクティブ状態として開始される。
【００６２】
一実施形態で、状態機械評価の進行は、評価サイクルを決定するクロック４０８によって条件付けられる。一実施形態で、すべての評価サイクルに、入力データの新しいバイトが装置に提示され、このバイトが、すべての状態遷移評価シンボルに対して並列に評価され（この実施形態では、これが、入力バイトと８ビット文字値の比較である）、状態遷移ダイナミック・トリガ４０４を表すＭ本の一致線の組の更新につながる。これらのＭ個のトリガ４０４は、状態遷移接続性コントロール４０２に対応するＭ＾２ビットと共に、ノード要素Ｎ１からＮＭの現在の状態値と組み合わされて、各ノード要素の次の状態が計算される。各ノード要素の次の状態の計算の論理式は、次の通りである。
状態遷移ダイナミック・トリガが、Ｔ1からＴMであり、
ノード要素がＮ1からＮMであり、
状態遷移接続性コントロールが、ビット・マトリックスＣI，Jである（Ｉ＝１，Ｍ、Ｊ＝１，Ｍ）場合に、
ノード要素ＮKの前の状態ＰＳKを与えられれば、次の状態ＮＳKは、次のようになる。
ＮＳK  ＝  ＯＲ  （
［ＰＳ1  ＡＮＤ  Ｔ1  ＡＮＤ  Ｃ1，K］，
［ＰＳ2  ＡＮＤ  Ｔ2  ＡＮＤ  Ｃ2，K］，
…
［ＰＳI  ＡＮＤ  ＴI  ＡＮＤ  ＣI，K］，
…
［ＰＳM  ＡＮＤ  ＴM  ＡＮＤ  ＣM，K］
）
【００６３】
ノード要素ごとに、次の状態計算は、Ｍ項の大きいＯＲ関数であれば効果的である。各項は、３つの値すなわち、ノード要素の前の状態値、対応するダイナミック・トリガ、特定の相互接続４０１がイネーブルされているかどうかを示す対応する接続性制御ビットのＡＮＤをとることによって計算される。
【００６４】
次の状態計算が完了したならば、ノード要素が、次の状態値を用いて更新され、状態機械は、単一の評価サイクルを完了する。次の状態計算の論理式からわかるように、この装置の評価サイクル時間は、３レベルの論理評価である。第１レベルは、トリガを計算するＡＮＤゲートからなり、第２レベルは、接続性コントロールを計算に入れるＡＮＤゲートからなり、最後にＭ入力ＯＲゲートがある。この評価サイクル時間は、市販マイクロプロセッサの動作周波数を制御するサイクル時間よりかなり短い。
【００６５】
上で説明したステップのシーケンスが、単一の論理評価サイクルに必要な計算を表すことに留意されたい。物理的に言えば、オペレーションの周波数をさらに高めるために、追加のパイプライン化が可能である。たとえば、状態遷移ダイナミック・トリガの計算（入力データの新しいバイトを与えられて）を、次の状態評価から切り離すことができる。
【００６６】
一実施形態に、状態機械評価の停止を制御する機構がある。Ｍ＝３２の場合に、受入状態選択コントロール４１０が、３２ビットのレジスタからなる。Ｍ＝１６の場合に、受入状態選択コントロール４１０が１６ビットのレジスタからなる。このレジスタの各ビットは１つのノード要素に対応する。このレジスタの任意の個数のビットに、１（アクティブ）をセットすることができる。状態機械が、これらの状態（アクティブになったノード要素に対応する）に入ったならば、状態機械はその評価を停止する。
【００６７】
前述は、単一の状態機械基本構成要素の評価サイクルの説明を提供する。そのようなブロックが、外部接続ファブリックを介して他の状態機械に結合される時に、さまざまな機械の評価サイクルを調整できるようにする追加の同期化ハンドシェークが必要である。
【００６８】
図６に、状態機械装置の一実施形態のプログラマからの図を示す。この状態機械アーキテクチャは、プログラマにはレジスタの組に見える。図６には、ノード要素のレジスタ、状態遷移評価シンボルのレジスタ、状態遷移接続性コントロールのレジスタ、開始状態選択コントロール・ベクトルのレジスタ、受入状態選択コントロール・ベクトルのレジスタが示されている。この装置の実施形態が、状態機械を表すのに必要なストレージに関して効率的であることに留意されたい。１６ノードの機械の場合に、５４バイトのレジスタだけが必要である。
【００６９】
図７に、チップ上で数千個の有限状態オートマトンを実装する実施形態の装置の使用を示す。単一の状態機械の規則的でコンパクトなデータパスが、複数回インスタンス化され、複数の行又はタイルの密なアレイにつながる。数千個のオートマトンを、単一のチップに収容することができる。
【００７０】
例示的アーキテクチャの説明で、この装置の１つの実施形態を説明したが、複数の代替実施形態が可能であることに留意されたい。
【００７１】
例示的な装置では、ノード要素と同一の個数の状態遷移評価シンボルを提供するソリューションを使用した。状態機械アーキテクチャのもう１つの実施形態では、相互接続と同一の個数のシンボルがあり、その結果、Ｍ＝３２の場合に、３２×３２又は１０２４個のシンボルがあり、このそれぞれが、１０２４個の可能な状態遷移の１つを制御する。
【００７２】
状態機械アーキテクチャの基本構成要素を使用するより大きい状態機械の構成
図８（ａ）に、より大きいグラフの状態機械基本構成要素の階層的使用によってより大きい状態機械の実現を可能にする状態機械アーキテクチャの実施形態を示す。選択された個数のインスタンス化されたノードを有する状態機械アーキテクチャの実施形態が、基本構成要素として選択されている。一実施形態で、この基本構成要素を図２に示されたものとすることができる。もう１つの実施形態で、この基本構成要素を図４に示されたものとすることができる。この基本構成要素を、より大きいグラフのスーパーノードとして扱うことができる。したがって、より大きい状態機械を実装するより大きいグラフは、複数のスーパーノードからなる。これらのスーパーノードは、本状態機械アーキテクチャの特徴を表すものと同一の技法を使用して接続される。グローバル・クロック又はスーパーノード・クロックが、より大きいグラフの評価を制御する同期化機構として使用される。この技法を使用することによって、より大きい状態機械を、状態機械基本構成要素の階層的使用によって構成することができる。
【００７３】
図８（ｂ）に、より大きい状態機械を実現するために基本構成要素の相互接続の代替方法を使用することによってより大きい状態機械の実現を可能にする、状態機械アーキテクチャの実施形態を示す。選択された個数のインスタンス化されたノードを有する状態機械アーキテクチャの実施形態が、基本構成要素として選択されている。一実施形態で、この基本構成要素を図２に示されたものとすることができる。もう１つの実施形態で、この基本構成要素を図４に示されたものとすることができる。この基本構成要素を、より大きいグラフのスーパーノードとして扱うことができる。したがって、より大きい状態機械を実装するより大きいグラフは、複数のスーパーノードからなる。図８（ｂ）には、より大きい状態機械を実現するために基本構成要素を相互接続する２つの代替の方法が示されている。一実施形態で、スーパーノード又は状態機械のすべてが、グローバル通信バスに直接に接続され、このバスを介して互いに通信する。もう１つの実施形態で、スーパーノードが、木として編成される。この方法を使用すると、状態機械の階層的に編成された木が、実装され、入力データに対して評価される。
【００７４】
図９（ａ）に、従来技術に対する、状態機械技法での例示的状態機械アーキテクチャの実施形態のストレージ及び性能の利益を示す。図９（ａ）の表からわかるように、例示的アーキテクチャは、非常に高い評価速度という利益と共に、オートマトンの状態のための減らされたストレージという利益を同時に提供する。例示的状態機械アーキテクチャは、ＮＦＡを実装するので、状態機械の状態のストレージは、オートマトンのノードの個数に比例する（Ｒ文字正規表現の場合に、これはＲに比例する）。評価の速度は、市販マイクロプロセッサを使用して可能な速度より大幅に高い。
【００７５】
図９（ｂ）に、状態機械アーキテクチャの実施形態を使用することによる、メモリ・ボトルネックの除去を示す。例示的状態機械アーキテクチャは、ＮＦＡを実装するので、状態機械の状態のストレージは、オートマトン内のノードの個数に比例する（Ｒ文字正規表現の場合に、これはＲに比例する）。これは、ＤＦＡベースの手法に必要なストレージよりかなり小さい。ストレージは、数千個のそのような状態機械を単一チップに収容することを可能にするのに十分に小さい。例示的状態機械アーキテクチャのクリティカル評価サイクル・タイム中に外部メモリにアクセスする必要は全くない。したがって、このソリューションでは、マイクロプロセッサ・ベースの手法の性能を制限するメモリ・ボトルネックが除去される。
【００７６】
本発明の多数の変更及び修正が、疑いなく、前述の説明を読んだ後に当業者に明白になるので、例として図示され、説明された特定の実施形態が、制限的に検討されることを全く意図されていないことを理解されたい。したがって、さまざまな実施形態の詳細への言及は、請求の範囲を制限することを意図されたものではなく、請求の範囲は、本発明に必須とみなされる特徴だけを列挙するものである。
【図面の簡単な説明】
【００７７】
【図１ａ】従来技術の状態機械技法のストレージ及び性能の制限を示す図である。
【図１ｂ】従来技術の状態機械技法のメモリ・ボトルネックを示す図である。
【図２】３状態を有する状態機械の状態機械アーキテクチャの一実施形態を示す図である。
【図３ａ】正規表現が、非決定的有限状態オートマトン（ＮＦＡ）の有限状態機械記述にどのようにマッピングされるかを示す図である。
【図３ｂ】ノード要素ごとに１つの評価シンボルを有する３状態非決定的有限状態オートマトン（ＮＦＡ）を評価するための状態機械の使用を示す図である。
【図４】状態機械アーキテクチャを使用する非決定的有限状態オートマトンを実現する１つの実施形態を示す図である。
【図５】有限状態オートマトンを実装する状態機械アーキテクチャの一実施形態を示す高水準ブロック図である。
【図６】有限状態オートマトンを実装する状態機械アーキテクチャの一実施形態を示すプログラマからの図である。
【図７】集積回路チップ上で数千個の有限状態オートマトンを実装する実施形態の装置の使用を示す図である。
【図８ａ】より大きいグラフの状態機械基本構成要素の階層的使用によってより大きい状態機械の実現を可能にする状態機械アーキテクチャの実施形態を示す図である。
【図８ｂ】より大きいグラフの状態機械基本構成要素の使用によってより大きい状態機械の実現を可能にする状態機械アーキテクチャの実施形態を示す図である。
【図９ａ】従来技術に対する、状態機械技法での例示的状態機械アーキテクチャの実施形態のストレージ及び性能の利益を示す図である。
【図９ｂ】状態機械アーキテクチャの実施形態を使用することによる、メモリ・ボトルネックの除去を示す図である。
【図１ａ】
2005537550.tif 000003
【図１ｂ】
2005537550.tif 000004
【図２】
2005537550.tif 000005
【図３ａ】
2005537550.tif 000006
【図３ｂ】
2005537550.tif 000007
【図４】
2005537550.tif 000008
【図５】
2005537550.tif 000009
【図６】
2005537550.tif 000010
【図７】
2005537550.tif 000011
【図８ａ】
2005537550.tif 000012
【図８ｂ】
2005537550.tif 000013
【図９ａ】
2005537550.tif 000014
【図９ｂ】
2005537550.tif 000015
【国際調査報告】
2005537550.tif 000016
2005537550.tif 000017
2005537550.tif 000018