"Dragonflyネットワーク内のターゲットノードから宛先ノードまでの複数のネットワークパスから、1または複数のルーティングテーブルに基づきネットワークパスを選択することによって、データをルーティングするように動作する少なくとも1つのルータを備える、Dragonflyプロセッサ相互接続ネットワークを含むマルチプロセッサコンピュータシステム。前記ルーティングテーブルは、グローバルルーティングテーブルとローカルルーティングテーブルを備える、請求項1記載のマルチプロセッサコンピュータシステム。前記ルーティングテーブルは、最小テーブルと非最小テーブルを備える、請求項1記載のマルチプロセッサコンピュータシステム。1または複数の前記ルーティングテーブルが使用されることによって、前記ターゲットノードと前記宛先ノードとの間に適応型ルーティングが提供される、請求項1記載のマルチプロセッサコンピュータシステム。適応型のルーティングすることは、経路の選択において、近隣ルータからのネットワーク輻輳情報と、前記近隣ルータからのネットワークリンク失敗情報とのうちの1または複数を使用することからなる、請求項1記載のマルチプロセッサコンピュータシステム。マルチプロセッサコンピュータシステムの動作方法であって、前記動作方法は、Dragonflyネットワーク内のターゲットノードから宛先ノードまでの複数のネットワークパスから、1または複数のルーティングテーブルに基づきネットワークパスを選択することによって、データをルーティングするステップを備える、マルチプロセッサコンピュータシステムの動作方法。前記ルーティングテーブルは、グローバルルーティングテーブルとローカルルーティングテーブルとを備える、請求項6記載のマルチプロセッサコンピュータシステムの動作方法。前記ルーティングテーブルは、最小テーブルと非最小テーブルとを備える、請求項6記載のマルチプロセッサコンピュータシステムの動作方法。1または複数の前記ルーティングテーブルが使用されることによって、前記ターゲットノードと前記宛先ノードとの間に適応型ルーティングが提供される、請求項6記載のマルチプロセッサコンピュータシステムの動作方法。適応型のルーティングすることは、経路の選択において、近隣ルータからのネットワーク輻輳情報と、前記近隣ルータからのネットワークリンク失敗情報とのうちの1または複数を使用することからなる、請求項6記載のマルチプロセッサコンピュータシステムの動作方法。同様に、ネットワークトポロジーや、処理ノードどうしの結合に使用する接続パターンによってもパフォーマンスが影響を受けるので、積極的な研究の余地がある。数十台のプロセッサを備えたシステム内で各ノードを相互に直接つなぐことは実用的でなく、プロセッサの数が数千台に達した場合にはほとんど不可能となる。さらに、特に長距離接続または高速の光ファイバリンクを必要とする場合には、通信インターフェース、ケーブル、その他の要素のコストによって、不十分な設計または非効率なプロセッサ相互接続ネットワークのコストが大幅にかさんでしまう。そのため、プロセッサ相互接続ネットワークの設計者にとっては、総リンク数、プロセッサ相互接続ネットワークのコストおよび複雑性を制御しながら、様々な処理ノード間に高速かつ効率的な通信を提供することが課題になっている。したがって、ネットワークのトポロジーまたはマルチプロセッサコンピュータシステムにおいて、どのように1つの処理ノードを別のノードにどのようにしてつなぐか決定するために使用される方法が関心範囲となる。本発明は1例において、複数のプロセッサノードと複数のルータとを設けたDragonflyプロセッサ相互接続ネットワークを実装したマルチプロセッサコンピュータシステムを備える。ルータは、例えばローカルルーティングテーブルおよびグローバルルーティングテーブル、最小および非最小ルーティングテーブルのような、1または複数のルーティングテーブルに基づき、Dragonflyネットワーク内のターゲットノードから宛先ノードまでの複数のネットワークパスの中からネットワークパスを選択することによって、データをルーティングするように動作する。以下の本発明の例示的な実施形態の詳細な説明では、特定の例を図面と例証の方法により参照する。これらの例は、当業者が本発明を実施するために十分詳細に説明され、どのようにして本発明を様々な目的または実施形態に応用できるか例証する役割を果たす。本発明の他の実施形態が存在し、それらは本発明の範囲内に入り、また、本発明の課題または範囲から逸脱しない限り、論理的、機械的、電気的な変更、さらにその他の変更を加えることができる。ここで記述している本発明の様々な実施形態の特徴または制限は、これらが援用されている例示的な実施形態にとって必須であるが、本発明全体を制限することはなく、また、本発明、およびその要素、操作、用途のいかなる参照も本発明全体を限定することはなく、これら例示的な実施形態を定義するためだけに貢献する。したがって、以下の詳細な説明は、添付の請求の範囲によってのみ定義される本発明の範囲を限定するものではない。相互接続ネットワークは、ハイエンドルータおよびスイッチ用のスイッチングファブリックとしての、マルチプロセッサ内のプロセッサおよびメモリを接続するために、そして、I/Oデバイスを接続するために幅広く使用されている。マルチプロセッサコンピュータシステム内のプロセッサおよびメモリのパフォーマンスが向上を続けるに従って、相互接続ネットワークのパフォーマンスがシステム全体のパフォーマンスを決定する中心的役割となっている。ネットワークのレイテンシと帯域幅は、遠隔メモリアクセスレイテンシおよび帯域幅の大部分を確立する。一般に、優れた相互接続ネットワークは、利用可能な技術の能力と制約とから大きく離れない範囲で設計される。例えば少数のポートを維持してポート毎の帯域幅を増加させるのではなく、増加した帯域幅を使ってルータ毎のポートの数を増やす高基数ルータの使用は、ルータピン帯域幅を増加させることによって、動機付けられた。高基数ネットワークを採用した最初のシステムの1つである、クレイ社のBlackWidowシステムは、折り返しクロスFoldedClosトポロジーの変異型と基数64radix-64ルータを使用する。これは従来の低基数3次元トーラスネットワークからの重要な新発展である。近年、経済的な光信号通信の登場によって、長距離チャネルを伴ったトポロジーが可能である。しかしこれらの長距離型の光チャネルは、短距離の電気チャネルよりも依然として遥かに高額である。そこで、ルータをグループ化してネットワークの有効基数をさらに増加させる先進の光信号通信技術を利用したDragonflyトポロジーが導入された。ネットワークのパフォーマンスとコストの両方は、相互接続ネットワークのトポロジーによって大きく左右される。ネットワークコストは、チャネルコスト、特に長距離型でグローバルなキャビネット間チャネルのコストによってそのほとんどが占められる。そのためグローバルチャネルの数を減らすことによって、ネットワークコストも大幅に低減できる。パフォーマンスを低下させずにグローバルチャネルの数を減らすには、平均パケットがトラバースするグローバルチャネルの数を減らす必要がある。Dragonflyトポロジーは、最小ルーティングを使用することによって、各パケットがトラバースするグローバルチャネルの数を1にまで低減する。Dragonflyトポロジーの例この1つのグローバル直径globaldiameterを達成するには、約2√Nここで、Nはネットワークのサイズであるという非常に高基数のルータを使用する。基数64のルータは既に導入されており、また基数128radix-128も実行可能であるが、従来の非常に高基数のルータ技術を使用して各パケットが1グローバルホップのみに限定される場合には、8K~1Mノードの規模のマシンを作るために、これよりも遥かに高い数百または数千という基数が必要となる。各ノードにつき数百台または数千台のポートを設けずに、ルータによってこの非常に高基数の恩恵を達成するために、Dragonflyネットワークトポロジーは、サブネットワーク内に接続したルータグループを、非常に高基数の仮想ルータとして使用することを提案する。この非常に高い有効基数によって、全ての最小ルータが最大1本のグローバルチャネルをトラバースするネットワークを構築することが可能になる。さらに先進の光信号通信技術の能力を利用することによって、グローバルチャネルの物理長も増す。Dragonflyトポロジー上の幅広いトラフィックパターンにおいて優れたパフォーマンスを達成するには、グローバルチャネルにかけて効率的な負荷分散が可能なルーティングアルゴリズムを選択することが必要となる。グローバル適応型ルーティングUGALは、ルーティング決定を行うソースルータにおいてグローバルチャネルの負荷を利用できる場合に、このような負荷分散を実行することが可能である。しかしDragonflyトポロジーを用いた場合、ソースルータは、当該のグローバルチャネルに接続されていないことがほとんどである。したがって適応型ルーティング決定は、遠隔または間接的な情報に基づき行われる。従来のUGALローカルキュー占有率を使用してルーティング決定を行うを使用している場合には、この決定の間接的な性質は、レイテンシとスループット両方の劣化を招く。我々は、DragonflyネットワークトポロジーのUGALルーティングアルゴリズムに対しこの制限を克服する2つの修正を加えることを提案したところ、グローバル情報を使用した理想的な実現に近いパフォーマンス結果が得られた。UGALUGAL-VCHに選択的な仮想チャネル分別を追加することで、最小パスおよび非最小パス間でのローカルチャネル共有による帯域幅の劣化が排除される。クレジットラウンドトリップレイテンシを、グローバルチャネル輻輳の感知と、この輻輳情報の上り伝播UGAL-CRの両方に使用すると、輻輳の感知にキュー占有率のみを使用した場合よりも遥かに力強いバックプレッシャが提供され、レイテンシの劣化が排除される。高基数ネットワークでは、低基数ネットワークと比べてネットワークの直径は縮小するが、ケーブルは長距離化する。信号通信技術の進化と近年におけるアクティブ光ケーブルの開発によって、長距離ケーブルを使用した高基数トポロジーの実現が容易化される。相互接続ネットワークは、パッケージング階層に組み込まれる。最下位レベルでは、ルータは、回路基板を介して接続され、次にこれらがバックプレーンまたはミッドプレーンを介して接続されている。1または複数のバックプレーンがキャビネット内に梱包され、且つ複数のキャビネットが電力ケーブルまたは光ケーブルによって接続されることによって、完全なシステムが形成される。多くの場合、ネットワークコストの大部分は、グローバルキャビネット間ケーブルとこれに関連するトランシーバによって占められる。ネットワークコストを最小化するためには、トポロジーは、利用可能な相互接続技術の特性、例えばコストおよびパフォーマンスと一致している必要がある。距離が増すに従って表皮効果と誘電体吸収による信号減衰が直線的に増加するため、電力ケーブルの最大帯域幅は、ケーブルの長さが長くなると低下する。一般的な高性能信号通信速度10~20Gb/sと技術パラメータの場合、電気信号通信パスは、回路基板内で約1m、ケーブル内で10mに制限される。これよりも長い距離では、信号通信速度を低減するかまたはリピータを挿入して、減衰を克服しなければならない。光信号通信の歴史上、高コストが原因で、光信号通信の使用は非常に長距離や、コスト度外視でパフォーマンスを求める用途に限定されてきた。光ケーブルの固定費用は高いが、データを長距離にわたって銅ケーブルのデータ速度の数倍の速度で伝送する能力のために、光ケーブルの単位距離当たりのコストは、電力ケーブルよりも低くなる。現在の技術を使用して利用できるデータに基づくと、損益分岐点は10mである。10m未満の距離では、電気信号通信の方が安価である。10mを超えると、光信号通信がより経済的である。Dragonflyトポロジーは、このコストと距離の関係を利用する。グローバルケーブルの数を減らすことで、光信号通信の高い固定間接費が最小化され、グローバルケーブルを長くすることで、光ファイバのより低い単位当たりのコストの利点が最大化される。Dragonflyは、本数の少ない長距離のグローバルケーブルを使用するため、1kノード以上のネットワークではDragonflyのドルコストも平坦化したバタフライFlattenedButterflyと好意的に比較され、4kノードまでのものについては約10の節約、さらに4kノード以上のものについては約20のコスト節約を、平坦化したバタフライトポロジーに関連して示している。これに比較すると、折り返しクロスおよび3次元トーラスネットワークは、大きなネットワークの直径をサポートするために多数のケーブルが必要であることで問題を抱える。1kノードだけのネットワークでは、Dragonflyのコストは3次元トーラスネットワークのコストの62、折り返しクロスネットワークの50である。このネットワークコストの低減はネットワーク消費電力の低減と直接相関するので、大型ネットワークにとっては、また、環境に優しいことが望ましい設置にとっては大きな利点となる。ここで提示しているDragonflyネットワークの例示的な実施形態は、1つのルータグループを仮想ルータとして使用することによって、どのようにネットワークの有効基数が増加するか、さらに、これによってどのようにネットワークの直径、コスト、レイテンシが低減するか示している。Dragonflyトポロジーは、ネットワークにおけるグローバルケーブルの本数を減らしながらグローバルケーブルの長さを増加させるので、先進のアクティブ光ケーブル固定費用は高いが、単位長さ当たりのコストは電力ケーブルよりも低いを使用した実現に特に適している。Dragonflyネットワークは、グローバルチャネルにアクティブ光ケーブルを使用することによって、同じ帯域幅を用いる平坦化したバタフライと比べて20、やはり同じ帯域幅を用いる折り返しクロスネットワークと比べて52のコスト低減が可能である。Dragonflyネットワークトポロジーの1例を示すために、Dragonflyトポロジーと、後述するルーティングアルゴリズムの例との説明において次の記号を使用する:Nネットワーク端末の数、p各ルータに接続された端末の数、a各グループにおけるルータの数、kルータの基数、k_グループの有効基数または仮想ルータ、h他のグループに接続するために使用された各ルータ内のチャネルの数、gシステム内に存在するグループの数、q出力ポートのキュー深度、qvcそれぞれの出力VCのキュー深度、Hホップカウント、Outiルータ出力ポートi。Dragonflyトポロジーは、図1に示すように、ルータ104、105、106、グループ101、102、103、システム、の3レベルで構成された階層ネットワークである。ルータレベルにて、各ルータはp個のノードに接続し、a-1個のローカルチャネルは同じグループ内の他のルータに接続し、h個のグローバルチャネルは他のグループ内のルータに接続している。したがって各ルータの基数または度数は、k=pah-1と定義される。グループは、図1の符号101で示すように、ローカルチャネルで形成されたグループ間相互接続ネットワークを介して接続したa個のルータで構成されている。各グループは端末へのap個の接続を有し、グローバルチャネルへのah個の接続を有しており、また、1グループ内の全てのルータは、基数k’=aphを伴う仮想ルータとして集合的に機能する。この非常に高い基数k’>>kにより、非常に小さいグローバル直径でのシステムレベルネットワークの実現が可能になる任意の2つのノード間の最小パス上に、最大数の高価なグローバルチャネルを設けている。最大でg=ah1までの数のグループN=apah1個の端末を1のグローバル直径に接続することができる。これに対し、基数k個のルータで直接構築したシステムレベルネットワークでは、より大きなグローバル直径が必要となる。最大サイズN=apah1のDragonflyでは、各1対のグループの間には厳密に1つの接続しか存在しない。これよりも小規模のDragonflyでは、各グループ以外との接続以外のグローバル接続の方が、他のグループとの接続よりも多い。これらの追加的なグローバル接続は、複数のグループにかけて分布しており、この複数のグループは、少なくとも_ah1g_本のチャネルで接続した各1対のグループ毎にまとめられている。Dragonflyパラメータa、p、hは、任意の値であってよい。しかしチャネル負荷を分散させるために、この例のネットワークは、a=2p=2hを有する。各パケットは、その経路に沿って、1本のグローバルチャネルと1本の端末チャネルの合計2本のローカルチャネルグローバルチャネルの各終端部分につき1本ずつをトラバースするので、この比率によってバランスが保たれる。グローバルチャネルは高価であるため、或る実施形態では、ローカルチャネルと端末チャネルを過剰供給して高価なグローバルチャネルが十分に利用される状態を保つ方法によって、この2:1の比率からの逸脱を行っている。つまり、このような例では、a≧2h、2p≧2hとなるようにネットワークのバランスをとっている。バランスのとれたDragonflyのスケーラビリティを図2に示す。有効基数を増加することでDragonflyトポロジーは高度にスケーラブルとなり、基数64ルータを用いた場合、トポロジーは、わずか3のホップ数でネットワークの直径256kノード以上にまでスケーリングされる。図1のグループ内およびグループ間ネットワークには、任意のネットワークを使用できる。本明細書で提示する例は、両方のネットワークについて、1次元の平坦化したバタフライまたは完全接続型トポロジーを使用している。図3に、Dragonflyの単純な例を示す。ここではp=h=2ルータ1つにつき処理ノード2つ、そして、各ルータ内には他グループに接続したチャネル2本が設けられている、a=4各グループ内にルータ4つであり、これが、k=7基数7のルータを用いて、N=72ネットワーク内の72ノードにスケーリングされる。図3のグループG0が8つのグローバル接続と8つのノード接続を有するので、仮想ルータを使用することによって、有効基数がk=7からk’=16にまで増加する。グループ内ネットワークにより高次元のトポロジーを使用することによって、グローバル基数k’をさらに増加することができる。さらに、このようなネットワークは、グループ内でのパッケージ化の局所参照性も利用する。例えば図4の符号401が示す2次元の平坦化したバタフライは、図5に示すグループと同じk’を有するが、より多くの帯域幅をローカルルータに提供することによって、パッケージ化局所参照性を利用する。図4の符号402では、3次元の平坦化したバタフライを使用して、有効基数をk’=16からK’=32に増加することによって、図1のものと同じk=7のルータを使用してトポロジーを最大N=1056にまでスケーリングできるようにしている。Dragonflyのような高基数ネットワークの端末帯域幅を増加するために、チャネルスライシングを採用することができる。チャネルを幅広くするのではなくこの場合、ルータ基数が減少してしまう、複数のネットワークを並列接続して容量を追加することができる。同様に或る実施形態では、Dragonflyトポロジーは、ネットワーク容量を追加するために、並列ネットワークを利用することもできる。これに加えて、ここまで説明したDragonflyネットワークでは、ネットワーク内の全てのノードに均等な帯域幅を仮定した。しかしこのような均等な帯域幅が不要な場合には、いくつかのグループからグループ間チャネルを除去することによって、帯域幅のテーパリングを実現することが可能である。Dragonflyルーティングの例様々な最小および非最小ルーティングアルゴリズムは、Dragonflyトポロジーを使用して実現できる。ローカル情報を使用するグローバル適応型ルーティングの或る実施形態は、中間負荷にて、スループットの制限と非常に高いレイテンシを招く。これらの問題を克服するために、我々はグローバル適応型ルーティングに、理想的なグローバル適応型ルーティングの実現にアプローチするパフォーマンスを提供できる新たなメカニズムを導入する。Dragonflyにおける、グループGs内のルータRsに取り付けたソースノードsからグループGd内のルータRdに取り付けた宛先ノードdまでの最小ルーティングが、1本のグローバルチャネルをトラバースし、これは次の3つのステップで達成される:ステップ1:Gs_=Gdであり且つRsがGdと接続していない場合、Gs内でRsからRaGdへのグローバルチャネルを有するルータまでをルーティングする。ステップ2:Gs_=Gdである場合、グローバルチャネルを、RaからGd内のルータRbに到達するまでトラバースする。ステップ3:Rb_=Rdである場合、Gd内でRbからRdまでルーティングする。この最小ルーティングは、負荷分散トラフィックには上手く適応するが、これと対抗するトラフィックパターン上では満足なパフォーマンスが得られない。対抗するトラフィックパターンを負荷分散させるためには、ヴァリアントValiantのアルゴリズムをシステムレベルに適用して、各パケットをまずランダムに選択した中間グループGiに、次にその最終宛先dにルーティングすることができる。ヴァリアントのアルゴリズムをグループに適用することによって、グローバルチャネルとローカルチャネルの両方の上の負荷は、十分に分散される。このランダム型の非最小ルーティングは、最大で2本のグローバルチャネルをトラバースし、また、次の5つのステップを必要とする:ステップ1:Gs_=Giであり且つRsがGiと接続していない場合、Gs内でRsからRaGiへのグローバルチャネルを有するルータまでをルーティングする。ステップ2:Gs_=Giである場合、グローバルチャネルを、RaからGi内のルータRxに到達するまでトラバースする。ステップ3:Gi_=Gdであり且つRxがGdと接続していない場合、Gi内でRxからRyGdへのグローバルチャネルを有するルータまでをルーティングする。ステップ4:Gi_=Gdである場合、グローバルチャネルを、RyからGd内のルータRbに到達するまでトラバースする。ステップ5:Rb_=Rdである場合、Gd内でRbからRdまでをルーティングする。ルーティングデッドロックを防ぐためには、図5に示すように、最小ルーティングに2本の仮想チャネルVCを採用し、また、非最小ルーティングの場合は3本の仮想チャネルが必要である。これらの仮想ルータを指定することで、ルーティングによって生じるチャネル依存が全て排除される。いくつかの用途では、プロトコルデッドロックを回避するために追加の仮想チャネルが必要になることがある。例えば共有メモリシステムでは、メッセージの要求と応答のために仮想チャネルの別個のセットが必要になることがある。次のようなDragonflyトポロジーのための様々なルーティングアルゴリズムが評価されてきた:最小MIN:先述したように最小パスを経る。バリアントVAL[32]:先述したランダム型の非最小ルーティング。ユニバーサルグローバル適応型負荷分散[29]:ネットワークを負荷分散するために、UGAL-G,UGAL-LUGALが、MINとVALの中からパケットバイパケットに基づき選択する。この選択は、ネットワーク遅延を推定するためにキュー長とホップカウントを使用し、遅延が最も小さいパスを選択することによって行われる。我々は、次の2つのバージョンのUGALを実現する。UGAL-L:現在のルータノードでのローカルキュー情報を使用する。UGAL-G:Gs内の全てのグローバルチャネルのためのキュー情報を使用する他のルータ上のキュー長がわかっていると仮定する。ローカルチャネルではなくグローバルチャネルの負荷分散が必要なので、これは実現が困難である一方で、UGALの理想的な実現を表すものである。図6に示すように、BENIGNパターンと、これに対抗する合成トラフィックパターンとの両方を使用して、異なるルーティングアルゴリズムを評価する。符号601の均等なランダムトラフィックと、これに対抗する符号602のトラフィックとの両方を使用して、4つのルーティングアルゴリズムについてのレイテンシ対供給負荷を示す。合成トラフィックパターンを使用することで、ネットワークを十分に評価するためにトポロジーとルーティングアルゴリズムを強調できるようになる。図6の符号601で示すように、均等ランダム型URのようなBENIGNトラフィックでは、MINで十分に低レイテンシと高スループットを提供できる。VALは、その負荷分散によってグローバルチャネル上の負荷が2倍になるので、ネットワーク容量の約半分を達成する。UGAL-GとUGAL-Lの両方はMINのスループットと似ているが、これらの方が飽和付近でのレイテンシが若干高い。この若干高いレイテンシは、並列またはグリーディ割当の使用によって生じる。並列またはグリーディ割当の使用では、各ポートにてルーティング決定は、並列に行われる。逐次割当を使用することによって、より複雑なアロケータの犠牲の上にレイテンシは、短縮する。Dragonflyでの適応型ルーティングは、ルータ出力ではなく、グローバルチャネル、グループ出力のバランスを取る必要があるため、課題が伴う。これによって、間接的なルーティング問題が生じる。各ルータは、グローバルチャネルの状態に間接的にのみ依存するローカル情報だけを使用して、使用するグローバルチャネルを選ぶ。先行技術によるグローバル適応型ルーティング方法は、ネットワーク輻輳を正確に推定するために、ローカルキュー情報、ソースキュー、出力キューを使用する。これらのケースでは、開始させた経路上の輻輳を直接示すローカルキューは、グローバル輻輳の正確なプロキシである。しかしDragonflyトポロジーを使用した場合には、ローカルキューは、ローカルチャネルにかかるバックプレッシャを介してグローバルチャネル上の輻輳を感知するだけである。ローカルチャネルを過剰提供した場合、ソースルータが輻輳を感知する以前に、過負荷状態の最小経路上で著しい数のパケットをエンキューしなければならない。これによって、先に図6の符号602で示したように、スループットとレイテンシが低下してしまう。UGAL-Lに伴うスループットの問題は、1本のローカルチャネルで最小および非最小トラフィックの両方を扱うことが原因で生じる。例えば図7では、R1のパケットは、gc7を使用する最小パスと、gc6を使用する非最小パスとを設けている。両パスは、同じR1からR2までのローカルチャネルを共用する。両パスが同じローカルキューを共用ししたがって、同じキュー占有率を有する、最小パスの方が非最小パスよりも短いためグローバルホップ:1対2、常に最小チャネルが選択される。これは、たとえパスが飽和状態にある時でも同じである。これによって最小グローバルチャネルが過負荷状態となるため、この最小チャネルと同じルータを共用している非最小グローバルチャネルは、利用されなくなってしまう。UGAL-Gを使用することで、最小チャネルが優先され、負荷は、全ての他のグローバルチャネルにかけて均等に分散される。これに対しUGAL-Lを使用することで、最小グローバルチャネルを含んでいるルータの非最小チャネルが利用されなくなり、その結果、ネットワークスループットは、低下する。この制限を克服するために、それぞれの仮想チャネルUGAL-LVCを使用することによって、キュー占有率を最小成分と非最小成分に分けるようにUGALアルゴリズムを修正する:ifqmvcHm≦qnmvcHnmrouteminimally;elseroutenonminimally;ここで、添字mは最小パスを、nmは非最小パスを示す。図5の仮想チャネル割当を使用すれば、qmvc=qVC1およびqnmvc=qVC0となる。比較すると、UGAL-LVCはWCトラフィックパターン内のUGAL-Gのスループットと一致するが、URトラフィックでは、スループットの制限により、スループットが約30低下する。ほとんどのトラフィックを非最小で送信する必要があるWCトラフィックの場合、最小キューが負荷の大きな状態となっているため、UGAL-LVCが上手く機能する。しかし、ほとんどのトラフィックを最小で送信する必要がある時に負荷分散されたトラフィックを用いると、それぞれの仮想チャネルがチャネル輻輳の正確な表示を提供せず、その結果、スループットが低下してしまう。この制限を克服するために、我々は、最小パスと非最小パスが同一の出力ポートから開始する場合にのみキュー占有率を最小成分と非最小成分に分けるように、UGALアルゴリズムをさらに修正する。我々のハイブリッド修正版のUGALルーティングアルゴリズムUGAL-LVCHは、次のとおりである:ifqmHm≦qnmHnmOutm_=Outnm||qmvcHm≦qnmvcHnmOutm=Outnmrouteminimally;elseroutenonminimally;UGAL-LVCと比較すると、UGAL-LVCHが提供するスループットは、WCトラフィックパターン上のものと同じであるが、URトラフィック上のUGAL-Gのスループットに一致し、それ故に、飽和状態に近い0.8の供給負荷での高い方のレイテンシのほぼ2倍となる。WCトラフィックでは、UGAL-LVCHは、中間レイテンシもUGAL-Gのものと比べて高くなる。このUGAL-Lの高い中間レイテンシは、輻輳を感知する前に、ソースと輻輳ポイントとの間のチャネルバッファが最小経路で送られたパケットで充填されることで生じる。我々の研究では、非最小経路で送られたパケットはUGAL-Gと比較可能なレイテンシ曲線を有する一方で、最小経路で送られたパケットは著しく高いレイテンシに遭遇することが示されている。入力バッファが増加すると、最小経路で送られたパケットのレイテンシが増加し、パケットのレイテンシは、バッファの深さに比例する。レイテンシ分布のヒストグラムは、次の2つの明白な分布を示している。1つは、非最小パケットについてのレイテンシが低い大きな分布であり、他の1つは、パケット数が制限されているが、最小パケットについてのレイテンシが遥かに高い分布である。UGAL-Lに伴うこの問題を理解するために、図7に示すDragonflyグループの例において、R1のパケットは、gc0を介して最小のルーティング、またはgc7を介して非最小のルーティングのいずれを行うかについてのグローバル適応型ルーティング決定を行っていると仮定する。ルーティング決定は、グローバルチャネル利用の負荷分散を行う必要があり、またチャネル利用をグローバルチャネルq0、q3に関連したキューから得られることが理想的である。しかし、q0、q3キュー情報はR0、R2でしか利用できず、R1ではまだ利用できる状態にないので、ルーティング決定は、R1で利用できるローカルキュー情報を介して間接的にしか行えない。この例では、q1はq0の状態を反映し、q2はq3の状態を反映する。q0またはq3のどちらかがフル状態である場合には、図7の矢印で示すように、フロー制御によってq1とq2にバックプレッシャが提供される。その結果、安定した状態の測定が得られ、スループットの正確な測定にこれらのローカルキュー情報を使用できるようになる。スループットは、レイテンシが無限大になるとまたはキュー占有率が無限大になると供給負荷として定義されるため、このローカルキュー情報で十分である。しかしq1がgc0の輻輳を反映でき、且つR1がパケットを非最小経路で送ることができるようにするには、q0は、完全にフル状態になる必要がある。したがってローカル情報を使用するには、数個のパケットを犠牲にして正確な輻輳を決定することを要し、その結果、最小で送られているパケットのレイテンシが遥かに高くなってしまう。負荷が増加するに従って、最小経路で送られたパケットのレイテンシは増加し続けるが、より多くのパケットが非最小で送られるようになり、その結果、飽和までの平均レイテンシは、低下する。ローカルキューがグローバル輻輳の優れた推定を提供できるようにするには、グローバルキューが完全にフル状態となり、ローカルキューに向けて力強いバックプレッシャを提供する必要がある。バックプレッシャの力強さはバッファの深さに反比例し、バッファが深いほどバックプレッシャの伝播に時間がかかり、バッファが浅いほど遥かに力強いバックプレッシャが提供される。バッファサイズが減少するに従って、バックプレッシャが力強くなるため、中間負荷におけるレイテンシは、低下する。しかし使用するバッファの数を減らすと、ネットワークスループットの低下という犠牲を払うことになる。高い中間レイテンシを克服するために、我々は、クレジットラウンドトリップレイテンシを使用して、高速な輻輳の感知とレイテンシの低減を図ることを提案する。図8に示すクレジットベースのフロー制御では、下流バッファについてクレジットカウントが維持される。パケットが下流に送られるに従い、適切なクレジットカウントが減少してゆくが、パケットが下流ルータを離れるとクレジットは上流に送り戻され、クレジットカウントが増加する。クレジットが戻るためのレイテンシはクレジットラウンドトリップレイテンシtcrtと呼ばれ、下流に輻輳がある場合にはパケットが直ぐに処理されないため、結果としてtcrtが増加する。図8を参照すると、図8Aでは従来のクレジットフロー制御を示している。パケットが下流に送信されると1、出力クレジットカウントが減少し2、クレジットが上流に送り戻される3。図8Bでは、このスキームが、ネットワーク内の輻輳を推定するためにクレジットラウンドトリップレイテンシを使用するように修正される。減少している出力クレジットカウント2に加えて、CTQで示すクレジットタイムキュー内にタイムスタンプが押し込まれる。クレジットを上流に送り戻す前に4、クレジットが遅延し3、また、下流のクレジットが受信されると5、クレジットカウント並びにクレジットラウンドトリップレイテンシtcrtがアップデートされる。tcrtの値を、グローバルチャネルの輻輳を推定するために使用できる。我々は、上流クレジットを遅延させるためにこの情報を使用することで、バックプレッシャを力強くして、輻輳情報をより高速に上流に伝播できるようにした。各出力Oについて、tcrtOが測定され、量tdO=tcrtO-tcrt0がレジスタに記憶される。次に、クレジットを即座に上流に送り戻す代わりに、フリットを出力Oに送信する場合には、クレジットはtdO-min[tdo]だけ遅延される。グローバルチャネル上で送信されるクレジットは遅延しない。これによってこのメカニズムに周期ループが存在しないことが保証され、グローバルチャネルを十分に利用できるようになる。戻されるクレジットの遅延によって、力強いバックプレッシャを作るための、より浅いバッファが提供される。しかしバッファ全体が利用され、高負荷においてスループットの低下が生じないことを保証するために、全ての出力にかけてクレジットをtdの変動分だけ遅延させる必要がある。我々は、この変動を、min[tdo]値を求め、差分を使用することによって推定する。クレジットを遅延させることで、上流ルータが輻輳をキューが充填されるのを待つ時と比べてより高速で観察し、より優れたグローバル適応型ルーティング決定が得られるようになる。WCおよびURトラフィックの両方について、クレジットレイテンシUGAL-LCRを使用したUGAL-Lルーティングアルゴリズム評価が、深さ16と256のバッファを使用して調査される。UGAL-LCRはUGAL-Lと比べてレイテンシを著しく低下させ、UGAL-Gのレイテンシ近くにまでする。WCトラフィックについて、UGAL-LCRは、深さ16のバッファでレイテンシを最大35低下させ、また、深さ256のバッファで中間レイテンシを最大で20分の1に低下させた低下率はUGAL-Lとの比較。UGAL-Lとは違い、UGAL-LCRの中間レイテンシはバッファサイズと無関係である。URトラフィックについて、UGAL-LCRは、飽和付近にてレイテンシを、UGAL-LVCHと比較し最大50低下させる。しかし、UGAL-LCRとUGALLVCHの両方共、そのローカル情報が不正確なためにいくつかのパケットが非最小でルーティングされてしまうので、URトラフィックを伴うUGAL-Gのスループットには達しない。このスキームを実現した結果、各ルータ側に必要なのは次の3つの特徴であるため、複雑性にかかる間接費は最小であった。tcrtを測定するために個々のクレジットの追跡、td値を記憶するためのレジスタ、クレジットを戻す際の遅延メカニズム。必要なtd記憶量は、Okレジスタのみが必要であるため最小量である。クレジットはデータフリット上にピギーバックされて戻されることが多く、また、次の上流でのデータフリットの送信を待つために、クレジットを遅延させる必要がある。提案したこのメカニズムに必要なことは、さらなる遅延を追加することだけである。個々のクレジットの追跡については、従来から、クレジットは、クレジットフロー制御においてクレジットのプールとして追跡されており、つまり、各出力仮想チャネルにつき1つのクレジットカウンタが維持され、このクレジットカウンタは、クレジットが受信されると増加する。UGAL-LCRの実現には、各クレジットを個別に追跡する必要がある。これは、図8Bに示すように、フリットが送信される度に、クレジットタイムスタンプキューCTQを使ってキューの末尾にタイムスタンプを押し、該当するクレジットが到着したらキューの先頭からタイムスタンプを取り出すことによって実行されうる。フリットとクレジットの割合は1:1であり、オーダリングを維持するので、ラウンドトリップクレジットレイテンシの測定には単純なキューで十分である。キューの深さはデータバッファの深さに比例していなければならないが、キューサイズは、輻輳の測定に不正確な情報を利用するために縮小されうる例えば、データバッファサイズの1/4のサイズのキューを設ければ、輻輳の測定を行うために、4個のクレジットのうちの1個のみを追跡すればよくなる。Dragonflyトポロジーにかかるコストも、平坦化したバタフライや他のトポロジーのコストと比較して優れている。平坦化したバタフライトポロジーは、中間ルータとチャネルを除去することによってButterflyのネットワークコストを低減する。その結果、平坦化したバタフライは、バランスの取れたトラフィック上での折り返しクロスと比べてコストが約50低減する。Dragonflyトポロジーは、ルータの有効基数を増加して、さらなるコスト低減およびネットワークのスケーラビリティを向上することによって、平坦化したバタフライを拡張する。各々64k個のノードを接続したDragonflyネットワークと平坦化したバタフライネットワークを比較したところ、平坦化したバタフライがグローバルチャネル用ルータポートの50を使用する一方で、Dragonflyはグローバル接続用ポートの25を使用することを示した。平坦化したバタフライは2つの次元を追加する必要があるが、Dragonflyは1次元である。さらにDragonflyでは、グループサイズを増加してネットワークのスケーリングが可能なので、より優れたスケーラビリティが得られるのに対し、平坦化したバタフライでは次元を追加する必要がある。Dragonflyは、ホップカウントがほぼ同一な状態であれば、より長い方のグローバルケーブルを相殺してグローバルケーブルの本数を減少させることによって、先進の信号通信技術に適合する、よりコスト効果的なトポロジーを提供する。ここで説明しているDragonflyネットワークの様々な実施形態も、Dragonflyが呈する間接的な適応型ルーティングの課題を克服する、グローバル適応型ルーティングの2つの新たなバリアントを備える。一般に、Dragonflyルータは、同一グループ内の別のルータに取り付けられているグローバルチャネルの状態に基づきルーティング決定を行う。この遠隔チャネルの状態を推論するためにローカルキュー占有率を使用する従来のグローバル適応型ルーティングアルゴリズムは、スループットとレイテンシとを低下させてしまう。そこで我々は、仮想チャネル分別の選択的な使用を導入することによって、帯域幅の減少を克服する。さらに我々は、チャネル輻輳を感知してこれを信号通信するために、クレジットラウンドトリップレイテンシも使用する。この2つの技術を組み合わせることによって、遠隔チャネル状態を完全に知得した理想的なアルゴリズムのパフォーマンスに近づくよう試みるグローバル適応型ルーティングアルゴリズムが得られる。Dragonflyネットワークにおける革新的な適応型ルーティングここでは、輻輳リンクまたはダウンしたリンクに基づき複数の正当な経路の中から選択を行うよう動作可能な、デッドロックを回避する適応型ルーティングを提供することによって、Dragonflyプロセッサ相互接続ネットワークのための向上したルーティング方法を提案する。この適応型ルーティング方法は、向上したルーティングパフォーマンスを提供することと、ダウンしたリンクまたはトラフィックの多いリンクを許容することを従来の方法よりも上手く行い、さらに帯域幅に悪影響を与えるクレジットを保留するのではなく、チャネル上の輻輳を明快に通信させる。或る実施形態では、ネットワーク経路は、例えば複数の異なる次元でのルーティングのような複数の最小経路からまず選択され、次に任意で、例えば輻輳リンクやダウンしたリンクを回避するためにランダム選択したホップを使用することによって、1または複数の非最小経路からさらに選択される。1例では、ルーティングの選択は、テーブルによって提示され、ネットワークの構成および状態に応じて、特定の経路、あるいは、最小経路または非最小経路に偏る可能性がある。例えば経路の選択が最高の効率のデフォルトによって最小ルーティングに偏るが、この偏りは、追加のトラフィックを任意または不必要に受信することから特定のネットワークリンクを保護するために、非最小ルーティングへの偏りに切り替わることもある。或る実施形態では、輻輳情報は、例えば出力キュー内のメッセージ数のカウントのような要素から予測される次のリンク輻輳を導出し、伝送中のクレジットやメッセージのような要因に基づき受信バッファ輻輳の推定を確立することによって利用される。ノードは、潜在的な受信側ノードに、平均的な次のリンク出力の輻輳について問い合わせ、ノードが輻輳リンクまたはダウンしたリンクの回避に基づきルーティング決定を行えるようにすることができる。図9は、本発明の例示的な実施形態と一致するDragonflyネットワークルータを示す。ここに示すルータブロックは、それぞれが入力/出力の対に対応した48個のタイルを備えている。タイルは8×6の行列に編成されているため、特定のタイルにおける入来パケットデータincomingpacketdataを、8列のうちの1つにつながる行にかけてルーティングし、次に、8列を上って、または下って、6行のうちの1つにルーティングし、適切なタイルに到達させて出力させる。さらなる実施形態では、チャネルは、複数の仮想チャネルと、仮想チャネル伝送中切り換えと、SECDEDのようなエラー修復と、さらに、ネットワークパフォーマンスを向上するために必要に応じて仮想チャネルへの動的割当を含む入力バッファリングとを特徴とする。再び図9の例を参照すると、タイルのうちの40個は外部ネットワークリンクに接続しており、8個はプロセッサノード域内のプロセッサコアに接続している。各タイルは、入力キュー、サブスイッチ、列バッファを備えている。入力キューは、シリアライザ/デシリアライザインターフェースからネットワークに送られたパケットを受信し、このパケットをどのようにルーティングするか決定する。パケットは、行バス上で、適当な列のサブスイッチへと送信される。サブスイッチは、このパケットを受信すると、これを適切な仮想チャネルへと切り換えてから、6列のバスのうちの1つを介して適切な行内の列バッファに送る。列バッファは、列内の6個のタイルからのパケットデータを収集し、これらをネットワークチャネル上で送信する。この例におけるDragonflyネットワークトポロジーは、2層の平坦化したバタフライトポロジーで構成された階層ネットワークである。第1層は、コンピュータキャビネットやシャーシのようなローカルグループ内の全てのルータチップを接続する2次元の平坦化したバタフライである。各グループは、非常に高基数のルータとして扱われ、また、単一次元の平坦化したバタフライall-to-allは、全てのグループを接続して、ここで示すDragonflyトポロジーの例の第2層を形成する。グループ内の第1の次元は便宜上緑色次元と呼ぶシャーシ内の16個のルータを接続する。グループ内の第2の次元は同様に黒色次元と呼ぶ、2キャビネットから成るグループ内の6個のシャーシを接続する。これは、図10のネットワークグループに示すネットワーク構成に反映されている。この図10のネットワークグループには、各シャーシにつき16個のルータ16個の列で示すで構成された6つのシャーシ6つの行で示すが図示されている。図10に示したようなグループは、図11に示すように、青色次元のリンクを使用してさらに相互結合する。これらのグループ間の青色リンクは、各グループを他の各グループと接続するものであり、接続可能な数は、この例では各グループにつき最大で240の青色リンク、または各システムにつき241グループである。各リンクは、例えば1つのリンクまたは1本の光ケーブルにつき4ポートというように、複数のポートを備えることができる。したがって4つのポートは、1本のケーブルでグループの各対に接続することになる。グループ数がより少ないシステムでは、各グループにつき240個の青色ポートのうちの未使用ポートを使用することによって、構成グループ間に追加の帯域幅を提供できる。これによって例えば、120個のグループで構成され、且つグループの各対を接続する8個のポートを提供しているネットワーク内部の各グループの対につき2つのリンクを設けることができる。このネットワークでは、ソースノードからターゲットノードまでルーティングされるパケットは、図9、図10、図11に示した次元のうち少なくとも1つの次元、しかしおそらくは3つ全ての次元をトラバースする。3つ全ての次元をトラバースするルーティングパスは、まず緑色次元にルーティングされ、次に黒色次元に送られて、ターゲットグループとつながっているグループ内の適切なノードに達し、その後に青色次元にルーティングされて目的のターゲットグループに到達する。次にパケットは、グループ内の緑色次元と黒色次元とにルーティングされ、ターゲットグループ内の目的のターゲットノードに到達することによって、ターゲット到達までに、3つの次元における5つのルーティングを辿ったことになる。一実施形態では、このネットワークは、適応型ルーティングと決定論的なルーティングの両方をサポートする。決定論的なルーティングは、ネットワーク輻輳に関係なく、所与のパケットをネットワーク上の定義済みの経路上に送信する。複数の決定論的なパスが利用可能である場合には、複数のパス間のトラフィックを分布させるために、宛先ノード、アドレス、または他の同様の特徴に基づき、決定論的なトラフィックをハッシュすることができる。或る実施形態では、ソース‐ターゲット間の全てのパケットは同一の決定論的なパスを使用するので、同一のソース‐ターゲット間を移動するパケットはターゲットに順番どおりに到達する。適応型ルーティングによって、パケットは、ネットワーク内の輻輳レベルに基づき、複数の異なる経路を使用できる。或る実施形態では、適応型ルーティングを使用すると、パケットは元の順番と違うバラバラの順番で到着してもよく、また輻輳のために最小パスの回避が指示された場合には、非最小パスを使用してもよい。Dragonflyにおける最小ルーティングは、パケットが所与の次元の最大1つのリンクをトラバースする際に生じる。したがって、例えば図10に示すようなグループ内の最小ルーティングは、緑色次元の最大1つのホップと、黒色次元の1つのホップとを使用する。異なるグループにあるノードどうしの間の最小パスは、各グループにおける、緑色次元の最大1つのホップと、黒色次元の1つのホップとを使用し、さらに追加の1つのホップを使用して、ソースグループからターゲットグループに移動する。最初に黒色または緑色次元のどちらかをトラバースすることができるので、ソースグループと宛先グループとの両方に複数の最小パスが存在する。グループ間に複数のリンクが存在する場合には、1つのパスにおける、ソースグループと宛先グループのどちらかの黒色または緑色次元でのホップを0にすることによって、最小パスの完了に必要な総ホップ数を5未満に減らすことができる。非最小ルーティングでは、ソースグループまたはターゲットグループ内の黒色または緑色いずれかの次元でのホップを複数にすることによって、総ホップ数を5以上にすることができる。ルータまでの最小パスまたは利用可能なパスに輻輳が発生している状況では、さらにホップを追加することによって、ターゲットへのメッセージ伝送速度を向上させる一方で、既に輻輳状態にあるネットワークリンクをさらに輻輳させないようにすることが望ましい。さらなる実施形態では、既に輻輳しているリンク周辺で同じパスを繰り返しルーティングした結果、輻輳したネットワーク領域をさらに作ってしまうことを回避するために、例えばパス選択をランダム化またはハッシュすることによって、トラフィックを利用可能なリンクにかけて拡散するべく試みる。このような実施形態の1つでは、図10に示したようなグループから中間ノードを1つ選択することで、メッセージをまず最小経路でこの中間ノードまでルーティングし、次に中間ノードからグループ内の最終ノードまでルーティングできるようになる。これによって、緑色次元と黒色次元の各々で最大2ホップ、またはグループ内の最小ルーティングにおいてはその2倍のホップ数となる。ルーティングは、ソースグループ内で非最小、ターゲットグループ内で非最小、またはソースグループおよびターゲットグループの両方において非最小であってよい。メッセージを、ソースグループとターゲットグループにおいて最小経路で、しかし両グループ間のリンクの輻輳を回避するために、ソースグループとターゲットグループの間の中間グループを経由させてルーティングする場合には、非最小ルーティングは、グループ間においても生じ得る。ソース、中間、ターゲットグループにおけるルーティングは、さらに、各グループでの輻輳に応じて最小または非最小であってよい。一実施形態では、所与のパケットまたはメッセージに使用するルーティングのタイプは、パケットヘッダ内のルーティング制御フィールドによって決定される。例えばルーティング制御記号は、パケット順序を保つことが望ましい時には、決定論的な非最小ハッシュ化ルーティングを使用すべきであることを示してもよい。パケットは、ターゲットノードをハッシュとして使用することによって、利用可能な複数のパスにかけて分布される。トラフィックは非最小ルーティングされるが、パケットをグループ内の様々な中間ノード間に分布させることによって、ホットスポットまたは輻輳は、減少する。決定論的な最小ハッシュ化ルーティングは、最小パス上でパケットのハッシュを提供するが、これは、緑色次元より前に黒色次元を、あるいは黒色次元より前に緑色次元というように、別の最小パス上でのルーティングを許可することによって所与グループ内のホップ数を減少させる。その結果、特定の状況においてはネットワークの重大な輻輳が発生する可能性があるので、これはグローバルトラフィックが特に均等に分布している場合を除き望ましくないかもしれない。決定論的な最小非ハッシュ化ルーティングは、1つの決定論的な最小パスを全トラフィックに用いるが、これはパケット順序付けを提供する一方で、利用可能なパス間への優れた帯域幅や負荷分布を提供しない。このようなルーティングは、制御メッセージやレイテンシが問題になるメッセージといった、頻繁でないまたは小サイズのメッセージに使用できる。順序付けが不要な場合には、適応型ルーティングをデフォルトルーティングタイプとして使用できる。パケットは、最小でのルーティングを試みるが、ネットワーク輻輳を回避するために、グループ内またはグループ間の非最小パスが使用されてもよい。或る実施形態では、適応型ルーティングは、ルーティングの選択を考慮するために、2つ以上の最小ポートおよび2つ以上の非最小ポートを提供するルーティングテーブルを使用することによって行われる。各ノードについて輻輳値が計算されることによって、または図9に示すルータタイルのようなルータ内のタイルの数が計算されることによって、同ルータ内の別のタイルに分布される。この例では適応型ルーティングアルゴリズムは、利用可能な2つの最小パスと2つの非最小パスを考慮し、この中から、輻輳値に基づき、また任意で様々に構成したバイアスに基づき選択を行う。さらなる実施形態では、下流ポート輻輳、推定される遠端リンク輻輳、近端リンク輻輳のような要素から、ポート輻輳値を導出する。特定の例では、2ビットの下流ポート輻輳情報は、ルータチップ内において各タイルに対応した外部チャネル上で伝播され、定期的に更新される。これらのビットは、送信ルータチップにおいて、チップ上の下流ポートの輻輳のビューを組合せることによって生成される。この2ビットの輻輳値に組み合わせられた下流ポートは、各タイルにおけるMMR構成可能マスクを介して選択される。これらの下流ポートの輻輳値を合計し、3つのプログラム可能な閾値と比較する。合計が最高閾値よりも大きい場合は、輻輳は2’b11である。合計が最高閾値未満であり、中間閾値よりも大きい場合は、輻輳は2’b10である。合計が中間閾値未満であり、最低閾値よりも大きい場合は、輻輳は2’b01である。あるいは、合計が最低閾値未満の場合は、輻輳は2’b00である。チャネルの受信側にて、この2ビット値は、4ビット幅の下流輻輳リマッピングテーブルによって4つのエントリ内にインデックスされることによって、4ビット値にマッピングされる。推定された遠端リンク輻輳の計算は、過去にチャネルラウンドドリップレイテンシよりも長い距離で送信され、未だ確認応答されていないフリットの数を追跡し、フリット送信とその確認応答受信との相対値を調整することによって行われる。この計算を行うために使用するメカニズムは、5ビット幅、32エントリの深さの遅延チェーンである。MMR構成可能なサイクル数1~31については、ルータは、この遅延チェーンの末尾位置に送信されたフリットの数をカウントする。この遅延の後に、全ての値がシフトされる。予想されるチャネル上の未だ確認応答されていないフリット送信済みで、確認応答が予想されるものの総数は、このチェーン内の値の合計である。この値を、未だ確認応答されていないクレジットカウントと比較する。未だ確認応答されていないクレジットの総数から、予想されるチャネル上のフリットを引くと、遠隔入力キューに記憶されるフリットの推定数が得られる。推定される遠端輻輳は、10ビット数として計算される。この数値をマッピングテーブルに従って4ビットインデックスに変換し、次にこの4ビット数を、16エントリ遠端輻輳リマッピングテーブル内にインデックスすることによって、別のプログラム可能な4ビット値にリマッピングする。近端リンク輻輳は、列バッファ内にキューイングされ、リンク上で送信されるのを待っている状態のフリットを合計することによって計算される。この合計も10ビット値であり、マッピングテーブルに従って4ビット値に変換される。次にこの4ビット数を、16エントリ近端輻輳リマッピングテーブル内にインデックスすることによって、別のプログラム可能な4ビット値にリマッピングする。このリマッピングされた4ビットの下流ポート輻輳値と、リマッピングされた4ビットの遠端リンク輻輳値と、さらにリマッピングされた4ビットの近端リンク輻輳値とを互いに組合わせることによって、1つの4ビット輻輳値をタイル毎に生成する。この組み合わせは、4ビット3入力符号なし飽和加算として行う。この4ビット輻輳値がチップ上の全ての他のタイルへと伝播されることによって、タイルが適応型のインフォームドチョイスを行うことが補助される。チップ上のnタイルの各々からチップ上の他の全てのタイルにリンクアライブlinkalive信号は、配信される。nタイルの各々に配信されるこのリンクアライブ信号は、該当するタイルと接続しているルータとの間にシリアルリンクが確立しているか否か示す。リンクがアライブ状態でないポートは、ポート選択の観点から無効であると考慮される。これによって、ルータは、最近失敗し且つまだソフトウェアによってルーティングテーブルから除去されていないリンクを適応的に回避できるようになる。リンクアライブ信号は、全てのネットワークタイルを接続する2線式シリアルチェーンを介してルータ周囲に伝播される。各タイルは、そのリンク状態情報を、適切なビットタイミングでシリアルチェーン上に配置する。輻輳論理に示されている全てのポートが無効である場合には、そのパケットは破棄される。この場合では、紛失パケットにタイムアウトを設定するか否かはエンドポイントハードウェア次第であり、また、再送信するか、エラーを適切と扱うかはより高レベルのソフトウェア次第である。各入力キューでは、2つの最小ポート候補と2つの非最小ポート候補の間で適応的な選択を行うために、配信輻輳値が使用される。これらの輻輳値を使用する前に、選択した2つの最小ポートおよび非最小ポート輻輳値にバイアス値を適用する。最初に、値の最も大きな部分にゼロを2つプリペンドすることで、値を論理的に6ビット値にまで拡張する。適応型ルーティングの制御タイプ適応型0、適応型1、適応型2、適応型3を使用して、4つのエントリバイアステーブルの中から1組のバイアスを選択する。各エントリは、最小ポートおよび非最小ポート輻輳値の各々に達するまで左にどれくらいシフトすればよいのか決定する、2ビットシフト値の1対を有する。6ビットに拡張された輻輳値は、0ビット、1ビット、または2ビットシフトされうる。このフィールドの符号化は、次のとおりである:2’b00=左に0ビットシフト×1、2’b01=左に1ビットシフト×2、2’b10=左に2ビットシフト×4、2’b11=リサーブ。各バイアスMMRは、拡張された最小および非最小輻輳値6ビットに加えて、追加の6ビット値の1対を含んでいる。この追加は飽和加算として実行され、6ビット数が得られる。最も低い輻輳に対応したポートが選ばれる。最小ポートと非最小ポートが同値である場合、ルータは、最小ポートを優先する。非最小として提示された2つのポート間、または、最小として提示された2つのポート間が同値の場合には、選択は、任意であり、あらゆる適切な方法で行われる。Dragonflyネットワークにおけるテーブル駆動型ルーティングメカニズムここで挙げるルーティング例では、パケットまたはメッセージをルーティングするために利用できるパスを決定するため、Dragonflyネットワーク構成にルーティングフレキシビリティを提供するために、様々なテーブルを使用する。グループ内またはグループ間にルーティングを提供するために、また、最小および非最小ルーティングパスのために、各種テーブルが存在する。ここに挙げた例示的なルータアーキテクチャにおけるルーティング構造は、次の4つの別個のテーブルセットに分割される。グローバル非最小GNテーブルセットと、グローバル最小GMテーブルと、ローカル非最小LNテーブルセットと、ローカル最小LMテーブルとである。この特定の例の論理フローを図12に示す。グローバルテーブルは、現在のグループがターゲットグループでない場合に、どのように遠隔グループにルーティングするか決定するために使用される。これらのテーブルは、ローカルグループから出るための出口である特定の光学ポートにルーティングするために使用される。ローカルテーブルは、現在のグループ内の特定のルータチップにルーティングするために使用される。これらのテーブルは、ローカルルーティングのためグループ内でのアップまたはダウンルーティングに使用されたり、あるいは中間グループ内でのアップルーティングに使用されたりする。最小テーブルは、最小のローカルまたはグローバル経路を指定する。これらの最小テーブルは、ダウンルーティングする時、または、適応型ルーティングのケースでは、アップ過程で最小パスの使用を試みる時に使用される。非最小テーブルは、非最小パスを指定し、アップルーティングする時のみ使用される。非最小テーブルはまた、アップルーティングの停止時を決定するためのルートroot検出メカニズムを提供する。グローバル非最小テーブルセットは、非最小トラフィックを中間グループにルーティングするために使用される。このテーブルセットは、安全な中間グループへと続くポートのリストを含んでおり、この安全な中間グループとは、他の全てのグループに接続している中間グループのことである。健全なネットワークでは、全てのグループが安全である。特に健全なネットワークにおいては、トラフィックをターゲットグループに接続していない可能性のある中間グループに送信することを回避するように、テーブルをプログラムしなければならない。このテーブルセットは、3つのテーブルで構成されている。第1テーブルは、現在のソースグループから出るためには緑色次元のどのランクをトラバースするか選択する。第2テーブルは、黒色次元をトラバースするよう選択する。第3テーブルは、現在のルータチップをオンにしておくために光学ポートを選択する。これらのテーブルは、固定優先順序で階層配列される。緑色次元テーブルは優先順位が1番高く、青色次元テーブルは一番低い。各テーブルには、Ariesルータ兼ファイアウォールをオンにしておくための複数のポート番号が、または現在のテーブルがその優先順位を下げて、優先順位階層における次のテーブルを考慮すべきであることを示す特別値がリストされている。最下位優先順位青色テーブル上の特別値を参照した場合、エラー状態が生じる。各テーブルは128エントリで構成されており、エントリの各々は6ビットポート番号または特別値6’b11xxxxである。各テーブルは、16×8エントリで編成されており、8エントリ毎の各ブロックにつき7ビットのECCが付加されている。このテーブルは、システム内の他の全てのグループに安全にルーティングすることが可能な中間グループに確実に続いている他のルータチップまたは光学ポート番号への経路しか含むべきでない。このテーブルはさらに、非最小トラフィックをシステム内の複数のグループにかけてほぼ均等に分布させるメカニズムを提供する。各テーブルにはエントリが128個あるので、有効基数18次元を用いた場合でも、各ポートが7回または8回リストされ、その次元で2つのポート間に最大14.3の不安定さが生じる。この不安定さは、グループ全体を通してテーブルを複数回コピーし、不安定なポートを変化させることによって最小化する。グローバル決定論的なルーティングの場合、このテーブルセットは、ターゲットtgtIDおそらくはローカルポート番号を含むハッシュ値によって、またオプションでパケットヘッダパケットアドレスからのものからのハッシュフィールドによって、インデックスされる。各テーブルは、互いに異なるインデックスを得る。グローバル適応型ルーティングの場合は、テーブルから、それぞれが8エントリで構成されている複数ブロックのうちの1つは、ランダムに選択される。次にこの同じ8エントリ構成のブロックから第2のエントリは、ランダムに選択される。2つのポートを互いに、またグローバル最小テーブルからの2つのエントリと比較することによって、パケットをどのパスでルーティングするか決定する。pタイルにおける緑色テーブルは、一般に、8回リストされた15個の緑色ポートと、8個の特別値を有する。さらにpタイルでは、黒色テーブルは、約7回リストされた15個の黒色ポートを、特別値を含んだ約21のエントリと共に有する。青色テーブルは、それぞれ約13回リストされた光学ポートの各々を有する。緑色のnタイルポートは、一般に、緑色テーブル内のエントリ全てを特別値として有する。黒色および青色テーブルは、pタイルの場合と同じ比率で構成される。黒色nタイルポートは、一般に、緑色および黒色テーブル内の全てのエントリを特別値として有する。青色テーブルは、pタイルの場合と同じ比率で構成される。グローバル最小テーブルは、現在のグループからターゲットグループまでの直接パスを決定するために使用される。このテーブルは256エントリで構成され、各エントリのビット幅は81ビットである。各エントリは、全ポートセットと規制されたポートセットとの2つの部分に分割されている。全ポートセットは、8個の6ビットポートエントリと、3ビットのモジュロ指定子とで構成される。モジュロフィールドは、関連するエントリにおける有効なポートの総数を示す。モジュロ指定子は、モジュロ-1として符号化される。つまり、モジュロフィールド内に7の値があれば、8のモジュロ演算ということである。規制されたポートセットは、4個の6ビットポートと、2ビットのモジュロ指定子で構成されている。81ビットエントリの各々が8ビットのECCを有する。このテーブルは、ターゲットグループ番号で編成されている。各ターゲットグループは、システムのサイズに応じて、テーブル内の1、2、4、8、16、32、64、または128エントリのブロックに対応している。241グループを持ったシステムは、テーブル内のブロック1個につき1エントリを有するエントリのうち15個は使用されない。65~128グループを有するシステムは、各ブロックにつき2つのエントリを使用する。33~64グループを有するシステムは4つのエントリを使用する。同様に続く。グループ番号、並びに0~7の追加のランダム適応型ルーティングまたはハッシュ決定論的なルーティングビットを使用して、テーブル内にインデックスを定義する。各エントリは、関連するターゲットグループに最小で接続するポートであって、ルーティングにおける現在のポイントから到達可能なAriesルータ兼ファイアウォールに続いているポートのリスト、または青色リンクを介してターゲットグループに直接続いているポートのリストを含む。全ポートセットは、グループ内でpタイルまたは光学nタイルのどちらかにて他のグループへの最小ルーティングを丁度開始した時に使用されたり、あるいは中間グループ内において非最小でルーティングし且つローカル非最小テーブルにルートrootが検出された際に任意のタイルにおいて使用されたりする以下を参照。テーブルのこのサイドには、インデックスが指定するグループに最小接続している利用可能な光学ポートまでの利用可能なパスが全て挙げられている。規制されたポートセットは、全ポートセットテーブルについて言及するルートroot検出の場合とルートroot注入の場合を除いて、グループ内でのルーティングに使用される。テーブルのこの半分は、最小ルーティングを行っていると仮定した場合に、グループネットワーク内の現在地点から正当であるネットワーク内のパスのみを示す。規制されたポートリストの重要な目的は、パケットがその出発点の方向に戻らないようにすることである。緑色ポートでは、規制されたテーブルエントリは、通常、黒色ポートと青色ポートしかリストしないはずである。黒色ポートでは、規制されたテーブルエントリは、通常、青色ポートしかリストしないはずである。規制されたセットにリストされた全てのポートが無効である場合には、このことは、パケットが正当な最小パスから分岐したことを、適応型ルーティング論理に示している。この場合、適応型ルーティング論理は、非最小選択肢から1つを選ぶ。これは、決定論的または最小にルーティングしたトラフィックでは絶対に発生しないはずである。なぜならテーブルは一貫した方法で書き込まれているはずであり、パケットが宛先にルーティングできないポイントに到着することはあり得ないからである。これが発生した場合には、ルータがエラーフラグを立て、そのパケットを破棄する。タイル内でルーティングされた正当な規制されたポートがない場合には、mod値は、任意の値に設定されうる。経路テーブルは、グループ番号に関連した全てのエントリに特別値6’b11xxxxを含んでいなければならない。正当な経路が1つしかない場合には、ポートリストは、少なくとも2回リストされている正当な経路と、これに合わせて2またはそれ以上に設定したmod値とを含んでいなければならない。決定論的なルーティングでは、関連するインデックス内の有効なエントリの数によってハッシュのモジュロを計算することで、全ポートセットまたは規制されたポートセットにおける有効なエントリのうちの1つが選択される。上述のケースと同様に、適応型ルーティングは、乱数と、N-1の第2モジュロとのモジュロを計算することによって第1の数字1に可算し、テーブル中に第2のランダムであるが固有のエントリのオフセットを取得することを除いて、テーブルから2つのエントリを選択する。ローカル非最小テーブルセットは、ローカルグループ内のルータチップを、このグループ内の非最小ルーティングのルートrootとして使用する目的で選ぶために使用される。このテーブルは、ソースグループおよびターゲットグループが同一である場合に、非最小ルーティングのために使用される。さらにテーブルは、中間グループ内での非最小ルーティングのためにも使用される。このテーブルセットは、青色テーブルが存在しないことを除けば、グローバル非最小テーブルと同様の構造である。ローカル非最小テーブルは、適応型ルーティングの場合にはランダムにインデックスされ、また非最小決定論的なルーティングの場合にはハッシュによってインデックスされる。グローバル非最小テーブルと類似し、適応型ルーティングの場合には、このテーブルから2つのエントリが生成され、比較される。設計におけるRAMマクロ総数を低減するために、これらのテーブルをRAM内のグローバル非最小テーブルと物理的に組み合わせる。このテーブルは、このタイルから到達可能なAriesルータ兼ファイアウォールをリストしている。これらAriesは、ローカル非最小ルーティングに安全に使用できる。健全なネットワークでは、pタイルと青色光学タイルは、グループ内の全てのAriesルータ兼ファイアウォールをほぼ均等にリストしなければならない。緑色テーブルのエントリのほぼ15/16には緑色ポートがリストされるべきであり、また約1/6は、緑色次元が既に条件を満たしており、黒色テーブルを使用すべきであるということを示す特別値を含んでいる必要がある。同様に黒色テーブルのエントリの約5/6は、黒色ポートをリストすべきであり、また約1/6は、黒色次元が条件を既に満たしたことを示す特別値を含んでいる必要がある。緑色テーブルと黒色テーブルの両方における特別値は、ルートrootに到達したこととルートroot検出、パケットをこの地点からダウンルーティングすべきであることを示す。緑色タイルは、特別値緑色次元の条件が満たされたことを示すで緑色テーブルを充填すべきであり、到達可能な6個のAriesルータ兼ファイアウォールを自身を含み、特別値を使用する。黒色テーブルに均等にリストすべきである。黒色タイルは、緑色テーブルと黒色テーブルの両方を特別ルートroot検出値によって充填すべきである。pタイルと光学タイルとは、全テーブルセットを必要とすべきである。nタイルは緑色テーブルなしでも技術上問題はないが、しかし、ここで示すルータテーブルの例は、フレキシビリティを持たせるためにnタイルを実現している。ローカル最小テーブルは、ターゲットグループ内での最小ルーティングダウンルーティングに使用され、さらにターゲットグループ内で適応的にアップルーティングを行う際にも使用される。このテーブルは、128エントリを有する。各エントリは52ビット幅であり、8個の6ビットポート番号と、分岐ビットと、テーブルのこのラインで有効なエントリの数を示すmod値とで構成されている。ターゲットグループ内のパスが最小パスから分岐しているため、そのパスは適応型アップルーティングを行う時には最小パスとして使用できず、したがってダウンルーティングにしか使用できないことを、分岐したビットは示す。これは、規制されたセットにおける全てのポートが無効であるグローバル最小テーブルのケースと類似している。このテーブルは、グループ内のターゲットAries番号で編成されている。各ローカルAries番号は、グループのサイズに応じて、テーブル内の1、2、4、8、または16エントリで構成されているブロックに対応している。65~128個のAriesルータ兼ファイアウォールを持ったグループは、1つのローカルAries番号につき1エントリのブロックサイズを使用する。33~64個のAriesルータ兼ファイアウォールを有するサイズのグループは、2のブロックサイズを使用する、などである。ローカルAries番号、並びに0~4の追加の乱数適応型ルーティングの場合またはハッシュ決定論的なルーティングビットは、テーブルにインデックスを定義するために使用される。各エントリは、関連するローカルAriesへと続くポートのリストを含む。決定論的なルーティングでは、関連インデックス内の有効なエントリの数によってハッシュのモジュロを計算することによって、テーブル内の有効なエントリの中から1つは、選択される。上述のケースと同様に、適応型ルーティングは、乱数と、N-1の第2モジュロとのモジュロを計算することによって第1の数字1に可算し、テーブル中に第2のランダムであるが固有のエントリのオフセットを取得することを除いて、テーブルから2つのエントリを選択する。グローバル非最小テーブルは、ソースグループのみにおいて、別のグループに向かうトラフィックのために使用される。グローバル非最小テーブルとローカル非最小テーブルとは、決して同時に使用されることはない。そのため必要なRAM総数を減らすために、グローバル非最小緑色テーブルは、ローカル非最小緑色テーブルと同じRAMに記憶される。グローバル非最小黒色テーブルは、ローカル非最小黒色テーブルと同じRAMに記憶される。グローバルテーブルは、これら2つのRAMそれぞれの下方インデックス値部分に記憶される。結論上述した例は、Dragonflyネットワークにおけるルーティングが、ネットワーク輻輳やトラフィックタイプのような要素に基づきネットワークパスを選択することが可能な適応型ルーティングと、最小および非最小ルーティングや、ローカルルーティングおよびグローバルルーティングを含む様々なルーティング用のルーティングテーブルとを使用して、どのように向上させられるか説明する。適応型ルーティングは、輻輳リンクまたはダウンしたリンクに基づき複数の正当な経路を選択し、また、チャネル上の輻輳を明快に通信させることによって向上したルーティングパフォーマンスと許容性を提供する、デッドロックを回避するルーティングを提供する。ルーティングは、まず、例えば異なる次元でのルーティングのように複数の最小経路にかけて実行され、その後に任意で、例えば輻輳リンクやダウンしたリンクを回避するためにランダムに選んだホップを使用して、1または複数の非最小経路から選択した非最小経路にかけて実行される。輻輳情報は、出力キュー内のメッセージ数をカウントすることや、伝送中のクレジットまたはメッセージのような要因から受信側バッファ輻輳推定を確立することといった要素から予想される、次のリンク輻輳に基づく。ノードは潜在的な受信側ノードに、平均的な次のリンク出力輻輳について問い合わせることができるため、輻輳リンクやダウンしたリンクの回避に基づきルーティング決定を行えるようになる。これ以外にもさらに、例えば、ルーティングパスを選ぶ際に、決定論的なハッシュまたは乱数を使用してトラフィックを拡散させるといった特徴が複数提供され、これらは輻輳を回避するためにトラフィックを拡散させる上で役立つ。1例では、ルーティングの選択はテーブルによって提示され、ネットワークの構成および状態に応じて、特定の経路に、あるいは、最小経路または非最小経路に偏る可能性がある。例えば、経路の選択が最高の効率のデフォルトによって最小ルーティングに偏るが、この偏りが、追加のトラフィックを任意または不必要に受信することから特定のネットワークリンクを保護するために、非最小ルーティングへの偏りに切り替わることもある。さらなる例では、ルーティングテーブルは、ローカルルーティングテーブルおよびグローバルルーティングテーブルを備えたテーブルと、最小パスおよび非最小パスとを含む。特定の実施形態をここで例証および説明したが、当業者は、同じ目的を達成すると推定されるあらゆる配列はここに示した特定の実施形態の代用となることを理解するであろう。本出願は、ここで説明した本発明の例示的な実施形態のあらゆる改造または応用を包括することを意図する。本発明は、特許請求の範囲、およびその均等物の全範囲によってのみ限定されることが意図されている。"