JP4555088B2 - データ内のパターンの高速文脈サーチ及び特徴付けを実行するためのプログラム可能な規則処理装置 - Google Patents

Description

関連出願

本願は、２００２年８月２８日出願の、米国仮特許出願第６０／４０６，８３４号の非仮出願である。

本発明は、情報処理の分野に関し、詳細には、コンテンツの解析と処理の分野に関する。

コンピューティングと通信の重要な傾向は、コンテンツの解析と処理に富んだ環境の登場をもたらしている。これらの環境は、メッセージ、ドキュメント又はパケットなどのコンテンツのサーチ、構文解析、解析、解釈、変換などためのファンクションのクラスに関して高性能でかつプログラム可能性であることを必要とする。このような豊富なコンテンツの解析と処理を重視する顕著な分野は、コンテンツ認知ネットワーキング、コンテンツベースのセキュリティ・システム、調査、分散コンピューティング、無線通信、コンピュータのヒューマン・インターフェース、情報の記憶や検索のシステム、意味ウェブ上のコンテンツ・サーチ、バイオ情報科学などを含む。

コンテンツ認知ネットワーキングの分野は、パケットとメッセージをどこに経路指定又は転送するかを決定するために、パケット又はメッセージ内部にあるコンテンツのサーチと検査を必要とする。このような検査は、ネットワーク接続のデータ転送速度である「ワイヤ・スピード」で伝送中のメッセージに対して実行される必要がある。最近のネットワークのワイヤ・レートが１００Ｍｂｉｔ／秒から４０Ｇｂｉｔ／秒までの範囲であるとするならば、コンテンツ検査ファンクションが実行されなければならない速度に対しては、甚大な重圧が掛かる。

コンテンツベースのセキュリティ・システムや調査・監視システムには、セキュリティ違反又は侵入の可能性があるか否かを判定するために、メッセージ又はパケットのコンテンツを解析し、一組の規則を適用することが必要である。通常、最近のネットワーク侵入検出システム（ＮＩＤＳ）上では、すべての潜在的なシステムの脆弱性を発見するために、多数のパターン、規則、式がワイヤ・スピードで入力ペイロードに適用される必要がある。ネットワークとコンピューティングインフラストラクチャが継続的に発展するとするならば、新たな脆弱性も引き続き発生することになる。さらに、検出から逃れるために、侵入者は益々高度な攻撃を使用する。侵入検出システムは、システム上のすべての周知の攻撃を検出することが可能であり、かつ新しい攻撃を示す異常で不審な挙動を検出するのに十分なほど知的でなければならない。これらすべての要因は、コンテンツの解析と処理に対して、プログラム可能性と非常な高性能の両方を要求することに繋がる。

分散型のクラスタ化されたコンピュータの出現により、タスクは、現在、複合ジョブを完了するために相互に共同し通信する、複数のコンピュータ又はサーバに分散されている。この分散は、コンピュータ通信の急速な増加をもたらし、したがってこのようなメッセージ処理に対して高性能が要求される。汎用データ交換に対する新しい標準としてＸＭＬ（拡張マークアップ言語）が登場したことにより、アプリケーションは、「アプリケーション層データ転送」としてＸＭＬを使用して相互に通信する。メッセージとドキュメントは、現在、ＸＭＬマークアップに埋め込まれている。すべてのメッセージ処理は、まずＸＭＬドキュメントを構文解析し、関連コンテンツを抽出し、解釈することを必要とし、次いであらゆる変換とフィルタリングを必要とする。これらのファンクションは高速メッセージで実行される必要があるので、これらはコンピュータ処理にとって非常に要求が厳しくなる。

解放された通信及び無線ネットワークの成長により、無線デバイスからの情報のアクセスが増加した。クライアント・デバイスの軽量という要因を考えれば、このデバイスに配信されるデータはフィルタリングされ、そのペイロードは小さく維持されることが重要である。将来の環境は、回線インフラストラクチャからのＸＭＬコンテンツを無線インフラストラクチャの軽量なコンテンツ（無線マークアップ言語又はＷＭＬを使用して）に変換することになるであろう。無線ネットワークの使用が増加するに伴い、このコンテンツ変換ファンクションが、その取り扱いのための効率的なソルーションが必要となるほどに一般的になるであろう。

もう一つの重要な新たに発生する必要性は、スピーチのようなヒューマン・インターフェースを使用してコンピュータと通信し、対話する能力である。スピーチ処理や自然言語処理は、コンテンツ・サーチ、字句解析、コンテンツ構文解析、文法処理に極度に集約している。ボイス・ストリームが一度テキストに変換されると、スピーチ・システムは、そのスピーチを理解するために、多量の語彙や構文・意味論規則を、着信テキスト・ストリームに適用する必要がある。

世界中に広まったウェブの登場と成長は、甚大なコンピュータの負荷を情報検索（ＩＲ）システムに課した。情報は、高速でこのウェブに追加され続ける。この情報は、通常、ワードの網羅的語彙に対して完全に索引が付けられ、サーチ・エンジンとＩＲシステムのデータベースに追加される。情報が継続的に作成され、追加されるので、インデクサは「常時オン」である必要がある。効率的なリアルタイムの文脈サーチを行うために、索引付けファンクション用の高性能パターン照合・システムがある必要がある。

豊富なコンテンツの解析と処理を重視する別の分野は、バイオ情報科学の分野である。遺伝子解析とプロテオミクスは、遺伝子配列と構造に対する複合サーチや解析アルゴリズムのアプリケーションを必然的に伴う。ここでもまた、このような計算は、高性能のサーチ、解析、解釈の能力を必要とする。

したがって、登場しつつある将来のコンピュータ環境と通信環境は、コンテンツの豊富な解析と処理を重視する。このような環境は、ドキュメント、メッセージ又はパケットのコンテンツに対するサーチ、字句解析、構文解析、特徴付け、解釈、フィルタリング、変換などのファンクションの効率的かつプログラム可能なソルーションを必要とする。

これらの豊富なコンテンツ処理ファンクションの中心には、文脈やコンテンツベースのサーチとナビゲーション、さらに豊富な連想ルックアップを実行するためのオペレーションがある。

従来技術では、サーチとルックアップの処理は、通常、２つの方法のうちの１つで実行されてきた。第１に、このような処理は、コンテンツ・アドレッサブル・メモリ（ＣＡＭ：content addressable memories）、コンパレータ・ハードウェア、専用論理の組み合わせなどを使用する、固定された特定用途向けＩＣ（ＡＳＩＣ）ソルーションを使用して実行されてきた。例えば、サーチ規則はコンテンツ・アドレッサブル・メモリに記憶され、データは、一度に１バイト又は１語シフトさせて構造全体がストリーミングされる。あるいは、特定のコンパレータが、着信データ内の特定値を認識するために固定された位置に配置される。一致の発生は、専用論理によって目標アプリケーションの要件のように記録され、消費される。固定のＡＳＩＣ方式は性能を向上させることができるが、容易なプログラム可能性に欠け、したがってそのアプリケーションは大幅に制約を受ける。さらに、対象のソルーションごとに特定チップを設計し、調整することに関連する費用は法外なものである。

第２に、従来の汎用マイクロプロセッサは、豊富なサーチとルックアップ・ファンクション、さらにそれに関連するコンテンツ処理を取り扱うために使用されてきた。マイクロプロセッサは、完全にプログラム可能なデバイスであり、発展しつつある問題の必要性に対処することが可能である。これは、ソフトウェアを容易に再プログラムすることによって、新しい機能性を再展開することができる。しかし、従来のマイクロプロセッサは、豊富なコンテンツの解析と処理に提供できる性能レベルが限定されている。

コンテンツの解析に対する性能の制限は、マイクロプロセッサのアーキテクチャの設計及び発展に特有のものである。コンピューティング・ユニットとして始まったマイクロプロセッサは、１、２、４、８バイト・ワードに対して算術演算を実行する。その後、コンピュータ処理の分野が発展するに従い、登場しつつある分野に対処するために、より多くの機能性がマイクロプロセッサに漸次追加された。その結果、汎用マイクロプロセッサは、非常に広範囲に亘るアプリケーション全体に対して機能するが、特にどれか１つに対して非常によく調整されたものではない。基本的に、コンテンツの解析の必要性に適用される場合、マイクロプロセッサのアーキテクチャには、２つの主な制限がある。つまり、（１）大きなデータ・セットに対して超並列の微粒子パターン照合と比較のオペレーションを同時に実行するファンクションに欠けること、（２）入力データに基づいた多数の高速な状態遷移と効率的な複数方向制御フロー変更を行う能力に欠けることである。

マイクロプロセッサの命令セットは、命令が単一の順序付けられたシーケンスで実行される必要のあるスカラー命令セットである。典型的なマイクロプロセッサの命令セットは、レジスタに記憶された単一６４ビットの量と、異なるレジスタに記憶された別の６４ビットの量を比較する。この比較は、位置合わせされた２つのオペランドによって実行される。この比較がパターン・サーチの目的で実行される場合、この比較は、これらオペランドの１つ又は両方を毎回バイトの可変数だけシフトさせた後で、反復的にインボークする必要がある。しばしば、このような反復されたシフトは、反復ごとにループの末尾のコードからループの最上のコードまで制御を転送する制御フロー変更により１ループで実行される。マイクロプロセッサにおける制御フロー変更は、新しいコードのシーケンスに分岐することによって達成される。最近のマイクロプロセッサは高度にパイプライン化されているので（カリフォルニア州サンタクララのＩｎｔｅｌ社製のＰｅｎｔｉｕｍ（登録商標）ＩＩＩ及びＰｅｎｔｉｕｍＩＶプロセッサのような製品の２０〜３０ステージ程度）、分岐のために被る性能の犠牲は著しい。マイクロプロセッサのパイプライン全体は、取られた分岐上でフラッシュされる必要がある。したがって、制御フロー変更に応じて、所望の経路から命令がパイプラインに十分に供給された状態にしておくために、そのようなプロセッサに高度な分岐予想技術が適用される必要がある。しかし、大部分の分岐予想技術は、経験則による、統計的な性能の改善だけを提供する。この結果、制御フロー変更は、その大部分が、配信可能な性能レベルに失速と非決定状態とを導入する。

マイクロプロセッサを最大限活用するために、多数のサーチとパターン照合アルゴリズムが発展した。Ｂｏｙｅｒ−Ｍｏｏｒｅアルゴリズムは、所与のデータ・セットでのパターンの発生を発見するために、マイクロプロセッサで利用される最もよく知られた技術の１つであると広くみなされている。このアルゴリズムは、一度に１つのパターンしか処理せず、１データ・セットで複数のパターンをサーチする場合には反復的に呼び出す必要がある。サーチされるべきパターンごとに、このアルゴリズムは当該データ・セットを通して連続的に進行し、事前に特徴付けられたパターンから得た観察に基づいて選択的な比較を行う。このアルゴリズムは、所与のデータ・セット内の合計比較数を低減することにより、他のパターン照合アルゴリズムよりも優れた性能を提供する。しかし、このアルゴリズムの連続的であるという性質により、その性能は、マイクロプロセッサ・アーキテクチャの基本的な制約、すなわちスカラー命令セットと分岐に対して課せられた犠牲とにより制限を受ける。

マイクロプロセッサの上記のアーキテクチャ上の制限があるため、従来のマイクロプロセッサの効率や能力には、上記の登場しつつあるコンピューティング及び通信環境によって大きな問題が課される。これらの議論を支持するために、いくつかのデータ・ポイントを提供することができる。例えば、Ｓｎｏｒｔのようなネットワーク侵入検出システム（ＮＩＤＳ）では、着信パケットに対して数百ストリングの署名検出を加えることが既に望ましいとされている。８バイト・パターンの署名によるこの作業負荷を、Ｂｏｙｅｒ−Ｍｏｏｒｅパターン照合アルゴリズムの改善版を利用する商用マイクロプロセッサ・ベースのシステム内の３ＧＨｚ Ｐｅｎｔｉｕｍ ＩＶプロセッサに対して実行することにより、パケット・レートは５０Ｍｂｐｓ未満に制限される。同様に、そのようなプラットフォーム上のＸＭＬドキュメントの構文解析は、１０ＭＢ／ｓ範囲に制限され、スピーチ処理は制約された文法と語彙に対して１リアルタイム・ストリームに制限される。これらのデータ・ポイントは、２００３又は２００４の従来型マイクロプロセッサが、豊富なコンテンツの解析と処理を１００Ｍｂｐｓ範囲程度の速度で配信することができることを示す。しかし、その時間枠により、１Ｇｂｐｓから１０Ｇｂｐｓの間のデータ転送速度は、企業ネットワークや環境では珍しいものではなくなる。明らかに、従来のマイクロプロセッサが提供できる性能と、環境が要求する性能の間には、１から２桁の大幅な不一致がある。目標速度で所望のファンクションのいくつかを実行するために複数の並列マイクロプロセッサ・システムを利用することは可能だが、これはシステムのコストを大幅に増大させる。これらの目標ファンクションに対して、より効率的なソルーションが求められていることは明らかである。

コンテンツの解析と処理に対してより適しており、メッセージ、パケット又はドキュメントのコンテンツの文脈サーチ、字句解析、構文解析、解釈、変換を含む一組のファンクションに対して効率的な、プログラム可能な処理装置に対する新しいソルーションが求められている。

文脈サーチを実行するための規則プロセッサに関して本明細書で開示される方法及び装置を説明する。一実施態様では、上記プロセッサは、複数の入力ペイロード・サーチ・レジスタとそのサーチ・レジスタに連結されたサーチ実行ハードウェアとを含む。本ハードウエアは、１つ又は複数のパターン・サーチを指定し、かつ１つ又は複数のパターンをサーチ・レジスタのコンテンツに与える１つ又は複数の命令の実行に呼応して、並列パターン照合によりサーチ・レジスタのコンテンツに対して１つ又は複数の文脈サーチを実行する。

本発明は、本発明の様々な実施形態に関して以下で提供される詳細な説明と添付の図面から、より完全に理解されよう。しかし、これら説明と図面は、本発明を特定の実施形態に限定するものとして解釈されるべきではなく、説明と理解のためのものである。

１ドキュメント、メッセージ、その他のコンテンツの中にある任意の長いパターンの高速文脈サーチを実行するためのプログラム可能な規則処理装置を説明する。規則プロセッサは、コンテンツのサーチと解析に合わせて調整されたアーキテクチャを提供する。一実施形態では、規則プロセッサが、コンテンツ・ペイロードに対する規則の高速並列と再帰的順序付けを可能にする。これによって、規則、すなわち文法に集約した作業負荷の効率的な処理が可能になる。

アーキテクチャとしては、規則プロセッサは、一組の入力ペイロード・サーチ・レジスタを利用する。サーチ・レジスタ・ファイルは、様々なサーチ規則に提示されるべき入力データ（すなわちコンテンツ・ペイロード）を保持する。データはメモリからサーチ・レジスタにロードしても、又は規則プロセッサ内の他の資源に対してサーチ・レジスタから出し入れしてもよい。一実施形態では、サーチ・レジスタのコンテンツに対して様々なサーチを実行することができる。これらのサーチは、ペイロード・データに提示されるサーチ命令又はサーチ規則の形式で指定される。サーチ実行ハードウェアは、サーチ・レジスタに連結されている。このハードウェアは、サーチ・ファンクションの結果を計算するために必要とされるパターン照合と処理ファンクションを実行する。

図１は、サーチ・レジスタ１０１とサーチ実行ハードウェア１０２とを含む規則プロセッサの一実施形態のブロック図である。サーチ命令１０３は、サーチ・レジスタ１０１とサーチ実行ハードウェア１０２とに提示される。プロセッサは、規則／命令メモリ１０４と称される命令ストアと、一実施形態では命令シーケンサ１０５と命令ポインタ１０６とを含む命令の流れを制御するための装置とをさらに含む。

一実施形態では、サーチ・レジスタ１０１は、それぞれ１バイトずつの２Ｋエントリを有するレジスタ・ファイルを含む。ここで、サーチ・レジスタ１０１内の値は、１１ビットのレジスタ・アドレスによってアドレス指定される。したがって、サーチされるべき２ＫＢのコンテンツ・データをサーチ・レジスタ１０１にロードすることができる。

典型的なサーチは、命令又は規則をサーチ・レジスタに提示することを必然的に伴う。この規則は、１つ又は複数の追加サーチパラメータと共に１つのパターンを指定する。一実施形態では、サーチ・ファンクションが多数の結果を返す。これらは、サーチ・レジスタ内のパターンとコンテンツとの間で一致が見つけられたか否かの指示と、ペイロード・サーチ・レジスタ内で一致が生じた場所を示す一致場所とを含む。

追加サーチ制御パラメータが、規則プロセッサによってサーチ実行ハードウェア１０２に提供される。サーチ命令は、目標サーチ・パターンを含む一組のバイトと共にマスク・ベクトルを提供する。マスク・ベクトルは、目標パターンの１つ又は複数のバイトに対応するビットで構成することができる。一実施形態では、サーチ・オペレーション中に無視されるべき目標パターンの特定バイトが、マスク・ベクトル内の対応するビットを０又は１の所定の論理レベルにセットすることにより選択される。したがって、サーチに使用される目標パターンのサイズを縮小することができる。さらに、規則処理命令は、サーチウィンドウを構成する開始場所と終了場所、又はサーチが制約されるサーチ・レジスタ１０１のバイト範囲を指定することができる。

サーチ命令に対する追加パラメータは、サーチが不成功だった場合に規則プロセッサが利用する分岐アドレスを含むことができる。サーチ実行ハードウェア１０２のデータ経路の幅よりも著しく長い数ストリングのバイトのサーチが、全く一致なしに失敗するか、又は最初の数バイトだけがサーチ・レジスタ１０１のコンテンツと一致した後で失敗した場合に、このファンクションは規則プロセッサの性能を強化する。規則プロセッサは、現行ストリングに対する最後のサーチ命令の後に続く命令に分岐することによって、現行ストリングに対する残りのサーチ命令を省略することができる。

サーチ命令の一例は、ウインドウ・ファインド・ファースト・フォーワード(windowed-find-fist-forward)命令である。一実施形態では、ウインドウ・ファインド・ファースト・フォーワードサーチにおいて、ある規則内にある、又はある規則によって指定された８バイト・パターン、８ビットのマスク、サーチ・レジスタ１０１内にある２ＫＢのコンテンツ・データ（例えば、ドキュメントデータ）の開始バイトを指し示す開始場所オフセット・アドレス、さらにサーチ・レジスタ１０１内にある２ＫＢのコンテンツ・データ（例えば、ドキュメントデータ）の終了バイトを指し示す終了場所オフセット・アドレスが与えられると、サーチは、このアドレスが終了場所オフセット・アドレスより前に開始するならば、マスクされたパターンと一致する指定された開始場所アドレスの後の最初のストリングのサーチ・レジスタ１０１内にある開始アドレス（例えば、１１ビット・ベクトル）を戻す。別の例では、ウインドウ・ファインド・ファースト・リバース(windowed-find-first-reverse)サーチを実行することができる。一実施形態では、このウインドウ・ファインド・ファースト・リバース・サーチで、規則内の８バイト・パターン、８ビットのマスク、サーチ・レジスタ１０１内の２ＫＢのコンテンツの開始バイトを指し示す開始場所オフセット・アドレスと、サーチ・レジスタ１０１内の２ＫＢのコンテンツの終了バイトを指し示す終了場所アドレスとが与えられると、サーチは、このアドレスが開始場所オフセット・アドレスより後に開始するならば、マスクされたパターンと一致する指定された終了場所アドレスの前の最後のストリングの開始アドレス（例えば、１１ビット・ベクトル）を戻す。

規則プロセッサは、ペイロード・データに適用されるべき規則又は一組の規則を含む制御ストア又は規則メモリ１０４も提供する。一実施形態では、メモリ１０４は、複数の一組の規則、複数の命令シーケンス、又はサーチ・レジスタ１０１で適用され検出される必要のあるパターン、規則、式又は文法を記述したコードを保持する。規則語彙は、限定はしないが、いくつかのレジスタに配信された個別及び複数の一致情報、規則プロセッサの出力ペイロードのオフセット、アドレスを生成するためのプリミティブ、さらにはサーチ結果に適用されるべき論理演算子と計算演算子と共に、完全一致又は部分一致によるグローバルサーチ又はローカル（windowed:窓付き）サーチを含めて、オペレーションの範囲を指定することができる。このような規則は、上記の様々なパラメータを指定する複数のフィールドから構成することができる。各パラメータは、規則内で直接的に指定しても、あるいは使用されるべき値を含んだレジスタ又はメモリ場所に対するポインタを使用することによって間接的に指定してもよい。直接的な指定と間接的な指定の両方が可能な実施形態では、そのようなフィールドはそれぞれに、直接的指定と間接的指定のどちらが利用されているかを示す追加のサブフィールドを含むことができる。

次の説明では、本発明の完全な理解を提供するために多数の詳細が述べられる。しかし、当業者には、本発明は、これらの具体的詳細なしに実行できることが明らかになるだろう。他の場合、本発明を分かりにくくすることを避けるために、周知の構造及びデバイスは、詳細にではなくブロック図形式で示される。

この後に続く詳細な説明の一部は、コンピュータ・メモリ内のデータ・ビットに対するオペレーションのアルゴリズムと記号表現に関して示される。これらのアルゴリズムの記述及び表現は、データ処理の当業者が、他の当業者にその作業のコンテンツを最も効果的に伝えるために使用する手段である。ここでは、また一般的には、アルゴリズムは、所望の結果をもたらす首尾一貫した一連のステップである。これらのステップは、物理量の物理的操作を要求するステップである。必須ではないが、通常は、これらの量は、記憶され、転送され、結合され、比較され、それ以外の操作を受ける電気信号又は磁気信号の形式をとる。原則として一般的な用途であるという理由から、これらの信号をビット、値、要素、記号、文字、用語、数字などと称することが場合によっては便利であると証明されている。

しかし、これら及び類似の用語はすべて、適切な物理量に関連付けられるべきであり、これらの量に適用された便宜的なラベルに過ぎないことを銘記されたい。次の解説から明らかになるように、特に具体的に述べられない限り、本明細書を通して、「処理」又は「コンピューティング」又は「計算」又は「決定」又は「表示」などの用語を使用した解説は、コンピュータ・システムのレジスタ及びメモリ内で物理（電子）量で表現されたデータを操作し、コンピュータ・システムのメモリ又はレジスタ又は他のそのような情報記憶、伝送又は表示デバイス内で物理量として同様に表現される他のデータに変換する、コンピュータ・システム又は類似の電子コンピューティング・デバイスの動作及び処理に言及するものと理解されたい。

本発明は、本明細書のオペレーションを実行するための装置にも関する。この装置は、要求された目的のために特別に構築しても、コンピュータに記憶されたコンピュータ・プログラムによって選択的にアクティブにされ又は再構成された汎用コンピュータを含んでもよい。このようなコンピュータ・プログラムは、限定はしないが、フロッピー（登録商標）・ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含むいかなるタイプのディスク、読み出し専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カード又は電子命令を記憶するのに適しており、それぞれがコンピュータ・システム・バスに連結されたいかなるタイプの媒体のような、コンピュータ可読記憶媒体に記憶することができる。

本明細書で提示したアルゴリズム及び表示は、いかなる特定のコンピュータ又は他の装置にでも本質的に関連するものではない。様々な汎用システムは、本明細書の教示に関連したプログラムと共に使用することができるが、要求される方法ステップを実行するためのさらに特化した装置を構築することが便利であると証明することができる。様々なこれらのシステムに要求される構造は、以下の説明から明らかになろう。さらに、本発明は、いかなる特定のプログラミング言語に関して説明されるものでもない。本明細書で説明するような本発明の教示を実施するために、様々なプログラミング言語を使用することができることが理解されよう。

機械可読媒体は、情報を機械（例えば、コンピュータ）によって可読の形式で記憶又は送信するためのいかなる機構をも含む。例えば、機械可読媒体は、読み出し専用メモリ（「ＲＯＭ」）、ランダム・アクセス・メモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ・デバイス、電子信号、光信号、音響信号又は他の形式の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号など）などを含む。

規則エンジン・アーキテクチャ例
規則処理アーキテクチャを、コンテンツ・ペイロードに対する規則の並列かつ再帰的順序付けを考慮した、コンテンツの解析用規則プロセッサでの使用に関して説明する。このアーキテクチャは、複数の高速コンテンツ・ベースの状態遷移を行う能力に結びつけられた並列パターン照合能力を提供する。

一実施形態では、規則プロセッサは、サーチ・レジスタに含まれるコンテンツに対する、プログラム・ストアからの実行のための規則を適用するための、命令又は規則シーケンサを含む。規則とコンテンツは、例えばパターン照合、字句解析、構文解析、解釈ファンクションのような、１つ又は複数のオペレーションに合わせて特に調整された規則語彙をサポートする実行エンジンによって消費される。

一実施形態では、規則プロセッサは、ドキュメント、ストリーム、メッセージ又はパケットの任意の位置から開始される、任意の長いパターンに対する、固定されたパターン又は固定されていないパターンの優先づけられたかつ方向付けられたサーチと、窓付きの範囲限定されたサーチの一連を実行する。パターンだけでなく範囲制御とプログラム制御フロー（例えば、分岐アドレス）を、プログラム・ストア内に含まれる規則で静的に指定しても、規則内で述べられたポインタ又は索引を使用してレジスタ・ファイルから間接的に動的に選択してもよい。

規則プロセッサは、一部には、サーチ・レジスタに連結された、特化したパターン照合・ハードウェア構造を使用してサーチを実行する。一実施形態では、規則プロセッサは、豊富なサーチ、ソート、優先順位付けファンクションをサポートする。一実施形態では、規則処理ハードウェアは、サーチ・アレイと、サーチ・レジスタに含まれる２Ｋｂのコンテンツ・データ（例えば、ドキュメント・データ）上で直接的に動作するソータ・ブロックとを有する４ステージのパイプラインとして構成される。４ステージは、（１）規則メモリからの規則フェッチと規則復号、（２）間接フィールドの規則アセンブリ、（３）サーチ・レジスタ内の値に対するサーチ実行オペレーション、（４）結果の配信の前の、サーチ・オペレーションの結果に対するソート・オペレーションである。

規則プロセッサは、サーチの１つ又は複数の規則をサーチ・レジスタ構造に提示する。一実施形態では、サーチ・レジスタは、各エントリが１バイト幅である、２ＫＢのレジスタ・ファイルである。サーチされるべきデータがサーチ・レジスタ・ファイルにロードされる。各規則は、記憶されたデータの中にパターンがあるか否かを判定するために、サーチ・レジスタ・ファイルに提示されたパターンを指定する。パターンをさらに構成し、かつ／又はサーチで使用中のパターンのサイズを縮小するために、マスクを提供することもできる。

図１は、規則プロセッサの一実施形態のブロック図である。図１を参照すると、サーチ・レジスタ１０１とサーチ実行ハードウェア１０２は、サーチ命令１０３と共に集合的に示されている。サーチ命令１０３は、図２Ａでさらに説明される。図２Ａを参照すると、サーチ命令２０１は、サーチ・オペレーションのタイプを記述するオペコード２０１ａと、サーチ・パターン２０１ｂと、現行サーチ命令に関連したパターン内のバイトを指定するマスク２０１ｃと、現行サーチ命令に関連したサーチ・レジスタ内の場所の開始と終了の限界をそれぞれに指定する２つのオフセット２０１ｄ、２０１ｅとを含む。サーチ実行ユニット２０２は、一実施形態では、サーチ・オペレーションの成功の指示から構成されて、限定はしないが、サーチ・オペレーションのサーチ命令を満たすサーチ・レジスタ内の場所を示す索引のような、１つ又は複数のパラメータをさらに含む結果２０３を出力する。

サーチ実行ハードウェア２０２は、図２Ａに示すように、サーチ・レジスタ２０２ａとソータ２０２ｂとを含む。サーチ・レジスタ２０２ａは、サーチを受けることのできるドキュメント、メッセージ、パケット又はいかなる他の周知のデータ・ソースからのコンテンツであってもよいサーチ可能なデータを記憶する。サーチ・レジスタ２０２ａのサイズは、任意のＭバイトであってよく、一実施形態では、それぞれにＮバイトのＭ行の、サーチ・アレイ２０２ｃと呼ばれる、より大きなアレイに構成される。サーチ・レジスタ２０２ａからのデータがサーチ・アレイ内に複製して記憶される。サーチ・レジスタのこの実施形態は、Ｎ個の隣接バイト・パターンに対するサーチに関して、より高い性能を含むので、複数の理由から好ましい。

一実施形態では、サーチされるべきデータは、アドレス・デコーダ２１２によって復号される、アドレス・ジェネレータ２１１から生成されたアドレスに基づいて、データ・ジェネレータ２１３を使用することによりサーチ・レジスタ２０２ａに記憶される。記憶の処理は、サーチ・レジスタ２０２ａにあるサーチ可能データのサイズを記録することも必然的に伴う。サーチ・レジスタ２０２ａの容量よりもサイズの小さいデータ・セットの場合、サーチ・レジスタ２０２ａは、サーチ・オペレーションを適切なデータに制約する機構を提供する。一実施形態では、データ・ジェネレータ２１３は、サーチ・アレイ２０２ｃの残りの場所にあるサーチ・オペレーションに対して無視されるデータになることが演繹的に確立されるパターンを記憶することができ、又は一代替形態では、サーチ・レジスタ２０２ａは、サーチ・アレイ２０２ｃの適切な場所をサーチ・オペレーションへの参加から無効にする。

指定されたパターンを見つける能力に加えて、サーチ・レジスタ２０２ａは、文字データに対する大文字小文字区別なしサーチのような、特別なサーチを実行する能力も提供することができる。このような特別なサーチ及び他の特別なサーチをサポートするために、サーチ・レジスタ２０２ａは、サーチ可能データの各バイトに関連付けられた追加情報を記憶することができる。一実施形態では、サーチ・レジスタ２０２ａは、大文字小文字区別なしサーチ又は定義済みクラスの文字に属する文字に対するサーチを可能にするサーチ可能データそれぞれに関連付けられた特別なビット・ベクトルを記憶することができる。

サーチ可能データがサーチ・アレイ２０２ｃを通して構成される方式とは関係なく、サーチ・アレイ２０２ｃはパターン２０１ｂとマスク２０１ｃを受け取る。パターン２０１ｂがサーチ・アレイ２０２ｃのエントリと比較される。一実施形態では、サーチ・アレイ２０２ｃはＮバイトのＭ行を有する。ここで、Ｎは、パターン２０１ｂ内と同じバイト数である。マスク２０１ｃは、サーチ中のパターンの一部ではないパターン２０１ｂのそれらのバイトの指示を提供する。すなわち、パターン２０１ｂがＮバイト未満のパターンである場合、マスク２０１ｃは、サーチ・アレイ２０２ｃがパターン２０１ｂのどのバイトを無視すべきかを指定する。一実施形態では、サーチ・アレイ２０２ｃは、サーチ・アレイ２０２ｃのＭ行のそれぞれに対する、サーチ中パターンがその特定の行に記憶されたコンテンツ・データと一致したか否かを示す出力線を有する。一実施形態では、出力が１の場合、パターンは、特定行内のコンテンツ・データと一致している。サーチ・アレイ２０２ｃのＭ個の出力ラインは、ソータ２０２ｂの入力に連結される。

ソータ２０２ｂは、サーチされるべきサーチ・レジスタ２０２ａの範囲の開始点と終了点をそれぞれ示すオフセット２０１ｄ、２０１ｅを受け取るように連結されているる。一実施形態では、これらのオフセットはｌｏｇ₂Ｍビット数である。サーチ・アレイ２０２ｃからの一致指示ラインと、オフセット２０１ｄ、２０１ｅにより指定された開始終了範囲に基づいて、ソータ２０２ｂはサーチ・アレイ２０２ｃの結果を処理する。このような処理は、１つ又は複数のオペレーションの処理を含む。これらのオペレーションは、オペレーションのタイプに従い特定の一致索引を出力する索引解決ファンクション(index resolution function)であってよい。一実施形態では、これらのオペレーションは、Ｆｉｎｄ＿Ｆｉｒｓｔ＿Ｆｏｒｗａｒｄ、Ｆｉｎｄ＿Ｆｉｒｓｔ＿Ｒｅｖｅｒｓｅ、Ｆｉｎｄ＿Ｐｏｐｕｌａｔｉｏｎ＿Ｃｏｕｎｔを含む。これらのオペレーションは、サーチ命令２０１のオペコード２０１ａにより指定される。ソータ２０２ｂは、サーチ・アレイ２０２ｃからの一致指示ラインと連動して後続オペレーションで使用することのできる、前のオペレーションの中間又は最終結果を記憶することができる。このようにして、前のオペレーションの結果を利用する一連のオペレーションを発行することにより、サーチ可能データ・セットを通して漸次ナビゲートするために、ソータ２０２ｂを使用することができる。さらに、ソータ２０２ｂは、前のオペレーションの結果を、任意の数の他のオペレーションが実行された後で実行することのできる後続オペレーションで使用するように記憶しておくために、レジスタ・ファイルに連結することもできる。ソータ２０２ｂの結果は、規則プログラム・オフセット（例えば、分岐アドレス）を生成するため、又はその生成を支援するために、図１の命令シーケンサ１０５のような、規則プロセッサ命令シーケンサにも連結することができる。

処理後、ソータ２０２ｂは、一致があるか否かを示す出力と、その一致に関連付けられた索引とを生成する。索引は、サーチ・レジスタ２０２ａの最上位に関して最初の一致が生じる場所又は最後の一致が生じる場所である、サーチ・レジスタ２０２ａの場所（アドレス）を示すことができる。あるいは、索引は、オフセットによって示される範囲内で生じた一致数を示すことができる。

オフセットによって指定された範囲は動的に変更できることに留意されたい。例えば、オフセット２０１ｄとオフセット２０１ｅによって指定される範囲にサーチ・アレイ２０２ｃのすべての行を含めておいて、最初のサーチ命令を最初にサーチ・アレイ２０２ｃに適用することができる。しかし、前のサーチ命令によって指定された範囲内にある一致ラインを含む場所からサーチが始まるように、最初のサーチ命令と一致が識別された後で、開始と終了の範囲を後続のサーチ命令で変更することができる。この能力は、汎用レジスタ・ファイルの値を参照するために規則又は命令のフィールドを可能にした、間接化技法のファンクションを使用して達成することができる。

図２Ａでは、一実施形態で、サーチ・アレイ２０２ｃはそれぞれ８バイトの２Ｋ行から構成される。したがって、サーチ・レジスタ２０２ａは２Ｋバイトのデータを保持する。サーチ・アレイ２０２ｃは複製されたデータを保持する。サーチ・レジスタ２０２ａの区別されたバイトで開始する各８バイトのストリングは、サーチ・アレイ２０２ｃのバイトの異なる行として記憶される。これらのストリングは、サーチ・レジスタ２０２ａからの区別されたバイトと、さらにサーチ・レジスタ２０２ａのそのバイトに続く７個の連続したバイトとから構成される。したがって、サーチ・アレイ２０２ｃの各行は、前行の７個の最上位バイトと、さらにそれら７バイトの右に付加された１つのすぐ上のバイトとを保持する。

一実施形態では、適切な８バイトのデータをソース・データから各行へ供給するデータ・ジェネレータ２１３によってサーチ・アレイ２０２ｃにデータがロードされる。

一実施形態では、８バイトのサーチ・パターンがそれぞれのサーチ命令に提示される。このサーチ・パターンは、サーチ・アレイ２０２ｃの８列のそれぞれが独自のバイトで提示されるように、サーチ・アレイ２０２ｃと位置合わせされる。これを図２Ｂに示す。図２Ｂを参照すると、状態バイト１から８が、行１から２Ｋのそれぞれに対してサーチ・アレイに記憶されている。図２Ｂに示す２Ｋの行と８列のサーチ・アレイの１要素として記憶されている各バイトについて、１個の信号ライン３１０が存在する。例えば、行１のバイト１は信号ライン３１０₁₁を生成し、行１のバイト２は信号ライン３１０₁₂を生成し、行２のバイト１は信号ライン３１０₂₁を生成し、等々である。記憶されているバイトが、その要素が属する同じ列に提示されるサーチ・パターンのバイトと一致する場合、各バイトに対する信号はサーチ・オペレーション中にアサートされる。この実施形態では、各行が８バイトを含むので、８個の信号ライン、例えば３１０₁₁から３１０₁₈が、当該行内のバイト・レベルの一致のそれぞれを示すために使用される。各行に対するバイト・レベルの一致は、行とマスク・リゾルバー・ブロック３１１のマスク１０２ｃのマスクと論理積演算される。論理積演算関数の結果は、各行で一致が生じたか否かの指示である。この実施形態では、サーチ・アレイは２Ｋ行を含むので、２Ｋの一致ラインがソータに出力される。このアレイ内の２つのバイト要素３１２の回路構成を図４に示す。この回路は、１クロック期間中にそのすべての行内で同時サーチを実行することにより、完全な並列サーチ・オペレーションを提供する方法で動作する。１回のサーチ・オペレーションが実行される際、１列内のすべてのバイト・レベル一致ライン４０１は、それぞれの記憶されたバイトとの一致を同時に示す。すべての列に対して同時に１つのサーチ・オペレーションがインボークされ、各行のマスクされた短縮ブロックが１つの行レベル一致を示すことを可能にする。したがって、サーチ・アレイのこの実施形態では、単一クロック中に、８個の隣接バイトからなるサーチ・レジスタ内のすべての２Ｋストリングの並列サーチが実行され、その結果が２Ｋ一致ラインに対して示される。

図３Ａは、ソータの一実施形態のブロック図である。図３Ａを参照すると、サーチ・アレイからの一致ライン３１０は、範囲マスク及び選択ユニット３０１に接続され、これに入力される。一実施形態では、一致ライン３１０は一致１から一致２０４８までを含む。範囲マスク及び選択ユニット３０１は、さらなる処理を実行するために、サーチ・アレイからのＭ個の一致ラインの行の範囲を指定する一対のオフセットを受け取る。一実施形態では、オフセットは、出力を提供するために一致ラインと論理積演算することのできる、２Ｋマスク・ビットに変換される１１ビットの数である。このような例を図３Ｂに示すが、同図では、開始範囲に対するオフセットは、ビットの剰余を１ビットとして１つ又は複数の０に変換され、範囲の終了に対するオフセットは、すべてのビットがそれ以降１になる特定ポイントまで末尾から通してすべて０に変換される。これらのレジスタを一致ラインと論理積演算することにより、当該範囲外の他の一致ラインはマスクされた状態で（例えば、所定の論理レベルに変更されて）、指定の開始と終了範囲内で生じた一致は変更されずに出力される。

範囲マスク及び選択ユニット３１０の出力は、索引解決ファンクション・ユニット３０２の入力と連結される。一実施形態では、索引解決ファンクション・ユニット３０２は、範囲マスク及び選択ユニット３０１の出力に対して実行される１つ又は複数の関数を含む。例えば、図示するように、ソータは、非マスク一致ラインによって示されるように、指定されたＮバイト・パターンとサーチ・アレイのコンテンツ・データの間の、（サーチ・アレイの最上位に関する）最初の一致の発生を見つけるために、１つの昇順優先順位エンコーダ３０２Ａを含む。非マスク一致ラインによって示されるように、Ｎバイト・パターンとサーチ・アレイのコンテンツ・データの間の、（サーチ・アレイの最上位に関する）最後の一致の発生を見つけるために、降順優先順位エンコーダ３０２Ｂを含むこともできる。ポピュレーション・カウンター３０２Ｃは、非マスク一致ラインによって示されるように、Ｎバイト・パターンとサーチ・アレイのデータの間で生じる一致数を示す。他の索引セレクタを使用してもよい。

索引解決ファンクション・ユニット３０２の出力は、オペコード１０２ａを受け取るために同様に連結された索引結合及び選択ユニット３０３に入力される。オペコード１０２ａは、サーチ命令内で指定され、索引解決ファンクション出力の１つをソータの出力として選択する。索引結合及び選択ユニット３０３は、索引３２２と共に一致があることを示す一致インジケータ３２１を生成する。これは、出力昇順優先順位エンコーダ３０２Ａが選択された場合は最初の一致の発生であり、降順優先順位インジケータ３０２Ｂの出力が選択された場合は最後の一致の発生である、データのサーチ・アレイ内の場所を示し、ポップ・カウンター３０２Ｃが選択された場合は非マスク一致ライン３０２Ｂの一致数を示すなどする。これらの出力の演算、すなわち一致インジケータ３２１と索引３２２に引き続き、一致インジケータ３２１又は他の類似の技術に応じて、命令メモリ（例えば、命令メモリ１０４）の指定アドレスに分岐して、汎用レジスタ内の出力をソーティングし、後続命令の間接指定を利用することにより、これらを後続の１つ又は複数のサーチ命令の実行を制御するために利用することができる。

図５は、サーチ装置を含む規則プロセッサのマイクロ・アーキテクチャを示す。図５を参照すると、サーチ命令が命令メモリ５０１に記憶されている。命令は、命令フェッチ・ポインタ・レジスタ６０２を使用してフロー制御により選択される。命令はデコーダ５０３によって復号される。各命令の個々の部分集合は、当該命令から取られるか、又は汎用レジスタ・ファイル５０４からフェッチされる。次いで、各命令の様々な部分集合が、別々のユニット、すなわち上記のように、サーチ・アレイ５０５、ソート・ユニット５０６ａとそれに続く特徴付けユニット５０６ｂとからなるソータ５０６、従来型演算論理回路（ＡＬＵ）５０７に供給される。一実施形態では、各命令の処理は、上記のように、（ｉ）命令フェッチ・ステージ５０８、（ii）命令アセンブリ・ステージ５０９、（iii）サーチ／実行ステージ５１０、及び（iv）結果のソート及び配信及び／又は分岐ステージ５１１からなる４ステージのパイプラインの後に続く。

一実施形態では、規則エンジン命令フォーマットは、１２８ビットの規則フォーマットを含む。１２８ビットの規則は、規則プロセッサに対して様々なハードウェア・エンジンに指令を発行する様々なフィールドを含んだ部分集合に分割される。一実施形態では、サーチ部分集合は、サーチ／ソート・オペコード・フィールド（５ビット）、パターン・フィールド（一実施形態では、これは、８バイト値又は８バイト値を提供する場所へのポインタを、当該命令内の８バイトがポインタであるか否かを指定する追加ビットと共に含んだ、６５ビットである）、バイト・レベル・マスク・フィールド（一実施形態では、８ビット）、開始場所アドレス・フィールド（一実施形態では、このフィールドは、１１ビット値又は１１ビット値を提供するレジスタへのポインタを含んでおり、また開始場所アドレスがその１１ビット値又はそのようなポインタを含んでいるか否かを示すための追加ビットを含めて、１２ビットである）、終了場所アドレス・フィールド（一実施形態では、このフィールドは、１１ビット値又は１１ビット値を提供するレジスタへのポインタを、終了場所アドレス情報がポインタであるか否かを指定するための追加ビットと共に含んだ１２ビットである）、サーチ・オペレーションの結果が戻されるべき場所を指定する結果レジスタ・フィールド（一実施形態では、このフィールドは６ビットである）、さらに分岐アドレス・フィールド（一実施形態では、このフィールドは、１９ビット値又は１９ビット値を提供するレジスタへのポインタを、分岐アドレス情報がポインタであるか否かを指定するための追加ビットと共に含んだ、２０ビットである）を含む。

図６は、上記規則プロセッサの一実施形態が処理することのできる、一組の規則の擬似コード６０１の一例を示す。この規則は、複数のパターンを有するが、これらは、このようなパターンがメッセージ又はドキュメント又はパケット内に存在することのできる場所についていくつかの特定の制約を伴う。この制約は、ＢＥＦＯＲＥ及びＡＮＤのようなキーワードの使用により擬似コードで表現される。簡約化のために、この例では、ストリング間に追加デリミタを入れずに６０１のパターンが使用されるが、これは実際にもこの通りであってよい。また図６は、例示規則プロセッサに対応するマイクロコードの一覧６０２である。命令のフォーマットは上記の通りである。説明のために第１の命令６０３を使用するが、これは、サーチ・レジスタに保持されるサーチ可能ペイロードの開始と終了を示すために（Ｉｎｄｉｒｅｃｔｉｏｎ Ｆｌａｇｓを使用することにより）定数値として表現される開始及び終了オフセットと共に、（０ｘＦＦをＭａｓｋとして使用することにより）８バイトのＰａｔｔｅｒｎ“ｃｐ／ｂｉｎ”が当該サーチに該当するＦＩＮＧ＿ＦＩＲＳＴ＿ＦＯＲＷＡＲＤオペコードからなる。簡略化のために、本明細書では定数の誘導は省略した。このオペコードの結果は汎用レジスタＡにロードされるべきものとして示し、最後に分岐アドレスが、図６に示す切断されたマイクロコードに続く命令である、定数値１１として指定される。この命令は、サーチ実行ハードウェアに、サーチ・レジスタ２０２ａのバイト場所０ｘ０３Ｄ及び０ｘ８００内の“ｃｐ／ｂｉｎ／”の発生をサーチさせる。サーチ・アレイ２０２ｃ内の一致するすべての行は、マイクロ・アーキテクチャのパイプラインのサーチ実行ステージ５１０の終了により、それぞれの一致ライン３１０をアサートする。ソート及び分岐ステージ５１１では、ソータ２０２ｂは、図３Ｂに示すように、０ｘ０３Ｄ及び０ｘ８００をビット・ベクトルに変換する。０ｘ０３Ｄから０ｘ８００までの場所枠外で開始するいかなる一致をも無効にするように、範囲マスク及び選択関数３０１を実行するために、ビット・ベクトルが使用される。現在は場所枠内にある残りの一致の中で、この命令のオペコードは、最低数の一致を１１ビットのバイナリ符号化された場所に変換するために、索引解決ファンクション３０２から昇順優先順位エンコーダ３０２ａを選択する。このような一致が見つかると、一致３２１がアサートされ、索引３２２が１１ビットの場所を保持する。一致が見つからないために一致３２１がアサートされない場合、命令シーケンサ１０５は、命令ポインタ１０６に分岐アドレス０ｘＢをロードする。索引３２２は、レジスタ・ファイル５０４の制御回路により、汎用レジスタＡにロードされる。汎用レジスタＡへのロードと、命令ポインタのロードは、適切ならば、ソート及び分岐実行ステージ５１１の終了により完了する。第２の命令６０４、ＦＩＮＤ＿ＦＯＲＷＡＲＤ＿ＡＮＣＨＯＲＥＤは、規則エンジン例の豊富な語彙をさらに示す。これは、成功すべきサーチのためのｓｔａｒｔ＿ｏｆｆｓｅｔから照合を始める必要があるという点で、ＦＩＮＤ＿ＦＩＲＳＴ＿ＦＯＲＷＡＲＤの異型である。

図７は、図５に示す規則プロセッサ例のマイクロ・アーキテクチャ内での、図６に示すマイクロコードの実行を示す。表７０１は、複数のクロック周期を通した実行を示す。簡約化のために、すべてのサーチ命令が、サーチ・レジスタ内で指定パターンを見つけることに成功するものと仮定する。実行は、図５に示す４ステージを通してパイプライン形式で進行する。間接指定の使用により、サーチ命令の実行は、直前の命令で計算されたオフセットを使用することができる。したがって、命令１から８は、連続する周期で実行される。命令８は、それぞれにクロック周期８とクロック周期９で計算された汎用レジスタＡと汎用レジスタＢのコンテンツの比較の結果に応じた、分岐である。この分岐は、クロック周期１１と、クロック周期１４で完了した命令実行とで取られる。したがって、擬似コード６０１を使用して記述された複合パターン照合式は、規則プロセッサ例の豊富な命令語彙を使用して１４クロック周期でのみ実行される。この例は、ドキュメント、メッセージ又はパケットの動的及び文脈サーチ及び解析を含むファンクションの実行に対する規則プロセッサ例の能力と効率を説明する。

上記の説明を読めば、当業者には本発明の多くの変形形態及び修正形態が確実に明らかになるだろうが、説明により図示し説明したいかなる特定の実施形態でも、限定を考慮することを意図するものでないことを理解されたい。したがって、様々な実施形態の詳細の参照は、本発明の本質とみなされる特徴のみをそこに記載した特許請求の範囲を限定することを意図するものではない。

サーチ装置を有する規則プロセッサの一実施形態のブロック図である。 サーチ・レジスタ及びサーチ実行ハードウェアの一実施形態のブロック図である。 サーチ・アレイの一実施形態のブロック図である。 ソータの一実施形態のブロック図である。 ソータ内の範囲選択機構の一実施形態のブロック図である。 サーチ・アレイの一実施形態の回路図である。 ４つの処理ステージを含む規則プロセッサのマイクロ・アーキテクチャ例を示す図である。 規則プロセッサ例に対する、複合パターン照合一組の規則の擬似コード例及び対応するマイクロコードを示す図である。 図６に示すマイクロコードの、クロックごとにパイプライン化された実行を示す図である。

Claims (18)

1. 文脈サーチを実行するための規則プロセッサであって、
   コンテンツを示す複数の入力ペイロードを格納する複数のサーチ・レジスタと、
   前記複数のサーチ・レジスタに連結され、指定された１つ又は複数のパターンを、前記サーチ・レジスタのコンテンツを検索するための検索パターンとして提供して前記コンテンツのパターンと照合させ、双方のパターンが一致する場合は一致ラインに一致信号を出力するサーチ命令の実行により前記サーチ・レジスタの前記コンテンツに対して１つ又は複数の文脈サーチを実行するサーチ実行エンジンと
   を含み、
   前記サーチ実行エンジンが、
   前記複数のサーチ・レジスタに連結されており、前記複数のサーチ・レジスタのコンテンツが複製され、サーチ対象として記憶されるサーチ・アレイと、
   前記サーチ・アレイに連結されたソータと
   を含み、
   前記サーチ・レジスタはＭ行×１バイトのデータを保持し、前記サーチ・アレイはＭ行×所定バイト数のデータの保持が可能であって前記データのサーチ結果の出力が可能なＭ個の前記一致ラインを有し、
   前記ソータは、前記サーチ・レジスタのサーチ範囲の開始点と終了点により指定された開始終了範囲、および前記サーチ・アレイからの前記一致ラインの信号に基づいて前記サーチ・アレイのサーチ結果を処理することを特徴とする規則プロセッサ。
2. 各サーチ命令が、前記複数のサーチ・レジスタと前記サーチ実行エンジンとに提供された請求項１に記載の規則プロセッサ。
3. 前記１つ又は複数のサーチ命令の少なくとも１つが、前記複数のサーチ・レジスタ内の前記コンテンツに対してサーチされるべきパターンと、前記コンテンツに対してマスクされるべきパターンを示す０又はそれ以上のサーチ命令のためのパラメータとを指定する請求項１に記載の規則プロセッサ。
4. １つのパラメータが、前記パターンの部分集合を前記サーチ・レジスタ内の前記コンテンツに対してサーチできるようにするために、マスクされるべき前記パターンの部分を指定する請求項３に記載の規則プロセッサ。
5. 前記マスクされるべきパターンの前記部分が、前記パターン内の特定バイトをマスク・オフするようにマスク・ベクトルによって指定される請求項４に記載の規則プロセッサ。
6. 前記サーチ実行エンジンが、前記サーチ・レジスタ内の前記コンテンツのサーチに成功したことを示す少なくとも１つの結果出力を生成する請求項１に記載の規則プロセッサ。
7. 前記少なくとも１つの結果出力が、前記命令の少なくとも１つで指定されたパターンと、前記複数のサーチ・レジスタ内の前記コンテンツとの間で一致が生じた、前記複数のサーチ・レジスタ内の場所の指示を含む請求項６に記載の規則プロセッサ。
8. 少なくとも１つのサーチ命令が、前記サーチを制御するために使用するパラメータを示す前記サーチの開始終了範囲又は前記サーチを制御するために前記パラメータを記憶するメモリ内へのポインタを指定する、フィールドを含む請求項１に記載の規則プロセッサ。
9. 前記サーチ・レジスタ内のデータに適用されるべき１つ又は複数のサーチ命令を記憶するためのメモリをさらに含む請求項１に記載の規則プロセッサ。
10. 前記サーチ命令が、前記サーチ・レジスタ内の前記コンテンツで任意のパターンに対するサーチを前記サーチ実行エンジンに実行させる請求項１に記載の規則プロセッサ。
11. １つ又は複数のサーチ命令を前記サーチ実行エンジンに実行させるための命令シーケンサをさらに含む請求項１に記載の規則プロセッサ。
12. 前記Ｍ個の一致ラインのそれぞれが、前記サーチ・アレイに記憶された一群のデータに関連付けられており、前記１つ又は複数のサーチ命令の１つによって指定された前記検索パターンが、前記サーチ・アレイに記憶された、それに関連付けられた一群のデータと一致するか否かを示す請求項１に記載の規則プロセッサ。
13. 前記ソータは、前記一致ラインの１つ又は複数が一致するか否かを示す第１の出力と、前記サーチ実行エンジンが、１つ又は複数のサーチ命令によって指定された前記検索パターンに呼応して、前記１つ又は複数の文脈サーチを実行した結果を示す第２の出力とを有する請求項１に記載の規則プロセッサ。
14. 前記ソータが、
    前記パターンと、前記サーチ・アレイの最上位側と末尾側のうち一方の側に関して前記サーチ・アレイに記憶されたデータとの間の一致の第１の発生に対応した前記Ｍ個の一致ラインに対応する、前記サーチ・アレイ内の場所を示すための、優先順位エンコーダをさらに含む請求項１に記載の規則プロセッサ。
15. 前記ソータが、
    前記パターンと、前記サーチ・アレイの最上位側に関して前記サーチ・アレイに記憶されたデータとの間の一致の第１の発生に対応した前記Ｍ個の一致ラインに対応する、前記サーチ・アレイ内の場所を示すための昇順優先順位エンコーダと、
    前記サーチ・アレイの末尾側に関して前記サーチ・アレイに記憶されたデータと前記パターンとの間の一致の第１の発生に対応した前記Ｍ個の一致ラインに対応する、前記サーチ・アレイ内の場所を示すための降順優先順位エンコーダと、
    前記Ｍ個の一致ラインの範囲における一致数を特定するためのカウンタと、
    前記昇順優先順位エンコーダ、前記降順優先順位エンコーダ、前記カウンタに連結されており、第１の出力を有し、前記昇順優先順位エンコーダ、前記降順優先順位エンコーダ、前記カウンタのいずれか１つの出力を前記ソータの前記第１の出力として選択するよう動作可能なセレクタと
    をさらに含む請求項１に記載の規則プロセッサ。
16. 一組のサーチ・レジスタにコンテンツをロードするステップと、
    前記サーチ・レジスタでサーチされるべきサーチ命令によって示されたパターンを提示するステップと、
    前記パターンと前記サーチ・レジスタに記憶された前記コンテンツとの間でパターン照合を実行するステップと、
    前記パターン照合を実行し、双方のパターンが一致する場合は一致ラインに一致信号を出力するステップと
    を含み、
    コードを一連のサーチ命令に変換するステップと、
    パターン照合が前記複数のサーチ命令のそれぞれに対して実行されるように、前記一連のサーチ命令を連続した周期で実行するステップと
    をさらに含み、
    前記サーチ・レジスタはＭ行×１バイトのデータを保持し、複数の前記サーチ・レジスタのコンテンツが複製され、サーチ対象として記憶されるサーチ・アレイはＭ行×所定バイト数のデータの保持が可能であって前記データのサーチ結果の出力が可能なＭ個の前記一致ラインを有し、
    前記サーチ・レジスタのサーチ範囲の開始点と終了点により指定された開始終了範囲、および前記サーチ・アレイからの前記一致ラインの信号に基づいて前記サーチ・アレイのサーチ結果を処理するステップを含むことを特徴とする処理。
17. 前記サーチ・アレイの数行に関連付けられた複数の一致ラインを生成するステップであって、前記複数の一致ラインの一致ラインが、前記パターンと前記一致ラインに関連付けられた１行との間で一致が生じたか否かを示すステップと、
    前記サーチ命令が指定する情報に応じて、少なくとも一組の前記一致ラインに対して前記１つ又は複数のオペレーションを実行するステップと、
    前記一致ラインの１つ又は複数が、前記パターンと前記１つ又は複数のオペレーションを実行した結果と一致するか否かに関する指示を出力するステップと
    をさらに含む請求項１６に記載の処理。
18. １行に対するデータが、シフトされた形式で隣接行に記憶されるように、データを記憶し、複製し、インタリーブするために、前記サーチ・レジスタをローディングするステップが実行される請求項１６に記載の処理。

Images