(57)【要約】到着するパケットデータで決定性有限オートマトン（ＤＦＡ）グラフをリアルタイムで走査するプロセッサ１１０を提供する。プロセッサは、少なくとも１つのプロセッサコア１２０と、この少なくとも１つのプロセッサコア１２０と非同期に動作するＤＦＡモジュール１３４とを有し、キャッシュコヒーレントメモリ１３０，１０８に格納されたパケットデータでノンキャッシュメモリ１１８に格納された少なくとも１つのＤＦＡグラフを走査する。【選択図】図１Ｂ
2008512797.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサコアと、
前記少なくとも１つのプロセッサコアと非同期に動作する決定性有限オートマトン（ＤＦＡ）モジュールであって、前記少なくとも１つのプロセッサコアからの命令に応答して、ノンキャッシュメモリに格納された少なくとも１つのＤＦＡグラフの複数のノードを、キャッシュコヒーレントメモリに格納されたパケットデータを用いて走査するＤＦＡモジュールとを備えたネットワークプロセッサ。
【請求項２】
請求項１において、前記ＤＦＡモジュールが、
前記ＤＦＡグラフを格納するメモリにアクセスするように適合されたノンキャッシュメモリコントローラと、
前記ノンキャッシュメモリのコントローラと通信する少なくとも１つのＤＦＡスレッドエンジンと、
前記少なくとも１つのプロセッサコアからの命令を、前記少なくとも１つのＤＦＡスレッドエンジンにスケジューリングするように適合された命令入力論理とを有するネットワークプロセッサ。
【請求項３】
請求項２において、さらに、命令待ち行列を備え、前記少なくとも１つのプロセッサコアが前記ＤＦＡモジュールへのＤＦＡ命令をこの命令待ち行列に送出するネットワークプロセッサ。
【請求項４】
請求項３において、前記ＤＦＡモジュールが前記命令待ち行列を指すポインタを保持するネットワークプロセッサ。
【請求項５】
請求項３において、前記ＤＦＡ命令が、キャッシュコヒーレントメモリに格納されたパケットデータを使用のために指示し、ノンキャッシュメモリに格納された少なくとも１つのＤＦＡグラフを走査のために指示するネットワークプロセッサ。
【請求項６】
請求項３において、前記ＤＦＡモジュールが、前記少なくとも１つのＤＦＡスレッドエンジンに、ＤＦＡ命令をスケジューリングするネットワークプロセッサ。
【請求項７】
請求項６において、前記少なくとも１つのＤＦＡスレッドエンジンが、
前記キャッシュコヒーレントメモリに格納されているパケットデータをフェッチし、
前記キャッシュコヒーレントメモリから受信されたパケットデータのバイト毎にノンキャッシュメモリロード命令を発行して、前記ノンキャッシュメモリに格納されたＤＦＡグラフの次の状態を走査し、
前記キャッシュコヒーレントメモリに中間および最終結果を書き込むネットワークプロセッサ。
【請求項８】
請求項７において、さらに、結果ワードを備え、この結果ワードに前記中間および最終結果が書き込まれるネットワークプロセッサ。
【請求項９】
請求項８において、前記結果ワードが命令完了フィールドを含み、このフィールドが設定されている場合にＤＦＡ命令の完了をこのフィールドが表示するネットワークプロセッサ。
【請求項１０】
請求項１において、前記ＤＦＡモジュールが、
共通の環境設定で前記少なくとも１つのプロセッサコアと関連づけられている複数のＤＦＡスレッドエンジンを有し、各ＤＦＡスレッドエンジンは、前記ノンキャッシュメモリに格納されている少なくとも１つのＤＦＡグラフを走査するように適合されているネットワークプロセッサ。
【請求項１１】
請求項１において、さらに、前記ＤＦＡグラフのノードタイプを特定するノードタイプ識別子を備えたネットワークプロセッサ。
【請求項１２】
請求項１１において、前記ノードタイプ識別子はマーク付けされたノードであり、前記マーク付けされたノードの走査はグラフの走査を妨害しないネットワークプロセッサ。
【請求項１３】
入力パケットデータを用いてＤＦＡグラフを走査する方法であって、
少なくとも１つのＤＦＡグラフをノンキャッシュコヒーレントメモリに格納する工程と、
ＤＦＡ命令をキャッシュコヒーレントメモリに格納する工程であって、このＤＦＡ命令は、前記キャッシュコヒーレントメモリに格納されたパケットデータを使用のために指示し、前記ノンキャッシュメモリに格納された少なくとも１つのＤＦＡグラフを走査のために指示する工程と、
前記ＤＦＡグラフを前記格納されたパケットデータを用いて走査し、前記キャッシュコヒーレントメモリに中間および最終結果を書き込む工程とを備えたＤＦＡグラフ走査方法。
【請求項１４】
請求項１３において、少なくとも１つのプロセッサコアがＤＦＡモジュールにＤＦＡ命令を送出するＤＦＡグラフ走査方法。
【請求項１５】
請求項１４において、ＤＦＡモジュールが、前記少なくとも１つのＤＦＡスレッドエンジンに、ＤＦＡ命令をスケジューリングするＤＦＡグラフ走査方法。
【請求項１６】
請求項１５において、前記少なくとも１つのＤＦＡスレッドエンジンが、
前記キャッシュコヒーレントメモリに格納されているパケットデータをフェッチし、
前記キャッシュコヒーレントメモリからフェッチされたパケットデータのバイト毎に１つのノンキャッシュメモリロード命令を発行し、
前記フェッチされたパケットデータのバイトに応じて、前記ノンキャッシュメモリに格納されたＤＦＡグラフの次の状態を走査し、
前記キャッシュコヒーレントメモリに中間および最終結果を書き込むＤＦＡグラフ走査方法。
【請求項１７】
請求項１６において、さらに、前記ＤＦＡグラフの各ノードに対する個々のノードタイプを特定するノードタイプ識別子を提供する工程を備え、前記中間および最終結果は前記ノードタイプ識別子から判断されるＤＦＡグラフ走査方法。
【請求項１８】
ノンキャッシュコヒーレントメモリに少なくとも１つのＤＦＡグラフを格納する手段と、
キャッシュコヒーレントメモリにＤＦＡ命令を格納する手段であって、前記ＤＦＡ命令が、前記キャッシュコヒーレントメモリに格納されたパケットデータを使用のために指示し、前記ノンキャッシュメモリに格納された少なくとも１つのＤＦＡグラフを走査のために指示する手段と、
前記ＤＦＡグラフを前記格納されたパケットデータを用いて走査し、前記キャッシュコヒーレントメモリに中間および最終結果を書き込む手段を備えたネットワークプロセッサ。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、2004年9月10日に出願された米国仮特許出願第60/609,211号、および2005年4月8日に出願された米国仮特許出願第60/669,672号の利益を主張するものであり、上記各出願の全内容は参照により本明細書に引用したものとする。
【背景技術】
【０００２】
開放型システム間相互接続（ＯＳＩ）参照モデルは、伝送媒体を介する通信に使用される７つのネットワークプロトコル層（Ｌ１−Ｌ７）を規定している。上位層（Ｌ４−Ｌ７）はエンド・ツー・エンド通信を表し、下位層（Ｌ１−Ｌ３）は局所的な通信を表す。
【０００３】
ネットワーキングアプリケーションアウェア型（アプリケーションが自動的にネットワークを制御する）システムは、Ｌ３からＬ７までの範囲のネットワークプロトコル層、例えば、ハイパーテキスト転送プロトコル（ＨＴＴＰ）およびシンプルメール転送プロトコル（ＳＭＴＰ）などのＬ７ネットワークプロトコル層、および伝送制御プロトコル（ＴＣＰ）などのＬ４ネットワークプロトコル層を処理し、フィルタリングし、かつ切り換える必要がある。ネットワークプロトコル層の処理に加えて、ネットワーキングアプリケーションアウェア型システムは、ファイアウォール、仮想プライベートネットワーク（ＶＰＮ）、セキュアソケットレイヤ（ＳＳＬ）、侵入検知システム（ＩＤＳ）、インターネットプロトコルセキュリティ（ＩＰＳｅｃ）、アンチウィルス（ＡＶ）およびアンチスパム機能を含む、Ｌ４からＬ７までのネットワークプロトコル層を介するアクセスベースおよびコンテンツベースのセキュリティによって、これらのプロトコルの安全性を同時にワイヤスピードで保護する必要もある。
【０００４】
ネットワークプロセッサが、高スループットのＬ２およびＬ３ネットワークプロトコル処理に利用される。このＬ２およびＬ３ネットワークプロトコル処理は、パケットをワイヤスピードで転送するパケット処理の実行である。一般に、より高度の処理を必要とするＬ４からＬ７までのネットワークプロトコルの処理には、汎用プロセッサが使用される。例えば、Ｌ４ネットワークプロトコルである伝送制御プロトコル（ＴＣＰ）は、パケット内の全ペイロードにわたるチェックサムの計算、ＴＣＰセグメントバッファの管理および複数のタイマの接続毎の常時保持を含む複数の計算集約型タスクを必要とする。汎用プロセッサは、計算集約型タスクを実行できるが、データを処理してワイヤスピードで転送できるだけの十分な性能は備えていない。
【０００５】
さらに、パケットのコンテンツを調べるコンテンツアウェア型アプリケーション（コンテンツを自動的に認識するアプリケーション）は、データストリーム内の固定文字列および可変回数で反復される文字クラスの双方を含む表現を探索する必要がある。ソフトウェアでこのタスクを実行するために、複数の探索アルゴリズムが使用される。このようなアルゴリズムの１つが、決定性有限オートマトン（ＤＦＡ）である。ただし、ＤＦＡ探索アルゴリズムを使用する場合、反復パターンによるグラフサイズの指数関数的拡大およびデータストリーム内の偽一致などの制限が生じる。
【０００６】
これらの制限があるため、コンテンツ処理アプリケーションは、パターン探索によって生じる結果に対してかなりの量の後処理を必要とする。後処理は、接続種別などの他の接続状態情報およびパケットに包含されるプロトコルヘッダ内の特定の値によって、一致パターンを識別する必要がある。またこれは、特定の他のタイプの計算集約型識別を必要とし、例えば、パターン一致が有効であるのは、それがデータストリーム内の特定の位置範囲内にあるか、あるいは、別のパターンが後に続いてかつ先行するパターンから特定の範囲内にあるか、または、先行するパターンから特定のオフセット位置もしくはそのオフセット位置の後にある場合のみである。例えば、正規表現一致は、種々の演算子と単一文字を組み合わせて、複合な表現の構成を可能にする。
【発明の開示】
【０００７】
本発明は、プロセッサがコンテンツ処理アプリケーションを処理できる速度を向上させることを目的とする。本プロセッサは、少なくとも１つのプロセッサコアと、この少なくとも１つのプロセッサコアと非同期に動作する決定性有限オートマトン（ＤＦＡ）モジュールであって、第１メモリに格納された少なくとも１つのＤＦＡグラフを、第２メモリに格納されたパケットデータを用いて走査するＤＦＡモジュールとを有する。
【０００８】
ＤＦＡモジュールは、第１メモリコントローラと、少なくとも１つのＤＦＡスレッドエンジンと、命令入力論理とを有することができる。プロセッサコアは、命令入力論理の命令待ち行列を介してＤＦＡモジュールにＤＦＡ命令を送出できる。ＤＦＡ命令は、第２メモリに格納されたパケットデータを使用のために指示でき、第１メモリに格納されたＤＦＡグラフを走査のために指示できる。ＤＦＡモジュールは、ＤＦＡスレッドエンジンにＤＦＡ命令をスケジューリングすることができる。ＤＦＡスレッドエンジンは、第２メモリに格納されているパケットデータをフェッチし、フェッチされたパケットデータに応じたメモリアクセス命令を発行できる。
【０００９】
例えば、第１メモリはノンキャッシュメモリであってもよく、第２メモリはキャッシュコヒーレントメモリであってもよい。ＤＦＡスレッドエンジンは、キャッシュコヒーレントメモリに格納されているパケットデータを一度に１バイトずつ逐次フェッチする。次に、ＤＦＡスレッドエンジンは、キャッシュコヒーレントメモリから受け取るパケットデータのバイト毎にノンキャッシュメモリロード命令を発行して、ノンキャッシュメモリに格納されているＤＦＡグラフの次の状態を走査する。ＤＦＡスレッドエンジンはまた、キャッシュコヒーレントメモリに中間および最終結果を書き込む。
【００１０】
本発明の上述および他の目的、特徴および利点は、添付図面に示す本発明の好ましい実施形態に関する以下のより詳細な説明から明らかとなるであろう。添付図面では、同一参照符号は異なる図面においても同一部分を指す。図面は、必ずしも縮尺通りではなく、本発明の原理を示すことに重点を置いている。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の好ましい実施形態について説明する。
【００１２】
図１Ａは、本発明の原理によるネットワークサービスプロセッサ１１０を含むセキュリティアシステム１００を示すブロック図である。セキュリティシステム１００は、１つのイーサネット（登録商標）ポート（Ｇｉｇ Ｅ）で受信したパケットを別のイーサネット（登録商標）ポート（Ｇｉｇ Ｅ）に切り換えて、受信したパケットに複数のセキュリティ機能を実行した後にそのパケットを転送する、スタンドアロン型システムである。例えば、セキュリティシステム１００を用いて、広域ネットワーク上で受信するパケットに対してセキュリティ処理を実行した後に、そのパケットをローカルエリアネットワークに転送することができる。
【００１３】
ネットワークサービスプロセッサ１１０は、ハードウェアパケット処理、バッファリング、ワークスケジューリング、順序づけ、同期化、およびキャッシュコヒーレンスサポートを提供することにより、全てのパケット処理タスクの速度を高める。ネットワークサービスプロセッサ１１０は、受信されたパケットにカプセル化されている開放型システム間相互接続ネットワークのＬ２からＬ７層までのプロトコルを処理する。
【００１４】
ネットワークサービスプロセッサ１１０は、イーサネット（登録商標）ポート（Ｇｉｇ Ｅ）から物理インタフェースＰＨＹ１０４ａ、１０４ｂを介してパケットを受信し、受信されたパケットに対してＬ７〜Ｌ２ネットワークプロトコル処理を実行し、処理されたパケットを物理インタフェース１０４ａ、１０４ｂから、またはＰＣＩバス１０６を介して転送する。ネットワークプロトコル処理には、ファイアウォール、アプリケーションファイアウォール、ＩＰセキュリティ（ＩＰＳＥＣ）および／またはセキュアソケットレイヤ（ＳＳＬ）を含む仮想プライベートネットワーク（ＶＰＮ）、侵入検知システム（ＩＤＳ）およびアンチウィルス（ＡＶ）などのネットワークセキュリティプロトコルの処理が含まれてもよい。
【００１５】
ネットワークサービスプロセッサ１１０内のダイナミックランダムアクセスメモリ（ＤＲＡＭ）コントローラ１３３（図１Ｂ）は、ネットワークサービスプロセッサ１１０に結合される外部ＤＲＡＭ１０８へのアクセスを制御する。ＤＲＡＭ１０８は、ＰＨＹインタフェース１０４ａ、１０４ｂまたはＰＣＩ拡張（ＰＣＩ−Ｘ）インタフェース１０６から受信されるデータパケットを、ネットワークサービスプロセッサ１１０によって処理するために格納する。
【００１６】
ネットワークサービスプロセッサ１１０内の低遅延メモリコントローラ３６０（図３Ｂ）は、低遅延メモリ（ＬＬＭ）１１８を制御する。ＬＬＭ１１８は、侵入検知システム（ＩＤＳ）またはアンチウィルス（ＡＶ）アプリケーションに必要とされる正規表現一致を含む、高速検索を可能にするインターネットサービス／セキュリティアプリケーションに使用されることができる。
【００１７】
正規表現は、文字列一致パターンを表現する一般的な方法である。正規表現の極小要素は、一致されるべき単一文字である。これらは、ユーザが連結、選択、クリーネ・スターなどを表現できるようにするメタ文字演算子と組み合わせることもできる。連結は、単一文字（またはサブ文字列）から複数の文字一致パターンを生成するために使用され、選択（|）は、２つ以上のサブ文字列のいずれにも一致できるパターンを生成するために使用される。クリーネ・スター（*）を使用することによって、パターンが文字列内でそのパターンのゼロ（０）またはそれ以上の出現に一致することが可能になる。それぞれの演算子と単一文字との組合せにより、複雑な表現の構築が可能になる。例えば、表現（th(is|at)*）は、th、this、that、thisis、thisat、thatis、thatat、などに一致する。
【００１８】
図１Ｂは、図１Ａに示すネットワークサービスプロセッサ１１０のブロック図である。ネットワークサービスプロセッサ１１０は、図１Ａに関連して説明したとおり、少なくとも１つのプロセッサコア１２０を使用して高いアプリケーション性能を提供する。
【００１９】
パケットは、ＳＰＩ−４．２またはＲＧＭIIインタフェースを介して、ＧＭＸ／ＳＰＸユニット１２２ａ、１２２ｂの任意の１つによって処理されるために受信される。パケットは、ＰＣＩインタフェース１２４によって受信されることもできる。ＧＭＸ／ＳＰＸユニット（１２２ａ、１２２ｂ）は、受信されたパケットに含まれるＬ２ネットワークプロトコルヘッダ内の様々なフィールドをチェックすることによって受信されたパケットの前処理を実行し、次にパケットをパケット入力ユニット１２６に転送する。
【００２０】
パケット入力ユニット１２６は、受信されたパケットに含まれるネットワークプロトコルヘッダ（Ｌ３およびＬ４）のさらなる前処理を実行する。前処理には、通信制御プロトコル（ＴＣＰ）／ユーザデータグラムプロトコル（ＵＤＰ）（Ｌ３ネットワークプロトコル）に関するチェックサムのチェックが含まれる。
【００２１】
フリープールのアロケータ（ＦＰＡ）１２８が、レベル２キャッシュメモリ１３０およびＤＲＡＭ１０８における空きメモリのポインタプールを保持する。パケット入力ユニット１２６は、ポインタのプールの１つを使用して、受信されたパケットデータをレベル２キャッシュメモリ１３０に格納し、ポインタの別のプールを使用してプロセッサコア１２０に対してワーク待ち行列エントリを割り当てる。
【００２２】
パケット入力ユニット１２６は次に、レベル２キャッシュ１３０またはＤＲＡＭ１０８内のバッファにパケットデータを書き込む。この書込みのフォーマットは、上位層のネットワークプロトコルによるその後の処理を容易にするために、プロセッサコア１２０のうちの少なくとも１つで実行される上位層ソフトウェアに好都合なフォーマットである。
【００２３】
Ｉ／Ｏインタフェース１３６は、全体のプロトコルおよびアービトレーション（調停）を管理し、コヒーレントなＩ／Ｏ区分（partitioning）を提供する。Ｉ／Ｏインタフェース１３６は、Ｉ／Ｏブリッジ（ＩＯＢ）１３８およびフェッチ・アンド・アッドユニット（ＦＡＵ）１４０を有する。フェッチ・アンド・アッドユニット１４０内のレジスタを用いて、パケット出力ユニット１４６を介して処理されたパケットを転送するのに使用される出力待ち行列の長さを保持する。Ｉ／Ｏブリッジ１３８は、コヒーレントメモリバス１４４、Ｉ／Ｏバス１４２、パケット入力ユニット１２６、およびパケット出力ユニット１４６間で転送される情報を格納するためのバッファ待ち行列を含む。
【００２４】
パケット順序／ワークモジュール（ＰＯＷ）１４８は、プロセッサコア１２０に対するワークをキューイングして（待ち行列に入れて）スケジューリングする。ワーク待ち行列エントリを待ち行列に追加することによって、ワークがキューイングされる（待ち行列に入れられる）。例えば、ワーク待ち行列エントリは、パケットの到着毎にパケット入力ユニット１２６によって追加される。プロセッサコア１２０のワークのスケジューリングには、タイマユニット１５０が使用される。
【００２５】
プロセッサコア１２０は、ＰＯＷモジュール１４８にワークを要求する。ＰＯＷモジュール１４８は、プロセッサコア１２０のうちの１つに対してワークを選択（すなわち、スケジューリング）し、そのワークを記述するワーク待ち行列エントリを指すポインタをプロセッサコア１２０に返す。
【００２６】
プロセッサコア１２０は、命令キャッシュ１５２、レベル１（Ｌ１）データキャッシュ１５４、および暗号アクセラレータ１５６を有する。一実施形態においては、ネットワークサービスプロセッサ１１０は、１６個のスーパースカラーＲＩＳＣ（縮小命令セットコンピュータ）型プロセッサコア１２０を有する。一実施形態においては、各スーパースケーラＲＩＳＣ型プロセッサコア１２０はＭＩＰＳ６４バージョン２プロセッサコアの拡張版である。
【００２７】
レベル２（Ｌ２）キャッシュメモリ１３０およびＤＲＡＭ１０８は、プロセッサコア１２０およびＩ／Ｏコプロセッサデバイスの全てによって共有される。各プロセッサコア１２０は、コヒーレントメモリバス１４４によってレベル２キャッシュメモリ１３０に結合される。コヒーレントメモリバス１４４は、プロセッサコア１２０、ＩＯＢ１３８ならびにＬ２キャッシュメモリ１３０およびＬ２キャッシュメモリコントローラ１３１間の全てのメモリおよびＩ／Ｏトランザクションのための通信チャネルである。一実施形態においては、コヒーレントメモリバス１４４は１６個のプロセッサコア１２０に対して適応でき、ライトスルーによって完全にコヒーレントなＬ１データキャッシュ１５４をサポートし、高度なバッファ機能を果たして、Ｉ／Ｏを優先順位付けすることができる。
【００２８】
Ｌ２キャッシュメモリコントローラ１３１は、メモリ参照コヒーレンスを保持する。Ｌ２キャッシュメモリコントローラ１３１は、ブロックがレベル２キャッシュメモリ１３０もしくは外部ＤＲＡＭ１０８に格納されていても、または「処理中（in-flight）」であっても、あらゆるＦＩＬＬ（フィル）要求に対して、ブロックの最新コピーを返す。Ｌ２キャッシュメモリコントローラ１３１はまた、各プロセッサコア１２０内にデータキャッシュ１５４に対するタグを２部格納する。Ｌ２キャッシュメモリコントローラ１３１は、キャッシュブロック格納の要求のアドレスをデータ−キャッシュタグと比較し、格納命令が別のプロセッサコアからであるか、またはＩ／Ｏインタフェース１３６を介するＩ／Ｏコンポーネントからであるときは、常にプロセッサコア１２０のデータ−キャッシュタグを（２部とも）無効にする。
【００２９】
ＤＲＡＭコントローラ１３３は、最大１６メガバイトのＤＲＡＭをサポートする。ＤＲＡＭコントローラ１３３は、ＤＲＡＭ１０８との６４ビットまたは１２８ビットインタフェースをサポートする。ＤＲＡＭコントローラ１３３は、ＤＤＲ−Ｉ（ダブルデータレート）およびＤＤＲ−IIプロトコルをサポートする。
【００３０】
プロセッサコア１２０によってパケットが処理されると、パケット出力ユニット（ＰＫＯ）１４６は、メモリからパケットデータを読み出し、Ｌ４ネットワークプロトコル後処理を実行し（例えば、ＴＣＰ／ＵＤＰチェックサムを生成し）、上記パケットをＧＭＸ／ＳＰＸユニット１２２ａ、１２２ｂを介して転送し、パケットによって使用されたＬ２キャッシュ１３０／ＤＲＡＭ１０８を解放する。
【００３１】
低遅延メモリコントローラ３６０（図３Ｂ）は、ＬＬＭ１１８との間の処理中（in-flight）のトランザクション（ロード／格納）を管理する。低遅延メモリ（ＬＬＭ）１１８は全てのプロセッサコア１２０によって共有される。ＬＬＭ１１８は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、低遅延ダイナミックランダムアクセスメモリ（ＲＬＤＲＡＭ）、同期ランダムアクセスメモリ（ＳＲＡＭ）、高速サイクルランダムアクセスメモリ（ＦＣＲＡＭ）または技術的に公知の他の任意の種類の低遅延メモリであってもよい。ＲＬＤＲＡＭは、３０ナノ秒またはそれ以下のメモリ遅延（すなわち、プロセッサ１２０によって開始されたメモリ要求が満たされるまでに要する時間）を提供する。各プロセッサコア１２０は、低遅延メモリバス１５８によってＬＬＭコントローラ３６０に直接結合される。低遅延メモリバス１５８は、プロセッサコア１２０とＬＬＭコントローラ３６０との間のコンテンツアウェア型アプリケーション処理のための通信チャネルである。ＬＬＭコントローラ３６０は、ＬＬＭ１１８へのアクセスを制御するためにプロセッサコア１２０とＬＬＭ１１８との間に結合される。
【００３２】
ネットワークサービスプロセッサ１１０は、プロセッサコア１２０をオフロード（負荷軽減）する特定用途向けコプロセッサを有し、これにより、ネットワークサービスプロセッサが高スループットを達成できるようにする。圧縮／解凍コプロセッサ１３２は、受信パケットの圧縮および解凍を専用に実行する。決定性有限オートマトン（ＤＦＡ）モジュール１３４は、専用のＤＦＡエンジン３７０（図３Ｂ）を有し、アンチウィルス（ＡＶ）、侵入検知システム（ＩＤＳ）および他のコンテンツ処理アプリケーションに必要なパターンおよび署名一致の処理を速くして、最大４Ｇｂｐｓまで加速する。
【００３３】
コンテンツアウェア型アプリケーションの処理は、ＬＬＭ１１８に格納されるパターン／表現（データ）を利用する。パターン／表現は、決定性有限オートマトン（ＤＦＡ）の形式であってもよい。ＤＦＡは、状態マシンである。ＤＦＡ状態マシンへの入力は、バイト（１バイト＝８ビット）の文字列である（すなわち、ＤＦＡではアルファベットが１バイトである）。各入力バイトが、状態マシンを１つの状態から次の状態に遷移させる。状態および遷移関数は、図２Ａに示すように、グラフ２００で表示することができる。ただし、各グラフノード（ノード０〜３）は１つの状態であり、異なるノードを相互接続する異なるグラフ弧は異なる入力バイトに対する状態遷移を表す。状態は、「Ａ…Ｚ，ａ…ｚ，０…９，」などの、状態に関連する特定の文字を含む。状態マシンの現在の状態は、グラフの特定のノードを選択するノード識別子である。ノード数は、小型サイズのグラフで数ノードから約128,000ノードまでの範囲内であってもよい。大型サイズのグラフは1,000,000ノードまでを有してもよく、それ以上であってもよい。
【００３４】
説明のための例では、ＤＦＡグラフ２００は、ターゲットの文字列表現「ａｂｃ」を探索するように設計されている。したがって、ＤＦＡグラフは、文字「ａｂｃ」の文字列に正確に一致する入力データを探索するために使用される。この表現は固定長表現であり、これより、ノード数、したがってグラフの深さは既知である（すなわち、一定である）。
【００３５】
ＤＦＡグラフを生成するために、上記表現が解析され、コンパイラはルートノード（すなわち、ノード「０」）を生成し、意図する表現に即してグラフにノード１から３を追加する（すなわち、ターゲット文字列の各文字につき１つの追加ノード）。本例を引き続き参照すると、例示的な文字の入力ストリームが文字列「１２ａｂｃ３」を含む。ＤＦＡグラフを使用して入力文字列が探索され、ターゲット文字列表現「ａｂｃ」が識別される。
【００３６】
ＤＦＡグラフの初期状態は、ノード「０」である。各文字またはバイトは逐次読み取られ、ＤＦＡは、ターゲット文字列表現の最初の文字が読み取られるまでノード０に留まる。例えば、入力ストリームにおけるターゲット文字列表現の最初の文字「ａ」が検出されると、ノード０からノード１に「ａ」で表記された弧が辿られる。次に、入力ストリームの次の文字が読み取られ、これがターゲット文字列表現の次の文字（すなわち、「ｂ」）以外のいずれかであることが検出されれば、「not ｂ」で表記された、ノード１からノード０に戻る弧が辿られる。しかし、入力ストリーム内の次の文字として文字「ｂ」が検出されると、「ｂ」で表記されたノード１からノード２への弧が辿られる。次いで、入力ストリームの次の文字が読み取られ、これがターゲット文字列表現の次の文字（すなわち、「ｃ」）以外のいずれかの文字であれば、「not ｃ」で表記されたノード２からノード０に戻る弧が辿られる。しかし、ノード２において、入力ストリーム内の文字「ｃ」が検出されると、「ｃ」で表記されたノード２からノード３への弧が辿られる。ターゲット文字列表現「ａｂｃ」は固定長表現であることから、ノード３は終端ノードであり、探索の結果、すなわち、表現「ａｂｃ」が発見されたことと、入力ストリーム内のこの表現の位置とが報告される。
【００３７】
さらに、コンパイラで１つまたは複数の意図する表現を解析し、意図する表現が要求する通りにグラフの適切なノードを生成することによって、さらに複雑なＤＦＡグラフを同様に生成することができる。したがって、単一のグラフを使用して、固定長、可変長および固定／可変長の組合せである複数の表現を探索することができる。
【００３８】
図３Ａは、本発明の原理による縮小命令セットコンピュータ型（ＲＩＳＣ）プロセッサ１２０を示すブロック図である。プロセッサ（プロセッサコア）１２０は整数演算ユニット３０２、命令ディスパッチユニット３０４、命令フェッチユニット３０６、メモリ管理ユニット（ＭＭＵ）３０８、システムインタフェース３１０、低遅延インタフェース３５０、ロード／格納ユニット３１４、書込みバッファ３１６、およびセキュリティアクセラレータ１５６を有する。プロセッサコア１２０はデバッグ動作を実行できるＥＪＴＡＧインタフェース３３０も有する。システムインタフェース３１０は、外部メモリ、すなわち、外部（Ｌ２）キャッシュメモリ１３０または主／メインメモリ１０８などの、プロセッサ１２０の外側にあるメモリへのアクセスを制御する。
【００３９】
整数演算ユニット３０２は、乗算ユニット３２６、少なくとも１つのレジスタファイル（主レジスタファイル）３２８、および２つの保持レジスタ３３０ａ、３３０ｂを有する。保持レジスタ３３０ａ、３３０ｂは、ＬＬＭのロード／格納命令を使用して、ＬＬＭ１１８に書き込まれるデータと、ＬＬＭ１１８から読み出されたデータとを格納するために使用される。保持レジスタ３３０ａ、３３０ｂは、命令パイプラインの効率を、このパイプラインを機能停止する前に２つの未処理ロードを許容することによって向上させる。２つの保持レジスタを示したが、１つ、または複数の保持レジスタを使用してもよい。乗算ユニット３２６は６４ビットのレジスタの直接乗算を実行できる。命令フェッチユニット３０６は、命令キャッシュ（ＩＣａｃｈｅ）１５２を有する。ロード／格納ユニット３１４はデータキャッシュ１５４を有する。一実施形態においては、命令キャッシュ１５２は３２キロバイトであり、データキャッシュ１５４は８キロバイトであり、書込みバッファ３１６は２キロバイトである。メモリ管理ユニット３０８は、変換ルックアサイドバッファ（ＴＬＢ）３４０を有する。
【００４０】
一実施形態においては、プロセッサ１２０は、トリプルデータ暗号化規格（３ＤＥＳ）、高度暗号化規格（ＡＥＳ）、セキュアハッシュアルゴリズム（ＳＨＡ−１）、メッセージダイジェストアルゴリズム５番（ＭＤ５）のための暗号アクセラレーションを含む暗号アクセラレーションモジュール（セキュリティアクセラレータ）１５６を有する。暗号アクセラレーションモジュール１５６は、転送を通して、演算ユニット３０２内の主レジスタファイル３２８と通信する。ＲＳＡおよびディフィ−ヘルマン（ＤＨ）アルゴリズムが、乗算ユニット３２６において実行される。
【００４１】
図３Ｂは、図３ＡのＤＦＡモジュール１３４を示すブロック図である。ＤＦＡモジュール１３４は低遅延ＤＲＡＭコントローラ３６０、少なくとも１つのＤＦＡスレッドエンジン（ＤＴＥ）３７０（１６個が示されている）、および命令入力論理３８０を有する。命令入力論理３８０は、ＤＦＡ命令待ち行列３８２およびドアベル３８４を有する。ＤＦＡ命令待ち行列３８２はＬ２／ＤＲＡＭ（１３０／１０８）に格納されたＤＦＡ命令をキューイングして（待ち行列に入れ）、ドアベルはＤＦＡ命令待ち行列３８２に格納されているＤＦＡ命令の数を示す。コア１２０のソフトウェアは、個々のＤＦＡ命令ごとにドアベルの書込みを発行することができ、すなわち、複数のＤＦＡ命令を単一のドアベル書込みに累積させることができる。各ＤＦＡ命令は、ＤＦＡモジュール１３４がＤＴＥ３７０を開始し、入力データを読み出し、ＬＬＭ１１８内に格納されているＤＦＡグラフ２００を走査し、かつ結果をＬ２／ＤＲＡＭ（１３０／１０８）に書き込む必要があるという情報を含む。ＤＦＡ命令のフォーマットについては、図８Ａに関連して後述する。
【００４２】
ＤＴＥ３７０は、パターン探索の実行に使用されることができる。一般に、ＤＴＥ３７０は、パケットデータ（Ｌ２／ＤＲＡＭ（１３０／１０８）内に存在）内の特定の表現を探索するために、入力パケットデータを用いてＤＦＡグラフ２００（図２）（ＬＬＭ１１８内に存在）を走査する。例えば、ネットワークサービスプロセッサは、別個のＤＴＥに送られた各入力ストリームを用いて同時に最大1000のＴＣＰ入力ストリームを追跡して、特定の表現を探索することができる。走査に先行して、コア１２０内のソフトウェアは、最初に、（i）ＬＬＭ１１８内のＤＦＡグラフをＬＬＭバス１５８を介して事前にロードし、（ii）Ｌ２／ＤＲＡＭ（１３０／１０８）内のＤＦＡ命令を事前にロードし、かつ（iii）ＩＯＢ１４２を介してＤＦＡ命令をＤＦＡモジュール１３４に送出する必要がある。ＤＦＡ命令は、入力パケットデータを用いて走査するＤＦＡグラフ２００を示す。この後、ＤＦＡモジュール１３４はＤＦＡ命令をフェッチして待ち行列に入れ、各ＤＦＡ命令を利用可能な１６個のＤＴＥ３７０のうちの１つにスケジューリングする。任意のＤＦＡ命令が任意の利用可能なＤＴＥ３７０にスケジューリングされることができるように、ＤＴＥ３７０は全て同一であり、等価である。命令を受信すると、ＤＴＥ３７０は、同時に、（ａ）ＩＯＢ１４２を介してＬ２／ＤＲＡＭ（１３０／１０８）からパケットデータをフェッチし、（ｂ）パケットデータのバイト毎に、このバイトについてＤＦＡグラフの次の状態へ移るようにＬＬＭ  ＤＲＡＭロード命令を発行し、（ｃ）ＩＯＢ１４２を介して元のＬ２／ＤＲＡＭ（１３０／１０８）に中間および最終結果を戻して書き込む。
【００４３】
一般に、ＤＴＥ３７０は、ハードウェア、ソフトウェアまたはハードウェア／ソフトウェアの組合せを使用して実現できる状態マシンである。実施形態によっては、ＤＴＥ３７０は、組合せ論理を使用してハードウェアで実現される。他の実施形態では、各ＤＴＥ３７０は異なるプロセッサ上でそれぞれ実現される。さらに他の実施形態では、ＤＴＥ３７０は共通のプロセッサを使用して実現される。例えば、各ＤＴＥ３７０は、共有のマルチタスク環境を提供するように適合化された共通のプロセッサ上で実行される個別のタスク（すなわち、命令シーケンス）であってもよい。マルチタスキングは、オペレーティングシステムにおいて複数の独立したジョブ（すなわち、ＤＴＥ３７０）間で単一のプロセッサを共有する技術である。さらに、もしくは代替として、ＤＴＥ３７０のそれぞれは、マルチスレッディング能力を提供するように適合化された共通プロセッサ上で実行される個別のプロセススレッドであってもよい。マルチスレッディングとマルチタスキングとの差は、スレッドが一般に、マルチタスキング下でタスクを実行するのに比べてその環境を互いに多く共用する点である。例えば、複数スレッドが単一アドレス空間および全体変数セットを共有する一方で、スレッドのプログラムカウンタおよびスタックポインタの値によって各スレッドを区別することもできる。
【００４４】
図４Ａは、Ｌ２／ＤＲＡＭ（１３０／１０８）に格納されるＤＦＡ命令待ち行列４００の構造を示す。各命令待ち行列は、チャンクまたはバッファ４０２のリンクされたリストである。各チャンク４０２は少なくとも３つのＤＦＡ命令４０４を含み、これら３つの命令が全体チャンクサイズ４０６を構成する。別のチャンク（例えば、４０２’）が存在すれば、チャンク４０２内の最後のＤＦＡ命令４０４の直後に、次のチャンクバッファポインタ４０８が続く。
【００４５】
ＤＦＡ命令待ち行列４００にパケットを挿入するには、コア１２０のソフトウェアはＤＦＡ命令４０４をＤＦＡ命令待ち行列４００に書き込み、必要であればチャンクを割り当て、次いでＤＦＡドアベル３８４に、ＤＦＡ命令待ち行列４００に追加されたＤＦＡ命令４０４の数を書き込む。ＤＦＡモジュール１３４は、ＤＦＡ命令待ち行列４００を読み出し（テール４１０から開始）、チャンクの最後の命令（例えば、４０４／４０４’’’）に到達すると、次のチャンク（例えば、４０２’／４０２’’）を指す次のチャンクバッファポインタ４０８を走査する。このようにしてチャンク４０２をジャンプすると、ＤＦＡモジュール１３４は、前のチャンク（例えば、４０２／４０２’）をＦＰＡ１２８（図１Ｂ）に解放する。
【００４６】
ＤＦＡモジュール１３４は、ＤＦＡ命令待ち行列４００のテールポインタ４１０を保持し、コア１２０のソフトウェアはＤＦＡ命令待ち行列４００のヘッドポインタ４１２を保持する。テールポインタ４１０とヘッドポインタ４１２との距離は、ＤＦＡ命令待ち行列４００のサイズ、および未処理のドアベルカウント数の両方に等しい。ＤＦＡ命令待ち行列４００のサイズは、利用可能なメモリおよびＤＦＡ命令待ち行列４００についての２０ビットである処理中ドアベルカウンタによってのみ制限される。
【００４７】
図４Ｂは、次のチャンクバッファポインタのフォーマット４５０を示す。次のチャンクバッファポインタは６４ビットワードであり、３６ビットのアドレス（Ａｄｄｒ）フィールド４５２を含む。Ａｄｄｒフィールド４５２は、次のＤＦＡ命令４０２を含む次のチャンク４００の有効なＬ２／ＤＲＡＭ（１３０／１０８）バイト位置を選択する。Ａｄｄｒフィールド４５２はバイトアドレスであるが、これは、その最小位の７ビットをゼロに設定することによって、１２８バイトのキャッシュブロックの境界上に当然に揃えられる。
【００４８】
図５Ａは、ＬＬＭ１１８に格納されるＤＦＡグラフ５００の構造を示す。ＤＦＡグラフ５００は、５１０ａ〜５１０ｎまでのＮ個のノードを含む。ＤＦＡグラフ５００内のノード５１０はそれぞれ、２５６個の次のノードポインタ５１２の単なるアレイであり、この次のノードポインタのそれぞれは入力バイト値に固有である。各次のノードポインタ５１２は、入力バイトの次のノード／状態を直接指定する次のノードＩＤ５１４を含む。
【００４９】
ＤＦＡモジュール１３４は、１８ビットの次のノードポインタ格納フォーマット５１６または３６ビットの次のノードポインタ格納フォーマット５１８のいずれかをサポートする。１８ビットのポインタの場合、各ノード５１０は、１８＊２５６ビットすなわち５１２バイトのＬＬＭ１１８格納を必要とする。各次のノードポインタ５１６は１７ビットの次のノードＩＤおよび１ビットのパリティビットである。パリティは、偶数である（すなわち、Ｐは１７ビットの次のノードＩＤ５１４における全ビットのＸＯＲ（排他的ＯＲ））。３６ビットポインタの場合、各ノード５１０は、３６＊２５６ビットすなわち約１キロバイトのＬＬＭ１１８格納を必要とする。したがって、複製は、格納に必要な容量要件を増大させる。各次のノードポインタ５１８は、２０ビットの次のノードＩＤ、２ビットのタイプ値、７ビットのＳＥＣＤＥＤ  ＥＣＣコード、およびゼロに設定される未使用の７ビットである。ＤＴＥ３７０は、３６ビットポインタ内のＳＥＣＤＥＤ  ＥＣＣコードを使用して全てのシングルビットエラーを自動的に修正し、全てのダブルビットエラーを検出する。タイプ値は次のノードのタイプ、例えば、０＝ノーマル、１＝マーク付け、２＝終端、を表示する。
【００５０】
ＤＴＥ３７０は、以下に示す３つの特別なノードポインタ条件をサポートする。
１．ＰＥＲＲ  −  次のノードポインタがエラーを含む。ＤＴＥ３７０は、欠陥のあるＬＬＭ１１８の位置を表示する結果ワードを生成する。ＤＴＥ３７０は、グラフ５００の走査を停止する。
２．ＴＥＲＭ  −  次のノードは終端ノードであり、グラフの走査は停止すべきである。ＤＴＥ３７０は、終端ノードへ走査したバイト、前のノードＩＤおよび次のノードＩＤを表示する結果ワードを生成する。ＤＴＥ３７０は、グラフ５００の走査を停止する。
３．ＭＡＲＫＥＤ  −  この遷移は、コア１２０のソフトウェアによる後の分析用にマーク付けされる。ＤＴＥ３７０は、上記マークされたノードへ走査したバイト、前のノードＩＤおよび次のノードＩＤを表示する結果ワードを生成する。ＤＴＥ３７０は、グラフ５００の走査を続行する。
【００５１】
１８ビットモードの場合、ＤＴＥ３７０は、次のノードＩＤを比較することによって、特殊なＴＥＲＭおよびＭＡＲＫＥＤ条件を判断する。この場合、マーク付けされたノードに入る全ての遷移がマーク付けされる。３６ビットモードの場合、ＤＴＥ３７０は、特殊なＴＥＲＭおよびＭＡＲＫＥＤ条件を次のノードポインタ内のタイプフィールドから直接判断する。３６ビットモードでは、個々のノードそのものではなく、個々の遷移にマーク付けすることができる。
【００５２】
図５Ｂは、可能な１７ビットノードＩＤの全て、およびこれらが１８ビットモードにおいていかに分類されるかを明らかにしている。終端ノードＩＤ５０２は、ＬＬＭ１１８内に実際に格納されることによるバックアップはされない。しかし、ノーマルノード５０４およびマーク付けされたノード５０６は、実際のＬＬＭ１１８への格納によってバックアップされる。ＤＦＡ命令４０４は、ＩＷＯＲＤ３（図８Ａ）に格納されるTSize（図８Ａ）である終端ノードの数５０３と、同様にＩＷＯＲＤ３に格納されるMSize（図８Ａ）であるマークされたノードの数５０７とを含む。
【００５３】
ＤＴＥ３７０は、グラフ５００を走査する間、例外的な条件が発生すると結果ワードを生成する。ＭＡＲＫＥＤ、ＴＥＲＭまたはＰＥＲＲである次のノードポインタは、このような例外的条件である。例外的な条件としては、さらに、入力データの完了および結果スペースの消耗という２つがある。入力バイトに関するグラフの走査は複数の例外的条件をもたらすこともあるが、単一の入力バイトから生成できる結果ワードは多くても１つである。例えば、最後の入力バイトが入力データの完了条件に遭遇すると、結果ワードを生成する。最後の入力バイトもマーク付けされた次のノードに遭遇することがあるが、第２の結果ワードは生成されない。グラフの走査は、（優先順に）ＰＥＲＲ、ＴＥＲＭ、入力データの完了および結果スペースの消耗という例外条件が発生した時点で停止し、ＤＴＥ３７０はその最も高い優先順位条件を報告する。例えば、図２のグラフを参照すると、次のノードはノード「ｃ」に到達した時点の終端ノードであり、ＤＴＥ３７０はグラフの走査を停止する。
【００５４】
各ＤＦＡ命令は、ＤＴＥ３７０によって、処理されるデータをいかにＬ２／ＤＲＡＭに格納するか（ダイレクトまたはギャザー）を指定できる。いずれの場合も、ＤＦＡモジュール１３４はＬ２／ＤＲＡＭ（１３０／１０８）からバイトを読み出す。
【００５５】
図６は、ＤＴＥ３７０によって処理されるデータを取得する例示的なダイレクトモード６００を示す。ＤＦＡ命令４０４は、開始位置およびバイト数を直接指定する。対応するＤＦＡ命令４０４を処理するＤＴＥ３７０は、Ｌ２／ＤＲＡＭ（１３０／１０８）から連続するバイトを読み出し、これらを処理する。
【００５６】
図７Ａは、ＤＴＥ３７０によって処理されるデータを取得する例示的なギャザーモード７００を示す。ＤＦＡ命令４０４は、ＤＦＡギャザーポインタ７１０のリストの開始位置およびサイズを直接指定する。ＤＦＡギャザーポインタ７１０リストの各エントリは、ＤＴＥ３７０が処理する開始位置およびバイト数を指定する。ＤＴＥ３７０の全体入力バイトストリームは、ＤＦＡギャザーポインタ７１０リストの各エントリによって指定されるバイトの連結である。
【００５７】
図７Ｂは、６４ビットＤＦＡギャザーポインタ７１０のフォーマットを示す。ＤＦＡギャザーポインタ７１０は、長さ７１２（バイト数）およびアドレスフィールド７１４（Ｌ２／ＤＲＡＭアドレス）を含む。ＤＦＡギャザーポインタ７１０は６４ビットの境界上に当然に揃えられるが、これらポインタが指すＬ２／ＤＲＡＭ内のバイトは任意の位置であってもよく、当然に揃えられなくてもよい。ギャザーモード７００では、合計バイト数は全てのＤＦＡギャザーポインタ７１０における長さフィールドの総和である。
【００５８】
図４Ａを再度参照して、各ＤＦＡ命令４０４は、ＤＦＡモジュール１３４によって必要とされる情報を提供して、（i）ＤＴＥ３７０を開始し、（ii）入力データを読み出し、（iii）ＬＬＭ１１８内のグラフ２００を走査し、（iv）結果を書き込む。ＤＦＡ命令４０４は、図８Ａに示す例示的なＤＦＡ命令フォーマットのような複数の命令ワードを含んでもよい。各ＤＦＡ命令４０４は、４つの独立したワード、４５５’、４５５’’、４５５’’’、４５５’’’’（総称して４５５）を含む。これらのワードはそれぞれ６４ビットを含み、レベル２キャッシュメモリ１３０またはＤＲＡＭ１０８内の合計３２バイトで表現される。好ましくは、各ＤＦＡ命令４０４は３２バイトの境界上に当然に揃えられる。ＤＦＡ命令４０４は、この命令がスケジューリングされている個々のＤＴＥ３７０によって処理される。ＤＦＡ命令４０４は、入力バイトの位置および結果の位置の両方を特定するフィールドを含む。
【００５９】
動作中、ＤＦＡモジュール１３４は、ＤＦＡ命令待ち行列３８２が有効なＤＦＡ命令４０４を有していれば、レベル２キャッシュメモリ１３０またはＤＲＡＭ１０８からＤＦＡ命令４０４および入力データを読み出し、結果を生成すると、その結果を書き込む（例えばバイト毎に）。また、ＤＦＡモジュール１３４は、終了後にＰＯＷ１４８（図１Ｂ）によってスケジューリングされるワーク待ち行列エントリを随時に送出でき、したがって、ＤＦＡ命令４０４はワーク待ち行列ポインタのためのフィールドを含むこともできる。
【００６０】
さらに詳細には、第１のＤＦＡ命令ワード４５５’は、その第１ノードによって使用される特定のＤＦＡグラフを指定する開始ノードＩＤ４６０を含む。第１ワード４５５’はまた、ＬＬＭ１１８内に格納される特定されたグラフの複製数に対応する複製値を格納する複製フィールド４６２などの追加情報も提供する。また、使用されるアドレス指定のタイプを示すタイプ値４６４（１８または３６ビット）が提供されてもよい。例示的な６４ビットワードは、１つまたは複数の予約フィールドも含む。
【００６１】
第２のＤＦＡ命令ワード４５５’’は、ＤＦＡモジュール１３４によって処理されるバイト数を特定する長さフィールド４７０と、処理されるパケットデータのレベル２キャッシュメモリ１３０またはＤＲＡＭ１０８における位置を特定するアドレスフィールド４７４とを含む。
【００６２】
第３のＤＦＡ命令ワード４５５’’’は、任意の結果が書き込まれるアドレス（例えば、レベル２キャッシュメモリ１３０またはＤＲＡＭ１０８内のアドレス）を特定する結果アドレスフィールド４８２と、許容される最大結果数を示す値を格納する最大結果フィールド４８０とを含む。さらに、ＤＦＡモジュール１３４は、終了後に随意にワーク待ち行列エントリを送出できるため、ＤＦＡ命令４０４は１つまたは複数のワーク待ち行列ポインタに対するワーク待ち行列処理（ＷＱＰ）フィールド４９０を含む。
【００６３】
図８Ｂは、ＤＦＡ命令４０４の結果フォーマット８００を示す。ＤＦＡ結果８００は、Ｌ２／ＤＲＡＭ（１３０／１０８）内に２つ以上の６４ビットのワードを有する。各ワードは、Ｌ２／ＤＲＡＭ（１３０／１０８）内に当然に揃えられる。ＤＦＡモジュール１３４は、ＤＦＡ命令４０４の処理中および処理後に、これらのワードをＬ２／ＤＲＡＭ（１３０／１０８）に書き込む。この構造体は可変長であって、可変数のマーク付けされたノードにヒットするＤＦＡ命令４０４を収容するが、結果の長さはＤＦＡ命令フィールドの最大結果の上限によって制限される場合がある。
【００６４】
先に述べたとおり、３６ビットのポインタ５１８（図５Ａ）を備えたタイプフィールドを使用することによって、ノードタイプをＤＦＡグラフのノードのうちの任意の１つまたはそれ以上に関連づけることが可能である。ＤＴＥ３７０は、グラフを走査する間に、例外的条件が発生すると結果ワードを生成する。少なくとも１つの例外的条件は、終端ノードである。ＤＴＥ３７０が終端ノードに達すると、このノードはＤＦＡグラフが終わりに到達したことを表し、ＤＴＥ３７０による走査は停止する。例外的条件の別の例は、マーク付けされたノードである。終端ノードとは対照的に、ＤＴＥ３７０がマーク付けされたノードに達しても、グラフの走査は必ずしも停止しない。しかし、出力ワードに、後の分析のために特定の上記マーク付けされたノードを特定する結果が書き込まれる。したがって、マーク付けされたノードを使用して、グラフ内の対応するノードが走査される時点を特定できる。
【００６５】
ＤＦＡ結果８００のＷＯＲＤ０は、ＤＦＡモジュール１３４によって２回以上書き込まれてもよい。ＷＯＲＤ０への最後の書込みのみが、有効なＤＦＡ結果８００を含む。ＤＦＡモジュール１３４は、ＷＯＲＤ０を複数回書き込むことができるが、ビット１６を設定できるのは最後の書込みのみである。すなわち、ビット１６は、ＤＦＡモジュール１３４がＤＦＡ命令４０４を完了するまでＤＦＡモジュール１３４によって設定されない。ＤＦＡモジュール１３４にＤＦＡ命令４０４を渡する前にＷＯＲＤ０の結果ビット１６にゼロを書き込むことによって、ソフトウェアは、ＷＯＲＤ０のビット１６をポーリングして、ＤＦＡモジュール１３４がＤＦＡ命令４０４を完了した時点を判断することができる。ＤＦＡ結果のＷＯＲＤ０が設定されているときは、全体結果が存在する。
【００６６】
図２Ｂに示す別の例では、２つの異なる文字列「ａｂｃｄ」および「ａｂｃｅ」の１つまたは複数の出現を発見するために、図２Ａのグラフが拡張されたものである。したがって、図２Ａのグラフに２つの追加ノード、すなわち、ノード４および５が追加されており（例えば、「ｄ」に対するノード４および「ｅ」に対するノード５）、１つのノードが各字列の第４文字に対するものである。いずれの文字列も最初の３文字が同一であるため、ノード４および５は、図のようにノード３に接続されている。好ましくは、いずれの文字列の場合もその出現は全て、入力文字列を通る単一の「パス」上で識別される。
【００６７】
文字列「ｘｗａｂｃｄ４５４ａｂｃｅａｂｃｄｓｆｋ」などの例示的な入力文字列は、ＤＦＡを通過し、結果として３つの「マーク付けされた」遷移が生成される。マーク付けされた遷移は、入力文字列内に配置される文字列セグメントの終わりで発生する（例えば、「ｄ」または「ｅ」が存在している各位置で１つ）。したがって、３つのマーク付けされた遷移は、３つの文字列が発見されたことを表す。最初と最後のマークはノード３からノード４への遷移を示し、入力文字列内の文字列「ａｂｃｄ」の存在および位置を表す（すなわち、ＤＴＥバイト＝５、先行＝３、次＝４およびＤＴＥバイト＝１７、先行＝３、次＝４）。中央のマーク付けされたノードは、ノード３からノード５への遷移を示し、入力文字列内の文字列「ａｂｃｅ」の存在を表す（すなわち、ＤＴＥバイト＝１３、先行＝３、次＝５）。ノード４および５は１８ビットポインタを使用してマーク付けされ、ノード３からノード４および５までの弧は３６ビットポインタを使用してマーク付けされる。したがって、ＤＦＡマーキング技術をＤＦＡスレッドエンジンと組み合せて使用することによって、同一入力文字列内の複数の異なる文字列の存在および位置を、上記入力文字列を通る１回のパスで発見することができる。
【００６８】
本出願は、2004年9月10日に出願された米国仮特許出願第60/609,211号、2004年12月28日に出願された米国特許出願第11/024,002号、2005年4月8日に出願された「Deterministic Finite Automata (DFA) Instruction」と題する米国仮特許出願第60/669,603号および2005年4月8日に出願された「Selective Replication of Data Structures」と題する米国仮特許出願第60/669,655号に関連するものである。上述の出願の全内容は参照により本明細書に引用したものとする。
【００６９】
以上、本発明をその好ましい実施形態に関連して詳細に示しかつ説明してきたが、当業者には、添付の特許請求の範囲に包含される本発明の範囲を逸脱することなく形態および細部に様々な変更を行ない得ることが理解されるであろう。
【図面の簡単な説明】
【００７０】
【図１Ａ】本発明の原理によるネットワークサービスプロセッサを含むネットワークサービス処理システムを示すブロック図である。
【図１Ｂ】図１Ａに示すネットワークサービスプロセッサを示すブロック図である。
【図２Ａ】例示的なＤＦＡグラフを示す概略図である。
【図２Ｂ】例示的なＤＦＡグラフを示す概略図である。
【図３Ａ】本発明の原理による縮小命令セットコンピュータ（ＲＩＳＣ）プロセッサを示すブロック図である。
【図３Ｂ】図３ＡのＤＦＡモジュールを示すブロック図である。
【図４Ａ】ＤＦＡ命令待ち行列の構造体を示す図である。
【図４Ｂ】次のチャンクバッファポインタの命令フォーマットを示す図である。
【図５Ａ】典型的なＤＦＡグラフの別の実施形態を示す図である。
【図５Ｂ】図５ＡのＤＦＡグラフの異なる可能なノードＩＤを示す図である。
【図６】ＤＴＥによって処理されるデータを構成するための直接モードの一例を示す図であえる。
【図７Ａ】ＤＴＥによって処理されるデータを構成するためのギャザーモードの一例を示す図である。
【図７Ｂ】ＤＦＡギャザーポインタの命令フォーマットを示す図である。
【図８Ａ】ＤＦＡ命令フォーマットを示す図である。
【図８Ｂ】ＤＦＡ結果フォーマットを示す図である。
【符号の説明】
【００７１】
１１０  プロセッサ
１２０  プロセッサコア
４００  ＤＦＡモジュール
【図１Ａ】
2008512797.tif 000003
【図１Ｂ】
2008512797.tif 000004
【図２Ａ】
2008512797.tif 000005
【図２Ｂ】
2008512797.tif 000006
【図３Ａ】
2008512797.tif 000007
【図３Ｂ】
2008512797.tif 000008
【図４Ａ】
2008512797.tif 000009
【図４Ｂ】
2008512797.tif 000010
【図５Ａ】
2008512797.tif 000011
【図５Ｂ】
2008512797.tif 000012
【図６】
2008512797.tif 000013
【図７Ａ】
2008512797.tif 000014
【図７Ｂ】
2008512797.tif 000015
【図８Ａ】
2008512797.tif 000016
【図８Ｂ】
2008512797.tif 000017
【国際調査報告】
2008512797.tif 000018
2008512797.tif 000019