(57)【要約】【課題】反復計算において、計算完了までの計算量をより精度よく推定する技術を提供すること。【解決手段】問題情報の解候補を求める計算を、解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行する反復計算部１１と、問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、要求条件を表す情報、および、評価値が要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を記憶した反復計算履歴記憶部１２と、反復計算履歴記憶部１２に記憶された情報と、反復計算部１１によって実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報とに基づいて、実行中の反復計算の総反復回数を推定する反復回数推定部１３とを備える。【選択図】      図１
2017097392.tif 000002
【特許請求の範囲】
【請求項１】
問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行する反復計算部と、
前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を記憶した反復計算履歴記憶部と、
前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定する反復回数推定部と、
を備えた反復計算量推定装置。
【請求項２】
前記反復計算履歴記憶部に記憶された情報に基づいて、前記反復計算における任意の反復回数までの前記評価値の列および前記要求条件を表す情報を入力として前記総反復回数を推定する反復回数推定式を学習する学習部をさらに備え、
前記反復回数推定部は、前記反復回数推定式を用いて、前記反復計算部によって実行中の反復計算における総反復回数を推定することを特徴とする請求項１に記載の反復計算量推定装置。
【請求項３】
前記反復計算部は、前記反復計算を、計算機クラスタのうち割り当てられた１つ以上の計算機を用いて実行し、
前記反復計算量推定部によって推定された総反復回数に基づいて、要求時間内に、前記評価値が前記要求条件を満たすまでの反復計算を完了するために必要な計算リソース量を決定する計算リソース量決定部と、
前記計算機クラスタのうち前記計算リソース量に基づく１つ以上の計算機を、前記反復計算部に割り当てる計算機割当部と、
をさらに備えたことを特徴とする請求項１または請求項２に記載の反復計算量推定装置。
【請求項４】
問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行し、
前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を反復計算履歴記憶部に記憶しておき、
前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定する方法。
【請求項５】
問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行するステップと、
前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を反復計算履歴記憶部に記憶するステップと、
前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定するステップと、
をコンピュータ装置に実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機によって実行される反復計算の処理量を予測する技術に関する。
【背景技術】
【０００２】
プログラムの処理量を予測することは、重要技術である。これは、プログラムの実行完了時間を知るだけでなく、プログラムを実行するための計算リソース量を見積りしたり、計算リソースを割り当てたりするなどの応用があるためである。
【０００３】
プログラムの処理量を予測する技術の一例が、特許文献１に記載されている。この関連技術は、あらかじめタスク総量が既知のジョブに関して、ジョブ実行中に動的にジョブの実行にかかる時間を推定する。そして、この関連技術は、推定した実行時間をもとに、時間制約を満たすように、必要となる計算リソースを制御する。具体的には、この関連技術は、ジョブの１／ｐの割合の部分タスクの実行時間Ｔを測定する。そして、この関連技術は、ジョブ全体の実行時間Ｔｅを、Ｔｅ=Ｔ（１−ｐ）／ｐの計算式により推定する。なお、“／”は除算を表す。
【０００４】
この関連技術には、ジョブのタスク総量が既知でないと、ジョブ全体の実行時間を見積もることができないという問題がある。例えば、与えられた条件が満たされるまで計算を繰り返す反復計算では、タスク総量があらかじめわかっていない。具体例としては、方程式の反復求解やSimulated Annealingのような計算は、評価値が要求閾値以上または以下になるまで反復計算および閾値判定を行うため、タスク総量をあらかじめ知ることは難しい。このため、この関連技術は、反復計算の完了までに必要となる計算リソース量を見積もることができない。
【０００５】
このような問題に関連する技術の一例が、特許文献２に記載されている。この関連技術は、評価値を最適化する反復計算において、反復回数および評価値の組の列から、それらの関係を表す近似曲線を求める。そして、この関連技術は、近似曲線の収束度合いから最終的な評価値および反復回数を推定する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第４３０８２４１号公報
【特許文献２】特開２００３−９１５１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した関連技術には、以下の課題がある。
【０００８】
特許文献２に記載された関連技術は、実行中の反復計算から得られる反復回数および評価値の組の列に基づくだけでは、反復回数の推定精度が充分でない可能性がある。
【０００９】
また、特許文献１に記載された関連技術は、前述のように、タスク総量が既知でないとジョブ全体の実行時間を推定できないため、反復計算において要求条件が満たされるまでの反復回数を推定することができない。
【００１０】
本発明は、上述の課題を解決するためになされたものである。すなわち、本発明は、反復計算において、計算完了までの計算量をより精度よく推定する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の反復計算量推定装置は、問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行する反復計算部と、前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を記憶した反復計算履歴記憶部と、前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定する反復回数推定部と、を備える。
【００１２】
また、本発明の方法は、問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行し、前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を反復計算履歴記憶部に記憶しておき、前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定する。
【００１３】
また、本発明のプログラムは、問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで繰り返す反復計算を実行するステップと、前記問題情報毎に実行された前記反復計算について、該反復計算において繰り返された各計算で算出された評価値の列、前記要求条件を表す情報、および、前記評価値が前記要求条件を満たすまでに繰り返された総反復回数をそれぞれ表す情報を反復計算履歴記憶部に記憶するステップと、前記反復計算履歴記憶部に記憶された情報と、前記反復計算部によって実行中の反復計算におけるそれまでの前記評価値の列および前記要求条件を表す情報とに基づいて、前記実行中の反復計算の総反復回数を推定するステップと、をコンピュータ装置に実行させる。
【発明の効果】
【００１４】
本発明は、反復計算において、計算完了までの計算量をより精度よく推定する技術を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第1の実施の形態としての反復計算量推定装置の構成を示すブロック図である。
【図２】本発明の第1の実施の形態としての反復計算量推定装置のハードウェア構成の一例を示す図である。
【図３】本発明の第1の実施の形態において反復計算履歴記憶部に記憶される情報の一例を示す図である。
【図４】本発明の第1の実施の形態としての反復計算量推定装置が総反復回数を推定する動作を説明するフローチャートである。
【図５】本発明の第1の実施の形態において反復計算履歴記憶部に記憶された情報を適用できない場合の、近似関数を用いた総反復回数の推定処理を説明する図である。
【図６】本発明の第２の実施の形態としての反復計算量推定装置の構成を示すブロック図である。
【図７】本発明の第２の実施の形態としての反復計算量推定装置が反復回数推定式を学習する動作を説明するフローチャートである。
【図８】本発明の第２の実施の形態としての反復計算量推定装置が総反復回数を推定する動作を説明するフローチャートである。
【図９】本発明の第３の実施の形態としての反復計算量推定装置の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態としての反復計算量推定装置のハードウェア構成の一例を示す図である。
【図１１】本発明の第３の実施の形態としての反復計算量推定装置が総反復回数を推定する動作を説明するフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１７】
（第１の実施の形態）
本発明の第１の実施の形態としての反復計算量推定装置１の機能ブロック構成を図１に示す。図１において、反復計算量推定装置１は、反復計算部１１と、反復計算履歴記憶部１２と、反復回数推定部１３とを備える。
【００１８】
ここで、反復計算量推定装置１は、図２に示すようなハードウェア要素によって構成可能である。図２において、反復計算量推定装置１は、ＣＰＵ（Central Processing Unit）１００１と、メモリ１００２と、出力装置１００３と、入力装置１００４とを含む。メモリ１００２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、補助記憶装置（ハードディスク等）等によって構成される。出力装置１００３は、ディスプレイ装置やプリンタ等のように、情報を出力する装置によって構成される。入力装置１００４は、キーボードやマウス等のように、ユーザ操作の入力を受け付ける装置によって構成される。この場合、反復計算部１１は、メモリ１００２に格納されるコンピュータ・プログラムを読み込んで実行するＣＰＵ１００１と、出力装置１００３と、入力装置１００４とによって構成される。また、反復計算履歴記憶部１２は、メモリ１００２によって構成される。また、反復回数推定部１３は、メモリ１００２に格納されるコンピュータ・プログラムを読み込んで実行するＣＰＵ１００１と、出力装置１００３とによって構成される。なお、反復計算量推定装置１およびその各機能ブロックのハードウェア構成は、上述の構成に限定されない。
【００１９】
反復計算部１１は、問題情報の解候補を求める計算を、その解候補の良さを表す評価値が要求条件を満たすまで繰り返す。問題情報および要求条件を表す情報は、例えば、入力装置１００４、メモリ１００２、可搬型記憶媒体、または、ネットワークを介して接続された他の装置等から入力される。例えば、要求情報を表す情報は、要求閾値によって表されていてもよい。評価値が低い（高い）ほど解候補の良さが高いことを示す場合、評価値が要求閾値を下回る（または上回る）ことが要求条件となる。そして、反復計算部１１は、評価値が要求条件を満たしたときに算出された解候補を、問題情報の解として出力する。出力先は、例えば、出力装置１００３、メモリ１００２、可搬型記憶媒体、または、ネットワークを介して接続された他の装置等であってもよい。ここで、反復計算部１１によって繰り返される計算は、前回までの計算において得られる情報を用いて今回の解候補を算出するよう定められた計算であってもよい。
【００２０】
また、反復計算部１１は、問題情報の解が算出されると、それまでの反復計算における評価値の列、要求条件を表す情報、および、総反復回数を、後述の反復計算履歴記憶部１２に保存する。ここで、総反復回数とは、評価値が要求条件を満たすまで繰り返された計算の回数である。
【００２１】
反復計算履歴記憶部１２は、問題情報毎に実行された反復計算について、その反復計算において繰り返された各計算で算出された評価値の列、要求条件を表す情報、および、総反復回数をそれぞれ表す情報を記憶する。
【００２２】
例えば、反復計算履歴記憶部１２に記憶される情報の一例を図３に示す。図３では、反復計算履歴記憶部１２には、Ｍ個の問題情報ｊ（ｊ＝１〜Ｍ、Mは1以上の整数）に対してそれぞれ実行された反復計算について、その履歴が記憶されている。各行は、問題情報ｊに対して実行された反復計算に関する履歴を表す。この例では、要求条件を表す情報は、要求閾値として表されている。問題情報ｊについて実行された反復計算の履歴は、評価値Ｅｊ＿１〜Ｅｊ＿Ｃｊの列、要求閾値Ｔｊ、および、総反復回数Ｃｊからなる。評価値Ｅｊ＿ｉ（ｉ＝１〜Ｃｊ）は、問題情報ｊに対して実行された反復計算におけるｉ回目の計算で算出された解候補の良さを表す評価値である。
【００２３】
反復回数推定部１３は、反復計算部１１によって実行中の反復計算における総反復回数を推定する。詳細には、反復回数推定部１３は、反復計算履歴記憶部１２に記憶された情報と、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報とに基づいて、実行中の反復計算における総反復回数を推定する。
【００２４】
例えば、反復回数推定部１３は、反復計算履歴記憶部１２に記憶された実行済みの反復計算に関する情報と、実行中の反復計算に関する情報とに基づいて、統計処理または学習処理を適用することにより、今回の総反復回数を推定してもよい。
【００２５】
以上のように構成された反復計算量推定装置１の動作を、図４を参照して説明する。なお、反復計算履歴記憶部１２には、既に、問題情報毎に実行済みの反復計算について、評価値の列、要求条件を表す情報、および、総反復回数を表す情報が記憶されているものとする。
【００２６】
まず、反復計算部１１は、問題情報および要求条件を表す情報を取得する（ステップＳ１）。
【００２７】
次に、反復計算部１１は、問題情報の解候補を算出する計算を行う（ステップＳ２）。
【００２８】
次に、反復計算部１１は、解候補の評価値を算出する（ステップＳ３）。なお、反復計算部１１は、このステップにおいて算出した評価値およびこれまでの計算の繰り返し回数を、メモリ１００２に、一時的に記憶するものとする。
【００２９】
次に、反復計算部１１は、評価値が要求条件を満たすか否かを判定する（ステップＳ４）。
【００３０】
ここで、評価値が要求条件を満たすと判定された場合について説明する。この場合、反復計算部１１は、この時点での解候補を解として出力する（ステップＳ５）。
【００３１】
次に、反復計算部１１は、反復計算部１１によってこれまでに算出された評価値の列、要求条件を表す情報、および、総反復回数を、反復計算履歴記憶部１２に記憶する（ステップＳ６）。そして、反復計算量推定装置１は、動作を終了する。
【００３２】
一方、ステップＳ４において、評価値が要求条件を満たさないと判定された場合について説明する。この場合、反復回数推定部１３は、総反復回数の推定処理の要否を判断する（ステップＳ７）。例えば、反復回数推定部１３は、ステップＳ２〜Ｓ３の計算が所定の回数繰り返されるごとに、推定処理を行うよう定められていてもよい。あるいは、反復回数推定部１３は、入力装置１００４等から入力される情報に基づいて、推定処理の要否を判断してもよい。
【００３３】
ここで、総反復回数の推定処理が必要でない場合、反復計算量推定装置１は、ステップＳ２に戻り、計算を繰り返す。
【００３４】
一方、総反復回数の推定処理が必要である場合、反復回数推定部１３は、反復計算履歴記憶部１２に記憶された情報と、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報とに基づいて、実行中の反復計算における総反復回数を推定する。そして、反復回数推定部１３は、推定した総反復回数を出力する（ステップＳ８）。
【００３５】
そして、反復計算量推定装置１は、ステップＳ２に戻り、計算を繰り返す。
【００３６】
なお、反復計算量推定装置１は、ステップＳ８における推定処理が完了してから、ステップＳ２に戻って計算を繰り返してもよい。あるいは、反復計算量推定装置１は、ステップＳ８における推定処理と並行して、ステップＳ２からの計算を繰り返してもよい。
【００３７】
以上で、反復計算量推定装置１の動作の説明を終了する。
【００３８】
次に、本発明の第１の実施の形態の効果について述べる。
【００３９】
本発明の第１の実施の形態としての反復計算量推定装置は、反復計算において、計算完了までの計算量をより精度よく推定することができる。
【００４０】
その理由について説明する。本実施の形態では、反復計算部が、問題情報の解候補を求める計算を、前記解候補の良さを表す評価値が要求条件を満たすまで計算を繰り返す。そして、反復計算履歴記憶部が、問題情報毎に実行された反復計算について、該反復計算において繰り返された各計算についてのそれまでの評価値の列、要求条件を表す情報、および、総反復回数をそれぞれ表す情報を記憶しておく。そして、反復回数推定部が、反復計算履歴記憶部に記憶された情報と、反復計算部によって実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報とに基づいて、実行中の反復計算における総反復回数を推定するからである。
【００４１】
このように、本実施の形態は、実行中の反復計算におけるそれまでの評価値の列だけでなく、過去に行われた実行済みの反復計算における評価値の列、要求条件および総反復回数の情報を利用して、実行中の反復計算の総反復回数を推定する。このため、本実施の形態は、実行中の反復計算の総反復回数を、より精度よく推定することができる。
【００４２】
なお、本実施の形態において、反復計算履歴記憶部に、過去に実行された反復計算に関する履歴がまだ記憶されていない場合も考えられる。また、何らかの理由により、反復計算履歴記憶部に記憶された情報が、今回の推定処理に適切でない場合も考えられる。この場合、反復回数推定部は、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報に基づいて、実行中の反復計算における総反復回数を推定してもよい。例えば、この場合、反復回数推定部は、実行中の反復計算におけるそれまでの評価値の列に基づいて、反復回数および評価値の関係を近似する近似関数を計算してもよい。近似関数の求め方としては、線形近似、指数近似、または、その他の各種の公知の技術が採用可能である。そして、反復回数推定部は、近似関数において要求条件を満たす評価値の近似値に対応する反復回数を、総反復回数として推定してもよい。
【００４３】
例えば、図５に示すように、実行中の反復計算における評価値の列Ｅ１，Ｅ２，Ｅ３，・・・Ｅｎに基づいて、近似関数Ｆ（ｋ）が計算されているとする。ここで、ｋは反復回数を表す。また、Ｆ（ｋ）は評価値を表す。このとき、要求条件が、要求閾値Ｔを下回ることである場合について説明する。この場合、反復回数推定部は、Ｆ（ｋ）＜Ｔを満たす最小の整数ｋを、総反復回数として推定してもよい。
【００４４】
なお、要求条件が、要求閾値Ｔを上回ることである場合も考えられる。例えば、近似関数Ｆ（ｋ）が増加関数である場合等である。この場合、反復回数推定部は、Ｆ（ｋ）＞Ｔを満たす最小の整数ｋを、総反復回数として推定すればよい。
【００４５】
このように構成することにより、本実施の形態は、反復計算履歴記憶部に、過去に実行された反復計算に関する履歴がまだ記憶されていない場合にも、総反復回数を精度よく推定することができる。
【００４６】
（第２の実施の形態）
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。なお、本実施の形態の説明において参照する各図面において、本発明の第１の実施の形態と同一の構成および同様に動作するステップには同一の符号を付して本実施の形態における詳細な説明を省略する。
【００４７】
まず、本発明の第２の実施の形態としての反復計算量推定装置２の機能ブロック構成を図６に示す。図６において、反復計算量推定装置２は、本発明の第１の実施の形態としての反復計算量推定装置１に対して、反復回数推定部１３に替えて反復回数推定部２３を備え、さらに、学習部２４を備える点が異なる。
【００４８】
ここで、反復計算量推定装置２は、図２を参照して説明した本発明の第１の実施の形態と同様のハードウェア要素によって構成可能である。この場合、学習部２４は、メモリ１００２に格納されるコンピュータ・プログラムを読み込んで実行するＣＰＵ１００１によって構成される。なお、反復計算量推定装置２およびその各機能ブロックのハードウェア構成は、上述の構成に限定されない。
【００４９】
反復回数推定部２３は、後述の学習部２４によって学習済みの反復回数推定式に、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報を適用することにより、実行中の反復計算の総反復回数を推定する。
【００５０】
学習部２４は、反復計算履歴記憶部１２に記憶された情報（問題情報毎に実行された反復計算についての評価値の列、要求条件を表す情報および総反復回数）に基づいて、反復回数推定式を学習する。例えば、反復回数推定式は、Ｎ個の評価値の列および要求条件を表す情報からなるＮ＋１個の変数を入力とし、総反復回数を導出する式であってもよい。学習には、公知の機械学習技術を採用可能である。なお、Ｎは、１以上の任意の整数である。
【００５１】
また、学習部２４は、反復回数推定式の学習処理を、反復計算部１１により実行中の反復計算についての反復回数推定部２３による推定処理とは非同期に行ってもよい。例えば、学習部２４は、所定期間が経過する毎に反復回数推定式の学習処理を行い、反復回数推定式を更新してもよい。また、例えば、学習部２４は、反復計算履歴記憶部１２に追加される情報が所定量に達する度に反復回数推定式の学習処理を行い、反復回数推定式を更新してもよい。あるいは、学習部２４は、反復計算部１１による反復計算の実行中における定められたタイミングで反復回数推定式の学習処理を行い、反復回数推定式を更新してもよい。あるいは、学習部２４は、入力装置１００４から学習処理を指示する情報が入力されたことに応じて反復回数推定式の学習処理を行い、反復回数推定式を更新してもよい。
【００５２】
以上のように構成された反復計算量推定装置２の動作について、図面を参照して説明する。なお、反復計算履歴記憶部１２には、既に、問題情報ごと実行された反復計算について、評価値の列、要求条件を表す情報、および、総反復回数を表す情報が記憶されているものとする。
【００５３】
まず、反復計算量推定装置２が反復回数推定式を学習する動作を図７に示す。
【００５４】
図７では、まず、学習部２４は、学習のタイミングであるか否かを判断する（ステップＳ１１）。
【００５５】
前述のように、学習のタイミングであるか否かの判断は、反復計算履歴記憶部１２に追加される情報が所定量に達したか否か、前回の学習から所定期間が経過したか否か、または、入力装置１００４から学習処理を指示する情報が入力されたか否か等に応じて行われる。
【００５６】
ここで、学習のタイミングでない場合、反復計算量推定装置２は、動作を終了する。
【００５７】
一方、学習のタイミングである場合、学習部２４は、反復計算履歴記憶部１２に記憶された情報に基づいて、反復回数推定式を学習する（ステップＳ１２）。
【００５８】
前述のように、反復回数推定式は、Ｎ個の評価値の列および要求条件を表す情報からなるＮ＋１個の変数を入力とし、総反復回数を導出する式であってもよい。
【００５９】
以上で、反復計算量推定装置２は、反復回数推定式の学習動作を終了する。
【００６０】
次に、反復計算量推定装置２が総反復回数を推定する動作を図８に示す。
【００６１】
図８では、まず、反復計算量推定装置２は、ステップＳ１〜Ｓ７については、本発明の第１の実施の形態と同様に動作する。
【００６２】
次に、ステップＳ７で推定処理が必要である場合、反復回数推定部２３は、学習済みの反復回数推定式に、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報を適用する。これにより、反復回数推定部２３は、実行中の反復計算における総反復回数を推定する（ステップＳ２１）。
【００６３】
以上で、反復計算量推定装置２が総反復回数を推定する動作の説明を終了する。
【００６４】
次に、本発明の第２の実施の形態の効果について述べる。
【００６５】
本発明の第２の実施の形態としての反復計算量推定装置は、反復計算において、計算完了までの計算量を、さらに精度よく推定することができる。
【００６６】
その理由について説明する。本実施の形態では、本発明の第１の実施の形態と同様の構成に加えて、学習部が、反復計算履歴記憶部に記憶された実行済みの反復計算ごとの評価値の列、要求条件を表す情報および総反復回数に基づいて、反復回数推定式を学習する。そして、反復回数推定部が、学習済みの反復回数推定式に、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報を適用することにより、実行中の反復計算の総反復回数を推定するからである。
【００６７】
このように、本実施の形態は、実行中の反復計算におけるそれまでの評価値の列および要求条件を表す情報を、過去に行われた反復計算に関する情報に基づき学習した反復回数推定式に適用することにより、実行中の反復計算の総反復回数を推定する。このため、本実施の形態は、実行中の反復計算における情報だけを利用する場合と比較して、実行中の反復計算の総反復回数を、さらに精度よく推定することができる。
【００６８】
（第３の実施の形態）
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。なお、本実施の形態の説明において参照する各図面において、本発明の第１の実施の形態と同一の構成および同様に動作するステップには同一の符号を付して本実施の形態における詳細な説明を省略する。
【００６９】
まず、本発明の第３の実施の形態としての反復計算量推定装置３の機能ブロック構成を図９に示す。図９において、反復計算量推定装置３は、本発明の第２の実施の形態としての反復計算量推定装置２に対して、反復計算部１１に替えて反復計算部３１を備える点が異なる。反復計算部３１は、計算機クラスタ３１１を含む。さらに、反復計算量推定装置３は、本発明の第２の実施の形態としての反復計算量推定装置２に対して、計算リソース量決定部３５と、計算機割当部３６とを備える点が異なる。
【００７０】
ここで、反復計算量推定装置３は、図１０に示すようなハードウェア要素によって構成可能である。図１０において、反復計算量推定装置３は、計算機２０００と、１つ以上の計算機３０００とによって構成される。計算機２０００は、ＣＰＵ１００１と、メモリ１００２と、出力装置１００３と、入力装置１００４と、ネットワークインタフェース２００５とを含む。計算機３０００は、ＣＰＵ３００１と、メモリ３００２と、ネットワークインタフェース３００５とを含む。計算機２０００は、ネットワークインタフェース２００５を介してネットワークに接続される。計算機３０００は、ネットワークインタフェース３００５を介してネットワークに接続される。また、計算機２０００および計算機３０００は、ネットワークを介して互いに通信可能となっている。この場合、計算リソース量決定部３５および計算機割当部３６は、それぞれ、計算機２０００においてメモリ１００２に格納されるコンピュータ・プログラムを読み込んで実行するＣＰＵ１００１によって構成される。また、計算機クラスタ３１１は、計算機３０００の群においてメモリ３００２を用いて動作するＣＰＵ３００１によって構成される。なお、図１０には、３つのコンピュータ装置３０００が示されているが、本実施の形態において計算機クラスタ３１１を構成する計算機３０００の数は限定されない。また、計算機２０００および計算機３０００の群は、１つの種類の計算機で構成されてもよいし、複数の種類の計算機で構成されてもよい。また、計算機２０００が、計算機３０００の群の１つとして機能するよう構成されていてもよい。
【００７１】
反復計算部３１は、評価値が要求条件を満たすまで解候補の計算および評価値の算出を繰り返す処理を、計算機クラスタ３１１のうち後述の計算機割当部３６によって割り当てられた１つ以上の計算機３０００を用いて実行する。
【００７２】
計算リソース量決定部３５は、反復回数推定部２３によって推定された総反復回数に基づいて、要求時間内に、評価値が要求条件を満たすまでの反復計算を完了するために必要な計算リソース量を決定する。要求時間は、例えば、入力装置１００４、メモリ１００２、可搬型記憶媒体、または、ネットワークを介して接続された他の装置等から入力される。
【００７３】
計算機割当部３６は、計算機クラスタ３１１を構成する計算機３０００のうち、決定された計算リソース量に基づく１つ以上の計算機３０００を、反復計算部３１に割り当てる。例えば、計算機割当部３６は、計算機クラスタ３１１を構成する計算機３０００のうち、それぞれの有する計算リソース量の合計が、決定された計算リソース量以上となるような１つ以上の計算機３０００を割り当ててもよい。なお、計算リソース量に基づく計算機３０００の割り当てには、各種の公知の技術を採用すればよい。
【００７４】
以上のように構成された反復計算量推定装置３の動作を、図１１を参照して説明する。
【００７５】
図１１では、まず、反復計算部３１は、問題情報および要求条件を表す情報に加えて、要求時間を表す情報を取得する（ステップＳ３１）。
【００７６】
その後、反復計算量推定装置３は、ステップＳ２〜Ｓ７、Ｓ２１まで本発明の第２の実施の形態と同様に動作して、実行中の反復計算の総反復回数を推定する。
【００７７】
次に、計算リソース量決定部３５は、推定された総反復回数と、要求時間とに基づいて、要求時間内に、評価値が要求条件を満たすまでの反復計算を完了するために必要な計算リソース量を決定する（ステップＳ３２）。
【００７８】
次に、計算機割当部３６は、計算機クラスタ３１１を構成する計算機３０００のうち、決定された計算リソース量に基づく１つ以上の計算機３０００を、反復計算部３１に割り当てる（ステップＳ３３）。
【００７９】
そして、反復計算量推定装置３の動作は、ステップＳ２に戻る。なお、以降のステップＳ２〜Ｓ３では、反復計算部３１は、ステップＳ３３で割り当てられた１つ以上の計算機３０００を用いて、解候補およびその評価値の計算を実行する。
【００８０】
以上で、反復計算量推定装置３の動作の説明を終了する。
【００８１】
次に、本発明の第３の実施の形態の効果について述べる。
【００８２】
本発明の第３の実施の形態としての反復計算量推定装置は、計算完了までの計算量が未知の反復計算を、要求時間内に完了させることができる。
【００８３】
その理由について説明する。本実施の形態では、本発明の第２の実施の形態と同様の構成により、実行中の反復計算の総反復回数を推定する。加えて、計算リソース量決定部が、推定された総反復回数に基づいて、要求時間内に、評価値が要求条件を満たすまでの反復計算を完了するために必要な計算リソース量を決定する。そして、計算機割当部が、計算機クラスタのうち、決定された計算リソース量に基づく１つ以上の計算機を、反復計算部に割り当てる。そして、以降では、反復計算部が、割り当てられた計算機を用いて反復計算を実行するからである。
【００８４】
このように、本実施の形態は、推定した総反復回数に応じて必要な計算リソース量を決定することにより、反復計算に用いる計算機を動的に変更することができるので、要求時間内に反復計算を完了させることができる。
【００８５】
なお、本実施の形態では、本発明の第２の実施の形態の構成に対して、反復計算部を計算機クラスタによって実現し、計算リソース量決定部および計算機割当部をさらに備える構成について説明した。これに限らず、本実施の形態の反復計算部、計算リソース量決定部、および、計算機割当部は、本発明の第１の実施の形態の構成に対して適用することも可能である。
【００８６】
また、上述した本発明の各実施の形態において、要求条件は、評価値が要求閾値を上回る（または下回る）ことである例を中心に説明した。これに限らず、要求条件は、評価値に基づき判定されるその他の条件であってもよい。
【００８７】
また、上述した本発明の各実施の形態において、反復計算量推定装置の各機能ブロックが、記憶装置またはＲＯＭに記憶されたコンピュータ・プログラムを実行するＣＰＵによって実現される例を中心に説明した。これに限らず、各機能ブロックの一部、全部、または、それらの組み合わせが専用のハードウェアにより実現されていてもよい。
【００８８】
また、上述した本発明の各実施の形態において、反復計算量推定装置を構成する機能ブロックは、複数の装置に分散されて実現されてもよい。
【００８９】
また、上述した本発明の各実施の形態において、各フローチャートを参照して説明した反復計算量推定装置の動作を、本発明のコンピュータ・プログラムとしてコンピュータ装置の記憶装置（記憶媒体）に格納しておいてもよい。そして、係るコンピュータ・プログラムを当該ＣＰＵが読み出して実行するようにしてもよい。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコードあるいは記憶媒体によって構成される。
【００９０】
また、上述した各実施の形態は、適宜組み合わせて実施されることが可能である。
【００９１】
また、本発明は、上述した各実施の形態に限定されず、様々な態様で実施されることが可能である。
【符号の説明】
【００９２】
１、２、３    反復計算量推定装置
１１、３１    反復計算部
１２    反復計算履歴記憶部
１３、２３    反復回数推定部
２４    学習部
３５    計算リソース量決定部
３６    計算機割当部
３１１  計算機クラスタ
２０００、３０００    計算機
１００１、３００１    ＣＰＵ
１００２、３００２    メモリ
１００３    出力装置
１００４    入力装置
２００５、３００５    ネットワークインタフェース
【図１】
2017097392.tif 000003
【図２】
2017097392.tif 000004
【図３】
2017097392.tif 000005
【図４】
2017097392.tif 000006
【図５】
2017097392.tif 000007
【図６】
2017097392.tif 000008
【図７】
2017097392.tif 000009
【図８】
2017097392.tif 000010
【図９】
2017097392.tif 000011
【図１０】
2017097392.tif 000012
【図１１】
2017097392.tif 000013