(57)【要約】【課題】  ジョブを効率良く投入することのできる並列計算機システムを提供する。【解決手段】  並列計算機システムは、投入されたジョブを実行可能な計算ノード３−１〜３−ｎと、上記ジョブを実行中の計算ノードが該実行中のジョブを中断した場合に、該中断したジョブの実行環境が保存されるローカルディスク３３と、計算ノード３−１〜３−ｎのいずれかが空き状態になると、予め蓄積された複数の実行待ちジョブから実行すべきジョブを選択して投入するジョブ管理ノード１１とを有する。ジョブ管理ノード１１は、実行すべきジョブとして複数の投入候補ジョブを選択し、該選択した投入候補ジョブのそれぞれについて、投入した場合に想定される投入コストが最小となる投入先ノードを、各ノードにおける上記ジョブの実行状況および実行環境の保存状況に基づいて決定し、該決定した投入先ノードの投入コストが最も小さな投入候補ジョブを投入ジョブとする。【選択図】図１
2006065658.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが投入されたジョブを実行可能な複数の計算ノードと、
前記ジョブを実行中の計算ノードが該実行中のジョブを中断した場合に、該中断ジョブの実行環境が保存される少なくとも１つのローカルディスクと、
前記複数の計算ノードのそれぞれにおける前記ジョブの実行状況および前記実行環境の保存状況を保持するとともに、前記複数の計算ノードのいずれかが空き状態になると、予め蓄積された複数の実行待ちジョブから実行すべきジョブを選択して投入する管理ノードとを有し、
前記ジョブ管理ノードは、前記実行すべきジョブとして複数の投入候補ジョブを選択し、該選択した投入候補ジョブのそれぞれについて、投入した場合に想定される投入コストが最小となる投入先ノードを、各ノードにおける前記ジョブの実行状況および実行環境の保存状況に基づいて決定し、該決定した投入先ノードの投入コストが最も小さな投入候補ジョブを投入ジョブとすることを特徴とする並列計算機システム。
【請求項２】
前記実行すべきジョブが前記中断ジョブであり、該中断ジョブの実行環境を前記ローカルディスク上に保存している計算ノードが空き状態の場合は、前記ジョブ管理ノードが、該空き状態の計算ノードに前記中断ジョブを投入する、請求項１に記載の並列計算機システム。
【請求項３】
前記実行すべきジョブが新規ジョブであり、前記中断ジョブの実行環境を前記ローカルディスク上に保存していない計算ノードが空き状態の場合は、前記ジョブ管理ノードが、該空き状態の計算ノードに前記新規ジョブを投入する、請求項１に記載の並列計算機システム。
【請求項４】
前記ジョブ管理ノードは、
前記複数の実行待ちジョブから複数の投入候補ジョブを選択する投入候補ジョブ選択部と、
前記投入候補ジョブ選択部で選択した投入候補ジョブ毎に、投入先となる複数の投入候補ノード群を選択し、該選択した投入候補ノード群毎に、各ノードにおける前記ジョブの実行状況および実行環境の保持状況に基づいて前記投入コストを計算し、該計算した投入コストの最も小さな投入候補ノード群を前記投入先ノードとする投入コスト計算部と、
前記投入候補ジョブ選択部で選択した投入候補ジョブのうち、前記投入先ノードの投入コストが最も小さな投入候補ジョブを前記投入ジョブとする投入ジョブ決定部とを有する、請求項１から３のいずれか１項に記載の並列計算機システム。
【請求項５】
前記投入ジョブ決定部で決定した投入ジョブが前記中断ジョブであり、前記投入ジョブの前記投入先ノードが前記実行環境を保持していない場合に、該投入先ノードに前記ローカルディスクから必要な実行環境を移動するジョブ実行環境移動部をさらに有する、請求項４に記載の並列計算機システム。
【請求項６】
前記投入ジョブ決定部は、前記投入ジョブの前記投入先ノードが他のジョブを実行中である場合は、当該投入ジョブに代えて、前記投入コストが次に低い投入候補ジョブを新たな投入ジョブとして決定する、請求項４に記載の並列計算機システム。
【請求項７】
それぞれが投入されたジョブを実行可能な複数の計算ノードと少なくとも１つのローカルディスクとを有する並列計算機システムにおいて行われるジョブ投入方法であって、
前記ジョブを実行中の計算ノードが該実行中のジョブを中断した場合に、該中断ジョブの実行環境を前記ローカルディスクに保存する第１のステップと、
前記複数の計算ノードのそれぞれについて前記ジョブの実行状況および前記実行環境の保存状況を保持する第２のステップと、
前記複数の計算ノードのいずれかが空き状態になると、予め蓄積された複数の実行待ちジョブから実行すべきジョブとして複数の投入候補ジョブを選択する第３のステップと、
前記第３のステップで選択した投入候補ジョブのそれぞれについて、投入した場合に想定される投入コストが最小となる投入先ノードを、各ノードにおける前記ジョブの実行状況および実行環境の保存状況に基づいて決定する第４のステップと、
前記第４のステップで決定した投入先ノードの投入コストが最も小さな投入候補ジョブを投入ジョブとする第５のステップとを含むジョブ投入方法。
【請求項８】
前記実行すべきジョブが前記中断ジョブであり、該中断ジョブの実行環境を前記ローカルディスク上に保存している計算ノードが空き状態の場合は、該空き状態の計算ノードに前記中断ジョブを投入するステップをさらに含む、請求項７に記載のジョブ投入方法。
【請求項９】
前記実行すべきジョブが新規ジョブであり、前記中断ジョブの実行環境を前記ローカルディスク上に保存していない計算ノードが空き状態の場合は、該空き状態の計算ノードに前記新規ジョブを投入するステップをさらに含む、請求項７に記載のジョブ投入方法。
【請求項１０】
前記第４のステップは、
前記第３のステップで選択した投入候補ジョブ毎に、投入先となる複数の投入候補ノード群を選択するステップと、
前記選択した投入候補ノード群毎に、各ノードにおける前記ジョブの実行状況および実行環境の保持状況に基づいて前記投入コストを計算するステップと、
前記計算した投入コストの最も小さな投入候補ノード群を前記投入先ノードとするステップとを含む、請求項７から９のいずれか１項に記載のジョブ投入方法。
【請求項１１】
前記第５のステップで決定した投入ジョブが前記中断ジョブであり、前記投入ジョブの前記投入先ノードが前記実行環境を保持していない場合に、該投入先ノードに前記ローカルディスクから必要な実行環境を移動するステップをさらに含む、請求項１０に記載のジョブ投入方法。
【請求項１２】
前記第５のステップで決定した投入ジョブの前記投入先ノードが他のジョブを実行中である場合は、当該投入ジョブに代えて、前記投入コストが次に低い投入候補ジョブを新たな投入ジョブとして決定するステップをさらに含む、請求項１０に記載のジョブ投入方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模なジョブを実行する並列計算機システムおよびそのようなシステムにおいて行われるジョブ投入方法に関する。
【背景技術】
【０００２】
それぞれがジョブを実行可能な複数の計算ノードをグループ化したクラスタ構造の並列計算機システムが知られている。特許文献１には、ジョブの割り当て時に、各計算ノード（プロセッサ）について測定された負荷に基づいて評価値を求め、求めた評価値の高い計算ノード順にジョブを投入することで、システム全体のスループットの向上を図ったものが記載されている。
【０００３】
最近では、並列計算機システムの大規模化、具体的には計算ノード数の大規模化および計算ノードのメモリ容量の大規模化が進み、このため、すべての計算ノードが１つのディスクに対してアクセス可能とされる均質なファイルシステムを構成することは、性能とコストの観点から現実的でなくなりつつある。そこで、全ノードがアクセスすることができるグローバルディスクと、特定のノードだけがアクセスすることができるローカルディスクとに階層化したファイルシステムを採用することが一般的となっている。
【０００４】
計算ノードに投入されるジョブには、一回の実行における制限時間（実行制限時間）がある。このようにジョブの実行時間が制限されている場合に、それを越える計算時間を要するジョブを実行すると、そのジョブの実行が途中で中断されることになり、中断したジョブの実行環境を何処に保持する必要がある。上述した階層構造の並列計算機システムでは、通常、ジョブが中断されると、そのジョブの実行環境がグローバルディスクに格納され（退避）、再実行時にはグローバルディスクからそのジョブの実行環境が読み出される（復帰）。計算規模が大きくなる程、退避および復帰にかかる時間の全体の処理時間に占める割合が大きくなる。
【特許文献１】特開平１０−１９８６４０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述した従来の並列計算機システムにおいては、中断されたジョブの実行環境は、どの計算ノードで実行されたかに関係なく、すべてグローバルディスクに格納される。グローバルディスクは、多数の計算ノードによって共有されているので、アクセスの競合が起こり易く、また、中継するネットワークの帯域やディスク自体の読み書き帯域にも制限がある。このため、中断したジョブの実行環境の退避と復帰に時間がかかる、という問題がある。
【０００６】
中断したジョブの実行環境をローカルディスクに退避することで、退避および復帰にかかる時間を短くすることが可能である。しかし、従来は、中断したジョブの再実行は、その実行環境をローカルディスク上で保持している計算ノード（前回ジョブを実行した計算ノード）で行われるようになっており、それ以外の計算ノードを使用した中断ジョブの再実行は考慮されていない。このため、前回ジョブを実行した計算ノードが他のジョブを実行中である場合は、他の計算ノードが空いているにもかかわらず、その計算ノードが空くのを待つこととなり、この待ち時間の分だけ、処理に時間を要することになる。
【０００７】
本発明の目的は、上記問題を解決し、ジョブを効率良く投入することのできる、並列計算機システムおよびジョブ投入方法を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の並列計算機システムは、それぞれが投入されたジョブを実行可能な複数の計算ノードと、前記ジョブを実行中の計算ノードが該実行中のジョブを中断した場合に、該中断ジョブの実行環境が保存される少なくとも１つのローカルディスクと、前記複数の計算ノード毎に前記ジョブの実行状況および前記実行環境の保存状況を保持するとともに、前記複数の計算ノードのいずれかが空き状態になると、予め蓄積された複数の実行待ちジョブから実行すべきジョブを選択して投入する管理ノードとを有し、前記ジョブ管理ノードは、前記実行すべきジョブとして複数の投入候補ジョブを選択し、該選択した投入候補ジョブのそれぞれについて、投入した場合に想定される投入コストが最小となる投入先ノードを、各ノードにおける前記ジョブの実行状況および実行環境の保存状況に基づいて決定し、該決定した投入先ノードの投入コストが最も小さな投入候補ジョブを投入ジョブとするように構成されている。
【０００９】
また、本発明のジョブ投入方法は、それぞれが投入されたジョブを実行可能な複数の計算ノードと少なくとも１つのローカルディスクとを有する並列計算機システムにおいて行われるジョブ投入方法であって、前記ジョブを実行中の計算ノードが該実行中のジョブを中断した場合に、該中断ジョブの実行環境を前記ローカルディスクに保存する第１のステップと、前記複数の計算ノード毎に前記ジョブの実行状況および前記実行環境の保存状況を保持する第２のステップと、前記複数の計算ノードのいずれかが空き状態になると、予め蓄積された複数の実行待ちジョブから実行すべきジョブとして複数の投入候補ジョブを選択する第３のステップと、前記第３のステップで選択した投入候補ジョブのそれぞれについて、投入した場合に想定される投入コストが最小となる投入先ノードを、各ノードにおける前記ジョブの実行状況および実行環境の保存状況に基づいて決定する第４のステップと、前記第４のステップで決定した投入先ノードの投入コストが最も小さな投入候補ジョブを投入ジョブとする第５のステップとを含む。
【００１０】
上述した本発明によれば、各ノードにおけるジョブの実行状況（他のジョブを実行中であるか否か）および実行環境の保存状況（中断ジョブの実行環境保持状況）を考慮したジョブの投入制御により、最小の投入コストでのジョブの投入が可能とされている。具体的には、実行待ちジョブ群から優先順位等により選択された複数の投入候補ジョブのそれぞれについて、投入コストが最小となる投入先ノードが決定される。そして、投入先ノードの投入コストが最も小さな投入候補ジョブが投入ジョブとされる。こうした処理により、全体としてのジョブの投入コストを最小にすることができる。
【００１１】
上記の場合、ジョブの種類を考慮することで、最小の投入コストでのジョブの投入をより確実なもとすることが可能となる。
【００１２】
また、本発明によれば、中断ジョブの実行環境はローカルディスクに保存されることから、グローバルディスクに保存する場合のように、実行環境の退避と復帰に時間がかかる、といった問題も生じない。
【発明の効果】
【００１３】
上述したように、本発明によれば、最小の投入コストでのジョブの投入が可能とされているので、ジョブの実行を効率良く行うことができ、全体でのジョブ処理時間を従来に比べて短くすることができる。
【発明を実施するための最良の形態】
【００１４】
次に、本発明の実施形態について図面を参照して説明する。
【００１５】
図１は、本発明の一実施形態である並列計算機システムの概略構成を示すブロック図である。この並列計算機システムは、ジョブ管理ノード１と、このジョブ管理ノード１にネットワーク２を介して接続された複数の計算ノードクラスタ３と、これら計算ノードクラスタ３がネットワーク４を介して共通に接続されたディスクノード５と、このディスクノード５に接続されたグローバルディスク６とを有する。
【００１６】
各計算ノードクラスタ３の構成は同じである。図１には、便宜上、１つの計算ノードクラスタ３の構成のみが示されている。計算ノードクラスタ３は、ローカルディスク３３が接続されたディスクノード３２と、このディスクノード３２とネットワーク３１を介して接続された複数の計算ノード３−１〜３−ｎとを有する。ネットワーク３１はネットワーク２と接続されている。
【００１７】
各計算ノード３−１〜３−ｎは、それぞれが独立したＣＰＵ・メモリを含むコンピュータシステムよりなり、ジョブ管理ノード１から投入されたジョブ（ジョブ制御文）を実行することができる。また、各計算ノードクラスタ３は、ジョブを中断した場合は、ディスクノード３２へアクセスして、その中断したジョブの実行環境をローカルディスク３３上に保持する。
【００１８】
ディスクノード５およびディスクノード３２はいずれも、ＣＰＵ・メモリを含むコンピュータシステムよりなり、これらノードはネットワーク４を介して互いに通信可能とされている。ディスクノード３２は、各計算ノード３−１〜３−ｎからのローカルディスク３３へのアクセスを受け付けて、ジョブの実行環境のローカルディスク３３上への保存およびその保存した実行環境の読み出しを行う。各計算ノード３−１〜３−ｎからの実行環境は、ローカルディスク３３上に、ディレクトリ別にファイル形式で保存される。グローバルディスク６には、ジョブ実行に必要となる全ての情報が格納される。ディスクノード５は、各計算ノードクラスタ３のディスクノード３２と連携して、グローバルディスク６から必要な情報を読み出して各計算ノードクラスタ３へ提供したり、各計算ノードクラス３におけるジョブ実行結果などをグローバルディスク６へ格納したりする。
【００１９】
ジョブ管理ノード１は、ＣＰＵ・メモリを含むコンピュータシステムよりなり、ネットワーク２、３１を介して各計算ノードクラスタ３の計算ノード３−１〜３−ｎの状態を監視するとともに、ジョブの投入および実行状態の管理を行う。図２に、ジョブ管理ノード１の主要な構成を示す。
【００２０】
図２を参照すると、ジョブ管理ノード１は、処理部１０、ジョブ蓄積部２０、ノード状態テーブル３０および時刻管理部４０からなる。時刻管理部４０は、現在の時刻を取得することのできる時計機能を有し、この機能により取得した現在時刻情報を処理部１０に提供する。
【００２１】
ジョブ蓄積部２０は、本並列計算機システムにおいて実行されるジョブが蓄積される部分であり、新規ジョブや中断されたジョブが実行待ちジョブとして蓄積される。このジョブ蓄積部２０に蓄積されるジョブの情報には、実行モジュール、必要ノード数、優先度、前処理、後処理などの情報に加え、ジョブを識別することのできるジョブ番号（以下、ＪＩＤと記す）、中断時の実行環境のサイズやその保管場所（ローカルディスク３３上のディレクトリ名やファイル名）などの情報が含まれる。実行モジュールは、プログラムの実行モジュールである。前処理および後処理は、予め必要なファイルを転送したり、実行結果が格納されたファイルの統合や転送を行ったりするための処理で、通常、コマンド列で記載される。実行環境サイズは、それらファイル（入出力ファイル）や中間結果のダンプファイルなど実行に必要なファイルの合計サイズである。
【００２２】
ノード状態テーブル３０は、各計算ノード３−１〜３−ｎの状態を示す情報が格納されるテーブルである。計算ノードクラスタ３ごとにノード状態テーブル３０を作成してもよく、また、全クラスタで１つのノード状態テーブル３０を作成してもよい。
【００２３】
図３に、ノード状態テーブル３０の一例を示す。この例では、「ノード番号」、「実行状態」、「実行開始時刻」、「保持ジョブ環境」および「サイズ」の項目があり、それぞれの項目について各計算ノード３−１〜３−ｎの状態が管理される。「ノード番号」は、各計算ノード３−１〜３−ｎを個別に管理するための番号であって、ここでは、シリアル番号としている。「実行状態」は、現在、ジョブを実行しているか否かを示すものである。「実行開始時刻」は、現在実行中のジョブの実行開始時刻である。この実行開始時刻は、時刻管理部４０が提供する現在時刻情報に基づいて設定される。「保持ジョブ環境」は、ジョブの実行を中断してローカルディスク３３上に実行環境を保持した場合に設定される情報であって、中断したジョブの番号（ＪＩＤ）が格納される。「サイズ」は、その中断したジョブの実行環境のサイズ（実行に必要なファイルの合計サイズ）である。
【００２４】
処理部１０は、ジョブ投入制御部１１およびノード状態管理部１２からなる。ノード状態管理部１２は、各計算ノード３−１〜３−ｎの状態を監視し、それぞれの状態に変化があるとノード状態テーブル４０の内容を更新する。この更新は、ジョブの投入時、中断時および終了時、保持ジョブ環境の移動時など、ノード状態テーブル４０の内容に変更が生じる場合に適宜に行われる。例えば、ノード状態管理部１２は、計算ノードにジョブが投入されて実行されると、ノード状態テーブル４０内のその計算ノードに対応するノード番号の欄の「実行状態」欄を「実行中」とするとともに、時刻管理部４０から提供される現在時刻情報に基づいて、そのジョブの実行開始時刻を取得して「実行開始時刻」欄に設定する。計算ノードが実行中のジョブを中断してその実行環境をローカルディスク３３に保存した場合には、ノード状態管理部１２は、その中断したジョブの番号（ＪＩＤ）を「保持ジョブ環境」欄に格納するとともに、その実行環境サイズを「サイズ」欄に格納する。
【００２５】
ジョブ投入制御部１１は、ジョブ蓄積部２０に蓄積された実行待ちジョブの計算ノードへの投入を制御するものである。このジョブ投入制御部１１によるジョブ投入制御では、ノード状態管理部１２による管理結果に基づいて、計算ノード３−１〜３−ｎのいずれかが空き状態となったか否かが判断される。空き状態となったことが検知されると、ジョブ蓄積部２０に蓄積された実行待ちジョブ群から複数の投入候補ジョブが選択され、その選択した投入候補ジョブのそれぞれについて投入コスト計算処理が行われる。投入候補ジョブの選択は、従来の手法と同様で、ジョブに設定されている優先順位や必要ノード数などの情報に基づいて行われる。
【００２６】
投入コスト計算処理では、選択した投入候補ジョブのそれぞれについて、投入コストが最小となる投入先ノードが決定される。そして、その決定した投入先ノードのコストが最も小さな投入候補ジョブが投入ジョブとされる。なお、投入ジョブの投入先ノードが他のジョブを実行中の場合は、投入先ノードのコストが次に小さな投入候補ジョブが投入ジョブとされる。また、投入ジョブが中断ジョブであり、その投入先ノードが実行環境保持ノードでない場合は、ローカルディスク３３上に保存されている必要なジョブ実行環境を投入先ノードへ移動する。このような投入コスト計算処理を行う部分として、ジョブ投入制御部１１は、投入候補ジョブ選択部１１１、投入コスト計算部１１２、投入ジョブ決定部１１３およびジョブ実行環境移動部１１４を備える。
【００２７】
投入候補ジョブ選択部１１１は、ジョブ蓄積部２０に蓄積された実行待ちジョブ群から複数の投入候補ジョブを選択する。選択する投入候補ジョブの数は、設計に応じて適宜決定される。選択する投入候補ジョブの数が多いほど、より投入コストの小さい投入候補ジョブの選択が可能となる。
【００２８】
投入コスト計算部１１２は、投入候補ジョブ選択部１１１で選択された各投入候補ジョブについて投入コストを計算する。この投入コストの計算では、選択された投入候補ジョブ毎に、複数の投入候補ノード群が選択され、その選択された投入候補ノード群のそれぞれについて、各ノードのコストが後述する計算式にしたがって計算される。そして、その計算したコストの最も小さい投入候補ノード群が投入候補ジョブの投入先とされ、そのコストが投入コストとされる。
【００２９】
投入ジョブ決定部１１３は、投入コスト計算部１１２で計算した投入コストが最も小さな投入候補ジョブを投入ジョブとする。ただし、その投入ジョブの投入先ノードが他のジョブを実行している場合には、投入ジョブ決定部１１３は、その投入候補ジョブを候補から外し、残った投入候補ジョブの中で、投入コストが最も小さな投入候補ジョブを投入ジョブとする。これは、投入先ノードが他のジョブを実行している投入候補ジョブについては、他のジョブの実行が終了した後に投入するほうが、より低いコストで投入を行うことができるからである。
【００３０】
ジョブ実行環境移動部１１４は、投入ジョブ決定部１１３で決定された投入ジョブの投入先ノードの中に、実行すべきジョブの実行環境を保持していない計算ノードがある場合に、その計算ノードに、ローカルディスク３３上に保存されている必要なジョブ実行環境を移動する。ジョブ実行環境のローカルディスク３３上のアドレスは、ジョブ投入制御部１１によって保持されており、ジョブ実行環境移動部１１４は、そのアドレスを参照してジョブ実行環境の移動を行う。
【００３１】
次に、投入コストの計算方法について具体的に説明する。図４に、投入コスト計算部１１２にて行われる投入コストの計算例の一例を示す。この例では、ジョブの種類、投入候補ノードの種類および実行状態に基づいて投入コストが計算される。
【００３２】
投入コストは、ジョブ投入コスト、待ちコストおよび移動コスト、の３つのコストに大きく分けられる。ジョブ投入コストは、ジョブを投入するためのコストである。このジョブ投入コストには、新規ジョブ投入コストと中断ジョブ投入コストの２つがあり、それぞれα、βと表す。これらα、βの値によって、新規ジョブと中断ジョブの優先度を制御することができる。
【００３３】
待ちコストは、投入先の計算ノードがジョブを実行中で、その実行ジョブの終了を待つ場合のコストであり、「Ａ・ｔｗ」と表す。ここで、「ｔｗ」は、実行中のジョブの残り時間である。この残り時間「ｔｗ」は、ノード状態テーブル３０に設定された実行開始時刻と時刻管理部４０から取得した現在時刻との差（経過時間）を実行制限時間から差し引くことで求めることができる。実行制限時間は、各ジョブで同じである。「Ａ」は、移動コストの兼ね合いで適当に設定される値である。
【００３４】
移動コストは、ジョブ実行環境を投入先の計算ノードに移動する場合のコストであって、第１および第２の移動コストがある。第１の移動コストは、ジョブの実行のために、投入先の計算ノードにジョブ実行環境を移動する際の移動コストであって、「ｂ・ｓｚ１」と表す。ここで、「ｓｚ１」は投入ジョブのジョブ環境サイズで、「ｂ」はファイル転送速度などから決定される係数である。第２の移動コストは、投入先の計算ノードによってローカルディスク３３上に保持されている別のジョブのジョブ実行環境を将来移動させることになる可能性を考慮した移動コストであって、「γ・ｂ・ｓｚ２」と表す。ここで「ｓｚ２」はその計算ノードで保持している別のジョブの実行環境のサイズで、「γ」は係数である。「γ」の値を適当に設定することで、将来コストが生じる可能性を評価するものである。この係数「γ」は、０〜１までの値をとるようにしても良い。
【００３５】
図４のコスト計算例では、上記のジョブ投入コスト、待ちコストおよび移動コストを用いて次のように計算コストが規定されている。
（１）投入候補ジョブが中断ジョブの場合：
（１−１）投入候補ジョブの実行環境を保持している計算ノードであり、実行状態が「空き」となっている場合は、そのコストを「α」とする。
【００３６】
（１−２）投入候補ジョブの実行環境を保持している計算ノードであり、実行状態が「実行中」となっている場合は、そのコストを「Ａ・ｔｗ＋α」とする。
【００３７】
（１−３）投入候補ジョブの実行環境を保持している計算ノード以外の、他のジョブの実行環境を保持している計算ノードであり、実行状態が「空き」となっている場合は、そのコストを「Ｂ・ｓｚ１＋γ・Ｂｓｚ２＋α」とする。
【００３８】
（１−４）投入候補ジョブの実行環境を保持している計算ノード以外の、他のジョブの実行環境を保持している計算ノードであり、実行状態が「実行中」となっている場合は、そのコストを「Ａ・ｔｗ＋Ｂ・ｓｚ１＋γ・Ｂｓｚ２＋α」とする。
【００３９】
（１−５）いずれのジョブの実行環境も保持していない計算ノードであり、実行状態が「空き」となっている場合は、そのコストを「Ｂ・ｓｚ１＋α」とする。
【００４０】
（１−６）いずれのジョブの実行環境も保持していない計算ノードであり、実行状態が「実行中」となっている場合は、そのコストを「Ａ・ｔｗ＋Ｂ・ｓｚ１＋α」とする。
（２）投入候補ジョブが新規ジョブの場合：
（２−１）いずれかのジョブの実行環境を保持している計算ノードであり、実行状態が「空き」となっている場合は、そのコストを「γ・Ｂ・ｓｚ２＋β」とする。
【００４１】
（２−２）いずれかのジョブの実行環境を保持している計算ノードであり、実行状態が「実行中」となっている場合は、そのコストを「Ａ・ｔｗ＋γ・Ｂ・ｓｚ２＋β」とする。
【００４２】
（２−３）いずれのジョブの実行環境も保持していない計算ノードであり、実行状態が「空き」となっている場合は、そのコストを「β」とする。
【００４３】
（２−４）いずれのジョブの実行環境も保持していない計算ノードであり、実行状態が「実行中」となっている場合は、そのコストを「Ａ・ｔｗ＋β」とする。
【００４４】
以上の計算例にしたがって、投入コスト計算部１１２では、投入候補ジョブ選択部１１１で選択された各投入候補ジョブについて、投入候補ノード群の投入コストが計算される。
【００４５】
次に、本実施形態の並列計算機システムの動作について説明する。
【００４６】
ジョブは、実行待ちジョブ群の中で実行を待つ。ジョブには一回の実行における制限時間（実行制限時間）があり、それを越えるとその実行が中断される。ジョブを中断した場合の実行環境は、そのジョブを実行していた計算ノードによってローカルディスク３３上に保存される。また、ジョブの実行が中断された場合は、その時点での実行環境サイズおよびローカルディスク３３上の保管場所（ディレクトリ名やファイル名など）がジョブ投入制御部１１によって保持される。中断されたジョブは、再び実行待ちジョブ群に戻る。この一連のジョブ実行処理において、ジョブの計算ノードへの投入がジョブ管理ノード１によって制御される。
【００４７】
図５に、ジョブ投入制御部１１によって行われるジョブ投入の一手順を示す。以下、図１〜５を参照して、ジョブ投入手順を説明する。
【００４８】
ノード状態管理部１２による管理結果に基づいて計算ノード３−１〜３−ｎのいずれかの計算ノードが空き状態となったことが検知されると、ジョブ蓄積部２０に格納されている実行待ちジョブ群から複数の投入候補ジョブを選択する（ステップＳ１０）。続いて、最初に選択した投入候補ジョブ（＃Ｊ＝０）について、中断ジョブと新規ジョブのいずれのジョブであるかを判断する（ステップＳ１１）。
【００４９】
ステップＳ１１で「中断ジョブ」と判断した場合は、その中断ジョブの実行環境を保持しているノードが空き状態であるか否かを確認する（ステップＳ１２）。この確認で、「Ｙｅｓ」となった場合は、ジョブの投入を行い（ステップＳ１４）、「Ｎｏ」となった場合は複数の投入候補ノード群を選択する（ステップＳ１５）。
【００５０】
ステップＳ１１で「新規ジョブ」と判断した場合は、実行環境を保持していない空きノードがあるか否かを確認する（ステップＳ１５）。この確認で、「Ｙｅｓ」となった場合は、ステップＳ１４に移行し、「Ｎｏ」となった場合は、ステップＳ１５に移行する。
【００５１】
ステップＳ１５で複数の投入候補ノード群が選択されると、続いて、最初に選択した投入候補ノード群（＃Ｎ＝０）の各ノードのコストを図４に示したコスト計算式により計算し、その積算値を投入コスト（＃Ｃ）とする（ステップＳ１６）。続いて、「＃Ｎ＝０」であるか、または、「＃ＭＩＮＣ＞＃Ｃ」であるかの判断を行う（ステップＳ１７）。「＃ＭＩＮＣ」は、現段階の処理における最小コストを意味する。この段階では、投入候補ノード群（＃Ｎ＝０）に関する処理が行われているので、ステップＳ１７では「Ｙｅｓ」と判断されることになる。
【００５２】
ステップＳ１７の判断で「Ｙｅｓ」となった場合は、ステップＳ１６で求めた投入コスト「＃Ｃ」を現段階の処理における最小コスト「＃ＭＩＮＣ」とし、その投入候補ノード群「＃Ｎ」を投入先ノード「＃ＮＯＤＥ」として設定する（ステップＳ１８）。続いて、投入候補ノード群「＃Ｎ」が最後の投入候補ノード群であるか否かを判断する（ステップＳ１９）。この判断で、「Ｎｏ」となった場合は、次の投入候補ノード群「＃Ｎ＋１」についてステップＳ１６〜Ｓ１８の処理を繰り返す。ステップＳ１７の判断で「Ｎｏ」となった場合は、ステップＳ１９へ移行する。
【００５３】
ステップＳ１９で「Ｙｅｓ」となった場合は、投入候補ジョブ「＃Ｊ」の投入コストおよび投入先ノードをそれぞれ、ステップＳ１８で設定した「＃ＭＩＮＣ」および「＃ＮＯＤＥ」とする（ステップＳ２０）。この処理により、投入候補ジョブ（＃Ｊ＝０）について、最小の投入コストの投入先ノードが決定される。
【００５４】
続いて、投入候補ジョブ「＃Ｊ」が最後の投入候補ジョブであるか否かを判断する（ステップＳ２１）。この段階では、投入候補ジョブ（＃Ｊ＝０）に関する処理が行われているので、ステップＳ２１では「Ｎｏ」と判断され、次の投入候補ジョブ「＃Ｊ＋１」についてステップＳ１１〜Ｓ２０の処理が繰り返される。
【００５５】
ステップＳ２１の判断で「Ｙｅｓ」となった場合は、ステップＳ２２で決定した投入コスト「＃ＭＩＮＣ」が最も小さな投入候補ジョブを投入ジョブとする（ステップＳ２２）。続いて、その投入ジョブの投入先ノード群が他のジョブを実行中であるかどうかを判断する（ステップＳ２３）。この判断で「Ｙｅｓ」となった場合は、投入コスト「＃ＭＩＮＣ」が次に小さな投入候補ジョブを投入ジョブとする（ステップＳ２４）。
【００５６】
ステップＳ２３の判断で「Ｎｏ」となった場合は、続いて、投入ジョブが中断ジョブであるか否かを判断する（ステップＳ２５）。この判断で「Ｙｅｓ」となった場合は、続いて、投入ジョブの投入先ノード群が必要な実行環境を保持しているか否かを判断する（ステップＳ２６）。この判断で「Ｎｏ」となった場合は、ローカルディスク３３から必要な実行環境を投入先ノード群に移動し（ステップＳ２７）、その後、ステップＳ１４にてジョブの投入を行う。ステップＳ２５の判断で「Ｎｏ」となった場合、または、ステップＳ２６の判断で「Ｙｅｓ」となった場合は、ステップＳ１４に移行する。
【００５７】
上述の投入制御の手順において、ステップＳ１６での投入コストの計算では、投入候補ノード群に含まれる全てのノードのコストを計算するようになっているが、これに代えて、投入候補ノード群の内、クラスタの先頭ノード（ノード状態テーブル３０のノード番号の数字が最も小さい番号のノード）に当たるノードについてコストを計算するようにしてもよい。
【００５８】
以上説明した本実施形態の並列計算機システムによれば、ノードの実行状態（他のジョブを実行中であるか否か）およびジョブの実行環境保持状況を考慮したジョブの投入制御により、最小の投入コストでのジョブの投入が可能とされているので、ジョブの実行を効率良く行うことができ、全体でのジョブ処理時間も従来に比べて短くなる。
【００５９】
また、中断ジョブは、できるだけ実行環境保持ノードに投入するようになっているので、退避や復帰に要する時間を従来に比較して短くすることができる。
【００６０】
さらに、中断ジョブを投入する場合で、投入先のノードに実行環境が保持されていない場合は、その投入先のノードに対して実行環境を移動した上でジョブの投入が行われるので、中断ジョブの再起動ができない、といった不具合が発生することがなく、安定したジョブ実行動作を提供することができる。
【００６１】
さらに、投入先のノードが他のジョブを実行中である場合の待ちコストや実行環境を移動する場合の移動コストも考慮して投入ノードおよび投入ジョブを決定するようになっているので、待ち時間を最小限にすることができる。
【００６２】
さらに、ジョブを投入する際に、ノードに保存されている実行環境に関して将来移動するコストを見込んで投入ノードが決定される。このように将来発生する移動コストを考慮したジョブの投入が可能であるので、待ち時間をより短くすることが可能である。
【００６３】
以上説明した本実施形態の並列計算システムは、一例であって、その構成及び動作は、発明の趣旨を逸脱しない範囲で、適宜に変更可能である。例えば、図６に示した投入コスト計算処理では、複数の投入候補ジョブを選択するようになっているが、選択する投入候補ジョブの数は１つであってもよい。この場合は、選択した投入候補ジョブについて、投入した場合に想定される投入コストが最小となる投入先ノードが決定される。そして、その選択した投入候補ジョブが投入ジョブとされる。なお、選択する投入候補ジョブの数が多いほど、より投入コストの小さい投入候補ジョブの選択が可能である。
【図面の簡単な説明】
【００６４】
【図１】本発明の一実施形態である並列計算機システムの概略構成を示すブロック図である。
【図２】図１に示す並列計算機システムのジョブ管理ノードの主要な構成を示すブロック図である。
【図３】図１に示す並列計算機システムにおいて用いられるノード状態テーブルの一例を示す図である。
【図４】図１に示す並列計算機システムにおいて行われる投入コストの計算例を示す図である。
【図５】ジョブ投入の一手順を示すフローチャートである。
【符号の説明】
【００６５】
１  ジョブ管理ノード
２、４、３１  ネットワーク
３  計算ノードクラスタ
５、３２  ディスクノード
６  グローバルディスク
３−１〜３−ｎ  計算ノード
３３  ローカルディスク
１０  処理部
１１  ジョブ投入制御部
１２  ノード状態管理部
１１１  投入候補ジョブ選択部
１１２  投入コスト計算部
１１３  投入ジョブ決定部
１１４  ジョブ実行環境移動部
２０  ジョブ蓄積部
３０  ノード状態テーブル
４０  時刻管理部
【図１】
2006065658.tif 000003
【図２】
2006065658.tif 000004
【図３】
2006065658.tif 000005
【図４】
2006065658.tif 000006
【図５】
2006065658.tif 000007