(57)【要約】【課題】評価関数の求解問題に対して、解の値によって計算時間が大きく変動する。【解決手段】複数のタスクを含む複数のジョブを生成するマスタ計算機と、複数のプロセッサを備え、前記マスタ計算機からネットワークを介して前記タスクの実行を依頼される複数のスレーブ計算機とを備える計算機システムであって、前記マスタ計算機は、所定の数値範囲における入力パラメタによって、単調増加又は単調減少する関数を計算する前記ジョブを生成し、前記所定の数値範囲を、各々の領域における前記関数の計算時間の差が最小になるように、複数の前記領域に分割し、前記ジョブは、前記領域の各々の境界である複数の前記入力パラメタによって前記関数を計算する複数の前記タスクを含む。【選択図】図１
2011070434.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスクを含む複数のジョブを生成するマスタ計算機と、複数のプロセッサを備え、前記マスタ計算機からネットワークを介して前記タスクの実行を依頼される複数のスレーブ計算機とを備える計算機システムであって、
前記マスタ計算機は、
所定の数値範囲における入力パラメタによって、単調増加又は単調減少する関数を計算する前記ジョブを生成し、
前記所定の数値範囲を、各々の領域における前記関数の計算時間の差が最小になるように、複数の前記領域に分割し、
前記ジョブは、前記領域の各々の境界である複数の前記入力パラメタによって前記関数を計算する複数の前記タスクを含むことを特徴とする計算機システム。
【請求項２】
前記マスタ計算機は、
前記関数の総計算時間を予測し、
前記予測された総計算時間を表示するデータを作成し、
前記総計算時間は、最も性能の高い前記プロセッサによって、最も前記計算時間が長い前記タスクを実行する際の実行時間と、前記領域をさらに複数に分割された領域において、最も性能の高い前記プロセッサによって、最も前記計算時間が長い前記タスクを実行する際の実行時間とを加えた値であることを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記マスタ計算機は、最も前記計算時間が長い前記タスクを、最も性能の高い前記プロセッサによって実行するために要する実行時間と、前記最も計算時間が長いタスク以外の複数の前記タスクを、前記最も性能の高いプロセッサ以外の複数の前記プロセッサによって実行するために要する前記実行時間とが、最も近くなるように、前記所定の数値範囲を複数の領域に分割することを特徴とする請求項２に記載の計算機システム。
【請求項４】
前記マスタ計算機は、
前記プロセッサによる前記タスクの実行が終了したことを取得し、
前記タスクにおいて計算された前記関数の結果が負であり、かつ、前記関数が前記単調増加する関数である場合、前記タスクにおいて計算された前記入力パラメタより小さい値の前記入力パラメタによる前記関数の計算をする前記タスクをキャンセルし、
前記タスクにおいて計算された前記関数の結果が正であり、かつ、前記関数が前記単調増加する関数である場合、前記タスクにおいて計算された前記入力パラメタより大きい値の前記入力パラメタによる前記関数の計算をする前記タスクをキャンセルし、
前記プロセッサのうち、前記タスクを実行する時間が最も長いと推定される前記プロセッサの前記タスクを、前記タスクを実行する時間が最も短いと推定される前記プロセッサに移動することを特徴とする請求項３に記載の計算機システム。
【請求項５】
前記マスタ計算機は、
前記領域における前記入力パラメタによる前記関数の計算をする前記複数のタスクを、前記複数のプロセッサによって実行するために要する実行時間が、最も前記計算時間が長い前記タスクを、最も性能の高い前記プロセッサによって実行するために要する実行時間よりも大きい場合、前記領域をさらに複数の前記領域に分割し、
前記さらに分割された領域の各々の境界である複数の前記入力パラメタによって前記関数を計算する複数の前記タスクを、前記複数のプロセッサによって実行させた場合、前記複数のプロセッサのうち少なくとも一つのプロセッサの、前記タスクの実行時間が、前記さらに分割された領域における最も前記計算時間が長い前記タスクを、最も性能の高い前記プロセッサによって実行するために要する実行時間よりも、小さくなるまで、前記複数の領域に分割することを特徴とする請求項４に記載の計算機システム。
【請求項６】
前記マスタ計算機は、
前記タスクの実行において、前記推定される最も長い実行時間が、所定の値よりも短縮された場合、前記実行時間から前記短縮された時間を、前記総計算時間から減じて、新たな前記総計算時間とすることを特徴とする請求項５に記載の計算機システム。
【請求項７】
前記マスタ計算機と前記スレーブ計算機は、複数の計算機によって仮想化された計算機によって実装されることを特徴とする請求項１に記載の計算機システム。
【請求項８】
前記スレーブ計算機は、前記タスクを前記複数のプロセッサによって実行することを特徴とする請求項１に記載の計算機システム。
【請求項９】
複数のタスクを含む複数のジョブを生成するマスタ計算機と、複数のプロセッサを備え、前記マスタ計算機からネットワークを介して前記タスクの実行を依頼される複数のスレーブ計算機とを備える計算機システムにおけるタスク生成方法であって、
前記マスタ計算機が、
所定の数値範囲における入力パラメタによって、単調増加又は単調減少する関数を計算する前記ジョブを生成し、
前記所定の数値範囲を、各々の領域における前記関数の計算時間の合計値が、略同一になるように、複数の前記領域に分割し、
前記ジョブは、前記領域の各々の境界である複数の前記入力パラメタによって前記関数を計算する複数の前記タスクを含むことを特徴とするタスク生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機システムに関し、特にタスクを生成する計算機システムに関する。
【背景技術】
【０００２】
機械学習による分析においては、分析に利用する最適なパラメタ値を得るため、様々なパラメタ値を用いた総当り計算による分析が行われている。例えば、機械学習の一つであるクラスタ分析においては、最適なクラスタ数を決定するために、様々なクラスタ数を用いた総当り計算によるクラスタ分析を行い、その中から最適なクラスタ数を選ぶ。
【０００３】
一方、総当り計算においては、複数のプロセッサ又は複数の計算機を利用して並列計算することによって、処理時間を短縮することが行われている。例えば、過去の分析のログに基づいて、今後実行する分析の実行時間を予測し、予測された各分析の実行時間に基づいて、全体の処理時間が最短になるように各計算機に各分析を割り当てる方法が提案されている（例えば、特許文献１参照）。これによって、特許文献１に記載された方法は、各計算機に均等に分析を割り当てる方法と比較して、計算機全体の稼働率が向上し、全体の処理時間を短くすることができる。
【０００４】
ところで、クラスタ分析の結果を評価する方法には、検証異常割合を利用する方法がある。検証異常割合とは、クラスタ半径外のサンプルデータの割合である。この方法においては、検証異常割合が基準値以下となるような、最大のクラスタ数を最適なクラスタ数とする。一般に検証異常割合は、クラスタ数に対して単調増加する傾向があるため、最適なクラスタ数を求める計算は、入力値をクラスタ数、出力値を検証異常割合と考える場合、単調増加関数の解を求めるための問題に帰着する。
【０００５】
単調増加関数の解を求めるための方法には、従来から二分法という方法が知られている。この二分法は、入力値の範囲を等分に二分割し、分割された境界の入力値における関数の値を計算することによって、解の範囲を絞り込む方法である。
【０００６】
図１３は、従来技術の関数ｆ（ｎ）の値がＹとなるような入力パラメタＮを求める手順を示す説明図である。
【０００７】
図１３において、最初にユーザが解の範囲がｎ０〜ｎ４であるとした場合に、ｆ（ｎ２）を計算することによって解の範囲をｎ２〜ｎ４に絞込み、次にｆ（ｎ３）を計算することによって解の範囲をｎ３〜ｎ４に絞り込む。並列計算環境においては、一回の分割を３等分以上に分割し、複数に分割された境界における関数の値を、複数の計算機（プロセッサ）が並列計算することによって、計算時間をさらに短縮することが可能である。この場合、特許文献１の方法を併用することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−２５９４３３公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
クラスタ分析を計算する時間は、クラスタ数が増加するごとに、大きく増加（Ｏ（ｎ2）以上のオーダ）する。従って、検証異常割合を計算する時間は、入力パラメタ（クラスタ数）が増加するごとに大きく増加する。このような特徴を持った関数ｆ（ｎ）の解を求めるために、等分割して解の範囲を絞り込む二分法のような方法を用いても、解の値によって計算時間が大きく変動する。
【００１０】
図１４は、従来技術の入力パラメタに対する評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）を示す説明図である。
【００１１】
図１４において、解がｎ０とｎ１の間にある場合、計算時間は、Ｔ（ｎ０）＋Ｔ（ｎ４）＋Ｔ（ｎ１）＋、、、となる。一方、解がｎ３とｎ４との間にある場合、計算時間は、Ｔ（ｎ０）＋Ｔ（ｎ４）＋Ｔ（ｎ３）＋、、、となる。このように、解が小さな値である場合、入力パラメタが小さな値において関数ｆ（ｎ）の計算を繰り返すため、総計算時間は短くなり、解が大きな値である場合、入力パラメタが大きな値において関数ｆ（ｎ）の計算を繰り返すため、総計算時間は長くなる。
【００１２】
このように、入力パラメタが大きくなるごとに計算時間が大きくなる状況においては、事前に分析に要する総計算時間を予測することが困難になるため、分析作業を業務として行う際に、作業の計画を立てづらいという課題が発生する。特許文献１に記載された並列計算方法は、総計算時間を短縮できるが、総計算時間が大きく変動することによって、総計算時間の予測が困難であるという課題を解決することはできない。
【００１３】
本発明の目的は、評価関数の解を求めるための計算時間の、解の値による変動を低減し、かつ、計算に要する時間を低減する計算機システムの提供である。
【課題を解決するための手段】
【００１４】
本発明の代表的な一実施形態によると、複数のタスクを含む複数のジョブを生成するマスタ計算機と、複数のプロセッサを備え、前記マスタ計算機からネットワークを介して前記タスクの実行を依頼される複数のスレーブ計算機とを備える計算機システムであって、前記マスタ計算機は、所定の数値範囲における入力パラメタによって、単調増加又は単調減少する関数を計算する前記ジョブを生成し、前記所定の数値範囲を、各々の領域における前記関数の計算時間の差が最小になるように、複数の前記領域に分割し、前記ジョブは、前記領域の各々の境界である複数の前記入力パラメタによって前記関数を計算する複数の前記タスクを含む。
【発明の効果】
【００１５】
本発明の代表的な一実施形態によると、計算時間を的確に予測することができるため、分析業務の計画が立てやすくなる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態の計算時間Ｔ（ｎ）を示す説明図である。
【図２】本発明の第１の実施形態のシステム構成を示すブロック図である。
【図３】本発明の第１の実施形態の計算機システムに用いられるハードウェアを示すブロック図である。
【図４】本発明の第１の実施形態のジョブ定義を示す説明図である。
【図５】本発明の第１の実施形態のプロセッサ管理テーブルを示す説明図である。
【図６】本発明の第１の実施形態のタスク生成の処理を示すフローチャートである。
【図７】本発明の第１の実施形態の計算時間マスタテーブルを示す説明図である。
【図８Ａ】本発明の第１の実施形態の計算時間管理テーブルを示す説明図である。
【図８Ｂ】本発明の第１の実施形態の計算時間管理テーブルを示す説明図である。
【図８Ｃ】本発明の第１の実施形態の計算時間管理テーブルを示す説明図である。
【図９Ａ】本発明の第１の実施形態のタスク管理テーブルを示す説明図である。
【図９Ｂ】本発明の第１の実施形態のタスク管理テーブルを示す説明図である。
【図９Ｃ】本発明の第１の実施形態のタスク管理テーブルを示す説明図である。
【図９Ｄ】本発明の第１の実施形態のタスク管理テーブルを示す説明図である。
【図９Ｅ】本発明の第１の実施形態のタスク管理テーブルを示す説明図である。
【図１０】本発明の第１の実施形態の領域分割を示すフローチャートである。
【図１１】本発明の第１の実施形態の総計算時間予測を示すフローチャートである。
【図１２】本発明の第２の実施形態のシステム構成を示すブロック図である。
【図１３】従来技術の関数ｆ（ｎ）の値がＹとなるような入力パラメタＮを求める手順を示す説明図である。
【図１４】従来技術の入力パラメタに対する評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）を示す説明図である。
【発明を実施するための形態】
【００１７】
実施形態の詳細な説明の前に、本発明の概念を示す。
【００１８】
従来の二分法等においては、解が存在する可能性がある領域を等分割し境界のパラメータによって関数を計算した後、領域を絞り込み、絞り込んだ領域をさらに計算する。図１４は、入力パラメタに対する評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）のグラフである。図１４において、領域を分割した後の総計算時間は、Ｔ（ｎ）のグラフにおける分割領域の面積に比例すると考えられる。
【００１９】
例えば、解がｎ０〜ｎ１の間に存在することが分かった後の総計算時間と、解がｎ３〜ｎ４の間に存在することが分かった後の総計算時間との比は、図１４における領域Ｄ０の面積と領域Ｄ１に面積との比に等しくなる。
【００２０】
そこで本発明においては、図１のように計算時間Ｔ（ｎ）のグラフにおいて各分割領域の面積が等しくなるように領域を分割する。これによって、解がどの分割領域に存在したとしても、分割後の計算処理に要する時間は、どの入力パラメタの範囲においても同程度になる。
【００２１】
図１は、本願発明の第１の実施形態の計算時間Ｔ（ｎ）を示す説明図である。
【００２２】
本実施形態における入力パラメタｎは、整数である。また本実施形態における評価関数ｆ（ｎ）は、入力パラメタｎに対して単調増加する関数であり、ｆ（ｎ）＝０となるｎの値を求める。しかし、計算したい評価関数が単調減少する場合は−ｆ（ｎ）を改めて評価関数とすればよく、ｆ（ｎ）＝ｃ（ｃ≠０）となるｎを求めたい場合は、ｆ（ｎ）−ｃを改めて評価関数とすればよい。
【００２３】
次に図面を用いて、本発明の実施形態を説明する。
【００２４】
図２は、本発明の第１の実施形態のシステム構成を示すブロック図である。
【００２５】
本発明の計算機システムは、ジョブを生成し、実行する計算機システムであって、ジョブは複数のタスクを含む。すなわち、本発明の計算機システムは、タスクも生成する。本発明の計算機システムは、一つのマスタ計算機１００と、複数のスレーブ計算機２００とが備わり、各々をネットワークによって接続される。ネットワークは、ＬＡＮ又はＷＡＮなどいずれのネットワークであってもよく、一つの匡体の中のバスであってもよい。
【００２６】
アプリケーション１１０は、ジョブの実行時間を予測する実行時間予測部１１１、ジョブ定義を生成するジョブ生成部１１２、ジョブの実行状態を監視するジョブ監視部１１３、ジョブプログラム１１４を含み、マスタ計算機１００上で稼動する。アプリケーション１１０は、プログラムによって実行される。
【００２７】
また、マスタ計算機１００においては、ジョブ全体を管理するジョブ管理部１２０が稼動し、スレーブ計算機２００においては、ジョブに含まれる各タスク２０１を管理するタスク管理部２０２が稼動する。ジョブ管理部１２０は、アプリケーション１１０から、後述するジョブ定義を受けると、ジョブ定義に記載されたタスク２０１を各スレーブ計算機２００におけるタスク管理部２０２に各々割り当てる。タスク２０１を割り当てられたタスク管理部２０２は、自スレーブ計算機２００上で割り当てられたタスク２０１を開始し、タスク２０１実行中はタスク２０１の進捗状況をジョブ管理部１２０に通知する。
【００２８】
マスタ計算機１００、及びスレーブ計算機２００は、いずれも一般的な計算機によって、各々実装される。マスタ計算機１００、及びスレーブ計算機２００が実装される計算機のハードウェアを図３に示す。
【００２９】
図３は、本発明の第１の実施形態の計算機システムに用いられるハードウェアを示すブロック図である。
【００３０】
マスタ計算機１００及びスレーブ計算機２００は、プロセッサ（ＣＰＵ）３０１、ネットワークＩ／Ｆ３０２、入出力Ｉ／Ｆ３０３、メモリ３０４、及びＤｉｓｋ  Ｉ／Ｆ３０５を、各々一つ以上備える。マスタ計算機１００及びスレーブ計算機２００を総称して計算機と記載する。
【００３１】
ネットワークＩ／Ｆ３０２は、計算機外部のＬＡＮなどのネットワークに接続され、計算機が他の計算機と通信をするために用いられる。Ｄｉｓｋ  Ｉ／Ｆ３０５は、各種プログラムやデータを記録するためのディスク装置３０９に接続される。入出力Ｉ／Ｆ３０３は、キーボード３０６、マウス３０７、及びディスプレイ３０８等の入出力装置に接続され、ユーザからの入力をプロセッサ３０１に送り、また、プロセッサ３０１からの出力結果をディスプレイなどの出力装置に送る。なお、スレーブ計算機２００において、前述の入出力装置は省略されてもよい。
【００３２】
計算機においてプロセッサ３０１は、メモリ３０４に格納されるプログラムを参照するか、又はＤｉｓｋ  Ｉ／Ｆ３０５を介してディスク装置３０９に格納されるブログラムを参照し、出力結果を入出力Ｉ／Ｆ３０３を介してユーザに提供する。または、ネットワークＩ／Ｆ３０２を介して、他の計算機に出力結果を送る。または、出力結果をメモリ３０４又はディスク装置３０９に格納する。
【００３３】
図４は、本発明の第１の実施形態のジョブ定義１１００を示す説明図である。
【００３４】
ジョブ定義１１００は、図４に示すように、タスクを実行するためのプログラム（"ｐｒｏｇｒａｍ"要素の部分）１１０１と、タスク定義（"ｔａｓｋｓ"要素の部分）１１０２とを含む。
【００３５】
タスク定義１１０２には、各タスクを一意に識別するタスク識別子（"ｔａｓｋ  ｔｉｄ"要素の部分）１１０２−１、各タスクを実行するプロセッサ３０１を一意に識別するプロセッサ識別子（"ｐｉｄ"要素の部分）１１０２−１−１と、プログラム１１０１に与えるパラメタ（"ｐａｒａｍ"要素の部分）１１０２−１−２が、各タスク毎に定義される。パラメタ１１０２−１−２は、入力パラメタｎに相当する。
【００３６】
プロセッサ識別子１１０２−１−１が示すプロセッサ３０１が、どの計算機に備わるかは、図５に示すプロセッサ管理テーブルＴ０１によって管理される。
【００３７】
図５は、本発明の第１の実施形態のプロセッサ管理テーブルＴ０１を示す説明図である。
【００３８】
プロセッサ管理テーブルＴ０１は、ＰＩＤ５０１、性能５０２、計算機名５０３、及び計算機内ＰＩＤ５０４を含む。ＰＩＤ５０１は、スレーブ計算機２００に備わるプロセッサ３０１に割り当てられ、ジョブ定義１１００に記載されるプロセッサ識別子１１０２−１−１と同じであり、計算機システム全体で一意である。性能５０２は、プロセッサ３０１の性能を示し、例えばクロック数などの数値が予め格納される。
【００３９】
計算機名５０３は、そのプロセッサ３０１が稼動するスレーブ計算機２００の名前であり、計算機内ＰＩＤ５０４は、そのスレーブ計算機２００におけるプロセッサ３０１の識別子である。プロセッサ管理テーブルＴ０１は、ジョブ管理部１２０によって、マスタ計算機１００のメモリ３０４又はディスク装置３０９にあらかじめ格納される。プロセッサ３０１が追加又は削除された場合に、ジョブ管理部１２０によって更新される。
【００４０】
以下の説明においては、評価関数ｆ（ｎ）がジョブプログラム１１４に予め含まれており、この評価関数ｆ（ｎ）の計算時間を予測する計算時間Ｔ（ｎ）がジョブ生成部１１２に予め含まれている。但し、評価関数ｆ（ｎ）、及び計算時間Ｔ（ｎ）は、ユーザによって入力されてもよい。
【００４１】
以下、図６を用いて本発明による計算手順を説明する。
【００４２】
図６は、本発明の第１の実施形態のタスク２０１の生成を示すフローチャートである。
【００４３】
まずユーザは、キーボード３０６又はマウス３０７の入力装置を介して、マスタ計算機１００のアプリケーション１１０に、評価関数ｆ（ｎ）の解の探索範囲すなわち入力パラメタｎの探索範囲を入力する（ステップ１０１）。
【００４４】
次に、アプリケーション１１０のジョブ生成部１１２は、ステップ１０２において、図７に示す計算時間管理マスタテーブルＴ０２を初期化する。
【００４５】
図７は、本発明の第１の実施形態の計算時間管理マスタテーブルＴ０２を示す説明図である。
【００４６】
図７に示す計算時間管理マスタテーブルＴ０２は、入力パラメタｎ７０１、計算時間Ｔ７０２、合計時間Ｓ７０３を含む。入力パラメタｎ７０１は入力パラメタであり、計算時間Ｔ７０２は入力パラメタｎ７０１に対する評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）の値であり、合計時間Ｓ７０３は入力パラメタｎ７０１の最小値からの計算時間Ｔ７０２の和である。計算時間管理マスタテーブルＴ０２、マスタ計算機１００のメモリ３０４又はディスク装置３０９に格納される。
【００４７】
計算機システムに異なる種類のプロセッサ３０１が存在する場合は、プロセッサ識別子５０１が最小のプロセッサ（基準プロセッサ）によって評価関数ｆ（ｎ）が計算されたときの計算時間をＴ（ｎ）とする。本実施形態において、システムには図５に示すプロセッサ３０１が存在するため、Ｔ（ｎ）の値は、プロセッサ識別子５０１が"１"を示すプロセッサ３０１によって計算されたときの計算時間になる。
【００４８】
ジョブ生成部１１２は、ステップ１０１においてユーザによって入力された入力パラメタｎの探索範囲のｎの値についてＴ（ｎ）を計算し、計算時間管理マスタテーブルＴ０２の入力パラメタｎ７０１及び計算時間Ｔ７０２に、入力パラメタｎ７０１が小さい順に結果を格納する。次にジョブ生成部１１２は、入力パラメタｎ７０１の小さい順に計算時間管理マスタテーブルＴ０２から計算時間Ｔ７０２を読み取り、和を合計時間Ｓ７０３に格納する。
【００４９】
例えば、図７に示す計算時間管理マスタテーブルＴ０２は、Ｔ（ｎ）＝１０００＋ｎ×ｎ（ｍｓｅｃ）として作成した例である。Ｔ（ｎ）のｎ×ｎ（ｍｓｅｃ）の部分が評価関数ｆ（ｎ）の計算時間であり、１０００（ｍｓｅｃ）の部分が計算のためのオーバーヘッドである。このように、評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）は、評価関数ｆ（ｎ）の実際の計算に要する時間に加えて、計算のためのオーバーヘッドも考慮して決定する必要がある。
【００５０】
まずジョブ生成部１１２は、入力パラメタｎ７０１の値が１〜１０００までについて、計算時間管理マスタテーブルＴ０２の入力パラメタｎ７０１及び計算時間Ｔ７０２を格納し、次に、ｎ＝０であるレコードＴの値を合計時間Ｓ７０３に記録する。Ｓ（ｎ）＝Ｓ（ｎ−１）＋Ｔ（ｎ）の関係から、以降は、入力パラメタｎ７０１の値が一つ小さいレコードの合計時間Ｓ７０３の値と、その入力パラメタｎ７０１の値に対応するレコードの計算時間Ｔ７０２の値の和を、そのレコードの合計時間Ｓ７０３として格納する。なお、本実施形態において、Ｔ（ｎ）＝１０００＋ｎ×ｎ（ｍｓｅｃ）としたが、Ｔ（ｎ）は入力パラメタｎに対してどのような特性を持ってもよい。前述の通り、ジョブ生成部１１２は、計算時間管理マスタテーブルＴ０２を初期化する（ステップ１０２）。
【００５１】
次にジョブ生成部１１２は、ステップ１０３において、入力パラメタｎの範囲を、タスクとして分割して計算すべき領域に分割する。分割境界点、すなわち分割される境界における位置の情報は、図８Ａ〜Ｃに示す計算時間管理テーブルＴ０３に格納する。
【００５２】
図８Ａ〜Ｃは、本発明の第１の実施形態の計算時間管理テーブルＴ０３を示す説明図である。
【００５３】
計算時間管理テーブルＴ０３は、入力パラメタｎ８０１、分割値８０２、及び計算時間Ｔ８０３を含む。入力パラメタｎ８０１は、分割境界点における入力パラメタｎの値、分割値８０２は入力パラメタｎの最大値と最小値との間で計算時間管理マスタテーブルＴ０２の合計時間Ｓ７０３の値を等分割した値、計算時間Ｔ８０３は入力パラメタｎに対する評価関数ｆ（ｎ）の計算時間Ｔ（ｎ）である。
【００５４】
計算時間管理テーブルＴ０３は、後述する作成方法によって、図８Ａ、Ｂ、Ｃの順に作成される。本実施形態においては、ステップ１０３によって、図８Ｃに示す計算時間管理テーブルＴ０３が得られるものとする。
【００５５】
図８Ｃに示す計算時間管理テーブルＴ０３の入力パラメタｎ８０１の値は、（１）Ｔ（ｎ）のグラフの各領域の面積がほぼ同じになる、（２）分割点における評価関数ｆ（ｎ）の値を並列計算する際、なるべくプロセッサの空き時間が少なくなる、（３）１回の並列処理がなるべく短時間で終了する、という三つの条件を満たすように定められる。
【００５６】
（１）の条件を適用する理由は、図１に示す通り、Ｔ（ｎ）のグラフの各領域の面積をほぼ同じにすることによって、各々の入力パラメタｎの範囲における計算に要する時間の合計が同程度になるためである。図１に示すＴ（ｎ）の各領域の面積とは、すなわち、各領域における各入力パラメタｎによって、評価関数ｆ（ｎ）を計算した際の計算時間を、各領域において加算した値である。
【００５７】
（２）及び（３）の条件を適用する理由は、１回の並列処理（イテレーション）の時間を減らして、イテレーションの回数を増やすほうが、効率的に領域を絞り込め、計算時間の短縮を図れるからである。
【００５８】
次に実行時間予測部１１１は、総計算時間予測値を後述する方法によって算出し、マスタ計算機１００に備えられたディスプレイ３０６に、残り時間として表示する。計算実行中、ディスプレイ３０６に表示する残り時間は、随時カウントダウンされる（ステップ１０４）。
【００５９】
次にジョブ生成部１１２は、ステップ１０５において、ジョブを生成する。ジョブ生成の際、実行時間予測部１１２によって作成された図９に示すタスク管理テーブルＴ０４を用いる。
【００６０】
図９Ａ〜Ｅは、本発明の第１の実施形態のタスク管理テーブルＴ０４を示す説明図である。
【００６１】
タスク管理テーブルＴ０４は、ｐｉｄ９０１、空き時間９０２、タスク９０３を含む。ｐｉｄ９０１は、タスクを実行するプロセッサ３０１の識別子であり、プロセッサ管理テーブルＴ０１のｐｉｄ５０１に相当する。以下において、ｐｉｄ５０１及びｐｉｄ９０１に格納される値を、ｐｉｄによって示す。
【００６２】
空き時間９０２は、対応するプロセッサ３０１において全体の並列計算が終了するまでの空き時間である。タスク９０３は、実行する処理の内容、すなわち入力パラメタｎを示す。
【００６３】
実行時間予測部１１２は、プロセッサ管理テーブルＴ０１からｐｉｄ５０１を参照し、タスク管理テーブルＴ０４のｐｉｄ９０１に格納する。本実施形態においては、実行時間予測部１１２は、ｐｉｄ＝１〜４であるレコード、すなわちｐｉｄ９０１が"１"、"２"、"３"及び"４"の四つのレコードを格納する。
【００６４】
次に実行時間予測部１１２は、計算時間管理テーブルＴ０３から計算時間Ｔ８０３の値が最大のレコードを抽出し、最も性能５０２が高いプロセッサ３０１に割り当てる。本実施形態においては、計算時間Ｔ８０３の値が最大のレコードは、図８Ｃに示す計算時間管理テーブルＴ０３のｎ＝９００のレコードであり、最も性能５０２が高いプロセッサ３０１はｐｉｄ＝１、２である。
【００６５】
本実施形態において、実行時間予測部１１２は、最も性能５０２が高いプロセッサ３０１は二つ存在するため、どちらにジョブを割り当ててもよいが、ここでは計算時間Ｔ８０３の値が最大のレコードに対応する入力パラメタｎによる計算を、ｐｉｄ＝１に対応するプロセッサ３０１に割り当てる。すなわち、ステップ１０１において与えられた入力パラメタｎの中で、最も計算時間が長い入力パラメタによる計算を、最も性能５０２の高いプロセッサ３０１に割り当てることとなる。
【００６６】
実行時間予測部１１２は、タスク管理テーブルＴ０４のｐｉｄ＝１のレコードのタスク９０３に、入力パラメタｎが１０００であることを示す"ｎ＝１０００"を格納する。
【００６７】
次に実行時間予測部１１２は、前述において計算を割り当てたプロセッサ３０１の実行時間を算出する。ｐｉｄ＝１のプロセッサ３０１は、計算時間管理マスタテーブルＴ０２を生成する際に用いた基準プロセッサであるため、実行時間は、入力パラメタｎ７０１が"１０００"の計算時間Ｔ（１０００）＝１００１０００（ｍｓｅｃ）となる。
【００６８】
基準プロセッサと異なるプロセッサ３０１によって計算を実行する場合、実行時間予測部１１２は、プロセッサ管理テーブルＴ０１の性能５０２を参照し、Ｔ（１０００）の値に、［基準プロセッサの性能５０２］／［計算を実行するプロセッサ３０１の性能５０２］を積算し、実行時間を算出する。
【００６９】
次に実行時間予測部１１２は、前述によって入力パラメタｎ＝１０００である計算を割り当てられたプロセッサ３０１について、タスク管理テーブルＴ０４の空き時間９０２に"０"を格納し、他のプロセッサ３０１の空き時間９０２に、前述によって計算を割りあてたプロセッサ３０１の実行時間を格納する。すなわち、ｐｉｄ＝１であるレコードの空き時間９０２には、"０"が格納され、ｐｉｄ＝２〜４であるレコードの空き時間９０２には、１０００１０００（ｍｓｅｃ）が格納される。この結果、図９Ａに示すタスク管理テーブルＴ０４が得られる。
【００７０】
次に実行時間予測部１１２は、図８Ｃに示す計算時間管理テーブルＴ０３の中から、まだプロセッサ３０１に割り当てられておらず、かつ、計算時間Ｔ８０３の値が最大のレコードを抽出する。そして、タスク管理テーブルＴ０４の空き時間９０２に、［基準プロセッサの性能５０２］／［レコードに対応するプロセッサ３０１の性能５０２］を積算した値が最大となるプロセッサ３０１に、計算時間管理テーブルＴ０３から抽出されたレコードの処理を割り当てる作業を繰り返す。
【００７１】
具体的には、計算時間管理テーブルＴ０３の入力パラメタｎ８０１が"１０００"であるレコードが割り当てられた後、入力パラメタｎ８０１が"９４１"であるレコードの計算時間Ｔ８０３の値が最大であり、［空き時間９０２］×（［基準プロセッサの性能５０２］／［レコードに対応するプロセッサ３０１の性能５０２］）が最大のプロセッサ３０１は、ｐｉｄ＝２を示すプロセッサ３０１である。
【００７２】
従って実行時間予測部１１２は、入力パラメタｎ＝９４１による計算を、ｐｉｄ＝２であるプロセッサ３０１に割り当てる。そして、この入力パラメタｎ＝９４１による計算の実行時間は、Ｔ（９４１）＝８８６４８１に［基準プロセッサの性能５０２］／［ｐｉｄ＝２のプロセッサ３０１の性能５０２］を積算し、この結果、８８６４８１（ｍｓｅｃ）となる。
【００７３】
実行時間予測部１１２は、この結果を、空き時間９０２から減算し、ｐｉｄ＝２であるレコードの空き時間９０２として、１００１０００−８８６４８１＝１１４５１９（ｍｓｅｃ）を算出する。実行時間予測部１１２は、タスク管理テーブルＴ０４のｐｉｄ＝２であるレコードの空き時間９０２に"１１４５１９"を格納し、タスク９０３に"ｎ＝９４１"を格納する。
【００７４】
このようにして、実行時間予測部１１２は、入力パラメタｎ＝８７３、７９３に対応する計算を、各プロセッサ３０１に割り当て、図９Ｂに示すタスク管理テーブルＴ０４を作成する。さらに、入力パラメタｎ＝６９２、５４９、１に対応する計算を、各プロセッサ３０１に割り当て、図９Ｃに示すタスク管理テーブルＴ０４を作成する。空き時間９０２が負の数を示すレコードは、最初に処理を割り当てたプロセッサ（ｐｉｄ＝１を示すプロセッサ３０１）の計算が終了した後に、そのプロセッサ３０１の計算が終了することを示す。
【００７５】
前述した手順によって、実行時間予測部１１２は、計算時間Ｔ８０３が長い計算を、空き時間９０２が多いプロセッサ３０１に順に割り当てるが、計算をプロセッサ３０１に最適に割り当てるため、割り当ての組み合わせすべてに、タスク管理テーブルＴ０４を作成し、空き時間９０２の最小値が最も大きいものを採用する手順を用いてもよい。
【００７６】
この手順を用いた場合、まず入力パラメタｎ＝１０００（すなわち、入力パラメタｎ８０１が"１０００"）の計算は、前述した手順と同じくｐｉｄ＝１のプロセッサ３０１に割り当てられ、残りの計算入力パラメタｎ＝９４１、８７３、７９３、６９２、５４９、１による計算と、残りのプロセッサ３０１（ｐｉｄ＝２、３、４）についての全ての組み合わせ（６通り×３通り＝１８通り）についてタスク管理テーブルＴ０４が作成される。
【００７７】
ジョブ生成部１１２は、タスク管理テーブルＴ０４を作成した後、図４に示すジョブ定義１１００を作成し、ジョブ管理部１２０に送る。ジョブ生成部１１２は、ジョブ定義１１００を送ることによって、ジョブ管理部１２０にジョブの実行を依頼する。
【００７８】
ジョブ定義１１００は、プログラム１１０１（"ｐｒｏｇｒａｍ"要素の部分）と、各プロセッサ３０１によって実行されるタスク定義１１０２（"ｔａｓｋｓ"要素の部分）を含み、パラメタ１１０２−１−２が示す異なる入力パラメタｎによって同一のプログラム１１０１を実行するための情報が記載されている。具体的には、一つのｔａｓｋ要素（すなわち、"＜ｔａｓｋ  ｔｉｄ＝"から、"＜／ｔａｓｋ＞で囲まれる記載）が一つのタスクに相当し、ｔａｓｋ要素のｔａｓｋ  ｔｉｄはタスク識別子１１０２−１であり、ｐｉｄはプロセッサ識別子１１０２−１−１であり、ｐａｒａｍは入力パラメタｎである。
【００７９】
プログラム１１０１は、１回の実行によって一つの入力パラメタｎに対する評価関数ｆ（ｎ）を計算するため、一つのタスクに記載できる入力パラメタｎは一つである。同一プロセッサ３０１に複数の入力パラメタｎを計算させる場合、ジョブ管理部１２０は、同一のプロセッサ識別子１１０２−１−１に複数のタスクを割り当てる。そして、タスクを割り当てられたプロセッサ３０１は、タスク識別子１１０２−１が小さい順に計算を実行する（ステップ１０５）。
【００８０】
ジョブ管理部１２０は、ステップ１０６において、ジョブ生成部１１２から受けたジョブ定義１１００に従って、各スレーブ計算機２００のタスク管理部２０２に処理の実行を依頼する。タスク管理部２０２は、処理の実行を依頼されると、自計算機上で稼動するスレーブ計算機２００上に存在するプロセッサ３０１に対応付けられた処理を実行するタスク２０１を生成し、処理を開始する。同一プロセッサ３０１に複数の処理が対応付けられた場合は、処理のタスク識別子１１０２−１が小さい順に実行する（ステップ１０６）。
【００８１】
各タスク管理部２０２は、ジョブ定義１１００に記載されたタスクが終了する毎にジョブ管理部１２０にタスク２０１の処理結果を通知する。本実施形態において、図９Ｂに示すタスク管理テーブルＴ０４の空き時間９０２の値が最も大きいレコードのタスク９０３、すなわち入力パラメタｎ＝７９３のタスクが最初に終了する。通知を受けたジョブ管理部１２０は、アプリケーション１１０のジョブ監視部１１３にタスク２０１の終了を通知する。ジョブ監視部１１３は、通知を受けると、ジョブ定義１１００に記載された全てのタスクが終了したか否かを判定する（ステップ１０７）。
【００８２】
ステップ１０７の判定の結果、すべてのタスクが終了していない場合、ジョブ監視部１１３は、以下の手順によって不要なタスクをキャンセルする。例えば、入力パラメタｎ＝７９３について評価関数の値ｆ（７９３）が正になった場合、入力パラメタｎ＝１と入力パラメタｎ＝７９３との間に評価関数ｆ（ｎ）の解は存在する。このため、ジョブ監視部１１３は、入力パラメタｎが７９３よりも大きい値のタスクのうち、実行中のタスクをキャンセル、すなわち削除する。
【００８３】
ジョブ監視部１１３は、図９Ｃに示すタスク管理テーブルＴ０４に基づいて、入力パラメタｎ＝８７３、９４１、１０００のタスク、すなわちタスク識別子１１０２−１が"０"、"１"及び"３"のタスクをキャンセルする。さらに、ジョブ監視部１１３は、まだ処理を開始していないタスクの実行をペンディングするようにジョブ管理部１２０に依頼する。
【００８４】
なお、ジョブ監視部１１３は、タスクが実行中ではなくても、入力パラメタｎが７９３よりも大きい値のタスクはすべてキャンセル、すなわち削除してよい。
【００８５】
また、ジョブ監視部１１３は、評価関数ｆ（ｎ）の値が負になった場合も、その入力パラメタｎの値以下の入力パラメタｎによる計算は不要であるため、前述と同じく計算が不要になったタスクをキャンセルする。
【００８６】
そして、ジョブ監視部１１３は、ジョブ管理部１２０に、計算を開始していないタスクの実行をペンディングさせる（ステップ１１１）。
【００８７】
次にジョブ生成部１１２は、ステップ１１２において、キャンセルしたタスクを実行していたプロセッサ３０１について、タスク管理テーブルＴ０４の空き時間を以下の手順によって更新し、再スケジュールする。ジョブ生成部１１２は、前回、ジョブの実行をジョブ管理部１２０に依頼した時刻とキャンセルを依頼した現在時刻とを比較し、その差からタスク管理テーブルＴ０４を作成してからの経過時間を求める。
【００８８】
本実施形態においては、上記値は入力パラメタｎ＝７９３による評価関数の計算を、ｐｉｄ＝３のプロセッサ３０１によって実行する時間、すなわちＴ（７９３）×２０００／１８００＝６９９８３２（ｍｓｅｃ）程度の時間が経過していると考えられる。ジョブの実行をジョブ管理部１２０に依頼した時刻とキャンセルを依頼した現在時刻との差は、入力パラメタｎ＝７９３による評価関数の計算時間よりもわずかながら大きいため、ここでは、７００秒（７０００００ｍｓｅｃ）の時間が経過したものとする。
【００８９】
ジョブ生成部１１２は、図９Ｃに示すタスク管理テーブルＴ０４の各レコードの空き時間９０２から上記経過時間を減算し、さらにレコード毎にキャンセルしたタスクの実行時間を加算する。なお、終了したタスクの実行時間を加算してもよい。これによって、各プロセッサ３０１における計算が終了するまでの時間を更新する。
【００９０】
本実施形態においては、ジョブ生成部１１２は、まずジョブの開始からの経過時間である７０００００（ｍｓｅｃ）を図９Ｃに示すタスク管理テーブルＴ０４の全レコードの空き時間９０２から減算する。そして、入力パラメタｎ＝８７３に対応するタスクを含むレコードは、ｐｉｄ＝３のレコードであるため、ｐｉｄ＝３のレコードからＴ（８７３）×（基準プロセッサの性能５０２）／（ｐｉｄ＝３のプロセッサ３０１の性能５０２）＝８４７９２１（ｍｓｅｃ）を加算する。すなわち、ジョブ生成部１１２は、−１８２９２２−７０００００＋８４７９２１＝−３５００１を算出し、ｐｉｄ＝３のレコードの空き時間９０２に算出した結果を格納する。
【００９１】
同じく、入力パラメタｎ＝９４１に対応するタスクを含むレコードは、ｐｉｄ＝２のレコードであるため、ｐｉｄ＝２のレコードからＴ（９４１）×（基準プロセッサの性能５０２）／（ｐｉｄ＝２のプロセッサ３０１の性能５０２）＝８８６４８１（ｍｓｅｃ）を加算する。すなわち、ジョブ生成部１１２は、−２３２０１４−７０００００＋８８６４８１＝−２３２１８２を算出し、ｐｉｄ＝４のレコードの空き時間９０２に算出した結果を格納する。
【００９２】
ジョブ生成部１１２は、入力パラメタｎ＝１０００に対応するタスクを含むレコードについても同じく更新する。
【００９３】
そしてジョブ生成部１１２は、終了及びキャンセルしたタスクの情報を、タスク管理テーブルＴ０４のタスク９０３から削除する。本実施形態においては、ｐｉｄ＝１のレコードから入力パラメタｎ＝１０００のタスクの情報を削除し、ｐｉｄ＝２のレコードから入力パラメタｎ＝９４１の情報を削除し、ｐｉｄ＝３のレコードから入力パラメタｎ＝８７３の情報を削除し、ｐｉｄ＝４のレコードから入力パラメタｎ＝７９３の情報を削除する。前述の処理によって、ジョブ生成部１１２は、図９Ｄに示すタスク管理テーブルＴ０４を作成する。
【００９４】
次にジョブ生成部１１２は、図９Ｄに示すタスク管理テーブルＴ０４に記載されているタスク９０３を、レコード間で移動させることによって、空き時間９０２の最小値を増加させる。具体的には、ジョブ生成部１１２は、空き時間９０２が最小のプロセッサ３０１から、空き時間９０２が最大のプロセッサ３０１へ、実行されていないタスクを移動する。
【００９５】
本実施形態において、ｐｉｄ＝４のプロセッサ３０１の空き時間９０２が最小であり、ｐｉｄ＝１のプロセッサ３０１の空き時間９０２が最大である。ｐｉｄ＝４のプロセッサ３０１に割り当てられた未実行のタスク９０３は、入力パラメタｎ＝６９２のタスクであり、これをｐｉｄ＝１のプロセッサ３０１において実行した場合、Ｔ（６９２）×（基準プロセッサの性能５０２）×（ｐｉｄ＝１のプロセッサ３０１の性能５０２）＝４７９８６４（ｍｓｅｃ）の時間が必要となる。そして、入力パラメタｎ＝６９２のタスクをｐｉｄ＝１のプロセッサ３０１へ移動させた場合、ｐｉｄ＝１のプロセッサ３０１の空き時間９０２は、３０１０００−４７９８６４＝−１７８８６４（ｍｓｅｃ）となる。
【００９６】
すなわち、入力パラメタｎ＝６９２のタスクを、ｐｉｄ＝４のプロセッサ３０１から、ｐｉｄ＝１のプロセッサ３０１に移動させることによって、空き時間９０２の最小値が−２３２１８２から、−１７８８６４に増加する。このため、ジョブ生成部１１２は、入力パラメタｎ＝６９２のタスクを、ｐｉｄ＝４のプロセッサ３０１から、ｐｉｄ＝１のプロセッサ３０１に移動させる。
【００９７】
そして、ジョブ生成部１１２は、タスク管理テーブルＴ０４のｐｉｄ＝１の空き時間９０２に、前述の方法によって算出された−１７８８６４（ｍｓｅｃ）を格納する。また、ｐｉｄ＝４の空き時間９０２に、入力パラメタｎ＝６９２による計算時間であるＴ（６９２）×（基準プロセッサの性能５０２）／（ｐｉｄ＝４のプロセッサ３０１の性能５０２）＝５３３１８２（ｍｓｅｃ）を加算する。その結果、ｐｉｄ＝４の空き時間９０２には、３０１０００（ｍｓｅｃ）が格納される。
【００９８】
ジョブ生成部１１２は、タスクを移動した結果に基づいて、タスク管理テーブルＴ０４のタスク９０３を更新する。前述の方法によって、ジョブ生成部１１２は、図９Ｅに示すタスク管理テーブルＴ０４を作成する。
【００９９】
なお、レコード間のタスクの移動は、前述のように、空き時間９０２の最小値から最大値へ一回のみ移動させることを、予め定められてもよいし、最小値が最も増加するまで繰り返してもよい。
【０１００】
タスクの移動の後、ジョブ生成部１１２は、図９Ｅに示すタスク管理テーブルＴ０４に基づいてジョブ定義１１００を作成し、ジョブ管理部１２０にペンディングとなっていたジョブの状態を、実行状態に変更するよう依頼する。ジョブ管理部１２０は、ジョブ生成部１１２からの依頼に基づいて実行されていないタスクを計算するプロセッサ３０１を変更するよう、各スレーブ計算機２００のタスク管理部２０２に依頼する（ステップ１１２）。
【０１０１】
ステップ１１２によって、本実施形態の計算機システムは、不要な計算を削除することができ、また、各タスクの終了毎に、実行されるプロセッサを移動させることによって、効率的にプロセッサ３０１を稼動させることができる。
【０１０２】
次に実行時間予測部１１１は、前回ジョブ管理部１２０にジョブ実行を依頼した時点での図９Ｃに示すタスク管理テーブルＴ０４と、図９Ｅに示すタスク管理テーブルＴ０４とを比較し、空き時間９０２の最小値に所定の値以上（例えば、１秒）の違いがあるか否かを確認する（ステップ１１３）。なお、この所定の値は、ユーザによって予め与えられてもよい。
【０１０３】
実行時間予測部１１１は、空き時間９０２の最小値に所定の値以上の違いがある場合、ディスプレイ３０８を介して表示していた残り時間から、その差を減算し、新たな残り時間を表示する。本実施形態において、図９Ｃに示す空き時間９０２の最小値は−２３２０１４（ｍｓｅｃ）であり、図９Ｅに示す空き時間９０２の最小値は−１７８８６４（ｍｓｅｃ）であるため、実行時間予測部１１１は、その差５３秒を残り時間から減算し、ディスプレイ３０８に減算した後の残り時間を表示する（ステップ１１４）。
【０１０４】
ステップ１１４の後、処理はステップ１０６に戻り、ステップ１１２における依頼に基づいて、並列計算を行う。
【０１０５】
ステップ１１１〜１１４によって、本実施形態の計算機システムは、ステップ１０３によって分割された領域の中から、評価関数ｆ（ｎ）の解が存在する領域を抽出することが可能となる。
【０１０６】
ステップ１０７において、ジョブに含まれる全てのタスクが終了したと判定された場合、ステップ１０８が処理される。ステップ１０８において、ジョブ生成部１１２は、評価関数ｆ（ｎ）のうちまだ計算されていない残りの領域について、総当りによる計算が可能か否かを調べる。
【０１０７】
例えば、ステップ１０６におけるタスクの並列計算によって、入力パラメタｎ＝６９２と入力パラメタｎ＝７９３との間に解が存在することが分かった場合、まだ計算されていない残り領域は、入力パラメタｎ＝６９２と入力パラメタｎ＝７９３との間の入力パラメタｎである。そして、残り領域の総当り計算を行うためには、入力パラメタｎ＝６９４〜７９２について総当り計算をする必要がある。
【０１０８】
ジョブ生成部１１２は、ステップ１０５と同じ方法によって、入力パラメタｎ＝６９４〜７９２による計算のうち計算時間８０３が最も長いレコード（入力パラメタｎ＝７９２による計算）を性能５０２が最大のプロセッサ３０１に割り当て、残りの計算（入力パラメタｎ＝６９４から入力パラメタｎ＝７９１による計算）を残りのプロセッサ３０１に割り当て、図示しない新たなタスク管理テーブルＴ０４を作成する。
【０１０９】
そして、ジョブ生成部１１２は、残り領域の総当り計算（総当り並列計算）が可能であるかを判定する（ステップ１０８）。
【０１１０】
全てのプロセッサ３０１に各入力パラメタｎによる計算を割り当てた際に、空き時間９０２に０以上の値が少なくとも一つある場合、ジョブ生成部１１２は、残り領域の総当り計算が可能であると判定し、ステップ１０９へ進む。空き時間９０２がすべて負の値である場合、ジョブ生成部１１２は、残り領域の総当り計算が不可能であると判定し、ステップ１０３へ戻り、領域を分割する（ステップ１０８）。
【０１１１】
ジョブ生成部１１２は、ステップ１０８において作成したタスク管理テーブルＴ０４に基づいて、ジョブ定義１１００を作成し、ジョブ管理部１２０へジョブ実行を依頼する（ステップ１０９）。
【０１１２】
ジョブ管理部１２０は、ステップ１０６と同じ方法によってタスクの並列計算を行う。そして、この総当り並列計算によって、ｆ（ｎ）＜０かつｆ（ｎ＋１）＞０、又は、ｆ（ｎ）＝０となる入力パラメタｎが求まるので、その際の入力パラメタｎ、ｎ＋１、ｆ（ｎ）、及び、ｆ（ｎ＋１）を計算結果として、ディスプレイ３０８等を介して出力する（ステップ１１０）。
【０１１３】
以上が、本発明による評価関数ｆ（ｎ）の解を求める手順である。ステップ１０３における処理を後述する。
【０１１４】
図１０は、本発明の第１の実施形態の領域分割を示すフローチャートである。以下では図１０を用いてステップ１０３における処理手順を説明する。
【０１１５】
複数のプロセッサ３０１を用いて並列計算する場合、プロセッサ３０１の数の並列計算が可能であるため、分割される境界の数は、プロセッサ３０１の数以上でよい。このため、ジョブ管理部１２０は、分割数をプロセッサ３０１の数に等しい値から試行を開始する（ステップ２０１）。
【０１１６】
ジョブ生成部１１２は、計算時間管理マスタテーブルＴ０２から、分割しようとしている領域における入力パラメタｎの最大値と最小値とに対応するレコードを抽出し、そのレコードの合計時間Ｓ７０３を抽出する。例えば、本実施の形態の最初の分割においては、入力パラメタｎの最小値は１であり、最大値は１０００であるため、合計時間Ｓ７０３の値は各々１００１、及び３３４８３３５００となる。
【０１１７】
なお、ステップ１０６における並列計算を行った後、再びステップ１０３において領域分割を行う場合、入力パラメタｎの範囲は、ステップ１０７においてタスクがすべて実行された際の、最後に実行されたタスクの入力パラメタｎと、最後から一つ前に実行されたタスクの入力パラメタｎとの範囲である。
【０１１８】
ステップ１０３を最初に実行する場合、ジョブ生成部１１２は、合計時間Ｓ７０３の値の範囲を（分割数−１）で等分割し、入力パラメタｎの最小値及び最大値である両端を含めた分割境界における合計時間Ｓ７０３の値を、計算時間管理テーブルＴ０３の分割値８０２に格納する。（分割数−１）で等分割する理由は、最初の分割を行うとき、分割領域の両端における評価関数ｆ（ｎ）を計算していないので、両端についても評価関数ｆ（ｎ）を計算する必要があるためである。
【０１１９】
ステップ１０３が２回目以降の場合は、ステップ１０６において分割領域の両端における評価関数ｆ（ｎ）は既に計算されているため、両端の計算は不要であり、この場合は（分割数＋１）で等分割し、両端を含まない分割境界における合計時間Ｓ７０３の値を計算時間管理テーブルＴ０３の分割値に格納する。
【０１２０】
ここではステップ１０３を最初に実行するため、（分割数−１）＝３であることから、領域を３等分に分割し、両端を含めた分割境界における合計時間Ｓ７０３の値を計算時間管理テーブルＴ０３の分割値に格納する。
【０１２１】
ステップ１０３における処理を具体的に示す。なお、入力パラメタｎの合計時間Ｓ７０３をＳ（ｎ）と記載する。ジョブ生成部１１２は、まず計算時間管理テーブルＴ０３の１レコード目の分割値８０２に、Ｓ（１）＝１００１を格納する。
【０１２２】
次に、ジョブ生成部１１２は、（Ｓ（１０００）−Ｓ（１））／３＋Ｓ（１）＝１１１６１１８３４の値を、２レコード目の分割値８０２に格納する。また、２（Ｓ（１０００）−Ｓ（１））／３＋Ｓ（１）＝２２３２２２６６７を３レコード目の分割値８０２に格納する。そして、Ｓ（１０００）＝３３４８３３５００を、４レコード目に格納する（ステップ２０２）。
【０１２３】
次に、ジョブ生成部１１２は、計算時間管理テーブルＴ０３に記載された各分割値８０２に、計算時間管理マスタテーブルＴ０２の合計時間Ｓ７０３の値が最も近い計算時間管理マスタテーブルＴ０２のレコードを検索し、そのレコードの入力パラメタｎの値を抽出し、対応する計算時間管理テーブルＴ０３の入力パラメタｎ８０１に格納する。また、そのレコードの計算時間Ｔ７０２の値を抽出し、対応する計算時間管理テーブルＴ０３の計算時間Ｔ８０３に格納する。これによって、ジョブ生成部１１２は、図８Ａに示す計算時間管理テーブルＴ０３を作成する（ステップ２０３）。
【０１２４】
次にジョブ生成部１１２は、分割領域の評価値を算出することによって、ステップ２０３において分割された領域が適切か否かを判定する。ジョブ生成部１１２は、まず、計算時間管理テーブルＴ０３の計算時間Ｔ８０３の値の最大値以外のものを加算する。そして、性能５０２が最大のプロセッサ３０１以外のプロセッサ３０１の性能５０２を加算する。さらに、この計算時間Ｔ８０３の値の加算値をプロセッサ３０１の性能５０２の加算値によって除算する。本実施形態において、以下に示す式によって値１が算出される。
【０１２５】
（１００１＋４８１６３６＋７６３８７６）／（２０００＋１８００＋１８００）＝２２２・・・・・・（値１）
【０１２６】
また、ジョブ生成部１１２は、計算時間管理テーブルＴ０３の計算時間Ｔ８０３の値の最大値を、性能５０２が最大のプロセッサ３０１の性能５０２によって除算する。本実施形態において、以下に示す式によって値２が算出される。
【０１２７】
１００１０００／２０００＝５０１・・・・・（値２）
【０１２８】
そしてジョブ生成部１１２は、値１から値２を減算し、減算した結果を分割方法評価値とする。本実施形態において、分割方法評価値は以下に示す式によって算出される（ステップ２０４）。
【０１２９】
２２２−５０１＝−２７９・・・・・（分割方法評価値）
【０１３０】
値２は、最大性能のプロセッサ３０１によって、計算時間が最も長い計算を実行した場合の実行時間である。また、値１は、最大性能ではないプロセッサ３０１によって、計算時間が最も長い計算以外の計算を、並列計算した場合の実行時間である。
【０１３１】
値１と値２とが最も近い値である場合、又は等しい値である場合、プロセッサ３０１の空き時間９０２が最小になり、効率的に並列計算が実行できていると言える。分割数を増加すると値１の分子が増加するため、値１は増える。一方、値２は、分割数によっては変化しない。
【０１３２】
そこで、ジョブ生成部１１２は、分割方法評価値が正になるまで、分割数を増やしつつステップ２０２〜ステップ２０４を行い、分割方法評価値が最も０に近くなる分割数を抽出する。
【０１３３】
ジョブ生成部１１２は、ステップ２０５において、分割方法評価値の結果が正であるか否かを判定する。そして、分割方法評価値の結果が負であると判定された場合は、分割数に１を加えてステップ２０２に戻る（ステップ２０７）。本実施形態の前述の式から、分割方法評価値の結果は負であるため、分割数に１を加えてステップ２０２に戻る。
【０１３４】
ステップ２０５において、分割方法評価値の結果が正であると判定された場合、ジョブ生成部１１２は、これまで計算した分割方法評価値の値が最も０に近い分割数を最適分割数として決定する。そして、マスタ計算機１００は、最適分割数の際の計算時間管理テーブルＴ０３をステップ１０４以降の処理において用いる。
【０１３５】
本実施形態において、分割数＝６である場合、ジョブ生成部１１２は、図８Ｂに示す計算時間管理テーブルＴ０３を作成する。そして、分割数＝６である場合の分割方法評価値を以下に示す。
（１００１＋３４０８８９＋５４２６９６＋７１１６４９＋８６２１８４）／（２０００＋１８００＋１８００）−１００１０００／２０００＝−６１．５
分割数＝７である場合、ジョブ生成部１１２は、図８Ｃに示す計算時間管理テーブルＴ０３を作成する。そして、分割数＝６である場合の分割方法評価値を以下に示す。
（１００１＋３０２４０１＋４７９８６４＋６２９８４９＋７６３１２９＋８８６４８１）／（２０００＋１８００＋１８００）−１００１０００／２０００＝４６．４
従って、ジョブ生成部１１２は、最適分割数として分割数＝７を選択し、図８Ｃに示す計算時間管理テーブルＴ０３をステップ１０４以降の処理において用いる（ステップ２０６）。
【０１３６】
前述のステップ１０３に示す領域分割において、評価関数ｆ（ｎ）の計算の範囲を、各々の領域における計算時間の合計値がほぼ等しいような領域に分割することによって、本発明の計算機システムは、入力パラメタｎの値による総計算時間の変動を低減することができる。また、ステップ２０４及び２０５において、分割方法評価値の計算と判定とを行うことによって、計算機システム内に存在するプロセッサ３０１を効率的に利用することができる。
【０１３７】
例えば、分割数が少なすぎる場合、最大性能のプロセッサ３０１が計算を実行している間、計算をしていないプロセッサ３０１が生じ、すべてのプロセッサ３０１を有効に利用できない。また、分割数が多すぎる場合、最大性能のプロセッサ３０１が計算を終了しても、その他のすべてのプロセッサ３０１が計算を続けていることになり、最大性能のプロセッサ３０１を有効に利用できない。すなわち、本発明の計算機システムは、最適な分割数によって評価関数ｆ（ｎ）の計算の範囲を分割できる。
【０１３８】
図１１は、本発明の第１の実施形態の総計算時間の予測を示すフローチャートである。図１１を用いて、ステップ１０４における処理を後述する。
【０１３９】
実行時間予測部１１１は、ステップ１０３において作成された計算時間管理テーブルＴ０３のレコードに記載されている計算時間Ｔ８０３の値の最大値に、（基準プロセッサの性能５０２）／（性能が最大のプロセッサ３０１の性能５０２）を積算したものを領域計算の実行時間として算出する。例えば、図８Ｃに示す計算時間管理テーブルにおいて、領域分割計算の実行時間は、Ｔ（１０００）×２０００／２０００＝１００１０００（ｍｓｅｃ）である（ステップ３０１）。
【０１４０】
実行時間予測部１１１は、ステップ１０３において作成された計算時間管理テーブルＴ０３のレコードの中から、隣り合うレコードの組、すなわち一つの領域を選択する。例えば図８Ｃに示す計算時間管理テーブルＴ０３の中央付近の組を一つ選択する（ステップ３０２）。
【０１４１】
実行時間予測部１１１は、評価関数ｆ（ｎ）の解が、ステップ３０２において選択された隣り合うレコードを境界とする領域に絞り込めたと仮定し、さらにその領域における計算時間を予測する。実行時間予測部１１１は、前述によって選択されたレコードの入力パラメタｎ８０１の値を入力パラメタｎの範囲として、ステップ１０８と同じ方法によって、総当り並列計算が可能か否かを判定する（ステップ３０３）。
【０１４２】
総当り計算が不可能である場合、実行時間予測部１１１は、ステップ３０２において選択された入力パラメタｎの範囲をステップ１０３と同じ方法によって領域分割を行い、ステップ３０１に戻る（ステップ３０６）。
【０１４３】
総当り計算が可能である場合、実行時間予測部１１１は、ステップ３０２において選択された入力パラメタの範囲において評価関数ｆ（ｎ）の計算時間が最大の計算時間を、計算時間管理マスタテーブルＴ０２の計算時間Ｔ７０２から抽出する。そして、抽出された計算時間Ｔ７０２の値に、（基準プロセッサの性能５０２）／（性能が最大のプロセッサ３０１の性能５０２）を積算したものを総当り計算の実行時間として算出する（ステップ３０４）。
【０１４４】
実行時間予測部１１１は、ステップ３０１において算出された領域計算の実行時間、及び総当り計算の実行時間の和を総計算時間の予測値として算出する（ステップ３０５）。
【０１４５】
前述のステップ１０４によって取得される総計算時間は、ステップ１０３において入力パラメタｎを、計算時間に基づいて複数の領域に分割することによって、どの領域に解が存在しても大きな変動はない。このためユーザは、ステップ１０４によって取得された総計算時間を参照することによって、分析業務における計画を容易に立てることができる。
【０１４６】
本発明は、上記実施の形態に限らず、数々の変形が可能である。
【０１４７】
例えば、第１の実施形態におけるシステム構成は、各計算機が１個のプロセッサ３０１を搭載しているが、複数個のプロセッサ３０１を搭載してもよい。また、一つのプロセッサ３０１が複数のプロセッサコアを搭載してもよい。この場合、第１の実施形態におけるプロセッサ３０１をプロセッサコアに置き換えればよい。
【０１４８】
図１２は、本発明の第２の実施形態のシステム構成を示すブロック図である。
【０１４９】
第１の実施形態における計算機システムは、１台のマスタ計算機１００及び複数台のスレーブ計算機２００を備えたが、図１２に示すシステム構成のように、マスタ計算機１００とスレーブ計算機２００の機能を１台の計算機に集約し、仮想化することによって計算機１台が処理を行ってもよい。この場合、処理を行う計算機には、複数のプロセッサ３０１、又は複数のプロセッサコアが搭載されていることが望ましい。
【０１５０】
また、第１の実施形態において、入力パラメタｎが整数であると仮定したが、入力パラメタｎが整数以外の場合、入力パラメタｎをｎ＝（ｍ／ｌ）（ｍ、ｌは整数）とすることによって、整数に変換してもよい。例えば、上記ｌの値を適当な固定値とすることによって、評価関数の引数を整数１個に変換することが可能である。入力パラメタｎの変換方法には、他にも様々な方法が適用可能であり、適切な方法を選んで実施することができる。
【０１５１】
本実施形態によれば、評価関数ｆ（ｎ）の解がどのような値であっても総計算時間が一定となり、総計算時間が予測可能となる。これによって、ユーザによる分析業務の計画を立てやすくなる。
【符号の説明】
【０１５２】
１００  マスタ計算機
１１０  アプリケーション
１１２  ジョブ生成部
１１３  ジョブ監視部
１１４  ジョブプログラム
１２０  ジョブ管理部
２００  スレーブ計算機
２０１  タスク
２０２  タスク管理部
【図１】
2011070434.tif 000003
【図２】
2011070434.tif 000004
【図３】
2011070434.tif 000005
【図４】
2011070434.tif 000006
【図５】
2011070434.tif 000007
【図６】
2011070434.tif 000008
【図７】
2011070434.tif 000009
【図８Ａ】
2011070434.tif 000010
【図８Ｂ】
2011070434.tif 000011
【図８Ｃ】
2011070434.tif 000012
【図９Ａ】
2011070434.tif 000013
【図９Ｂ】
2011070434.tif 000014
【図９Ｃ】
2011070434.tif 000015
【図９Ｄ】
2011070434.tif 000016
【図９Ｅ】
2011070434.tif 000017
【図１０】
2011070434.tif 000018
【図１１】
2011070434.tif 000019
【図１２】
2011070434.tif 000020
【図１３】
2011070434.tif 000021
【図１４】
2011070434.tif 000022