【手続補正書】
【提出日】平成20年7月3日(2008.7.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
並列処理システム上の２つまたはそれ以上の並列計算ノードにわたってソフトウェア・アプリケーションの割り振りを最適化するためのコンピュータ実施方法であって、
通信ファブリックによって互いに結合された並列処理システム上の２つまたはそれ以上の並列計算ノードにわたって実行するための複数のソフトウェア計算を有する、ソフトウェア・アプリケーションの通信プロファイルを受け取るステップであって、前記複数のソフトウェア計算のうちの第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含む、受け取るステップと、
ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にするステップであって、前記通信コストは、前記ソフトウェア・アプリケーションが前記ソフトウェア計算間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、最小にするステップと、
を有する、コンピュータ実施方法。
【請求項２】
ノード間で転送されるソフトウェア・アプリケーション・データの前記合計量が、前記ソフトウェア・アプリケーションの前記通信コストを削減するように、グローバルおよび離散時間間隔のうちの少なくとも１つで最小化される、請求項１に記載のコンピュータ実施方法。
【請求項３】
前記通信コストが、使用可能通信トポロジの使用、ネットワーク・トポロジのタイプ、バッファの可用度、ネットワーク・トポロジでのコンテンション、ソフトウェア・アプリケーション・オーバヘッド、および通信待ち時間のうちの、少なくとも１つに依存する、請求項１に記載のコンピュータ実施方法。
【請求項４】
前記コスト関数を数学的に最小にすることに応答して、少なくとも前記ソフトウェア計算で、前記複数のノードのうちの１つから前記複数のノードのうちの他のノードへ再配置するステップをさらに有する、請求項１に記載のコンピュータ実施方法。
【請求項５】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、以前にマッピングされたノードと共にアプリケーション・データを送る前記ソフトウェア計算のそれぞれが、最近隣にあるノードとして定義された近隣ノードにマッピングされるように、前記ソフトウェア計算のそれぞれを前記ノードのうちの１つに順次マッピングするヒューリスティック・マップを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項６】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、それらの間で送られるソフトウェア・アプリケーション・データの量に関して最大限に独立したソフトウェア計算を識別する、グラフ区画マップを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項７】
前記グラフ区画マップが、グラフ内のクリークおよびバイクリークを決定するために少なくとも１つのアルゴリズムを使用するステップを含む、請求項６に記載のコンピュータ実施方法。
【請求項８】
前記グラフ区画マップがＭＥＴＩＳツールを使用するステップを含む、請求項６に記載のコンピュータ実施方法。
【請求項９】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、並列処理システム上の２つまたはそれ以上の並列計算ノードｊにわたって実行するための複数のソフトウェア計算ｉを有し、前記複数のソフトウェア計算のうちの前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの前記第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、Ｃ（ｉ，ｊ）によって与えられた前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記ノード間通信コスト関数が、前記第１のソフトウェア・アプリケーションを前記２つまたはそれ以上のノードのうちの第２のノードへ再配置することによって、前記２つまたはそれ以上のノードのうちの第１のノードに割り振られる前記第１のソフトウェア・アプリケーションについて、Ｆ＝Σｉ，ｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）によって与えられ、前記ノード間通信コスト関数が、前記第１のノードで送られるソフトウェア・アプリケーション・データの前記量と、Ｈ（ｉ，ｊ）によって与えられる、前記第１のノードがソフトウェア・アプリケーション・データを送信した際に使用した前記第１のノードと残りのすべてのノードとの間の通信パス・コスト／データ単位との、積によって与えられる、請求項１に記載のコンピュータ実施方法。
【請求項１０】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、各ノードがそれらの間にトーラス通信ネットワークを備えて３Ｄ格子に配置構成される、並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項１１】
前記ソフトウェア・アプリケーションの前記通信プロファイルを受け取るステップが、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータである並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１に記載のコンピュータ実施方法。
【請求項１２】
請求項１−１１のいずれか１項の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【請求項１３】
複数の独立ネットワークによって相互接続された少なくとも２つの並列計算ノードを備え、各ノードは、通信プロファイルに従って複数の並列アルゴリズム操作を含むソフトウェア・アプリケーションを実行する場合に、計算および通信アクティビティのうちの少なくとも１つを必要に応じて実行するための１つまたは複数の処理要素を含み、前記複数の独立ネットワークは、少なくとも１つのノードおよびその独立した区画サブセットの間で、ポイント・ツー・ポイント、グローバル・ツリー通信、ならびにグローバル・バリアおよび通知操作を実行可能にするためのネットワークを含み、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、前記ソフトウェア・アプリケーションの帯域幅および待ち時間の要件に従って、協調的および単独の少なくとも１つで利用され、前記複数のソフトウェア計算のうちの第１のソフトウェア計算は、前記複数のソフトウェア・アルゴリズムのうちの第２のソフトウェア・アプリケーションからアプリケーション・データを送り、通信プロファイルは、前記ソフトウェア・アルゴリズムのそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にすることによって利用され、前記通信コストは、前記ソフトウェア・アルゴリズムが前記ソフトウェア・アルゴリズム間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、
超並列処理システム。
【請求項１４】
ノード間で転送されるソフトウェア・アプリケーション・データの前記合計量が、前記ソフトウェア・アプリケーションの前記通信コストを削減するように、グローバルおよび離散時間間隔のうちの少なくとも１つで最小化される、請求項２３に記載の超並列処理システム。
【請求項１５】
前記通信コストが、使用可能通信トポロジの使用、ネットワーク・トポロジのタイプ、バッファの可用度、ネットワーク・トポロジでのコンテンション、ソフトウェア・アプリケーション・オーバヘッド、および通信待ち時間のうちの、少なくとも１つに依存する、請求項１３に記載の超並列処理システム。
【請求項１６】
前記コスト関数を数学的に最小にすることに応答して、少なくとも前記ソフトウェア計算で、前記複数のノードのうちの１つから前記複数のノードのうちの他のノードへ再配置するための手段をさらに有する、請求項１３に記載の超並列処理システム。
【請求項１７】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、以前にマッピングされたノードと共にアプリケーション・データを送る前記ソフトウェア計算のそれぞれが、最近隣にあるノードとして定義された近隣ノードにマッピングされるように、前記ソフトウェア計算のそれぞれを前記ノードのうちの１つに順次マッピングするヒューリスティック・マップを受け取るステップを含む、請求項１３に記載の超並列処理システム。
【請求項１８】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、それらの間で送られるソフトウェア・アプリケーション・データの量に関して最大限に独立したソフトウェア計算を識別する、グラフ区画マップを受け取るステップを含む、請求項１３に記載の超並列処理システム。
【請求項１９】
前記グラフ区画マップが、グラフ内のクリークおよびバイクリークを決定するために少なくとも１つのアルゴリズムを使用するステップを含む、請求項１８に記載の超並列処理システム。
【請求項２０】
前記グラフ区画マップがＭＥＴＩＳツールを使用するステップを含む、請求項１８に記載の超並列処理システム。
【請求項２１】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、並列処理システム上の２つまたはそれ以上の並列計算ノードｊにわたって実行するための複数のソフトウェア計算ｉを有し、前記複数のソフトウェア計算のうちの前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの前記第２のソフトウェア・アプリケーションからアプリケーション・データを送り、前記通信プロファイルが、Ｃ（ｉ，ｊ）によって与えられた前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含み、
前記ノード間通信コスト関数が、前記第１のソフトウェア・アプリケーションを前記２つまたはそれ以上のノードのうちの第２のノードへ再配置することによって、前記２つまたはそれ以上のノードのうちの第１のノードに割り振られる前記第１のソフトウェア・アプリケーションについて、Ｆ＝Σｉ，ｊＣ（ｉ，ｊ）Ｈ（ｉ，ｊ）によって与えられ、前記ノード間通信コスト関数が、前記第１のノードで送られるソフトウェア・アプリケーション・データの前記量と、Ｈ（ｉ，ｊ）によって与えられる、前記第１のノードがソフトウェア・アプリケーション・データを送信した際に使用した前記第１のノードと残りのすべてのノードとの間の通信パス・コスト／データ単位との、積によって与えられる、請求項１８に記載の超並列処理システム。
【請求項２２】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、各ノードがそれらの間にトーラス通信ネットワークを備えて３Ｄ格子に配置構成される、並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１８に記載の超並列処理システム。
【請求項２３】
前記ソフトウェア・アプリケーションの前記通信プロファイルが、Ｂｌｕｅ  Ｇｅｎｅ／Ｌスーパーコンピュータである並列処理システム上で前記プロファイルを受け取るステップを含む、請求項１８に記載の超並列処理システム。
【請求項２４】
並列アルゴリズム操作を実行する場合、各ノードが必要に応じて計算または通信アクティビティを実行するための１つまたは複数の処理要素を含む、独立ネットワークによって相互接続された複数の処理ノードと、
ネットワークのノードまたはノードのサブセットの間で、高速、低待ち時間の、ポイント・ツー・ポイントおよびマルチキャスト・パケット通信を提供するために最適化された方法でノードを相互接続する、通信リンクを含むｎ次元トーラス・ネットワークを備える、第１の独立ネットワークと、
前記ネットワークのノードまたはノードのサブセットの間で、同時グローバル操作を容易にするノード相互接続を備える、スケーラブルなグローバル・ツリー・ネットワークを含む、第２の前記複数の独立ネットワークと、
通信プロファイルに従って、ならびに、前記複数のソフトウェア計算のうちの前記第１のソフトウェア計算が、前記複数のソフトウェア計算のうちの前記第２のソフトウェア・アプリケーションからアプリケーション・データを送る要件に従って、独立処理ネットワークの１つまたは複数の組み合わせを動的に構成するための区画化手段であって、前記通信プロファイルは、前記ソフトウェア計算のそれぞれの間で送られるソフトウェア・アプリケーション・データの量を含む、区画化手段と、
前記第１および第２のネットワークの分割可能部分によって相互接続された処理ノードの構成可能サブセットを含む各独立ネットワークであって、前記構成された独立処理ネットワークのそれぞれが、ソフトウェア・アプリケーション処理性能を最適化するための同時協調処理を実行可能にするために利用される、各独立ネットワークと、
を備える、スケーラブルな超並列コンピュータであって、
前記並列計算ノードを相互接続する前記複数の独立ネットワークの組み合わせは、ノード間で転送されるソフトウェア・アプリケーション・データの合計量について、ノード間通信コスト関数を数学的に最小にすることによって協調的または単独で利用され、前記通信コストは、前記ソフトウェア・アルゴリズムが前記ソフトウェア計算間でのソフトウェア・アプリケーション・データ通信に対して前記通信ファブリックを使用する方法に依存する、スケーラブルな超並列コンピュータ。