(57)【要約】【課題】算術機能を実行する方法およびシステムを提供すること。【解決手段】本発明の第１の態様によれば、クラス・ネットワーク経路指定のソフトウェア・アルゴリズムおよびハードウェア実施形態とあいまって働く、トーラスでグローバル算術演算に必要な時間の非常に大幅な削減を達成する方法および装置が提供される。したがって、これは、大型並列計算機で稼動するアプリケーションのより高いスケーラビリティにつながる。本発明は、グローバル演算の効率および正確さを改善する、下記の３つのステップすなわち、（１）すべてのノードが、同一の順序でデータに対するグローバル演算を行い、したがって、丸め誤差と独立に、一意の答えを得ることを、必要な時に保証するステップ、（２）データ転送動作の時間ステップ数を絶対最小限まで減らすために、ホップ数およびネットワークの両方向能力を最小にするのにトーラスのトポロジを使用するステップ、および（３）データ転送の待ち時間を減らすためにクラス機能経路指定を使用するステップが含まれる。本発明の方法を用いて、すべての単一の要素が、１回だけネットワークに注入され、それ以上のソフトウェア・オーバーヘッドなしで保管され、転送される。本発明の第２の態様によれば、グローバル・コンバイニング演算をサポートするネットワークでグローバル算術演算を効率的に実施する方法およびシステムが提供される。そのようなグローバル演算を行う際の待ち時間が、この方法を使用することによって大幅に減らされる。
2005506596.tif 000002
【特許請求の範囲】
【請求項１】
複数の相互接続されたノードを有する分散並列トーラス・アーキテクチャを有するコンピュータ・システムで、シフト・アンド・オペレート手順を使用して算術機能を実行する方法であって、
前記ノードのグループのそれぞれにデータ値の同一の組を与えるステップと、
グローバル算術演算を実行するステップであって、前記ノードのそれぞれが、最終的な値を得るために前記データ値のすべてに対して前記算術演算を実行する、ステップと、
２進再現可能結果を保証するために、前記グループの前記ノードのすべてが、同一の順序で前記データ値に対する前記グローバル演算を実行することを保証するステップと
を含む方法。
【請求項２】
前記保証するステップが、各ノードが、前記ノードが前記データ値のすべてを与えられた後に、前記グローバル算術演算を実行するステップを含む、請求項１に記載の方法。
【請求項３】
前記与えるステップが、前記グループの各ノードが、前記グループの他のノードから前記データ値を受け取るステップを含む、請求項２に記載の方法。
【請求項４】
前記ノードが、両方向リンクによって一緒に接続され、前記与えるステップが、前記リンクを介して２方向で前記ノードに前記データ値を送るステップを含む、請求項１に記載の方法。
【請求項５】
前記与えるステップが、前記ノードのそれぞれが前記ネットワークに１回だけ前記データ値を注入するステップを含む、請求項１に記載の方法。
【請求項６】
前記注入するステップが、前記ノードの前記それぞれ以外のノードの前記グループのノードが、前記グローバル演算の待ち時間を減らすために、前記グループの他のノードに前記データ値の前記１つを転送するステップを含む、請求項５に記載の方法。
【請求項７】
複数の相互接続されたノードを有する分散並列トーラス・アーキテクチャを有するコンピュータ・システムで、シフト・アンド・オペレート手順を使用して算術機能を実行するシステムであって、
データ値の同一の組を与えられる前記ノードのグループと、
グローバル算術演算を実行する手段であって、前記ノードのそれぞれが、最終的な値を得るために前記データ値のすべてに対して前記算術演算を実行する、手段と、
２進再現可能結果を保証するために、前記グループの前記ノードのすべてが、同一の順序で前記データ値に対する前記グローバル演算を実行することを保証する手段と
を含むシステム。
【請求項８】
前記保証する手段が、各ノードで、前記ノードが前記データ値のすべてを与えられた後に、前記グローバル算術演算を実行する手段を含む、請求項７に記載のシステム。
【請求項９】
前記グループの各ノードが、前記グループの他のノードから前記データ値を受け取る、請求項７に記載のシステム。
【請求項１０】
前記ノードが、両方向リンクによって一緒に接続され、前記与える手段が、前記リンクを介して２方向で前記ノードに前記データ値を送る手段を含む、請求項７に記載のシステム。
【請求項１１】
前記ノードのそれぞれが前記ネットワークに１回だけ前記データ値を注入する、請求項７に記載のシステム。
【請求項１２】
前記ノードの前記それぞれ以外のノードの前記グループのノードが、前記グローバル演算の待ち時間を減らすために、前記グループの他のノードに前記データ値の前記１つを転送する、請求項７に記載のシステム。
【請求項１３】
複数の相互接続されたノードを有する分散並列トーラス・アーキテクチャを有するコンピュータ・システムで、シフト・アンド・オペレート手順を使用して算術機能を実行する方法ステップを実行するために計算機によって実行可能な命令のプログラムを有形に実施する、前記計算機によって可読のプログラム記憶装置であって、前記方法ステップが、
前記ノードのグループのそれぞれにデータ値の同一の組を与えるステップと、
グローバル算術演算を実行するステップであって、前記ノードのそれぞれが、最終的な値を得るために前記データ値のすべてに対して前記算術演算を実行する、ステップと、
２進再現可能結果を保証するために、前記グループの前記ノードのすべてが、同一の順序で前記データ値に対する前記グローバル演算を実行することを保証するステップと
を含むプログラム記憶装置。
【請求項１４】
前記保証するステップが、各ノードが、前記ノードが前記データ値のすべてを与えられた後に、前記グローバル算術演算を実行するステップを含む、請求項１３に記載のプログラム記憶装置。
【請求項１５】
前記与えるステップが、前記グループの各ノードが、前記グループの他のノードから前記データ値を受け取るステップを含む、請求項１４に記載のプログラム記憶装置。
【請求項１６】
前記ノードが、両方向リンクによって一緒に接続され、前記与えるステップが、前記リンクを介して２方向で前記ノードに前記データ値を送るステップを含む、請求項１３に記載のプログラム記憶装置。
【請求項１７】
前記与えるステップが、前記ノードのそれぞれが前記ネットワークに１回だけ前記データ値を注入するステップを含む、請求項１３に記載のプログラム記憶装置。
【請求項１８】
前記注入するステップが、前記ノードの前記それぞれ以外のノードの前記グループのノードが、前記グローバル演算の待ち時間を減らすために、前記グループの他のノードに前記データ値の前記１つを転送するステップを含む、請求項１７に記載のプログラム記憶装置。
【請求項１９】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムで算術機能を実行する方法であって、
ノードのグループのそれぞれに第１値を与えるステップと、
前記第１値のそれぞれからめいめいの第２値を得るために、第１定義済み処理に従って前記第１値のそれぞれを処理するステップであって、前記第２値のすべてが、整数値である、ステップと、
前記第２値を使用して、前記ネットワークにまたがるグローバル整数コンバイン動作を実行するステップと
を含む方法。
【請求項２０】
前記実行するステップが、前記ネットワークにまたがるグローバル符号なし整数合計を実行するステップを含む、請求項１９に記載の方法。
【請求項２１】
前記実行するステップが、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最大値を識別するために前記グローバル最大値演算の結果を使用するステップを含む、請求項１９に記載の方法。
【請求項２２】
前記実行するステップが、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最小値を識別するために前記グローバル最大値演算の結果を使用するステップを含む、請求項１９に記載の方法。
【請求項２３】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムで算術機能を実行するシステムであって、前記方法が、
ノードのグループであって、前記グループの前記ノードのそれぞれに第１値が与えられる、ノードのグループと、
前記第１値のそれぞれからめいめいの第２値を得るために、第１定義済み処理に従って前記第１値のそれぞれを処理するプロセッサであって、前記第２値のすべてが、整数値である、プロセッサと、
前記第２値を使用して、前記ネットワークにまたがるグローバル整数組合せ動作を実行する手段と
のステップを含むシステム。
【請求項２４】
前記実行する手段が、前記ネットワークにまたがるグローバル符号なし整数合計を実行する手段を含む、請求項２３に記載のシステム。
【請求項２５】
前記実行する手段が、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最大値を識別するために前記グローバル最大値演算の結果を使用する手段を含む、請求項２３に記載のシステム。
【請求項２６】
前記実行する手段が、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最小値を識別するために前記グローバル最大値演算の結果を使用する手段を含む、請求項２３に記載のシステム。
【請求項２７】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムで算術機能を実行する方法ステップを実行するために計算機によって実行可能な命令のプログラムを有形に実施する、前記計算機によって可読のプログラム記憶装置であって、前記方法ステップが、
ノードのグループのそれぞれに第１値を与えるステップと、
前記第１値のそれぞれからめいめいの第２値を得るために、第１定義済み処理に従って前記第１値のそれぞれを処理するステップであって、前記第２値のすべてが、整数値である、ステップと、
前記第２値を使用して、前記ネットワークにまたがるグローバル整数コンバイン・オペレーティングを実行するステップと
を含むプログラム記憶装置。
【請求項２８】
前記実行するステップが、前記ネットワークにまたがるグローバル符号なし整数合計を実行するステップを含む、請求項２７に記載のプログラム記憶装置。
【請求項２９】
前記実行するステップが、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最大値を識別するために前記グローバル最大値演算の結果を使用するステップを含む、請求項２７に記載のプログラム記憶装置。
【請求項３０】
前記実行するステップが、前記ネットワークにまたがるグローバル最大値演算を実行し、前記第１値の最小値を識別するために前記グローバル最大値演算の結果を使用するステップを含む、請求項２７に記載のプログラム記憶装置。
【請求項３１】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムでグローバル動作を実行する方法であって、
各ノードに任意のタイプの１つまたは複数の数を与えるステップと、
前記ノードの前記数をアレイに組み立てるステップであって、前記アレイが、所与の数の位置を有し、前記組み立てるステップが、
ｉ）各ノードが前記ノードの前記数の１つまたは複数を前記アレイの前記位置の１つまたは複数に置き、前記アレイの他の位置のすべてにゼロ値を置くステップと、
ｉ）前記アレイの各位置に置かれた前記数のすべてを合計するために前記グローバル・ツリー・ネットワークを使用するステップと
を含む、ステップと
を含む方法。
【請求項３２】
前記アレイの位置の前記所与の数が、定義済みシーケンスで配置され、
前記組み立てるステップが、さらに、各ノードが、やはり前記定義済みシーケンスで配置された前記所与の数の位置を有する関連するアレイを確立し、前記ノードの前記１つまたは複数の数を前記関連するアレイの１つまたは複数の位置に置き、前記関連するアレイの他の位置のすべてに０値を置くステップを含む
請求項３１に記載の方法。
【請求項３３】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムでグローバル動作を実行するシステムであって、
ノードのグループであって、ノードの前記グループのそれぞれが、１つまたは複数の数を与えられる、ノードのグループと、
前記ノードの前記数をアレイに組み立てる手段であって、前記アレイが、所与の数の位置を有し、前記組み立てる手段が、
ｉ）前記グループの前記ノードの１つまたは複数の前記数を前記アレイの１つまたは複数の前記位置に置き、前記アレイの他の位置のすべてにゼロ値を置く手段と、
ｉ）前記アレイの各位置に置かれた前記数のすべてを合計するために前記グローバル・ツリー・ネットワークを使用する手段と
を含む、組み立てる手段と
を含むシステム。
【請求項３４】
前記アレイの前記所与の数の位置が、定義済みシーケンスで配置され、
前記組み立てる手段が、さらに、やはり前記定義済みシーケンスで配置された前記所与の数の位置を有する、前記グループの前記ノードのそれぞれに関連するめいめいの１つのアレイを確立し、前記ノードのそれぞれの前記１つまたは複数の数を前記関連するアレイの１つまたは複数の前記位置に置き、前記関連するアレイの他の位置のすべてに０値を置く手段を含む
請求項３３に記載のシステム。
【請求項３５】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムでグローバル動作を実行する方法ステップを実行するために計算機によって実行可能な命令のプログラムを有形に実施する、前記計算機によって可読のプログラム記憶装置であって、前記方法ステップが、
各ノードに１つまたは複数の数を与えるステップと、
前記ノードの前記数をアレイに組み立てるステップであって、前記アレイが、所与の数の位置を有し、前記組み立てるステップが、
ａ．各ノードが前記ノードの１つまたは複数の前記数を前記アレイの１つまたは複数の前記位置に置き、前記アレイの他の位置のすべてにゼロ値を置くステップと、
ａ．前記アレイの各位置に置かれた前記数のすべてを合計するために前記グローバル・ツリー・ネットワークを使用するステップと
を含む、ステップと
を含むプログラム記憶装置。
【請求項３６】
前記アレイの前記所与の数の位置が、定義済みシーケンスで配置され、
前記組み立てるステップが、さらに、各ノードが、やはり前記定義済みシーケンスで配置された前記所与の数の位置を有する関連するアレイを確立し、前記ノードの前記１つまたは複数の数を前記関連するアレイの１つまたは複数の前記位置に置き、前記関連するアレイの他の位置のすべてに０値を置くステップを含む
請求項３５に記載の方法。
【請求項３７】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数を有するコンピュータ・システムで算術機能を実行する方法であって、
前記ノードのそれぞれが第１値の組を与えるステップと、
前記第１値を使用して、前記ネットワークにまたがるグローバル整数コンバイン動作を実行するステップと
を含む方法。
【請求項３８】
前記実行するステップが、前記第１値の特性を識別するために、前記グローバル整数コンバイン動作の結果を使用するステップを含む、請求項３７に記載の方法。
【請求項３９】
整数コンバイニング演算をサポートするグローバル・ツリー・ネットワークによって相互接続された複数のノードを有するコンピュータ・システムで算術機能を実行するシステムであって、
ノードのグループであって、前記グループの前記ノードのそれぞれが、第１値の組からなる、ノードのグループと、
前記第１値を使用して、前記ネットワークにまたがるグローバル整数コンバイン動作を実行するプロセッサと
を含むシステム。
【請求項４０】
前記プロセッサが、前記第１値の特性を識別するために、前記グローバル整数コンバイン動作の結果を使用する手段を含む、請求項３９に記載のシステム。
【請求項４１】
グローバル・ツリー・ネットワークおよびトーラス・ネットワークの両方によって相互接続された複数のノードを有する並列処理コンピュータ・システムを動作させる方法であって、
定義された動作を実行するために前記コンピュータ・システムを使用することと、
リダクション動作で協力するために前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用することと
を含む方法。
【請求項４２】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記ステップが、１つのプロセッサにトーラス動作を処理させ、別のプロセッサにツリー動作を処理させることによってそれを行うステップを含む、請求項４１に記載の方法。
【請求項４３】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記ステップが、３次元トーラスで、前記トーラス上のノードが３つ以上の組み合わせるべきパケットを受け取らないようにトーラス通信を配置することによってそれを行うステップを含む、請求項４１に記載の方法。
【請求項４４】
グローバル・ツリー・ネットワークおよびトーラス・ネットワークの両方によって相互接続された複数のノードを有する並列処理コンピュータ・システムを動作させる方法ステップを実行するために計算機によって実行可能な命令のプログラムを有形に実施する、前記計算機によって可読のプログラム記憶装置であって、前記方法ステップが、
定義された動作を実行するために前記コンピュータ・システムを使用することと、
リダクション動作で協力するために前記トーラス・ネットワークおよび前記３ネットワークの両方を使用することと
を含む、プログラム記憶装置。
【請求項４５】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記ステップが、１つのプロセッサにトーラス動作を処理させ、別のプロセッサにツリー動作を処理させることによってそれを行うステップを含む、請求項４４に記載のプログラム記憶装置。
【請求項４６】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記ステップが、３次元トーラスで、前記トーラス上のノードが３つ以上の組み合わせるべきパケットを受け取らないようにトーラス通信を配置することによってそれを行うステップを含む、請求項４４に記載のプログラム記憶装置。
【請求項４７】
並列処理コンピュータ・システムであって、
複数のノードと、
前記ノードを相互接続もするグローバル・ツリー・ネットワークと、
前記ノードを相互接続もするトーラス・ネットワークと、
リダクション動作で協力するために前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する手段と
を含む並列処理コンピュータ・システム。
【請求項４８】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記手段が、トーラス動作を処理する１つのプロセッサと、ツリー動作を処理する別のプロセッサとを含む、請求項４７に記載のコンピュータ・システム。
【請求項４９】
前記トーラス・ネットワークおよび前記ツリー・ネットワークの両方を使用する前記手段が、３次元トーラスで、前記トーラス上のノードが３つ以上の組み合わせるべきパケットを受け取らないようにトーラス通信を配置する手段を含む、請求項４７に記載のコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
米国仮出願番号６０／２７１，１２４、表題「A Novel MassivelyParallel SuperComputer」に、多数のコンピューティング・ノードおよびより少数の入出力ノードからなるコンピュータが記載されている。これらのノードは、複数のネットワークによって接続される。具体的に言うと、これらのノードは、トーラス・ネットワークと二重機能ツリー・ネットワークの両方によって相互接続される。このトーラス・ネットワークは、コンピュータの効率を改善するために複数の形で使用することができる。
【背景技術】
【０００２】
詳しく述べると、十分に多数のノードを有し、Ｍ次元トーラスの接続性を有するネットワークを有する計算機で、グローバル動作を行う通常の方法は、シフト・アンド・オペレート（shift and operate）によるものである。たとえば、すべてのノードに対するグローバル合計（MPI_SUM）を行うために、各計算ノードがそれ自体のローカル部分合計を行った後に、各ノードが、まず、ローカル合計を１つの次元に沿った＋方向の隣に送り、そのノードが隣から受け取った数にそれ自体の合計を加算する。第２に、ノードは、−方向の隣から受け取った数を、＋方向の隣に渡し、受け取った数をそれ自体の合計に加算する。第２ステップを（Ｎ−１）回（Ｎは、この１つの次元に沿ったノードの数である）繰り返した後に、１時に１次元ずつすべての次元についてこのシーケンス全体を繰り返すことによって、すべてのノードに対する所望の結果が得られる。しかし、浮動小数点数について、各ノードで実行される浮動小数点合計の次数が異なるので、各ノードは、各ノードで実行される浮動小数点合計の次数が異なるという事実に起因する丸め効果のゆえに、わずかに異なる結果でおわる。これは、グローバル合計の値に依存するグローバル判断が行われる場合に、問題を引き起こす。多くの場合に、この問題は、最初に他のすべてのノードからデータを集め、この計算全体を行い、次いですべてのノードに合計をブロードキャストする特別なノードを選択することによって回避される。しかし、ノードの数が十分に多い時に、この方法は、シフト・アンド・オペレート方法より低速である。
【０００３】
さらに、上で示したように、米国仮出願番号６０／２７１，１２４で開示されたコンピュータでは、ノードが、整数合計、整数最大値（max）、および整数最小値（min）などの整数コンバイニング演算をサポートする二重機能ツリー・ネットワークによっても接続される。グローバル・コンバイニング・ネットワークの存在によって、このネットワークにまたがるグローバル算術演算を効率的に実施する可能性が開かれる。たとえば、コンピューティング・ノードのそれぞれからの浮動小数点数の加算、およびすべての参加するノードへの合計のブロードキャストである。通常の並列スーパーコンピュータでは、この種の演算が、通常は、普通のメッセージ受渡トラフィックを搬送するネットワークを介して行われる。通常は、その種のグローバル動作に関連する長い待ち時間がある。
【特許文献１】
米国仮出願番号６０／２７１，１２４
【特許文献２】
米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００４４ＵＳ１（１５２７０））
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、分散並列コンピュータでグローバル動作に関するグローバル値を計算する改良された手順を提供することである。
【０００５】
本発明のもう１つの目的は、多数のノードを有する分散並列Ｍ−トーラス・アーキテクチャで非常に効率的な形でシフト・アンド・オペレート方法を使用してグローバル動作に関する一意のグローバル値を計算することである。
【０００６】
本発明のもう１つの目的は、クラス・ネットワーク経路指定のソフトウェア・アルゴリズムおよびハードウェア実施形態とあいまって働く、トーラス・アーキテクチャでグローバル算術演算に必要な時間の非常に大幅な削減を達成する方法および装置を提供することである。
【０００７】
本発明のもう１つの目的は、グローバル・コンバイニング演算をサポートするネットワークでのグローバル算術演算を効率的に実施することである。
【０００８】
本発明のもう１つの目的は、２進再現可能結果を生成するグローバル算術演算を実施することである。
【０００９】
本発明の１つの目的は、グローバル合計演算を行う改良された手順を提供することである。
【００１０】
本発明のもう１つの目的は、グローバル・オール・ギャザー（all gather）演算を行う改良された手順を提供することである。
【課題を解決するための手段】
【００１１】
上記および他の目的は、下で説明する、算術機能を実行する方法およびシステムによって達成される。本発明の第１の態様によれば、クラス・ネットワーク経路指定のソフトウェア・アルゴリズムおよびハードウェア実施形態とあいまって働く、トーラスでグローバル算術演算に必要な時間の非常に大幅な削減を達成する方法および装置が提供される。これは、大型並列計算機で稼動するアプリケーションのより高いスケーラビリティにつながる。本発明は、グローバル演算の効率、正確さ、および正確な再現可能性を改善する、下記の３つのステップが含まれる。
１．すべてのノードが、同一の順序でデータに対するグローバル演算を行い、したがって、丸め誤差と独立に、一意の答えを得ることを、必要な時に保証するステップ。
２．データ転送動作の時間ステップ数を絶対最小限まで減らすために、ホップ数およびネットワークの両方向能力を最小にするのにトーラスのトポロジを使用するステップ。
３．データ転送の待ち時間を減らすためにクラス機能経路指定（米国仮出願番号＿＿＿＿＿＿（ＹＯＲ９２００２００４４ＵＳ１（１５２７０）））を使用するステップ。本発明の方法を用いて、すべての単一の要素が、１回だけネットワークに注入され、それ以上のソフトウェア・オーバーヘッドなしで保管され、転送される。
【００１２】
本発明の第２の態様によれば、グローバル・コンバイニング演算をサポートするネットワークでグローバル算術演算を効率的に実施する方法およびシステムが提供される。そのようなグローバル演算を行う際の待ち時間が、これらの方法を使用することによって大幅に減らされる。具体的に言うと、整数最大値ＭＡＸ、加算ＳＵＭ、ビット単位ＡＮＤ、ビット単位ＯＲ、およびビット単位ＸＯＲをサポートするコンバイニング・ツリー・ネットワークを用いて、ＭＰＩ（Message-Passing Interface Standard）で事前定義されたグローバル・リダクション動作の事実上すべてすなわち、MPI_SUM、MPI_MAX、MPI_MIN、MPI_LAND、MPI_BAND、MPI_LOR、MPI_BOR、MPI_LXOR、MPI_BXOR、MPI_MAXLOC、およびMPI_MINLOCと、このネットワークでのMPI_ALLGATHERを実施することができる。実施形態は、簡単かつ効率的であり、コンバイニング・ツリー・ネットワークが大規模並列スーパーコンピュータにもたらす高い柔軟性および効率が実証される。
【００１３】
本発明のさらなる利益および長所は、本発明の好ましい実施形態を指定し、示す、添付図面と共に以下の詳細な説明を検討することから明白になる。
【発明を実施するための最良の形態】
【００１４】
本発明は、コンピュータでの算術演算の実行に関し、適するコンピュータの１つが、米国仮出願番号６０／２７１，１２４で開示されている。このコンピュータは、多数の計算ノードとより少数の入出力ノードからなり、このコンピュータのノードは、図１の１０に概略的に示されたトーラス・ネットワークと、図２の２０に概略的に示された二重機能ツリー・ネットワークの両方によって相互接続される。
【００１５】
具体的に言うと、本発明の１態様では、クラス・ネットワーク経路指定のソフトウェア・アルゴリズムおよびハードウェア実施形態とあいまって働く、トーラス・アーキテクチャでグローバル算術演算に必要な時間の非常に大幅な削減を達成する方法および装置が提供される。したがって、これは、大型並列計算機で稼動するアプリケーションのより高いスケーラビリティにつながる。図３からわかるように、本発明には、グローバル演算の効率および正確さを改善する、下記の３つのステップが含まれる。
１．すべてのノードが、同一の順序でデータに対するグローバル演算を行い、したがって、丸め誤差と独立に、一意の答えを得ることを、必要な時に保証するステップ。
２．データ転送動作の時間ステップ数を絶対最小限まで減らすために、ホップ数およびネットワークの両方向能力を最小にするのにトーラスのトポロジを使用するステップ。
３．データ転送の待ち時間を減らすためにクラス機能経路指定を使用するステップ。本発明の好ましい方法を用いて、すべての単一の要素が、１回だけネットワークに注入され、それ以上のソフトウェア・オーバーヘッドなしで保管され、転送される。
【００１６】
これらのステップのそれぞれを、下で詳細に説明する。
【００１７】
１．同一の順序でグローバル動作（たとえばMPI_SUM）に対するすべてのノードの保証：
ローカル部分合計の１次元シフトおよび加算を行う時に、入ってきた時に数を加算するのではなく、各ノードが、各方向で受信されるＮ−１個の数を保持する。グローバル動作は、数がすべて受け取られた後にそれらの数に対して実行され、その結果、動作が、固定された順序で実行され、すべてのノードで一意の結果がもたらされる。
【００１８】
たとえば、図４からわかるように、各ノードで、受信した時に数を加算する場合に、計算される合計は、ノード０ではS0+S3+S2+S1、ノード１ではS1+S0+S3+S2、ノード３ではS2+S1+S0+S3、ノード４ではS3+S2+S1+S0になる。これらの合計の間に、丸めの差があることになる。しかし、すべてのノードが受信する数が、メモリに保持される場合に、すべてのノードが同一の順序で合計を行って、S0+S1+S2+S3を得ることができ、丸めの差がなくなる。
【００１９】
これを、他のすべての次元について繰り返す。最後に、すべてのノードが、同一の数を有し、最終的なブロードキャストは不要である。
【００２０】
１．Ｍ−トーラス・アーキテクチャでデータ転送のステップ数を最小にする：
２つの隣接するノードの間のネットワーク・リンクが双方向であるすべての計算機で、ステップのそれぞれで両方向でデータを送ることができる。これは、各データ要素がネットワーク上で移動しなければならない総距離が、２分の１に減ることを意味する。これによって、トーラスでのグローバル算術を実行する時間も、およそ２分の１に減る。
【００２１】
１．クラス機能経路指定を使用する待ち時間の削減：
ネットワーク・ハードウェアにストア・アンド・フォワード・クラス・ネットワーク経路指定動作を含め、これによって、同一のデータ要素をネットワークから複数回抽出し、挿入するというソフトウェア・オーバーヘッドをなくすことによって、追加の性能利益を達成することができる。クラス経路指定が可能なネットワークでグローバル算術演算を実施する時に、図４に示されたステップ１から３が、単純に、単一のネットワーク・ステップになる、すなわち、各ノードが、数を１回だけ注入する必要があり、他のすべてのノードが、この数を、それを必要とするすべての他のノードに自動的に転送すると同時に、それ自体の使用のためにコピーを保持する。これによって、グローバル動作の待ち時間が大幅に減る。トーラスのすべてのホップでソフトウェア・オーバーヘッドをこうむるのではなく、計算機の次元ごとに単一のオーバーヘッド・コストだけをこうむる。たとえば、米国仮出願番号６０／２７１，１２４で開示されるコンピュータ・システムで、ＣＰＵが単一ユーザ・モードで稼動している時に少なくとも５倍、マルチユーザ・モードで１０倍を超える改善があると推定される。
【００２２】
上で述べた３つの改善ステップを用いて、分散並列アーキテクチャでのグローバル算術演算について少なくとも１０倍の改善を達成することができ、大型並列計算機でのアプリケーションのスケーラビリティも大幅に改善することができる。
【００２３】
さらに、前に述べたように、上で識別された米国仮出願に開示されたコンピュータ・システムでは、ノードが、整数合計、整数最大値、整数最小値、ビット単位AND、ビット単位OR、およびビット単位XORなどのデータ・コンバイニング演算をサポートするツリー・ネットワークによっても接続される。さらに、このツリー・ネットワークでは、最終的に組み合わされた結果が、すべての参加ノードに自動的にブロードキャストされる。グローバル・コンバイニング演算をサポートするコンピューティング・ネットワークを用いると、多数のグローバル通信パターンを、このネットワークによって効率的にサポートすることができる。コンバイニング・ネットワーク・ハードウェアに関する最も単純な要件は、ある精度までの符号なし整数加算および符号なし整数最大値をサポートすることである。たとえば、上で識別された米国仮出願書に開示されたスーパーコンピュータは、少なくとも３２ビット、６４ビット、および１２８ビットの符号なし整数の加算または最大値をサポートし、２０４８ビット・パケット・サイズまでの非常に長い精度の合計または最大値をサポートする。このネットワーク・ハードウェアのコンバイニング機能は、高性能グローバル算術機能を実施する際の高い柔軟性をもたらす。これらの実施形態の複数の例を、下で提示する。
【００２４】
１．符号付き整数のグローバル合計
図５に、グローバル合計の動作を示す。各参加ノードは、同数のアレイ要素を有する等しいサイズの数のアレイを有する。グローバル合計演算の結果は、各ノードが、すべてのノードからのアレイの対応する要素の合計を有することである。これは、ＭＰＩ（Message Passing Interface）標準規格のMPI_SUM機能に関連する。
【００２５】
通常は、最終結果の精度を維持するために、各ローカル数と比較して、ネットワーク内でより高い精度を使用する必要がある。Ｎが、合計に参加するノードの個数であり、Ｍが、合計される整数の最大の絶対値であり、2^Pが、Ｍを超える大きい正の整数であるものとする。符号なし演算をサポートするネットワークで符号付き整数合計を実施するためには、下記のことのみが必要である。
（１）大きい正の整数2^Pを、合計されるすべての数に加算し、その結果、これらが、非負になるようにする。
（１）ネットワークにまたがる符号なし整数合計を行う。
（１）結果から（N×2^P）を引く。
Ｐは、2^P>Mになるように選択され、（N×2^(P+1)）は、コンバイニング・ネットワークでオーバーフローしない。
【００２６】
２．符号付き整数のグローバルmaxおよびグローバルmin
これらの演算は、上で述べたグローバル合計に非常に似ているが、最終結果が、対応する要素の合計ではなく、最大の要素または最小の要素であることが異なる。これらは、整数入力を有する、ＭＰＩのMPI_MAX機能およびMPI_MIN機能に関連する。グローバルmaxの実施形態は、上で述べたグローバル合計の実施形態に非常に似ている。
（１）すべての数に大きい正の整数2^Pを加算して、非負にする。
（１）ネットワークにまたがる符号なしグローバルmaxを行う。
（１）結果から2^Pを引く。
グローバルminを行うには、すべての数の符号を反転し、グローバルmaxを行う。
【００２７】
３．浮動小数点数のグローバル合計：
浮動小数点数のグローバル合計の動作は、入力が浮動小数点数であることを除いて、前に説明した整数合計に非常に似ている。説明を簡単にするために、各ノードからの１つの数の合計を示す。アレイ合計を行うには、このステップを繰り返すだけである。
【００２８】
基本的な発想は、コンバイニング・ネットワークで２つのラウンド・トリップを行うことである。
（１）グローバルmaxの説明で概要を示したステップを使用して、すべての数の指数の整数の最大値Emaxを見つける。
（１）各ノードで、ローカルな数を正規化し、整数に変換する。ノード「ｉ」のローカルな数が、X_iであり、その指数がE_iであるものとする。グローバル合計の説明で定義した表記を使用すると、この変換は次の計算に対応する。
A_i=2^P+2^[P-(Emax-E)-1]×X_i    （式１）
ここで、A_iは、符号なし整数である。グローバル符号なし整数合計を、コンバイニング・ハードウェアを使用してネットワークで実行することができる。各ノードで最終的な合計Ａに達した時に、真の合計Ｓは、ローカルに下記を計算することによって各ノードで得ることができる。
S=(A-N×2^P)/2^(P-1)
やはり、Ｐは、N×2^(P+1)がコンバイニング・ネットワークでオーバーフローしないように選択される。
【００２９】
マイクロプロセッサの浮動小数点ユニットを使用して、負の数を正に変換し、その後、整数ユニットを使用して正しいシフトを行うことによって、上の式（１）で行われるステップが、可能な最高の精度で達成されることに留意されたい。
【００３０】
この浮動小数点合計アルゴリズムの重要な特徴の１つは、実際の合計が整数合計を介して行われるので、合計が実行される順序に対する依存性がないことである。各参加ノードは、グローバル合計の後に、正確に同一の数を得る。通常は、浮動小数点グローバル合計が通常のメッセージ受渡ネットワークを介して実施される場合に必要な、特殊なノードからの追加のブロードキャストは不要である。
【００３１】
当業者は、ネットワーク・ハードウェアが符号なし整数合計だけをサポートする場合であっても、整数が２の補数フォーマットで表される時に、オーバーフローが最後の結果および中間結果で発生せず、２つの数に対する合計のキャリー・ビットがハードウェアによって捨てられる限り、正確な合計が得られることを諒解するであろう。グローバル整数合計およびグローバル浮動小数点合計に対する動作ステップの単純化は、ネットワーク・ハードウェアが正しいオーバーフロー処理を用いて符号付き整数合計をサポートする時と同様に、本発明の範囲に含まれる。
【００３２】
たとえば、米国仮出願番号６０／２７１，１２４に開示されたスーパーコンピュータで実施されるように、ハードウェアが、符号なし整数合計だけをサポートし、符号なし整数オーバーフローからのキャリー・ビットのすべてを捨てる時に、単純化された符号付き整数合計ステップを、次のようにすることができる。
（１）各整数をより高い精度に符号拡張して、結果のオーバーフローが全く発生しないようにする。すなわち、正の整数および０について、拡張された上位ビットのすべてに０を埋め込み、負の整数の拡張されたビットのすべてに１を埋め込む。
（２）ネットワークにまたがって合計を行う。最終的な結果は、正しい符号を有する。
上記を、浮動小数点合計の合計ステップにも適用することができる。
【００３３】
整数のグローバル合計の説明からグローバルmaxの説明への修正に類似する修正を用いて、浮動小数点のmaxおよびminも、簡単に得ることができる。
【００３４】
非負数の浮動小数点ｍａｘにも特別な場合があり、その動作は、２つではなく１つのラウンド・トリップで達成することができる。浮動小数点２進算術（Floating Point Binary Arithmetic）フォーマットに関するＩＥＥＥ  ７５４標準規格を使用する数について、近代マイクロプロセッサのほとんどで、追加のローカル動作は不要である。正しいバイト順序付けを用いて、各ノードが、数をコンバイニング・ネットワークに置くことができる。一部のディジタル信号プロセッサで使用されるものなどの他の浮動小数点フォーマットについて、指数フィールドのあるローカル操作が必要になる場合がある。負の数のminについても、その絶対値に対するグローバルmaxを行うことによって、同一の単一のラウンド・トリップを達成することができる。
【００３５】
４．整数グローバル合計を使用するグローバル・オール・ギャザー動作
グローバル・オール・ギャザー動作を、図６に示す。各ノードが、１つまたは複数の数を与える。最終結果は、その位置が数が来た元の位置に対応するアレイに置かれた数である。たとえば、ノード１からの数は、最終的なアレイで最初に現れ、その後にノード２、…などからの数が続く。この演算は、ＭＰＩ標準規格のMPI_ALLGATHER機能に対応する。
【００３６】
この機能は、整数合計をサポートするコンバイニング・ネットワークでの１パス動作で簡単に実施することができる。ある数に０を加算すると同一の数が得られるという事実を使用して、各ノードは、単に、サイズが最終的なアレイと等しいアレイを組み立て、対応する位置に数を置き、他のすべてのノードからの数に対応する他のすべての位置に０を置く必要がある。コンバイニング・ネットワークを介するすべてのノードからのアレイの整数合計の後に、各ノードは、すべての数をその数の位置に分類された最終的なアレイを有する。
【００３７】
５．整数グローバルmaxを使用するグローバルmin_locおよびグローバルmax_loc
これらの機能は、ＭＰＩ標準規格のMPI_MINLOCおよびMPI_MAXLOCに対応する。グローバル最小値またはグローバル最大値を見つける他に、数のそれぞれにインデックスが付加され、その結果、たとえば、どのノードがグローバル最小値またはグローバル最大値を有するかを見つけることができる。
【００３８】
整数グローバルmaxをサポートするコンバイニング・ネットワークでは、これらの機能は、実施が単純である。例として、グローバルmax_locを示す。ノード「ｊ」、ｊ＝１、…、Ｎが、数X_jおよびインデックスK_jを有するものとする。Ｍが、M>max(K_j)の大きい整数であるものとすると、ノード「ｊ」は、下記の２つの数を、グローバル整数maxに関して単一の単位としてコンバイニング・ネットワークに置くことだけが必要である：
X_j
M-K_j
動作の終りに、各ノードは、
X
M-K
を受け取る。ここでX=max(X_j)は、すべてのX_jの最大値であり、Ｋは、最大値Ｘに対応するインデックス番号である。最大値Ｘと等しい複数の数がある場合には、Ｋは、最小のインデックス番号になる。
【００３９】
グローバルmin_locは、上のX_jをP-X_jに変更することによって達成することができ、ここで、Ｐは、大きい正の整数であり、P>max(X_j)である。
【００４０】
グローバルmax動作またはグローバルmix動作で数の後ろにインデックス番号を付加するという発想は、浮動小数点数にも適用される。上で浮動小数点数のグローバル合計の実行の手順の説明で述べた物に類似するステップを用いて。
【００４１】
６．他の動作：
米国仮出願番号６０／２７１，１２４に記載のスーパーコンピュータ・システムでは、追加のグローバル・ビット単位AND動作、グローバル・ビット単位OR動作、およびグローバル・ビット単位XOR動作も、コンバイニング・ネットワークでサポートされる。これによって、ＭＰＩ標準規格のMPI_BAND、MPI_BOR、およびMPI_BXORなどのグローバル・ビット単位リダクション動作の非常に簡単な実施が可能になる。基本的に、各ノードは、グローバル動作のオペランドをネットワークに置くことだけが必要であり、グローバル動作は、ハードウェアによって自動的に処理される。
【００４２】
さらに、論理動作MPI_LAND、MPI_LOR、およびMPI_LXORも、ビット単位動作で１ビットだけを使用することによって、実施することができる。
【００４３】
最後に、グローバル動作のそれぞれに、グローバル・バリア動作も含まれる。これは、すべてのオペランドがネットワークに注入されるまで、ネットワークが進行しないからである。したがって、効率的なMPI_BARRIER動作を、グローバル・ビット単位ANDなどのグローバル算術演算のいずれかを使用して実施することができる。
【００４４】
７．トーラス・ネットワークとツリー・ネットワークの両方を使用する動作：
トーラス・ネットワークとツリー・ネットワークの相対帯域幅に依存し、浮動小数点表現と固定小数点表現の間の変換に必要なオーバーヘッドに依存して、トーラス・ネットワークとツリー・ネットワークの両方を同時に使用して、グローバル浮動小数点リダクション動作を行うことがより効率的になる場合がある。そのような場合には、トーラスが、リダクション動作を行うのに使用され、ツリーが、結果をすべてのノードにブロードキャストするのに使用される。トーラスでリダクションを行う従来技術は、既知である。しかし、従来技術では、ブロードキャスト相も、トーラスで行われる。たとえば、図７の３０に示された３×４トーラス（またはメッシュ）で、リダクションが、行に沿って行われ、その後、行の終りでノードによって列に沿って行われる。具体的に言うと、合計リダクションでは、図７に、パケットを挿入し、ノードＱ２１に送るノードＱ２０が示されている。Ｑ２１は、対応する要素を着信パケットの要素に加算し、合計を含むパケットをＱ２２に送ることによって、このパケットを処理する。Ｑ２２は、対応する要素を着信パケットの要素に加算し、合計を含むパケットをＱ２３に送ることによって、このパケットを処理する。これらの動作が、行ごとに繰り返される。ノードＱ２３は、Ｑ２２からのパケットの対応する値とそのローカル値を合計し、結果のパケットをＱ１３に送る。ノードＱ１３は、Ｑ１２およびＱ２３からのパケットの値とそのローカル値を合計し、結果の合計をＱ０３に送る。Ｑ０３は、Ｑ１３からのパケットの対応する値とそのローカル値を合計する。Ｑ０３は、グローバル合計を有する。従来技術では、このグローバル合計が、トーラス・ネットワークを介して（図示のツリー上ではなく）すべての他のノードに送られる。より多数のノードへおよびより高次元のトーラスへの拡張は、当業者の能力の範囲内であり、本発明の範囲内である。多数の値にまたがるリダクションについて、複数のパケットが、パイプライン化された形で使用される。
【００４５】
しかし、最終的なブロードキャスト動作は、トーラス・ネットワークではなくツリー・ネットワークを使用することによって、より高速かつより効率的に行うことができる。これを、図８に示す。あるプロセッサにトーラスでのリダクション動作を処理させ、第２のプロセッサにツリーでブロードキャストされるパケットの受取を処理させることによって、性能を最適化することができる。リダクション・ステップでのホップ数を減らすことによって、さらに性能を最適化することができる。たとえば、パケットを、行の端ではなく、行の中央に送る（かつ合計する）ことができる。
【００４６】
３次元トーラスでは、上記の単純な拡張が、各ｚ平面内の単一のノードでのｚ次元での値の合計をもたらす。これは、これらのノードが３つの着信パケットを処理することを必要とするという不利益がある。たとえば、ノードＱ０３ｚは、Ｑ０２ｚ、Ｑ１３ｚ、およびＱ０３（ｚ＋１）からのパケットを受け取らなければならない。プロセッサが十分に高速でない場合には、これが、この動作のボトルネックになる。性能を最適化するために、通信パターンを変更し、その結果、トーラスで２つを超える着信パケットを処理する必要があるノードをなくす。これを、図８に示す。この図では、ノードＱ０３ｚが、そのパケットを、ｚ次元での合計のためにノードＱ００ｚに転送する。さらに、ノードＱ００ｚは、そのパケットをノードＱ０１ｚに送るのではなく、ノードＱ００（ｚ＋１）からパケットを受け取り、そのローカル値と２つの着信パケット内の対応する値を合計する。最後に、ノードＱ０００が、最終的な合計をツリー・ネットワークを介してブロードキャストする。
【００４７】
本明細書で開示された発明が、上で述べた目的を満たすように十分に考慮されていることは明白であるが、多数の修正形態および実施形態を当業者が考案できることを諒解されたい。添付の請求項が、そのような修正形態および実施形態のすべてを、本発明の真の趣旨および範囲に含まれるものとして包含することが意図されている。
【図面の簡単な説明】
【００４８】
【図１】コンピュータのノードを接続するトーラス・ネットワークを表す概略図である。ラップされたネットワーク接続は図示されていない。
【図２】コンピュータのノードを接続するツリー・ネットワークを概略的に示す図である。
【図３】１次元トーラスでグローバル合計を実行する手順を示す図である。
【図４】トーラス・アーキテクチャでグローバル算術演算の効率を改善するのに使用することができるテーブル識別ステップを示す図である。
【図５】二重機能ツリー・ネットワークでのグローバル合計の動作を示す図である。
【図６】二重機能ツリー・ネットワークでのグローバル・オール・ギャザーの動作を示す図である。
【図７】３×４トーラス・ネットワークを示す図である。
【図８】最終的なブロードキャスト動作を行うツリー・ネットワークを示す図である。
【図１】
2005506596.tif 000003
【図２】
2005506596.tif 000004
【図３】
2005506596.tif 000005
【図４】
2005506596.tif 000006
【図５】
2005506596.tif 000007
【図６】
2005506596.tif 000008
【図７】
2005506596.tif 000009
【図８】
2005506596.tif 000010
【国際公開パンフレット】
2005506596.tif 000011
2005506596.tif 000012
2005506596.tif 000013
2005506596.tif 000014
2005506596.tif 000015
2005506596.tif 000016
2005506596.tif 000017
2005506596.tif 000018
2005506596.tif 000019
2005506596.tif 000020
2005506596.tif 000021
2005506596.tif 000022
2005506596.tif 000023
2005506596.tif 000024
2005506596.tif 000025
2005506596.tif 000026
2005506596.tif 000027
2005506596.tif 000028
2005506596.tif 000029
2005506596.tif 000030
2005506596.tif 000031
2005506596.tif 000032
2005506596.tif 000033
2005506596.tif 000034
2005506596.tif 000035
2005506596.tif 000036
2005506596.tif 000037
2005506596.tif 000038
2005506596.tif 000039
2005506596.tif 000040
2005506596.tif 000041
2005506596.tif 000042
2005506596.tif 000043
【国際調査報告】
2005506596.tif 000044
2005506596.tif 000045