(57)【要約】マルチコアを有するネットワークサービスプロセッサ内のワークを順序づけ、同期化しかつスケジューリングする方法とその装置を提供する。各ひとまとまりのワークは、このワークがいかに同期化されかつ順序づけられるべきかを示すタグによって特定される。異なるタグを有するワークを異なるプロセッサコアで並列に処理することによって、スループットが向上する。パケット処理は種々のステージに分割されることができ、各ステージは、順序づけおよび同期化に関する制約に応じて、異なるタグを有する。コアによって開始されるタグスイッチ操作は、ステージに応じてタグを切り換える。専用のタグスイッチバスが、タグスイッチ操作の待ち時間を最小限に抑える。【選択図】図６
2008512950.tif 000002
【特許請求の範囲】
【請求項１】
複数の独立したプロセッサであって、各プロセッサは並行に動作してワークを実行するプロセッサと、
前記プロセッサによって並行に実行されるワークを、ワークのタグに基づいて、ワークの実行が順序づけされかつ同期化されるように、動的にスケジューリングするワーク順序モジュールとを備えたネットワークサービスプロセッサ。
【請求項２】
請求項１において、前記プロセッサによって実行されるワークが入力待ち行列に格納されるネットワークサービスプロセッサ。
【請求項３】
請求項２において、前記ワーク順序モジュールが、さらに、複数の処理中リストを備え、
各処理中リストは、タグを有する処理中ワークを追跡するために、それぞれ別個のタグを有しており、前記ワーク順序モジュールは入力待ち行列に格納されているワークを、ワークのタグに応じて、処理中リストにスケジューリングするネットワークサービスプロセッサ。
【請求項４】
請求項２において、前記ワーク順序モジュールが、さらに、プロセッサごとのグループ識別子を備え、
このグループ識別子はプロセッサがワークを受け入れるワークのグループを示し、前記ワーク順序モジュールは入力待ち行列のワークをグループによって区別化して、そのグループからワークを受け入れるプロセッサにワークがスケジューリングされるようにする、ネットワークサービスプロセッサ。
【請求項５】
請求項２において、入力待ち行列のワークは、前記ワーク順序モジュールまたは前記ワーク順序モジュールの外部に存在するメモリに格納されることができるネットワークサービスプロセッサ。
【請求項６】
請求項１において、さらに、タイマを備え、
このタイマはワークが入力待ち行列に追加される時点を制御するネットワークサービスプロセッサ。
【請求項７】
請求項５において、前記タグはタグタイプを有し、前記処理中リストが、このリストの先頭にあるワークのみが前記複数のプロセッサのうちの１つによって実行可能であることを示すアトミックのタグタイプを有するワークを格納するネットワークサービスプロセッサ。
【請求項８】
請求項５において、前記タグはタグタイプを有し、前記処理中リストが、このリストの全てのワークが実行可能であることを示す順序づけのタグタイプを有するワークを格納し、ワークは前記複数のプロセッサのうちの１つによって前記リストの先頭からのみ除去されることができるネットワークサービスプロセッサ。
【請求項９】
請求項１において、さらに、
前記複数のプロセッサと前記ワーク順序モジュールとの間に結合され、前記パケットワーク順序モジュールによるタグスイッチ操作の完了の表示を送信する専用タグスイッチバスを備えたネットワークサービスプロセッサ。
【請求項１０】
請求項９において、前記コアは、格納命令を実行することによってタグスイッチ操作を開始し、前記パケットワーク順序モジュールは、この格納命令を検出すると、タグを変更して、変更されたタグに関連する処理中待ち行列にワークを移動させるネットワークサービスプロセッサ。
【請求項１１】
請求項１において、前記ワークはＩＰＳｅｃ復号化を実行するネットワークサービスプロセッサ。
【請求項１２】
請求項１において、前記ワークはＩＰＳｅｃ暗号化を実行するネットワークサービスプロセッサ。
【請求項１３】
請求項１において、前記ワークは仮想プライベートネットワークパケットのデフラグメントであるネットワークサービスプロセッサ。
【請求項１４】
請求項１において、前記ワークはＴＣＰシーケンス番号を調整するネットワークサービスプロセッサ。
【請求項１５】
請求項２において、各入力待ち行列は割り当てられた優先順位を有するネットワークサービスプロセッサ。
【請求項１６】
請求項２において、各入力待ち行列は１つのワークタイプを格納するように割り当てられているネットワークサービスプロセッサ。
【請求項１７】
請求項１において、前記複数のプロセッサのうちの少なくとも１つはコントロールプレーン処理を実行し、前記複数のプロセッサのうちの別の１つはデータプレーン処理を実行するネットワークサービスプロセッサ。
【請求項１８】
ネットワークサービスプロセッサにおけるパケットを処理する方法であって、
複数の独立したプロセッサによってワークを並行に処理する工程と、
前記複数のプロセッサによって並行に実行されるワークを、ワークのタグに基づいて、ワークの実行が順序づけされかつ同期化されるように、動的にスケジューリングする工程とを備えたパケット処理方法。
【請求項１９】
請求項１８において、さらに、
入力待ち行列に格納されているワークを、ワークのタグに応じて、複数の処理中リストのうちの１つにスケジューリングする工程であって、各処理中リストは、タグを有する処理中ワークを追跡するために、それぞれ別個のタグを有するスケジューリング工程を備えたパケット処理方法。
【請求項２０】
請求項１９において、さらに、
前記入力待ち行列のワークをグループによって区別化して、そのグループからワークを受け入れるプロセッサにワークがスケジューリングされるようにする工程であって、プロセッサがワークを受け入れるワークのグループをグループ識別子が示す工程を備えたパケット処理方法。
【請求項２１】
請求項１９において、入力待ち行列内のワークは、前記ワーク順序モジュールまたは前記ワーク順序モジュールの外部に存在するメモリに格納されることができるパケット処理方法。
【請求項２２】
請求項１８において、さらに、
タイマによって、ワークが入力待ち行列に追加される時点を制御する工程を備えたパケット処理方法。
【請求項２３】
請求項１８において、前記タグはタグタイプを有し、前記処理中リストが、このリストの先頭にあるワークのみが前記複数のプロセッサのうちの１つによって実行可能であることを示すアトミックのタグタイプを有するワークを格納するパケット処理方法。
【請求項２４】
請求項１８において、前記タグはタグタイプを有し、前記処理中リストが、このリストの全てのワークが実行可能であることを示す順序づけのタグタイプを有するワークを格納し、ワークは前記複数のプロセッサのうちの１つによって前記リストの先頭からのみ除去されることができるパケット処理方法。
【請求項２５】
請求項１８において、さらに、
前記複数のプロセッサと前記ワーク順序モジュールとの間に結合された専用タグスイッチバスで、前記パケットワーク順序モジュールによるタグスイッチ操作の完了の表示を送信する工程を備えたパケット処理方法。
【請求項２６】
請求項２５において、さらに、
格納命令を実行することによってタグスイッチ操作を開始する工程と、この格納命令を検出すると、タグを変更して、変更されたタグを有する処理中待ち行列にワークを移動させる工程とを備えたパケット処理方法。
【請求項２７】
請求項１８において、前記ワークはＩＰＳｅｃ復号化を実行するパケット処理方法。
【請求項２８】
請求項１８において、前記ワークはＩＰＳｅｃ暗号化を実行するパケット処理方法。
【請求項２９】
請求項１８において、前記ワークは仮想プライベートネットワークパケットのデフラグメントであるパケット処理方法。
【請求項３０】
請求項１８において、前記ワークはＴＣＰシーケンス番号を調整するパケット処理方法。
【請求項３１】
請求項１９において、各入力待ち行列は割り当てられた優先順位を有するパケット処理方法。
【請求項３２】
請求項１９において、各入力待ち行列は１つのワークタイプを格納するように割り当てられるパケット処理方法。
【請求項３３】
請求項１９において、前記複数のプロセッサのうちの少なくとも１つはコントロールプレーン処理を実行し、前記複数のプロセッサのうちの別の１つはデータプレーン処理を実行するパケット処理方法。
【請求項３４】
ネットワークサービスプロセッサにおけるパケットを処理する装置であって、
ワークを並行に処理する手段と、
並行に実行されるワークを、ワークのタグに基づいて、ワークの実行が順序づけされかつ同期化されるように、動的にスケジューリングする手段とを備えたパケット処理装置。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、2004年9月10日に出願された米国仮特許出願第60/609,211号の出願の利益を主張する、2004年12月6日に出願された米国特許出願第11/005,490号の継続出願である。上記出願の全内容は参照により本明細書に引用したものとする。
【背景技術】
【０００２】
開放型システム間相互接続（ＯＳＩ）参照モデルは、伝送媒体を介する通信に使用される７つのネットワークプロトコル層（Ｌ１−Ｌ７）を規定している。上位層（Ｌ４−Ｌ７）はエンド・ツー・エンド通信を表し、下位層（Ｌ１−Ｌ３）は局所的な通信を表す。
【０００３】
ネットワーキングアプリケーションアウェア型（アプリケーションが自動的にネットワークを制御する）システムは、Ｌ３からＬ７までの範囲のネットワークプロトコル層、例えば、ハイパーテキスト転送プロトコル（ＨＴＴＰ）およびシンプルメール転送プロトコル（ＳＭＴＰ）などのＬ７ネットワークプロトコル層、および伝送制御プロトコル（ＴＣＰ）などのＬ４ネットワークプロトコル層を処理し、フィルタリングし、かつ切り換える必要がある。ネットワークプロトコル層の処理に加えて、ネットワーキングアプリケーションアウェア型システムは、ファイアウォール、仮想プライベートネットワーク（ＶＰＮ）、セキュアソケットレイヤ（ＳＳＬ）、侵入検知システム、インターネットプロトコルセキュリティ、アンチウィルス（ＡＶ）およびアンチスパム機能を含む、Ｌ４からＬ７までのネットワークプロトコル層を介するアクセスベースおよびコンテンツベースのセキュリティによって、これらのプロトコルの安全性を同時にワイヤスピードで保護する必要もある。
【０００４】
ネットワークプロセッサが、高スループットのＬ２およびＬ３ネットワークプロトコル処理に利用される。このＬ２およびＬ３ネットワークプロトコル処理は、パケットをワイヤスピードで転送するパケット処理の実行である。一般に、より高度の処理を必要とするＬ４からＬ７までのネットワークプロトコルの処理には、汎用プロセッサが使用される。例えば、Ｌ４ネットワークプロトコルである伝送制御プロトコル（ＴＣＰ）は、パケット内の全ペイロードにわたるチェックサムの計算、ＴＣＰセグメントバッファの管理および複数のタイマの接続ごとの常時保持を含む複数の計算集約型タスクを必要とする。汎用プロセッサは、計算集約型タスクを実行できるが、データを処理してワイヤスピードで転送できるだけの十分な性能は備えていない。
【発明の開示】
【０００５】
ネットワークサービスプロセッサは、Ｌ４〜Ｌ７のネットワークプロトコルが１つまたは複数のプロセッサによって実行されるように、ワーク（パケット処理操作）をスケジューリングしてキューイングする（待ち行列に入れる）パケットワーク順序モジュールを有する。スケジューリングされるワークは入力待ち行列に入れられる。パケットワーク順序モジュールによって新しいワークをスケジューリングすることができない場合でも入力待ち行列にワークを追加できるように、入力待ち行列が外部メモリに拡張することができることによって、この入力待ち行列は無限に見える。したがって、新しいワークのキューイングは、パケットワーク順序ユニットがビジーの間でもストール（停止）しない。処理のためにパケットワーク順序モジュールに移動されることが可能になるまで、ワークは外部メモリ内に順番にキューイングされる。
【０００６】
特定のパケットに実行されるパケット処理（ワーク）は、複数のパケット処理操作（ひとまとまりのワーク）を含む。各ひとまとまりのワークは、関連のタグを有する。タグによって、ワークの実行が順序づけられかつ同期化されることを保証しながら、複数のプロセッサによってワークが並列に実行されるように、ワークはスケジューリングされる。パケット処理操作のスケジューリングおよびキューイングによって、ワイヤスピードすなわちネットワークのデータ転送速度でデータが送出されるように、データは処理される。
【０００７】
本発明によれば、パケット処理をキューイングしてスケジューリングするシステムおよび方法は、ネットワークサービスプロセッサにおけるパケット処理のスループットを向上させる。ネットワークサービスプロセッサは、複数の独立したプロセッサ、およびワーク順序モジュールを有する。各プロセッサは並行して動作してワークを実行する。ワーク順序モジュールは、プロセッサによって並行処理されるワークを、ワークに関連づけられているタグに基づいて、ワークの実行が順序づけられかつ同期化されるように、動的にスケジューリングする。
【０００８】
ワーク順序モジュールは、プロセッサによって実行されるワークを格納する入力待ち行列と、複数の処理中のリストとを有する。入力待ち行列内のワークは、ワーク待ち行列が無限に見えるように、ワーク順序モジュールまたはワーク順序モジュールの外部のメモリに格納されることができる。ワーク待ち行列が無限に見えることにより、ワークは外部のメモリにキューイングされて、後に、処理のためにワークがスケジューリングされるのに先立ってパケットワーク順序モジュールに移動されることができる。ワークには、例えば、ＩＰＳｅｃ暗号化、ＩＰＳｅｃ復号化、仮想プライベートネットワークパケットのデフラグメントまたはＴＣＰシーケンス番号の調整が含まれてもよい。プロセッサのうちの少なくとも１つはコントロールプレーンの処理を実行してもよく、プロセッサのうちの別の１つはデータプレーンの処理を実行してもよい。
【０００９】
処理中のリストはそれぞれ、タグに関連する処理中のワークを追跡するために、異なるタグに関連づけられている。入力待ち行列に入っているワークは、ワーク順序モジュールによってスケジューリングされる。ワークは、ワークを入力待ち行列から処理中のリストに移動させることによってスケジューリングされる。処理中のリストは、そのワークに関連づけられているタグに応じて選択される。
【００１０】
ワーク順序モジュールはまた、プロセッサごとのグループ識別子を含んでもよい。グループ識別子は、プロセッサが受け入れるワークのグループを示し、かつ入力待ち行列内のワークをグループによって区別化する。これにより、ワークは、そのグループからワークを受け入れるプロセッサにスケジューリングされる。
【００１１】
ネットワークサービスプロセッサはまた、ワークが入力待ち行列に加えられる時点を制御するためのタイマを有してもよい。タグは、タグタイプを含んでもよい。処理中のリストはアトミックのタグタイプを有するワークを格納してもよく、この場合、リストの先頭にあるワークのみが複数のプロセッサのうちの１つによって実行されることができる。別の処理中のリストは、順序づけのタグタイプを有するワークを格納してもよく、この場合、リスト上のワークは全て実行可能であり、ワークは、複数のプロセッサのうちの１つによってこのリストの先頭からのみ除去されることが可能である。
【００１２】
タグスイッチ操作、すなわち、ワークに関連づけられているタグを変更する操作の遅延を最小限に抑えるために、プロセッサとワーク順序モジュールとの間には、パケットワーク順序ユニットによるタグスイッチ操作の完了の表示を送信する専用のタグスイッチバスが結合されてもよい。コアは、格納命令を実行することによってタグスイッチ操作を開始し、パケットワーク順序ユニットは、タグを変更して、変更されたタグに関連する処理中待ち行列にワークを移動させる。各入力待ち行列は、割り当てられた優先順位を有してもよく、かつ／または特定のワークタイプを格納するように割り当てられてもよい。
【００１３】
各パケット処理操作がいかに実行されるかを規定することができるので、受信パケットの上位プロトコル層処理はパケットをワイヤスピードで転送するように実行される。さらに、入力待ち行列を外部メモリに拡張することができるので、ネットワークサービスプロセッサが他のワークの処理でビジーの間でもワークの順序づけられたキューイングが可能である。
【００１４】
本発明の上述および他の目的、特徴および利点は、添付図面に示す本発明の好ましい実施形態に関する以下のより詳細な説明から明らかとなるであろう。添付図面では、同一参照符号は異なる図面においても同一部分を指す。図面は、必ずしも縮尺通りではなく、本発明の原理を示すことに重点を置いている。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の好ましい実施形態について説明する。
【００１６】
図１は、本発明の原理によるネットワークサービスプロセッサ１００を含むセキュリティアプライアンス１０２を示すブロック図である。セキュリティアプライアンス１０２は、１つのイーサネット（登録商標）ポート（Ｇｉｇ Ｅ）で受信したパケットを別のイーサネット（登録商標）ポート（Ｇｉｇ Ｅ）に切り換えて、受信したパケットに複数のセキュリティ機能を実行した後にそのパケットを転送する、スタンドアロン型システムである。例えば、セキュリティアプライアンス１０２を用いて、広域ネットワーク（ＷＡＮ）上で受信するパケットに対してセキュリティ処理を実行した後に、そのパケットをローカルエリアネットワーク（ＬＡＮ）に転送することができる。ネットワークサービスプロセッサ１００は、本発明の原理による全てのパケット処理タスクの速度を高めるために、ハードウェアパケット処理、バッファリング、ワークスケジューリング、順序づけ、同期化、およびコヒーレンスサポートを有する。
【００１７】
ネットワークサービスプロセッサ１００は、受信されたパケットにカプセル化されている開放型システム間相互接続ネットワークのＬ２からＬ７層までのプロトコルを処理する。当業者には周知であるように、開放型システム間相互接続（ＯＳＩ）参照モデルは、７つのネットワークプロトコル層（Ｌ１〜Ｌ７）を規定している。物理層（Ｌ１）は、装置を伝送媒体に接続する実際の電気的および物理的インタフェースを表す。データリンク層（Ｌ２）は、データのフレーミングを実行する。ネットワーク層（Ｌ３）は、データをパケットにフォーマットする。トランスポート層（Ｌ４）は、エンド・ツー・エンド転送を取り扱う。セッション層（Ｌ５）は、装置間の通信、例えば、通信が半二重であるか、全二重であるかを管理する。プレゼンテーション層（Ｌ６）は、データの形式および表現、例えば、構文、制御コード、特殊なグラフィクスおよび文字セットを管理する。アプリケーション層（Ｌ７）は、ユーザ間の通信、例えば、ファイル転送および電子メールを許容する。
【００１８】
ネットワークサービスプロセッサは、例えばＬ４からＬ７までの上位のネットワークプロトコルに対するワーク（パケット処理操作）をスケジューリングしてキューイングする（待ち行列に入れる）。特定のパケットに実行されるパケット処理（ワーク）は、複数のパケット処理操作（ひとまとまりのワーク）を含む。各ひとまとまりのワークは、それぞれに関連するタグを有する。タグは、ワークの実行が順序づけられかつ同期化されることを保証しながら、ネットワークサービスプロセッサにおける複数のプロセッサコアによってワークが並行してスケジューリングされることを可能にする。ワークのキューイングおよびスケジューリングによって、受信されるパケット内の上位ネットワークプロトコルの処理は、パケットをワイヤスピードで送出するように実行される。ワイヤスピードは、データが送受信されるネットワークのデータ転送速度である。パケットをワイヤスピードで送出するようにプロトコルを処理するので、ネットワークサービスプロセッサはネットワークのデータ転送速度を低下させない。
【００１９】
ネットワークサービスプロセッサ１００は、オフチップＰＨＹ１０４ａ、１０４ｂへの標準縮小ギガバイト・メディア独立型インタフェース（ＲＧＭII）接続を用いた複数のイーサネット（登録商標）媒体アクセス制御インタフェースを有する。
【００２０】
ネットワークサービスプロセッサ１００は、イーサネット（登録商標）・ポート（Ｇｉｇ Ｅ）から物理インタフェースＰＨＹ１０４ａ、１０４ｂを介してパケットを受信し、受信されたパケットに対してＬ７〜Ｌ２ネットワークプロトコル処理を実行し、処理されたパケットを、物理インタフェース１０４ａ、１０４ｂを介してネットワーク内の別のホップもしくは最終的な宛先へ転送するか、またはホストプロセッサによるさらなる処理のためにＰＣＩバス１０６を介して転送する。ネットワークプロトコル処理には、ファイアウォール、アプリケーションファイアウォール、ＩＰセキュリティ（ＩＰＳｅｃ）および／またはセキュアソケットレイヤ（ＳＳＬ）を含む仮想プライベートネットワーク（ＶＰＮ）、侵入検知システム（ＩＤＳ）およびアンチウィルス（ＡＶ）などのネットワークセキュリティプロトコルの処理が含まれてもよい。
【００２１】
ネットワークサービスプロセッサ１００内のＤＲＡＭコントローラは、ネットワークサービスプロセッサ１００に結合される外部のダイナミックランダムアクセスメモリ（ＤＲＡＭ）１０８へのアクセスを制御する。ＤＲＡＭ１０８は、ＰＨＹインタフェース１０４ａ、１０４ｂまたは周辺装置相互接続拡張（ＰＣＩ−Ｘ）インタフェース１０６から受信されるデータパケットを、ネットワークサービスプロセッサ１００によって処理するために格納する。一実施形態においては、ＤＲＡＭインタフェースは、８００ＭＨｚまで動作可能な６４または１２８ビットダブルデータレートII同期ダイナミックランダムアクセスメモリ（ＤＤＲIIＳＤＲＡＭ）をサポートする。
【００２２】
ブートバス１１０が必要なブートコードを供給する。このブートコードは、フラッシュメモリ１１２に格納されており、ネットワークサービスプロセッサ１００がオンにされると、またはリセットされると、ネットワークサービスプロセッサ１００によって実行される。ブートバス１１０上では、コンパクトフラッシュ（登録商標）規格を実装するデバイス１１４から、またはＰＣＩバスを介して取り付けられるディスクの場合もある別の高容量デバイスからネットワークサービスプロセッサ１００にアプリケーションコードがロードされてもよい。
【００２３】
様々なＩ／Ｏインタフェース（miscellaneous I/O interface）１１６が、汎用入力／出力（ＧＰＩＯ）、フラッシュ、ＩＥＥＥ８０２の２線式管理インタフェース（ＭＤＩＯ）、汎用非同期送受信器（ＵＡＲＴ）およびシリアルインタフェースなどの補助インタフェースを提供する。
【００２４】
ネットワークサービスプロセッサ１００は、低遅延ＤＲＡＭ１１８を制御する別のメモリコントローラを有する。低遅延ＤＲＡＭ１１８は、侵入検知システム（ＩＤＳ）またはアンチウィルス（ＡＶ）アプリケーションに必要とされる場合のある文字列一致を含む高速検索を可能にするインターネットサービス／セキュリティアプリケーションに使用される。
【００２５】
図２は、図１に示すネットワークサービスプロセッサ１００のブロック図である。ネットワークサービスプロセッサ１００は、複数のプロセッサコア２０２を使用して高いアプリケーション性能を提供する。ネットワークアプリケーションは、データプレーン（実データを転送するための伝送ネットワーク）操作とコントロールプレーン（実データの転送制御を行うための制御ネットワーク）操作とに分類することができる。各コア２０２は、データプレーン操作またはコントロールプレーン操作を専門に行うことができる。データプレーン操作は、パケット転送のためのパケット操作を含む。コントロールプレーン操作は、インターネットプロトコルセキュリティ（ＩＰＳｅｃ）、通信制御プロトコル（ＴＣＰ）およびセキュアソケットレイヤ（ＳＳＬ）などの複雑な上位層プロトコルの一部を処理することを含む。データプレーン操作は、これらの複雑な上位層プロトコルの他の部分の処理を含んでもよい。
【００２６】
パケット入力ユニット２１４は、各パケットにワーク待ち行列エントリを割り当て、生成する。このワーク待ち行列エントリは、Ｌ２キャッシュ２１２またはＤＲＡＭ１０８（図１）に格納されているバッファリングされたパケットを指すポインタを含む。ワーク待ち行列エントリについては、図４に関連して後述する。
【００２７】
パケットの入力／出力処理は、インタフェースユニット２１０ａ、２１０ｂ、パケット入力ユニット（パケット入力）２１４およびパケット出力ユニット（ＰＫＯ）２１８によって実行される。入力コントローラおよびインタフェースユニット２１０ａ、２１０ｂは、コア２０２をオフロード（負荷軽減）するために、受信したパケットの全解析を行って結果チェックを実行する。
【００２８】
パケットは、ＳＰＩ−４．２またはＲＧＭIIインタフェースを介して、インタフェースユニット２１０ａ、２１０ｂのいずれかによって受信される。パケットは、ＰＣＩインタフェース２２４によって受信されることもできる。インタフェースユニット２１０ａ、２１０ｂは、受信されたパケットに含まれるＬ２ネットワークプロトコルヘッダ内の様々なフィールドをチェックすることによって受信されたパケットのＬ２ネットワークプロトコル前処理を実行する。インタフェースユニット２１０ａ、２１０ｂによってＬ２ネットワークプロトコル処理が実行された後、パケットはパケット入力ユニット２１４に転送される。パケット入力ユニット２１４は、受信されたパケットに含まれるＬ３およびＬ４ネットワークプロトコルヘッダの前処理を実行する。前処理には、通信制御プロトコル（ＴＣＰ）／ユーザデータグラムプロトコル（ＵＤＰ）（Ｌ３ネットワークプロトコル）に関するチェックサムチェックが含まれる。
【００２９】
パケット入力ユニット２１４は、レベル２キャッシュ２１２またはＤＲＡＭ１０８内のバッファにパケットデータを書き込む。このパケットデータは、上位層のネットワークプロトコルによるその後の処理のために、プロセッサコア２０２のうちの少なくとも１つで実行される上位層ソフトウェアに好都合のフォーマットで書き込まれる。パケット入力ユニット２１４はプログラマブルバッファサイズをサポートし、かつ複数のバッファに渡ってパケットデータを分散させて大きいパケット入力サイズをサポートすることができる。
【００３０】
パケット順序／ワーク（ＰＯＷ）モジュール（ユニット）２２８は、プロセッサコア２０２に対するワーク（パケット処理操作）をキューイングして（待ち行列に入れて）スケジューリングする。ワークは、コアによって実行される任意のタスクであると定義付けされる。このコアは、ワーク待ち行列のエントリによって特定されるものである。タスクはパケット処理操作を含んでもよく、例えば、ワーク待ち行列のワーク待ち行列エントリによって特定される受信パケットに対して実行されるべきＬ４層からＬ７層までのパケット処理操作を含んでもよい。個々のパケット処理操作は、メモリに格納されている受信パケットに対してコアによって実行されるべきひとまとまりのワークである。例えば、ワークは、受信したファイアウォール／仮想プライベートネットワーク（ＶＰＮ）パケットの処理であってもよい。ファイアウォール／ＶＰＮパケットの処理は、次のような個別のパケット処理操作（ひとまとまりのワーク）、すなわち、（１）受信したパケットのフラグメントを順序どおりに並べるためのデフラグメント、（２）ＩＰＳｅｃ復号化、（３）ＩＰＳｅｃ暗号化、および（４）パケット転送に先立つネットワークアドレス変換（ＮＡＴ）またはＴＣＰシーケンス番号調整、を含む。
【００３１】
パケット処理操作の中には順序づけを必要とするものがあり、かつ他のパケット処理操作は順序づけおよび同期化の両方を必要とするため、各ひとまとまりのワークには、実行されるべき処理のタイプを規定するタグが関連付けられている。
【００３２】
ＰＯＷモジュール２２８は、コア２０２に対してワークを選択（すなわち、スケジューリング）し、そのワークを記述するワーク待ち行列エントリを指すポインタをコア２０２に返す。各ひとまとまりのワーク（パケット処理操作）は、関連するグループ識別子およびタグを有する。
【００３３】
タグは、コアによって、スケジューリングされたワークを順序づけかつ同期化するために使用される。タグは、タグ値とタグタイプとを含む。タグ値によって、同一フローのワーク（発信元から宛先までが同一）は順序づけられかつ同期化される。タグタイプは、ワークを同期化しかつ順序づける方法を選択する。異なる３つのタグタイプが存在する。これらタイプには、順序づけ（順序づけが保証される）、アトミック（順序づけおよびアトミック性が保証される）およびヌル（順序づけが保証されない）がある。コアは、他のコアが同時に同一データ構造にアクセスすることができない場合には、「アトミックに」データ構造にアクセスする（すなわち、「アトミックの」タグを有する）。これより、アトミック性は、最大１つのコアが所与のタグを有することを保証する。ワークに関連づけられる最初のタグは、ワークの生成者に依存する。このタグは、コアによって開始されるタグスイッチ操作によって変更されることができる。
【００３４】
例えば、ファイアウォール／仮想プライベートネットワーク（ＶＰＮ）パケットを処理する場合、処理ステージによっては、順序づけのみを必要とするものもあれば、順序づけおよび同期化の両方を必要とするものもある。順序づけのタグタイプは、同一フローのフラグメントが順序づけられるように、デフラグメントステージの間に使用されることができる。アトミックのタグタイプは、同一ＩＰＳｅｃトンネルを使用するパケット間に同期化を提供するようにＩＰＳｅｃ処理の間に使用されることができる。これより、コアによるパケットのデフラグメント処理の完了後、コアは、パケットにＩＰＳｅｃ処理を実行する前に、次のパケット処理操作（ＩＰＳｅｃ復号化）に対するワークのタグタイプをアトミックに切り換えるタグスイッチ操作を開始する。タグスイッチ操作が完了すると、ＩＰＳｅｃ処理が同一コアまたは異なるコアによって実行されてもよい。
【００３５】
グループ識別子は、ワークを最初にスケジューリングすることができる１つまたは複数のコアを選択するために使用される。全てのワークが等しいわけではないため、グループ識別子によって異なるワークが異なるコアで実行される。例えば、コアがワークを受け入れるグループを規定することによって、１つのコアグループから別のコアグループにパケット処理がパイプライン化されてもよい。ワークを１つのコアグループから別のコアグループに移すために、または多大な同期遅延を必要とするワークにコアが費やされてしまうことを回避するために、スケジューリングされているワークをコアがスケジューリングから外すことができる。コアがタグタイプをヌルに変更するタグスイッチ操作を開始することによって、ワークはスケジューリングから外される。ワークをスケジューリングし直す場合には、スケジューリングから外されたワークがスケジューリングし直されるべきコアを選択するために、ＰＯＷモジュールによってグループ識別子が使用される。
【００３６】
ＰＯＷモジュールの操作をさらに詳述する前に、コア内の他のモジュールについて説明する。コア２０２によってパケットが処理された後、パケット出力ユニット（ＰＫＯ）２１８はＬ２キャッシュまたはＤＲＡＭからパケットデータを読み出し、Ｌ４ネットワークプロトコル後処理を実行し（例えば、ＴＣＰ／ＵＤＰチェックサムを生成し）、インタフェースユニット２１０ａ、２１０ｂを介してパケットを転送し、パケットの格納に使用されたＬ２キャッシュ２１２またはＤＲＡＭ１０８のロケーションを開放する。
【００３７】
ネットワークサービスプロセッサ１００は、ネットワークサービスプロセッサが高スループットを達成するように、コア２０２をオフロード（負荷軽減）する特定用途向けコプロセッサを有することができる。特定用途向けコプロセッサには、決定性有限オートマトン（ＤＦＡ）を実行するＤＦＡコプロセッサ２４４ならびに圧縮および解凍を実行する圧縮／解凍コプロセッサ２０８が含まれる。
【００３８】
各プロセッサコア２０２は、命令キャッシュ２０６と、レベル１データキャッシュ２０４と、暗号化アルゴリズム用の内蔵式ハードウェアアクセラレーション（暗号アクセラレーションモジュール）２００とを備え、低遅延メモリバス２３０上で低遅延メモリへの直接アクセスを有する、命令同時発行のスーパースカラープロセッサである。Ｌ２キャッシュメモリ２１２を迂回する低遅延メモリ１１８への低遅延直接アクセス経路は、コア２０２およびＤＦＡコプロセッサ２４４の両方から直接アクセスされることができる。
【００３９】
ネットワークサービスプロセッサ１００は、メモリサブシステムも有する。メモリサブシステムには、各コア２０２内のレベル１データキャッシュメモリ２０４、各コア２０２内の命令キャッシュ２０６、レベル２キャッシュメモリ２１２、外部ＤＲＡＭメモリ用のＤＲＡＭコントローラ２１６および外部低遅延メモリへのインタフェース２３０が含まれる。
【００４０】
メモリサブシステムはマルチコアをサポートするように設計され、メモリ集約的コンテンツネットワーキングアプリケーションに必要とされる高スループットおよび低遅延の両方を提供するように調整される。Ｌ２キャッシュメモリ２１２および外部ＤＲＡＭメモリ１０８（図１）は、コア２０２およびＩ／Ｏコプロセッサデバイスの全てによって共有される。
【００４１】
各コア２０２は、コヒーレントメモリバス２３４によってＬ２キャッシュに結合される。コヒーレントメモリバス２３４は、コア２０２、Ｉ／Ｏブリッジ（ＩＯＢ）２３２およびレベル２キャッシュコントローラ２１２間の全てのメモリおよびＩ／Ｏトランザクションのための通信チャネルである。
【００４２】
フリープールのアロケータ（ＦＰＡ）２３６が、レベル２キャッシュメモリ２１２およびＤＲＡＭにおける空きメモリへのポインタのプールを保持する。各空きポインタプールには、帯域幅効率的（後入れ先出し（ＬＩＦＯ））スタックが実装される。ポインタプールが大きすぎてフリープールのアロケータ（ＦＰＡ）２３６に適合しなければ、フリープールのアロケータ（ＦＰＡ）２３６は、追加のポインタを格納するために、ポインタプール内の開放されたメモリを使用してＬ２キャッシュ２１２またはＤＲＡＭ内にツリー／リスト構造を構築する。
【００４３】
Ｉ／Ｏブリッジ（ＩＯＢ）２３２は、全体のプロトコルおよびアービトレーション（調停）を管理し、コヒーレントなＩ／Ｏ区分化（partitioning）を提供する。ＩＯＢ２３２は、ブリッジ２３８と、フェッチ・アンド・アッドユニット（ＦＡＵ）２４０とを有する。ブリッジ２３８は、Ｉ／Ｏバス、コヒーレントメモリバス、パケット入力ユニット２１４およびパケット出力ユニット２１８間で転送されるべき情報を格納するためのバッファ待ち行列を含む。
【００４４】
フェッチ・アンド・アッド・ユニット（ＦＡＵ）２４０は、読み出し、書き込み、アトミックなフェッチ・アンド・アッドおよびアトミックな更新の各操作をサポートする２ＫＢのレジスタファイルである。フェッチ・アンド・アッドユニット（ＦＡＵ）２４０は、コア２０２およびパケット出力ユニット２１８の両方からアクセスされることができる。これらのレジスタは使用頻度の高い値を格納し、これによってこれらの値にアクセスするトラフィックを低減させる。ＦＡＵ２４０内のレジスタは、パケット出力ユニット２１８を介して処理されたパケットを転送するために使用される出力待ち行列の長さを保持するのに使用される。
【００４５】
ＰＣＩインタフェースコントローラ２２４は、プロセッサコア２０２がデータをネットワークサービスプロセッサ内のローカルメモリとリモート（ＰＣＩ）メモリとの間で双方向に非同期的に移動させることを可能にするＤＭＡエンジンを有する。
【００４６】
図３は、図２に示すネットワークサービスプロセッサにおける入力／出力パケット処理を実行するためのユニットをさらに詳しく示すブロック図である。
【００４７】
図１および図２に関連して既に述べたように、パケットは、インタフェースユニット２１０ａ、２１０ｂのいずれか一方、またはＰＣＩインタフェース２２４を介して受信される。インタフェースユニット２１０ａ、２１０ｂおよびパケット入力ユニット２１４は受信したパケットの解析を実行し、コア２０２をオフロードするために解析の結果をチェックする。インタフェースユニット２１０ａ、２１０ｂは、受信したパケットに含まれるＬ２ネットワークプロトコルトレーラを一般的な例外に関してチェックする。例えば、Ｌ２ネットワークプロトコルトレーラ内のフレームチェックシーケンス（ＦＣＳ）フィールドは、パケットの送信者によって実行されたフレームのビットに関するＣＲＣ計算結果を格納している。インタフェースユニット２１０ａ、２１０ｂは、受信したパケットについて同一のＣＲＣ計算を実行し、その結果をＦＣＳフィールドに格納されている値と比較する。インタフェースユニット２１０ａ、２１０ｂは、エラーが検出された場合にそのパケットを受け入れなくてもよく、すなわち、そのパケットは廃棄される。インタフェースユニット２１０ａ、２１０ｂがパケットを受け入れた場合、フリープールのアロケータ（ＦＰＡ）２３６はそのパケットにＬ２キャッシュメモリまたはＤＲＡＭ内のメモリを割り当て、パケットはメモリに格納される。
【００４８】
パケット入力ユニット２１４は、パケット入力処理（ＰＩＰ）ユニット３０２と、入力パケットデータ（ＩＰＤ）ユニット３００とを有する。パケット入力ユニット２１４は、ＦＰＡ２３６内のポインタプールのうちの１つを使用して、受信したパケットデータをレベル２キャッシュメモリまたはＤＲＡＭ内に格納し、別のポインタプールを使用してワーク待ち行列エントリを割り当てる。ワーク待ち行列エントリについては、図４に関連して後述する。
【００４９】
Ｉ／Ｏバスには、到着用バス（ＩＯＢＩ）および発信用バス（ＩＯＢＯ）、パケット出力バス（ＰＯＢ）、ＰＫＯ指定バス（ＰＫＯＢ）、入力パケットデータバス（ＩＰＤＢ）および関連する制御バスが含まれる。インタフェースユニット２１０ａ、２１０ｂは、受信したパケットからの６４ビットのパケットセグメントをＩＯＢＩバスに置く。パケット入力ユニット２１４内のＩＰＤ３００は、ＩＯＢＩバスからの各６４ビットパケットセグメントを処理のためにラッチする。ＩＰＤ３００は、６４ビットパケットセグメントを１２８バイトのキャッシュブロックに蓄積する。ＩＰＤ３００は次に、このキャッシュブロックライトをＩＰＤＢバスに送出する。Ｉ／Ｏブリッジ２３２は、キャッシュブロックライトをコヒーレントメモリバス（ＣＭＢ）に送出する。
【００５０】
パケット入力ユニット２１４は、受信したパケットに含まれるＬ３およびＬ４ネットワークプロトコルヘッダの前処理を実行する。例えば、ＩＰヘッダのＬ３ネットワークプロトコル前処理は、ＩＰバージョンフィールドをチェックしてそのＩＰバージョンがバージョン４であるかバージョン６であるかを判断することと、有効期間（ＴＴＬ）フィールドに格納されている値がゼロよりも大きいことを検証することと、オプションフィールドをチェックすることとを含む。パケット入力ユニット２１４は、インターネットプロトコルバージョン４（ＩＰｖ４）およびインターネットプロトコルバージョン６（ＩＰｖ６）のトラフィックをサポートする。ＴＣＰ／ＵＤＰヘッダのＬ４前処理は、ポート番号フィールド、チェックサムフィールド、長さフィールドおよびフラグフィールドを検証することを含む。パケット入力ユニット２１４はまた、Ｌ３およびＬ４ネットワークプロトコルヘッダ内のフィールドに格納されている値をコアによる後の処理のために抽出する。
【００５１】
パケット順序／ワーク（ＰＯＷ）ユニット２２８は、コアのためにワークをキューイングして（待ち行列に入れて）スケジューリングするハードウェアワークキューイング、ハードウェアワークスケジューリングならびにタグベースの同期化および順序づけを実装する。ワーク待ち行列には、パケットが到着するごとにパケット入力ユニット２１４によってワーク待ち行列エントリが追加される。ワーク待ち行列エントリは、コアによって実行されるべきワークを記述するプライマリディスクリプタであり、これについては図４に関連して後述する。ワーク待ち行列エントリは、ＰＩＰ／ＩＰＤモジュール２１４またはコア２０２によって生成されてもよい。ＰＩＰ／ＩＰＤモジュール２１４は、パケットが到着する度にパケット順序／ワーク（ＰＯＷ）ユニット２２８にワークを提出する。
【００５２】
Ｌ２キャッシュ／ＤＲＡＭに格納されているワーク待ち行列エントリによって特定されるワークは、複数のＰＯＷ入力待ち行列のうちの１つを介してパケット順序／ワーク（ＰＯＷ）ユニット２２８に入る。一実施形態においては、ＰＯＷ入力待ち行列は８個存在し、ＰＯＷモジュールは２０４８個のＰＯＷエントリを含む。ＰＯＷエントリについては、図５に関連して後述する。ＰＯＷモジュール２２８は、ＰＯＷエントリを使用して、ワーク待ち行列エントリによって特定されるワークを順序づけ、スケジューリングしかつ同期化する。ＰＯＷモジュール２２８は、ＰＯＷエントリにおけるワーク待ち行列エントリを指すポインタを格納し、コアからのワーク要求に応答して、ワーク待ち行列エントリを指すポインタをコアに提供する。
【００５３】
異なるサービスレベルを提供するために、異なるＰＯＷ入力待ち行列を使用することができる。パケット入力処理（ＰＩＰ）ユニット３０２が、デフォルト値、仮想ローカルエリアネットワーク（ＶＬＡＮ）優先順位およびポートごとに設定可能なＩＰディフサーブ値を使用して、パケットをＰＯＷ２２８内の８個の入力ワーク待ち行列のうちの１つに分類することができる。
【００５４】
タイマユニット２４２が、コアのワークをスケジューリングするために使用される。タイマユニットは、レベル２キャッシュメモリ２１２またはＤＲＡＭ１０８（図１）に格納されるプログラム可能な数のバケットを有するリングを管理する。各バケットは、タイマエントリのリストを格納している。各タイマエントリは、ワーク待ち行列エントリのポインタを格納する。各リング内のバケット間の時間周期はプログラム可能である。バケットの時間周期が終わるごとに、リング内の次のバケットが処理され、バケット内のタイマエントリに格納されているワーク待ち行列エントリのポインタによって特定されるワークがスケジューリングされる。
【００５５】
図４は、Ｌ２キャッシュ２１２またはＤＲＡＭ１０８に格納されることのできるワーク待ち行列エントリ４００を示す。ワーク待ち行列エントリ４００のワード４０２、４０４は、パケット順序／ワーク（ＰＯＷ）モジュール２２８によってコアのワークをスケジューリングするために使用される。
【００５６】
ワード４０２は、メモリ入力待ち行列を実装するために、ハードウェアチェックサムを格納するハードウェアチェックサムフィールド４１２と、次のワーク待ち行列エントリを指すポインタを格納する次ポインタフィールド４１４とを含む。一実施形態においては、ハードウェアチェックサムは、パケットに渡って計算される、ハードウェアにより生成されたパケットデータ補完合計の１６ビットチェックサムである。次ポインタフィールド４１４は、ワーク待ち行列エントリをリンクするために使用される。
【００５７】
ワード４０４は、長さフィールド４１６、入力ポート（ｉｐｒｔ）フィールド４１８、ＱＯＳフィールド４２０、グループ（Ｇｒｐ）フィールド４２２、ＴＴフィールド４２４、およびタグフィールド４２６を含む。長さフィールド４１６は、ワーク待ち行列エントリ４００のパケットデータの合計バイト数を格納する。一実施形態においては、その長さは１から６５５３５バイトまでの範囲であってもよい。入力ポートフィールド４１８は、パケットが到着した入力ポートを格納する。ＱＯＳフィールド４２０は、パケット入力ユニット２１４によって選択されるＰＯＷモジュール２２８内の入力待ち行列を格納する。パケット入力ユニット２１４は、ポートごとのデフォルト値または受信したパケット内のフィールドに基づいて（例えばＶＬＡＮ ＩＤもしくはディフサーブＤＳＣＰフィールドに基づいて）、入力待ち行列を選択することができる。グループフィールド４２２は、ワークのコアグループ番号を格納する。ＴＴフィールド４２４は、ワーク待ち行列エントリの最初のタグタイプを格納する。タグタイプは、ヌル、順序づけ、またはアトミックであってもよい。タグタイプは、ＩＰおよび非ＩＰパケット、ＩＰｖ４およびＩＰｖ６パケット、ならびにＴＣＰおよび非ＴＣＰパケットに対して異なってもよい。最初のタグ値はＩＰＤユニット３００によって割り当てられ、パケットが到着したポート番号、ＩＰ発信元／宛先アドレス、ＩＰプロトコルの次ヘッダ値およびＴＣＰ／ＵＤＰ発信元／宛先ポートに基づいてもよい。ＰＯＷモジュール２２８は、ＱＯＳフィールドの値を読み出して入力待ち行列を選択する。ＰＯＷモジュール２２８はまた、ワークを入力待ち行列に追加する際にグループフィールド、ＴＴフィールドおよびタグフィールドの値を読み込む。
【００５８】
ワーク待ち行列エントリのワード４０４内のタグフィールド４２６によって、各ひとまとまりのワークがタグ付けされる。ＰＩＰ／ＩＰＤモジュール２１４は、最初のタグ情報を生成し、これをワーク待ち行列エントリに格納する。例えば、ＰＩＰ／ＩＰＤモジュールは、「フロー」を定義する標準のＴＣＰの５タプル（5-tuple）（発信元ＩＰアドレス、宛先ＩＰアドレス、ＩＰプロトコル、ＴＣＰ発信元ポート、ＴＣＰ宛先ポート）のハッシュを実行することによって、タグを生成することができる。パケット順序／ワーク（ＰＯＷ）ユニット２２８は、この最初のタグ情報を用いて、同期化、順序づけおよびスケジューリングを行う。ひとまとまりのワークの２つがワード４０４のタグフィールド４２６に格納されている同一のタグ値およびＴＴフィールド４２４に格納されているタグタイプを共有している場合、これらは順序づけられかつ／または同期化される。ひとまとまりのワークの２つが異なるタグすなわちタグタイプ値を有する場合には、これらは関係のないものであるとされてもよく、異なるコアで完全に並行して実行されることができる。同一のフローは同一のタグ値を有するため、順序づけられかつ同期化される。異なるフローは異なるタグ値を有すると思われるため、順序づけおよび同期化は行われない可能性が高く、異なるコア上で完全に並行して実行されることができる。
【００５９】
ワード４０６は、パケットデータに関する情報、例えば、入力パケットの処理中にパケットヘッダから抽出される情報を格納する。この情報は、Ｌ２プロトコルヘッダに仮想ＬＡＮ識別子が発見されたか否か、このパケットはＵＤＰであるかＴＣＰであるか、Ｌ２ヘッダ内の宛先ＭＡＣアドレスフィールドはブロードキャストであるかマルチキャストであるか、およびこのパケットはＩＰＳｅｃ復号化を必要とするか否か、に関する表示を含むことができる。この情報はまた、パケットデータの格納に使用されるバッファの数も含む。
【００６０】
ワード４０８は、バッファ記述子である。アドレスフィールド４３６は、バッファ内のパケットデータの最初のバイトのアドレスを格納する。サイズフィールド４３４は、バッファ内に格納されるパケットデータのバイト数を格納する。一実施形態においては、プールフィールド４３２およびＩフィールド４２８が「０」に設定され、バックフィールド４３０は、アドレスフィールド４３６に格納されたアドレスからバッファの先頭までのキャッシュブロックの数を格納する。
【００６１】
ワード４１０は、パケットのタイプに依存したパケットデータを格納する。待ち行列エントリに格納されるパケットデータのフォーマットは、本発明の範囲外である。
【００６２】
ＰＯＷモジュール２２８は、ＰＯＷ入力待ち行列を含む様々なリストに存在する複数のＰＯＷエントリを有する。典型的には、各ＰＯＷエントリは、Ｌ２キャッシュ／ＤＲＡＭに格納されるワーク待ち行列エントリを指すポインタを含む。ワーク待ち行列エントリは、ＰＯＷ入力待ち行列を拡張するために使用されてもよい。
【００６３】
図５は、ＰＯＷエントリ５００を示す。ＰＯＷエントリ５００は、ワーク待ち行列ポインタ（ＷＱＰ）５０２を格納する。一実施形態においては、ＷＱＰは、ワーク待ち行列エントリ４００を指す、Ｌ２キャッシュ２１２またはＤＲＡＭ２０８内に揃えられた６４ビットポインタである。
【００６４】
ＰＯＷエントリ５００はまた、関連のワーク待ち行列エントリ４００によって記述されるワークに割り当てられる現タグ値５０４およびタグタイプ５０６、ワークに関連づけられる１つまたは複数の現グループ５０８、ならびにＰＯＷエントリ５００をＰＯＷモジュール２２８内の様々なリストにリンクするために使用される他のポインタ５１０も格納する。
【００６５】
ＰＯＷモジュール２２８は、タグ値およびタグタイプを使用して、スケジューリングされるワークを順序づける。タグ値によって、同一のフロー（発信元から宛先まで）のワークが順序づけられかつ同期化される。例えば、タグ値は、「フロー」を定義するデータパケットのヘッダにおける標準のＴＣＰ５タプル（発信元ＩＰアドレス、宛先ＩＰアドレス、ＩＰプロトコル、ＴＣＰ発信元ポート、ＴＣＰ宛先ポート）のハッシュであってもよい。同一のフローは同一のタグ値を有するため、順序づけられかつ同期化される。異なるフローは異なるタグ値を有すると思われるため、順序づけおよび同期化は行われず、異なるコア上で完全に並行して実行されることができる。一実施形態においては、タグ値は３２ビット値である。タグタイプ５０６は、実行される順序づけおよび同期化のタイプを特定する。
【００６６】
一実施形態においては、ＰＯＷエントリ５００によって特定される各ひとまとまりのワークにヌル、順序づけまたはアトミックの３つのタグタイプのうちの１つが割り当てられる。タグタイプがヌルの場合、順序づけは保証されない。順序づけのタグタイプを有するワークには、順序づけが保証される。アトミックのタグタイプを有するワークには、順序づけとアトミック性が保証される。アトミックのタグ識別子を有するひとまとまりのワークの２つが同一タグ値を同時に保有することはできない。
【００６７】
異なるタイプのワークが同一のＰＯＷモジュール２２８を使用する。全てのワークが同一ではないため、ＰＯＷは複数のグループをサポートする。一実施形態においては、ＰＯＷモジュールは１６の異なるグループをサポートする。全てのコアが同一のＰＯＷモジュール２２８を共用するとしても、異なるコアで異なる機能を実行する手段をグループが提供する。例えば、コアが受け入れるワークのグループを定義することによって、第１のグループがワークの最初のステージを実行しかつ次のグループがワークの次のステージを実行して、１つのコアグループから別のコアグループにパケット処理がパイプライン化されてもよい。グループは、各コアが受け入れるワークのタイプを指定することを可能にし、ＰＯＷモジュール２２８はワークを利用可能なコアに動的に分配することができる。
【００６８】
プロセッサコア２０２は、ＰＯＷモジュール２２８にワークを要求する。典型的には、コアは、ワークを見つけるためにＰＯＷモジュールをポーリングする。しかし、場合によっては、ＰＯＷモジュール２２８が、コアに提供するワークを有していればそのコアに割り込むように選択されてもよい。ＰＯＷモジュール２２８は、コアがワークを受け入れるグループに基づいて、コアにワークを選択、すなわち、スケジューリングする。ＰＯＷモジュール２２８は、コアごとにＰＯＷコアグループマスクレジスタを有する。各グループマスクレジスタは、１グループにつき１ビットを有するビットマスクとして実装され、コアがワークを受け入れるグループの組合せを指定することが可能である。
【００６９】
ワークのグループをコアが受け入れなければ、ＰＯＷモジュール２２８はコアにひとまとまりのワークをスケジューリングしない。コアのグループマスクレジスタにおける値ゼロは、コアが任意の新しいワークを受信することを防止する。１６グループを有する実施形態では、グループマスクレジスタは、マスクレジスタ内に１グループにつき１ビット、計１６のマスクビットを有する。ビット位置における「１」が、対応するグループにおけるそのコアの帰属を設定する。
【００７０】
図６は、ＰＯＷモジュール２２８を流れるワークの状態を示す。ワークは、複数の入力待ち行列６０４のうちの１つを介してＰＯＷモジュール２２８に入り、Ｌ２キャッシュ／ＤＲＡＭまたはＰＯＷモジュールに格納されることができるＰＯＷエントリ５００によって特定される。ワークは、コアからのＧＥＴ＿ＷＯＲＫ要求に応答して、入力待ち行列６０４内のＰＯＷエントリのリスト６０６からＰＯＷモジュールによってスケジューリングされる。
【００７１】
ＰＯＷモジュール内のＰＯＷエントリを入力待ち行列６０４から処理中待ち行列に移動させることによって、ワークがスケジューリングされる。処理中待ち行列は、ＰＯＷエントリ５００に格納されているタグ値およびタグタイプに基づいて選択される。１６個のコアが存在する場合、１６のＰＯＷエントリによって特定されるワークは、１つのコアにつき１つのワークを並行してスケジューリングされることができる。ＰＯＷによって最初にワークが処理中待ち行列にスケジューリングされた後、スケジューリングされたワーク６０８は、コアがタグスイッチ操作を実行することによって処理中待ち行列間を移動されてもよい。
【００７２】
スケジューリングされたワークは、コアによってスケジューリングから外されてもよい。スケジューリングから外されたワーク６１０は、処理中の状態のままであり、後にＰＯＷモジュールによってコアの１つにスケジューリングし直される。スケジューリングされていない（ＰＯＷモジュールからみてスケジューリングされていない）ワークは、タグスイッチ６１２がタグタイプをヌルから順序づけまたはアトミックに変更することで、コアによってスケジューリングされてもよい。
【００７３】
図７Ａおよび図７Ｂは、ＰＯＷモジュール２２８における様々なリスト内のＰＯＷエントリ５００を示す本来１つのブロック図を構成するもので、図７Ａは左側部分、図７Ｂは右側部分の図である。ＰＯＷエントリ５００は、入力待ち行列７０４ａ〜７０４ｃ、または処理中待ち行列７０６ａ〜７０６ｃに入れられる。ＰＯＷエントリ５００はまた、空きリスト７０２であっても、コア２０２に関連づけられてもよい。
【００７４】
ワークは、入力待ち行列７０４ａ〜７０４ｃを介してＰＯＷモジュールに入る。図示の実施形態では、３つの入力待ち行列７０４ａ〜７０４ｃが示されている。各入力待ち行列７０４ａ〜７０４ｃは、ＰＯＷエントリのリストを指す、入力のヘッドおよびテールのポインタ７１２と、ＰＯＷモジュール２２８の外部にあるメモリ７１０に格納されたワーク待ち行列エントリ７０８のリストを指す入力待ち行列メモリのヘッドおよびテールのポインタ７１４とを含む。
【００７５】
ＰＯＷエントリ５００の数は制限されるが、ＰＯＷモジュール２２８はワーク待ち行列を無数に有するように見える。空きリスト７０２からＰＯＷエントリ５００を入手することができなければ、ＰＯＷモジュール２２８は、入力待ち行列メモリのヘッドおよびテールのポインタ（メモリリスト）７１４を介してワーク待ち行列エントリを加えることによって、ワークを入力待ち行列に追加する。ＰＯＷモジュールがワーク待ち行列エントリ７０８を介してワークを追加すれば、ＰＯＷモジュールは、後にＰＯＷエントリ５００が利用可能となり次第、自動的にワークをメモリ７１０からＰＯＷエントリ５００に、ワークが当初入力待ち行列７０４ａ〜７０４ｃに追加された順位以外の順位で移動する。
【００７６】
第１の入力待ち行列７０４ａには２つのＰＯＷエントリ５００が存在し、入力待ち行列のヘッドポインタ７１２は第１の入力待ち行列の先頭にあるＰＯＷエントリを指している。第１の入力待ち行列は、メモリに格納されているワーク待ち行列エントリ７０８によって拡張される。入力待ち行列メモリのヘッドポインタ７１４は、ワーク待ち行列エントリ７０８を指している。第２の入力待ち行列７０４ｂは空であり、すなわち、ＰＯＷエントリは存在しない。第３の入力待ち行列７０４ｃには、ＰＯＷエントリ５００が１つ存在する。
【００７７】
空きリスト７０２内のＰＯＷエントリ５００は、入力待ち行列７０４ａ〜７０４ｃのいずれかに割り当てるために利用可能である。空きリスト７０２のＰＯＷエントリ５００が利用可能な場合、ＰＯＷモジュール２２８は入力待ち行列７０４ａ〜７０４ｃのために空きリスト７０２からそのＰＯＷエントリ５００を割り当て、ワーク待ち行列エントリに関連するタグ値、タグタイプおよびグループを割り当てられたＰＯＷエントリに格納する。ＰＯＷエントリ５００には、メモリ７１０に格納されているワーク待ち行列エントリ７０８を指すポインタ（ＷＱＰ）も格納される。ＰＯＷエントリは、空きリスト７０２に置かれることによって開放される。
【００７８】
コア２０２はＰＯＷモジュール２２８にワークを要求し、ＰＯＷモジュール２２８は、入力待ち行列７０４ａ〜７０４ｃにおけるＰＯＷエントリによって特定されるワークを要求側であるコアにスケジューリングする。コアの１つからワーク要求を受信すると、ＰＯＷモジュールは、入力待ち行列７０４ａ〜７０４ｃのうちの１つにおけるＰＯＷエントリ５００の１つをスケジューリングする。スケジューリングされるＰＯＷエントリ５００は、ＰＯＷエントリ５００のグループフィールド５０８に格納されているグループ識別子と、要求側コアによってサポートされ、コアのコアグループマスクレジスタ７１６によって特定されるグループとに基づく。ＰＯＷエントリは、処理中リスト７０６ａ〜７０６ｃに移動されることによってスケジューリングされる。処理中リストは、ＰＯＷエントリ５００内のタグ値フィールド５０４およびタグタイプフィールド５０６にそれぞれ格納されているタグ値およびタイプ値に基づいて選択される。処理中リスト（待ち行列）７０６ａ〜７０６ｃに存在するＰＯＷエントリによって特定されるワークは、「処理中」ワークと呼ばれる。
【００７９】
ＰＯＷモジュールは、入力待ち行列に異なる優先順位をつけてワークがユニットを滑らかに流れる（滞らずに送出されていく）ように保つ幾つかのサービス品質の特徴を含む。サービス品質の１つの特徴は、個々の入力待ち行列７０４ａ〜７０４ｃによって費やされるＰＯＷエントリの数を制限するしきい値である。入力待ち行列７０４ａ〜７０４ｃはそれぞれ、保持するＰＯＷエントリの最大数を有する。ＰＯＷエントリが最大数に達すると、入力待ち行列７０４ａ〜７０４ｃは、ワーク待ち行列エントリ７０８の使用によって拡張される。空きＰＯＷエントリに、入力待ち行列ごとの最小数も存在する。利用可能なＰＯＷエントリの数がこの最小数よりも小さい間は、入力待ち行列にＰＯＷエントリは割り当てられない。
【００８０】
サービス品質の別の特徴は、入力待ち行列の走査を制御する仕組みである。ＰＯＷモジュールは、コア２０２にスケジューリングする新しいワークを探索する際に、全ての入力待ち行列７０４ａ〜７０４ｃを並行して走査する。探索は、ラウンド式に進む。一実施形態においては、構成されたラウンドフィールドで３２ラウンドが設定されてもよい。この３２ラウンドは、ＰＯＷモジュールが使用するものである。８個の入力待ち行列が存在する実施形態では、構成された各ラウンドは、そのラウンドに参加できる入力待ち行列を表示する８ビットのビットマスクである。入力待ち行列の優先順位は、それが参加することのできるラウンドの数に依存する。例えば、最も高い優先順位の入力待ち行列は３２ラウンドの全てに参加し、最も低い優先順位の入力待ち行列は３２ラウンドのうちの１つに参加する。これより、各待ち行列内にスケジューリング可能なアイテムが存在するものとすれば、優先順位の低い入力待ち行列では１つのアイテムがスケジューリングされるのに対して、最も高い優先順位の待ち行列では３２アイテムがことごとくスケジューリングされる。
【００８１】
ワークをコアにスケジューリングするために、ＰＯＷモジュール２２８はまず、スケジューリング除外リスト６１０におけるスケジューリングを外されたワークをスキャンする。その後、ＰＯＷモジュールは、入力待ち行列のスキャンを現ラウンドにおいて現入力待ち行列から開始する。この現ラウンドに参加する残りの待ち行列が、ワークに対してまず逐次スキャンされる。スキャンは、ラウンド式に循環して行われる。各入力待ち行列は順番にスキャンされ、かつ異なる入力待ち行列がラウンド構成によって示される順序でスキャンされる。入力待ち行列からスケジュール可能なワークを見つけると、ＰＯＷモジュールは、このワークをコアに配信し、タグに応じてこのワークを処理中待ち行列に移動し、次のワーク要求が、スケジュール可能な最後のワークが見つけられた位置の次にくる待ち行列およびラウンドから始まるように、現待ち行列および現ラウンドを更新する。
【００８２】
概念的には、ＰＯＷエントリは処理中待ち行列内に先入れ先出し（ＦＩＦＯ）順に編成され、処理中待ち行列７０６ａ〜７０６ｃはそれぞれ固有のタグ値およびタグタイプ値の組合せに関連づけられている。処理中待ち行列内のＰＯＷエントリは、２つのタグタイプ（アトミックまたは順序づけ）のうちの一方を有する。場合によっては、ＰＯＷモジュールは、ワークがヌルタグタイプへの保留タグスイッチを有する場合、順序づけられたリストからワークを順不同で除去することができる。
【００８３】
任意の所定時間においては、ひとまとまりのワークの１つのみが、特定のコア２０２にスケジューリングされる。これより、スケジューリングされることのできるひとまとまりのワークの数は、コアの数に限定される。一実施形態においては、存在するプロセッサコア２０２は１６個であり、ひとまとまりのワークの１６個をスケジューリングすることが許容される。
【００８４】
ＰＯＷモジュール２２８はコア２０２と組み合わされて、ＰＯＷエントリ５００内に格納されているタグ値およびタグタイプ値を使用して関連するワークを順序づけかつ同期化させ、関連のないワークを順序づけずに同期化しないようにする。これによって、効率的なマルチコア実行が可能になる。ひとまとまりのワークの２つが同一のタグ値およびタグタイプを共有している場合、これらワークは関連があり、よって順序づけられかつ同期化される。ＰＯＷエントリによって特定されるひとまとまりのワークの２つが異なるタグ値またはタグタイプ値を有する場合、これらワークは異なるコア２０２で並行して実行されることができる。
【００８５】
図７Ｂでは、ＦＩＦＯ順で格納されるＰＯＷエントリを有する３つの処理中リスト７０６ａ〜７０６ｃが示されている。ＰＯＷモジュール２２８が入力待ち行列７０４ａ〜７０４ｃからのワークをスケジューリングするか、スケジューリングから外したワークをスケジューリングし直すと、処理中リスト７０６ａ〜７０６ｃにワークが入る。処理中待ち行列７０６ａ〜７０６ｃに格納されるのは、アトミックまたは順序づけのタグタイプを有するＰＯＷエントリのみである。図７Ｂに示す例では、タグ「Ｏ７」を有する、すなわちタグ識別子が７で順序づけのタグタイプ（Ｏ）を有するパケットのＰＯＷエントリが処理中のリスト７０６ａに格納されている。タグＡ５、すなわち、タグ識別子が５でアトミックのタグタイプ（Ａ）を有するパケットのＰＯＷエントリが、処理中リスト７０６ｂ内に存在する。タグＡ７、すなわち、識別子が７でアトミックのタグタイプ（Ａ）を有するパケットのＰＯＷエントリが、処理中リスト７０６ｃに存在する。
【００８６】
入力待ち行列のＰＯＷエントリ５００またはワーク待ち行列エントリ７０８は、ワークに割り当てられた最初のタグ値を格納している。最初のタグ値は、ワークの生成者に依存しており、パケット入力ユニット２１４またはコア２０２によって割り当てられる。ひとまとまりのワークのタグ値５０４およびタグタイプ５０６は、コアによって実行されるタグスイッチ命令で変更されてもよい。
【００８７】
処理中リスト内のＰＯＷエントリによって特定される処理中ワークが異なる処理ステージを進むにつれて、タグおよびタグタイプを変更することにより、コアはタグスイッチを実行することができる。タグスイッチによって、ＰＯＷエントリは１つの処理中待ち行列から別の処理中待ち行列に移動するか、または処理中ワークのスケジューリングから外されるかもしくは完了させられる。タグスイッチについては、図８に関連して後述する。
【００８８】
ＰＯＷモジュールは、タグスイッチにわたって順序を保持する。それぞれが同一のタグ値およびタグタイプ値を有する、同一の一連のタグスイッチを実行する処理中ワークはいずれも、処理中に、各タグスイッチを通じて等しく順序づけられる。以下の条件、すなわち、（１）同一フローからの全てのパケットが、同一の最初のタグ値およびグループを有して同一の入力待ち行列を介してＰＯＷモジュールに入る、および（２）同一フローからのパケットが、非ヌル（順序づけまたはアトミック）のタグスイッチの同一シーケンスで処理される、が真であれば、ＰＯＷモジュールは、全パケットの処理を１つのフローに順序づけることができる。
【００８９】
ＰＯＷモジュール２２８は、ワーク待ち行列エントリ７０８によって特定されるワークを、入力待ち行列７０４ａ〜７０４ｃに、１つの待ち行列当たり順番に維持する。入力待ち行列７０４ａ〜７０４ｃ内のＰＯＷエントリ５００によって特定されるワークは、順不同でスケジューリングされてもよい。ＰＯＷモジュールのスケジューラは、スケジューリング可能なワークの探索に際して、即時スケジューリングが不可能な入力待ち行列７０４ａ〜７０４ｃ内のＰＯＷエントリ５００をスキップする。ＰＯＷモジュールは、順序づけまたはヌルのタグタイプを有するＰＯＷエントリによって特定されるワークをスキップしない。これより、ＰＯＷモジュールは、これらのタグタイプおよび同一グループ識別子を有するワークを入力待ち行列順にスケジューリングする。ＰＯＷモジュールは、アトミックのタグタイプおよび即時スケジューリングが不可能なタグ値を有するＰＯＷエントリによって特定されるワークをスキップし、これより、同一グループを有してタグタイプがアトミックである入力ワーク待ち行列内のＰＯＷエントリによって特定されるワークに対して、タグ順序を保証するのみである。ＰＯＷモジュールは、所望のグループではない、入力ワーク待ち行列内のＰＯＷエントリによって特定されるワークをスキップし、これより、異なるグループ識別子を有する、入力待ち行列エントリ内のＰＯＷエントリ間に順序づけは生じない。
【００９０】
ワークがスケジューリングされた後、ワークは処理中状態となり、順序づけはタグ値およびタグタイプ値に基づいて行われる。スケジューリングされた処理中ワークの順序づけは、そのワークのグループ識別子に依存しない。スケジューリングされたワークは、ＰＯＷモジュールの「処理中」ワークの部分集合である。アトミックまたは順序づけのタグ値を有するワークは、タグスイッチトランザクションの完了後もスケジューリングされたままである。コアは、この処理中ワークをスケジューリングから外すことができ、ＰＯＷモジュールは後にこのワークをスケジューリングし直すことができる。処理中ワークには、コアによってスケジューリングから外されたスケジューリングされるワークも含まれる。スケジューリングから外されたワークは処理中のままであり、後にはスケジューリングし直されるが、現時点ではコアで実行されるものではない。ワークのスケジューリングからの除外は、ワークを１つのコアグループから別のコアグループに転送することによって「ワークパイプライン化」の実装に使用されてもよい。これはまた、大幅な同期遅延を必要とするワークのためにコアを費やすことを回避するため、およびワークを中断できるものにするために使用されてもよい。スケジューリングから外されたワークには、ヌルのタグタイプが割り当てられる。ＰＯＷモジュールは、先にスケジューリングから外されたワークを、入力待ち行列からの新しいワークをスケジューリングするよりも高い優先順位でスケジューリングし直す。
【００９１】
グループ識別子が、スケジューリングから外されている処理中ワークをコアにスケジューリングし直すことのできるコアを判断するために使用される。ＰＯＷモジュールは、異なるタグ値または異なるタグタイプ値を使用する処理中ワークに、順序づけを強要することもなければ、同期化させることもない。この処理中ワークは、制限なく並行して実行される。
【００９２】
ＦＩＦＯ順は、全ての順序づけおよび同期上の制約を暗に含んでいる。順序づけされたタグタイプを有するワークに対して、ＦＩＦＯ順はワークの順序づけを示す。順序づけされたタグタイプ値を有する任意のＰＯＷエントリが実行されることはできるが、リストの先頭にあるＰＯＷエントリのみが処理中のリストから除かれる。処理中待ち行列７０６ａは順序づけられており、これより、ひとまとまりのワークの３つのそれぞれが順序づけられたタグへのスイッチが成功している。処理中待ち行列７０６ａの先頭は保留スイッチを有することができないが、残りのワークは順序づけまたはアトミックという異なるタグタイプへの保留スイッチを有してもよい。例えば、順序づけまたはアトミックの保留中タグスイッチに起因して、処理中待ち行列の先頭ではないワークが移動を留保されていれば、この移動は、先頭のワークが移動するまで行うことができない。
【００９３】
アトミックのタグタイプを有するワークに対して、ＦＩＦＯ順は、ワークがこのアトミックのタグタイプに切り換わる順序を示す。アトミックの処理中リストの先頭は、アトミックのタグタイプへのスイッチが成功した唯一のワークである。したがって、アトミックのタグタイプ値を有するＰＯＷエントリのリストの先頭のみが、いつでも実行されることができる。処理中待ち行列Ａ７では、Ａ７への切換は処理中待ち行列における先頭のエントリに関して完了されるが、他のＰＯＷエントリによって特定される他のワークは留保にされる。アトミックの処理中待ち行列では、異なるタグへの保留タグスイッチをワークは有することができない。
【００９４】
任意の順序づけまたはアトミックのタグスイッチの間、ＰＯＷモジュールは、ある処理中待ち行列の先頭のＰＯＷエントリを指すポインタを別の処理中待ち行列の末尾に移動させる。ポインタの移動は、順序づけのタグタイプへの切換を完了させるが、アトミックのタグタイプに関しては、ＰＯＷエントリが処理中待ち行列の先頭に到達するまで切換は完了しない。したがって、処理中待ち行列の先頭のＰＯＷエントリによって特定されるワークが保留スイッチを有することはなく、保留スイッチを有する場合は、ＰＯＷモジュールがそのスイッチによって要求される移動を即時実行することになる。処理中待ち行列Ａ５はＰＯＷエントリを１つしか保有していないため、保留タグスイッチは存在しない。ＰＯＷエントリによって特定されるひとまとまりのワークの１つが、アトミックのタグを保有する。
【００９５】
コアは、処理中ワークまたはスケジューリングされないワークにスケジューリングされることができる。図７Ａには、５つのコアが示されている。コア０はＰＯＷエントリに結び付けられているが、このエントリはスケジューリングされていない。コア１は、スケジューリングされていない、すなわち、ＰＯＷに結び付けられていない。コア２、コア３およびコア４は、処理中ワークにスケジューリングされている。コア２は、現時点では順序づけの状態であり、すなわち別の状態への保留スイッチを有している。コア３は、アトミックの状態への保留スイッチを有する。コア４は順序づけされた状態にあり、保留スイッチを有しない。
【００９６】
コアからのワーク要求に応答して、ＰＯＷモジュールは、スケジューリングを外されたワークをコアにスケジューリングすることもできる。スケジューリングを外されたワークは、ワーク待ち行列内のワークよりも高い優先順位を有する。ＰＯＷモジュールは、保留タスクスイッチを有するスケジューリングを外されたワークのスケジューリングは行わず、アトミックのタグタイプを有する入力待ち行列内のＰＯＷエントリのスケジューリングに対しては、そのエントリがそのタグを即時有することができない限り行わない。したがって、ＰＯＷモジュールが行なうワークのスケジューリングは、ワークが処理される状態にある場合に限られる。ヌルのタグタイプを有する入力待ち行列内のＰＯＷエントリは、即時スケジューリングから外される。
【００９７】
図６に関連して述べたように、スケジューリングされていない（ＰＯＷモジュールからみてスケジューリングされていない）コアがタグスイッチトランザクションを実行する場合にも、ワークはＰＯＷモジュールに入る。このようにしてＰＯＷモジュールに入るワークは、直ちにスケジューリングされる。スケジューリングされた後のワークは、スケジューリングされた他のワークから区別されるものではない。
【００９８】
ＰＯＷモジュールは、アイドル以外のサイクル中に全てのコアのワークをプリフェッチする（予め取り出しておく）ことができる。したがって、ワークを取得するためのトランザクションは最小の待ち時間で完了することができ、ユニットとの間でワークを転送するバスコンテンションを排除できる。しかし、コアに関連するグループマスクへの変更およびタグスイッチトランザクションは、プリフェッチを無効にする。
【００９９】
図８は、コア、ＰＯＷモジュールおよびＩＯブリッジに結合される専用タグスイッチバスを示すブロック図である。タグスイッチ操作は要求と完了を含み、（１）コアは、新しいタグをＰＯＷモジュールに転送し、（２）ＰＯＷモジュールはコアに、タグスイッチの完了が成功したことを示す。コアは、新しいタグを主として入力／出力（ＩＯ）格納機構を介して転送する。タグスイッチ操作は、コアがＩ／Ｏ格納命令を実行してコア内に保留タグスイッチビットを設定することによって開始される。一実施形態においては、タグスイッチの格納部は、ｏｐフィールド（操作フィールド）に格納されるｏｐコード（操作コード）と、この格納部のデータ部分に格納されるタグとを含む。この格納部は、コア２０２内の書込みバッファに確保され、コヒーレントメモリバス２３４を通って反映されて、ＩＯブリッジ（ＩＯＢ）／ＦＡＵ２３２を介してＩＯバス３０４に送信され、ＰＯＷモジュール２２８に入る。
【０１００】
各コアは、それぞれに保留スイッチビット８００を有する。ＩＯＢ／ＦＡＵ２３２には、各コアからの保留スイッチビットのコピー８０２が格納される。さらに、ＰＯＷモジュールが保留スイッチ状態を格納する。コア内の保留スイッチビットは、コアが格納命令を実行することによってスイッチ操作を開始すると、ＰＯＷモジュールを宛先とするＩＯ空間の物理アドレスに設定される。アドレスに、例えばアドレス・ビット＜４２：４０＞のように適切なｓｕｂｄｉｄ（sub-directive count）が使用されると、このコアに対応する保留スイッチビットがコア内に設定される。ＦＡＵも、そのコアの保留スイッチビットを、同一の格納命令を見つけると設定する。ＦＡＵは、この保留スイッチビットを使用して、選択された要求をスイッチが完了し終わるまで遅延させる。コアは、保留タグスイッチを多くとも１つしか有することができないため、必要な保留スイッチビットは１つのみである。
【０１０１】
コア２０２からタグスイッチ要求を受け取ると、ＰＯＷモジュール２２８は、ＰＯＷエントリ５００内のタグ値および／またはタグタイプを変更し、タグ値およびタグタイプ値に依存してＰＯＷエントリ５００を別の処理中リスト７０６ａ〜７０６ｃに移動させ、専用タグスイッチバス８０４上にタグスイッチの完了指示を提供する。ＰＯＷモジュールからのタグスイッチの完了によって、対応するコアおよびＦＡＵ内の保留タグスイッチビット８００はクリアされる。タグスイッチ操作は、別々のスイッチ要求操作およびスイッチ完了待機操作を有する。ワークに対し要求された順序づけおよびアトミック性の抑制が満足されると、ＰＯＷモジュールは要求されたタグ値の切換を完了する。このようにスイッチトランザクションを分離することによって、コアは、スイッチ要求に起因する待ち時間を他のワークとオーバーラップさせることができ、かつタグスイッチの保留中にワークをスケジューリングから外すことができる。これにより、長い同期遅延が回避される。
【０１０２】
タグスイッチの完了は、専用スイッチバス８０４上に送られる。一実施形態においては、スイッチバス８０４は５ビットを有し、５ビットのうちの４ビットはアドレスされている特定のコア（１６コアのうちの１つ）を選択するために使用され、もう１つのビット（有効ビット）は、所定のサイクルにおいてそのスイッチが有効か否かを指示するために使用される。ＰＯＷモジュールが、タグスイッチ操作の完了に成功すると、このコアに関するその保留スイッチ状態をクリアし、スイッチバス８０４の４ビットにおけるコアＩＤを符号化し、有効ビットを設定することによってこのコアＩＤを有効にする。コアおよびＩＯＢ／ＦＡＵの両方は、スイッチバス８０４を調査し、タグスイッチの完了が成功したことをＰＯＷモジュールが指示すると、コアＩＤによって選択されるコアの保留スイッチビット８００をクリアする。
【０１０３】
専用スイッチバス８０４がタグスイッチの完了に必要なコヒーレント／ＩＯバス帯域幅を最小限に抑えることより、必要なワイヤは５つ（ビット／信号）のみである。各コア内の局所的な保留スイッチビット８００の値をそのコアが調べるのみでよいため、コアがタグスイッチの完了を局所的にポーリングすることができる。したがって、帯域幅を最小限に抑えられる。スケジュールの効率的な除外にはポーリングが必要とされることから、効率的なポーリングは重要である。これにより、タグスイッチが完了するまでＩＯＢ／ＦＡＵ操作が遅延されることをも可能になる。多くのアプリケーションにとってこれは重要である。これはまた、スイッチを完了するための待ち時間を最小限に抑える。
【０１０４】
スイッチタグトランザクションは最優先事項であって最小限の待ち時間で完了し、同期化／順序づけの衝突がなければ、ＰＯＷモジュールへ要求を転送するバスコンテンションは防止される。
【０１０５】
ＰＯＷモジュールによる同期化サポートは極めて柔軟で、多くの異なる方法で使用することができる。ファイアウォール／仮想プライベートネットワーク（ＶＰＮ）パケット処理に関する同期化の一例を、以下の表１に示す。この例は、各パケットの処理を６つのアプリケーションステージ、すなわち、（１）デフラグメント、（２）ＩＰＳｅｃ復号化、（３）ルックアップ、（４）処理、（５）ＩＰＳｅｃ暗号化、および（６）出力キューイング、に分割できると仮定している。本例は、インターネットプロトコル（ＩＰ）バージョン４の使用を想定している。ただし、当業者には周知であるように、これをＩＰバージョン６用に変更することは容易である。
【０１０６】
【表１】
2008512950.tif 000003
【０１０７】
ＩＰ入力パケットは、デフラグメントステージの間にデフラグメントされる。当業者には周知であるように、ネットワーク上で伝送されるＩＰパケットのサイズの制限に起因して、大きいＩＰパケットのデータフィールドはフラグメント化され、これらフラグメントは一連の小さいＩＰパケットで送信される。各フラグメントのヘッダ内で伝送されるフラグメントオフセットフィールドは、フラグメントを再度順番に並べるために使用される。ＩＰＳｅｃ復号化ステージは、パケットのＩＰＳｅｃ復号化を実行する。ルックアップステージは、フローレコードを見つけて、状態を更新する。処理ステージは、パケットの送出前に必要なパケット処理を実行する。例えば、パケットは、ネットワークアドレス変換（ＮＡＴ）またはＴＣＰシーケンス番号の調整を必要とする場合がある。ＩＰＳｅｃ暗号化ステージは、パケットのＩＰＳｅｃ暗号化を実行する。出力ステージは、プロセッサから送出される出力待ち行列にパケットを配置する。
【０１０８】
各アプリケーションステージには、ステージＩＤ（０から５まで）が割り当てられる。各ステージに割り当てられるタグ値５０４は、割り当てられるステージ識別子およびステージタグを含む。同一のフロー識別子およびタグ識別子を有するパケットが異なるコア上で異なるステージにある他の任意のパケットと同時に実行されることを許容することによって、ステージ識別子が、異なる処理ステージをパイプライン方式に並行して実行できるようにする。同一フロー内の複数のパケットは、それらが異なるステージタグ値を有していれば、同一フロー内の異なるコア上で自由に実行されてもよい。
【０１０９】
種々のステージ識別子が、同一フロー内（および同一方向）の全てのパケット間の処理順序をも保証する。その目的は、多くの異なるタグ値をＰＯＷモジュールに示すことで、ＰＯＷモジュールは可能な限り多くのワークを並列化することができ、さらに分類があいまいなデータ構造体同士へのアクセスが適切に同期化されることを保証できるようにすることにある。
【０１１０】
一般に、ステージタグは、可能な限りフローを区別化するためにパケットのヘッダにおける多数のフィールドを使用するハッシュ結果であることより、同一フローからの２つのパケットが同一ハッシュ値を生成する。ステージタグはまた、分類があいまいなデータ構造体の見出しであっても、ハッシュ結果とこの指数の組合せであってもよい。
【０１１１】
表１を参照して、デフラグメントステージは順序づけのタグタイプ５０６を有し、タグ識別子５０４は、ステージ識別子０と、パケットに含まれる発信元ＩＰアドレスおよび宛先ＩＰアドレスに対して実行されたハッシュ関数の結果から導出されるステージタグとを含む。入力パケットは、デフラグメントステージの間にデフラグメントされる。入力パケットは全てこのステージに入り、そのうちのいくつかはフラグメント化されたものである可能性があり、デフラグメントされて少ない数のパケットがこのステージを出る。同一フロー内で到着するパケットはいずれも、フラグメントされているか否かに関わらず、発信元ＩＰアドレスおよび宛先ＩＰアドレスについて同一値を有するため同一ステージタグを有することより、これらパケットは順番に並べられる。同一フローからのパケットは、フラグメント化されなかったパケットもデフラグメントされたパケットも、共に順番に次のステージに入る。
【０１１２】
このデフラグメントステージに入るが、このステージから出ることのないフラグメントは、ヌルのタグタイプに切り換わり、他のいずれのステージにおいても処理されない。最後のフラグメントが到着して完全にデフラグメントされたパケットを生成すると、このデフラグメントされたパケットは次のステージにおいて入力フラグメントの代わりに処理される。これにより、このデフラグメントされたパケットは、入力フラグメントのワーク順序づけを担う。これは、デフラグメントされたパケットに理想的な順序づけを与える。すなわち、多数の入力フラグメントからこのデフラグメントされるパケットを生成するのに必要とされるソフトウェア処理時間が多大なものである場合でも、その最後の入力フラグメントによって瞬時に現出したかのようである。
【０１１３】
ＩＰＳｅｃ復号化ステージは、ＩＰＳｅｃ復号化を必要とするパケットに対してこれを実行する。必要がなければ、このステージは完全にスキップされる。タグタイプはアトミックであり、ステージ識別子は「１」であり、ステージタグは、ＡＨおよびＥＳＰプロトコルにおいて伝送されるセキュリティパラメータインデックス（ＳＰＩ）およびセキュリティアソシエーション（ＳＡ）から導出される。ＩＰＳｅｃは、認証ヘッダ（ＡＨ）、カプセル化セキュリティペイロード（ＥＳＰ）、ＩＰペイロード圧縮（ＩＰｃｏｍｐ）およびインターネット鍵交換（ＩＫＥ）を含む別々のプロトコルを含む。ＩＰＳｅｃは、www.ietf.org/rfc/rfc2401.txtで、インターネット（ＩＥＴＦ）ネットワークワーキンググループのコメント要求（ＲＦＣ）２４０１に記述されている。
【０１１４】
一般に、ＩＰＳｅｃ処理は、例えばリプレイ防止ウィンドウのようなデータ構造体を有する同一ＩＰＳｅｃトンネルを使用する異なるパケット間でいくつかの同期化を必要とする。リプレイ防止ウィンドウは、到着するＡＨまたはＥＳＰパケットがリプレイされているか否かを判断するために使用される３２ビットカウンタである。このアーキテクチャは、パケット復号化全体に対してＩＰＳｅｃセキュリティアソシエーション（ＳＡ）をカバーする単一のアトミックのタグを指定する。ステージタグ値はＳＡを一意に特定することより、到着のタグスイッチが完了した後、コアは、次のタグスイッチまでトンネルデータ構造体に自由にアクセスすることができる。
【０１１５】
同一フローからのパケットは全て同一のＩＰＳｅｃ ＳＰＩ／ＳＡ値を有するため、これらパケットがこのステージを出るときも順序づけされたままである。同一トンネルを使用する他のフローからのパケットもこのステージを通じて順番に並べられて、このステージを順番に出るが、次のステージでは異なるタグを有する可能性があるため、次のステージには順不同で入っていく可能性が高い。
【０１１６】
ルックアップステージは、フローレコードを見つけて、状態を更新する。なお、フローレコードは５タプルで特定されるものである。表示した例は、ステートフル（stateful：状態をもつ）なファイアウォールを想定している。ファイアウォールは、ネットワーク内のコンピュータがネットワーク外のコンピュータと直接通信することを防止する。代わりに、全ての通信は、特定のメッセージまたはファイルをネットワークに通すことが安全か否かを決定するプロキシサーバを介してルーティングされる。ステートフルなファイアウォールは、ネットワークを流れるＴＣＰストリームのようなネットワーク接続を追跡する。フローの最初のパケット上には、そのフローに対する高速パスのフローレコードは存在しないため、フローは有効化されて後のパケットのためにキャッシュされなければならない。このステージのステージタグは、特定のハッシュバケットを選択する。これにより、アトミックのタグがバケットへのアクセスを順番に並べて、このハッシュデータ構造体に対するさらなる同期化は必要とされない。フローからのパケットはいずれも、そのフローからの先のパケットがキャッシュ状態を更新する前に、フロー状態を観察（または修正）しない。
【０１１７】
キャッシュアーキテクチャを用いることで、後続のパケットの処理にかかる時間よりも、フロー状態を最初に有効化してキャッシュする時間の方が長い可能性が高い。したがって、いくつかのパケットは、パケットのルックアップが成功する前に、有効化が完了するのを待機する必要があるかもしれない。ＴＣＰのようなプロトコルでは、この事態は同一フローでは発生しないが、他のプロトコルまたは異なるフローからのパケットでは、不運にも偶然同一ハッシュバケット内で衝突が発生した場合に長い待機の可能性がある。これらの長い待機状況では、ＰＯＷモジュールによってスケジューリングの除外操作が提供されてもよい。現ワークがスケジューリングを外されて他のワークが実行されてもよく、後に、ＰＯＷモジュールは、アトミックのタグが利用可能になった時点でこのワークをスケジューリングし直すことができる。
【０１１８】
処理ステージは、パケットの送出前に、必要とされる場合のあるパケットの処理を実行する。例えば、パケットは、ネットワークアドレス変換（ＮＡＴ）またはＴＣＰシーケンス番号の調整を必要とする場合がある。ＮＡＴは、イントラネットまたは他の専用ネットワーク（スタブドメインと呼ばれる）内で使用されるＩＰアドレスと、インターネットＩＰアドレスとの間の変換処理である。この処理ステージは、順序づけのタグタイプと、ステージタグについてハッシュされたフロー識別子とを使用する。これは、同一フロー内のパケットがこのステージを出る際の順序を可能な限り正確に強要する。パケットは、ルックアップステージまたは処理ステージのいずれかにおいて、その後のステージを何ら実行されることなく廃棄されてもよい。
【０１１９】
ＩＰＳｅｃ暗号化ステージは、これを必要とするパケットにＩＰＳｅｃ暗号化を実行する。必要でなければ、このステージはスキップされる。タグの利用法は、ＩＰＳｅｃ復号化ステージに極似している。
【０１２０】
出力ステージは、パケットを、プロセッサから送出される出力待ち行列に配置する。タグタイプは、キューイングに必要とされる分類があいまいなデータ構造体を同期化するためにアトミックである。ステージタグは正確な出力待ち行列を特定するため、同一の出力待ち行列を使用する参照のみが順番に並べられる。このステージの間、出力待ち行列のサイズに基づいてパケットを廃棄するべきか否かを判断するために、例えばランダム初期検知（ＲＥＤ）のようなＱＯＳ計算が実行されてもよい。
【０１２１】
タグスイッチ操作は、１つのステージから次のステージへの遷移を規定する。ＰＩＰ／ＩＰＤユニットはパケットの最初のタグ、すなわち、デフラグメントステージを生成する。タグは順序づけとされ、タグ値は位相ＩＤ＝０、および位相タグ＝ハッシュ（IPsrc,IPdest）を有する。ＰＯＷモジュールは、ワークを最初のタグでスケジューリングする。最後のスイッチはＰＯＷモジュールにおいて実行され、次のパケットをスケジューリングするためのワーク要求を示す部分となることができる。なお、この最後のスイッチは、ＰＯＷモジュールからワークを除去するタグタイプであるヌルへの切換えである。したがって、ＩＰＳｅｃパケットの処理には、暗号化／復号化ステージがない場合、３つのタグスイッチのみが必要とされる。各ステージは一意のタグ値を有するため、マルチコアによって異なるフローの並列処理が可能である。
【０１２２】
以上、本発明をその好ましい実施形態に関連して詳細には示しかつ説明してきたが、当業者には、添付の請求の範囲に包含される本発明の範囲を逸脱することなく形態および細部に様々な変更を実行できることが理解されるであろう。
【図面の簡単な説明】
【０１２３】
【図１】本発明の原理によるネットワークサービスプロセッサを含むセキュリティアプライアンスを示すブロック図である。
【図２】図１に示すネットワークサービスプロセッサのブロック図である。
【図３】図２に示すネットワークサービスプロセッサにおける入出力パケット処理を実行するユニットを示すブロック図である。
【図４】Ｌ２キャッシュまたはＤＲＡＭに格納されるワーク待ち行列エントリを示す図である。
【図５】パケット順序ワークのエントリを示す図である。
【図６】パケット順序／ワークユニットを流れるワークの状態を示す図である。
【図７Ａ】パケット順序／ワークユニット内の様々なリストにおけるパケット順序／ワークのエントリを示すブロック図の左側部分の図である。
【図７Ｂ】パケット順序／ワークユニット内の様々なリストにおけるパケット順序／ワークのエントリを示すブロック図の右側部分の図である。
【図８】コア、パケット順序／ワークユニットおよびＩ／Ｏブリッジに結合される専用タグスイッチバスを示すブロック図である。
【符号の説明】
【０１２４】
２０２  プロセッサコア
２２８  パケット順序／ワークモジュール
【図１】
2008512950.tif 000004
【図２】
2008512950.tif 000005
【図３】
2008512950.tif 000006
【図４】
2008512950.tif 000007
【図５】
2008512950.tif 000008
【図６】
2008512950.tif 000009
【図７Ａ】
2008512950.tif 000010
【図７Ｂ】
2008512950.tif 000011
【図８】
2008512950.tif 000012
【国際調査報告】
2008512950.tif 000013
2008512950.tif 000014
2008512950.tif 000015