(57)【要約】【課題】ツリー・ネットワーク構造に従って相互接続された処理ノードの間での高速短待ち時間グローバル・ツリー通信を可能にするシステムおよび方法。【解決手段】グローバル・ツリー・ネットワークによって、複数の相互接続された処理ノードを有するコンピュータ構造内で実行される並列アルゴリズム動作中に集合リダクション動作を実行することが、最適に可能にされる。リンクを介してツリーのノードを相互接続するルータ装置が含まれて、仮想ツリーおよびサブツリー構造のノードでの短待ち時間グローバル処理動作の実行が容易になる。グローバル動作に、仮想ツリーのルート・ノードから葉ノードへの下流方向のグローバル・ブロードキャスト動作、仮想ツリーの葉ノードからルート・ノードへの上流方向のグローバル・リダクション動作、および仮想ツリーの任意のノードからルート・ノードへのポイントツーポイント・メッセージ受渡の１つまたは複数が含まれる。仮想ツリー・ネットワークの１つのノードが、入出力ノードに結合され、入出力ノードとして機能して、仮想ツリーの各ノードに外部システムとの入出力機能性を与える。グローバル・ツリー・ネットワークを構成して、同期式または非同期の形でグローバル・バリアおよび割込み機能性を提供することができる。したがって、たとえば並列コンピューティング・システムで使用される、並列アルゴリズム処理動作を、並列アルゴリズム動作のある動作相に従って最適に実行することができる。大量並列スーパーコンピューティング構造で実施される時に、グローバル・ツリー・ネットワークは、処理アルゴリズムの必要に従って、物理的および論理的に分割可能である。
2004536372.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理ノードを含むコンピューティング構造で実行される並列アルゴリズム動作中に、集合リダクション、ブロードキャスト、およびポイントツーポイント・メッセージ受渡を実行する装置であって、
前記ノードをツリー構成で相互接続する経路指定装置を含むグローバル・ツリー・ネットワークであって、前記ツリー構成が、１つまたは複数のその仮想ツリー・ネットワークを含み、前記グローバル・ツリー・ネットワークが、指定された仮想ツリー・ネットワークのルート・ノードから葉ノードへの下流へのグローバル・ブロードキャスト動作と、前記仮想ツリーの葉ノードからルート・ノードへの上流へのグローバル・リダクション動作と、前記仮想ツリーの任意のノードから前記仮想ツリーのルート・ノードへのポイントツーポイント・メッセージ受渡との１つまたは複数を含むグローバル処理動作を必要に応じて使用可能にする、グローバル・ツリー・ネットワーク
を含み、前記グローバル・ツリー・ネットワークおよび経路指定装置構成が、前記コンピューティング構造で短待ち時間通信を提供するために最適化される
装置。
【請求項２】
前記コンピューティング構造が、第１ネットワークを形成するために相互接続された複数の処理ノードを含み、前記１つまたは複数の仮想ツリー・ネットワークおよび前記第１ネットワークが、並列アルゴリズム処理性能を最適化するために並列アルゴリズムの帯域幅要件および待ち時間要件に従って集合的にまたは独立に利用される、請求項１に記載の装置。
【請求項３】
仮想ツリー・ネットワークのルート・ノードが、外部システムへの高速接続を含む入出力ノードとして機能し、前記入出力ノードが、前記第１ネットワークで実行される処理と独立に、仮想ツリー・ネットワークに関する入出力動作を実行する、請求項１に記載の装置。
【請求項４】
各前記ルータが、仮想ツリーの他のノードからパケットを受け取る入力装置と、前記ツリーの他のノードにパケットを転送する出力装置と、パケットを前記ツリーに注入するローカル注入装置と、前記ツリーからパケットを除去するローカル受取装置とを含み、前記装置が、さらに、前記仮想ツリーに参加するまたは参加しないのいずれかに前記ルータを構成する手段を含む、請求項３に記載の装置。
【請求項５】
前記ルータを構成する前記手段が、さらに、リダクション動作に関する仮想ツリーのルートとしての前記ノードの参加を指定する、請求項４に記載の装置。
【請求項６】
前記ルータを構成する前記手段が、さらに、リダクション動作中のオペランドの供給に関する入力装置およびローカル注入装置の参加を指定する、請求項５に記載の装置。
【請求項７】
前記ルータが、さらに、寄与する場合に、寄与する入力装置およびローカル注入装置によって受け取られるパケット内容に対する指定されたリダクション動作を計算する手段と、前記出力装置を介してそのノードの上流の親ノードへの計算結果の伝送を引き起こす手段とを含む、請求項６に記載の装置。
【請求項８】
前記仮想ツリー・ネットワークが、前記ルート・ノードでの単一パケットとしての完了のために、グローバルに組み合わされた結果が前記仮想ツリーで上に計算されることを再帰的に引き起こすようにプログラムされる、請求項７に記載の装置。
【請求項９】
仮想ツリーでのリダクションにオペランドを与えるように構成された参加する子のすべてのそれぞれに前記ルートでの単一の組み合わされたパケットをブロードキャストする手段をさらに含む、請求項８に記載の装置。
【請求項１０】
前記高速接続を介して外部システムに宛てられたポイントツーポイント・パケットを仮想ツリーのルートにある入出力ノードに送ることを計算ノードが行えるようにする機構をさらに含む、請求項３に記載の装置。
【請求項１１】
仮想ツリーのノードでのブロードキャスト・パケットの受取を制御するフィルタ機構をさらに含み、前記受取が、前記仮想ツリーでのノード・アドレスおよび参加に基づく、請求項９に記載の装置。
【請求項１２】
各ノードが、アドレスを含み、前記システムが、さらに、各前記仮想ツリーのノードの間でのポイントツーポイント・メッセージングを可能にするプログラマブル手段を含み、前記アドレスが、外部ホスト・システムがすべてのノードまたは前記ノードのサブセットに直接に通信できるようにする、請求項１１に記載の装置。
【請求項１３】
ローカル受取装置によって受け取られるパケットの内容に基づいて、処理ノードのプロセッサへのハードウェア割込みを生成する機構をさらに含む、請求項９に記載の装置。
【請求項１４】
各仮想ツリーで不要なダウン・ツリー・トラフィックを独立にブロックする機構をさらに含む、請求項９に記載の装置。
【請求項１５】
パケットを通信する時にルータの間のフロー制御を提供する機構をさらに含む、請求項１１に記載の装置。
【請求項１６】
積極的なブロードキャストを実行するために、前記フロー制御機構から分離された個々のダウンストリーム・リンクでパケットをブロードキャストできるようにする手段をさらに含む、請求項１５に記載の装置。
【請求項１７】
前記第１ネットワークが、ｎ次元トーラスを含み、ｎが、１以上である、請求項２に記載の装置。
【請求項１８】
複数の相互接続された処理ノードを有するコンピュータ構造で実行される並列アルゴリズム動作中に、集合リダクション、ブロードキャスト、およびメッセージ受渡を実行する方法であって、
グローバル・ツリー・ネットワーク構造に従ってリンクを介して前記ノードを相互接続するルータ装置を設けることであって、前記ツリー構造が、１つまたは複数の１つまたは複数の仮想サブツリー構造を含む、設けることと、
前記仮想ツリー構造のノードで短待ち時間グローバル処理動作を実行できるようにすることであって、前記グローバル動作が、前記並列アルゴリズム動作を実行する時の必要に応じて、指定されたツリー仮想サブツリー・ネットワークのルート・ノードから葉ノードへの下流へのグローバル・ブロードキャスト動作と、前記ツリーの葉ノードからルート・ノードへの上流へのグローバル・リダクション動作と、前記仮想ツリーの任意のノードから前記仮想ツリーのルート・ノードへのポイントツーポイント・メッセージ受渡との１つまたは複数を含む、実行できるようにすることと
を含む方法。
【請求項１９】
前記コンピューティング構造が、第１ネットワークを形成するために相互接続された複数の処理ノードを含み、前記方法が、並列アルゴリズム処理性能を最適化するために並列アルゴリズムの帯域幅要件および待ち時間要件に従って前記グローバル・ツリー・ネットワークおよび前記第１ネットワークを集合的にまたは独立に利用するステップをさらに含む、請求項１８に記載の方法。
【請求項２０】
各仮想ツリー・ネットワークのルート・ノードが、外部システムへの高速接続を含む入出力ノードとして機能し、前記方法が、前記第１ネットワークで実行される動作と独立に、仮想ツリー・ネットワークに関するノード入出力動作を実行するステップを含む、請求項１８に記載の方法。
【請求項２１】
各前記ルータが、仮想ツリーの他のノードからパケットを受け取る入力装置と、前記ツリーの他のノードにパケットを転送する出力装置と、パケットを前記ツリーに注入するローカル注入装置と、前記ツリーからパケットを除去するローカル受取装置とを含み、前記方法が、さらに、仮想ツリーに参加するまたは参加しないのいずれかに前記ルータを構成するステップを含む、請求項２０に記載の方法。
【請求項２２】
前記ルータを構成するステップが、さらに、リダクション動作を実行する時の仮想ツリーのルートとしてのノードの参加を指定するステップを含む、請求項２０に記載の方法。
【請求項２３】
前記ルータを構成するステップが、さらに、
リダクション動作中にオペランドを注入するための前記ルータに結合された前記処理ノードの参加を指定するステップと、
リダクション動作中にオペランドを注入するための前記ルータに結合された前記処理ノードの参加を指定するステップと
の１つまたは複数を含む、請求項２２に記載の方法。
【請求項２４】
寄与する子ノードおよび前記処理ノードから受け取られるパケット内容に対する指定されたリダクション動作を計算するように前記ルータを構成するステップと、出力装置を介するそのノードの上流親ノードへの計算結果の伝送を行わせるステップとをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記ルート・ノードでの単一パケットとしての完了のために、グローバルに組み合わされた結果が前記仮想ツリーで上に計算されることを再帰的に引き起こすステップをさらに含む、請求項２４に記載の方法。
【請求項２６】
仮想ツリーでのリダクションにオペランドを与えるように構成された参加する子のすべてのそれぞれに前記ルートでの単一の組み合わされたパケットをブロードキャストするステップをさらに含む、請求項２５に記載の方法。
【請求項２７】
前記高速接続を介して外部システムに宛てられたポイントツーポイント・パケットを仮想ツリーのルートにある入出力ノードに送ることを計算ノードが行えるようにするステップをさらに含む、請求項２０に記載の方法。
【請求項２８】
仮想ツリーのノードでのブロードキャスト・パケットの受取を制御するステップをさらに含み、前記受取が、前記仮想ツリーでの前記ノードの前記アドレスおよび参加に基づく、請求項２６に記載の方法。
【請求項２９】
各ノードが、アドレスを含み、前記方法が、さらに、各前記仮想ツリーのノードの間でのポイントツーポイント・メッセージングおよびサブツリー・メッセージングを可能にするステップを含み、前記アドレスが、ホスト・システムがすべてのノードまたは前記ノードのサブセットに直接に通信できるようにする、請求項２８に記載の方法。
【請求項３０】
ローカル受取装置によって受け取られるパケットの内容に基づいて、処理ノードのプロセッサへのハードウェア割込みを生成するステップをさらに含む、請求項２６に記載の方法。
【請求項３１】
各仮想ツリーで不要なダウン・ツリー・トラフィックを独立にブロックするステップをさらに含む、請求項２６に記載の方法。
【請求項３２】
パケットを通信する時にルータの間のフロー制御を提供するステップをさらに含む、請求項２８に記載の方法。
【請求項３３】
前記フロー制御機構から分離することによって、個々のダウンストリーム・リンクでパケットの積極的なブロードキャストを可能にするステップをさらに含む、請求項３２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には分散メモリ・メッセージ受渡並列コンピュータの設計およびシステム・ソフトウェアに関し、具体的には、たとえば大量並列分散メモリ・コンピュータで使用される個々のプロセッサを相互接続する新規の方法および装置に関する。
【背景技術】
【０００２】
大量並列コンピューティング構造（「ウルトラスケール・コンピュータ」または「スーパーコンピュータ」とも称する）では、多数の計算ノードが、一般に、グリッド、格子、またはトーラスなどの非常に規則的な構造の形で相互接続される。
【０００３】
そのような大量並列システムで一般に直面する問題の１つが、多数のノードを伴う集合的な算術演算または論理演算の効率的な計算である。そのようなシステムで一般に直面する第２の問題が、すべてのノードによる限られた数の外部入出力の効率的な共用である。多数の計算ノードでの集合算術演算を用いる一般的な計算の１つの例が、グローバル合計に基づくグローバル内積を必要とする疎な線形方程式の反復解法である。
【０００４】
端で「ラップ」される単純な３次元最近傍相互接続を含む図１に示された３次元トーラス相互接続コンピューティング構造１０は、ほとんどのタイプのプロセッサ間通信でよく機能するが、計算ノード１２のそれぞれによって供給されるオペランドから単一の結果が計算されるリダクションなどの集合演算については、または外部入出力接続（図示せず）などの限られたリソースの効率的な共用については、それほどよく実行しない。
【０００５】
したがって、グローバル・リダクション計算などのグローバル算術演算、データ分配、同期化、および限られたリソースの共用を必要とするものを含む多数のクラスの動作を効率的に信頼性のある形で実行するために最適化された処理ノードの独自の相互接続を含む、ウルトラスケール・スーパーコンピューティング・アーキテクチャを提供することが、非常に望ましい。
【０００６】
トーラスなどの高速ネットワークの通常の接続性は、単純に、より長い待ち時間のゆえに、この目的に完全に適してはいない。
【０００７】
すなわち、物理トーラス相互接続へのツリー通信パターンの単なるマッピングは、隣接するツリー・ノードがトーラス上で隣接することが必要である場合に、必要以上に深いツリーをもたらし、あるいは、これらのノードがトーラス内で隣接しない時に、より長い待ち時間を有するツリーをもたらす。相互接続リソースが限られる時に最も効率的に集合演算を計算するためには、真のツリー・ネットワークすなわち、ノードの間の物理的相互接続が、ノードをツリーに形成するネットワークが必要である。
【特許文献１】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００２９ＵＳ１（１５２７２））
【特許文献２】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００１０２１１ＵＳ２、Ｄ＃  １５２７５）
【特許文献３】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００２）
【特許文献４】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００５）
【特許文献５】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００９）
【特許文献６】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００３１ＵＳ１）
【特許文献７】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００３２ＵＳ１（１５２５８））
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、コンピューティング構造の個々の処理ノードを相互接続し、その結果、これらのノードが効率的に信頼性のある形でグローバル・リダクションを計算し、データを分配し、同期化し、限られたリソースを共用できるようにするシステムおよび方法を提供することである。
【０００９】
本発明のもう１つの目的は、ツリー相互接続として配置され、グローバル動作、算術演算、および集合動作を容易にする、大量並列分散メモリ・コンピュータの個々のプロセッサを相互接続する独立の単一の物理ネットワークを提供することである。
【００１０】
本発明のもう１つの目的は、物理ネットワークのサブツリーである仮想ツリー・ネットワークの１つまたは複数のノードに外部入出力およびサービス機能性を提供するグローバル・ツリー相互接続として配置される、大量並列分散メモリ・コンピュータの個々のプロセッサを相互接続する独立の単一の物理ネットワークを提供することである。そのようなグローバル・ツリー相互接続システムに、メッセージ受渡トーラスまたはグリッド・コンピューティング構造からメッセージ・トラフィックを離す専用の入出力ノードを含めることができる。
【課題を解決するための手段】
【００１１】
本発明によれば、ツリー・ネットワーク構造に従って相互接続された処理ノードの間での高速短待ち時間グローバル通信を可能にするシステムおよび方法が提供される。グローバル・ツリー・ネットワークによって、複数の相互接続された処理ノードを有するコンピュータ構造内で実行される並列アルゴリズム動作中に集合リダクション動作を実行することが、最適に可能にされる。リンクを介してツリーのノードを相互接続するルータ装置が含まれて、ツリーのノードでの短待ち時間グローバル処理動作の実行が容易になる。ツリー・ネットワーク内の全ノードのサブセットを構成する「仮想ツリー」の定義を可能にする構成オプションが含まれる。グローバル動作に、仮想ツリーのルート・ノードから葉ノードへの下流方向のグローバル・ブロードキャスト動作、仮想ツリーの葉ノードからルート・ノードへの上流方向のグローバル・リダクション動作、および仮想ツリーの任意のノードからルート・ノードへのポイントツーポイント・メッセージ受渡の１つまたは複数が含まれる。仮想ツリー・ネットワークの１つのノードが、入出力ノードに結合され、入出力ノードとして機能して、仮想ツリーの各ノードに外部システムとの入出力機能性を与える。グローバル・ツリー・ネットワークを構成して、同期式または非同期の形でグローバル・バリアおよび割込み機能性を提供することができる。これは、同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００２９ＵＳ１（１５２７２））に記載されている。したがって、たとえば並列コンピューティング・システムで使用される、並列アルゴリズム処理動作を、並列アルゴリズム動作のある動作相に従って最適に実行することができる。大量並列スーパーコンピューティング構造で実施される時に、グローバル・ツリー・ネットワークは、処理アルゴリズムの必要に従って、物理的および論理的に分割可能である。
【００１２】
大量並列コンピュータでは、計算ノードのすべてが、一般に、ファイル・システムなどの外部リソースへのアクセスを必要とする。限られた数の外部入出力接続を効率的に共用するという問題は、そのような接続を設けるコストが、個々の計算ノードのコストよりかなり高いので生じる。したがって、入出力接続を効率的に共用することによって、入出力帯域幅がシステム・スケーラビリティに関する制限的コスト要因にならないことが保証される。限られたプロセッサ間相互接続を仮定すると、平均待ち時間に関する単一リソース共用の最も効率的なネットワークは、共用リソースがツリーのルートにあるグローバル・ツリーである。
【００１３】
グローバル動作および集合動作に関して、単一の大きいツリーを使用して、すべてのプロセッサを相互接続することができる。しかし、ファイル・システム入出力は、入出力機能がルートにある、多数の小さいツリーを必要とする。大きいツリーには、複数のより小さいサブツリーが含まれるので、外部接続を大きいツリー内の適当なサイズのサブツリーのルート戦略的に配置することによって、ファイル・システム入出力に単一の大きいツリーを使用することができる。さらに、ファイル・システム入出力は、本発明によって使用可能にされ、集合動作には必要ない、ポイントツーポイント・メッセージングを必要とする。
【００１４】
有利なことに、本発明のグローバル・ツリー・ネットワークを組み込んだスケーラブル大量並列スーパーコンピュータは、生命科学の分野で実行される並列アルゴリズムによく適する。
【００１５】
本発明の装置および方法のさらなる特徴、態様、および長所は、以下の説明、請求項、および添付図面に関してよりよく理解される。
【発明を実施するための最良の形態】
【００１６】
本発明は、本明細書に組み込まれる、本願の所有者が所有する、同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００１０２１１ＵＳ２、Ｄ＃  １５２７５）に記載のものなどのコンピュータ構造で実施され、この米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００１０２１１ＵＳ２、Ｄ＃  １５２７５）には、広範囲のアプリケーションにテラＯＰＳ（１兆演算毎秒）程度の処理能力を引き渡すように設計された、３次元トーラスの形の新規の大量並列スーパーコンピュータ・アーキテクチャが記載されている。この大量並列スーパーコンピュータ・アーキテクチャは、説明される例示的実施形態で、６４×３２×３２個の３次元トーラスとして編成された６５５３６個の処理ノードが含まれ、各処理ノードは、６つの隣接するノード１２に接続される。図１に、８つのノード１２からなるそのようなトーラスを示すが、３つのすべての次元に沿ってノード１２の数を増やすことによって、この相互接続がどのようにスケーリングされるかが、明らかにわかる。現在の技術を用いると、このアーキテクチャを、通信よりかなり多くの計算を必要とするか、最近傍通信だけを必要とするアプリケーションに、数百テラＯＰＳまで活用することができる。本発明を、スーパーコンピュータ以外の多数の他のコンピュータ構造で実施できることを理解されたい。
【００１７】
前に述べたように、トーラス処理ノードを接続する相互接続ネットワークは、ほとんどのタイプのプロセッサ間通信でよく機能するが、ノードのそれぞれによって供給されるオペランドから単一の結果が計算されるリダクションなどの集合演算については、それほどよく機能しない。
【００１８】
本明細書に組み込まれる、本願の所有者が所有する、同時係属の米国仮出願番号＿＿＿＿＿＿（Ｄ＃１５２７５）に記載されているように、トーラスでの集合リダクション動作を実行する、最小待ち時間に関する最も効率的な機構は、真のツリー・ネットワークすなわち、ノード間の物理接続によってノードがツリーに形成されるネットワークを提供することである。
【００１９】
したがって、本発明の好ましい実施形態によれば、ノードＡＳＩＣごとに１つの複数の相互接続されたルータ装置を含むグローバル・ツリー・ネットワークが提供される。各ルータは、３つの「子」ポートおよび１つの「親」ポートを提供し、このポートのそれぞれが、選択的に使用可能にされる。２つの子ポートは、ツリー・トポロジを作成するのに十分である。より多くの子によって、ツリーの高さ、またはルートに達するのに必要な接続が減る。したがって、より多くの子によって、より多くの相互接続を犠牲にして、集合動作の待ち時間を減らすことができる。ツリーは、親を有しない（すなわち、その親ポートに何も接続されていない）「ルート」ノードから開始することによって形成される。ルート・ノードは、ツリーの最上位「レベル」を形成する。次の下のレベルは、１つまたは複数のルートの子ポートを他のルータの親ポートに接続することによって形成される。この場合に、ルート・ノードは、その下のレベルのノードの「親」である。この処理は、子を有しない（すなわち、そのルータの子ポートのどれにも何も接続されない）ノードに達するまで再帰的に継続される。これらのノードを、ツリーの「葉」と称する。たとえば、図２の例のツリー・ネットワーク１００に示されているように、ノードＢ１１０が、ルート・ノードであり、葉は、ルート・ノードから最も遠い最下部のノード１２０である。本明細書では、ツリーを上にルートに向かって移動するデータを、「アップ・ツリー」トラフィックと称し、ルートから離れて葉に向かって移動するデータを、「ダウン・ツリー」トラフィックと称する。
【００２０】
下で詳細に説明するように、ツリー・ネットワークに、ルータ（ノード）を相互接続するリンク上の仮想チャネルによってサポートされる、複数の独立の「仮想ネットワーク」を含めることができる。リンクを共用するために、仮想ネットワーク・データ・ストリームが、パケット化され、公平な形でインターリーブされる。仮想ネットワークのそれぞれが、それ自体のストレージ・リソースを有し、ある仮想ネットワークでの機能デッドロックは、他の仮想ネットワークに影響しない。
【００２１】
各仮想ネットワークを、仮想ツリー（またはサブツリー）にさらに再分割することができ、この仮想ツリーは、独立（各仮想ネットワーク内で）または非独立とすることができる。任意のノードを、１６個の仮想ツリーの１つのルートになるように構成することができる。仮想ツリーには、ルートとして指定されたノードと、ａ）同一の仮想ツリー番号のルートとしても指定されたノードと、ｂ）ａ）を満足するノードの子とを除く、ルートの子のすべてが含まれる。したがって、同一の仮想ツリー番号を有する仮想ツリーは、オーバーラップすることができないが、異なる番号を有する仮想ツリーは、オーバーラップすることができる。
【００２２】
ノードを、任意の数の仮想ツリーに参加するか、全く参加しないように構成することができる。参加する場合に、ノードは、リダクション動作にオペランドを与えるなど、すべてのツリー・セマンティクスに従うことが期待される。ノードは、複数の仮想ツリーに参加することができるので、ノードが仮想ネットワークに注入するすべてのパケットについて、仮想ツリー番号を指定しなければならない。
【００２３】
本発明に従って使用される例のツリー構造１００を、図２に示す。具体的に言うと、図２には、３５個のノード（円によって表される）と、３５個のノードのすべてを接続するツリー・ネットワーク１００を含む仮想ツリー・ネットワークの例が示されている。ツリー・ネットワーク１００は、これから詳細に示すように、グローバル・リダクションおよびブロードキャストに使用される。入出力および外部システムとのリソース共用のために、図２の例の仮想ネットワーク１００のノードは、仮想ツリー１から５として図２で参照される５つのオーバーラップしない仮想サブツリーにグループ化される。すなわち、仮想サブツリーのそれぞれが、円の中の異なる番号によって示される。各めいめいのサブツリー１から５のめいめいのルートにあるノード１１１、１１２、１１３、１１４、および１１０には、外部システム（たとえばホストまたはファイル・システム）へのインターフェース接続が含まれる。したがって、各入出力接続では、それがルートに接続されるサブツリーの７つのノードのすべてのトラフィックが処理される。好ましい実施形態では、各サブツリーのルートにあるノードが、入出力専用であるが、これが必ず必要なわけではない。
【００２４】
図２および、そのルートにノードＡ  １１１がある仮想ツリー番号１を参照すると、この構造から外にデータを送ることを望む通常のノード１１５は、メッセージを、上に、仮想ツリーのルート・ノード１１１に渡し、このルート・ノード１１１で、メッセージが外部接続に転送される。外部ネットワーク接続に達するデータを、本明細書で詳細に説明するように、他のすべてのノードをフィルタ・アウトするブロードキャスト・フィルタを使用することによって、１１５などの特定のノードに転送することができる。グローバル・ツリー・ネットワークの動作、特に入出力、プログラム・ロード、システム管理、並列ジョブ監視、およびデバッグに使用されるプログラマブル・ポイントツーポイントまたはサブツリー・メッセージングをサポートする機能性に関するさらなる詳細は、本明細書に組み込まれる、本願の所有者が所有する、同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００２）、米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００５）、および米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９８２００１−１００９）に記載されている。
【００２５】
図２に戻ると、一般に、入出力トラフィックは、そのルートに外部接続を有する仮想ツリー内に残る。しかし、外部接続に障害が発生する場合に、外部接続を有するもう１つのノードを、フェイルオーバに使用することができる。たとえば、図２のノードＡ  １１１への外部入出力接続に障害が発生する場合に、ルートがノードＡであるサブツリー内のノードのすべてが、ノードＢ  １１０を介して外部のファイル・システムまたはホスト・システムと通信することができる。
【００２６】
ツリー２０に作られるハードウェア機能性に、整数加算、整数最大値、最小値、ビット単位論理AND、ビット単位論理OR、ビット単位論理XOR（排他的OR）、およびブロードキャストが含まれるが、これに制限されないことを理解されたい。これらの機能は、最短待ち時間が可能な形で実施される。たとえば、加算機能は、ワードの最下位バイトがまずグローバル・ネットワークに送られることをもたらす。この下位バイトは、即座に他のソースからの他方のバイトに加算され（ハードウェア内で）、結果は、ツリーの次のレベルにシフト・アウトされる。この形で、たとえば８バイト・ワードが、上位バイトがシフト・アウトされる前に、既にツリーの複数の層を上に進行している。これによって、計算機全体を介する非常に短い待ち時間の加算の可能性がもたらされる。同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００３１ＵＳ１）および米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００３２ＵＳ１（１５２５８））、表題「ArithmeticFunctions in Torus and Tree Networks」に記載されているように、最小値および減算などの他の算術機能を、データの適当な事前条件設定によって達成することができる。浮動小数点合計も、ツリーでの２パスによって、グローバル・コンバイニング・ツリーなしでこの結果を達成する方法と比較して非常に短い待ち時間で、達成することができる。必ず、ツリーでの算術演算または論理演算が、ツリーの上への流れをもたらし、ツリーの上部ですべての結果が組み合わされ、後続のルートからツリーの下への流れがもたらされ、結果がすべての分岐に分配される。後で説明するように、ある種の分岐を、制御された形で計算から省略することができる。
【００２７】
好ましい実施形態では、本発明のグローバル・ツリー・ネットワークに、ノードごとに１つの、それぞれがデータの移動ならびに集合リダクションの計算を行う、相互接続されたルータが含まれる。図３に、図２のツリー・ネットワークのルータ装置２００の基本的なアーキテクチャを示す。図３からわかるように、各ルータ装置２００には、複数の、たとえば４つの、ポートが含まれ、これらのポートを、別のルータに接続する、または接続されない時に使用不可にするのいずれかが可能である。図３からわかるように、ルータは、４つの入力ポート２１０ａから２１３ａと、対応する４つの出力ポート２１０ｂから２１３ｂを有して、３ツリーを構成できるデータパスを形成する。一実施形態では、４つのポートの１つだけを、親ノードへの接続として指定することができ、残りのポートのうちの３つまでを、子ノードに接続することができる。ツリーの最下部の葉ノードは、親に接続された１つのポートだけを使用可能にされ、ツリーのルートは、親を使用可能にされるのではなく、少なくとも１つの子を使用可能にされる。データパスが、図３に示されているようにクロスバ・スイッチ２１５を介して作成されることを理解されたい。
【００２８】
説明のために、図３のルータ装置２００では、データが必ず左から右に流れる。したがって、パケットは、ローカル注入ＦＩＦＯ２０２またはルータの入力ポート２１０ａから２１３ａの１つのいずれかからルータ装置２００に入ることができる。パケットがポートに入る場合に、そのパケットは、それが２つの仮想ネットワークのどちらであるかに応じて、２つの入力ＦＩＦＯの１つ（たとえばＡまたはＢ）に置かれる。パケットは、最終的に、アップ・ツリー選択ブロック２２０内に設けられるＡＬＵユニット２４０によって実行される論理演算および算術演算か、ダウン・ツリー選択ブロック２３０のいずれかによって消費される。アップ・ツリー論理またはダウン・ツリー選択の結果は、４つの出力ポート２１０ｂから２１３ｂのすべてにブロードキャストされ、これらの出力ポートのそれぞれは、動作に応じてそれを処理することもしないこともでき、宛先のポートに出力する。選択ブロック２２０および２３０には、パケット（１つまたは複数）がルータを介して移動されるかどうかを判断するアービタ回路（図示せず）が含まれる。アップ・ツリーとダウン・ツリーで同時にトラフィックがある場合があることを理解されたい。
【００２９】
ツリーへのソフトウェア・アクセスは、注入インターフェース２０２および受取インターフェース２０４と、１組の構成レジスタ２１８によってもたらされる。一般に、構成レジスタ２１８は、ルータを構成し、その状況を判定するのに使用され、注入インターフェース２０２および受取インターフェース２０４は、アプリケーションによって、それぞれオペランドを供給し、結果を受け取るのに使用される。具体的に言うと、各仮想ツリーは、各ルータの仮想ツリー構成レジスタ２１８に適当な値を保管することによって構成され、この仮想ツリー構成レジスタ２１８は、仮想ツリーごとに１つある。仮想ツリーのそれぞれについて、構成レジスタによって、ノードが、１）ツリーのルートとして機能するか否か、２）ツリーに参加するか否か、および／または３）アップ・ツリー・ブロードキャスト・パケットの受取を強制するか否かを指定できるようになる。さらに仮想ツリー構成レジスタ２１８によって、子のうちのどれが、ツリーに参加する、またはその下に参加するノードを有するのいずれかであることを指定できるようになる。これは、疎なツリーをサポートするのに必要である。
【００３０】
アプリケーションは、ＣＰＵ注入２０２インターフェースおよびＣＰＵ受取２０４インターフェースを介してツリーと相互作用する。データは、明示的または直接メモリ・アクセス（ＤＭＡ）を介するのいずれかで、パケットとして注入インターフェース２０２に保管されることによって、ツリーに送られる。同様に、結果は、明示的にまたはＤＭＡを介するのいずれかで、受取インターフェース２０４からパケットとして読み取られることによって、ツリーから除去される。
【００３１】
図示されてはいないが、ルータの間で、たとえばスラックの価値がある複数のパケットを許可するトークンベースのプロトコルを使用して、フロー制御技法が実施されることを理解されたい。すなわち、使用可能にされているすべての出力ポート２１０ｂから２１３ｂが、別のルータの単一の入力ポートに接続される。一般に、その入力ポートの各仮想チャネルは、出力ポートの対応する仮想チャネルに、その入力ＦＩＦＯ内のバッファ空間の価値があるすべてのパケットに関するトークンを与える。出力ポートは、パケットを送出する際にトークンを消費し、入力ポートは、ＦＩＦＯ空間を解放するかのように出力ポートにトークンを返す。したがって、出力ポートは、使用可能なトークンを有する限り、パケットの送出を継続することができる。
【００３２】
好ましい実施形態のルータ装置内の演算論理装置（ＡＬＵ）ブロック２４０は、４つのオペランド・サイズに対する５つのリダクション動作を実行するために使用可能にされる。動作は、整数加算、整数最大値、ビット単位論理OR、ビット単位論理XOR、およびビット単位論理ANDである。オペランド・サイズは、３２ビット、６４ビット、１２８ビット、および２０４８ビットである。図３に示されたアーキテクチャで、動作またはオペランド・サイズに関する異なる選択が除外されないことを理解されたい。具体的に言うと、ソフトウェアを使用して、動作およびオペランド・サイズを選択する。
【００３３】
通常、リダクション動作に参加するノードは、ＣＰＵ注入ＦＩＦＯ２０２に保管することによって、「リダクション」タイプのパケットを注入する。リダクションは、パケットの粒度で実行され、パケットは、一実施形態によれば、たとえば２５６バイトのペイロードを担持する。個々のパケットは、必ず同一サイズのオペランドを担持し、オペランドのすべてに対して同一のリダクションを実行する。どのノードでも、各仮想ツリーのリダクションに参加しないように構成することができる。この場合に、ノードは、リダクションにデータを供給せず、結果を受け取らない。
【００３４】
仮想ツリーのそれぞれについて、ルータ装置２００は、子のどれがリダクションに参加するかを指定するように構成される。ルータ装置は、そのルータの参加する子のそれぞれおよびローカル注入ＦＩＦＯ（ローカル・ノードが参加していないのでない限り）からリダクション・パケットを受け取る時に、パケットの内容に対して、指定されたリダクション動作を計算し、結果を単一のパケットとして親に送る。すなわち、各パケットの第１ワードを組み合わせて、結果パケットの第１ワードを作る、各パケットの第２ワードを組み合わせて、結果パケットの第２ワードを作り、以下同様である。この形で、グローバル結果が、ツリーの上へ再帰的に計算され、最終的に、リダクション・ツリーのルート・ノードで、結果を含む単一のパケットとして完了する。
【００３５】
どのノードでも、仮想リダクション・ツリーのルートとして構成できることが好ましい。リダクションがそのノードに達したならば、単一の組み合わされたパケットが、受け取られるか、すべての参加する子にブロードキャストされるか、その両方である。ルータは、ダウン・ツリーの子ノード宛のリダクション・パケットを受け取る時に、そのパケットのコピーをその子のそれぞれに転送する。ルータは、その仮想ツリー上のリダクションに参加するように構成されている場合に、そのパケットのコピーをローカル受取ＦＩＦＯ２０４にも置く。
【００３６】
好ましい実施形態では、物理的な相互接続の幅が、オペランドの幅より狭く、したがって、オペランドは、直列化された形でツリー上で送られる。可能な最短待ち時間を達成するために、整数オペランドは、最下位ビットを先に送られ、その結果、オペランドが到着する際に結果を計算でき、転送もできるようにされる。この形で、結果は、潜在的に、その上位ビットがシフト・アウトされる前にツリーの数レベル上に進行し、すべてのノードにわたる非常に短い待ち時間がもたらされる。数は、異なる最上位のビットに基づいて異なることがわかるので、パイプライン化された最大値演算が、最上位ビットを含むワードから開始して計算されることを理解されたい。ハードウェアは、注入され受け取られる最大値オペランドを自動的に逆転し、その結果、計算が、最上位ビットから最下位ビットへと実行される。
【００３７】
整数リダクションをさらに使用して、浮動小数点リダクションを計算することができる。たとえば、グローバル浮動小数点合計を、ツリーを２回使用することによって実行することができ、この場合に、１回目で、すべての指数の最大値を求め、２回目で、すべてのシフトされた仮数を加算する。
【００３８】
前に述べたように、本発明のツリー・ネットワーク１００は、効率的なグローバル・ブロードキャストを実行するのに理想的な構造である。ハードウェア・ブロードキャスト動作は、必ずツリーのルートから実行されるが、どのノードでも、まずルート・ノードのルータ装置にポイントツーポイント「ブロードキャスト」タイプ・メッセージを送ることによってブロードキャストすることができ、このメッセージによって、ブロードキャストが自動的に開始される。グローバル・ブロードキャストでは、大部分は、リダクションの規則および制限が尊重されるが、アップ・ツリーでの挙動は異なる。どのノードでも、ブロードキャスト・タイプのパケットを仮想ツリーに注入することによって、ペイロードのブロードキャストを実行することができる。パケットは、仮想ツリーのルートとして構成されたノードに達するまで、変更されずにツリーを上へ移動する。ルートでは、パケットが向きを換え、その仮想ツリーの参加する子のすべてにブロードキャストされる。したがって、そのパケットは、仮想ツリー上のリダクションに参加するノードによってのみ受け取られる。
【００３９】
本発明によるブロードキャストの受取は、さらに、パケット内に含まれる情報をフィルタリングすることによって制御される。好ましい実施形態のフィルタリング機構は、パケットに含まれる値を、各ルータに保管された事前に構成された値と突き合わせ、値が一致する場合に限ってパケットを受け取ることによって機能する。一般に、システム内のすべてのノードに、一意の値（アドレス）が割り当てられ、したがって、このブロードキャスト・フィルタリング機構によって、ルート・ノードからその下の単一のノードにメッセージを送れるようになる。一意でないアドレスを使用して、ノードのサブセットによる受取を引き起こすこともできる。ブロードキャスト・フィルタリングを一般化できる多数の形がある。たとえば、アドレスの代わりにビット・ベクトルを使用することによって、ノードの複数のばらばらの構成可能なサブセットがブロードキャストを受け取れるようになる。
【００４０】
外部入出力接続の効率的な共用は、ブロードキャスト・フィルタリングと「ルート」パケット・タイプの組合せによってもたらされる。ルートタイプ・パケットは、仮想ツリーのルートとして指定されたノードに出会うまで常に仮想ツリーを上に移動し、そのノードで、無条件で受け取られる。これによって、ルート以外のノードがルートにメッセージを送れるようになり、ルートで、メッセージを外部接続に転送することができる。外部接続に達するデータを、所期の宛先と一致するアドレスを用いたフィルタリング・ブロードキャストを使用して、特定の非ルート・ノードに転送することができる。
【００４１】
外部接続に障害が発生する場合に、その接続を使用するノードは、ツリーの上側で外部接続を有する次のノードにフェール・オーバすることができる。ノードからのトラフィックに関して、これは、単に、障害を発生した外部接続を有するノードを再構成し、その結果、そのノードが、もはや仮想ツリーのルートにならないようにし、フェールオーバ・ノードを新しいルートとして再構成することによって実行される。ノードへのトラフィックは、より複雑である。というのは、フェールオーバ・ルートからのブロードキャストが、障害を発生したノードの下の子だけではなく、フェールオーバ・ルートの下のすべての子に向かうからである。たとえば、図２のノードＡ  １１１が、ノードＢ  １１０にフェール・オーバする場合に、ノードＢからのパケットが、ツリー全体にブロードキャストされるようになる。
【００４２】
不要なトラフィックを防ぐために、どのルータ装置でも、各仮想ツリーのダウン・ツリー・トラフィックを独立にブロックするように構成することができる。ブロックするように構成された仮想ツリーのアップ・ツリー・リンクのルータに入るパケットは、単純に捨てられる。たとえば、図２のノードＡ  １１１の下のノードが、ツリー１という符号を付けられた仮想ツリーを使用して、ノードＡ  １１１の接続を使用して外部入出力を送受すると仮定する。ノードＡでの接続をノードＢにフェール・オーバするために、ノードＢを、ノードＡの代わりに仮想ツリー１のルートになるように構成し、ノードＣおよびノードＤを、仮想ツリー１のダウン・ツリー・トラフィックをブロックするように構成する。このダウン・ツリー・ブロック機構を、仮想ツリーの枝刈りに一般的に使用できることを理解されたい。
【００４３】
どのパケットでも、割込み要求を付加してツリー・ネットワークに注入することができる。これの最終的な効果は、そのパケットを受け取るすべてのノードでマスク可能割込みを引き起こすことであり、あるいは、リダクションの場合には、パケットから結果が計算される。リダクション結果は、その結果に寄与する注入されたパケットのどれかによって割込みが要求された場合に、割込みを引き起こす。さらに、グローバル・リダクション動作を使用して、割込み機構を用いてソフトウェア・バリアを実行することができる。簡単に言うと、各ノードは、その割込みフラグをクリアし、その後、グローバル・リダクションに寄与することによって、バリアに入る。このノードは、割込みフラグをポーリングするか、割込みを受け取ることによって、バリアの完了を検出する。グローバル・コンバイニング・ツリーおよびバリア・ネットワークの動作に関するさらなる詳細は、本明細書に組み込まれる、本願の所有者が所有する、同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ  ８−２００１−１００９）に記載されている。
【００４４】
本発明のツリー・ネットワークでは、基本的な順序付けの規則に従う動作である限り、動作の正しい完了が保証される。すなわち、パケットは、受け取られた順序でルータ２００によって処理されるので、仮想ネットワークのデッドロックは、仮想ツリーでの動作に参加するノードが、同一の順序でリダクション・オペランドを注入しないか、オペランドを注入できない場合に発生する。同様に、デッドロックは、２つの仮想ツリーが、同一の仮想ネットワークでオーバーラップし、オペランド注入が、仮想ネットワークの厳密な順序付け規則に違反する場合に発生する可能性がある。ブロードキャスト動作またはポイントツーポイント・メッセージング動作に対する順序付け制限がなく、これらの動作を、リダクションとインターリーブできることが好ましい。
【００４５】
正しく順序付けられた動作の保証された完了は、ハードウェア・エラー回復機構によってもたらされる。簡単に言うと、各ルータは、グローバル・ツリー・ネットワーク・リンクを介して送られるパケットが、エラーなしで受け取られたことの肯定応答を受け取るまで、それらのパケットのすべてのコピーを保存する。パケットＣＲＣ付きのスライディング・ウィンドウ・プロトコルなど、破壊されたパケットの検出の機構と、保存されたコピーを使用してそれらのパケットを再送出させる機構とを含む、リンクレベル通信プロトコルを実施することができる。
【００４６】
前に述べたように、フロー制御は、トークンベースの通信プロトコルの使用を介して維持される。「下流」ルータにパケットを送る「上流」ルータは、下流ルータの空き記憶容量を表す個数のトークンを有する。上流ルータは、パケットを送る時に、必ず、トークンを消費し、トークンが残っていなければパケットを送ることができない。逆に、下流ルータは、記憶空間を解放した時に、必ず上流ルータにトークンを発行する。記憶空間とパケット待ち時間の間のバランスによって、リンクが常に使用中の状態に保たれることが保証される。
【００４７】
通常は単一のパケットが複数のダウン・ツリー・リンクを介して送られ、ローカルに受け取られるダウン・ツリー・ブロードキャストでは、フロー制御を実施して、ダウン・ツリー・リンクのすべてでトークンが使用可能であり、ＣＰＵ受取ＦＩＦＯ２０４に余地があるようになるまで、パケットの進行を防ぐことができる。しかし、この保守的な手法は、単一の宛先に向けられたフィルタリング・ブロードキャストのスループットに影響する可能性がある。というのは、その宛先が、トークンを有するリンクの下にあるが、パケットが、トークンを有しない別のリンクで待たなければならない可能性があるからである。したがって、好ましい実施形態では、ツリー・ネットワークが、「積極的な」ブロードキャストを実行し、このブロードキャストでは、基本的に、個々のダウン・ツリー・リンクでのフロー制御が分離される。図３を参照すると、パケットは、適当なダウン・ツリー・リンクおよび仮想ネットワークのすべてで十分な記憶空間が使用可能になると、すぐに、ダウン・ツリー・リンクおよび仮想ネットワークの出ＦＩＦＯ２５０に転送される。その後、各出ＦＩＦＯ２５０は、トークンが使用可能になる時に、出力ポート２１０ｂから２１３ｂに個別にドレーンされる。前に説明したように、再送出を介する伝送エラー回復のために、いずれにせよパケットの個々のコピーを各出ＦＩＦＯ２５０に置かなければならないことに留意されたい。
【００４８】
好ましい実施形態では、本願の所有者が所有する、同時係属の米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９−２００１０２１１ＵＳ２（１５２７５））、表題「A Novel Massively Parallel Supercomputer」に詳細に記載され、図１から３に関して本明細書で説明したように、各処理ノード１２が、システムオンアチップ・プロセスに基づく、すなわち、経路指定機能を含むコンピュータ・ノードのすべての機能が、単一のＡＳＩＣに集積され、ノード・サイズに関する劇的なサイズおよび電力の削減がもたらされる。このスーパーコンピュータ・アーキテクチャをさらに活用して、ノード密度を高め、これによって、計算機の総合的なコスト／性能を下げることができる。各ノードで、PowerPC  ４４０組込み処理コア、浮動小数点コア、組込みＤＲＡＭ、統合外部ＤＤＲメモリ・コントローラ、メッセージ・プロセッサ、イーサネット（Ｒ）・アダプタ、ならびにネットワーク・ルータを含むがこれに制限されない、多数の機能がコンピュータＡＳＩＣに組み込まれることが好ましい。一実施形態では、同一の計算ＡＳＩＣノードを、ファイルサーバ通信動作および入出力動作を処理するために、コンピュータ・ノードのサブセット、たとえば６４個のノードに関連する入出力ノードとして使用することができる。すなわち、入出力ノードは、コンピュータ・ノードに非常に似ているが、たとえばギガビット・イーサネット（Ｒ）などの外部ネットワーク・インターフェースの他に、外部メモリ構成に関してのみ異なる場合がある。本明細書に記載のツリー・ネットワーク・ルータが、好ましい実施形態の集積されたデバイスの他に、独立の装置として機能することができることを理解されたい。
【００４９】
本発明の例示的な事前に形成された実施形態に関して本発明を具体的に図示し、説明してきたが、形態および詳細における前述および他の変更を、本発明の趣旨および範囲から逸脱せずに行うことができ、本発明の趣旨および範囲が、請求項の範囲のみによって制限されなければならないことを理解されたい。
【図面の簡単な説明】
【００５０】
【図１】８つの計算ノードを相互接続する３次元トーラス・ネットワークを示す図である。
【図２】３５個のノード（円によって表される）およびノードのすべてを接続するツリー・ネットワーク１００を含む通常のシステムの例を示す図である。
【図３】図２のグローバル・ツリー・ネットワークで実施されるルータ装置の基本的なアーキテクチャを示す図である。
【図１】
2004536372.tif 000003
【図２】
2004536372.tif 000004
【図３】
2004536372.tif 000005
【国際公開パンフレット】
2004536372.tif 000006
2004536372.tif 000007
2004536372.tif 000008
2004536372.tif 000009
2004536372.tif 000010
2004536372.tif 000011
2004536372.tif 000012
2004536372.tif 000013
2004536372.tif 000014
2004536372.tif 000015
2004536372.tif 000016
2004536372.tif 000017
2004536372.tif 000018
2004536372.tif 000019
2004536372.tif 000020
2004536372.tif 000021
2004536372.tif 000022
2004536372.tif 000023
2004536372.tif 000024
2004536372.tif 000025
2004536372.tif 000026
2004536372.tif 000027
2004536372.tif 000028
2004536372.tif 000029
2004536372.tif 000030
2004536372.tif 000031
2004536372.tif 000032
【国際調査報告】
2004536372.tif 000033