(57)【要約】      （修正有）【課題】三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図るプロセスの自動最適配置を提供する。【解決手段】複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行うジョブ管理ノード１１が、三次元トーラス構造における各ノードの位置座標を保持し、各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた計算ノード１２と、計算ノード１２によるファイル入出力時のアクセス対象である各Ｉ／Ｏノード１３との間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、算定値が最小となるＩ／Ｏノード１３と計算ノード１２の組を特定し、特定した組の計算ノード１２のＭＰＩランクを決定する。【選択図】図１
2012252591.tif 000002
【特許請求の範囲】
【請求項１】
複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行う情報処理システムであって、
前記三次元トーラス構造における各ノードの位置座標を保持している記憶部と、
記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードを並列プログラム実行の基準とし、ＭＰＩランクを「０」とする計算ノードと決定する処理を実行する演算部と、
を備えることを特徴とするプロセス割当システム。
【請求項２】
前記三次元トーラス構造によるネットワークトポロジーは、ｘ、ｙ、ｚ軸方向の各々に環状の構造を有し、２つのノード間通信において１以上のネットワークスイッチを経由した通信が実行されるものであり、
前記記憶部における各ノードの位置座標の情報は、所定ネットワークスイッチを三次元の原点座標にした場合の、各ネットワークスイッチにおける前記原点座標との相対位置座標によって三次元座標が規定されており、
前記演算部は、ノード間で通信を行う場合の経路上のネットワークスイッチ数を、該当各ノードの三次元座標間におけるｘ、ｙ、ｚ座標のそれぞれの差分の合計を算定して求めることを特徴とする請求項１に記載のプロセス割当システム。
【請求項３】
前記演算部は、前記ＭＰＩランクが「０」のノードとの経路上のネットワークスイッチ数を各計算ノードについて算定し、ＭＰＩプログラムのジョブ投入時に指定されたプロセス数に応じた数の計算ノードを、前記算定したネットワークスイッチ数が少ない順に選択することを特徴とする請求項１または２に記載のプロセス割当システム。
【請求項４】
前記演算部は、
ＭＰＩ集団通信関数の実行に際し、前記プロセス数に応じて選択された計算ノード群を、基準となる前記ＭＰＩランク「０」のノードとの経路上のネットワークスイッチ数の多少により、前記ネットワークスイッチ数が少ない方のグループであり、ＭＰＩランク「０」のノードをベースノードとするグループＡ、前記ネットワークスイッチ数が多い方のグループのグループＢ、の２分割するグループ分けの処理と、
前記グループＢに含まれる計算ノードのうち、前記ネットワークスイッチ数が最少のものを、当該グループＢにおいて、ＭＰＩ集団通信関数実行時に前記ＭＰＩランク「０」のノードから最初にデータ転送を受けるベースノードとして特定する処理と、
前記グループＡ、Ｂのそれぞれに関し、ベースノード以外の計算ノードが残っている限り、前記グループ分けの処理および前記ベースノードの特定の処理を再帰的に繰り返し実行する処理とを実行するものである、
ことを特徴とする請求項３に記載のプロセス割当システム。
【請求項５】
前記演算部は、ＭＰＩ実装に際し、前記プロセス数に応じて選択された計算ノード群について、少なくとも該計算ノード群が含む前記ＭＰＩランク「０」の計算ノードおよび前記各グループのベースノードの情報をＭＰＩランク情報としてファイル出力することを特徴とする請求項４に記載のプロセス割当システム。
【請求項６】
複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行うべく、記憶部において、前記三次元トーラス構造における各ノードの位置座標を保持したコンピュータが、
記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードのＭＰＩランクを決定する処理を実行することを特徴とするプロセス割当方法。
【請求項７】
複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行うべく、記憶部において、前記三次元トーラス構造における各ノードの位置座標を保持したコンピュータに、
記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードのＭＰＩランクを決定する処理を実行させる、
ことを特徴とするプロセス割当プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセス割当システム、プロセス割当方法、およびプロセス割当プログラムに関するものであり、具体的には、三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図る、プロセスの自動最適配置を可能とする技術に関する。
【背景技術】
【０００２】
近年の大規模ＰＣクラスタシステムでは、三次元トーラス構造によるネットワークトポロジーにより計算ノードを接続し、多数の計算ノードを同時に使用することで並列プログラムを実行する。並列プログラムを実行する計算資源は、ジョブ管理ノードにより決定される。ジョブ管理ノードは、並列プログラムを実行するために必要となる計算能力、メモリ容量をもつ計算ノードをユーザ指定のノード数で確保することになる。並列プログラムは、こうして確保された計算ノードのＣＰＵ資源を使用し計算を行うとともに、他のノードに対してデータ入出力やファイル入出力の各処理を行い、全体の計算を進めていく。
【０００３】
科学技術計算分野の並列プログラムは、一般にＭＰＩ(Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ Ｉｎｔｅｒｆａｃｅ)ライブラリを用いて実装されるものがほとんどである。並列プログラムの実行時には、このＭＰＩのプロトコルに従い複数のプロセス間でメッセージ（データ）を送受信し、全体としての計算を進めていく。
【０００４】
こうした技術に関して、三次元トーラス構造のネットワークトポロジーによって計算ノードを接続しているＰＣクラスタシステムを対象に、大規模なＭＰＩプログラムをジョブ投入する場合、計算ノード間の距離が最小となるよう資源確保を行うスケジューリング技術（特許文献１参照）などが提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１４６８６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述のように、大規模ＰＣクラスタシステムで実行される並列プログラムは、複数のプロセス間でメッセージ（データ）を送受信しながら全体の計算を進めていく。プロセスを実行する複数の計算ノードは、上記の従来技術などによりジョブ管理プログラムにより決定される。一方、並列プログラムの実行に要する時間は、計算時間と通信時間の和で求めることができる。このうち前記計算時間は、各プロセス間でほぼ同じ計算時間となるように最適化が実施されている。ここで、前記通信時間は、メッセージ送受信のプロセスを実行する計算ノード間の距離によって変化する。
【０００７】
このため、並列プログラムの実行に要する全体時間の短縮を目指す場合、通信時間をもできるだけ短縮するために、計算ノードの割り当てに加えてプロセスの最適配置を行う技術が必要になる。しかしながら従来技術では、並列プログラムを実行する上で通信時間の短縮は考慮されておらず、利用者は手動で通信ログを採取し、プロセスを割り当てる計算ノードの配置を試みていた。
【０００８】
そこで本発明の目的は、三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図る、プロセスの自動最適配置を可能とする技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決する本発明のプロセス割当システムは、複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行う情報処理システムであって、前記三次元トーラス構造における各ノードの位置座標を保持している記憶部と、記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードのＭＰＩランクを決定する処理を実行する演算部と、を備えることを特徴とする。
【００１０】
また、本発明のプロセス割当方法は、複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行うべく、記憶部において、前記三次元トーラス構造における各ノードの位置座標を保持したコンピュータが、記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードのＭＰＩランクを決定する処理を実行することを特徴とする。
【００１１】
また、本発明のプロセス割当プログラムは、複数ノードと結ばれたネットワークスイッチが三次元トーラス構造で相互に接続された大規模ＰＣクラスタシステムにおいて、ＭＰＩプログラムを対象とする並列プログラム実行のためのプロセス割り当てを行うべく、記憶部において、前記三次元トーラス構造における各ノードの位置座標を保持したコンピュータに、記憶部における前記三次元トーラス構造における各ノードの位置座標に基づいて、各ネットワークスイッチに結ばれた、並列プログラム実行に当たってプロセス割り当てを受け計算を行う各計算ノードと、該計算ノードによるファイル入出力時のアクセス対象である各Ｉ／Ｏノードとの間の、三次元トーラス構造での経路におけるネットワークスイッチ数を算定し、該算定値が最小となるＩ／Ｏノードと計算ノードの組を特定し、該特定した組の計算ノードのＭＰＩランクを決定する処理を実行させる、ことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図る、プロセスの自動最適配置が可能となる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態のプロセス割当システム（ジョブ管理ノード）を含む大規模ＰＣクラスタシステムの構成例を示す図である。
【図２】本実施形態の計算ノードの構成例を示す図である。
【図３】本実施形態のジョブ管理ノードの構成例を示す図である。
【図４】本実施形態における一次元トーラス構造を示す図である。
【図５】本実施形態におけるネットワークスイッチと計算ノードの構成例を示す図である。
【図６】本実施形態の二次元トーラス構造を示す図である。
【図７】本実施形態の三次元トーラス構造の一部を示す図である。
【図８】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステムを示す図である。
【図９】本実施形態のＭＰＩプログラムの集団通信関数による並列処理を示す図である。
【図１０】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステム上で並列プログラムを実行する空間を示す図である。
【図１１】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステムの大きさを示す図である。
【図１２】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステムを構成する計算オブジェクトを示す図である。
【図１３】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステムを構成するＩ／Ｏオブジェクトを示す図である。
【図１４】本実施形態のネットワークスイッチおよびノードの命名規則を示す図である。
【図１５】本実施形態のトーラスにおけるオブジェクト間距離を示す図である。
【図１６】本実施形態の三次元トーラスによる大規模ＰＣクラスタシステムのノード間距離を示す図である。
【図１７】本実施形態のプロセス割当方法の処理手順例１を示すフロー図である。
【図１８】本実施形態のプロセス割当方法の処理手順例２を示すフロー図である。
【図１９】本実施形態のＩ／Ｏノードと計算ノードの最小距離を算出するモデルを示す図である。
【図２０】本実施形態のプロセス割当方法の処理手順例３を示すフロー図である。
【図２１】本実施形態のＭＰＩ集団通信関数実行における最小の距離算出にて使用する作業領域を示す図である。
【図２２】本実施形態のプロセス割当方法の処理手順例４を示すフロー図である。
【図２３】本実施形態のＭＰＩ集団通信関数実行における最小の距離算出を行う再帰呼出し関数の関数仕様（ＡＰＩ）を示す図である。
【図２４】本実施形態のプロセス割当方法の処理手順例５を示すフロー図である。
【図２５】本実施形態のプロセス割当方法の処理手順例６を示すフロー図である。
【発明を実施するための形態】
【００１４】
以下に本発明の実施形態について図面を用いて詳細に説明する。図１は、本実施形態のプロセス割当システムたるジョブ管理ノード１１を含むネットワーク構成図である。図１に示すジョブ管理ノード１１は、三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図る、プロセスの自動最適配置を可能とするコンピュータである。
【００１５】
多数の計算ノード１２等が接続された大規模なＰＣクラスタシステム１は、ログインノード１０、前記ジョブ管理ノード１１、計算ノード１２、およびＩ／Ｏノード１３がネットワーク１４に接続された構成となっている。各ノードは１台の計算機であり、他のノードとはネットワーク１４を通じて通信を行う。ＰＣクラスタシステム１の利用者は、ログインノード１０に端末エミュレータソフトウェアなどを使用して接続し、プログラム編集、コンパイル、データ編集などを行うことになる。また、こうしたＰＣクラスタシステム１において、ＭＰＩプログラムに対応して、複数の計算ノード１２を同時に使用する並列プログラムを実行する場合、利用者が、ログインノード１０での操作によりジョブ投入を指示する。
【００１６】
図２は本実施形態の計算ノードの構成例を示す図であり、図３は本実施形態のジョブ管理ノードの構成例を示す図である。上記のジョブ投入時には、ログインノード１０から、ジョブ管理ノード１１で動作中のジョブ管理プログラム３０４に対し、通知が行われる。ジョブ管理プログラム３０４の一つの機能であるスケジューリング機能３０６は、並列プログラムを実行する複数の計算ノード候補を決定し、その情報をジョブキュー３０７に保存する。
【００１７】
また、ジョブ管理プログラム３０４のもう一つの機能であるジョブ制御機能３０５は、実行状態のジョブの計算ノード１２の状態を常に管理し、スケジューリング機能３０６によって決定された複数の計算ノード候補が使用可能と確認した時点で、その計算ノード候補に並列プログラムのプロセスを生成し、一斉に実行を開始する。
【００１８】
計算ノード１２で実行する並列プログラムのプロセスは、ネットワーク１４を通じ、Ｉ／Ｏノード１３を対象としたファイルアクセスや、別の計算ノード１２で動作する並列プログラムのプロセスとのメッセージ送受信を行いながら並列プログラム全体の実行を進めていく。
【００１９】
実行中の並列プログラムの全プロセスの終了をジョブ管理プログラム３０４のジョブ制御機能３０５が検知した時点で、並列プログラムを実行していた全ての計算ノード１２はプログラム実行中の状態からプログラム未実行の状態となる。プログラム未実行である状態の計算ノード１２は、ジョブ制御機能３０５により、新たなプログラム実行のための計算資源として使用することができる。プログラム実行が終了したジョブの情報は、ジョブ管理プログラム３０４のジョブ制御機能３０５によって、前記ログインノード１０で操作を行った前記利用者（のユーザ端末等）に対し、電子メール等を介して通知される。こうして電子メール等によって通知を受けた利用者は、ログインノード１０での操作により、ジョブ投入を行ったプログラムの出力や実行ステータス、エラー情報などを確認することができる。
【００２０】
ここで前記ジョブ管理ノード１１およびジョブ管理ノード１１のハードウェア構成について、図２，３を用いてあらためて説明する。
【００２１】
前記計算ノード１２は、メモリーやハードディスクドライブなどで構成される記憶部２０１、前記記憶部２０１に格納された並列プログラム２０４等の各種プログラムを実行し計算機自体の統括制御や各種演算等を行なうＣＰＵ部２０２、他装置とネットワーク１４を介してデータ授受を行うネットワークインタフェース部２０３とを備えている。また、前記記憶部２０１、ＣＰＵ部２０２、ネットワークインタフェース部２０３は、ＢＵＳにより結ばれている。
【００２２】
こうした計算ノード１２において、並列プログラム２０４の実行時には、前記記憶部２０１に該当プログラムがローディングされ、所定のオペレーティングシステム（特に図示せず）がその実行制御を行うこととなる。並列プログラム２０４は、計算機能２０５、ファイル入出力機能２０６、データ入出力機能２０７などにより構成され、計算ノード１２のＣＰＵ部２０２と記憶部２０１を使用する。並列プログラム２０４のファイル入出力機能２０６およびデータ入出力機能２０７は、計算ノード外との通信を必要とし、ネットワークインタフェース部２０３を使用して通信を行うこととなる。
【００２３】
また、前記ジョブ管理ノード１１は、メモリーやハードディスクドライブなどで構成される記憶部３０１、前記記憶部３０１に保持されるジョブ管理プログラム３０４等を実行し計算機自体の統括制御や各種判定、演算及び制御処理を行なうＣＰＵ部３０２、ネットワーク１４を介して他装置と接続してデータ授受を行うネットワークインタフェース部３０３を備える。
【００２４】
こうしたジョブ管理ノード１１では、記憶部３０１にジョブ管理プログラム３０４がローディングされ、このジョブ管理プログラム３０４がＣＰＵ部３０２と記憶部３０１を使用して常に動作している。ログインノード１０からのジョブ投入の情報は、ネットワークインタフェース部３０３を通じてジョブ管理プログラム３０４が取得することになる。  このジョブ管理プログラム３０４は、ジョブのスケジューリング機能３０６により、並列プログラムを実行する計算ノード候補を決定する。ジョブ管理プログラム３０４のジョブ制御機能３０５は、ネットワークインタフェース部３０３を通じて、計算ノード１２で実行すべき並列プログラムのプロセス生成や、計算ノード１２で実行するプログラムの状態取得を行う。また、ジョブのスケジューリング機能３０６は、前記ジョブ制御機能３０５より取得した最新の全ての計算ノード１２の実行情報を参照し、並列プログラムを実行する計算ノード候補を決定する。スケジューリング機能３０６は、ジョブスケジューリングを行った情報をジョブキュー３０７に登録する。また、スケジューリング機能３０６は、前記ジョブ制御機能３０５により実行対象の計算ノード候補が利用可能であることが検出された時点で、その計算ノード１２を対象に、並列プログラムのプロセスを生成し実行を開始させる。
【００２５】
図４は、一次元のトーラス構造を示す図である。トーラス構造は、基準点から一方向に進んでいく場合に元の基準点に戻る特性をもつ構造である。図４における構造では、オブジェクト４０１を基準点とし、右回りに順に進んでいく場合にオブジェクト４０１に戻る。同様に左回りに順に進んでいく場合も元のオブジェクト４０１に戻るため、図４の構造はトーラス構造である。図４のトーラス構造が計算機システムを構成するネットワーク構造となる場合は、オブジェクト４０１はネットワークスイッチをその内部に含み、オブジェクト間は、ネットワークケーブルによりネットワークスイッチ同士を接続する構成となる。このような構造を有するネットワークは、一台のネットワークスイッチの障害やネットワークケーブルの断線が発生した場合に、逆方向のネットワークスイッチとネットワークケーブルを使用し通信を行うことでオブジェクト４０１の通信が可能となり、冗長性を有する構造となっている。
【００２６】
図５は、トーラス構造によるネットワークトポロジーにより計算機システムを構築する場合のオブジェクト（ネットワーク構成要素）の内部構造を示す図である。オブジェクト４０１は、ネットワークスイッチ５０１と複数のノード５０２で構成する。また、ネットワークスイッチ５０１は、当該ネットワークスイッチ５０１を中心に、ｘ軸方向、ｙ軸方向、ｚ軸方向の全６方向に対してネットワークケーブルを接続し、隣のオブジェクト（ネットワーク構成要素）のネットワークスイッチ５０１との間で通信を行う。
【００２７】
ネットワークスイッチ５０１には、ｘ軸方向同士を接続するネットワークケーブル５０３、ｙ軸方向同士を接続するネットワークケーブル５０４、ｚ軸方向同士を接続するネットワークケーブル５０５、オブジェクト４０１に含まれるノード５０２と接続するネットワークケーブル５０６を接続のために使用する。
【００２８】
ネットワークスイッチ５０１は、これらの経路から取得したパケットに対するスイッチングを行い、オブジェクト内部のノード方向あるいは外部のオブジェクト（ネットワーク構成要素）方向にパケットを送出する。同じネットワークスイッチ５０１に接続されるノード５０２の間で通信を行う場合は、１台のネットワークスイッチ５０１のみのスイッチングでノード５０２間のデータ転送を完結することができる。異なるネットワークスイッチ５０１に接続されるノード５０２と通信を行う場合には、送信元のノード５０２から当該ノード５０２が属するネットワークスイッチ５０１にデータを送り、そこから別のオブジェクト４０１に含まれるネットワークスイッチ５０１にデータが送られる。これを受信先のノード５０２を含んでいるオブジェクト４０１に至るまで隣のネットワークスイッチ５０１を対象とした通信を繰り返し、最後に受信先のノード５０２を含んでいるネットワークスイッチ５０１から受信先のノード５０２にデータを送ることで、２つのノード間でのデータ転送を完了する。
【００２９】
図６は、二次元トーラス構造を示す図である。二次元トーラス構造は、基準点から一方向に進んでいく場合に元の基準点に戻る特性を２つの軸に対して同時に満たす構造である。図６の構造において、オブジェクト４０１を基準点とし、右方向に進んでいく場合も左方向に進んでいく場合も元のオブジェクト４０１に戻る。同様に、オブジェクト４０１を基準点とし、上方向に進んでいく場合も下方向に進んでいく場合も元のオブジェクト４０１に戻る。これらの特徴を兼ね備えていることから、図６の構造は二次元トーラス構造としての要件を満たしている。オブジェクト４０１はネットワークスイッチ５０１とノード５０２で構成しており、ネットワークスイッチ５０１のｘ軸方向およびｙ軸方向にネットワークケーブルを接続することで、二次元トーラス構造のネットワークを構成することができる。
【００３０】
図７は、三次元トーラス構造を示す図である。三次元トーラス構造は、基準点から一方向に進んでいく場合に元の基準点に戻る特性を３つの軸に対して同時に満たす構造である。図７の構造において、オブジェクト４０１を基準点とし、ｘ軸方向に進んでいく場合、ｙ軸方向に進んでいく場合、そしてｚ軸方向に進んでいく場合のそれぞれで元のオブジェクト４０１に戻る。これらの特徴を全て満たしていることから、図７の構造は三次元トーラス構造としての要件を満たしている。オブジェクト４０１はネットワークスイッチ５０１とノード５０２で構成しており、ネットワークスイッチ５０１のｘ軸方向、ｙ軸方向およびｚ軸方向にネットワークケーブルを接続することで、三次元トーラス構造のネットワークを構成することができる。
【００３１】
図８は、三次元トーラス構造による大規模ＰＣクラスタシステムの構成例を示す図である。大規模ＰＣクラスタシステム１は、三次元トーラス構造のネットワークトポロジーによりオブジェクト（ネットワーク構成要素）間を接続する。オブジェクト４０１は２種類に分類され、１台のネットワークスイッチ５０１と複数の計算ノード１２によって構成されるオブジェクト８０３と、１台のネットワークスイッチ５０１と複数の計算ノード１２のほかに１台または複数のＩ／Ｏノード１３、ログインノード１０、ジョブ管理ノード１１を含むオブジェクト８０４とする。大規模ＰＣクラスタシステム１で並列プログラムをジョブとして実行する場合、利用者はいずれかのオブジェクト８０４に含まれるログインノード１０に端末エミュレータソフトウェアなどを使用して接続し、所定操作によってジョブ投入を行う。
【００３２】
並列プログラムを実行する計算ノード候補の決定は、いずれかのオブジェクト８０４に含まれるジョブ管理ノード１１で常に動作するジョブ管理プログラム３０４のスケジューリング機能３０６によって行い、計算ノード候補ができるだけ密となる三次元空間で並列プログラムを実行する計算ノード候補を集約するよう、スケジューリングを行う。
【００３３】
このようなスケジューリングを実施した結果、三次元トーラス構造の三次元空間の一部分であるジョブ実行空間８０２の中の複数のオブジェクト４０１に含まれる各計算ノード１２が並列プログラムをそれぞれ実行する。
【００３４】
計算ノード１２で実行するプログラムがファイル入出力を行う場合において、同一のネットワークスイッチ５０１にＩ／Ｏノード１３が接続され、その中のファイルが入出力の対象である場合は、ネットワークスイッチ間の通信を必要とせずにファイル入出力が可能である。そうでない場合は、別のオブジェクト８０４に接続されるＩ／Ｏノードを対象にファイル入出力を行うこととなり、ネットワークスイッチ間の通信を何回か繰り返す通信を行って、ファイル入出力を行う。
【００３５】
図９は、ＭＰＩプログラムにおいてＭＰＩ＿ＢＣＡＳＴ関数などの集団通信関数を実行した場合のデータの流れの例を示す図である。ＭＰＩ＿ＢＣＡＳＴ関数は１つのプロセスのみが所有しているデータを他の全てのプロセスに与える機能を提供する。ＭＰＩ＿ＢＣＡＳＴ関数は、同期型の関数であり、全プロセスでＭＰＩ＿ＢＣＡＳＴ関数を実行すると、内部で同期を行った後、データ転送のための通信を並列に行い、１つのプロセスが所有するデータを残りの全てのプロセスに与えることができる。
【００３６】
ＭＰＩプログラムがＮプロセスで実行され、ＭＰＩ＿ＢＣＡＳＴ関数が全プロセスから呼び出される場合は、データを所有する１プロセスからデータを所有しない残りの（Ｎ−１）プロセスに対してＮ−１回のデータ転送を行う方式を行わない。図９に示す方式によって、ＭＰＩプログラムのプロセスあたり最大ｌｏｇ2 Ｎ回（小数点以下は切り上げ）の通信を行い全てのプロセスへのデータを転送する。
【００３７】
図９は、ＭＰＩプログラムが８プロセスの並列で実行される場合の、ＭＰＩ＿ＢＣＡＳＴ関数実行時のデータの流れを示している。この図の場合、Ｎ＝８であるために、プロセスあたり最大ｌｏｇ2 Ｎ回すなわち最大３回の転送回数で全てのプロセスへのデータ転送が完了する。図９は並列数が「８」であるために８プロセスのそれぞれにＭＰＩランクとして０から７までが与えられる。
【００３８】
データははじめにＭＰＩランク「０」のプロセスが保持しており、これをＭＰＩランク１から７までの７プロセスにＭＰＩ＿ＢＣＡＳＴ関数によって与える。１回目の転送ではＭＰＩランク０のプロセスとＭＰＩランク４のプロセスとの間でデータを送受信する。次に２回目の転送処理ではＭＰＩランク０のプロセスはＭＰＩランク２のプロセスとの間でデータを送受信する。ＭＰＩランク４のプロセスは既にデータを受信済みであり、この時に並行してＭＰＩランク０から受信したデータを直ちにＭＰＩランク４のプロセスとＭＰＩランク６のプロセスとの間で送受信する。２回目までの転送処理が完了した時点でデータを所有するＭＰＩランクは０，２，４，６の４つとなる。次に３回目の転送処理を行う時点ではＭＰＩランク０のプロセスはＭＰＩランク１のプロセスとの間で送受信を行う。同じく既にデータを受信しているプロセスはまだ未受信のプロセスとの間で送受信を行い、ＭＰＩランク２のプロセスはＭＰＩランク３のプロセスと、ＭＰＩランク４のプロセスはＭＰＩランク５のプロセスと、ＭＰＩランク６のプロセスはＭＰＩランク７のプロセスとの間で送受信を行う。その結果、ここまでの全ての送受信が完了した時点でデータは全てのプロセスが持つこととなる。ＭＰＩランク０のプロセスが３回のデータ送受信を行う間に、他のＭＰＩランクのプロセスがデータ未受信のプロセスを対象に適切にデータ送受信を繰り返すことで短い時間で全プロセスへのデータ転送を完了することができる。本方式は、ｌｏｇ2 Ｎ回数で全プロセスへの転送が完了するため、例えば６５５３６プロセスのＭＰＩプログラムの中でＭＰＩ＿ＢＣＡＳＴ関数を実行した場合は１６回（ｌｏｇ2 ６５５３６＝１６）の転送回数に要する時間で全６５５３６プロセスで同一データを持つことができる。
【００３９】
図１０は三次元トーラス構造によるＰＣクラスタシステム１における計算ノード１２とＩ／Ｏノード１３の距離について示した図である。三次元トーラス構造によるＰＣクラスタシステム１は計算ノード１２のみを含むオブジェクト（以下、計算オブジェクト）とＩ／Ｏノード１３を含むオブジェクト（以下、Ｉ／Ｏオブジェクト）で構成し、いくつかの計算オブジェクトおよびＩ／Ｏオブジェクトによってジョブ実行空間８０２を構成している。
【００４０】
ジョブ実行空間８０２は計算オブジェクト１００１および計算オブジェクト１００２を含んでいる。ここでオブジェクト間の距離は２つのオブジェクトの物理空間上の距離ではなく、２つのオブジェクト４０１を接続しているネットワークスイッチ５０１の三次元空間座標上の差分と定義する。このような定義を行った上で、Ｉ／Ｏオブジェクト１００３と計算オブジェクト１００１の距離とＩ／Ｏオブジェクト１００３と計算オブジェクト１００２の距離を比較する。計算オブジェクト１００１と計算オブジェクト１００２の座標のｘおよびｙが同じであり、ｚのみが異なる場合を考えることとする。ＰＣクラスタシステム１の全体は三次元トーラス構造であるため、図１０においてＩ／Ｏオブジェクト１００３が存在するＰＣクラスタシステム１の一番下のｘｙ平面は一番上のｘｙ平面とｚ方向に隣の関係にある。このため、ジョブ実行空間８０２でＩ／Ｏオブジェクト１００３により近い計算オブジェクトはｚ方向に隣となる計算オブジェクト１００１である。ジョブ実行空間８０２はＩ／Ｏオブジェクト１００４も含んでいる。Ｉ／Ｏオブジェクト１００４も計算ノードを含んでおり、ジョブ実行空間８０２に含む計算オブジェクト１００１、計算オブジェクト１００２、Ｉ／Ｏオブジェクト１００４で一番Ｉ／Ｏノードに近い計算ノードを含むオブジェクトはＩ／Ｏオブジェクト１００４でその距離を０とする。
【００４１】
図１１は三次元トーラス構造によるＰＣクラスタシステム１の大きさを示した図である。トーラス構造は基準点から一方向に進んでいく場合に同じ基準点に戻る性質があるため、同一方向に無限に進むことも可能となる。ここでｘ方向に進み、再び基準点に到達するまでのオブジェクト４０１の個数をＭｘ個とする。同様にｙ方向およびｚ方向に進み、基準点に到達するまでのオブジェクト４０１の個数をＭｙ個およびＭｚ個とする。ｘ、ｙ、ｚ方向に共通の基準となる三次元空間の原点を設け（０,０,０）の座標位置にあるオブジェクト４０１を定義する。ｘ方向にＭｘ個、ｙ方向にＭｙ個、ｚ方向にＭｚ個のオブジェクトが存在しているため、三次元トーラス構造によるＰＣクラスタシステム１を構成するオブジェクト４０１は、全て三次元座標で表すことができる。全てのオブジェクト４０１は（０,０,０）から(Ｍｘ−１,Ｍｙ−１,Ｍｚ−１)までのいずれかの座標に存在し、オブジェクト総数はＭｘ×Ｍｙ×Ｍｚ個である。
【００４２】
図１２は計算オブジェクトの三次元座標位置とオブジェクトの内部構造との関連を示した図である。計算オブジェクトはネットワークスイッチ５０１と複数の計算ノード１２で構成する。計算オブジェクトの座標位置はネットワークスイッチ５０１の座標位置と同一とし、隣接のネットワークスイッチ５０１のｘ、ｙ、ｚ方向に対して１をプラスまたはマイナスした位置となる。三次元トーラス構造であるために、ｘ座標がとりうる座標位置としては０からＭｘ−１までである。ｙ座標も同様に０からＭｙ−１まで、ｚ座標も同様に０からＭｚ−１までである。
【００４３】
あるネットワークスイッチ５０１のｘ座標が０またはＭｘ−１である場合、隣のネットワークスイッチ５０１の座標は、−１またはＭｘが座標値とならず、ｘ座標が０の場合に１をマイナスした座標位置としてＭｘ−１、ｘ座標がＭｘ−１の場合に１をプラスした座標位置として０となる。ｙ座標の値が０またはＭｙ−１の場合やｚ座標の値が０またはＭｚ−１の場合にも同様となる。
【００４４】
また、計算オブジェクト内部の計算ノード１２に関してもノード番号を設定する。図１２では計算オブジェクトは計算ノード１２を６ノード有し、ノード番号０１から０６までとしている。このノード番号は、オブジェクトの中で一意の値となるように設定する。三次元トーラス構造のＰＣクラスタシステム１からノードを特定する場合、オブジェクト４０１の三次元座標とノード番号との組合せにより求めることができる。
【００４５】
図１３はＩ／Ｏオブジェクトの三次元座標位置とオブジェクトの内部構造との関連を示した図である。Ｉ／Ｏオブジェクトは計算オブジェクトとほぼ同じであるが、複数の計算ノード１２に加えてＩ／Ｏノード１３を含むことが異なる。Ｉ／Ｏオブジェクトの座標位置については計算オブジェクトと同じ考え方であり、ノード番号についても同じ考え方である。Ｉ／Ｏオブジェクト内部の計算ノード１２およびＩ／Ｏノード１３に関して、図１３の例では計算ノード１２を６ノード、Ｉ／Ｏノード１３を１ノード有している。これらのノード番号がＩ／Ｏオブジェクトで一意の値となるように、計算ノード１２のノード番号は０１から０６までとし、Ｉ／Ｏノード１３のノード番号はこれに続く０７とする。
【００４６】
図１４はオブジェクトを構成するネットワークスイッチ５０１およびノード５０２の名称と三次元空間座標やノード番号との対応関係を示した表である。三次元トーラス構造によるＰＣクラスタシステム１を構成するオブジェクト４０１は、三次元座標を持ち、計算ノード１２およびＩ／Ｏノード１３には同一オブジェクト内で一意となるノード番号をもつ。
【００４７】
オブジェクトには１台のネットワークスイッチ５０１があり、ネットワークスイッチ名にはオブジェクトの三次元座標を与えることで、三次元トーラス空間内での一意のネットワークスイッチ名称をもつことができる。この例におけるネットワークスイッチ名称は「Ｓ＋座標位置」とし、先頭文字たるＳでスイッチであることを、それ以外の文字でネットワークスイッチ５０１の座標位置を表す。座標位置を示す情報はｘ、ｙ、ｚそれぞれの座標値を１文字で表し、合計で３文字とする。座標値が１０未満である場合は１０進数の値として０から９までの１文字で表現できる。座標値が１６未満の場合は１６進数の値として、０からＦまでの１文字で表現する。座標値が１６以上の場合はｎ進数としてＦより後のアルファベット文字を使用することにより解決する（１６＝Ｇ，１７＝Ｈ，１８＝Ｉ，以下同様）。
【００４８】
また、ノード名はオブジェクト４０１の座標位置に加えてノード番号を使用する。ノード名称は「Ｎ＋座標位置+＿+ノード番号」とし、先頭文字のＮでノードであることを、それ以外の文字によりオブジェクト座標とノード番号を表す。ノード名称には座標位置が含まれ、これはノード５０２が接続されるネットワークスイッチ５０１の座標と同じであるため、ノード５０２が接続するネットワークスイッチ５０１はノード名から自明となる。ノード名の座標位置の部分の名称が同一である場合は同一のネットワークスイッチ５０１に接続されていることを表し、ノード間の距離は「０」となる。一方、ノード名の中の座標位置の部分が異なる場合には異なるネットワークスイッチ５０１に接続されていることを表している。
【００４９】
図１５はオブジェクト間の距離について示した図である。上述してきたとおり、トーラス構造は基準点から同一方向に進む場合に元の基準点に戻る特性がある。図１５に例示する一次元トーラス構造は、Ｍｘ個のオブジェクト４０１で構成されており、オブジェクト１５０１を基準点としている。この基準点から右回りにｎ個進んだオブジェクト１５０２までの距離を考える場合、右回りに進んだ距離と左回りに進んだ距離の２通りが存在する。
【００５０】
オブジェクト１５０１とオブジェクト１５０２の間の距離は、右回りに進んだ場合はｎ、左回りに進んだ場合はＭｘ−ｎである。ここでｎがＭｘ／２より小さい場合には右回りに進む距離が小さく、Ｍｘ／２より大きい場合には左回りに進む距離が小さくなる。オブジェクト間の距離は、このように進む経路により２通りの値をとるが、Ｍｘ／２以下の、より小さい値をオブジェクト間の距離と定義する。オブジェクト４０１はネットワークスイッチ５０１と複数のノード５０２で構成しており、オブジェクトの距離は２つのネットワークスイッチ間の距離、２つのノード間の距離と等しい。ここでいう距離は三次元トーラス構造のＰＣクラスタシステム１において、ネットワークスイッチ５０１を経由する個数という意味となる。
【００５１】
図１６は三次元トーラス構造によるＰＣクラスタシステム１のノード間の距離の計算方法を示した図である。三次元トーラスによるＰＣクラスタシステム１は、オブジェクト４０１によりｘ方向、ｙ方向、ｚ方向のそれぞれにトーラス構造をもつ。図１６のＰＣクラスタシステム例においては、ｘ方向に１０個のオブジェクト(Ｍｘ＝１０)、ｙ方向に１０個のオブジェクト(Ｍｙ＝１０)、ｚ方向に１０個のオブジェクト(Ｍｚ＝１０)で構成しているものとする。
【００５２】
座標位置(０，０，０)にあるオブジェクト４０１にノード１６０１があり、このノード番号が０７である場合、図１４で例示した定義によりノード名はＮ０００＿０７と定義できる。また、座標位置(１，１，１)にあるオブジェクト４０１にノード１６０２があり、このノード番号が０１である場合、同様にノード名はＮ１１１＿０１と定義される。また、座標位置(９，０，１)にあるオブジェクト４０１にノード１６０３があり、ノード番号が０６である場合、ノード名はＮ９０１＿０６と定義される。
【００５３】
ここでノード１６０１とノード１６０２との間の距離を考える。ノード１６０１の座標位置は、そのノード名にも表されているように（０，０，０）であり、ノード１６０２の座標位置は(１，１，１)である。ｘ方向の距離を考える場合、右方向には１−０＝１となる。左方向にはＭｘ＝１０であるために１０−１＝９となる。小さい値が距離となるためにノード１６０１とノード１６０２のｘ方向の距離は１である。同様にｙ方向の距離も１、ｚ方向の距離も１である。ここで、ノード間の距離はｘ方向、ｙ方向、ｚ方向の距離を全て足した値となり、ノード１６０１とノード１６０２の間の距離は、前記距離を足した３となる。
【００５４】
同様に、オブジェクト１６０１とオブジェクト１６０３の間の距離を求める。ノード１６０１の座標位置は(０，０，０)、ノード１６０３の座標位置は(９,０,１)である。ｘ方向の距離を考える場合、右方向には９−０＝９となる。左方向にはＭｘ＝１０であるために１０−９＝１となる。小さい値を採用するためにノード１６０１とノード１６０３のｘ方向の距離は１となる。同様にｙ方向の距離は０、ｚ方向の距離は１である。以上によりノード１６０１とノード１６０３の距離は２である。最後にノード１６０２とノード１６０３の距離を求める。ノード１６０２の座標位置は(１，１，１)、ノード１６０３の座標位置は(９，０，１)である。ｘ方向の距離を考える場合、右方向には９−１＝８となる。左方向にはＭｘ＝１０であるために１０―９＋１＝２となる。小さい値を採用するためにノード１６０２とノード１６０３のｘ方向の距離は２となる。同様にｙ方向の距離は１、ｚ方向の距離は０である。以上によりノード１６０２とノード１６０３の距離は３である。
【００５５】
以下、本実施形態におけるプロセス割当方法の実際手順について図に基づき説明する。以下で説明するプロセス割当方法に対応する各種動作は、主として前記ジョブ管理ノード１１が実行するジョブ管理プログラム３０４によって実現される。そして、こうしたプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００５６】
図１７は並列プログラムを実行する際の、利用者の操作手順と合わせて、ジョブ管理ノード１１におけるジョブ管理プログラム３０４のスケジューリング機能３０６、およびジョブ制御機能３０５の処理フロー例を示す図である。
【００５７】
利用者はログインノード１０に大規模ＰＣクラスタシステム１の外部のネットワークを通じて端末エミュレータソフトウェアなどを使用してログイン（Ｓ１７０１）し、対話的な操作をログインノード１０で行う。また、利用者はログインノード１０上で並列プログラムの入力データをファイルシステム上に作成（Ｓ１７０２）し、その後にジョブ投入のための操作を行うことで並列プログラムの実行指示（Ｓ１７０３）を行う。ログインノード１０上の実行指示（Ｓ１７０３）はジョブ管理ノード１１で常に動作するジョブ管理プログラム３０４にネットワーク１４を通じ、直ちに通知される。
【００５８】
一方、ジョブ管理ノード１１で動作するジョブ管理プログラム３０４のスケジューリング機能３０６では、ジョブ実行対象の計算ノード構成を定義するキューの情報をファイルやデータベースなどを通じて取得（Ｓ１７０７）し、利用者が指定したプログラム実行のための要件とキューの構成を比較する。その結果とジョブ制御機能３０５が提供する計算ノード１２の使用状況の情報とを用いてジョブスケジューリング（Ｓ１７０８）を行い、並列プログラム実行のための情報をジョブという単位で管理する。一つ一つのジョブにはジョブＩＤと呼ぶ一意の識別番号をジョブ管理プログラム３０４が設定する。
【００５９】
前記ジョブ管理ノード１１のスケジューリング機能３０６は、前記ジョブスケジューリング（Ｓ１７０８）によって生成するジョブを、ＦＩＦＯ（Ｆｉｒｓｔ Iｎ  Ｆｉｒｓｔ Ｏｕｔ）を基本とするジョブキューを対象にジョブ登録（Ｓ１７０９）する。登録したジョブはジョブＩＤをキーとしてジョブキュー３０７から取得することができる。
【００６０】
また、前記スケジューリング機能３０６は、該当ジョブのジョブＩＤを、ログインノード１０にて対話的操作を行ってジョブ投入を行った前記利用者（の操作端末）に対し、応答メッセージとして返却する。
【００６１】
実行要件に合致する全計算ノード候補のうち、他のジョブのプログラムが実行されておらずプログラム実行が可能であるものについて検知したジョブ制御機能３０５は、プログラムを実行する計算ノード候補に関して、実行環境初期化（Ｓ１７１０）を行い、前記ジョブ登録（Ｓ１７０９）によってジョブキュー３０７に登録された情報について「実行待ち」から「実行開始」にジョブのステータスを変更する。
【００６２】
その後、前記ジョブ制御機能３０５は、計算ノード候補に対しジョブの実行プログラムのプロセスを生成し、ジョブ実行（Ｓ１７１１）によってプログラムの実行を開始する。この時に、ジョブキュー３０７で「実行開始」から「実行中」に該当ジョブのステータスを変更する。ログインノード１０の利用者は、ジョブＩＤによってジョブの実行状況を確認することが可能であり、この場合、例えばジョブ制御機能３０５が前記ジョブキュー３０７から、該当するジョブＩＤを有するジョブのステータスの情報を読み出して表示する。  また、計算ノード１２での実行中プログラムの終了について検知したジョブ制御機能３０５は、ジョブ実行終了（Ｓ１７１２）の処理を行う。ジョブ実行終了（Ｓ１７１２）の処理では、プログラム実行結果の情報を電子メール等により、ログインノード１０の利用者のアカウントに対して送信するとともに、前記ジョブキュー３０７にて「実行中」から「実行終了」に該当ジョブのステータスを変更する。ログインノード１０の利用者は（所定の端末において）、ジョブ管理プログラム３０４より送信された電子メールを受信し、その内容やプログラムが出力した結果ファイルの参照などをログインノード１０上で閲覧する、実行結果確認（Ｓ１７０５）を行う。
【００６３】
図１８は、ＭＰＩプログラムでの通信時間最小化を目的として、前記スケジューリング機能３０６にＭＰＩランク決定機能を追加する処理の流れを示した図である。ジョブ管理ノード１１にて実行するジョブ管理プログラム３０４のスケジューリング機能３０６は、ジョブ実行対象の計算ノード構成の定義情報としてファイルやデータベースなどからジョブキュー３０７の情報取得（Ｓ１８０１）を行う。次にスケジューリング機能３０６は、ジョブ制御機能３０５が具備する計算ノード１２の実行状態取得機能を用いて、ジョブキュー３０７を構成する計算ノード１２の実行状況の取得（Ｓ１８０２）を行う。
【００６４】
スケジューリング機能３０６は、その後に計算ノード１２の実行状況とジョブキュー３０７の制限条件、既にスケジューリングが完了しているジョブの優先度や並列プログラム実行のために指定された要件などの情報などからジョブスケジューリング（Ｓ１８０３）を行い、ジョブキュー３０７に登録する情報（ジョブ）を生成する。
【００６５】
いままでのスケジューリング機能３０６では、ジョブ登録（Ｓ１８０４）でジョブ管理プログラム３０４のスケジューリング機能３０６が完了するが、本方式ではジョブ登録（Ｓ１８０４）の前にジョブスケジューリング（Ｓ１８０３）により決定した計算ノードに対して一般的なＭＰＩプログラムが通信時間を短縮するためのＭＰＩランクの決定（Ｓ１８０５）を行うこととなる。
【００６６】
スケジューリング機能３０６に追加をするＭＰＩランクの決定を行う処理（Ｓ１８０５）は４つの処理で成り立っており、初めにＭＰＩランクが「０」となる計算ノード１２を決定する処理（Ｓ１８０６）を行って、一般的なＭＰＩプログラムにおいて他のノードとは異なる特別な役割を行うことが多いＭＰＩランクが「０」となるプロセスを配置する計算ノード１２を決定する。
【００６７】
ＭＰＩランクの決定を行う処理（Ｓ１８０５）の次処理では、ＭＰＩ集団通信関数の実行で通信経路が最小となるための情報を保持するテーブルの初期化（Ｓ１８０７）を行い、その後にＭＰＩランクが「０」以外となる計算ノードを決定する処理（Ｓ１８０８）を行う。これらの処理は、ＭＰＩ集団通信関数の通信時間を短縮するためのＭＰＩプロセス配置を決定する。ここまでの処理の追加でＭＰＩプログラム全体の通信時間を短縮するためのＭＰＩランクは決定している。ＭＰＩランクの決定を行う処理（Ｓ１８０５）に追加する最後の処理では、決定したＭＰＩランクをファイルなど外部に出力する処理（Ｓ１８０９）を行う。  また、ジョブ登録の処理（Ｓ１８０４）では、ジョブキュー３０７に登録する情報と、ＭＰＩランクが出力されるファイルの情報とを関連付けした後に、これら情報をジョブキュー３０７に登録する。ジョブキュー３０７に登録しているジョブに関しては、計算ノード１２の状態の変更（ノードの故障、ノードの追加など）やジョブの実行状況の変化（強制終了やジョブの凍結、優先順位の変更）などによって、一度決定した計算ノード１２を変更する再スケジューリングを行うことがある。本方式によって追加を行うこれらの処理は計算ノード１２が変更となる再スケジューリングが発生した場合には、新たにスケジューリングが行われた計算ノード候補を対象として前記Ｓ１８０６から前記Ｓ１８０９までの処理を再度行い、ジョブキュー３０７に登録しているジョブと一致したＭＰＩランク情報を生成する。
【００６８】
図１９はＭＰＩランクが「０」となる計算ノード１２を決定する処理の考え方を導くための、三次元トーラス構造によるＰＣクラスタシステム１の構成図である。ＭＰＩランクが「０」のプロセスは、その他のプロセスと比較して特別な処理を行うケースが多い。例えば、入出力ファイルをアクセスする処理を、ＭＰＩランクが「０」のプロセスが全プロセスを代表して行うことや、ＭＰＩランクが「０」のプロセスが読み込んだ入力データを、ＭＰＩ＿ＢＣＡＳＴ関数などのＭＰＩ集団通信関数を使用して全プロセスに配布するといった例を挙げることができる。
【００６９】
ファイル入出力を実行する計算ノード１２はＩ／Ｏノード１３との距離が小さいことは入出力時間の短縮とネットワーク資源の効率的な利用の点で優位となる。図１９の三次元トーラスによるＰＣクラスタシステム１において、Ｉ／Ｏノード１９０２は座標位置(０，０，０)のノード番号０７にあるとする。一方、並列プログラムの実行はジョブ実行空間８０２のいずれかのオブジェクト内の計算ノード１２を使用するものとする。ジョブ実行空間８０２の中の計算ノード１２のどれをＭＰＩランク「０」とすべきかはオブジェクト間の距離を算出し、その距離が一番小さいノードを特定することで行う。こうして特定したノードは最も効率よく最小の通信量でファイル入出力を行うことが可能である。
【００７０】
ここで、オブジェクト間の距離を算出するための式は式１９０３であり、図１４で例示したノード名の規則に従う場合のＩ／Ｏノード名に含まれる座標位置を(ｘ１,ｙ１,ｚ１)とし、計算ノード名に含まれる座標位置を(ｘ２,ｙ２,ｚ２)とする。ジョブ管理ノード１１は、この２つの座標を式１９０３に当てはめてオブジェクト間の距離を算出する。全ての計算ノード１２とＩ／Ｏノード１３との組み合わせで距離を求め、一番距離の小さい計算ノード１２をＭＰＩランク「０」のプロセスを実行する計算ノードと決定する。
【００７１】
図１９のジョブ実行空間８０２は全て計算オブジェクトのみで構成しているが、Ｉ／Ｏオブジェクトを含む場合は、Ｉ／Ｏオブジェクトに含まれる計算ノード１２が一番距離の小さい計算ノードとなり（Ｉ／Ｏノードと計算ノードが同一ネットワークスイッチ５０１に接続されるため）、その場合にはＭＰＩランク「０」をＩ／Ｏオブジェクトに含む計算ノード１２となる。Ｉ／Ｏオブジェクトは複数の計算ノード１２を含み、ＭＰＩランク「０」とする計算ノード１２のノード番号はオブジェクト内の計算ノード１２の最小のノード番号を有する計算ノード１２とする。
【００７２】
図２０は、本実施形態のＭＰＩ集団通信関数実行における最小の距離算出を示すフローであって、ジョブ管理ノード１１による、ＭＰＩランク「０」とするプロセスを実行する計算ノード１２を求めるフローチャートとなる。このフローは図１８のＭＰＩランク「０」のノードの決定（Ｓ１８０６）の詳細な処理内容を示している。
【００７３】
ここで、ジョブ管理ノード１１は、ノード間の最小距離、計算ノード１２およびＩ／Ｏノード１３に関するノード番号や三次元座標位置を初期化する（Ｓ２００２）。続いて、ジョブ管理ノード１１は、ＰＣクラスタシステム１を構成するＩ／Ｏノード１３の座標情報を、例えば記憶部３０１の定義ファイルやデータベースなどから取得（Ｓ２００３）する。同様に、ジョブ管理ノード１１は計算ノード１２の座標情報を前記定義ファイルやデータベースなどから取得する（Ｓ２００４）。これらの処理によりジョブ管理ノード１１は、全てのＩ／Ｏノード名が格納されるリストと全ての計算ノード名が格納されるリストを用意している。
【００７４】
次にジョブ管理ノード１１は、Ｉ／Ｏノード名のリストと計算ノード名のリストを用いた２重ループ構造の処理によって、ＭＰＩランク「０」とする計算ノード１２を求める。繰り返し処理Ｓ２００５はＩ／Ｏノード名のリストによる繰り返しであり、ジョブ管理ノード１１は、そのループ内でＩ／Ｏノード名を分解しＩ／Ｏノード１３の座標とノード番号を取得する（Ｓ２００６）。次にジョブ管理ノード１１は、繰り返し処理Ｓ２００７にて、計算ノード名のリストによる繰り返しを実行し、そのループ内で計算ノード名を分解し、計算ノード１２の座標とノード番号を取得する（Ｓ２００８）。
【００７５】
続いてジョブ管理ノード１１は、前記Ｓ２００６およびＳ２００８の処理で取得したＩ／Ｏノード座標と計算ノード座標からノード間の距離を算出する（Ｓ２００９）。ジョブ管理ノード１１はこのＳ２００９で算出した距離と、これまで得ているノード間の最小距離とを判定処理Ｓ２０１０によって比較し、前記Ｓ２００９で算出した距離が既存の最小距離より小さい場合には（Ｓ２０１０：ｙｅｓ）、ノード間の最小距離、計算ノード座標とノード番号、Ｉ／Ｏノード座標とノード番号を該当ノードの情報で更新する（Ｓ２０１１）。ジョブ管理ノード１１は、計算ノード１２に対する繰り返し終了Ｓ２０１２とＩ／Ｏノード１３に対する繰り返し終了Ｓ２０１３を行い、全てのＩ／Ｏノード１３と計算ノード１２の組み合わせに対して上記の処理を行うことで、最終的に一番距離の小さいＩ／Ｏノード座標とノード番号、計算ノード座標とノード番号を決定し、ここで求めた計算ノード１２をＭＰＩランクが「０」の計算ノードとする。
【００７６】
図２１はＭＰＩランクを決定する処理で扱う計算ノード一覧のテーブル情報を示す図である。計算ノード一覧テーブル２１０１は、並列プログラムを実行するプロセス数だけ要素数すなわちレコードがある。一つのプロセスについては３つの情報をもつ。一つはプロセスを実行する計算ノード名（nodename）である。計算ノード名のカラムには計算ノードが含まれるオブジェクトすなわちネットワークスイッチ５０１の三次元座標位置とノード番号の２つの情報を含んでいる。グループＩＤ（groupid）のカラムはＭＰＩランクの決定処理を実行していく上で作業用に使用し、初期値は全て「０」である。ＭＰＩランクのカラム（mpirank）は、決定したＭＰＩランクを設定し、初期値は全て「−１」である。ＭＰＩランクが負の値であることはＭＰＩランクが未決定であることを表し、０以上の値はＭＰＩランクが決定していることを表す。
【００７７】
この図２１の上段における計算ノード一覧テーブル２１０１は、初期状態のテーブルであり、全てのグループＩＤは「０」、全てのＭＰＩランクは「−１」に設定されている。一方、図２０で述べた処理を行い、ＭＰＩランクが「０」となるノード名が決定した場合、ジョブ管理ノード１１は、前記決定した計算ノード１２について、ＭＰＩランクのカラムの値を「０」に設定する。
【００７８】
図２２は計算ノード一覧テーブル２１０１を初期化するフローチャートであり、図１８のランクテーブルの初期化（Ｓ１８０７）の詳細な処理内容を示している。はじめに、ジョブ管理ノード１１は、前記スケジューリング機能３０６によって決定した計算ノード候補のリストを取得し、所定記憶領域での「Nodelist」に設定する（Ｓ２２０１）。次にジョブ管理ノード１１は、計算ノード一覧テーブル２１０１をメモリー上に確保し、所定記憶領域に設定したカウンタiをゼロに初期化する（Ｓ２２０２）。次にジョブ管理ノード１１は、繰り返し処理Ｓ２２０３の内部で計算ノード一覧テーブル２１０１のノード名（nodename）に、計算ノード一覧のリストからインデックスiで取得した計算ノード名を設定し、計算ノード一覧テーブル２１０１のグループＩＤ(groupid)をゼロに初期化する（Ｓ２２０４）。  次にジョブ管理ノード１１は、比較処理Ｓ２２０５において、計算ノード一覧からインデックスiで取得した計算ノード名と、前記ＭＰＩランク「０」のノードの決定（Ｓ１８０６）で決定しているＭＰＩランクが「０」の計算ノード名とを比較する。
【００７９】
これらノード名が一致しない場合（Ｓ２２０５：ｎｏ）、ジョブ管理ノード１１は計算ノード一覧テーブル２１０１のＭＰＩランク(mpirank)に、ＭＰＩランク未決定を表す「−１」を設定する（Ｓ２２０６）。他方、前記ノード名が一致する場合（Ｓ２２０５：ｙｅｓ）、ジョブ管理ノード１１は計算ノード一覧テーブル２１０１のＭＰＩランク(mpirank)に、前記ＭＰＩランクの値である「０」を設定する（Ｓ２２０７）。
【００８０】
その後、ジョブ管理ノード１１は、前記カウンタｉを更新し（Ｓ２２０８）、繰り返し処理Ｓ２２０３の終了判定により、計算ノード一覧のリストにインデックスｉでアクセスできる限り、繰り返し処理を行う（Ｓ２２０９）。全ての処理を終了した時点では、計算ノード一覧テーブル２１０１の全ての要素の計算ノード名には、スケジューリング機能３０６により決定した計算ノード名が、グループＩＤ（groupid）には「０」が設定される。ＭＰＩランクが０である計算ノード１２のＭＰＩランク（mpirank）のみに「０」を設定し、その他の計算ノードのＭＰＩランク(mpirank)には「−１」を設定する。
【００８１】
図２３はジョブ管理ノード１１がＭＰＩランクが「０」以外のＭＰＩランクを決定する処理の関数仕様を示した図である。ここで、図１８のランク０以外のＭＰＩランク決定（Ｓ１８０８）を行うための処理を一つの関数とし、この関数は図２１のテーブルに格納された情報を更新しながらＭＰＩランクが「０」以外のプロセスを実行する計算ノードを決定していく。関数名は「ＲａｎｋＤｅｃｉｓｉｏｎ」とし、５つの引数を必要とする。この関数は再帰呼出しを行い、再帰呼び出しの深さは第５引数の「ｄｅｐｔｈ」に設定する（初期の深さは０である）。
【００８２】
ＲａｎｋＤｅｃｉｓｉｏｎ関数の第１引数には、図２１に示した計算ノード一覧テーブルを指定する。第２引数には図２１に示した計算ノード一覧テーブルの要素数（プロセス数）を指定する。第３引数には基準ランクを指定し、初回の呼び出し時にはＭＰＩランク「０」のノードのみが決定済みであり、「０」を指定する。第４引数は対象のグループＩＤであり、初回の呼び出し時には図２２の処理により、初期化を行った値である「０」を指定する。第５引数は関数の再帰呼出し数を指定し、初回の呼び出し時には「０」を指定する。ＲａｎｋＤｅｃｉｓｉｏｎ関数は、指定されたグループＩＤの範囲で深さ「ｄｅｐｔｈ」の集団通信実行時に、基準ランク（ベースノード）と通信を行う相手のＭＰＩランクを求める。この時、グループＩＤを２分割し、一方は次の深さで基準ランクと通信を行うグループＩＤでＲａｎｋＤｅｃｉｓｉｏｎ関数を呼び出す。もう一方は新たなグループＩＤを更新し、今回決定した相手先のＭＰＩランクを新たな基準ランクとし、次の深さにて新たな基準ランクと通信を行う新たなグループＩＤでＲａｎｋＤｅｃｉｓｉｏｎ関数を呼び出す。
【００８３】
図２４および図２５はＭＰＩランク「０」以外のＭＰＩランクを決定する処理のフローチャートであり、図１８のランク０ノード以外の決定（Ｓ１８０８）の詳細な処理内容を示している。この場合、ジョブ管理ノード１１が、ＭＰＩランク「０」以外の計算ノードを決定する処理に際し、前記ＲａｎｋＤｅｃｉｓｉｏｎ関数２３０１を利用する。ＲａｎｋＤｅｃｉｓｉｏｎ関数２３０１は図２３に示す関数仕様に従って処理を行う。引数で与えられた「ｂａｓｅｎｏｄｅ」には既にＭＰＩランクが決定している計算ノード１２のＭＰＩランクが設定され、初回のＲａｎｋＤｅｃｉｓｉｏｎ関数呼出し時には図２０の処理で決定するＭＰＩランク「０」が設定される。
【００８４】
この場合、ＲａｎｋＤｅｃｉｓｉｏｎ関数は、はじめに「ｂａｓｅｎｏｄｅ」で指定されたＭＰＩランクのプロセスが実行される計算ノード１２の名称を取得する（Ｓ２４０１）。次にＲａｎｋＤｅｃｉｓｉｏｎ関数は、先に取得した計算ノード名と、グループＩＤが一致する各計算ノードとのそれぞれの距離を求め、各ノード間の距離一覧を作成する。ＲａｎｋＤｅｃｉｓｉｏｎ関数は、ここで求めた距離が最大のノード名を保存する（Ｓ２４０２）。距離が最大のノード名は、「ｂａｓｅｎｏｄｅ」の計算ノード１２から最も多くネットワークスイッチ５０１を経由したデータ転送が必要となる計算ノード１２である。
【００８５】
次にＲａｎｋＤｅｃｉｓｉｏｎ関数は、最も距離の遠いノードとグループが一致する全てのノードとでそれぞれの距離を求め保存する（Ｓ２４０３）。このことによりＲａｎｋＤｅｃｉｓｉｏｎ関数は、グループＩＤが一致するノードについて「ｂａｓｅｎｏｄｅ」からの距離と、「ｂａｓｅｎｏｄｅ」から最も距離の遠いノードからの距離との２つの距離を算出する。次にＲａｎｋＤｅｃｉｓｉｏｎ関数は、処理Ｓ２４０３までに求めた２つの距離をもとにグループを２分する（Ｓ２４０４）。これまでは同一のグループに所属していたものを２分割するのである。「ｂａｓｅｎｏｄｅ」から距離が近いものを、例えばＡグループ、「ｂａｓｅｎｏｄｅ」から最も遠いノードから距離が近いものをＢグループとする。ノード数ｎが偶数である場合は、ＡグループおよびＢグループに所属するノードは各々ｎ／２である。ノード数ｎが奇数である場合は、最後に残るノードは「ｂａｓｅｎｏｄｅ」からの距離と「ｂａｓｅｎｏｄｅ」から一番遠いノードからの距離とを比較し、小さいほうのグループに所属する。
【００８６】
次にＲａｎｋＤｅｃｉｓｉｏｎ関数は、新しいグループＩＤを設定する（Ｓ２４０５）。「ｂａｓｅｎｏｄｅ」に近いグループはグループＩＤを２倍した値を新しいグループＩＤとしてグループＩＤを更新する。最初の呼び出しではグループＩＤは「０」であるため、２倍し更新されたグループＩＤも「０」である。「ｂａｓｅｎｏｄｅ」から最も遠いノードに所属するグループはグループＩＤを２倍して１を加えた値を新しいグループＩＤとして設定する。最初の呼び出しではグループＩＤは「０」であるため、更新されたグループＩＤは「１」となり、新しいグループＩＤとして「１」を設定する。
【００８７】
処理Ｓ２４０５をグループＩＤが「０」の場合に行うことで、新しいグループＩＤとして「０」のグループと「１」のグループとにノード群を分割し、グループ設定することになる。
【００８８】
続いてＲａｎｋＤｅｃｉｓｉｏｎ関数は、「ｂａｓｅｎｏｄｅ」から最も遠いノードに所属するグループの中で、「ｂａｓｅｎｏｄｅ」に最も距離が近いノードを検索する（Ｓ２４０６）。Ｓ２４０６の処理で検索したノードには、ＭＰＩランクをテーブル２１０２に設定する。ここで設定するＭＰＩランクは引数で渡された「ｂａｓｅｎｏｄｅ」、「ｔａｂｌｅｃｎｔ」、「ｄｅｐｔｈ」によって一意となる値である。ＲａｎｋＤｅｃｉｓｉｏｎ関数は、ＭＰＩランクを設定した後、判定処理Ｓ２４０７により、２分割したグループＢの個数が「０」より大きい場合（Ｓ２４０７：ｙｅｓ）、グループＢを対象にＲａｎｋＤｅｃｉｓｉｏｎ関数を呼出す（Ｓ２４０８）。再帰呼出しが行われたＲａｎｋＤｅｃｉｓｉｏｎ関数は、これまでのＳ２４０１からＳ２４０６までの処理を行い、グループの分割と１つのＭＰＩランクの決定を行い、必要に応じて更にＲａｎｋＤｅｃｉｓｉｏｎ関数を呼び出す。判定処理Ｓ２４０７の後に判定処理Ｓ２４０９により、２分割したグループＡの個数が０より大きい場合（Ｓ２４０９：ｙｅｓ）、グループＡを対象にＲａｎｋＤｅｃｉｓｉｏｎ関数を呼出す（Ｓ２４１０）。再帰呼出しが行われたＲａｎｋＤｅｃｉｓｉｏｎ関数は、これまでのＳ２４０１からＳ２４０６までの処理を行い、グループの分割と１つのＭＰＩランクの決定を行い、必要に応じて更にＲａｎｋＤｅｃｉｓｉｏｎ関数を呼び出す。再帰呼出しでは、ＭＰＩランク決定に伴って更新したテーブルとサイズ、決定したＭＰＩランク、「ｂａｓｅｎｏｄｅ」から近いノードに所属するグループのグループＩＤ、「ｄｅｐｔｈ」に１を加えた値をＲａｎｋＤｅｃｉｓｉｏｎ関数の引数として渡すことになる。
【００８９】
以上、本発明を実施するための最良の形態などについて具体的に説明したが、本発明はこれに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能である。
【００９０】
こうした本実施形態によれば、三次元トーラス構造の大規模ＰＣクラスタシステム上で、ＭＰＩライブラリを用いた並列プログラムの実行時間短縮を図る、プロセスの自動最適配置が可能となる。
【００９１】
本明細書の記載により、少なくとも次のことが明らかにされる。すなわち、前記プロセス割当システムにおいて、前記三次元トーラス構造によるネットワークトポロジーは、ｘ、ｙ、ｚ軸方向の各々に環状の構造を有し、２つのノード間通信において１以上のネットワークスイッチを経由した通信が実行されるものであり、前記記憶部における各ノードの位置座標の情報は、所定ネットワークスイッチを三次元の原点座標にした場合の、各ネットワークスイッチにおける前記原点座標との相対位置座標によって三次元座標が規定されており、前記演算部は、ノード間で通信を行う場合の経路上のネットワークスイッチ数を、該当各ノードの三次元座標間におけるｘ、ｙ、ｚ座標のそれぞれの差分の合計を算定して求めるとしてもよい。
【００９２】
また、前記プロセス割当システムにおいて、前記演算部は、前記ＭＰＩランク「０」のノードとの経路上のネットワークスイッチ数を各計算ノードについて算定し、ＭＰＩプログラムのジョブ投入時に指定されたプロセス数に応じた数の計算ノードを、前記算定したネットワークスイッチ数が少ない順に選択するとしてもよい。
【００９３】
また、前記プロセス割当システムにおいて、前記演算部は、ＭＰＩ集団通信関数の実行に際し、前記プロセス数に応じて選択された計算ノード群を、前記ＭＰＩランク「０」のノードとの経路上のネットワークスイッチ数の多少により、前記ネットワークスイッチ数が少ない方のグループであり、ＭＰＩランク「０」のノードをベースノードとするグループＡ、前記ネットワークスイッチ数が多い方のグループのグループＢ、の２分割するグループ分けの処理と、前記グループＢに含まれる計算ノードのうち、前記ネットワークスイッチ数が最少のものを、当該グループＢにおいて、ＭＰＩ集団通信関数実行時に前記ＭＰＩランク「０」のノードから最初にデータ転送を受けるベースノードとして特定する処理と、前記グループＡ、Ｂのそれぞれに関し、ベースノード以外の計算ノードが残っている限り、前記グループ分けの処理および前記ベースノードの特定の処理を繰り返し実行する処理とを実行するとしてもよい。
【００９４】
また、前記プロセス割当システムにおいて、前記演算部は、ＭＰＩ実装に際し、前記プロセス数に応じて選択された計算ノード群について、少なくとも該計算ノード群が含む計算ノードおよび前記各グループのベースノードの情報をＭＰＩランク情報としてファイル出力するとしてもよい。
【符号の説明】
【００９５】
１  大規模ＰＣクラスタシステム
１０  ログインノード
１１  ジョブ管理ノード（プロセス割当システム）
１２  計算ノード
１３  Ｉ／Ｏノード
１４  ネットワーク
２０１  計算ノードの記憶部
２０２  計算ノードのＣＰＵ部
２０３  計算ノードのネットワークインタフェース部
２０４  並列プログラム
３０１  ジョブ管理ノードの記憶部
３０２  ジョブ管理ノードのＣＰＵ部（演算部）
３０３  ジョブ管理ノードのネットワークインタフェース部
３０４  ジョブ管理プログラム
４０１  オブジェクト
５０１  ネットワークスイッチ
８０２  ジョブ管理プログラムが確保したノード空間
８０３  計算ノードのみで構成するオブジェクト
８０４  計算ノードとＩ／Ｏノードで構成するオブジェクト
【図１】
2012252591.tif 000003
【図２】
2012252591.tif 000004
【図３】
2012252591.tif 000005
【図４】
2012252591.tif 000006
【図５】
2012252591.tif 000007
【図６】
2012252591.tif 000008
【図７】
2012252591.tif 000009
【図８】
2012252591.tif 000010
【図１０】
2012252591.tif 000011
【図１１】
2012252591.tif 000012
【図１２】
2012252591.tif 000013
【図１３】
2012252591.tif 000014
【図１４】
2012252591.tif 000015
【図１５】
2012252591.tif 000016
【図１６】
2012252591.tif 000017
【図１７】
2012252591.tif 000018
【図１８】
2012252591.tif 000019
【図１９】
2012252591.tif 000020
【図２０】
2012252591.tif 000021
【図２１】
2012252591.tif 000022
【図２２】
2012252591.tif 000023
【図２３】
2012252591.tif 000024
【図２４】
2012252591.tif 000025
【図２５】
2012252591.tif 000026
【図９】
2012252591.tif 000027