(57)【要約】【課題】超並列型スーパーコンピュータでの問題レイアウトを最適化するための、汎用コンピュータが実施する方法および装置を提供すること。【解決手段】この方法では、エントリＣ（ｉ，ｊ）がドメインｉからドメインｊに送られるデータの量であるアレイの形の、任意の問題の通信マトリクスを入力として採用する。Ｃ（ｉ，ｊ）が与えられた場合、第１に、スーパーコンピュータ・ノードにマッピングされるドメイン数を（できる限り）一定に保ちながら、ドメインおよびその通信近隣を、同じスーパーコンピュータ・ノードまたはスーパーコンピュータ・トーラス上の近隣ノードのいずれかに順次マッピングすることを試行する、ヒューリスティック・マップが実施される。【選択図】  図１０
2008516346.tif 000002
【特許請求の範囲】
【請求項１】
並列処理システム上の２つまたはそれ以上の並列計算ノードにわたってソフトウェア・アプリケーションの割り振りを最適化するためのコンピュータ実施方法であって、
通信ファブリックによって互いに結合された並列処理システム上の２つまたはそれ以上の並列計算ノードにわたって実行するための複数のソフトウェア計算を有する、ソフトウェア・アプリケーションの通信プロファイルを受け取るステップであって、前記複数のソフトウェア計算のうちの少なくとも第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含む、受け取るステップと、
ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にするステップであって、前記通信コストは、前記ソフトウェア・アプリケーションが前記ソフトウェア計算間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、最小にするステップと、
を有する、コンピュータ実施方法。
【請求項２】
ノード間で転送されるソフトウェア・アプリケーション・データの前記合計量が、前記ソフトウェア・アプリケーションの前記通信コストを削減するように、グローバルおよび離散時間間隔のうちの少なくとも１つで最小化される、請求項１に記載のコンピュータ実施方法。
【請求項３】
前記通信コストが、使用可能通信トポロジの使用、ネットワーク・トポロジのタイプ、バッファの可用度、ネットワーク・トポロジでのコンテンション、ソフトウェア・アプリケーション・オーバヘッド、および通信待ち時間のうちの、少なくとも１つに依存する、請求項１に記載のコンピュータ実施方法。
【請求項４】
前記コスト関数を数学的に最小にすることに応答して、少なくとも前記ソフトウェア計算で、前記複数のノードのうちの１つから前記複数のノードのうちの他のノードへ再配置するステップをさらに有する、請求項１に記載のコンピュータ実施方法。
【請求項５】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、以前にマッピングされたノードと共にアプリケーション・データを送る前記ソフトウェア計算のそれぞれが、最近隣にあるノードとして定義された近隣ノードにマッピングされるように、前記ソフトウェア計算のそれぞれを前記ノードのうちの１つに順次マッピングするヒューリスティック・マップを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項６】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、それらの間で送られるソフトウェア・アプリケーション・データの量に関して最大限に独立したソフトウェア計算を識別する、グラフ区画マップを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項７】
前記グラフ区画マップが、グラフ内のクリークおよびバイクリークを決定するために少なくとも１つのアルゴリズムを使用するステップを含む、請求項６に記載のコンピュータ実施方法。
【請求項８】
前記グラフ区画マップがＭＥＴＩＳツールを使用するステップを含む、請求項６に記載のコンピュータ実施方法。
【請求項９】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、並列処理システム上の２つまたはそれ以上の並列計算ノードｊにわたって実行するための複数のソフトウェア計算ｉを有し、前記複数のソフトウェア計算のうちの少なくとも前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも前記第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、Ｃ（ｉ，ｊ）によって与えられた前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記ノード間通信コスト関数が、前記第１のソフトウェア・アプリケーションを前記２つまたはそれ以上のノードのうちの第２のノードへ再配置することによって、前記２つまたはそれ以上のノードのうちの第１のノードに割り振られる前記第１のソフトウェア・アプリケーションについて、Ｆ＝Σｉ，ｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）によって与えられ、前記ノード間通信コスト関数が、前記第１のノードで送られるソフトウェア・アプリケーション・データの前記量と、Ｈ（ｉ，ｊ）によって与えられる、前記第１のノードがソフトウェア・アプリケーション・データを送信した際に使用した前記第１のノードと残りのすべてのノードとの間の通信パス・コスト／データ単位との、積によって与えられる、請求項１に記載のコンピュータ実施方法。
【請求項１０】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、各ノードがそれらの間にトーラス通信ネットワークを備えて３Ｄ格子に配置構成される、並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項１１】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータである並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項１２】
２つのアプリケーション・データ構造間でデータを転送する並列処理システム上の２つまたはそれ以上の並列計算ノードにわたってソフトウェア・アプリケーションの割り振りを最適化するためのコンピュータ・プログラムであって、
処理回路によって読み取り可能であり、
通信ファブリックによって互いに結合された並列処理システム上の２つまたはそれ以上の並列計算ノードにわたって実行するための複数のソフトウェア計算を有する、ソフトウェア・アプリケーションの通信プロファイルを受け取るステップであって、前記複数のソフトウェア計算のうちの少なくとも第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含む、受け取るステップと、
ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にするステップであって、前記通信コストは、前記ソフトウェア・アプリケーションが前記ソフトウェア計算間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、最小にするステップと、
を有する方法を実行するための、処理回路による実行のためのコンピュータ命令を格納した、
コンピュータ読み取り可能記憶媒体を備える、コンピュータ・プログラム。
【請求項１３】
ノード間で転送されるソフトウェア・アプリケーション・データの前記合計量が、前記ソフトウェア・アプリケーションの前記通信コストを削減するように、グローバルおよび離散時間間隔のうちの少なくとも１つで最小化される、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
前記通信コストが、使用可能通信トポロジの使用、ネットワーク・トポロジのタイプ、バッファの可用度、ネットワーク・トポロジでのコンテンション、ソフトウェア・アプリケーション・オーバヘッド、および通信待ち時間のうちの、少なくとも１つに依存する、請求項１２に記載のコンピュータ・プログラム。
【請求項１５】
前記コスト関数を数学的に最小にすることに応答して、少なくとも前記ソフトウェア計算で、前記複数のノードのうちの１つから前記複数のノードのうちの他のノードへ再配置するステップをさらに有する、請求項１２に記載のコンピュータ・プログラム。
【請求項１６】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、以前にマッピングされたノードと共にアプリケーション・データを送る前記ソフトウェア計算のそれぞれが、最近隣にあるノードとして定義された近隣ノードにマッピングされるように、前記ソフトウェア計算のそれぞれを前記ノードのうちの１つに順次マッピングするヒューリスティック・マップを受け取るステップを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１７】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、それらの間で送られるソフトウェア・アプリケーション・データの量に関して最大限に独立したソフトウェア計算を識別する、グラフ区画マップを受け取るステップを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１８】
前記グラフ区画マップが、グラフ内のクリークおよびバイクリークを決定するために少なくとも１つのアルゴリズムを使用するステップを含む、請求項１７に記載のコンピュータ・プログラム。
【請求項１９】
前記グラフ区画マップがＭＥＴＩＳツールを使用するステップを含む、請求項１７に記載のコンピュータ・プログラム。
【請求項２０】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、並列処理システム上の２つまたはそれ以上の並列計算ノードｊにわたって実行するための複数のソフトウェア計算ｉを有し、前記複数のソフトウェア計算のうちの少なくとも前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも前記第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、Ｃ（ｉ，ｊ）によって与えられた前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記ノード間通信コスト関数が、前記第１のソフトウェア・アプリケーションを前記２つまたはそれ以上のノードのうちの第２のノードへ再配置することによって、前記２つまたはそれ以上のノードのうちの第１のノードに割り振られる前記第１のソフトウェア・アプリケーションについて、Ｆ＝Σｉ，ｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）によって与えられ、前記ノード間通信コスト関数が、前記第１のノードで送られるソフトウェア・アプリケーション・データの前記量と、Ｈ（ｉ，ｊ）によって与えられる、前記第１のノードがソフトウェア・アプリケーション・データを送信した際に使用した前記第１のノードと残りのすべてのノードとの間の通信パス・コスト／データ単位との、積によって与えられる、請求項１２に記載のコンピュータ・プログラム。
【請求項２１】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、各ノードがそれらの間にトーラス通信ネットワークを備えて３Ｄ格子に配置構成される、並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項２２】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータである並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１２に記載のコンピュータ・プログラム。
【請求項２３】
複数の独立ネットワークによって相互接続された少なくとも２つの並列計算ノードを備え、各ノードは、通信プロファイルに従って複数の並列アルゴリズム操作を含むソフトウェア・アプリケーションを実行する場合に、計算および通信アクティビティのうちの少なくとも１つを必要に応じて実行するための１つまたは複数の処理要素を含み、前記複数の独立ネットワークは、少なくとも１つのノードおよびその独立した区画サブセットの間で、ポイント・ツー・ポイント、グローバル・ツリー通信、ならびにグローバル・バリアおよび通知操作を実行可能にするためのネットワークを含み、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、前記ソフトウェア・アプリケーションの帯域幅および待ち時間の要件に従って、協調的および単独の少なくとも１つで利用され、前記複数のソフトウェア計算のうちの少なくとも第１のソフトウェア計算は、前記複数のソフトウェア・アルゴリズムのうちの少なくとも第２のソフトウェア・アプリケーションからアプリケーション・データを送り、通信プロファイルは、前記ソフトウェア・アルゴリズムのそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にすることによって利用され、前記通信コストは、前記ソフトウェア・アルゴリズムが前記ソフトウェア・アルゴリズム間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、
超並列処理システム・コンピューティング・ストラクチャ。
【請求項２４】
ノード間で転送されるソフトウェア・アプリケーション・データの前記合計量が、前記ソフトウェア・アプリケーションの前記通信コストを削減するように、グローバルおよび離散時間間隔のうちの少なくとも１つで最小化される、請求項２３に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項２５】
前記通信コストが、使用可能通信トポロジの使用、ネットワーク・トポロジのタイプ、バッファの可用度、ネットワーク・トポロジでのコンテンション、ソフトウェア・アプリケーション・オーバヘッド、および通信待ち時間のうちの、少なくとも１つに依存する、請求項２３に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項２６】
前記コスト関数を数学的に最小にすることに応答して、少なくとも前記ソフトウェア計算で、前記複数のノードのうちの１つから前記複数のノードのうちの他のノードへ再配置するための手段をさらに有する、請求項２３に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項２７】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、以前にマッピングされたノードと共にアプリケーション・データを送る前記ソフトウェア計算のそれぞれが、最近隣にあるノードとして定義された近隣ノードにマッピングされるように、前記ソフトウェア計算のそれぞれを前記ノードのうちの１つに順次マッピングするヒューリスティック・マップを受け取るステップを含む、請求項２３に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項２８】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、それらの間で送られるソフトウェア・アプリケーション・データの量に関して最大限に独立したソフトウェア計算を識別する、グラフ区画マップを受け取るステップを含む、請求項２３に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項２９】
前記グラフ区画マップが、グラフ内のクリークおよびバイクリークを決定するために少なくとも１つのアルゴリズムを使用するステップを含む、請求項２８に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項３０】
前記グラフ区画マップがＭＥＴＩＳツールを使用するステップを含む、請求項２８に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項３１】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、並列処理システム上の２つまたはそれ以上の並列計算ノードｊにわたって実行するための複数のソフトウェア計算ｉを有し、前記複数のソフトウェア計算のうちの少なくとも前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも前記第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、Ｃ（ｉ，ｊ）によって与えられた前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記ノード間通信コスト関数が、前記第１のソフトウェア・アプリケーションを前記２つまたはそれ以上のノードのうちの第２のノードへ再配置することによって、前記２つまたはそれ以上のノードのうちの第１のノードに割り振られる前記第１のソフトウェア・アプリケーションについて、Ｆ＝Σｉ，ｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）によって与えられ、前記ノード間通信コスト関数が、前記第１のノードで送られるソフトウェア・アプリケーション・データの前記量と、Ｈ（ｉ，ｊ）によって与えられる、前記第１のノードがソフトウェア・アプリケーション・データを送信した際に使用した前記第１のノードと残りのすべてのノードとの間の通信パス・コスト／データ単位との、積によって与えられる、請求項２８に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項３２】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、各ノードがそれらの間にトーラス通信ネットワークを備えて３Ｄ格子に配置構成される、並列処理システム上で前記プロファイルを受け取るステップを含む、請求項２８に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項３３】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータである並列処理システム上で前記プロファイルを受け取るステップを含む、請求項２８に記載の超並列処理システム・コンピューティング・ストラクチャ。
【請求項３４】
並列アルゴリズム操作を実行する場合、各ノードが必要に応じて計算または通信アクティビティを実行するための１つまたは複数の処理要素を含む、独立ネットワークによって相互接続された複数の処理ノードと、
ネットワークのノードまたはノードのサブセットの間で、高速、低待ち時間の、ポイント・ツー・ポイントおよびマルチキャスト・パケット通信を提供するために最適化された方法でノードを相互接続する、通信リンクを含むｎ次元トーラス・ネットワークを備える、第１の独立ネットワークと、
前記ネットワークのノードまたはノードのサブセットの間で、同時グローバル操作を容易にするノード相互接続を備える、スケーラブルなグローバル・ツリー・ネットワークを含む、第２の前記複数の独立ネットワークと、
通信プロファイルに従って、ならびに、前記複数のソフトウェア計算のうちの少なくとも前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの少なくとも前記第２のソフトウェア・アプリケーションからアプリケーション・データを送る要件に従って、独立処理ネットワークの１つまたは複数の組み合わせを動的に構成するための区画化手段であって、前記通信プロファイルは、前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含む、区画化手段と、
前記第１および第２のネットワークの分割可能部分によって相互接続された処理ノードの構成可能サブセットを含む各独立ネットワークであって、前記構成された独立処理ネットワークのそれぞれが、ソフトウェア・アプリケーション処理性能を最適化するための同時協調処理を実行可能にするために利用される、各独立ネットワークと、
を備える、スケーラブルな超並列コンピューティング・ストラクチャであって、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にすることによって協調的または単独で利用され、前記通信コストは、前記ソフトウェア・アルゴリズムが前記ソフトウェア計算間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、スケーラブルな超並列コンピューティング・ストラクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にスーパーコンピュータのシステムおよびアーキテクチャの分野に関し、とりわけ、スーパーコンピュータ・システム上での実行時間を最小にするために、任意の並列アプリケーションを最適にマッピングすることに関する。
【背景技術】
【０００２】
超並列コンピューティング・ストラクチャ（「超大規模コンピュータ」または「スーパーコンピュータ」とも呼ばれる）は、多数の計算ノードを相互接続する。相互接続トポロジは、時には周期的境界条件を備えるツリーまたはグリッドなどの規則正しいストラクチャの形であることがかなり多い。最も費用対効果の高い超大規模コンピュータのための従来の手法は、メッセージ・パッシング通信をサポートする相互接続ネットワークを備え、ユニプロセッサまたは対称マルチプロセッサ（ＳＭＰ）構成で構成された、標準プロセッサ（ノード）を使用することである。現在、これらのスーパーコンピューティング・マシンは、テラＯＰＳ規模を達成するコンピューティング性能を示している。スーパーコンピュータの一例が、ニューヨーク州アーモンクのインターナショナル・ビジネス・マシンズ・コーポレーションによって発表されたＢｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータ（ＢＧ／Ｌ）である。ＢＧ／Ｌアーキテクチャに関する一般的な情報は、論文、“The Blue Gene/L Supercomputer”, by G.Bhanot, D.Chen, A.Gara andP.Vranas, Nucl. Phys. B (Proc. Suppl.) 119 (2003) 114を備えた、オンラインＵＲＬ（http://sc2002.org/paperpdfs/pap.pap207.pdf）で入手可能である。ＢＧ／Ｌは、３Ｄトーラス（torus）トポロジを使用する最近隣ネットワーク、およびグローバル・ツリーの、２つのデータ通信ネットワークを有する超並列コンピュータである。通常の使用では、トーラスは基本通信ネットワークであり、ポイント・ツー・ポイント通信およびグローバルまたは共同（collective）通信の両方に使用される。ツリーは、典型的には集合通信に使用される。
【０００３】
ＢＧ／Ｌ上のコンピュータ・ノードは論理的には３Ｄ格子に配置構成され、トーラス通信ネットワークはその格子内の最近隣間にのみ物理リンクを提供する。したがって、ノード間のすべての通信は使用可能な物理接続を使用するようにルーティングしなければならず、ノード間の通信コストは、関連するノードと、バッファの可用度、ネットワークを介した使用可能パスの数、ネットワーク・コンテンションなどの他の効果との間の距離に応じて変化する。したがって最大の課題は、通信時間および計算時間の関数である合計実行時間を最小にするために、任意の並列アプリケーションを最適にマッピングすることである。
【０００４】
並列コンピュータで構成することが効率的な使用である場合、最適な負荷バランスを達成するように、およびプロセッサ間通信を最小にするように、並列処理コンピュータのプロセッサにタスクを割り当てる問題が重要である。この問題については、近年多くのグループによって研究されてきた。しかしながら、通信コストではなく計算バランスを相対的に重視すること、ならびにプロセッサの数およびプロセッサ間ネットワーク・アーキテクチャに関する想定が様々に異なることにより、この問題に対して多くの異なる手法が生じてきた。
【０００５】
プロセッサが少数である場合、多くの技法を首尾良く適用することができる。たとえば、その全文が参照により本明細書に組み込まれた、”Task Assignment on Distributed-Memory Systems with AdaptiveWormhole Routing”, Vibha A. Dixit-Radiya and Dhabaleswar K. Panda, Symposium onParallel and Distributed Processing (SPDP ’93), pp. 674〜681では、最大６４のプロセッサを備えたプロセッサ・ネットワークでのタスクのレイアウトを最適化するために、単純なヒューリスティック（heuristic）に続く反復改善プロセスが開発されている。この研究は、リンク・コンテンションならびにレイアウト時の総トラフィック量を含むという点で、特異である。少数の異機種プロセッサに対して良い結果をもたらすより複雑なアルゴリズムは、その全文が参照により本明細書に組み込まれた、”An efficient algorithm for a task allocation problem”, A.Billionnet, M. C. Costa and A. Sutter, J. ACM, Vol. 39, No.3, 1992, pp 502〜518に提示されている。しかしながら、通信コストが通信エンドポイントとは無関係であるため、交換ネットワークによってリンクされたプロセッサにとっては有用であるが、より複雑なネットワーク・トポロジを使用する並列コンピュータにはあまり適切ではないことが想定される。
【０００６】
負荷バランシング問題、および階層ネットワークで局所性を最適化するためのタスクのクラスタ化（たとえば、その全文が参照により本明細書に組み込まれた、”Implementing the MPI Process Topology Mechanism”, Jesper LarssonTraaff, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, 2002,pp.1〜14にある、交換ネットワークによってリンクされたＳＭＰノードのクラスタ）では、グラフ区分化技法が使用されてきた。その全文が参照により本明細書に組み込まれた、”Task Allocation onto a Hypercube by Recursive Mincut Bipartitioning”,F. Ercal, J. Ramanujam and P. Sadayappan, Journal of Parallel and DistributedComputing Vo. 10. No.1 1990 pp. 35〜44 （以下、「F. Ercal等」と呼ぶ）によって、グラフ２区分化（bipartitioning）も８ノード・ハイパーキューブでのタスク・クラスタ化およびマッピングに使用されてきた。
【０００７】
前セクションに示されたF.Ercal等、および、その全文が参照により本明細書に組み込まれた、”A New Mapping Heuristic Based on Mean Field Annealing”, TevfikBultan and Cevdet Aykanat, Journal of Parallel and Distributed Computing, Vol.16, No.4, 1992, pp 292〜305 （以下、「Tevfix Bultan等」と呼ぶ）のいくつかのグループによって、擬似焼きなまし（SimulatedAnnealing）および関連する技法が、マッピング問題に適用されてきた。擬似焼きなましは適切なマッピングを作成するために有用であるが、計算的には高価である。平均場（Mean Field）焼きなましは、TevfikBultan等に言及された擬似焼きなましに類似したアルゴリズムである。これは、ハイパーキューブおよびメッシュ・トポロジにおける最高４００のタスクおよび３２のプロセッサを伴う問題に適用され、Tevfik Bultan等に言及された擬似焼きなましと比較される。
【０００８】
他の研究では、それ自体をある種の通信パターンを表示する問題に限定している。たとえば、その全文が参照により本明細書に組み込まれた、”Rectilinear Partitioning of Irregular Data Parallel Computation”,David Nicol, Journal of Parallel and Distributed Computing Vol. 23 No.2,November 1994, pp 119〜134では、直線トポロジによるマッピング問題に関するアルゴリズムを展開している。これは、その全文が参照により本明細書に組み込まれた、”On Bottleneck Partitioning of k-ary n-cubes”, David Nicol andWeizhen Mao, Parallel Processing Letters Vol.6, No.6, June 1996, pp 389〜399における、ｋ−ａｒｙ  ｎ−ｃｕｂｅ作業および通信パターンを伴う問題向けに拡張された。
【０００９】
前述のソリューションは有用であるが、Ｎ個のプロセッサへのＭ＞＞Ｎ個のタスクのマッピングよりも制約の多い問題である、Ｎ個のプロセッサへのＮ個のタスクのマッピングを最適化することを対象にしたソリューションはない。
【００１０】
さらに、ＢＧ／Ｌなどのコンピュータ・システムは、以前のリサーチのターゲット・アーキテクチャよりもかなり大規模であり、何千ものノードへのマッピングが不可欠な規模である。ＢＧ／Ｌの３Ｄトーラスは、マッピング問題をさらに複雑にする。
【００１１】
さらに、計算負荷のバランスをとり、区画間通信を最小にする、タスクの区画を達成することに、多くの注目が集められてきた。こうした区画を、異なるプロセッサ・ペア間での通信コストが大きく変化する、トーラスまたはメッシュなどのネットワークによってリンクされたプロセッサ上に配置することには、ほとんど注目が集められてこなかった。このことは、トーラスにおけるマッピングの良し悪しによるコストの差がプロセッサの数に応じて増加するため、ＢＧ／Ｌなどのコンピュータにとっては特に重要である。
【特許文献１】「Novel Massively Parallel Supercomputer」という名称の米国特許出願第１０／４６８９９３号（公開番号ＵＳ  ２００４／０１０３２１８）
【特許文献２】「Optimized Scalable Network Switch」という名称の米国特許出願
【特許文献３】「Ethernet Addressing Via Physical Location for Massively ParallelSystems」という名称の米国特許出願第１０／４６９００３号
【特許文献４】「Arithmetic Functions in Torus and Tree Networks」という名称の米国特許出願第１０／４６８９９１号
【特許文献５】「A Global Tree Network for Computing Structures」という名称の米国特許出願第１０／４６９０００号
【非特許文献１】“The Blue Gene/L Supercomputer”, by G.Bhanot, D.Chen, A.Gara andP.Vranas, Nucl. Phys. B (Proc. Suppl.) 119 (2003) 114
【非特許文献２】”Task Assignment on Distributed-Memory Systems with AdaptiveWormhole Routing”, Vibha A. Dixit-Radiya and Dhabaleswar K. Panda, Symposium onParallel and Distributed Processing (SPDP ’93), pp. 674〜681
【非特許文献３】”An efficient algorithm for a task allocation problem”, A.Billionnet, M. C. Costa and A. Sutter, J. ACM, Vol. 39, No.3, 1992, pp 502〜518
【非特許文献４】”Implementing the MPI Process Topology Mechanism”, Jesper LarssonTraaff, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, 2002,pp.1〜14
【非特許文献５】”Task Allocation onto a Hypercube by Recursive Mincut Bipartitioning”,F. Ercal, J. Ramanujam and P. Sadayappan, Journal of Parallel and DistributedComputing Vo. 10. No.1 1990 pp. 35〜44
【非特許文献６】”A New Mapping Heuristic Based on Mean Field Annealing”, TevfikBultan and Cevdet Aykanat, Journal of Parallel and Distributed Computing, Vol.16, No.4, 1992, pp 292〜305
【非特許文献７】”Rectilinear Partitioning of Irregular Data Parallel Computation”,David Nicol, Journal of Parallel and Distributed Computing Vol. 23 No.2,November 1994, pp 119〜134
【非特許文献８】”On Bottleneck Partitioning of k-ary n-cubes”, David Nicol andWeizhen Mao, Parallel Processing Letters Vol.6, No.6, June 1996, pp 389〜399
【非特許文献９】‘Markov Chain Monte Carlo in Practice”, W. R. Gilks, S. Richardson,D.J. Spiegelhalter(eds), Boca Raton, FL: Chapman and Hall (ISBN:0412055511）
【非特許文献１０】‘Introduction to the Monte Carlo Method’, I. Manno, Budapest,Hungary, 1999 (ISBN:9630576155)
【非特許文献１１】”Simulated Annealing: Theory and Applications (Mathematics and ItsApplications, 37)”, RJ.M. Van Laarhoven, E.H.L Aarts, P.J.M. Van Laarhoven, DReidel Pub Co, September 1987 (ISBN: 9027725136)
【非特許文献１２】’Markov Chains’ by Pierre Bremaud, Springer Verlag, 1999 (ISBN:0387985093)
【非特許文献１３】“Markov Chain Monte Carlo in Practice”, W. R. Gilks, S. Richardson,D.J. Spiegelhalter (eds), Boca Raton FL: Chapman and Hall, 1996 (ISBN:0412055511)
【非特許文献１４】‘Introduction to the Monte Carlo Method’, I. Manno, Budapest,Hungary, 1999 (ISBN: 9630576155)
【非特許文献１５】D.J. Kerbyson, H.J. Alme, A. Hoisie, F. Petrini, H.J. Wasserman, M.Gittings, ”Predictive Performance and Scalability Modeling of a Large-ScaleApplication”, Proceedings of the 2001 ACM/IEEE Conference on Supercomputing
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、スーパーコンピュータ・システムでの実行時間を最小にするために、任意の並列アプリケーションに関してＮ個のタスクをＮ個のプロセッサに最適にマッピングすることが求められている。
【００１３】
さらに、ＢＧ／Ｌなどのスーパーコンピュータ上での最適なマップ、および、スーパーコンピュータ・システムでの実行時間を最小にするために、任意の並列アプリケーションに関して３Ｄトーラスの相互接続を使用するスーパーコンピュータが求められている。
【００１４】
さらに、スーパーコンピュータ・システムでのタスク間の通信時間を最小にするために、任意の並列アプリケーションに関してバランスのとれたレイアウトを見つけることが求められている。
【課題を解決するための手段】
【００１５】
手短に言えば、本発明は、通信コストがタスクの配置に依存するスーパーコンピュータ・システムでの合計通信時間を最小にするために、任意の並列アプリケーションを所与の相互接続ネットワークへ最適にマッピングするための、コンピュータ実施方法、コンピュータ読み取り可能媒体、および対応するシステムを開示する。
【００１６】
超並列スーパーコンピュータでの問題レイアウトを最適化するための、汎用コンピュータが実施する方法および装置について説明する。この方法では、エントリＣ（ｉ，ｊ）がドメインｉからドメインｊに送られるデータの量であるアレイの形の、任意の問題の通信マトリクスを入力として採用する。Ｃ（ｉ，ｊ）が与えられた場合、第１に、頂点がドメインのグラフが作成され、通信し合うドメインのペア間にリンクが存在する。リンクの重みは、接続されたドメイン間で通信し合うデータの量である。ここでこのグラフは、各部片を接続するリンク上での総通信ができる限り少なくなるように、Ｋ個の部片に区分される。現時点では、この区画化にはＭＥＴＩＳ（http://www-users.cs.unm.edu/karypis/metis/）が使用されるが、グラフ内のクリーク（clique）およびバイクリーク（biclique）を決定するためのアルゴリズムを含む他の技法も使用可能である。次に、通信し合うドメインが、同じＢＧ／Ｌノードにマッピングされる（最終マッピングの計算負荷バランスがとれるように、１つのノードにマッピングされるドメイン数を一定に維持しながら）か、または使用可能なトーラス上の最近隣ノードにマッピングされるように、１区画内でＢＧ／Ｌノードにドメインが割り当てられる。次に、自由エネルギー（コスト関数）Ｆ＝ΣｉｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）を伴うモンテカルロ・シミュレーションを使用して、初期マップからマップのマルコフ連鎖が生成されるが、この式でＨ（ｉ，ｊ）は、推定通信パス・コスト／単位データ、たとえば、ドメインｉとドメインｊの間のトーラス上での最小ホップ数である。マルコフ連鎖は、ＢＧ／Ｌノード間のドメインをスワッピングすること、あるいは（計算負荷バランスを維持しながら）ドメインを非占有または部分占有ノードへ移動すること、および、メトロポリス・アルゴリズムを使用してテストすることによって、生成される（‘Markov Chain Monte Carlo in Practice”, W. R. Gilks, S. Richardson,D.J. Spiegelhalter(eds), Boca Raton, FL: Chapman and Hall (ISBN:0412055511）; ‘Introduction to the Monte Carlo Method’,I. Manno, Budapest, Hungary, 1999 (ISBN:9630576155))。メトロポリス・プロシージャにおける温度（Ｔ=１／β）は、高値から低値へと循環し、自由エネルギーは、すべての通信し合うドメインが同じノード上にまたは近隣ノード近くにある、仮想上（ただし通常は不可能な）完全なマッピングにおいて取得されることになる、理想自由エネルギーＦ（ｍｉｎ）で割ることによって正規化される。高温から低音へのメトロポリス・スイープ時に、各温度でのシステムの平均自由エネルギーが測定され、この量が停滞期（plateau）（ほぼ固定された値）に達するとプロシージャは停止する。この状態が発生した場合、ドメインの新しい部分は、上記と同じヒューリスティックを使用してＢＧ／Ｌにマッピングされ、温度は高値から低値へと再度循環する。これは、すべてのドメインがＢＧ／Ｌにマッピングされ、合計自由エネルギーがほぼ平衡値になるまで繰り返される。その後、各ドメインに関するＢＧ／Ｌノードのロケーションのリスト（トーラス上の座標（ｘ，ｙ，ｚ））が出力ファイルに書き込まれ、最適マップを構成する。１から３２の範囲内にあるＫ値は、実行時間がより高速になる大きなＫ値、およびより良好なマップを生成する小さなＫ値で、テストされた。
【００１７】
上記ではＨ（ｉ，ｊ）に関するコスト関数の一例が示されたが、本発明がこの例に限定されるものでないことに留意されたい。例示的コスト関数の他の例には、Ｈ（ｉ，ｊ）＝ＬＰ＝（ｘ−ｈｏｐＰ＋ｙ−ｈｏｐＰ＋ｚ−ｈｏｐＰ）１／ｐが含まれ、この式でｘ−ｈｏｐ（ｙ−ｈｏｐ、ｚ−ｈｏｐ）は、ノードＩからノードｊの間のｘ（ｙ、ｚ、それぞれ）ディメンションにおけるホップ数である。ｐ＝１の場合、Ｌ１は前述のホップ数である。ｐ＝２の場合、Ｌ２はノードＩからＪの間のユークリッド距離である。Ｐが増加するにつれて、この例示的コスト関数は最多ホップ数をより重視するようになり、Ｐが無限大まで増加すると最高ホップ数に達する。前述のコスト関数の例は単純である。本発明の真の範囲および趣旨において有利に使用される、より複雑なコスト関数が示されることに留意されたい。より複雑なコスト関数を使用することで、必要不可欠な計算費用によるトレードオフが発生する。たとえば、Ｈ（ｉ，ｊ）＝Σｉｊ（ｉからｊの間のすべてのリンクを介する）と、各リンクの推定使用率に関する関数との組み合わせは、より複雑な例示的コスト関数であり、より多くの計算費用が必要となる。
【００１８】
前述のプロシージャよりも高速のマッピングを実行するための代替方法は、単にヒューリスティックを実施し、擬似焼きなましステップを省略することである。このヒューリスティックはほとんどの場合合理的に働き、最適に近いマップを生成する。
【００１９】
２つのアプリケーション（ＳＡＧＥおよびＵＭＴ２０００）では、擬似焼きなましおよびヒューリスティック・マップがデフォルト・マップ（順位）に照らしてテストされた。この結果は、表２および３に添付された文書に記載されている。デフォルト（順位）マップと比べると、２５６および２０４８ノードのＳＡＧＥの場合は因数１．５および２．５によって、さらに２５６および１０２４ノードのＵＭＴ２０００の場合は因数１．６によって、合計自由エネルギーを減じるために、本開示のプロシージャを使用して最適化されたマップが見つけられた。
【００２０】
要約すると、コンピュータ実施方法は、ノードを接続する任意の通信ネットワークについて、並列コンピュータのノード全体にわたってソフトウェア・アプリケーションのＭＰＩ（メッセージ・パッシング・インターフェース）タスクを最適化する。この方法は、アプリケーション内の各ＭＰＩタスクによってアプリケーション内の他のあらゆるＭＰＩタスクへ送られるデータの量を使用したリストの形で、ソフトウェア・アプリケーションの通信マップを入力として採用する。次に、コスト関数を最小にするためにターゲット・コンピュータのノードへのＭＰＩタスクのマッピングを生成するように、適切なノード間通信コスト関数を数学的に最小にすることによって、ターゲット・コンピュータ上のノードの所与のネットワークに対するこの通信マップの最適マップを計算する。マッピングの目的は、元のソフトウェア・アプリケーション内のノード間でデータを通信するための合計時間を減らすことである。
【００２１】
添付の図面は、別々の図全体を通じて同じ参照番号が同一または機能的に同様の要素を表し、以下の詳細な説明と共に本明細書に組み込まれ、またその一部を形成するものであり、さらに様々な実施形態を図示する働き、ならびに本発明に従った様々な原理および利点のすべてを説明する働きをする。
【発明を実施するための最良の形態】
【００２２】
本明細書には、新規であるとみなされる本発明の特徴を定義した特許請求の範囲が添付されているが、本発明は、同じ参照番号が繰り返される図面と共に以下の説明を考察することによって、より良く理解されるであろう。本発明の方法は、例示のために、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータの特定のアーキテクチャ上で実施されるものとして説明される。しかしながら、説明される方法はさらにかなり一般的であり、コスト関数が適切に定義されると、ネットワークによって接続された計算／通信ノードの任意のセットに適用されることに留意されたい。
【００２３】
Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータの汎用アーキテクチャ
Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータは、３次元ネットワークによって接続されたいくつかのノード（２の累乗でなければならない）で構成される。ノードの数が５１２ノードを越える場合、３次元ネットワークはトーラスである。ノード数が５１２未満の場合、ネットワークはメッシュである。図９は、本発明が有利に使用されることが示された、５１２のコンピューティング・ノードを有する典型的な基本トーラス構成からの、８つのコンピューティング・ノードを相互接続する３次元トーラス形状のごく一部１０を示す。図９および１０に示されるように、トーラス・ネットワークの場合、各ノード１２は双方向トーラス・リンク１３によってその６つの近隣に接続される。しかしながら、本願の所有者が所有する同時係属の「Novel Massively Parallel Supercomputer」という名称の米国特許出願第１０／４６８９９３号（公開番号ＵＳ  ２００４／０１０３２１８）に記載されたものを含み、異なるトーラス構成（たとえば、４次元またはそれ以上の次元のトーラス）でより多くの処理ノードを備える他のアーキテクチャが企図されることを理解されよう。
【００２４】
加えてトーラスは、ネットワークに投入された単一のパケットが複数の宛先で堆積可能な、自動マルチキャスト「クラス・ルーティング」技法を提供する。好ましくは、ネットワークは、デッドロックを回避するために２つの動的仮想回路ならびに２つのエスケープ「バブル」回路を採用することによって、デッドロックが発生しない。本明細書に組み込まれた、本願の所有者が所有する同時係属の「Optimized Scalable Network Switch」という名称の米国特許出願に記載のように、これまではトーラス・ネットワークが使用されてきたが、大規模スケーラブル・システムにおいて少ない待ち時間および高いスループットを達成するためには、新規なアービトレーション・ポリシーが使用される。ポイント・ツー・ポイントのトークン・ベースのフロー制御は、トラフィックをホット・スポットから遠ざけて配信しながら、ネットワーク・バッファリングを最も効果的に利用する。さらにトーラスでは、ヘッダ上での別々のＣＲＣエラー検出、ならびに破損したネットワーク・パケットの自動再送に関するフル・パケットＣＲＣエラー検出を採用することによって、保証された信頼できるパケットの送達が実行可能である。
【００２５】
グローバル・ツリー・ネットワークに関する１つの主要な機能は、グローバル・ブロードキャスト（ダウンツリー）およびグローバル削減（reduce）（アップツリー）操作をサポートすることである。入力／出力、プログラム・ロード、システム管理、並列ジョブ監視、およびデバッグに使用される、プログラム可能なポイント・ツー・ポイントまたはサブツリー・メッセージングをサポートするために、追加の機能が提供される。この機能により、並列計算に干渉しないように、「サービス」または入力／出力ノードをトーラスから分離することができる。すなわち、サービス・ノードが非同期外部対話をオフロードする間に、トーラス内のすべてのノードは最高計算レートで動作することができる。これにより、計算を実行しているすべてのノードが最高および一貫したレートで動作するため、並列計算のスケーラビリティおよび再現性が保証される。好ましくは、グローバル・ツリーは、メッセージング操作削減を実施するそれらの数学的機能の実行をサポートする。好ましくは、グローバル・ツリー・ネットワークは、さらに複数の独立した仮想チャネルをサポートすることによって、複数の独立したグローバル操作を同時に進行させることができる。この設計は構成可能であり、ノードを処理するための計算ノードの割合は並列計算の要件に応じてフレキシブルである。代替パッケージング・ストラテジでは、すべてのサービスまたは入力／出力ノードからなるマシンを含む、極端にデータが集中する計算にとって理想的な、任意の割合が可能である。
【００２６】
図９に関して説明したようなＢｌｕｅ  Ｇｅｎｅ／Ｌの３次元トーラス・ネットワークでは、物理マシン・アーキテクチャは、例示的実施形態ではエッジで「折り返される」単純な３次元最近隣相互接続である、ｎ次元トーラス１０に関する。特定用途向け集積回路（ＡＳＩＣ）の異なるラック間に存在するような飛行時間差を除き、すべての近隣は等しい距離にあるため、コードの書き込みおよび最適化が容易である。例示的実施形態では、ノード間の最近隣リンクは、各方向１．４  Ｇｂ／秒のメッセージ大域幅を同時に担持する。各ノードは、１．０５  ＧＢ／秒のノードへの、およびこのノードからの集合大域幅を備えた、６つの独立した双方向最近隣リンクをサポートする。
【００２７】
グローバル結合ツリー
図１０は、本発明に従った、ツリー構造の計算ノード１２を相互接続し、グローバル信号および外部ネットワーク接続を含む、グローバル結合ツリー・ネットワーク５９と呼ばれる第２のネットワークを示す。ツリーには、グローバル結合ツリーを介して所定数の計算ノード１２に接続された、関連するＩ／Ｏ処理ノード１２’が含まれる。図５に示されたような好ましい実施形態では、１つのＩ／Ｏノード１２’が、６４の計算ノード１２にサービスおよびＩ／Ｏ操作を提供することに専念する。このＩ／Ｏノード対コンピュータ・ノードの割合は、スーパーコンピュータの物理パッケージングを最適化するように構成可能であることを理解されたい。すなわち、パッケージング設計により、並列計算の要件に応じて計算ノード対サービス・ノードの割合が変化するような代替構成が可能である。好ましい実施形態では、パッケージング技術が２５６：１から８：１までをサポートする。代替パッケージング・ストラテジでは、すべてのサービスまたは入力／出力ノードからなるマシンを含む、極端にデータが集中する計算にとって理想的な、任意の割合が可能である。
【００２８】
図１０に示されるように、１００  Ｍｂ／秒イーサネット（登録商標）・ネットワーク９８は、計算ノード１２および関連するＩ／Ｏノード１２’の両方を、たとえばネットワーク・スイッチ１８を介して、大規模ネットワークに接続する。本明細書に組み込まれた、本願の所有者が所有する同時係属の、「Ethernet Addressing Via Physical Location for Massively ParallelSystems」という名称の米国特許出願第１０／４６９００３号でより詳細に説明されるように、各ノードＡＳＩＣは、ホスト・システム５０があらゆるノードと通信できるようにする固有のＭＡＣアドレスを有する。このＭＡＣアドレスに関連付けられたＴＣＰ／ＩＰアドレスは、ノードの符号化された幾何学的ロケーションをスーパーコンピューティング・マシンに格納した。したがって、たとえば障害ノードからの診断報告を、そのラックの行および列へのそのＴＣＰ／ＩＰアドレス、およびスーパーコンピュータのラック内のそのロケーションを介して、直接追跡することができる。高速ネットワークに結合された状態で、マシン内のすべてのノードの状態を同時に凍結するための機能が提供される。スーパーコンピュータの一実施形態は、８１，９２０個の計算ノードならびに１，２８０個の入力／出力ノードを備えるため、前例のないレベルの診断、デバッグ、および検査が提供される。
【００２９】
Ｉ／Ｏノード１２’として機能している場合、ＡＳＩＣ  ２０は、ノードに対するローカル・ディスクとして働く大規模ＲＡＩＤディスク・システム５５へのアクセスに使用可能な、ギガビット・イーサネット（登録商標）９９またはＩｎｆｉｎｉｂａｎｄなどの同様のインターフェースを含む。ＲＡＩＤシステム５５は、冗長性のために二重化され、ギガビット・イーサネット（登録商標）９９またはＩｎｆｉｎｉｂａｎｄの１０２４チャネルを介し、スイッチ（図示せず）を介してシステムに接続される。スイッチはホストともインターフェースしているため、ホストは、単純なイーサネット（登録商標）Ｉ／Ｐトランザクションを介して、システム・ノードまたはＲＡＩＤディスク・システムのいずれかにアクセスすることができる。マシン内部では、追加の外部メモリを備えたＡＳＩＣである専用Ｉ／Ｏプロセッサが、ギガビット・イーサネット（登録商標）／Ｉｎｆｉｎｉｂａｎｄ接続を終端させる。任意のＩ／Ｏノードは、最高ギガビット速度でＲＡＩＤディスクの読み取りまたは書き込みが実行できる。説明された例示的実施形態では、システムの６４ｋノードが、毎秒１テラビットを超えるディスクまたはホストへのピーク集合Ｉ／Ｏ大域幅を有するように構成される。
【００３０】
好ましくは、この２進の様な結合ツリー５９をスーパーコンピュータ・マシン全体にわたって拡張することが可能であるため、低い冗長度で任意のノード１２からすべての他のノードまたはノード１２のサブセットへデータを送る（ブロードキャスト）ことができる。ツリーは３つより多くのポート（３ポートは２進を意味する（２つがイン、１つがアウト））を有することが可能であることを理解されよう。トーラスの場合とまったく同様に、ツリーがより高次元、すなわち４次元、５次元、または６次元になると、より多くのチップ間接続およびかなり高い配線コストをかけて、より短くより低い冗長度パスが可能になる。次元が下がるほど冗長度が長くなり、チップ間通信が少なくなる。メッセージ・パッシングは、グローバル結合ツリー５９でサポートされており、各ＡＳＩＣ内のいずれかのプロセッサによって制御されるため、全対全（all-to-all）通信などの集中操作を計算ノードとは独立に進行させることができる。このツリーのあらゆる分岐は、送信および受信の両方向において、１．４ＧＢ／秒またはプロセッサ・サイクルあたり２バイトの、好ましいターゲット大域幅を有する。
【００３１】
ツリー５９に組み込まれたハードウェア機能は、整数加算、減算、最大、最小、ビットごとのＡＮＤ、ＯＲ、ＸＯＲ、およびブロードキャストである。これらの機能は最低冗長度が可能な方法で実施される。たとえば加算機能の結果として、グローバル・ネットワーク上で最小バイトのワードが最初に送信されることになる。この少ないバイトは、他のソースから（ハードウェア内の）他のバイトに即時に追加され、その結果、ツリーの次のレベルにシフトアウトされることになる。この方法では、６４ビット・ワードは、高位バイトがシフトアウトされる前にすでにツリー内で数レイヤ上に進行している。その結果、マシン全体にわたって、非常にわずかな待ち時間が加えられることになる。このわずかな待ち時間の追加は、グローバル内積を必要とする反復の疎な一次方程式解法にとって重大である。
【００３２】
データのグローバル・ブロードキャストには、リング内を回るように送信するのではなく、同じツリーを利用することができる。１対全（one-to-all）からの通信の場合、ソフトウェア側から見れば、これは最近隣３Ｄリンク・ネットワーク全体にわたるかなりの改善である。３Ｄリンク・ネットワークを介した通信と同時である必要がある１対全転送が存在する場合、ブロードキャスト機能も非常に有用である。ブロードキャストは、３Ｄリンク・ネットワークを介して処理することもできる。
【００３３】
最終的に、２進ツリーを２回利用することによって、マシン全体にわたるグローバル浮動小数点合計を数マイクロ秒で実行することができる。最初に、すべての指数の最高値が取得され、次に、シフトされた整数全体がグローバル操作で加算される。トーラスを介した演算機能の実施に関する詳細は、本明細書に組み込まれた、本願の所有者が所有する同時係属の、「Arithmetic Functions in Torus and Tree Networks」という名称の米国特許出願第１０／４６８９９１号に記載されている。グローバル結合ツリー・ネットワークの操作に関する詳細、とりわけ、入力／出力、プログラム・ロード、システム管理、並列ジョブ監視、およびデバッグに使用される、プログラム可能ポイント・ツー・ポイントまたはサブツリー・メッセージングをサポートする機能に関する詳細は、本明細書に組み込まれた、本願の所有者が所有する同時係属の、「A Global Tree Network for Computing Structures」という名称の米国特許出願第１０／４６９０００号に記載されている。
【００３４】
スーパーコンピュータの例示的ハードウェア実施例
スーパーコンピュータ・ノードは、通常５１２ＭＢのメモリと、それぞれが２．８ギガフロップスのピーク性能が可能な２つのＣＰＵとを有する。したがって、ノードのピーク性能は、ＣＰＵがどちらも計算に使用されるか、または一方は計算に他方は通信に使用されるかに応じて、５．６または２．８ギガフロップス／秒である。各計算ノードには６つのトーラス・リンクが組み込まれ、それらは、最近隣間に１つのホップがあるように、それぞれ＋ｘ、！ｘ、＋ｙ、！ｙ、＋ｚ、！ｚ方向の６つの最近隣に接続される。トーラス上のリンクは、１．４  Ｇｂ／秒のピーク大域幅を有する。各ノードは、各方向に１．４  Ｇｂ／秒の速度でその近隣と通信することができる。
【００３５】
本発明の一実施形態では、アプリケーションはいくつかのドメインからなる。ドメインは、計算を実行した後に他のドメインからの情報にアクセスし、さらに続いて他の計算を実行する、という具合である。ドメイン間で交換されるデータの量が、通信トラフィックを定義する。この実施形態では、１つまたは複数のドメインが単一のスーパーコンピュータ・ノードにマッピングされる。本発明は、通信時間が最低となるような、スーパーコンピュータ・ノードへのドメインの最適なマッピングを提供する。「ドメイン」の定義は、通信データの収集方法に応じて異なることに留意されたい。本発明で使用される例では、データは、スーパーコンピュータでのＭＰＩベースのアプリケーション・コードの実行から取得されたため、ドメインはＭＰＩタスクであった。しかしながら、ドメインは単に、単一の変数または変数の集まりとすることもできる。コードが動的な負荷バランシングに使用される場合、データはランタイム時に収集することもできる。この場合、ドメインはプロセスまたはシステム・スレッドの可能性がある。
【００３６】
本発明の一実施形態では、計算時間はプロセッサ間で均一であること、および本発明者等のコスト関数が通信時間を最低にすることのみを必要とすることが想定される。他の実施形態では、本発明の真の範囲および趣旨の範囲内において、計算時間は他の実施形態におけるプロセッサ間で異なる可能性があることに留意されたい。本発明において入力として必要な情報は、アプリケーションの実行中にランタイム・システム（ＲＴＳ）から取得可能であるか、または以前のテスト実行からのデータとして提供可能であることに留意されたい。
【００３７】
マッピングの概要
Ｌ×Ｍ×Ｎノードを備えたスーパーコンピュータにマッピングされることになる、Ｄドメインに伴うある問題が与えられたと想定してみる。ドメインｉからドメインｊへ送られるデータの量をＣ（ｉ，ｊ）、ドメインｉからドメインｊの間の通信に関する単位データあたりのコストをＨ（ｉ，ｊ）とする。Ｃ（ｉ，ｊ）は基礎となるアプリケーションによって定められ、最適化プロセス全体を通じて変更されず、一定のままである。これに対して、Ｈ（ｉ，ｊ）は、最適化の任意の所与のステップで、ノードへのドメインの特定マッピングに直接依存し、リンク利用率に応じて常に変化する。わかりやすくするために、この実施形態では、Ｈ（ｉ，ｊ）が、ドメインｉおよびｊがマッピングされるノード間の距離にのみ依存すること、ならびに伝送されるデータの実際量とは無関係であることが想定される。
【００３８】
スーパーコンピュータ上では、ノードは３Ｄ格子内に配置構成され、トーラス相互接続を介してそれらの６つの最近隣にのみ接続される。格子内の各ノードには、格子内のその（整数）デカルト座標（ｘ，ｙ，ｚ）によってラベル付けされる。この相互接続された格子上では、Ｈ（ｉ，ｊ）に関する最も単純な選択は、ノードｉをノードｊに接続しているトーラス上の最短パス内のホップ数と等しくなるように設定することである。
【００３９】
この定義を使用した場合、最小にするための本発明のコスト関数は以下のように与えられる。
【数１】
2008516346.tif 000003
【００４０】
以下、本発明では、擬似焼きなましおよびＦと呼ぶ自由エネルギーの用語が採用される。
【００４１】
数値作業の場合、固定領域に制約されるように自由エネルギーを正規化することが役立つ。３Ｄスーパーコンピュータ・トーラスでは、各ノードが６つの最近隣（距離１ホップ）、１８の次の最近隣（距離２ホップ）などを有する。自由エネルギーＦは、項ΣｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）のすべてのドメインｉにわたる合計である。最初にドメインｉと同じノードへ、次にｉの最近隣へ、次にｉの次の最近隣へという具合に、Ｃ（ｉ，ｊ）の値が減少する順に、ドメインｊが「分配（deal out）」された場合、これら個々の項のそれぞれについて達成可能な最小値が取得される。その後、合計自由エネルギーについて達成可能な最小値が、これらの個々のドメイン最小値それぞれのドメインにわたる合計によって与えられる。この最小自由エネルギーは、Ｆｍｉｎと示される。ほとんどの場合（および特に非自明な（non trivial）パターンの場合）、この最小値の達成は不可能である。にもかかわらず、これは正規化にとって、および理想的な「理論上の」下限（lower bound）として、有用な概念である。
【００４２】
本発明における一般的な最適化方法は、”Simulated Annealing: Theory and Applications (Mathematics and ItsApplications, 37)”, RJ.M. Van Laarhoven, E.H.L Aarts, P.J.M. Van Laarhoven, DReidel Pub Co, September 1987 (ISBN: 9027725136)にあるような、擬似焼きなまし（ＳＡ）である。ＳＡは、所与の構成を改善するために、ランダムに変更することによって反復的に試行する反復法である。このプロセスを促進する（seed）ためには、初期構成をセットアップしなければならない。一実施形態では、適切な開始構成として以下の方法が採用されるが、開始構成として多くの他の好適な手法が可能であることを理解されたい。
【００４３】
関数ｃ（ｉ）を以下のように定義する。
【数２】
2008516346.tif 000004
【００４４】
ｃ（ｉ）は、ドメインｉによって送られる合計データである。単純な再配列により、ドメインは、ｃ（１）≧ｃ（２）≧ｃ（３）となるようにラベル付けに従って配置構成される。スーパーコンピュータのプロセッサは、それらのデカルト座標（ｘ，ｙ，ｚ）によって決定される。平均して、各スーパーコンピュータ・ノードにマッピングされるドメインの数をｐ＝Ｄ／（Ｌ  Ｍ  Ｎ））とする。ノード（ｘ，ｙ，ｚ）にマッピングされるドメインの数をｎ（ｘ，ｙ，ｚ）とする。計算負荷バランシングの場合、この実施形態では、ｎはｐに近くなるように制約される。最も厳しい制約は以下のように要求することである。
【００４５】
Ｉｎｔ（ｐ）≦ｎ（ｘ，ｙ，ｚ）≦Ｉｎｔ（ｐ＋１）                      （４）
【００４６】
上式で、Ｉｎｔ（ｐ）はｐの整数部である。
【００４７】
初期のヒューリスティック・マップは、以下のアルゴリズムによって定義される。
【００４８】
１．ドメインｉ＝１を任意のロケーション（ｘ，ｙ，ｚ）にマッピングする。
【００４９】
２．数式４の制約を満たしながら、ドメインｉ＝１が通信するすべてのドメインを、ロケーション（ｘ，ｙ，ｚ）またはスーパーコンピュータ・トーラス上のその近隣ロケーションにマッピングする。
【００５０】
３．次に、数式４の制約を満たしながら、ドメインｉ＝２（まだマッピングされていない場合）を任意のロケーション（ｘ，ｙ，ｚ）にマッピングし、通信するドメインを同じノードまたはトーラス上の近隣ノードにマッピングする。
【００５１】
４．この最終ステップをｉ＝３、４、．．．、Ｄに対して反復する。
【００５２】
このヒューリスティック・マップから始まり、最小の自由エネルギーＦを見つけるために擬似焼きなましが実行される。このため、マッピングのマルコフ連鎖を定義する（その全文が参照により本明細書に組み込まれた、’Markov Chains’ by Pierre Bremaud, Springer Verlag, 1999 (ISBN:0387985093)）。｛Ｍｊ，ｉ＝０、１、２、．．．、ｎ｝ここでＭ０はヒューリスティック・マップであり、Ｍｉは以下のアルゴリズム（その全文が参照により本明細書に組み込まれた、“Markov Chain Monte Carlo in Practice”, W. R. Gilks, S. Richardson,D.J. Spiegelhalter (eds), Boca Raton FL: Chapman and Hall, 1996 (ISBN:0412055511); ‘Introduction to the Monte Carlo Method’, I. Manno, Budapest,Hungary, 1999 (ISBN: 9630576155)に記載されるように、メトロポリス・アルゴリズムと呼ばれる）を適用することによってＭｉ−１から導出される。
【００５３】
１．逆温度（inverse temperature）にある新しいパラメータβ（β＝１／Ｔ）を導入し、初期にβを何らかの小さな値に設定する。
【００５４】
２．数式４に反することなく、２つのドメインをランダムに選択したトーラス上のロケーション間でスワッピングすること、またはあるドメインをトーラス上のランダムなロケーションから他のロケーションへと移動することによって、Ｍｉ−１から新しい候補マップＭＮｉを生成する。
【００５５】
３．ＭＮｉを受け入れる、すなわち、Ｍｉ＝ＭＮｉ  ｉｆｆ、Ｒ＜ｅｘｐ［−β｛Ｆ（ＭＮｉ）−Ｆ（Ｍｉ−１）｝／Ｆｍｉｎ］を設定し、この式でＲは（０，１）内で均一に分散された乱数である。
【００５６】
４．自由エネルギーが安定平衡へと減少するまで、同じβ値を使用して新しい候補マッピングの生成を続行する。
【００５７】
５．ここで、段階的にβを増加させ、それぞれの新しいβについて新しい自由エネルギー平衡に達するまで、マルコフ連鎖プロセスを続行する。
【００５８】
このプロシージャは、金属が不純物を除去するために最初に加熱され、その後ゆっくりと冷却される、冶金学の焼きなまし工程に類似しているため、擬似焼きなましと呼ばれる。自由エネルギーに使用される正規化も、数式５の要素に入れられることに留意されたい。この正規化は計算的に役立つ。
【００５９】
本発明を使用してマッピングされるアプリケーションの例
これらの方法をテストするための単純な例として、規則的な３Ｄトーラス上に８３のドメインを有し、各ドメインが固定量のデータをその６つの最近隣に送るという、問題を考えてみる。この例では、この問題は８３のスーパーコンピュータ・トーラスにマッピングされる。問題は小さく、単純で、明らかな最適マップを備える。にもかかわらず、これは、本発明によって記載される方法の有用なテストとするのに十分なほど複雑かつ大規模である。
【００６０】
図１は、本発明に従って解決された例示的問題に関する通信マトリクスＣ（ｉ，ｊ）の構造を示すプロットである。水平軸は送信側ＩＤ、ｉを指定する。垂直軸は、受信側ＩＤ、ｊを指定する。このマトリクス内では、非ゼロ・エントリは十字形として示される。この方法の主な調整可能パラメータは、使用されるβの値、および任意の所与のβの値について実行される反復回数である。
【００６１】
この方法を成功させるためには、移動のための許容レートが低すぎないように保証することが重要である。低い許容レートは、マッピングがステップによって変化しないことを示す。許容レートの妥当な範囲は、１０％〜５０％である。許容レートは、乱数が正規化された自由エネルギー（Ｆ／Ｆｍｉｎ）における変化の指数掛けるβより少ないという条件によって決定される、数式５を想起されたい。構造により、Ｆ／Ｆｍｉｎ≧１であるが、良好なマッピングＦ／Ｆｍｉｎは値１に近いものと予想される。そこで、βの典型的な値は１≦Ｂ＜１０である。これらの範囲で、指数の引数は通常０（１０）未満であり、メトロポリス・ステップに対して妥当な許容レートが達成可能である。
【００６２】
βの所与の値について実行する反復回数を決定するためには、焼きなましの進行に従って自由エネルギー関数の挙動を監視すれば十分である。典型的には、これは一時的に急落し、その後停滞する。停滞は、βの所与の値に対する平衡の開始を示し、通常は、所与のβについて停滞が明らかに確立されると、新しいβへと切り替わる。
【００６３】
図２は、本発明に従った擬似焼きなましアルゴリズムの実行例に関する、正規化された自由エネルギーの展開を示すプロットである。正規化された自由エネルギーは反復の関数である。このプロットの垂直の仕切りは、βが増加するポイントを画定する。固定された各β帯域内で、自由エネルギーは初期には下降し、その後停滞する。帯域間を左から右へと移動するにつれて、βは増加し、自由エネルギーの平衡または停滞値は減少する。シミュレーションの初期には、収束はゆっくりであり、停滞はほとんど目立たない。図示された最後のβ変化では、収束は非常に急激に発生する。この種の収束プロファイルは、焼きなましではかなり一般的である。図３は、本発明に従った、同じ実行に関する各固定βセグメントの最後尾で達成される正規化された自由エネルギーの値を示すプロットである。自由エネルギーの収束された停滞値はベータの関数として達成する。この問題ではβがある値を超えて増加すると、自由エネルギーは理想的な最低値１に収束する。結果として生じるレイアウトは、３Ｄ最近隣問題に関するＢＧ／Ｌトーラスへのドメインの最適なマッピングである。どちらの図でも、正規化された自由エネルギーの値は着実に降下し、最終的に理想値１を達成することに留意されたい。この最終的に達成された構成に関するノードへのドメインのマッピングを調べると、最近隣の通信のみが必要な方法でドメインがトーラスにマッピングされるという理想形に対応することがわかる。
【００６４】
本発明に対する機能強化の実施形態
「本発明を使用してマッピングされるアプリケーションの例」と題する前述のセクションでは、少なくとも単純なケースでは、擬似焼きなましを使用して、スーパーコンピュータ計算ノードへの問題ドメインの良好なマッピングを探すことができることが実証された。しかしながら、前述のセクションで説明した単純な実施は、最高６５３３６個のコンピュータ・ノードを含む可能性のあるフルサイズのスーパーコンピュータ・システム上で使用するように十分にスケーリングされない。単純な実施に関する計算時間は、０（１０３）プロセッサでのレイアウトの最適化についてすでに何時間にも及び、フル・スーパーコンピュータ・マシンにとっては法外な数字である。
【００６５】
しかしながら、焼きなまし法は非常に堅固であり、ほぼ無限大の変形が認められる。この実施形態では、わずかに次善のマッピングを高速生成することが可能な、本発明で有利に実施されてきた分割統治（divide-and-conquer）法について説明する。この手法を使用して、非常に良好なマッピングを生成することができる。本発明者等の例で、最終マップは、全擬似焼きなましによって発見される最適マップに非常に近く、デフォルトのＭＰＩ順位マッピングよりもかなり良好である。
【００６６】
多くの並列アプリケーションの場合、通信マトリクスＣ（ｉ，ｊ）は疎である。ほとんどのケースで、問題ドメインは近くのドメインと通信し、遠くのドメインとの通信は比較的まれ、または少ない。これにより、問題ドメインのノードへのマッピングは１回に１ドメインで構築されることを示唆する。こうした手法の利点は明らかである。ｎノード・システムの場合、最適なレイアウトのために探索しなければならない可能なマッピングは０（ｎ！）である。サイズｎの１マップよりもサイズｎ／ｋのｋマップを最適化する方が、より効率的なのは明らかである。もちろん、一般に、分割統治法から得られる最小自由エネルギーは、最適化が実行される探索スペースが切り捨てられるため、最適ではない。
【００６７】
本発明で有利に使用されることがわかっている分割統治法は、以下のように進行する。第１にグラフＣ（Ｖ，Ｅ）が構築され、ここで各頂点ｖ∈Ｖは問題ドメインを表す。
【００６８】
２つの頂点ｉ，ｊはエッジで接合され、Ｃ（ｉ，ｊ）＞０の場合、ｅｉｊ∈Ｅである。各エッジには重みＣ（ｉ，ｊ）が割り当てられる。ＧのサブグラフＳ（Ｖｓ，Ｅｓ）は、ＶのサブセットＶｓおよびＥのサブセットＥｓからなり、ここで∀ｅｉｊ∈Ｅｓ，ｉ，ｊ∈Ｖｓである。
【００６９】
ここで通信グラフＧは、サブグラフ間の通信を最小にするようにサブグラフに分割される。本発明と有利に働くように示された１つのパッケージが、この区画化に関するＭＥＴＩＳと呼ばれる公的ドメイン・パッケージである（その全文が参照により本明細書に組み込まれたオンラインＵＲＬ  http://www-users.cs.umn.edu/karypis/metis/を参照）。ＭＥＴＩＳは、グラフの区画化における標準ツールである。これは、区画のエッジ・カットを最小にするバランスのとれた区画を生成するように試みる。エッジ・カットとは、異なる区画に属する頂点をリンクするすべてのエッジの重みの合計である。この区画化スキームにより、互いに最大限に独立した問題ドメインのグループが識別できるため、最小限の干渉で計算ノードに独立に割り当てられることができる。
【００７０】
ＭＥＴＩＳ区画化が取得されると、次に、マッピングは、「マッピングの概要」と題する前述のセクションで定義されたヒューリスティック方法を使用して、１度に１つのサブグラフをノード・セットにマッピングし、次に、ＳＡを使用してサブグラフ・マップを１つずつ最適化するように、順に進行する。任意の所与のステップで、マッピングされるサブグラフにのみ焼きなましが適用される。以前にマッピングされたサブグラフは、未変更のままである。計算ノードにマッピングされる第１のサブグラフは、ランダムに選択される。その後、マッピングされる次のサブグラフは、すでにマッピングされたサブグラフへの最大の接続性を有するサブグラフとして選択される。
【００７１】
このプロセスの重要な側面は、個々の区画のサイズの決定である。小さい区画はすぐに焼きなましされる。しかしながら、大きい区画は、最適または最適に近いマッピングを達成する必要がある。ＧのサブグラフＳ（Ｖｓ，Ｅｓ）では、割合
【数３】
2008516346.tif 000005
は、サブグラフＳが残りの通信グラフＧにどのように接続されるかを示す。ｌの制約が、マッピングの最適化のために焼きなましの生成を実施する際に、品質を管理するために
通常使用される方法となる。本発明のこの実施形態では、この手法は採用されない。その代わりに、様々な区画サイズに関する結果が示される。小さな区画（たとえば、１区画あたり８ノード、合計１２８区画）を使用する最適化に関する典型的な実行時間は、０（３０）分であった。大きな区画（たとえば、１区画あたり２５６ノード、合計４区画）を使用する最適化に関する典型的な実行時間は０（１０）時間であった。
【００７２】
本発明に従ったマッピングの結果例
本発明のこれらの方法のテストとして、４つの別々の通信問題が使用される。
【００７３】
１．Ｃｕｂｉｃ  １：これは、すでに前述した３Ｄ最近隣問題である。８×８×８トーラス上の各ノードについて１つのドメインがあり、タスクはそれらを８×８×８スーパーコンピュータ・トーラス上に配置することである。通信パターンは、各ドメインが同じサイズのパケットを、トーラス上のその６つの最近隣それぞれに送信することである。このケースでの的確な（最適な）ソリューションがわかっているため、現在の方法からのマッピングの結果を最適なマッピングと比較することができる。
【００７４】
２．Ｃｕｂｉｃ  ２：この問題はＣｕｂｉｃ  １と同様であるが、ここではドメインが、トーラスのデカルト方向に沿ってフルサイズのパケットをそれらの６つの最近隣（距離１ホップ）に送り、ハーフサイズのパケットをそれらの次の最近隣（距離２ホップ）に送る。パケットは直線でのみ送信され、グリッド上での回転は含まれない。ここでも、最適なマップが分析的にわかる。
【００７５】
３．ＳＡＧＥ：これは、その全文が参照により本明細書に組み込まれた、D.J. Kerbyson, H.J. Alme, A. Hoisie, F. Petrini, H.J. Wasserman, M.Gittings, ”Predictive Performance and Scalability Modeling of a Large-ScaleApplication”, Proceedings of the 2001 ACM/IEEE Conference on Supercomputingに記載された、Ｓｃｉｅｎｃｅ  Ａｐｐｌｉｃａｔｉｏｎｓ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  ＣｏｒｐｏｒａｔｉｏｎからのＡｄａｐｔｉｖｅ  Ｇｒｉｄ  Ｅｕｌｅｒｉａｎ流体力学アプリケーションである。この実施形態で使用される例では、適応メッシュの改善なしに熱伝導および流体力学を実行する、ｔｉｍｉｎｇ＿ｈ入力セットを使用する単純なケースのみについて考慮される。通信パターンは、このケースがそれだけで有用なように十分複雑である。（ＡＭＲを備えた）フルコードの要件は同様であり、問題グリッドが再定義されるたびにノードへのマッピングを見つける必要がある。フルコードでも分析の主要点は同様であり、本発明者等の方法はこの場合にも適用される。
【００７６】
ＳＡＧＥは、セルがブロックにグループ化され、２×２×２の構成で各ブロックが８つのセルを含む、規則的なデカルト・グリッドを使用する。ブロックは、（ｘ，ｙ，ｚ）の順に分散される。スケーリングの目的で、１タスクあたりの一定のセル数が使用される。最も単純な入力セットでは、グローバル・ドメインは立方体である。少ないタスク数の場合、分解ストラテジにより、グローバル・ドメインのスラブ解体に近い何らかの結果が生じる。ローカル・ドメインの精密な形状は、１タスクあたりのセル数およびタスク数に依存する。以下に、アルゴリズム１を示す。
【００７７】
入力：
Ｔ、スーパーコンピュータ・トーラス・ネットワークにおける計算ノードのセット
全未区分化グラフ  Ｇ（Ｖ，Ｅ）
Ｇのサブグラフ  Ｓ（Ｖｓ，Ｅｓ）
Ｐ⊂Ｖ、ここでｐ∈Ｐは、Ｔにおいてすでに計算ノードにマッピングされた頂点
マッピング  Ｍ：Ｐ←Ｔ
Ｌ、細分に関する制限
出力：
ＶｓからＴへのマッピングを含むように、Ｍを更新する。Ｖｓを含むようにＰを更新する。
（１）ＭＥＴＩＳを使用して、ＳをＳ１（Ｖ１，Ｅ１）およびＳ２（Ｖ２，Ｅ２）に分割する。
【数４】
2008516346.tif 000006
（３）ｌ１＜Ｌまたはｌ２＜Ｌの場合
（４）擬似焼きなましを使用して、各ｖ∈Ｖｓをノードｔ∈Ｔに割り当てる。
（５）Ｐ：Ｐ←Ｐ∪Ｖｓを更新する
（６）ＶｓからＴへのマッピングを含むように、Ｍを更新する。
（７）さもなければ
【数５】
2008516346.tif 000007
（１０）ｃ１＞ｃ２の場合、（１１）区画（Ｔ，Ｇ，Ｓ１，Ｐ，Ｍ，Ｌ）
（１２）区画（Ｔ，Ｇ，Ｓ２，Ｐ，Ｍ，Ｌ）
（１３）さもなければ
（１４）区画（Ｔ，Ｇ，Ｓ２，Ｐ，Ｍ，Ｌ）  （１５）区画（Ｔ，Ｇ，Ｓ１，Ｐ，Ｍ，Ｌ）
（１６）Ｍを戻す
【００７８】
上記アルゴリズム１：区画。このアルゴリズムは、サブグラフが擬似焼きなましを使用してトーラスにマッピングされるように十分小さくなるまで、グラフを再帰的に２分する。
【００７９】
４．ＵＭＴ２０００：これは、その全文が参照により本明細書に組み込まれた、オンラインＵＲＬ  http://www.llnl.gov/asci/purple/benchmarks/limited/umtで入手可能なＡＳＣＩ  Ｐｕｒｐｌｅ  Ｂｅｎｃｈｍａｒｋのウェブ・ページにあるような、非構造化メッシュ上のフォトン（photon）移送問題を解決するＡＳＣＩ  Ｐｕｒｐｌｅ  Ｂｅｎｃｈｍａｒｋである。このアプリケーションは、ＭＰＩおよびオプションでＯｐｅｎＭＰを使用してＦｏｒｔｒａｎ−９０で作成される。非構造化メッシュは、ＭＥＴＩＳライブラリを使用してコード内で静的に区分される。１タスクあたりの計算作業の量にはかなりの広がりがあるため、このコードには重大な計算負荷の不均衡がある可能性がある。しかしながらこの実施形態では、同じく重要な通信の不均衡のみが対処される。
【００８０】
Ｃｕｂｉｃ  ２、ＳＡＧＥ、およびＵＭＴ２０００の通信パターンが、図４、５、および６に示される。ＣｕｂｉｃおよびＳＡＧＥのケースは、規則的な通信パターンを有する。ＵＭＴ２０００は不規則なパターンを有する。図４では、Ｃｕｂｉｃ  ２問題の通信パターンは８×８×８トーラス上にある。図５では、ＳＡＧＥの通信パターンは８×８×８グリッド上にある。ＳＡＧＥは極度に規則的な通信パターンを有し、ノードはそれらのＭＰＩ順位の近隣とのみ通信し、フルパターンのサブセットのみが示される。
【００８１】
表１、２、および３は、研究された各テスト・ケースについての様々なグリッド・サイズおよび擬似焼きなましの変形形態に関する、最適化の結果を示す。
【００８２】
この表で、「理想」は、前述の自由エネルギーに関する理想的な「理論上の」値を示す。「ヒューリスティック」は、セクション３のヒューリスティック配置アルゴリズムが使用される場合に達成される値である。「ＭＰＩ順位」は、ドメインがＭＰＩ順位で配置される場合に達成される値である。「ランダム」は、１００のドメインをスーパーコンピュータ・トーラス上にランダムに配置する場合に達成される平均値である。「理想」および「ランダム」のケースでは、それぞれ正規化された自由エネルギーに対して下限および上限を提供する。最後の「ｓａ  ｎ」エントリは、ドメインがＭＥＴＩＳを使用してｉｔサブドメインに分割され、全問題がマッピングされるまでこれらの各サブドメインの配置が首尾よく最適化される、分割統治の変形形態に対して達成された結果を提供する。この変形形態で、「ｓａ  １」ケースは、すべてのノードを含む１区画での全擬似焼きなまし実行を表す。図７は、分割統治法によって生成された典型的な収束曲線を示すプロットである。
【００８３】
図１１は、予想通り既知の最適なマップを見つける、Ｃｕｂｉｃ  １およびＣｕｂｉｃ  ２マップを入手する方法を示す表１である。これらは３Ｄ問題であり、理想的なマッピング・ケースが識別しやすいために選択される。理想的なマッピング・ケースは、１の正規化自由エネルギーを有する。ヒューリスティック、ＭＰＩ順位、およびランダムのケースは、本発明で説明された様々な配置ストラテジによって達成可能な、自由エネルギー値に対する基準値を提供する。これらの問題では、１に等しい正規化自由エネルギーで最適なレイアウトを生成した（的確なソリューション）、すべてのノードを含む単一の区画（ｓａ  １）のみを使用して焼きなましが試行された。
【００８４】
続いて図１２では、ＵＭＴ２０００に関する最適化の結果を示す表２が示され、デフォルト・マップ（ＭＰＩ順位）を介したコスト関数における改善は、２５６および１０２４の両方のタスクについて約１．６６の因数による。図１３では、表３が、ＳＡＧＥについて達成された改善結果を示す。デフォルトＭＰＩレイアウトを介したこの改善は、２５６および２０４８のＭＰＩタスクについて約１．５２および２．４５の因数である。図１４は、いくつかの異なるマップを使用して、５１２のプロセッサＳＡＧＥ実行に関する通信時間結果を示す表４である。ＭＰＩ順位マップのコストおよび時間は、それぞれコストおよび通信時間を正規化するために使用される。これらは、非常に重要な結果であり、「マップに関して測定される通信コスト」と題する次のセクションに示されるような通信性能の改善につながる。本発明を使用した実験は、より大量のタスクに関する改善が等しいかまたはさらに良好となることを確実に示すであろう。
【００８５】
マップに関して測定される通信コスト
これまでは、自由エネルギー値における改善について論じてきた。次に、異なるマッピングが使用された場合の、測定される通信時間における変化を示す結果を提示する。様々なマッピングを使用するスーパーコンピュータ・ハードウェアで、あるアプリケーションを実行した。各マッピングのランタイムが記録され、より重要なことには、ＭＰＩのポイント・ツー・ポイント通信でアプリケーションが費やした時間が測定された。この実施形態では、ＵＭＴ２０００よりも多くの通信バウンドであるため、ＳＡＧＥが最も適切なアプリケーションとして５１２ノード区画上で使用される。
【００８６】
マッピングは前述の方法を使用して作成された。さらに、最も良く知られた手作りのマップも使用された。ＭＰＩ順位に関連付けられたコストおよび時間は、正規化定数として使用される。
【００８７】
図８は、マッピングに関するコスト関数および通信時間における改善要因を示すプロットである。図７は、デフォルトのＭＰＩ順位付けマップに対するコストおよび通信時間を示す。結果は興味深いものである。単一区画の擬似焼きなまし実行によって作成された最良のマッピングは、デフォルトのＭＰＩ順位付けマップにわたって、因数１．７９の改善を示す。ヒューリスティック方法および４区画擬似焼きなまし実行も、因数１．７を超える改善を示す。加えて、すべての擬似焼きなまし実行およびヒューリスティック方法は、手作りのマップよりも通信時間が短い。本発明者等の方法を使用して発見されたマッピングは、実際のランタイム性能においても、手作りのマッピング（ＭＰＩ順位にわたって因数１．５９３の改善しか示さない）よりも良好である。コスト関数とランタイムとの間に完全な一致が見られない理由は、コスト関数が通信パターンまたはネットワーク挙動を完全にモデル化しない（これには法外に費用がかかる）ためである。
【００８８】
他の実施形態および結論
本発明でテストされた最適化のケースでは、擬似焼きなまし方法が良好なマッピングを生成し、並列コードのための一般的なレイアウト最適化ツールとして使用される可能性を有することが示された。これまでに開発された直列コードは、ＭＰＩで容易に実施可能である。アプリケーションがデフォルト・マッピングを使用して実行される場合、ランタイム・システムは通信トラフィックの分析を行い、実行の終わりに、後続の実行で使用するための改良されたマップを提案するための分析を行うように、コードを作成することもできる。その後、ユーザには、後続の実行のためにデフォルトのＭＰＩ順位マップの代わりに最適化されたマップを使用するための、ランタイム・フラグを使用するオプションが与えられる。
【００８９】
本明細書で説明した方法が実際に有用な場合（多種多様な実際のアプリケーション全体にわたる性能利得につながる）、最適なレイアウトが発見された後に同じ問題サイズに対して繰り返し実行することが予測されるアプリケーションにとっては、特に有用であろう。この方法は、未知の問題をスーパーコンピュータにマッピングする際の初期設定ステップとしても有用な可能性がある。これは、自動メッシュ改良（いくつかの気象モデル化コード、ＳＡＧＥ、航空機シミュレーション・コードなど）を使用する問題でも役立つ。
【００９０】
例示の目的で、本発明の諸実施形態では、ポイント・ツー・ポイント通信およびＢＧ／Ｌスーパーコンピュータのトーラス・ネットワークを含む最適化について論じてきた。しかしながら、当業者であれば、本発明の真の範囲および趣旨において、グローバル・ツリー・ネットワークを使用し、ドメイン（アプリケーション内に存在する場合）間での負荷の不均衡を計算する、集合通信が、コスト関数を適切に修正することによってこの分析に含まれることを理解されよう。
【００９１】
以上、本発明の好ましい諸実施形態について図示および説明してきたが、本発明がこのように限定されるものでないことは明らかであろう。当業者であれば、添付の特許請求の範囲によって定義された本発明の趣旨および範囲を逸脱することなく、多数の修正、変更、変形、置換、および等価を思いつくであろう。
【図面の簡単な説明】
【００９２】
【図１】本発明に従って解決された問題例に関する通信マトリクスＣ（ｉ，ｊ）の構造を示すプロットである。
【図２】本発明に従った擬似焼きなましアルゴリズムの実行例に関する、正規化された自由エネルギーの展開を示すプロットである。
【図３】本発明に従った、同じ実行に関する各固定βセグメントの最後尾で達成される正規化された自由エネルギーの値を示すプロットである。
【図４】８×８×８問題についてのＣｕｂｉｃソフトウェア・アプリケーションに関する通信マップを示す図であるが、これは本発明を使用して任意のコンピュータ・ネットワーク上で実施可能な入力マップの単なる例示に過ぎないことに留意されたい。
【図５】８×８×８問題についてのＳＡＧＥソフトウェア・アプリケーションに関する通信マップを示す図であるが、これは本発明を使用して任意のコンピュータ・ネットワーク上で実施可能な入力マップの単なる例示に過ぎないことに留意されたい。
【図６】８×８×８問題についてのＵＭＴ２０００ソフトウェア・アプリケーションに関する通信マップを示す図であるが、これは本発明を使用して任意のコンピュータ・ネットワーク上で実施可能な入力マップの単なる例示に過ぎないことに留意されたい。
【図７】本発明に従った、分割統治法によって生成された典型的な収束曲線を示すプロットである。
【図８】アプリケーションＳＡＧＥに関する本発明に従った、マッピングに関するコスト関数および実際のランタイム時通信時間における改善要因を示すプロットである。
【図９】本発明が有利に使用されることが示された、５１２のコンピューティング・ノードを有する典型的な基本トーラス構成からの、８つのコンピューティング・ノードを相互接続する３次元トーラス形状のごく一部を示す図である。
【図１０】本発明に従った、グローバル信号および外部ネットワーク接続を含むグローバル結合ツリーを示す図である。
【図１１】本発明に従った、Ｃｕｂｉｃ  １およびＣｕｂｉｃ  ２のケースについて達成される最適化の結果を示す表１である。
【図１２】本発明に従った、ＵＭＴ２０００について達成される最適化の結果を示す表２である。
【図１３】本発明に従った、ＳＡＧＥについて達成される最適化の結果を示す表３である。
【図１４】本発明に従った、いくつかの最適化マップを使用して、５１２のプロセッサＳＡＧＥ実行に関する通信時間結果を示す表４である。
【図１】
2008516346.tif 000008
【図２】
2008516346.tif 000009
【図３】
2008516346.tif 000010
【図４】
2008516346.tif 000011
【図５】
2008516346.tif 000012
【図６】
2008516346.tif 000013
【図７】
2008516346.tif 000014
【図８】
2008516346.tif 000015
【図９】
2008516346.tif 000016
【図１０】
2008516346.tif 000017
【図１１】
2008516346.tif 000018
【図１２】
2008516346.tif 000019
【図１３】
2008516346.tif 000020
【図１４】
2008516346.tif 000021
【国際調査報告】
2008516346.tif 000022
2008516346.tif 000023
2008516346.tif 000024