(57)【要約】  チップ上のコンポーネント・ネットワークの高速仮想チャネルを使用するための、方法、ルーターノード、及び一組の命令が開示されている。入力リンク３０２は、高速仮想チャネル１１０を経てパケット交換ネットワークのソースノード１０２から、高速フローコントロール・ユニットを受信してもよい。出力リンク３０６は、高速フローコントロール・ユニットをシンクノード１０６に送信してもよい。スイッチ・アロケータ３２２は、出力リンク３０６に高速フローコントロール・ユニットを直接転送してもよい。
2011517903.tif 000002
【特許請求の範囲】
【請求項１】
高速仮想チャネルを経てパケット交換ネットワークのソースノードから高速フローコントロール・ユニットを受信するステップと；
シンクノードに送信するために直接出力リンクに前記高速フローコントロール・ユニットを転送するステップと；
を有する方法。
【請求項２】
前記高速仮想チャネルから受信される高速フローコントロール・ユニットをトラッキングするステップと；
スターベーション閾値に達する場合、スターベーション回復モードに入るステップと；
隣接ノードに通常フローコントロール・ユニットを伝送するステップと；
を更に有する請求項１記載の方法。
【請求項３】
前記高速仮想チャネルは、静的な長さを有する、請求項１記載の方法。
【請求項４】
前記高速仮想チャネルは、動的な長さを有する、請求項１記載の方法。
【請求項５】
最適な高速仮想チャネルが利用できない場合、前記高速仮想チャネルは、代替の高速仮想チャネルである、請求項１記載の方法。
【請求項６】
前記高速仮想チャネルは、静的に割り当てられたバッファを有する、請求項１記載の方法。
【請求項７】
前記高速仮想チャネルは、動的に割り当てられたバッファを有する、請求項１記載の方法。
【請求項８】
高速仮想チャネルを経てパケット交換ネットワークのソースノードから、高速フローコントロール・ユニットを受信する入力リンクと；
前記高速フローコントロール・ユニットをシンクノードに送信する出力リンクと；
前記高速フローコントロール・ユニットを直接に前記出力リンクに転送するスイッチ・アロケータと；
を有するルーターノード。
【請求項９】
通常のフローコントロール・ユニットが隣接ノードに届くよう、スターベーション閾値に達するかどうか判定するスターベーションカウンタ、
を更に有する請求項８記載のルーターノード。
【請求項１０】
前記高速仮想チャネルは、静的な長さを有する、請求項８記載のルーターノード。
【請求項１１】
前記高速仮想チャネルは、動的な長さを有する、請求項８記載のルーターノード。
【請求項１２】
最適な高速仮想チャネルが利用できない場合、前記高速仮想チャネルは代替の高速仮想チャネルである、請求項８記載のルーターノード。
【請求項１３】
前記高速仮想チャネルは、静的に割り当てられたバッファを有する、請求項８記載のルーターノード。
【請求項１４】
前記高速仮想チャネルは、動的に割り当てられたバッファを有する、請求項８記載のルーターノード。
【請求項１５】
前記パケット交換ネットワークは、チップ・マルチプロセッサである、請求項８記載のルーターノード。
【請求項１６】
記憶媒体に格納された一組の命令であって、前記一組の命令は、データ処理のための方法をインプリメントするプロセッサによって実行可能であり、前記方法は、
高速仮想チャネルを経てパケット交換ネットワークのソースノードから高速フローコントロール・ユニットを受信するステップと；
シンクノードに送信するために直接出力リンクに前記高速フローコントロール・ユニットを転送するステップと；
を有する、記憶媒体に格納された一組の命令。
【請求項１７】
前記方法は、
前記高速仮想チャネルから受信される高速フローコントロール・ユニットをトラッキングするステップと；
スターベーション閾値に達する場合、スターベーション回復モードに入るステップと；
隣接ノードに通常フローコントロール・ユニットを伝送するステップと；
を有する、請求項１６記載の記憶媒体に格納された一組の命令。
【請求項１８】
前記高速仮想チャネルは、動的な長さを有する、請求項１６の記憶媒体に格納された一組の命令。
【請求項１９】
最適な高速仮想チャネルが利用できない場合、前記高速仮想チャネルは代替の高速仮想チャネルである、請求項１６記載の記憶媒体に格納された一組の命令。
【請求項２０】
前記高速仮想チャネルは、動的に割り当てられたバッファを有する、請求項１６記載の記憶媒体に格納された一組の命令。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の技術分野は、一般にチップ・マルチプロセッサ上のコンポーネント間の通信に関する。より詳細には、本発明は、特にチップ・マルチプロセッサ上のコンポーネント間の高速仮想通信チャネルを形成することに関する。
【背景技術】
【０００２】
［はじめに］
チップ・マルチプロセッサ（ＣＭＰ）または特定アプリケーション用のシステムが構築されたチップ（ＡＳＯＣ：ａｐｐｌｉｃａｔｉｏｎ−ｓｐｅｃｉｆｉｃ  ｓｙｓｔｅｍｓ−ｏｎ−ａ−ｃｈｉｐ）は、相互に通信することを必要とするいくつかのコンポーネントを有している。これらのコンポーネントとしては、プロセッサ、キャッシュ、データレジスタ、あるいはその他のチップが挙げられる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
チップコンポーネントは、バスシステムまたは専用のルーティングシステムを使用して通信してもよい。これらのシステムのいずれにおいても、チップ上の貴重なスペースを使用し、多くのルーティングを必要とする。それと共に、信号間の干渉をつくる。
【課題を解決するための手段】
【０００４】
コンポーネントは、パケット交換システムを使用することにより、より空間的に効率的な方法で通信することができる。パケット交換システムは、コンポーネント間において、データのパケットを通過させることによって行ってもよい。そして、いかなる２つのコンポーネント間のルーティングの量をも減らすことができる。
添付の図面は、特定の実施例を示したものであり、従って、発明の範囲を限定するためのものではない。本発明の特徴は、図面を用いて説明する。
【図面の簡単な説明】
【０００５】
【図１】チップ・マルチプロセッサ・コンポーネント・データパケット伝送の実施例を示すブロック図である。
【０００６】
【図２】チップ上のコンポーネント・ネットワークの二次元のメッシュネットワークに係る実施例を例示する図である。
【０００７】
【図３】高速仮想チャネルをインプリメントする、ルーター・ノードマイクロアーキテクチュアを示す実施例のブロック図である。
【０００８】
【図４】二次元のメッシュネットワークとして、チップ上の動的高速仮想チャネル・コンポーネント・ネットワークの一実施例を示す図である。
【０００９】
【図５】フレキシブルなルートを持つチップ上の動的高速仮想チャネル・コンポーネント・ネットワークの一実施例を示すブロック図である。
【００１０】
【図６】仮想チャネルからのデータパケットを処理するルーターノードの方法に係る一実施例を示すフローチャートである。
【００１１】
【図７】メッシュネットワークにおいて、高速仮想チャネルネットワークのスターベーションの事象の一実施例を示す図である。
【００１２】
【図８】通常の仮想チャネルのクレジットベースのバッファ管理システムの一実施例を示す図である。
【００１３】
【図９】高速仮想チャネルのクレジットベースのバッファ管理システムの一実施例を示す図である。
【００１４】
【図１０】静的バッファ管理システムのためのバッファカウントの一実施例を示すブロック図である。
【００１５】
【図１１】動的に共有されたバッファ管理システムのためのバッファカウントの一実施例を示すブロック図である。
【００１６】
【図１２】与えられたノードが利用し得るパスの組合せの一実施例のブロック図である。
【００１７】
【図１３】仮想チャネルの静的パーティショニングの一実施例を示すブロック図である。
【００１８】
【図１４】ルーターノードとして機能し得るコンピュータシステムの一実施例を示すブロック図である。
【発明を実施するための形態】
【００１９】
［発明の詳細な説明］
本発明の付加的な特徴および効果は、詳細な説明において後述する。そして、これらの一部は記載から明らかであり、又は本発明の実施により明らかとなる。本発明の特徴および効果は、特に添付の請求の範囲において定義される事項の組合せによって得られてもよい。本発明のこれらの、そしてまた他の、特徴は、以下の説明、及び添付の請求の範囲から明らかとなる。あるいは、本願明細書において記載されるように、本発明の実施によって得られてもよい。
【００２０】
本発明の様々な実施態様について、以下に詳細に述べる。特定の実施例が示されているが、これらは、例示的に示すことのみを目的としたものである。本願発明の技術分野の当業者は、その他のコンポーネントを認識し、かつ、構成は本発明の精神と範囲から逸脱しない限りこれを採用しても良い。
【００２１】
本発明は、種々の実施例、例えば、方法、装置、コンピュータ命令の一組、及び本発明の基礎概念に関する他の実施例を含む。方法、ルーターノード、及びチップ上のコンポーネント・ネットワークの高速仮想チャネルを使用するための命令のセットが開示される。入力リンクは、高速仮想チャネルを経てパケット交換ネットワークのソースノードから、高速フローコントロール・ユニットを受信してもよい。出力リンクは、高速フローコントロール・ユニットをシンクノード（ｓｉｎｋ  ｎｏｄｅ）に送信してもよい。スイッチ・アロケータは、出力リンクに直接に、高速フローコントロール・ユニットを伝送してもよい。
【００２２】
チップ・マルチプロセッサ（ＣＭＰ）または特定アプリケーション用のシステムが構築されたチップ（ＡＳＯＣ）は、相互に通信することを必要とする多くのコンポーネントを有してもよい。これらのコンポーネントは、パケット交換を使用して、チップスペースを浪費せずに、データを通信してもよい。図１は、チップ・マルチプロセッサ・コンポーネント・データ転送１００の一実施例を示すブロック図である。ソースノード１０２として機能するコンポーネントは、一組のデータをデータパケットに組み立てても良い。データパケットは、一つ以上のフローコントロール・ユニット（ＦＬＩＴ）に分けられてもよい。ソースノード１０２は、最も近い利用できるコンポーネントに各々のＦＬＩＴを伝送してもよい。受信コンポーネントは、ルーターノード１０４として機能し、シンクノード１０６として機能しているコンポーネントに達するまで、次の最も近い利用できるコンポーネントに、データを伝送してもよい。ＦＬＩＴがソースノード１０２からシンクノード１０６と通過するパスは、仮想チャネル組み込まれてもよい。通常の仮想チャネル（ＮＶＣ）１０８において、ソースノード１０２はルーターノード１０４にＦＬＩＴを伝送してもよい。これは、ＦＬＩＴをバッファリングしてもよく、ＦＬＩＴ、及び他のＦＬＩＴｓをパイプラインによって扱ってもよい。そして、それは、出力リンクに送信し、それらを次のルーターノード１０４またはシンクノード１０６に送信する。
【００２３】
高速仮想チャネル（ＥＶＣ）１１０は、パケット化オンチップ・ネットワークと、理想の相互接続製品との間の、パフォーマンスとエネルギーとのギャップを縮めるために利用されてもよい。そして、これによって、待ち時間及びエネルギーを専用のリンクのものに近づける。ＥＶＣ１１０は、ＦＬＩＴｓに対して、あらかじめ定義されたノードのペア間のパスに沿って、中間のルーターノード１０４をバイパスさせてもよい。ＥＶＣ１１０を通過するＦＬＩＴは、他のＦＬＩＴｓとは異なる選択（ｐｒｅｆｅｒｅｎｃｅ）を与えてもよい。これによって、各ルーターノードで、バッファリングやルータパイプラインを通過しなければならないことを回避し、直接に出力リンクを利用することができる。ＥＶＣ１１０はいかなる回路セットアップ段階も含むことなく、回線交換に類似した方法のネットワークの中でフローの生成を容易にする。そして、パケット通信待ち時間をかなり減らすことができる。さらに、ＦＬＩＴが実質的に中間のルーターノード１０４をバイパスすることを可能とすることによって、ＥＶＣ１１０はバッファリング、ルーター・スイッチング処理、及びプレホップ・リソースコンテンションを減らし、エネルギー及び領域効率を増加させる。
【実施例】
【００２４】
図２は、二次元のメッシュネットワークとしての、静的ＥＶＣ  パケット交換ネットワーク２００の一実施例を例示する。パケット交換された、チップマルチプロセッサネットワークが用いられているが、ＥＶＣ１１０はいかなるパケット交換ネットワークに使用されてもよい。このメッシュネットワークの、サイズ及び二次元の形態は、例示であって、本発明の目的において、決して限定的でない点に留意すべきである。各々のノード２０２は、ソースノード１０２、ルーターノード１０４またはシンクノード１０６として機能してもよい。ネットワーク２００の各々のノード２０２は、ＮＶＣ１０８によって隣接ノード２０２に接続されてもよい。更に、ノード２０２は、ＥＶＣ１１０によって、隣接していないノードに接続されてもよい。これによって、ＦＬＩＴは、複数の中間ノードまたはルーターノード１０４を飛び越えることができる。これによって、あらかじめ定義されたパスに沿って、ルーターノード１０４での停止やバッファリングを回避する。例えば、ノードのＢからノードのＧに動くＦＬＩＴは、普通のＮＶＣパス１０８をノードのＢからノードのＤまで経由し、ノードのＤからノードのＧまでは、ＥＶＣ１１０のリンクを経由してもよい。ＥＶＣ１１０は、ルーターノード１０４（例えばノードのＥ、及びＦ）による待ち時間を排除し得る。かつルーターノード１０４上の全てのバッファオペレーションを排除することによって、パワーを節約してもよい。静的ＥＶＣネットワークにおいて、特定のソースノード１０２とシンクノード１０６とは、ＥＶＣ１１０で接続されてもよい。４つのノードの静的ＥＶＣ１１０が本実施例では使用されるが、選択によっては、より大きいか、又はより小さい長さの静的ＥＶＣ１１０が使用されてもよい。
【００２５】
ルータは、仮想チャネル・フローコントロールに加えて、高速リンクをインプリメントしてもよい。ルータは、高速パスを通過するデータパケットによって利用されるだけの仮想チャネルを利用してもよい。図３は、ＥＶＣ１１０をインプリメントするルーター・ノード・マイクロアーキテクチャ３００の一実施例のブロック図を示す。ルーターノード１０４は、入力リンク３０２上の仮想チャネルを経てＦＬＩＴを受信してもよく、かつ、フロー制御モジュール３０４にＦＬＩＴを入力してもよい。フローコントロールのために使用される仮想チャネルは、ＮＶＣｓ１０８、及びＥＶＣｓ１１０として構成されてもよい。フロー制御モジュール３０４は、ＦＬＩＴの優先度を決定するために仮想チャネルを使用してもよい。これによって、どのＦＬＩＴを、クロスバースイッチ３０８によって選択された出力リンク３０６に転送するかを選択する。
【００２６】
ルート計算論理モジュール３１０はルート計算を実行してもよい。又は、各々のルーターノード１０４でのソースノード１０２とシンクノード１０６との間を通過するデータパケットのパスを計算してもよい。ルート計算論理モジュール３１０は、データパケットがＥＶＣ１１０に到来した場合、資格を与える（ｑｕａｌｉｆｙ）役割を果たしてもよい。加えて、ルート計算論理モジュール３１０は、全てのパケットのルート先取り（ｌｏｏｋ  ａｈｅａｄ  ｒｏｕｔｉｎｇ）を行ってもよい。これによって、一旦データパケットがノードあるいはＥＶＣパス１１０エンドポイントに達した場合、ルート計算は、ルータパイプラインで、厳密なパス（ｃｒｉｔｉｃａｌ  ｐａｔｈ）でなくてもよい。ルート計算は、使用されているベースルーティングアルゴリズムにいかなる影響も与えない。ＥＶＣアロケータ３１２は、ＥＶＣ１１０を、一対のノード間を通過するために高速伝送路を使用する予定になっているデータパケットに割り当ててもよい。これに対して、ＮＶＣアロケータ３１４は、ＮＶＣ１０８を隣接したノードに通過する予定になっている他のデータパケットに割り当ててもよい。
【００２７】
フロー制御モジュール３０４は、ＥＶＣ入力バッファ（ＥＶＣ  ＢＵＦ）３１６を経て、ＥＶＣ１１０からＦＬＩＴを受信してもよい。あるいは、ＮＶＣ入力バッファ（ＮＶＣ  ＢＵＦ）３１８を経て、ＮＶＣ１０８からＦＬＩＴを受信してもよい。ＥＶＣラッチ３２０は、ＦＬＩＴがその高速パス１１０上のいかなるルーターノード１０４も通過するように、設定してもよい。ＥＶＣラッチ３２０によって通過するＦＬＩＴは、同じ出力ポート３０６上の他のいかなるデータパケット・フローよりも先取りしてもよい。ＥＶＣラッチ３２０は、ソースノード１０２（例えばより低い優先度ＥＶＣフロー）によって送られる２つのノード間の進行中のデータパケット伝送をインターラプトしてもよい。
【００２８】
スイッチ・アロケータ３２２は、ＥＶＣフロー１１０をＮＶＣフロー１０８より優先してもよい。スイッチ・アロケータ３２２は、ＦＬＩＴｓのＥＶＣフロー１１０を、ソースノード１０２で、より少ないホップでインターラプトする。このため、より多くのホップを有するＦＬＩＴｓのＥＶＣフロー１１０は、そのルーターノード１０４を使用してもよい。スイッチ・アロケータ３２２は、ＦＬＩＴｓのＥＶＣフロー１１０を、ソースノード１０２により近いところでインターラプトする。したがって、ソースノード１０２から、より遠いＦＬＩＴｓのＥＶＣフロー１１０は、ルーターノード１０４を使用してもよい。
【００２９】
ネットワーク２００は、ＥＶＣｓ１１０、及びＮＶＣｓ１０８に静的に分けられ、また、仮想チャネルをより動的に生成し得る。図４は、動的ＥＶＣパケット交換ネットワーク４００の一実施例の、二次元のメッシュネットワークを示す。動的ＥＶＣパケット交換ネットワーク４００において、ノード２０２間のいかなるホップの組も、動的ＥＶＣ４０２として示されてもよい。コンポーネント・ネットワーク制約によって定まる最大ＥＶＣ長の範囲内で、与えられたデータパスのために必要とされるパスとして、ＥＶＣパス４０２の長さが設定されてもよい。例えば、静的ＥＶＣネットワーク２００で、ソースノード１０２は、単一のホップＮＶＣパス１０８を経てノードのＢからノードのＣに、及びノードＣからノードのＤに横断してもよく、そして、ノードのＤからノードのＧに静的に割当られたＥＶＣパス１１０を経て横断してもよい。３ホップが最大であるＥＶＣパス４０２を可能とする動的ネットワークにおいて、ソースノード１０２は、ノードのＢから直接にＦＬＩＴをノードのＥに送ってもよく、そしてノードのＧに行くために、２ホップ長さのサブセットＥＶＣパス４０２を使用してもよい。以下同様である。
【００３０】
図５は、チップ５００上のルートフレキシブルな動的ＥＶＣコンポーネント・ネットワークの一実施例を例示するブロック図である。時々、データパスは、リソース制約のために、最適ＥＶＣパス５０２（例えば最も長いＥＶＣパス５０２）を使用することができなくてもよい。この場合、ソースノード１０２は、代替のＥＶＣパス５０４を経て、ＦＬＩＴを送ってもよい。例えば、これは利用可能資源を有する次のより短いＥＶＣパス５０４である。例えば、シンクノードＧ１０６にＦＬＩＴを送るソースノードＡ１０２のために最も効率的なデータパスは、第１の最適ＥＶＣパス５０２に沿って、ソースノードＡ１０２から直接にノードのＤにＦＬＩＴを送り、そして第２の最適ＥＶＣパス５０２に沿って、ルーターノードのＤ１０４からシンクノードＧ１０６に送ることである。しかしながら、最も効率的なデータパスは、利用可能な資源を有していない。ソースノードＡ１０２は、シンクノードに代替パス５０４に沿ってＦＬＩＴを送ってもよい。ソースノードＡ１０２は、代替のＥＶＣパス５０４に沿って、ルーターノードのＣ１０４に、ＦＬＩＴを送ってもよい。そして、ルーターノードのＣ１０４からルーターノードのＥ１０４に、そして、ルーターノードのＥ１０４からシンクノードＧ１０６に送ることになる。ＥＶＣアロケータ２１２は、データパケットの経路情報を考慮することによって、最善経路を決定してもよい。
【００３１】
図６は、仮想チャネルからＦＬＩＴを処理するルーターノードのための一実施例の方法６００のフローチャートを示す。ルーターノード１０４は、仮想チャネル（ＶＣ）（ブロック６０２）を経て、ＦＬＩＴを受信してもよい。ＦＬＩＴが通常のＦＬＩＴ（ＮＦ）（ブロック６０４）である場合、ルーターノード１０４が入力バッファにＮＦを記憶してもよく（ブロック６０６）、そしてＮＦを処理する（ブロック６０８）。ＮＦは、ルーターノード１０４がソースノード１０２であるＦＬＩＴであってもよい。また、ＮＶＣ１０８上の隣接したノードからルーターノード１０４に到着したＦＬＩＴまたはルーターノード１０４がＥＶＣ１１０の終点であるが、シンクノード１０６でないＦＬＩＴであってもよい。ＮＶＣ１０８として到着する場合、入力ポートはＮＶＣ入力バッファ３１８であり、ＥＶＣ１１０として到着する場合、ＥＶＣ入力バッファ３１６である。ルーターノード１０４は、処理したＮＦを、出力リンク３０６に送ってもよい（ブロック６１０）。ＦＬＩＴが高速ＦＬＩＴ（ＥＦ）１１０である場合（ブロック６０４）、ルーターノード１０４は、ＥＦを出力リンク３０６に転送する（６１２ブロック）。高速ＦＬＩＴは、ＥＶＣ１１０の途中でルーターノード１０４によって受信されるＦＬＩＴであってもよい。
【００３２】
特定のメッセージフローのためにバンド幅を事前に確保しているいかなるネットワークにおいても、予め確立された回路を通過するメッセージが他のメッセージをブロックするときに、スターベーション（ｓｔａｒｖａｔｉｏｎ）が発生し得る。図７は、ＥＶＣネットワークにおいて、スターベーション７００が発生したメッシュネットワークの一実施例を示す。ＥＦｓ７０２に与えられた上位の優先度は、結果としてスターベーションシナリオ７０４を誘発する。より詳細には、ＥＶＣ７０２のパスに沿ったルーターノードＤ１０４がＥＦのサービスを行う入力を受ける場合、ルーターノードＤ１０４で局所的にバッファリングされるＮＦは物理チャネルを使用する機会を決して得られない。上流からの高速データパケットも、下流のルータから生じている異なるＥＶＣ１１０上の高速データパケットを連続的にスターブ（ｓｔａｒｖｅ）させ得る。
【００３３】
これを解決するために、各々のルーターノード１０４は、ルーターノード１０４が特定のＥＶＣパス１１０にサービスを提供した連続的なサイクルのカウントの数を維持してもよい。高速ＦＬＩＴｓにサービスを提供した連続的なサイクルが閾値の数を超えた後に、ルーターノード１０４がスターベーションメッセージを送信してもよい。例えば、「スターベーション回復を開始する」旨のメッセージまたは「スターベーション・オン」トークン、をＥＶＣソースノードＡ１０２にアップストリーム方向に送信してもよい。このトークンを受信すると、即座に、ソースノードＡ１０２は対応するリンク上の送信ＥＦｓを停止してもよい。そして、局所的にスターブされたＦＬＩＴがサービスを受けることを可能とする。設定されたサイクル数、これを行った後、ルーターノードのＤ１０４は、「スターベーションの回復終了」のメッセージまたは「スターベーション・オフ」のトークンをＥＶＣソースノードＡ１０２に送ってもよい。これによって、ＥＶＣコミュニケーションを再開してよい旨が送信される。
【００３４】
図６に示すように、ＥＦに対して、同じ出力ポート３０６を予定しているＮＦがバッファリングされる場合（ブロック６１４）、ルーターノード１０４はスターベーションカウント（ＳＣＴ）を＋１増加してもよい（ブロック６１６）。ルーターノード１０４は、スターベーション閾値（ＳＴＨＲ）に達したかどうか見るために、ＳＣＴをチェックしてもよい（ブロック６１８）。ＳＣＴがＳＴＨＲの値に達した場合（ブロック６１８）、ルーターノード１０４は、「スターベーション回復を開始する」メッセージ（ＢＳＲＭ）の上流方向の全てのＥＶＣソースノード１０２（ブロック６２０）に送ってもよい。全ての適切な上流のノードがＢＲＳＭを受信することが可能な時間の後、ルーターノード１０４は、ルーターノードがＥＦｓを受信していない間、スターベーション回復モードに入ってもよい。ルーターノード１０４がスターベーション回復モードである間、ＥＶＣソースノード１０２は休止してもよい。あるいは、ＥＦｓの伝送はＥＦｓをルート変更するか、または他の代替措置をとる。ルーターノード１０４は、スターベーション回復周期カウンタ（ＳＲＰ）をゼロにセットしてもよい（ブロック６２２）。
【００３５】
ＮＦに対しては、ルーターノード１０４がスターベーション回復モードでない場合（ブロック６２４）、ルーターノード１０４はＳＣＴをゼロにリセットしてもよい（ブロック６２６）。ルーターノード１０４がスターベーション調停モードである場合（ブロック６２４）、一旦ＮＦが出力ポート３０６にうまく送られるならば、ルーターノード１０４はＳＲＰを＋１増加してもよい（ブロック６２８）。一旦スターベーション回復の期間が終ると（ブロック６３０）、ルーターノード１０４は全ての上流のＥＶＣソースノード１０２に「スターベーションの回復終了」のメッセージ（ＥＳＲＭ）、すなわち、ルーターノード１０４がＥＦｓをもう一度受信する信号（ブロック６３２）、を送信してもよい。
【００３６】
チップ上のコンポーネント・ネットワークは、バッファを管理し、かつ隣接したルーターノード１０４間のそれらの利用可能性を通信するために、バッファードフロー制御技術を使用してもよい。下流ノードは、バックプレッシャにより、上流のノードに、利用できる空きバッファの数を通信してもよい。クレジットベースのバッファ管理は、下流で利用できる空きバッファのカウントの数を維持するために、上流のルータを使用してもよい。カウントは、ＦＬＩＴが転送されるたびに、デクリメントされてもよい。それに伴って、下流のバッファを消費する。ＦＬＩＴが下流ノードから離れ、そして、対応するバッファを開放した場合、クレジットは上流に送り返されてもよく、かつ、対応する空きバッファカウントが増加してもよい。
【００３７】
コンポーネント・ネットワークは、その仮想チャネルに対するクレジットの往復遅延と同じに、静的にバッファリングを各々の仮想チャネルに割り当てる単純なバッファ管理方式を使用してもよい。図８は、一実施例であるＮＶＣ１０８のクレジットベースッファ管理システム８００を、時間軸に沿って示した図である。時刻ｔ１で、ノードＢがＦＬＩＴを次のノードに送信する（矢印８０２）と、ノードＢは、クレジットをｔ１とｔ２との間でノードＡに送信してもよい（矢印８０４）。ノードＡは、ｔ２とｔ３との間でクレジットを処理する（矢印８０６）。ノードＡは、ｔ３とｔ４との間でノードＢにＦＬＩＴを送っている間に（矢印８０２）、クレジットを前のノードに送信してもよい（矢印８０４）。ノードＢは、ｔ４とｔ５との間で、非高速パイプラインでＦＬＩＴを処理していてもよい（矢印８０８）。したがって、クレジット往復遅延（ＴＣＲＮ）は、ｔ１からｔ５までかかることになる。
【００３８】
ＥＶＣ１１０を使用するときに、バッファ利用可能性に係る通信は下流のＥＶＣシンクノード１０６で空きバッファを確実にするために数ホップ全体にされてもよい。バッファ利用可能性のマルチホップ通信は結果としてより長いバッファ所用時間となり、処理能力上の有利でない効果を有し得る。図９は、一実施例としてＥＶＣ１１０クレジットベースバッファ管理システム９００を時間軸に沿って示した図である。時刻ｔ１で、ノードＤがＦＬＩＴを次のノードに送信し（矢印９０２）、ノードＤはクレジットをｔｉとｔ２との間にノードＡに送信してもよい（矢印９０４）。ノードＡは、ｔ２とｔ３との間でクレジットを処理する（矢印９０６）。ｔ３とｔ４と間のノードＢでＦＬＩＴを送るときに（矢印９０２）、ノードのＡはクレジットを前のノードに送信してもよい（矢印９０４）。ｔ４とｔ５との間に、ノードＢは、高速パイプラインの一部としてＦＬＩＴを出力リンクに転送する（矢印９０８）。ノードのＢは、ｔ５とｔ６との間のノードＣに、ＦＬＩＴを送ってもよい（矢印９０２）。ｔ６とｔ７との間で、ノードＣは、高速パイプラインの一部としてＦＬＩＴを出力リンクに転送する（矢印９０８）。ノードＣは、ｔ７とｔ８との間でノードＤに、ＦＬＩＴを送ってもよい（矢印９０２）。ノードＣは、ｔ８とｔ９との間で、非高速パイプラインのＦＬＩＴを処理していてもよい（矢印９１０）。したがって、クレジット往復遅延（ＴＣＲＥ）は、ｔ１からｔ９までとなる。
【００３９】
バッファ管理システムは、静的にバッファを管理してもよい。図１０は、静的バッファ管理システム１０００のためのバッファカウントの一実施例のブロック図を示している。静的バッファの数は各々の仮想チャネルに割り当てられてもよい。そして、これは、各々の仮想チャネルに到来するＦＬＩＴｓのためのものである。ＮＶＣバッファの一組１００２は、各々のＮＶＣ１０８のために予約されていてもよい。そして、ＥＶＣバッファの一組１００４は、各々のＥＶＣ１１０のために予約されていてもよい。一組のバッファの数をセットするときに、各々の一組ＥＶＣバッファ１００４のサイズは、ＴＣＲＥを考慮してもよい。
【００４０】
静的バッファ管理は、阻害のあるトラフィック（ａｄｖｅｒｓａｒｉａｌ  ｔｒａｆｆｉｃ）の場合にはバッファを割り当てるときに非効率的になることがある。大多数のネットワークトラフィックがごく近隣で起きている場合、ＥＶＣ１１０は決して使用されないかもしれない。そして、静的にＥＶＣｓ１１０に割り当てられたバッファスペースは、利用されないかもしれない。静的にバッファをＶＣ（例えばＮＶＣ１０８、及びＥＶＣ１１０）に仕切る代わりに、バッファは、要求があり次第ＶＣに割り当てられてもよい。上流のノードに対してＥＶＣの存在を知らせるハイウォーターマーク方式は、バッファが利用できるようになった場合に、長いホップより、短いホップのＥＶＣｓ４０２またはＮＶＣｓ１０８に優先度を与える。例えば、２ホップのＥＶＣ４０２が、少なくとも８つの利用できるバッファを要求する場合、下流のルータは、上流のルータに対して、もし、下流のルータの８つのバッファカウントが８になった場合、離れているＥＶＣ４０２の２つのノードが利用できる旨の信号を送ってもよい。そのバッファは、ＶＣ全体に自由に動くことができ（ｆｌｏａｔ  ｆｒｅｅｌｙ）、そうすることによって、ＶＣがただ一つのＦＬＩＴを持つ。
【００４１】
図１１は、動的な共用バッファ管理システム１１００のためのバッファカウントの一実施例のブロック図を示す。バッファカウント１１０２は、利用できる（または自由な）バッファの数を意味してもよい。利用できるバッファの数が、ＮＶＣ閾値１１０４、又は、ＮＶＣ１０８をオペレートするために必要なバッファの数、と等しいことを、バッファのカウント１１０２が示している場合、ノードはＮＶＣ１０８を使用してもよい。利用できるバッファの数が、ＥＶＣ閾値１１０６、又は、ＥＶＣ４０２をオペレートするために必要なバッファの数、と等しいことを、バッファのカウント１１０２が示している場合、ノードはＥＶＣ４０２を使用してもよい。ＥＶＣ閾値１１０６は、ＥＶＣパス４０２の長さに関連し得る。
【００４２】
フレキシブルなバッファリングを可能にするために、下流のルータは、適切な信号を上流のルータに送信しなければならないかもしれない。図１２は、与えられたノードが利用し得るパス１２００の組合せの一実施例を示すブロック図である。８つのノードのネットワークが示されているが、他のサイズのネットワークが使用されてもよい。
【００４３】
ＶＣは、静的に分割されてもよい。図１３は、仮想チャネルの静的分割１３００の一実施例を示すブロック図である。ＶＣ１３０２またはパケット状態トラッカの合計数は、両ＮＶＣｓ１０８、及び異なる長さのＥＶＣｓ４０２で分かれる。この分割は、設計時に行ってもよい。最長ＩＭＡＸの長さのＥＶＣのための能力を持つネットワークコンポーネントに対して、総数（ｋ×ＩＭＡＸ）組の仮想チャネルが提供されてもよい。このコンポーネント・ネットワークは、ＮＶＣｓ１０８に対してｋ１個の仮想チャネル１３０２、長さ２のＥＶＣ４０２に対してｋ２個の仮想チャネル、長さ３のＥＶＣ４０２に対してｋ３個の仮想チャネル、等となる。
【００４４】
図１４は、パケット交換ネットワークのルーターノード１０４として機能するためのコンピューティング・システム１４００の可能な構成を例示する。ルーターノード１０４は、バス１４４０によって接続された、コントローラ／プロセッサ１４１０と、メモリ１４２０と、ネットワークインターフェース１４３０とを有する。ルーターノード１０４は、いかなるオペレーティングシステム（例えばＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）またはＬＩＮＵＸ）をインプリメントしてもよい。クライアント、及びサーバ・ソフトウェアは、例えばいかなるプログラミング言語（例えばＣ、Ｃ＋＋、Ｊａｖａ（登録商標）またはＶｉｓｕａｌ  Ｂａｓｉｃ）で書かれてもよい。サーバ・ソフトウェアは、アプリケーション・フレームワーク（例えばＪａｖａ（登録商標）サーバまたは．ＮＥＴ（登録商標）フレームワーク）上で動作してもよい。
【００４５】
コントローラ／プロセッサ１４１０は、当業者にとって既知のいかなるプログラムされたプロセッサであってもよい。しかしながら、意志決定サポート方法は、また、専用又は汎用コンピュータ、プログラムされたマイクロプロセッサまたはマイクロコントローラ、周辺集積回路素子、特定用途向け集積回路、ハードウェア／電子的論理回路、例えばディスクリートエレメント回路または他の集積回路、プログラマブル・ロジック・デバイス、例えばプログラマブル・ロジック・アレイ、フィールド・プログラマブル・ゲートアレイ等にインプリメントされてもよい。一般に、本願明細書において記載されているように、ＥＶＣルーティング方法をインプリメントすることが可能ないかなるデバイスまたはデバイスも、本発明の意志決定支援システム機能をインプリメントするために使用されてもよい。
【００４６】
メモリ１４２０は揮発性及び不揮発性のデータ記憶装置を含んでもよい。そして、一つ以上の電気的、磁気的、光学的メモリ（例えばランダムアクセスメモリ（ＲＡＭ）、キャッシュ、ハードディスクまたは他のメモリ素子）を含む。メモリは、特定のデータへの速度アクセスに、キャッシュを有してもよい。メモリ１４２０はまた、コンパクトディスクに接続されてもよい。読取り専用メモリ（ＣＤ−ＲＯＭ）ディジタル・ビデオ・ディスク  メモリ（ＤＶＤ−ＲＯＭ）、ＤＶＤ読み書き入力、テープ装置、その他の、システムにデータを直接アップロードすることを可能とするリムーバブル・メモリー素子を含む。
【００４７】
ネットワークコネクション・インターフェース１４３０は、ネットワークから信号を送受信することが可能な通信デバイス、モデム、ネットワークインターフェイスカード、トランシーバまたは他のいかなるデバイスに接続されてもよい。ネットワークコネクション・インターフェース１４３０は、ルーターノード１０４をネットワークに接続するために使用してもよい。ルーターノード１０４のコンポーネントは、例えば、電気的なバス１４４０を経て接続されてもよく、無線で接続されてもよい。
【００４８】
クライアントソフトウェア、及びデータベースは、メモリ１４２０からコントローラ／プロセッサ１４１０によってアクセスされてもよく、例えば、同様にデータベース・アプリケーション（ワードプロセッシングアプリケーション）を含んでもよい。あるいは本発明の決定の機能をサポートするコンポーネントを含んでもよい。ルーターノード１０４は、例えばいかなるオペレーティングシステム（例えばＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）、ＬＩＮＵＸまたはＵＮＩＸ（登録商標）をインプリメントしてもよい。クライアント、及びサーバ・ソフトウェアは、例えばいかなるプログラミング言語（例えばＣ、Ｃ＋＋、Ｊａｖａ（登録商標）またはＶｉｓｕａｌ  Ｂａｓｉｃ）で書かれてもよい。必ずしも必要ではないが、本発明は、少なくとも一部で、コンピュータで実行可能な命令で記述される。例えば、電子デバイス（例えば汎用コンピュータ）によって実行されるプログラム・モジュールが挙げられる。一般に、プログラム・モジュールは、ルーチン・プログラム、オブジェクト、コンポーネント、データ構造等の特定のタスクを実行し、あるいは特定の抽象的なデータタイプをインプリメントするものを含む。さらに、当業者は、本発明の実施が、ネットワーク、コンピューティング環境で行われることを理解するであろう。この環境には、パソコン、ハンドヘルドデバイス、マルチプロセッサーシステム、マイクロプロセッサあるいはプログラム可能な家電、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、などを含む多くのタイプのコンピュータシステムが含まれる。
【００４９】
一般に、プログラム・モジュールは、ルーチン・プログラム、オブジェクト、コンポーネント、データ構造等の特定のタスクを実行しあるいは特定の抽象的なデータタイプをインプリメントするものを含む。さらに、当業者は、本発明の実施がネットワーク、コンピューティング環境で行われることを理解するであろう。この環境には、パソコン、ハンドヘルドデバイス、マルチプロセッサーシステム、マイクロプロセッサに基づくかプログラム可能な家電、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、などを含む多くのタイプのコンピュータシステムが含まれる。
【００５０】
実施例は、また、タスクが通信ネットワークで連結される（ハードウエアリンク、ワイヤレス・リンク、あるいはそれらの組合せによって）、ローカル、及び遠隔処理デバイスによって遂行される分散コンピューティング環境において実施されてもよい。
【００５１】
本発明の範囲内の実施例はまた、コンピュータ可読のメディアを含んでもよい。そして、コンピュータ実行可能な命令またはデータ構造を実行し、記憶する。この種のコンピュータ可読のメディアは、一般のまたは専用コンピュータによってアクセスし得るいかなる利用可能なメディアでもあってもよい。例えば、この例に限らないが、この種のコンピュータ可読のメディアはＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたは他の光学ディスク記憶装置（磁気ディスク記憶装置または他の磁気記憶装置）を有してもよい。又は所望のプログラムコードを実行するかまたは記憶するために、コンピュータ実行可能な命令またはデータの形での構造で使用され得る他のいかなる媒体をも意味する。情報がネットワークまたはコンピュータへの他の通信接続（ハードワイヤード、ワイヤレス、あるいはこれらの組合せ）を通じて転送されるかまたは提供されるときに、コンピュータは、適切に、この接続を、コンピュータ可読媒体と同じように認識する。したがって、この種の接続は、コンピュータ可読媒体として捉えることができる。また、上記の組合せもコンピュータ可読のメディアの範囲内に含まれなければならない。
【００５２】
コンピュータ実行可能な命令は、例えば、特定の機能または機能のグループを実行するための、汎用コンピュータ、専用コンピュータまたは特殊目的処理デバイスと捉えることができる、命令及びデータを含む。コンピュータ実行可能な命令は、スタンドアローンまたはネットワーク環境のコンピュータによって実行されるプログラム・モジュールを含む。通常、プログラム・モジュールはルーチン、プログラム、オブジェクト、コンポーネント及びデータ構造、等を含む。これらは、特定のタスクを遂行するかまたは特定の抽象データタイプをインプリメントする。コンピュータ実行可能な命令、関連データ構造、及びプログラム・モジュールは、本願明細書において開示される方法のステップを実行するためのプログラムコード手段の実施例を表すものである。この種の実行可能命令の特定のシーケンスまたは関連データ構造は、この種のステップに記載されている機能をインプリメントするための対応する動作の実施例を表すものである。
【００５３】
前記説明が具体的な詳細を含んでいるが、いかなる形であれ請求項を制限するように、それらは解釈されてはならない。本発明に記載されている実施例の他の構成は、本発明の技術的範囲に属する。例えば、本発明の原則は、各々のユーザがこの種のシステムを個々に利用している個々のユーザに適用されてもよい。このことは、（多数の考えられるアプリケーションのいかなる一つも本願明細書において記載されている機能を必要としない場合であっても）各々のユーザが本発明の利点を利用することを可能にする。複数の電子デバイスの各々は、様々な形で、本願発明の内容を処理することができる。本願発明は、必ずしも、全てのエンドユーザによって使用される１つのシステムである必要はない。したがって、記載された具体例よりむしろ、添付の請求の範囲及びそれらの均等物が本発明を定義する。
【図１】
2011517903.tif 000003
【図２】
2011517903.tif 000004
【図３】
2011517903.tif 000005
【図４】
2011517903.tif 000006
【図５】
2011517903.tif 000007
【図６】
2011517903.tif 000008
【図７】
2011517903.tif 000009
【図８】
2011517903.tif 000010
【図９】
2011517903.tif 000011
【図１０】
2011517903.tif 000012
【図１１】
2011517903.tif 000013
【図１２】
2011517903.tif 000014
【図１３】
2011517903.tif 000015
【図１４】
2011517903.tif 000016
【国際調査報告】
2011517903.tif 000017
2011517903.tif 000018