(57)【要約】      （修正有）【課題】ジョブを実行する複数の情報処理装置における負荷の平準化を向上させる。【解決手段】並列計算機システム１０は、複数の情報処理装置２１〜２Ｎと、複数の情報処理装置を制御する管理装置１とを有する。情報処理装置の各々は、自装置が実行するジョブに対し、自装置の資源ごとの資源使用量の変動を所定の時間単位で出力する出力部２１３〜２Ｎ３を備える。管理装置は、ジョブの実行ごとに、実行対象のジョブの属性及び各情報処理装置の出力部が出力する資源使用量の変動を含む実行履歴を生成する生成部１３１と、新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、新規ジョブの資源使用量を推定する推定部１３３と、推定された資源使用量に基づいて、新規ジョブを割り当てる情報処理装置を特定する特定部１３４とを備える。【選択図】図２
2016042284.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報処理装置と、前記複数の情報処理装置を制御する管理装置とを有する並列計算機システムにおいて、
前記複数の情報処理装置の各々は、
自装置が実行するジョブに対し、自装置の資源ごとの資源使用量の変動を所定の時間単位で出力する出力部を備え、
前記管理装置は、
ジョブの実行ごとに、実行対象の前記ジョブの属性及び各情報処理装置の出力部が出力する資源使用量の変動を含む実行履歴を生成する生成部と、
新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定する推定部と、
推定された前記資源使用量に基づいて、前記新規ジョブを割り当てる情報処理装置を特定する特定部とを備える、
並列計算機システム。
【請求項２】
前記管理装置は、
生成された実行履歴を、属性及び資源使用量の変動における所定の類似度に基づいて、複数のグループに分類する分類部をさらに備え、
前記推定部は、前記類似ジョブの実行履歴を含むグループの資源使用量の変動を回帰分析により推定し、推定された前記資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定する、
請求項１に記載の並列計算機システム。
【請求項３】
前記推定部は、前記類似ジョブの実行履歴を含むグループが複数存在する場合、各グループに含まれる前記類似ジョブの実行履歴の数に基づいて、各グループへの所属確率を算出し、前記各グループの資源使用量の変動及び前記所属確率に基づいて、前記新規ジョブの資源使用量を推定する、
請求項１又は２に記載の並列計算機システム。
【請求項４】
前記資源使用量の変動は、周波数成分として実行履歴に含まれる、
請求項１から３のいずれか一項に記載の並列計算機システム。
【請求項５】
前記類似ジョブは、前記類似ジョブの属性の属性値と前記新規ジョブの属性の属性値とを成分として算出されるユークリッド距離が所定の閾値より小さいジョブである、
請求項１から４のいずれか一項に記載の並列計算機システム。
【請求項６】
前記ユークリッド距離は、成分ごとに異なる重みづけの係数を乗じて求められる、
請求項５に記載の並列計算機システム。
【請求項７】
前記特定部は、前記複数の情報処理装置から選択される一以上の情報処理装置の組合せを割当て位置候補とし、複数の割当て位置候補の中から、割当て位置候補に含まれる各情報処理装置における前記新規ジョブ及び既存のジョブの資源使用量の推定値の合計が、他の割当て位置候補よりも小さい割当て位置候補を、前記新規ジョブを割り当てる情報処理装置として特定する、
請求項１から６のいずれか一項に記載の並列計算機システム。
【請求項８】
前記複数の情報処理装置は、ジョブの演算処理を実行する演算ノードと、前記ジョブに対する入出力処理を実行する入出力ノードとを含み、
資源使用量の一つとして、前記演算ノードと前記入出力ノードとの間のネットワーク資
源の使用量を含む、
請求項１から７のいずれか一項に記載の並列計算機システム。
【請求項９】
複数の情報処理装置と、前記複数の情報処理装置を制御する管理装置とを有する並列計算機システムの制御方法において、
前記複数の情報処理装置の各々有する出力部が、自装置が実行するジョブに対し、自装置の資源ごとの資源使用量の変動を所定の時間単位で出力し、
前記管理装置が有する生成部が、ジョブの実行ごとに、実行対象の前記ジョブの属性及び各情報処理装置が出力する資源使用量の変動を含む実行履歴を生成し、
前記管理装置が有する推定部が、新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定し、
前記管理装置が有する特定部が、推定された前記資源使用量に基づいて、前記新規ジョブを割り当てる情報処理装置を特定する、
並列計算機システムの制御方法。
【請求項１０】
複数の情報処理装置を制御する管理装置において、
前記複数の情報処理装置の各々が実行するジョブの実行ごとに、実行対象の前記ジョブの属性及び各情報処理装置が出力する資源使用量の変動を含む実行履歴を生成する生成部と、
新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定する推定部と、
推定された前記資源使用量に基づいて、前記新規ジョブを割り当てる情報処理装置を特定する特定部と、
を備える管理装置。
【請求項１１】
複数の情報処理装置を制御する管理装置の制御プログラムにおいて、
前記管理装置が有する生成部に、前記複数の情報処理装置の各々が実行するジョブの実行ごとに、実行対象の前記ジョブの属性及び各情報処理装置が出力する資源使用量の変動を含む実行履歴を生成させ、
前記管理装置が有する推定部に、新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定させ、
前記管理装置が有する特定部に、推定された前記資源使用量に基づいて、前記新規ジョブを割り当てる情報処理装置を特定させる、
管理装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算機システム、管理装置、並列計算機システムの制御方法及び管理装置の制御プログラムに関する。
【背景技術】
【０００２】
並列計算機システムは、複数のプロセッサに処理（以下、ジョブともいう）を分散して割り当て、複数のプロセッサが割り当てられたジョブを並列して実行することで、システム全体の処理性能を向上させる。並列計算機システムで実行されるジョブは、負荷が分散されるように実行スケジュールを調整して、各プロセッサに割り当てられる。ジョブの実行スケジュールを調整する方法の一つに、ジョブの実行履歴に基づくスケジューリングがある。
【０００３】
ジョブの実行履歴に基づくスケジューリングでは、新規に投入されたジョブの類似ジョブが、実行履歴から検出される。実行履歴は、例えば、プロセッサの使用時間、メモリの使用量、使用ノード数等の実行条件を含む。検出された類似ジョブの実行履歴に基づいて、新たに投入される新規ジョブの実行条件を予測し、負荷が分散されるようにジョブの実行スケジュールが調整される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平０５−３１３９２１号公報
【特許文献２】特開２００５−１４８９０１号公報
【特許文献３】特開平０８−１５２９０３号公報
【特許文献４】国際公開第２０１１／１０２２１９号
【特許文献５】特表２００７−５１９１０３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ジョブの実行履歴に基づくスケジューリングにおいて、適切な類似ジョブの実行条件を得られない場合がある。例えば、同一の並列プログラムは、毎回、同じ並列度で実行されるとは限らない。即ち、同一のプログラムを実行する複数のジョブは、同一の実行条件を有しない場合があり得る。このとき、適切な類似ジョブの実行条件は得られない。
【０００６】
また、近年、プロセッサの並列化手段が多様化している。並列計算機システム内の一部ノードに、General-Purpose computing on Graphics Processing Units（ＧＰＧＰＵ）又はField Programmable Gate Array（ＦＰＧＡ）等のアクセラレータが配置される場合が
ある。一部のノードがアクセラレータを搭載するような、異種のプロセッサが混在するヘテロジニアスなシステム構成では、ジョブ名、使用ノード数等が同じでも、実行条件が異なる場合があり得る。このとき、適切な類似ジョブの実行条件は得られない。
【０００７】
さらに、並列計算機システムは、一部のノードのCentral Processing Unit（ＣＰＵ）
がアップグレードされたり、次世代のＣＰＵを搭載するノード群が増設されたりすることで、ヘテロジニアスなシステム構成となる。このとき、環境の差を考慮した適切な類似ジョブの実行条件は得られない。
【０００８】
適切な類似ジョブの実行条件が得られない場合、新規ジョブの実行条件の推定ができないため、スケジューリングによって、ジョブを実行する複数の情報処理装置における負荷の平準化が図れない。
【０００９】
開示の実施形態の一態様は、ジョブを実行する複数の情報処理装置における負荷の平準化を向上させることができる並列計算機システム、管理装置、並列計算機システムの制御方法及び管理装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
開示の実施形態の態様の一つは、並列計算機システムによって例示される。本並列計算機システムは、
複数の情報処理装置と、前記複数の情報処理装置を制御する管理装置とを有する並列計算機システムにおいて、
前記複数の情報処理装置の各々は、
自装置が実行するジョブに対し、自装置の資源ごとの資源使用量の変動を所定の時間単位で出力する出力部を備え、
前記管理装置は、
ジョブの実行ごとに、実行対象の前記ジョブの属性及び各情報処理装置の出力部が出力する資源使用量の変動を含む実行履歴を生成する生成部と、
新たに投入された新規ジョブと属性が類似する類似ジョブの実行履歴に含まれる資源使用量の変動に基づいて、前記新規ジョブの資源使用量を推定する推定部と、
推定された前記資源使用量に基づいて、前記新規ジョブを割り当てる情報処理装置を特定する特定部とを備える。
【発明の効果】
【００１１】
開示の並列計算機システム、管理装置、並列計算機システムの制御方法及び管理装置の制御プログラムによれば、ジョブを実行する複数の情報処理装置における負荷の平準化を向上させることができる。
【図面の簡単な説明】
【００１２】
【図１】並列計算機システムのシステム構成の一例を示す図である。
【図２】並列計算機システムにおける各ノード及びサーバの処理構成の一例を示す図である。
【図３】資源使用変動のデータ構造の一例を示す図である。
【図４】実行履歴のデータ構造の一例を示す図である。
【図５Ａ】入力パラメタのデータ構造の一例を示す図である。
【図５Ｂ】プログラムレコードのデータ構造の一例を示す図である。
【図５Ｃ】使用者レコードのデータ構造の一例を示す図である。
【図５Ｄ】ジョブ資源指定レコードのデータ構造の一例を示す図である。
【図６】専有資源レコードのデータ構造の一例を示す図である。
【図７】資源使用変動レコードのデータ構造の一例を示す図である。
【図８】資源使用量の変動を記録する処理のフローチャートの一例である。
【図９】ジョブの実行終了後に実行履歴を登録する処理のフローチャートの一例である。
【図１０】実行履歴のクラスタ分析処理のフローチャートの一例である。
【図１１】クラスタ間の非類似度を求める処理のフローチャートの一例である。
【図１２】新規ジョブの資源使用量の推定値を求める処理のフローチャートの一例である。
【図１３】新規ジョブが使用する資源の割当て位置を最適化する処理のフローチャートの一例である。
【発明を実施するための形態】
【００１３】
以下、図面に基づいて、本発明の実施の形態を説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１４】
＜第１実施形態＞
第１実施形態では、並列計算機システムは、実行するジョブの資源使用量の変動を単位時間ごとに記録し、実行履歴を生成する。新たに投入されたジョブ（以下、新規ジョブともいう）に対し、並列計算機システムは、新規ジョブと所定の類似性を有する既存のジョブ（以下、類似ジョブともいう）の実行履歴に基づいて、新規ジョブの資源使用量を推定する。
【００１５】
ジョブの実行履歴は、クラスタ分析により複数のクラスタに分類してもよい。この場合、各クラスタの資源使用量は、クラスタ内の実行履歴に基づき、例えば、回帰分析によって推定することができる。新規ジョブの資源使用量は、類似ジョブを含むクラスタの資源使用量に基づいて推定してもよい。
【００１６】
＜システム構成＞
図１は、並列計算機システム１０のシステム構成の一例を示す図である。並列計算機システム１０は、ジョブスケジューラ・ノード１、計算ノード２１から２Ｎで例示される計算ノード群、Input / Output（ＩＯ）ノード３１から３Ｎで例示されるＩＯノード群を含み、各ノードは相互に接続される。なお、ネットワーク・トポロジーは、図１の構成に限定されず、Ｎ次元メッシュ、Ｎ次元トーラス、Ｆａｔ  Ｔｒｅｅ又はこれらの組み合わせであってもよい。
【００１７】
並列計算機システム１０において、計算ノードの数及びＩＯノードの数は、限定されない。並列計算機システム１０内で相互に接続される計算ノードは、計算ノード２と総称される。また、並列計算機システム１０内で相互に接続されるＩＯノードは、ＩＯノード３と総称される。
【００１８】
ジョブスケジューラ・ノード１は、ジョブの資源使用状況を管理し、各ジョブに資源を割り当てる。図１において、ジョブスケジューラ・ノード１は、Central Processing Unit（ＣＰＵ）１ａ、メモリ１ｂ、Network Interface Card（ＮＩＣ）１ｃを備える。なお
、ジョブスケジューラ・ノード１の具体的な装置構成は、図１に示されるものに限定されず、適宜、追加、置換、削除等の変更が可能である。
【００１９】
ＣＰＵ  １ａは、メモリ１ｂ上に実行可能に展開されたコンピュータプログラムを実行することによって、様々な処理を実行する。ＣＰＵ  １ａは、１つに限られず、複数備えられてもよい。
【００２０】
メモリ１ｂは、ＣＰＵ  １ａに、プログラムをロードするための記憶領域、及びプログラムを実行するための作業領域を提供する。メモリ１ｂは、データを一時的に保持するためのバッファとして用いられる。また、メモリ１ｂは、様々なプログラムや、各プログラムの実行に際してＣＰＵ  １ａが使用するデータを格納する。メモリ１ｂは、例えば、揮発性のRandom Access Memory（ＲＡＭ）、不揮発性のRead Only Memory（ＲＯＭ）等の半導体メモリである。
【００２１】
ＮＩＣ  １ｃは、ネットワークと情報を入出力するためのインターフェースである。ＮＩＣ  １ｃは、有線のネットワーク、又は無線のネットワークと接続する。ＮＩＣ  １ｃを介して受信されたデータ等は、メモリ１ｂに格納される。
【００２２】
計算ノード２は、ジョブスケジューラ・ノード１によって割り当てられたジョブを実行し、ジョブの実行による資源使用量の変動量を単位時間ごとに資源使用変動として記録する。資源使用変動は、資源ごとに記録され、管理される。資源は、例えば、ＣＰＵ時間、ワーキングセットサイズ、仮想空間サイズ、単位時間ごとのメモリアクセス量（即ち、キャッシュミス発生量）、Input/Output Per Second（ＩＯＰＳ）、ＩＯバンド幅である。
また、計算ノード２のＣＰＵ  ２ａが、複数のプロセッサコアを含むマルチプロセッサ等である場合、資源使用変動は、コアごとに記録される。
【００２３】
図１において、計算ノード２１は、ＣＰＵ  ２１ａ、メモリ２１ｂ、ＮＩＣ  ２１ｃを備える。計算ノード２２は、ＣＰＵ  ２２ａ、メモリ２２ｂ、ＮＩＣ  ２２ｃを備える。計算ノード２Ｎは、ＣＰＵ  ２Ｎａ、メモリ２Ｎｂ、ＮＩＣ  ２Ｎｃを備える。なお、計算ノード２の具体的な装置構成は、図１に示されるものに限定されず、適宜、追加、置換、削除等の変更が可能である。
【００２４】
各計算ノード２が備えるＣＰＵ  ２１ａから２Ｎａは、ＣＰＵ  ２ａと総称される。各計算ノードが備えるメモリ２１ｂから２Ｎｂは、メモリ２ｂと総称される。各計算ノードが備えるＮＩＣ  ２１ｃから２Ｎｃは、ＮＩＣ  ２ｃと総称される。計算ノード２１と同様に、各計算ノード２は、それぞれにＣＰＵ  ２ａ、メモリ２ｂ、ＮＩＣ  ２ｃを備える。
【００２５】
ＣＰＵ  ２ａは、メモリ２ｂ上に実行可能に展開されたコンピュータプログラムを実行することによって、様々な処理を実行する。ＣＰＵ  ２ａは、１つに限られず、複数備えられてもよい。また、ＣＰＵ  ２ａは、複数のプロセッサコアを搭載したマルチコアプロセッサでもよい。さらに、ＣＰＵ  ２ａは、General-Purpose computing on Graphics Processing Units（ＧＰＧＰＵ）、Field Programmable Gate Array（ＦＰＧＡ）等のアク
セラレータとしてもよい。アクセラレータは、複数のプロセッサコアを含むものであってもよい。ＣＰＵ  ２ａがマルチコアプロセッサである場合、ＣＰＵ  ２ａに含まれる各プロセッサコアを、以下、コアともいう。
【００２６】
メモリ２ｂは、ＣＰＵ  ２ａに、プログラムをロードするための記憶領域、及びプログラムを実行するための作業領域を提供する。メモリ２ｂは、データを一時的に保持するためのバッファとして用いられる。また、メモリ２ｂは、様々なプログラムや、各プログラムの実行に際してＣＰＵ  ２ａが使用するデータを格納する。メモリ２ｂは、例えば、揮発性のRandom Access Memory（ＲＡＭ）、不揮発性のRead Only Memory（ＲＯＭ）等の半導体メモリである。
【００２７】
ＮＩＣ  ２ｃは、ネットワークと情報を入出力するためのインターフェースである。ＮＩＣ  ２ｃは、有線のネットワーク、又は無線のネットワークと接続する。メモリ２ｂに記録されたデータ等は、ＮＩＣ  ２ｃを介してネットワークに送信される。
【００２８】
ＩＯノード３は、ジョブの実行に使用するデータを保持する。計算ノード２は、ネットワーク経由でＩＯノード３にアクセスするため、ジョブの実行時にはネットワーク資源が使用される。図１において、ＩＯノード３１は、ＣＰＵ  ３１ａ、メモリ３１ｂ、ＮＩＣ
３１ｃを備える。ＩＯノード３２は、ＣＰＵ  ３２ａ、メモリ３２ｂ、ＮＩＣ  ３２ｃを備える。ＩＯノード３Ｎは、ＣＰＵ  ３Ｎａ、メモリ３Ｎｂ、ＮＩＣ  ３Ｎｃを備える。なお、ＩＯノード３の具体的な装置構成は、図１に示されるものに限定されず、適宜、追加、置換、削除等の変更が可能である。
【００２９】
各ＩＯノードが備えるＣＰＵは、ＣＰＵ  ３ａと総称される。各ＩＯノードが備えるメ
モリは、メモリ３ｂと総称される。各ＩＯノードが備えるＮＩＣは、ＮＩＣ  ３ｃと総称される。ＩＯノード３１と同様に、各ＩＯノード３は、それぞれにＣＰＵ  ３ａ、メモリ３ｂ、ＮＩＣ  ３ｃを備える。
【００３０】
ＣＰＵ  ３ａは、メモリ１ｂ上に実行可能に展開されたコンピュータプログラムを実行することによって、様々な処理を実行する。ＣＰＵ  ３ａは、１つに限られず、複数備えられてもよい。
【００３１】
メモリ３ｂは、ＣＰＵ  ３ａに、プログラムをロードするための記憶領域、及びプログラムを実行するための作業領域を提供する。メモリ３ｂは、データを一時的に保持するためのバッファとして用いられる。また、メモリ３ｂは、様々なプログラムや、各プログラムの実行に際してＣＰＵ  ３ａが使用するデータを格納する。メモリ３ｂは、例えば、揮発性のRandom Access Memory（ＲＡＭ）、不揮発性のRead Only Memory（ＲＯＭ）等の半導体メモリである。メモリ３ｂは、例えば、ジョブの実行に使用されるデータを格納する。
【００３２】
ＮＩＣ  ３ｃは、ネットワークと情報を入出力するためのインターフェースである。ＮＩＣ  ３ｃは、有線のネットワーク、又は無線のネットワークと接続する。メモリ３ｂに記録されたデータ等は、ＮＩＣ  ３ｃを介して計算ノード２に送信され、ジョブの実行に使用される。
【００３３】
＜処理構成＞
図２は、並列計算機システム１０の処理構成の例を示し、図３から図７は、各処理構成において使用されるデータのデータ構造の例を示す。
【００３４】
図２は、並列計算機システム１０における各ノード及びサーバの処理構成の一例を示す図である。図２において、並列計算機システム１０は、ジョブスケジューラ・ノード１、計算ノード２（２１から２Ｎ）、database（ＤＢ）サーバ４を含む。
【００３５】
ジョブスケジューラ・ノード１は、スケジューラ（マスター）として、ジョブの実行スケジュールを調整する。ジョブスケジューラ・ノード１は、通信処理部１１、資源割当処理部１２、最適化処理部１３を備える。ＣＰＵ  １ａは、コンピュータプログラムにより、ジョブスケジューラ・ノード１が備える各処理構成の処理を実行する。ジョブスケジューラ・ノード１が備える各処理構成のいずれか、またはその処理の一部がハードウェア回路により実行されてもよい。
【００３６】
通信処理部１１は、計算ノード２との通信処理を制御する。資源割当処理部１２は、通信処理部１１を介して、計算ノード２からデータを受信したり、計算ノード２にジョブの実行を指示したりする。通信処理部１１及び資源割当処理部１２は、制御部の一例である。
【００３７】
資源割当処理部１２は、資源使用状況を管理し、ジョブに対して資源を割り当て、計算ノード２にジョブの実行開始を指示する。資源割当処理部１２は、ジョブ実行開始指示部/終了監視部１２１、資源使用状況管理部１２２、資源使用履歴データ受信部１２３、最
適化処理呼出インターフェース１２４を備える。
【００３８】
ジョブ実行開始指示部/終了監視部１２１は、ジョブを割り当てた計算ノード２に対し
、ジョブの実行開始を指示する。また、ジョブ実行開始指示部/終了監視部１２１は、ジ
ョブの実行を監視し、ジョブの終了を検知する。
【００３９】
資源使用状況管理部１２２は、計算ノード２の各資源の使用状況を管理し、資源使用状況に応じて、ジョブに割り当てる計算ノード２の割当て位置の候補（以下、割当て位置候補ともいう）を、最適化処理部１３に通知する。ここで、割当て位置とは、並列計算機システム１０において、ジョブに割り当てる一の計算ノード２、又は複数の計算ノード２の組み合わせを意味する。
【００４０】
資源使用履歴データ受信部１２３は、通信処理部１１を介して、計算ノード２から、ジョブの実行による資源使用の変動量を資源ごとに記録した資源使用変動データを受信する。資源使用履歴データ受信部１２３は、例えば、ジョブ実行開始指示部/終了監視部１２
１が検知したジョブの終了時に、資源使用変動データを受信することができる。
【００４１】
さらに、資源使用履歴データ受信部１２３は、受信した資源使用変動データから、ジョブごとに実行履歴を生成する。生成された実行履歴は、ＤＢサーバ４に記憶される。資源使用履歴データ受信部１２３は、生成部の一例である。
【００４２】
最適化処理呼出インターフェース１２４は、最適化処理部１３で実行する処理を呼び出すためのインターフェースである。最適化処理部１３で実行する処理は、実行履歴から新規ジョブの資源使用の変動量を推定するための処理を含む。
【００４３】
最適化処理部１３は、実行履歴を複数のグループに分類し、新規ジョブが属するグループに含まれる実行履歴から、新規ジョブの資源使用の変動を推定することで、新規ジョブの割当て位置を最適化する。最適化処理部１３は、実行履歴クラスタ作成部１３１、新規ジョブ所属クラスタ推定部１３２、資源使用変動パターン推定部１３３、専有資源特定部１３４、ＤＢインターフェース１３５を備える。
【００４４】
実行履歴クラスタ作成部１３１は、実行履歴を複数のグループに分類する。例えば、実行履歴クラスタ作成部１３１は、最短距離法、メディアン法等のクラスタリング手法により、１つの「最上位」クラスタに統合される「ツリー」を形成する「階層化クラスタ」を作成することで、実行履歴を複数のクラスタに分類することができる。各クラスタは、一以上の実行履歴を含む。同一のクラスタに含まれる実行履歴は、相互に所定の類似度を有する。実行履歴クラスタ作成部１３１は、分類部の一例である。
【００４５】
新規ジョブ所属クラスタ推定部１３２は、新規ジョブが、実行履歴クラスタ作成部１３１により作成されたクラスタのうち、どのクラスタに所属するかを推定する。新規ジョブ所属クラスタ推定部１３２は、ジョブの属性が類似する類似ジョブの実行履歴を含むクラスタを、新規ジョブの所属するクラスタとして推定する。ジョブの属性は、例えば、プログラム名、使用されるロードモジュール、ライブラリ関数のバイナリハッシュ値、使用者、使用者が所属するグループ、実行予定時間である。
【００４６】
資源使用変動パターン推定部１３３は、新規ジョブが所属するクラスタに含まれる類似ジョブの実行履歴に基づいて、新規ジョブの資源使用変動パターンを推定する。資源使用変動パターンは、具体的には例えば、資源使用変動の周波数成分である。資源使用変動パターン推定部１３３は、クラスタ内の実行履歴の回帰分析により、新規ジョブの資源使用変動パターンを推定することができる。類似ジョブの実行履歴が複数のクラスタに含まれる場合、資源使用変動パターン推定部１３３は、各クラスタに含まれる類似ジョブの実行履歴の数に応じた所属確率を考慮して、新規ジョブの資源使用変動パターンを推定してもよい。資源使用変動パターン推定部１３３は、推定部の一例である。
【００４７】
専有資源特定部１３４は、推定された新規ジョブの資源使用変動パターンに基づいて、新規ジョブを割り当てる資源を特定する。ＤＢインターフェース１３５は、ＤＢサーバ４
とのインターフェースである。最適化処理部１３は、ＤＢインターフェース１３５を介して、新規ジョブの資源使用変動パターンの推定に使用するデータを、ＤＢサーバ４から取得する。専有資源特定部１３４は、は特定部の一例である。
【００４８】
計算ノード２は、スケジューラ（サブ）として、ジョブスケジューラ・ノード１から割り当てられたジョブを実行し、各計算ノード２上の資源使用変動を、所定の単位時間ごとに記録する。計算ノード２は、例えば、１秒ごとに自身の計算ノード２上での資源使用変動を記録する。ＣＰＵ  ２ａがマルチコアプロセッサ等である場合、資源使用変動は、コアごとに記録される。
【００４９】
図２において、計算ノード２１は、ジョブ起動/終了管理部２１１、ジョブ資源使用量
監視部２１２、資源使用状況通知部２１３を備える。計算ノード２２は、ジョブ起動/終
了管理部２２１、ジョブ資源使用量監視部２２２、資源使用状況通知部２２３を備える。計算ノード２Ｎは、ジョブ起動/終了管理部２Ｎ１、ジョブ資源使用量監視部２Ｎ２、資
源使用状況通知部２Ｎ３を備える。
【００５０】
各計算ノード２が備えるジョブ起動/終了管理部２１１から２Ｎ１は、ジョブ起動/終了管理部２１と総称される。各計算ノード２が備えるジョブ資源使用量監視部２１２から２Ｎ２は、ジョブ資源使用量監視部２２と総称される。各計算ノード２が備える資源使用状況通知部２１３から２Ｎ３は、資源使用状況通知部２３と総称される。計算ノード２１と同様に、各計算ノード２は、それぞれにジョブ起動/終了管理部２１、ジョブ資源使用量
監視部２２、資源使用状況通知部２３を備える。
【００５１】
ＣＰＵ  ２ａは、コンピュータプログラムにより、計算ノード２が備える各処理構成の処理を実行する。計算ノード２が備える各処理構成のいずれか、またはその処理の一部がハードウェア回路により実行されてもよい。
【００５２】
ジョブ起動/終了管理部２１は、ジョブ実行開始指示部/終了監視部１２１からの指示を受けてジョブを起動する。また、ジョブ起動/終了管理部２１は、ジョブ実行開始指示部/終了監視部１２１にジョブの終了を通知する。
【００５３】
ジョブ資源使用量監視部２２は、ジョブの資源使用量を監視し、各ジョブの時間の経過に伴って、各ノード上での資源使用変動を所定の単位時間ごとに記録する。資源使用変動は、資源別に記録してもよい。ジョブ資源使用量監視部２２は、資源使用変動を、資源使用履歴としてメモリ２ｂに記憶することができる。ジョブ資源使用量監視部２２は、出力部の一例である。資源使用状況通知部２３は、ジョブ資源使用量監視部２２が記録した資源使用変動データを、資源使用履歴データ受信部１２３に通知する。
【００５４】
ＤＢサーバ４は、資源使用履歴データ受信部１２３が生成したジョブの実行履歴を記憶する。ＤＢサーバ４は、実行履歴データベース４１を備える。実行履歴データベース４１は、入力パラメタ−実行時間−サブレコード表４１１、専有資源表４１２、資源使用変動表４１３を含む。
【００５５】
入力パラメタ−実行時間−サブレコード表４１１は、ジョブの実行履歴を記憶するメインテーブルである。専有資源表４１２は、ジョブの実行に使用した専有資源を記憶する。専有資源は、ジョブが使用する装置、例えば、ＣＰＵ  ２ａ、ＣＰＵ  ２ａのコア、メモリ２ｂ、メモリ内の特定領域等である。
【００５６】
資源使用変動表４１３は、各計算ノード２上又は各コア上での、資源ごとの資源使用変動を周波数成分に分解して、周波数成分ごとに記憶する。資源使用変動は、例えば、離散
フーリエ変換により、周波数成分に分解される。ここで、離散フーリエ変換は、離散コサイン変換や離散サイン変換を含む広義の離散フーリエ変換である。
【００５７】
図３は、資源使用履歴のデータ構造の一例を示す図である。資源使用履歴は、計算ノード２のジョブ資源使用量監視部２２によって記録される資源使用変動である。図３において、資源使用履歴は、「タイムスタンプ」及び「資源使用量の差分」を記憶する。「タイムスタンプ」は、資源使用量の差分を記録する時刻である。「資源使用量の差分」は、直前のタイムスタンプからの資源使用量の変動量である。図３の例では、資源使用履歴は、資源ごとに記録されるものとする。
【００５８】
図４は、実行履歴のデータ構造の一例を示す図である。実行履歴は、入力パラメタ−実行時間−サブレコード表４１１として、実行履歴データベース４１に記憶される。入力パラメタ−実行時間−サブレコード表４１１は、「入力パラメタ」、「実行時間」、「専有資源レコードリスト」、「専有資源変動レコードリスト」を記憶する。「入力パラメタ」は、ジョブの実行前に指定されるパラメタのデータである。「実行時間」、「専有資源レコードリスト」、「専有資源変動レコードリスト」は、ジョブの実行後に、実行結果として登録されるデータである。
【００５９】
「入力パラメタ」は、オペレーティングシステム（Operating System、ＯＳ）、ジョブスケジューラ、又は言語処理系のランタイムシステムによる管理対象としての特徴を示すデータを含む。例えば、「入力パラメタ」は、プログラム名、プログラムのバイナリハッシュ値、使用するロードモジュールやライブラリ関数のバイナリハッシュ値、使用者、使用者が所属するグループ、実行予定時間等のデータを含む。使用するロードモジュールやライブラリ関数のバイナリハッシュ値は、ジョブのプログラムから取得することができる。さらに、ジョブの実行に使用する計算ノード２又はコアに関する条件を指定する場合には、「入力パラメタ」は、使用ノード数、使用コア数、使用ノードの配置等の指定した条件を含む。入力パラメタは、属性の一例である。
【００６０】
「実行時間」は、ジョブの実行に要した時間を記憶する。「専有資源レコードリスト」は、専有資源表４１２で管理される専有資源レコードの所定数のリストである。「専有資源変動レコードリスト」は、資源使用変動表４１３で管理される専有資源変動レコードの所定数のリストである。
【００６１】
また、実行履歴は、以下に示す２つの集合ＣＰ、ＴＲから定まる直積集合ＣＰ×ＴＲの要素と考えることができる。
ＣＰ＝[入力パラメタ（の組み合わせ）：Ｉ｝
ＴＲ＝[実行時に採取されるデータ（実行時間、専有資源、資源使用変動）：Ｄ]
（Ｉ，Ｄ）∈  ＣＰ×ＴＲ
【００６２】
図５Ａ、図５Ｂ、図５Ｃ、図５Ｄは、入力パラメタを例示する図である。図５Ａは、入力パラメタのデータ構造の一例を示す図である。入力パラメタは、「プログラムレコード」、「使用者レコード」、「ジョブ資源指定レコード」を含む。図５Ｂ、図５Ｃ、図５Ｄは、それぞれ「プログラムレコード」、「使用者レコード」、「ジョブ資源指定レコード」のデータ構造を例示する。
【００６３】
図５Ｂは、プログラムレコードのデータ構造の一例を示す図である。プログラムレコードは、「プログラム名」及び「プログラムのバイナリハッシュ値」を含む。「プログラム名」は、ジョブのプログラム名を記憶する。「プログラムのバイナリハッシュ値」は、当該プログラムのバイナリハッシュ値を記憶する。
【００６４】
図５Ｃは、使用者レコードのデータ構造の一例を示す図である。使用者レコードは、「使用者名」及び「使用者の所属グループ」を含む。「使用者名」は、ジョブの使用者を記憶する。「使用者の所属グループ」は、当該使用者の所属グループを記憶する。
【００６５】
図５Ｄは、ジョブ資源指定レコードのデータ構造の一例を示す図である。ジョブ資源指定レコードは、「実行予定時間」、「ノード配置形状」、「使用ノード種別」を含む。「実行予定時間」は、予測される実行時間を記憶する。「ノード配置形状」は、ジョブの実行に使用する一以上の計算ノード２の組合せを記憶する。「使用ノード種別」は、ジョブの実行に使用する計算ノード２の種別を記憶する。計算ノード２の種別は、計算ノード２に含まれる資源の仕様、例えば、ＣＰＵ  ２ａの性能、メモリ２ｂの容量、又はＣＰＵ  ２ａがＧＰＧＰＵやＦＰＧＡ等のアクセラレータであるか否か等の仕様により指定される種別である。
【００６６】
図６は、専有資源レコードのデータ構造の一例を示す図である。専有資源レコードは、「専有資源の種別」、「資源数」、「ノード配置形状」を含む。「専有資源の種別」は、ＣＰＵ  ２ａ、ＣＰＵ  ２ａのコア、メモリ２ｂ、メモリ内の特定領域等の専有資源の種別を記憶する。「資源数」は、ジョブの実行に使用される当該専有資源の数を記憶する。「ノード配置形状」は、ジョブの実行に使用された一以上の計算ノード２の組合せを記憶する。
【００６７】
図７は、資源使用変動レコードのデータ構造の一例を示す図である。資源使用変動レコードは、「資源種別」、「資源使用の周波数成分識別子」、「使用ノード種別」を含む。「資源種別」は、各計算ノード２上又は各コア上の資源の種別である。資源は、例えば、ＣＰＵ時間、ワーキングセットサイズ、仮想空間サイズ、単位時間ごとのメモリアクセス量（即ち、キャッシュミス発生量）、ＩＯＰＳ、ＩＯバンド幅である。「資源使用の周波数成分識別子」は、各計算ノード２上又は各コア上での当該資源の使用量の変動を周波数成分に分解したものを特定する識別子を記憶する。資源使用の周波数成分は、ジョブの実行終了後に、ＤＢサーバ４内の補助記憶装置（図示せず）上に記憶され、「資源使用の周波数成分識別子」を介して取得される。「使用ノード種別」は、ジョブの実行に使用された計算ノード２の種別を記憶する。
【００６８】
＜処理の流れ＞
図８から１２は、第１実施形態の処理の流れを説明するための図である。図８は、資源使用量の変動を記録する処理のフローチャートの一例である。図８に示される処理は、計算ノード２のジョブ起動/終了管理部２１がジョブを起動することにより開始される。
【００６９】
ＯＰ１１では、ジョブ資源使用量監視部２２は、計算ノード２上でジョブが実行中であるか否かを判定する。ジョブが実行中である場合には（ＯＰ１１：Ｙ）、処理がＯＰ１２に進む。ジョブが実行中でない場合には（ＯＰ１１：Ｎ）、図８に示される処理が終了する。
【００７０】
ＯＰ１２では、ジョブ資源使用量監視部２２は、計算ノード２上での資源使用の変動量を、資源ごとにメモリ２ｂに記録する。各資源使用の変動量は、例えば、図３に示す資源使用変動のデータ構造により記録される。次に処理がＯＰ１３に進む。
【００７１】
ＯＰ１３では、ジョブ資源使用量監視部２２は、所定の時間待機する。次に処理がａに戻り、ジョブの実行中（ＯＰ１１：Ｙ）、ＯＰ１１からＯＰ１３の処理が繰り返される。ここでは、計算ノード２ごとの資源使用変動を記録する例を示したが、ＣＰＵ  ２ａがマルチコアプロセッサ等、複数のプロセッサコアを含む場合、ジョブ資源使用量監視部２２は、コアごとに資源使用変動を記録する。
【００７２】
図９は、ジョブの実行終了後に実行履歴を登録する処理のフローチャートの一例である。実行履歴を登録する処理は、図８に示される処理によって各計算ノード２上の資源使用変動が記録され、ジョブの実行が終了した後に開始される。図９に示される処理は、例えば、ジョブ実行開始指示部/終了監視部１２１が、ジョブを実行する計算ノード２から、
各計算ノード２上でのジョブの終了の通知を受信することにより開始される。
【００７３】
ＯＰ２１では、資源使用履歴データ受信部１２３は、ジョブを実行する計算ノード２から資源使用変動データを受信し、資源使用量の変動を離散フーリエ変換により、周波数成分を取り出す。次に処理がＯＰ２２に進む。
【００７４】
ＯＰ２２では、資源使用履歴データ受信部１２３は、取り出した周波数成分を含むジョブの実行履歴を生成し、実行履歴データベース４１に登録する。ジョブの実行履歴は、例えば、図４に示す実行履歴のデータ構造により記録される。その後、図９に示される処理が終了する。
【００７５】
図１０は、実行履歴のクラスタ分析処理のフローチャートの一例である。図１０に示される処理は、図９に示される処理によって生成されたジョブの実行履歴に対するクラスタ分析処理である。図１０においてクラスタ分析処理は、１つの「最上位」クラスタに統合される「ツリー」を形成する「階層化クラスタ」を作成する。実行履歴クラスタ作成部１３１は、クラスタ分析処理を所定のタイミングで開始し、動的に実行する。
【００７６】
ＯＰ３１では、実行履歴クラスタ作成部１３１は、初期状態として、個々のジョブ実行履歴データを１つのクラスタとする。次に処理がＯＰ３２に進む。ＯＰ３２では、実行履歴クラスタ作成部１３１は、クラスタ数Ｋをジョブ実行履歴データの数ｎとする。なお、ＯＰ３１及びＯＰ３２の処理は順序が入れ替わってもよい。次に処理がＯＰ３３に進む。
【００７７】
ＯＰ３３では、実行履歴クラスタ作成部１３１は、Ｋ個のクラスタの中で最も非類似度が小さい対を求め、その対を１つのクラスタとして融合する。非類似度とは、実行履歴間または実行履歴のクラスタ間の距離に相当する。
【００７８】
本実施形態における距離は、ジョブの開始日時等の間隔尺度、又は資源使用量等の比例尺度のような数値データに対しては、ユークリッド距離とすることができる。また、定性的な利用者名等の名義尺度に対しては、距離は、同一か否かを示す０、１等の２値データとすることができる。
【００７９】
比較の際に複数の尺度、例えば名義尺度、間隔尺度、比例尺度を使用する場合、各尺度の重みづけを考慮し、各尺度に所定の重み係数を掛けて加算したものを、距離、即ち非類似度として定めてもよい。ＯＰ３３の次に、処理がＯＰ３４に進む。
【００８０】
ＯＰ３４では、実行履歴クラスタ作成部１３１は、ＫにＫ−１を代入し、クラスタ数Ｋを１減らす。次に処理がＯＰ３５に進む。ＯＰ３５では、Ｋが１より大きいか否かを判定する。Ｋが１より大きい場合には（ＯＰ３５：Ｙ）、処理がＯＰ３６に進む。Ｋが１以下である場合には（ＯＰ１１：Ｎ）、図９に示される処理が終了する。
【００８１】
ＯＰ３６では、実行履歴クラスタ作成部１３１は、ＯＰ３３において対の融合により生成された新規クラスタと、他のクラスタの非類似度を求める。次に処理がｂに戻り、Ｋが１より大きい場合（ＯＰ３５：Ｙ）、即ち、階層化クラスタの作成が完了するまで、ＯＰ３３からＯＰ３６の処理が繰り返される。
【００８２】
図１１は、クラスタ間の非類似度を求める処理のフローチャートの一例である。図１１は、図１０のＯＰ３６の処理の詳細を示す。なお、ＯＰ４１からＯＰ４４の処理は、任意の順序で行ってもよい。
【００８３】
ＯＰ４１では、実行履歴クラスタ作成部１３１は、C(i)に、ＯＰ３３において融合されたクラスタの対のうち、構成データ数が少ない方のクラスタを設定する。ＯＰ４２では、実行履歴クラスタ作成部１３１は、C(j)に、ＯＰ３３において融合されたクラスタの対のうち、構成データ数が少なくない方のクラスタを設定する。融合されたクラスタの対の構成データ数が同じである場合は、一方のクラスタをC(i)とし、他方のクラスタをC(j)とすればよい。
【００８４】
ＯＰ４３では、実行履歴クラスタ作成部１３１は、ＣＬに、融合されたクラスタの対、即ちC(i)、C(j)以外のクラスタのリストを設定する。ＯＰ４４では、実行履歴クラスタ作成部１３１は、ＤＬに空のリストを設定する。次に処理がＯＰ４５に進む。
【００８５】
ＯＰ４５では、実行履歴クラスタ作成部１３１は、ＣＬが空のリストであるか否かを判定する。ＣＬが空のリストである場合には（ＯＰ４５：Ｙ）、図１１に示される処理が終了し、処理が図１０のｂに戻る。ＣＬが空のリストでない場合には（ＯＰ４５：Ｎ）、処理がＯＰ４６に進む。
【００８６】
ＯＰ４６では、実行履歴クラスタ作成部１３１は、C(k)に、ＣＬの先頭要素のクラスタを設定する。次に処理がＯＰ４７に進む。ＯＰ４７では、実行履歴クラスタ作成部１３１は、ＣＬから先頭要素のクラスタC(k)を取り外す。次に処理がＯＰ４８に進む。
【００８７】
ＯＰ４８では、実行履歴クラスタ作成部１３１は、ＯＰ３３における融合により生成された新規クラスタC(i)∪C(j)と、ＣＬの先頭要素のクラスタC(k)との距離を、下記の式により求める。
（数１）
d(C(i)∪C(j),C(k)) ＝ α(i)*d(C(i),C(k))+α(j)*d(C(j),C(k))
+β*d(C(i),C(j))+γ|d(C(i),C(k))-d(C(j),C(k))|
【００８８】
（数１）において、dはクラスタ間の距離を示す。例えば、d(C(i),C(j))は、クラスタC(i)とクラスタC(j)の距離である。また、α(i)、α(j)、β、γは、クラスタリング手法
により定まる係数である。例えば、最短距離法及びメディアン法を使用する場合、係数は以下の値をとる。
最短距離法：α(i)＝α(j)＝１／２、β＝０、γ＝−１／２
メディアン法：α(i)＝α(j)＝１／２、β＝−１／４、γ＝０
他にも、（数１）において係数の定め方が異なるクラスタリング手法が、複数知られている。
【００８９】
（数１）により求めた距離は、クラスタC(i)∪C(j)とクラスタC(k)との非類似度とする。次に処理がｃに戻り、ＣＬのリストが空になるまで、ＯＰ４５からＯＰ４８までの処理を繰り返す。図１１に示される処理により、クラスタC(i)∪C(j)と、ＯＰ４３でＣＬに設定されたリスト内の各クラスタC(k)との非類似度が求められる。
【００９０】
図１２は、新規ジョブの資源使用量の推定値を求める処理のフローチャートの一例である。新規ジョブが複数のクラスタに所属する場合、各クラスタへの所属確率に応じて、資源使用量が推定してもよい。また、実行履歴からの資源使用量の推定は、クラスタ内において、入力パラメタ、実行時間、専有資源、資源使用変動を変数とする回帰分析により行うことができる。
【００９１】
ここでの回帰分析は、複数の説明変数に基づく重回帰分析を含む。例えば、重回帰分析は、入力パラメタと専有資源レコードリストを説明変数として、ある資源使用変動の各周波数成分を目的変数としてもよい。また、重回帰分析は、入力パラメタを説明変数として、ある資源使用変動の各周波数成分を目的変数としてもよい。ただし、説明変数は１つであってもよい。例えば、入力パラメタに実行予定時間が含まれる場合、実際の実行時間は、１つのパラメタで説明することができる。
【００９２】
図１２に示される処理は、例えば、新規ジョブの投入により開始される。ＯＰ５１では、新規ジョブ所属クラスタ推定部１３２は、ＣＬに、資源使用量推定が可能なクラスタＣ１のリストを設定する。資源使用量推定が可能なクラスタＣ１は、所定数の実行履歴を含み、回帰分析等により資源使用量を推定することができるクラスタである。次に処理がＯＰ５２に進む。
【００９３】
ＯＰ５２では、新規ジョブ所属クラスタ推定部１３２は、ＣＬリスト内に、新規ジョブの入力パラメタＰと同一の入力パラメタを持つ実行履歴を含むクラスタがあるか否かを判定する。同一の入力パラメタを持つ実行履歴を含むクラスタがある場合には（ＯＰ５２：Ｙ）、処理がＯＰ５３に進む。同一の入力パラメタを持つ実行履歴を含むクラスタがない場合には（ＯＰ５２：Ｎ）、処理がＯＰ５７に進む。
【００９４】
ＯＰ５３では、新規ジョブ所属クラスタ推定部１３２は、ＭＬに、条件を満たすクラスタで最下位のクラスタＣ２のリストを設定する。条件を満たすクラスタは、新規ジョブの入力パラメタＰと同一の入力パラメタを持つ実行履歴を含むクラスタである。次に処理がＯＰ５４に進む。
【００９５】
ＯＰ５４では、資源使用変動パターン推定部１３３は、ＭＬの各要素Ｃ２に対し、入力パラメタがＰの新規ジョブが所属した場合の資源使用量推定値を求める。次に処理がＯＰ５５に進む。
【００９６】
ＯＰ５５では、資源使用変動パターン推定部１３３は、ＭＬの各要素Ｃ２に対し、入力パラメタがＰの新規ジョブの推定所属確率を求める。入力パラメタ又は入力パラメタの組みあわせがＰと同一であるという条件で、新規ジョブがクラスタＣ２に所属する確率は、各クラスタＣ２の要素で入力パラメタがＰと同一の実行履歴の数に比例するものとして、以下のように計算する。
Ｎ（Ｃ２）＝（入力パラメタがＰである実行履歴の数）
Ｎ（ＡＬＬ２）＝（入力パラメタがＰである実行履歴の総数）
クラスタＣ２に対する入力パラメタＰのジョブの所属確率＝Ｎ（Ｃ２）／Ｎ（ＡＬＬ２）
なお、ＭＬの要素Ｃ２が１つの場合、その１つのクラスタに対する所属確率を１とする。次に処理がＯＰ５６に進む。
【００９７】
ＯＰ５６では、資源使用変動パターン推定部１３３は、ＭＬ全体における資源使用量の推定値を、ＭＬの各クラスタＣ２に対する（推定所属確率）×（資源使用量推定値)の総
和とする。その後、処理がｄ３に進み、図１２に示される処理が終了する。
【００９８】
ＯＰ５７では、新規ジョブ所属クラスタ推定部１３２は、ＤＬに、ＣＬ内で新規ジョブの入力パラメタＰとの距離がd以下であるクラスタＣ３のリストを設定する。距離dは、例えば、入力パラメタの各成分に異なる重みをつけたユークリッド距離としてもよい。次に処理がＯＰ５８に進む。
【００９９】
ＯＰ５８では、新規ジョブ所属クラスタ推定部１３２は、ＤＬが空のリストであるか否かを判定する。ＤＬが空のリストである場合には（ＯＰ５８：Ｙ）、処理がＯＰ５９に進む。ＤＬが空のリストでない場合には（ＯＰ５８：Ｎ）、処理がＯＰ６０に進む。
【０１００】
ＯＰ５９では、新規ジョブ所属クラスタ推定部１３２は、新規ジョブの入力パラメタＰとの距離dを所定の値だけ増加させる。距離dを増加させることで、新規ジョブの入力パラメタＰとの距離がd以下となるクラスタの対象範囲が広がる。次に処理がｄ１に戻り、Ｄ
Ｌにリストが設定されるまで、ＯＰ５７からＯＰ５９までの処理が繰り返される。
【０１０１】
ＯＰ６０では、資源使用変動パターン推定部１３３は、ＤＬの各要素Ｃ３に対し、入力パラメタがＰの新規ジョブが所属した場合の資源使用量推定値を求める。次に処理がＯＰ６１に進む。
【０１０２】
ＯＰ６１では、資源使用変動パターン推定部１３３は、ＤＬの各要素Ｃ３に対し、入力パラメタがＰの新規ジョブの推定所属確率を求める。新規ジョブがクラスタＣ３に所属する確率は、各クラスタＣ３の要素で入力パラメタＰとの距離がd以下である実行履歴の数
に比例するものとして、以下のように計算する。
Ｎ（Ｃ３）＝（入力パラメタＰとの距離がd以下である実行履歴の数）
Ｎ（ＡＬＬ３）＝（入力パラメタＰとの距離がd以下である実行履歴の総数）
クラスタＣ３に対する入力パラメタＰのジョブの所属確率＝Ｎ（Ｃ３）／Ｎ（ＡＬＬ３）
なお、ＤＬの要素Ｃ３が１つの場合、その１つのクラスタに対する所属確率を１とする。次に処理がＯＰ６２に進む。
【０１０３】
ＯＰ６２では、資源使用変動パターン推定部１３３は、ＤＬ全体における資源使用量の推定値を、ＤＬの各クラスタＣ３に対する（推定所属確率）×（資源使用量推定値)の総
和とする。その後、処理がｄ３に進み、図１２に示される処理が終了する。
【０１０４】
以上により得られた新規ジョブの資源使用量の推定値に基づいて、専有資源特定部１３４は、新規ジョブが使用する計算ノード２の割当て位置を特定する。
【０１０５】
＜第１実施形態の作用効果＞
資源使用変動パターン推定部１３３は、クラスタ内での回帰分析により資源使用変動を推定する場合、説明変数として、入力パラメタ、実行時間、専有資源、資源使用変動等の条件を任意に組み合わせてもよい。これにより、資源使用変動パターン推定部１３３は、着目する資源に応じて、柔軟な負荷の平準化を図ることができる。
【０１０６】
新規ジョブの類似ジョブの実行履歴が複数のクラスタに含まれる場合、資源使用変動パターン推定部１３３は、各クラスタに含まれる類似ジョブの実行履歴の数に応じた所属確率を考慮して、新規ジョブの資源使用変動パターンを推定してもよい。これにより、資源使用変動パターン推定部１３３は、特定のクラスタに含まれる実行履歴よりも多くの実行履歴から推定するため、新規ジョブの資源使用量を精度良く推定することができる。
【０１０７】
資源使用変動パターン推定部１３３は、資源使用変動から、離散フーリエ変換により周波数成分を取り出して比較することで、資源使用変動パターンの類似性を判定する。資源使用変動パターン推定部１３３は、周波数成分の比較により、例えば、少し時間をずらして平行移動したほぼ同じ資源使用変動パターンの類似性の見落としが避けられる。これにより、資源使用変動パターン推定部１３３は、新規ジョブに対し、適切な類似ジョブを特定し、新規ジョブの資源使用量を精度よく推定することができる。
【０１０８】
新規ジョブ所属クラスタ推定部１３２は、新規ジョブと類似ジョブとの非類似度を、各ジョブの入力パラメタに含まれる各尺度の値から算出されるユークリッド距離とすることができる。これにより、新規ジョブと入力パラメタが一致する類似ジョブが存在しない場合でも、新規ジョブ所属クラスタ推定部１３２は、非類似度が、所定の閾値より小さいジョブを類似ジョブとして、新規ジョブの所属クラスタを推定することができる。
【０１０９】
新規ジョブ所属クラスタ推定部１３２は、ユークリッド距離を求める際、各尺度に所定の重み係数を掛けてもよい。これにより、新規ジョブ所属クラスタ推定部１３２は、着目する尺度に応じた類似ジョブを推定することができる。
【０１１０】
以上より、専有資源特定部１３４は、新規ジョブに対し、適切な類似ジョブを特定し、新規ジョブの資源使用量を精度よく推定することにより、新規ジョブに対する計算ノード２の割当てを最適化し、負荷の平準化を向上させることができる。
【０１１１】
＜第２実施形態＞
第２実施形態では、並列計算機システムは、既存ジョブの資源使用量も含めた各計算ノード２上の資源使用量に基づいて、ジョブ間の干渉を低減するように、新規ジョブの割当て位置を最適化する。本実施形態では、新規ジョブを割り当てる対象が計算ノード２であるものとして説明するが、ＣＰＵ  ２ａが複数のプロセッサコアを含むマルチプロセッサ等である場合、新規ジョブを割り当てる対象は、コアであってもよい。
【０１１２】
第２実施形態における装置構成及び処理構成は、第１実施形態と同様である。第２実施形態では、第１実施形態と重複する説明は省略される。第２実施形態において、専有資源特定部１３４は、各計算ノード２から各ＩＯノード３への時間帯別のネットワーク資源使用量を推定し、ネットワークの輻輳が最小となるように、新規ジョブが使用する計算ノード２の割当て位置を最適化する。
【０１１３】
＜処理の流れ＞
図１３は、新規ジョブが使用する資源の割当て位置を最適化する処理のフローチャートの一例である。ここでの割当て位置の最適化は、ネットワーク資源の使用量に基づくネットワーク負荷を平準化するため処理として説明される。図１３に示される処理は、図１２に示される処理によって、資源使用変動パターンが推定された後、開始される。
【０１１４】
ＯＰ７１では、専有資源特定部１３４は、ＬＬに、入力パラメタから定まる計算ノード２の割当て位置候補のリストを設定する。割当て位置候補は、一の計算ノード２又は複数の計算ノード２の組合せである。割当て位置候補のリストは、ジョブスケジューラ・ノード１から取得される。次に処理がＯＰ７２に進む。
【０１１５】
ＯＰ７２では、専有資源特定部１３４は、ＦＦに、ジョブのＩＯによって発生するネットワーク負荷の全周波数成分の推定値を設定する。ネットワーク負荷は、ネットワーク資源の使用量に相当する。また、全周波数成分は、新規ジョブと既存ジョブにおけるネットワーク資源使用量の周波数成分を含む。次に処理がＯＰ７３に進む。
【０１１６】
ＯＰ７３では、専有資源特定部１３４は、逆フーリエ変換により、ＦＦから一定時間間隔でのネットワーク負荷の推定値を求める。次に処理がＯＰ７４に進む。ＯＰ７４では、専有資源特定部１３４は、ＥＬに、各割当て位置候補における各時間帯での負荷の推定値を設定する。負荷の推定値は、割当て位置候補に含まれる計算ノード２ごとに求められる。また、負荷の推定値は、新規ジョブと既存ジョブの負荷の推定値の和である。次に処理がＯＰ７５に進む。
【０１１７】
ＯＰ７５では、専有資源特定部１３４は、ＸＬに各割当て位置候補での輻輳度を設定する。各割当て位置候補での輻輳度は、(各時間帯での負荷の推定値が適正負荷を上回る箇
所の超過負荷×時間)の和である。次に処理がＯＰ７６に進む。
【０１１８】
ＯＰ７６では、専有資源特定部１３４は、ＸＬから、輻輳度が最小となる割当て位置候補を割当て位置とする。その後、図１３に示される処理が終了する。
【０１１９】
＜第２実施形態の作用効果＞
並列計算機環境では、計算ノード群はＩＯノード群と分離されており、ＩＯノード群は、計算ノード群からネットワーク経由でアクセスすべき共有資源となる。このため、ネットワーク負荷を含むＩＯ負荷を平準化し、ＩＯ負荷間の干渉を低減することが求められる。
【０１２０】
第２実施形態では、専有資源特定部１３４は、新規ジョブ及び既存ジョブのネットワーク資源の資源使用量を推定し、各専有資源における各時間帯での資源使用量を平準化する割当て位置候補に、新規ジョブを割り当てる。これにより、並列計算機システム１０は、ネットワークを考慮したＩＯ負荷の平準化及び既存ジョブとの干渉の低減を図ることができる。
【０１２１】
負荷の平準化や干渉の低減を図るために考慮する資源は、ネットワーク資源に限られない。他の資源、又はネットワーク資源を含む複数の資源の組み合わせに基づいて、資源使用量を推定し、割当て位置が最適化されてもよい。並列計算機システムは、考慮した資源又は資源の組み合わせに応じた負荷の平準化や干渉の低減を図ることができる。
【０１２２】
＜記録媒体＞
コンピュータその他の機械、装置（以下、コンピュータ等）に上記いずれかの機能を実現させるプログラムをコンピュータ等が読み取り可能な記録媒体に記録することができる。そして、コンピュータ等に、この記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。
【０１２３】
ここで、コンピュータ等が読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。このような記録媒体のうちコンピュータ等から取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ／Ｗ、ＤＶＤ、ブルーレイディスク、ＤＡＴ、８ｍｍテープ、フラッシュメモリなどのメモリカード等がある。また、コンピュータ等に固定された記録媒体としてハードディスクやＲＯＭ（リードオンリーメモリ）等がある。さらに、Solid State Drive（ＳＳＤ）はコンピュータ等から取り外し可能な記録媒体としても、コンピュータ等
に固定された記録媒体としても利用可能である。
【符号の説明】
【０１２４】
１０                並列計算機システム
１                  ジョブスケジューラ・ノード
２                  計算ノード
３                  ＩＯノード
１ａ、２ａ、３ａ    ＣＰＵ
１ｂ、２ｂ、３ｂ    メモリ
１ｃ、２ｃ、３ｃ    ＮＩＣ
１１                通信処理部
１２                資源割当処理部
１２１              ジョブ実行開始指示部/終了監視部
１２２              資源使用状況管理部
１２３              資源使用履歴データ受信部
１２４              最適化処理呼出インターフェース
１３                最適化処理部
１３１              実行履歴クラスタ作成部
１３２              新規ジョブ所属クラスタ推定部
１３３              資源使用変動パターン推定部
１３４              専有資源特定部
１３５              ＤＢインターフェース
２１                ジョブ起動/終了管理部
２２                ジョブ資源使用量監視部
２３                資源使用状況通知部
４                  ＤＢサーバ
４１                実行履歴データベース
【図１】
2016042284.tif 000003
【図２】
2016042284.tif 000004
【図３】
2016042284.tif 000005
【図４】
2016042284.tif 000006
【図５Ａ】
2016042284.tif 000007
【図５Ｂ】
2016042284.tif 000008
【図５Ｃ】
2016042284.tif 000009
【図５Ｄ】
2016042284.tif 000010
【図６】
2016042284.tif 000011
【図７】
2016042284.tif 000012
【図８】
2016042284.tif 000013
【図９】
2016042284.tif 000014
【図１０】
2016042284.tif 000015
【図１１】
2016042284.tif 000016
【図１２】
2016042284.tif 000017
【図１３】
2016042284.tif 000018