(57)【特許請求の範囲】
【請求項１】
計算機システムが使用するリソースの量と計算時間との関係を評価する、コンピュータが実行する性能評価方法であって、
使用するリソースの量を変えて前記計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定し、
前記測定された複数の第１の計算時間それぞれと、前記評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出し、
前記評価モデルに前記決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、前記決定したパラメータの値が前記算出した変動量だけ変動することによって受ける影響を示す情報を出力する、性能評価方法。
【請求項２】
前記変動量の算出では、各測定された第１の計算時間と当該第１の計算時間に対応する第２の計算時間との差が前記閾値以下であることを、パラメータの値の変動量を示す自由変数を用いて表した複数の不等式を生成し、前記複数の不等式の集合を数式処理することで前記自由変数が取り得る値を算出する、請求項１記載の性能評価方法。
【請求項３】
前記数式処理は、前記複数の不等式の集合に対し限量子消去法を適用することを含む、請求項２記載の性能評価方法。
【請求項４】
前記閾値として、各測定された第１の計算時間と前記評価モデルに前記決定したパラメータの値を適用することで算出される当該第１の計算時間に対応する第２の計算時間との差のうちの最大値を用いる、請求項１記載の性能評価方法。
【請求項５】
使用するリソースの量を変えて計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間を示す測定情報を記憶する記憶部と、
前記測定情報を用いてリソース量と計算時間との関係を評価する演算部と、
を有し、前記演算部は、
前記測定情報に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定し、
前記測定情報が示す複数の第１の計算時間それぞれと、前記評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出し、
前記評価モデルに前記決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、前記決定したパラメータの値が前記算出した変動量だけ変動することによって受ける影響を示す情報を出力する、情報処理装置。
【請求項６】
計算機システムが使用するリソースの量と計算時間との関係を評価するためのプログラムであって、コンピュータに、
使用するリソースの量を変えて前記計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定し、
前記測定された複数の第１の計算時間それぞれと、前記評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出し、
前記評価モデルに前記決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、前記決定したパラメータの値が前記算出した変動量だけ変動することによって受ける影響を示す情報を出力する、処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は性能評価方法、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
現在、大量のデータを処理する場合や複雑な計算を行う場合などに、多数のプロセッサを備えるような大きなリソースをもつ計算機システムを利用することがある。このような大規模な計算機システムを利用するユーザは、例えば、投入するプログラムに割り当てるリソースの量（例えば、プロセッサ数）とプログラムの実行が完了するまでの計算時間との関係を予測し、所望の量のリソースを予約する。もし予測に誤りがあると、意図した日時までに計算が終了しない、または、計算が早く終了して予約していたリソースが無駄になる、という問題が生じる。このため、計算時間をどのように予測するかが重要となる。
【０００３】
この点、計算時間τが、プロセッサ数ｐと問題の大きさｘと利用する計算機システムに応じたパラメータｃとに依存することを示すモデル式が提案されている。このモデル式によれば、プロセッサ数ｐが大きいほど並列化オーバヘッドが大きくなる。モデル式を使用する場合、例えば、プロセッサ数ｐを変えつつサンプル問題の計算時間τを測定し、プロセッサ数ｐと測定した計算時間τとの組をモデル式にフィッティングして、パラメータｃを決定する。パラメータｃが決定されて計算機システムに応じたモデルが生成されると、投入するプログラムに対するプロセッサ数ｐと計算時間τとの関係を予測できる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】折居茂夫，“時間モデルを用いた並列処理の性能評価−並列化部に隠れた並列オーバヘッド−”，情報処理学会研究報告  ハイパフォーマンスコンピューティング（ＨＰＣ），２０１１−ＨＰＣ−１３０  Ｎｏ．１，２０１１年７月
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、測定値と予測値とが完全に一致するようなモデルを生成できる（例えば、グラフにおいてモデルが示す曲線上に全ての測定値が乗る）ことは少なく、少なくとも一部の測定値とモデルによる予測値との間には残差が存在することが多い。このため、測定値をモデル式にフィッティングしてパラメータの値を決定する過程において、測定値のばらつき方に応じて、生成したモデルの予測精度が低下してしまう可能性がある。一方、小規模なサンプル問題を解くことで生成したモデルを大規模な問題に適用すると、少しの精度低下が大きな計算時間の誤差になって現れる。例えば、１％の精度低下が数十時間の計算時間の誤差になる可能性がある。このため、モデルから計算時間を予測するにあたっては、予測精度（例えば、どの程度の誤差が生じ得るか）を評価できることが好ましい。
【課題を解決するための手段】
【０００６】
一側面では、計算機システムが使用するリソースの量と計算時間との関係を評価する、コンピュータが実行する性能評価方法が提供される。性能評価方法では、使用するリソースの量を変えて計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定する。測定された複数の第１の計算時間それぞれと、評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出する。評価モデルに決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、決定したパラメータの値が算出した変動量だけ変動することによって受ける影響を示す情報を出力する。
【０００７】
また、一側面では、使用するリソースの量を変えて計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間を示す測定情報を記憶する記憶部と、測定情報を用いてリソース量と計算時間との関係を評価する演算部と、を有する情報処理装置が提供される。演算部は、測定情報に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定する。演算部は、測定情報が示す複数の第１の計算時間それぞれと、評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出する。演算部は、評価モデルに決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、決定したパラメータの値が算出した変動量だけ変動することによって受ける影響を示す情報を出力する。
【０００８】
また、一側面では、計算機システムが使用するリソースの量と計算時間との関係を評価するためのプログラムが提供される。プログラムを実行するコンピュータは、使用するリソースの量を変えて計算機システムにサンプルプログラムを複数回実行させることで測定された複数の第１の計算時間に基づいて、リソース量と計算時間との関係を算出するための評価モデルに用いられるパラメータの値を決定する。測定された複数の第１の計算時間それぞれと、評価モデルに従って算出される当該第１の計算時間に対応する第２の計算時間との差が、閾値まで広がることを許容した場合の、パラメータの値の変動量を算出する。評価モデルに決定したパラメータの値を適用することで示されるリソース量と計算時間との関係が、決定したパラメータの値が算出した変動量だけ変動することによって受ける影響を示す情報を出力する。
【発明の効果】
【０００９】
一側面では、計算機システムが要する計算時間の予測の精度を評価できる。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態の情報処理装置を示す図である。
【図２】第２の実施の形態の情報処理システムを示す図である。
【図３】シミュレーション装置のハードウェア例を示すブロック図である。
【図４】シミュレーション装置の機能例を示すブロック図である。
【図５】計算時間予測の手順例を示すフローチャートである。
【図６】パラメータの取り得る値の例を示すグラフである。
【図７】計算時間の予測結果の例を示す第１のグラフである。
【図８】計算時間の予測結果の例を示す第２のグラフである。
【発明を実施するための形態】
【００１１】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。情報処理装置１０は、計算機システム２０が使用するリソースの量と計算時間との関係を評価する。リソース量は、例えば、プロセッサ数であり、計算機システム２０は複数のプロセッサを並列に用いてプログラムを実行できる。計算時間は、例えば、使用する複数のプロセッサのうち何れかのプロセッサで投入したプログラムの実行が開始されてから、それら複数のプロセッサの全てで投入したプログラムの実行が終了するまでの時間である。情報処理装置１０は、ユーザが操作する端末装置としてのクライアントコンピュータでもよいし、端末装置からアクセス可能なサーバコンピュータでもよい。情報処理装置１０は、ネットワークを介して、リソース量を指定して計算機システム２０にプログラムの実行を指示できる。
【００１２】
情報処理装置１０は、記憶部１１と演算部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。演算部１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサでもよいし、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などのプロセッサ以外の電子回路でもよい。プロセッサは、例えば、記憶部１１または他のメモリに記憶されたプログラムを実行する。プロセッサは、プログラムの命令を実行するための演算器やレジスタ以外に、他の電子回路を含んでもよい。
【００１３】
記憶部１１は、リソース量（例えば、プロセッサ数）と測定された計算時間とを対応付けた測定情報１１ａを記憶する。測定情報１１ａが示す複数の計算時間は、リソース量を変えて計算機システム２０にサンプルプログラムを複数回実行させることで測定される。サンプルプログラムの実行指示、計算時間の測定、測定情報１１ａの生成などは、情報処理装置１０が行ってもよいし、他の情報処理装置が行ってもよい。また、測定情報１１ａは、性能評価を行う毎に生成してもよいし、予め生成したものを利用してもよい。
【００１４】
サンプルプログラムによって解く問題は、好ましくは、後述の性能評価を行った後に計算機システム２０に実行させる本番プログラムによって解く問題よりも、十分に小規模なものとする。ただし、サンプルプログラムによって解く問題と本番プログラムによって解く問題とは、好ましくは、同種の問題（例えば、計算アルゴリズムが類似しているもの）とする。サンプルプログラムと本番プログラムを同一のものとし、処理するデータの量を変えることで問題の規模を変えるようにしてもよい。これにより、小規模な問題を通じて生成された計算機システム２０のモデルを、大規模な問題に適用しやすくなる。
【００１５】
演算部１２は、リソース量と計算時間の関係を算出するためのモデル式と、記憶部１１に記憶された測定情報１１ａとを用いて、計算機システム２０についてのリソース量と計算時間との関係を評価する。モデル式は、予め用意されており、プログラムを実行する計算機システムに依存するパラメータＣを含む（２以上のパラメータを含んでもよい）。パラメータＣは、例えば、プロセッサやプロセッサ間の接続に関するアーキテクチャに依存し、また、解く問題の種類に依存することもある。演算部１２は、測定情報１１ａを用いて、モデル式に含まれるパラメータＣの値を決定する。例えば、演算部１２は、最小二乗法により、各リソース量についての残差（測定された計算時間とモデルから予測される計算時間との差）の二乗和が最小になるように、パラメータＣの値を決定する。
【００１６】
また、演算部１２は、モデル式と決定したパラメータＣの値と測定情報１１ａとを用いて、誤差を考慮したパラメータＣの変動量ΔＣの値を算出する。変動量ΔＣは、測定情報１１ａが示す各リソース量について、測定された計算時間とモデルから予測される計算時間との差が閾値まで広がることを許容した場合に、パラメータＣの値が上記の決定した値からどの程度変動し得るかを示す。変動量ΔＣの値は、数式処理によって算出し得る。
【００１７】
例えば、演算部１２は、ｎ個（ｎは２以上の整数）の計算時間が測定されているとき、測定された計算時間と誤差を考慮したモデル上の計算時間との差が閾値以下であることを示すｎ個の不等式を生成する。各リソース量に対する誤差を考慮したモデル上の計算時間は、モデル式のパラメータＣをＣ＋ΔＣに置き換え、置き換えた式にリソース量と上記の決定したパラメータＣの値を代入することで得られる。これにより、変動量ΔＣを自由変数として含むｎ個の不等式が生成される。閾値は、例えば、パラメータＣの値を決定するとき算出した残差の最大値、または、ｎ個の不等式が解をもつ条件下での最小値（通常は残差の最小値より大きい）とする。ただし、閾値を、両者の間の任意の値としてもよい。
【００１８】
生成したｎ個の不等式に対し、演算部１２は、例えば、限量子消去（ＱＥ：Quantifier Elimination）法を適用して、自由変数である変動量ΔＣの取り得る値を算出する。測定した計算時間のばらつきが大きく残差が平均的に大きい場合や、測定した計算時間の中に特異点があり一部の残差のみが大きい場合などに、変動量ΔＣの値が大きくなり得る。限量子消去については、例えば、次の書籍に説明がある：穴井宏和  横山和弘，“ＱＥの計算アルゴリズムとその応用−数式処理による最適化”，東京大学出版会，２０１１年８月２５日。限量子消去の具体例については、第２の実施の形態でも説明する。
【００１９】
そして、演算部１２は、モデル式に上記の決定したパラメータＣの値を代入することで算出されるリソース量と計算時間の関係が、パラメータＣの値が変動量ΔＣの値だけ変動することでどのような影響を受けるかを示す情報を出力する。例えば、演算部１２は、情報処理装置１０または他の情報処理装置に接続されたディスプレイに、変動量ΔＣの影響を示す情報を表示させる。変動量ΔＣの影響を示す情報として、例えば、モデル式のパラメータＣに上記の決定した値を代入したモデルを示す曲線と、パラメータＣにＣ＋ΔＣに相当する値を代入したモデルを示す曲線とを表示するための情報が考えられる。また、変動量ΔＣの影響を示す情報として、例えば、あるリソース量に対応する計算時間が、変動量ΔＣを考慮すると、考慮しない場合より最大で何％変化するかを示す情報も考えられる。
【００２０】
第１の実施の形態の情報処理装置１０によれば、測定情報１１ａからパラメータＣの値を決定することで生成したモデルが、どの程度の精度で計算機システム２０の計算時間を予測できるかを定量的に評価することができる。このため、サンプル問題よりも大規模な問題を解くプログラムを大きなリソースを用いて計算機システム２０に実行させるときでも、モデルによる計算時間の予測結果を効果的に利用できるようになる。例えば、ユーザは、予測精度が許容できるとき、予測誤差を考慮して計算機システム２０のリソースを予約することができる。一方、予測精度が許容できないとき、より精度の高いモデルを生成するため、演算部１２が出力した情報を手掛かりに測定情報１１ａの中から異常な測定値を探し、異常な測定値を除去することや測定をやり直すなどの措置をとることができる。
【００２１】
［第２の実施の形態］
図２は、第２の実施の形態の情報処理システムを示す図である。第２の実施の形態の情報処理システムは、シミュレーション装置１００とサーバ装置２１０〜２４０を含む。シミュレーション装置１００およびサーバ装置２１０〜２４０は、ネットワーク３１に接続されている。なお、シミュレーション装置１００は、前述の情報処理装置１０の一例であり、サーバ装置２１０〜２４０の集合は、前述の計算機システム２０の一例である。
【００２２】
シミュレーション装置１００は、ユーザが操作する端末装置としてのコンピュータである。シミュレーション装置１００は、サーバ装置２１０〜２４０にサンプルプログラムを実行させて計算時間を測定し、測定結果からサーバ装置２１０〜２４０の性能を評価したモデルを生成する。また、シミュレーション装置１００は、ユーザからの指示に応じて、サーバ装置２１０〜２４０が備えるリソースの一部または全部を、リソース量および使用期間を指定して予約し、サーバ装置２１０〜２４０にプログラムを実行させる。
【００２３】
サーバ装置２１０〜２４０は、ユーザが予約したリソースを用いてユーザから取得したプログラムを実行するサーバコンピュータである。サーバ装置２１０〜２４０の集合は、複数のプロセッサを並列に用いて計算を行うことができる並列処理システムであると言える。ユーザから指定されるリソース量には、プロセッサ数が含まれる。例えば、ジョブを制御するサーバ装置が、シミュレーション装置１００からプログラムの実行の指示を受け付け、ジョブが割り当てられていない空きプロセッサの中から指定された数のプロセッサを選択し、選択したプロセッサにジョブを割り当てて計算を開始させる。
【００２４】
図３は、シミュレーション装置のハードウェア例を示すブロック図である。シミュレーション装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１は、第１の実施の形態の演算部１２の一例であり、ＲＡＭ１０２やＨＤＤ１０３は、第１の実施の形態の記憶部１１の一例である。
【００２５】
ＣＰＵ１０１は、プログラムの命令を実行する演算器を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、シミュレーション装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。
【００２６】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや計算に用いられるデータを一時的に記憶する揮発性メモリである。なお、シミュレーション装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。
【００２７】
ＨＤＤ１０３は、ＯＳ（Operating System）やファームウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性記憶装置である。なお、シミュレーション装置１００は、フラッシュメモリなどの他の種類の不揮発性記憶装置を備えてもよく、複数の不揮発性記憶装置を備えてもよい。
【００２８】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、シミュレーション装置１００に接続されたディスプレイ３２に画像を出力する。ディスプレイ３２としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００２９】
入力信号処理部１０５は、シミュレーション装置１００に接続された入力デバイス３３から入力信号を取得し、ＣＰＵ１０１に通知する。入力デバイス３３としては、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００３０】
ディスクドライブ１０６は、記録媒体３４に記録されたプログラムやデータを読み取る駆動装置である。記録媒体３４として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１からの命令に従って、記録媒体３４から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３１】
通信インタフェース１０７は、ネットワーク３１を介してサーバ装置２１０〜２４０と通信を行えるインタフェースである。通信インタフェース１０７は、有線網に接続する有線インタフェースでもよいし、無線網に接続する無線インタフェースでもよい。
【００３２】
なお、サーバ装置２１０〜２４０も、シミュレーション装置１００と同様のハードウェア構成によって実現することができる。ただし、サーバ装置２１０〜２４０は、ディスプレイや入力デバイスに接続されていなくてもよく、画像信号処理部や入力信号処理部やディスクドライブを備えていなくてもよい。また、サーバ装置２１０〜２４０は、それぞれ複数のＣＰＵやＲＡＭやＨＤＤを備えていてもよい。
【００３３】
図４は、シミュレーション装置の機能例を示すブロック図である。シミュレーション装置１００は、測定部１１１、測定情報記憶部１１２、モデル生成部１１３、誤差判定部１１４および評価結果表示部１１５を有する。測定情報記憶部１１２は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域として実現できる。測定部１１１、モデル生成部１１３、誤差判定部１１４および評価結果表示部１１５は、例えば、ＣＰＵ１０１が実行するプログラムのモジュールとして実現できる。
【００３４】
測定部１１１は、サーバ装置２１０〜２４０を含む並列処理システムに、プロセッサ数を変えながらサンプルプログラムを複数回実行させ、この並列処理システムが要する計算時間を測定する。例えば、測定部１１１は、プロセッサ数として、１０，２０，３０，４０，５０，６０，７０，８０．９０，１００，１１０，１２０の１２通りを指定し、それぞれの場合の計算時間を測定する。プロセッサ数が多くなると、並列化のオーバヘッドも大きくなるため、プロセッサ数が多いほど計算時間が短くなるとは限らない。
【００３５】
なお、サンプルプログラムによって解く問題は、サーバ装置２１０〜２４０を用いて解きたい大規模な問題と同種のもの（例えば、計算アルゴリズムが類似するもの）で小規模なものとする。計算時間は、使用する複数のプロセッサの何れか１つが計算を開始してから、全てのプロセッサが計算を終了するまでの時間とする。計算時間は、サーバ装置２１０〜２４０で生成されたログに基づいて算出してもよく、測定部１１１がコマンドを送信してからレスポンスを受信するまでの時間を測定することで算出してもよい。
【００３６】
測定情報記憶部１１２は、測定部１１１の測定結果を示す測定情報を記憶する。測定情報には、プロセッサ数ｐiと測定された計算時間ｄi（ｉ＝１，２，…，ｎ）との組を示すエントリがｎ個（ｎは２以上の整数）含まれる。例えば、測定部１１１が１２通りのプロセッサ数を指定して計算時間を測定した場合、測定情報は１２個のエントリを含む。
【００３７】
モデル生成部１１３は、測定情報記憶部１１２に記憶された測定情報をモデル式にフィッティングすることで、サーバ装置２１０〜２４０に対応するモデルを生成する。第２の実施の形態で使用するモデル式は、パラメータ集合Ｃとプロセッサ数ｐと問題の大きさｘとから、計算時間を計算する関数Ｔ（Ｃ，ｐ，ｘ）である。パラメータ集合Ｃは、１またはそれ以上のパラメータを含む。各パラメータは、サーバ装置２１０〜２４０のアーキテクチャや解きたい問題の種類に応じた値を取る。モデル生成部１１３は、問題の大きさｘを固定して、測定情報が示すプロセッサ数ｐiと計算時間ｄiの組に対して最小二乗法を適用することで、各パラメータｃj（ｊ＝１，２，…）の値を決定する。
【００３８】
誤差判定部１１４は、モデル生成部１１３がパラメータｃjの値を決定して生成したモデルの精度を評価する。具体的には、誤差判定部１１４は、測定された計算時間ｄiをモデル式にフィッティングする過程でパラメータｃjの値に生じる誤差を推定し、パラメータｃjの誤差が計算時間の予測にどの程度の影響を与えるか定量的に評価する。
【００３９】
まず、誤差判定部１１４は、各パラメータｃjの値の変動量Δｃjを自由変数として用いて、測定情報が示すｎ通りのプロセッサ数ｐiに対応するｎ個の不等式を生成する。各不等式は、測定した計算時間ｄiとモデル式に従って算出される計算時間Ｔ（Ｃ＋ΔＣ，ｐi，ｘi）との差を、閾値ｅまで許容することを示す。ΔＣは、変動量Δｃjの集合である。パラメータｃjにモデル生成部１１３が決定した値を代入し、閾値ｅを所定の方法で決定することで、ｎ個の不等式は自由変数として変動量Δｃjのみを含むことになる。そして、誤差判定部１１４は、生成したｎ個の不等式を、後述する限量子消去（ＱＥ）法を用いて解くことで、変動量の集合ΔＣの取り得る値の範囲を算出する。これにより、モデルから予測される計算時間の変動する範囲を算出することができる。
【００４０】
評価結果表示部１１５は、モデル生成部１１３が算出したパラメータｃjの値を用いたモデルの曲線と、誤差判定部１１４が算出した誤差を考慮したパラメータｃj＋Δｃjの値を用いたモデルの曲線とを合わせて、ディスプレイ３２に表示する。これにより、シミュレーション装置１００のユーザは、モデルの精度を視覚的に確認することができる。また、評価結果表示部１１５は、ユーザからプロセッサ数が指定されると、最小二乗法によって生成したモデルを用いて算出される計算時間が、最大で何％増加または減少する可能性があるかを算出し、予測される計算時間とその誤差をディスプレイ３２に表示する。これにより、ユーザは、計算時間の予測誤差を定量的に確認することができる。
【００４１】
ここで、前述の限量子消去（ＱＥ）について説明する。限量子消去は、一階述語論理として記述された限量子を含む論理式を、限量子を含まない等価な式に変換する数式処理である。入力される論理式は、代数的等式、代数的不等式、限量子（全称限量子および存在限量子）および論理演算子（論理積や論理和など）を用いて記述することができる。入力される論理式に、限量子が付された束縛変数の他に、限量子が付されていない自由変数が含まれる場合は、出力される式は自由変数の取り得る値の範囲を示す。
【００４２】
例えば、以下に示す数式（１）の左辺は、全てのｘの値について括弧内の論理式が成立することを要求している。限量子消去法により論理式から束縛変数ｘを消去すると、数式（１）の右辺に示すように、左辺の論理式が成立するための自由変数ａ，ｂ，ｃの条件を示す式が算出される。また、以下に示す数式（２）の左辺は、括弧内の論理式が成立するようなｘ1，ｘ2の値の組が少なくとも１つ存在することを要求している。限量子消去法により論理式から束縛変数ｘ1，ｘ2を消去すると、数式（２）の右辺に示すように、左辺の論理式が成立するための自由変数ｙの条件を示す式が算出される。このような限量子消去は、数式処理を行うアプリケーションソフトウェアに実装されていることがある。
【００４３】
【数１】
0005765266.tif 000002
【００４４】
【数２】
0005765266.tif 000003
【００４５】
図５は、計算時間予測の手順例を示すフローチャートである。
（ステップＳ１）測定部１１１は、問題の大きさｘを固定した状態で（例えば、同じサンプルプログラムと同じデータを用いて）、プロセッサ数ｐを変えながらサーバ装置２１０〜２４０にサンプルプログラムを実行させ、ｎ通りの計算時間ｄを測定する。例えば、測定部１１１は、ｐ＝１０，２０，…，１２０の１２通りの計算時間ｄを測定する。測定部１１１は、プロセッサ数ｐiと測定した計算時間ｄiを関連付けた測定情報を生成し、生成した測定情報を測定情報記憶部１１２に格納する。
【００４６】
（ステップＳ２）モデル生成部１１３は、測定情報記憶部１１２に記憶された測定情報が示すｎ個の計算時間ｄiを、モデル式である関数Ｔ（Ｃ，ｐ，ｘ）にフィッティングすることで、パラメータ集合Ｃに属する各パラメータｃjの値を決定する。フィッティングでは、各プロセッサ数ｐiについての残差ｅi（以下の数式（３）参照）の二乗和が最小になるように、最小二乗法によって各パラメータｃjの値を決定する。
【００４７】
【数３】
0005765266.tif 000004
【００４８】
（ステップＳ３）誤差判定部１１４は、以下の数式（４）に示すように、測定情報が示すｎ個の計算時間ｄiに対応するｎ個の不等式を生成する。各不等式は、変動量ΔＣを自由変数として用いてパラメータ変動後の計算時間を表した式Ｔ（Ｃ＋ΔＣ，ｐi，ｘi）と測定された計算時間ｄiとの差が、閾値ｅ以下であることを示す。パラメータ変動後の計算時間を表した式は、モデル式のパラメータ集合ＣをＣ＋ΔＣに置き換え、ステップＳ２で決定したパラメータ集合Ｃの値とプロセッサ数ｐiとを代入することで生成される。
【００４９】
また、誤差判定部１１４は、閾値ｅを決定する。閾値ｅは、数式（３）により算出されるｎ個の残差ｅ1〜ｅnの中の最大値Ｍａｘ（ｅi）以下であり、かつ、上記のｎ個の不等式が解をもつ範囲での下限値ｅm以上であることが望ましい。下限値ｅmは、通常は残差ｅ1〜ｅnの中の最小値Ｍｉｎ（ｅi）より大きい値になる。閾値ｅとしてＭａｘ（ｅi）を選択した場合、パラメータ集合Ｃの誤差を悲観的に評価することになり、閾値ｅとしてｅmを選択した場合、パラメータ集合Ｃの誤差を楽観的に評価することになる。モデルの精度評価の観点から、誤差判定部１１４は、好ましくは、閾値ｅ＝Ｍａｘ（ｅi）の場合と閾値ｅ＝ｅmの場合の両方について、以下の処理を実行する。なお、ｎ個の不等式から閾値ｅの下限値ｅmを算出する方法は、後述する。
【００５０】
【数４】
0005765266.tif 000005
【００５１】
（ステップＳ４）誤差判定部１１４は、ステップＳ３で生成したｎ個の不等式および閾値ｅを定義する式の集合に対して限量子消去（ＱＥ）法を適用し、束縛変数である閾値ｅを消去して自由変数である変動量ΔＣの取り得る値の範囲を算出する。
【００５２】
（ステップＳ５）誤差判定部１１４は、ステップＳ４で算出した変動量ΔＣの取り得る値の範囲から、モデルに従って算出される計算時間を最も増加させる（正の誤差が最も大きくなる）変動量Δｃjの組み合わせを抽出する。また、誤差判定部１１４は、変動量ΔＣの取り得る値の範囲から、モデルに従って算出される計算時間を最も減少させる（負の誤差が最も大きくなる）変動量Δｃjの組み合わせを抽出する。
【００５３】
（ステップＳ６）評価結果表示部１１５は、ステップＳ２でモデル生成部１１３が決定した各パラメータｃjの値をモデル式に代入することで生成されるグラフを、ディスプレイ３２に表示する。また、評価結果表示部１１５は、各パラメータｃjの値をステップＳ５で誤差判定部１１４が抽出した変動量Δｃjだけ変動させる（モデル式にｃj＋Δｃjの値を代入する）ことで生成されるグラフを、ディスプレイ３２に表示する。
【００５４】
一例として、フィッティングに用いるモデル式として、問題の大きさｘを固定した（問題の大きさｘを変数として含まない）以下に示す数式（５）を考える。数式（５）において、２つのパラメータｃ1，ｃ2はパラメータ集合Ｃに属し、定数ａは固定値である。数式（５）は、プロセッサ数ｐが大きいほど小さな値になる項と、プロセッサ数ｐが大きいほど大きな値になる項とを含む。前者は、負荷分散によるプロセッサ１個当たりの計算量の減少を反映し、後者は、プロセッサ間の通信によるオーバヘッドを反映している。数式（５）によれば、プロセッサ数ｐを１から徐々に増やしていくと、最初は計算時間が短くなるが、あるプロセッサ数を過ぎるとオーバヘッドの影響で計算時間が長くなる。
【００５５】
【数５】
0005765266.tif 000006
【００５６】
以下に示す数式（６）は、数式（５）のモデル式を用いた場合に、上記のステップＳ３において生成される一階述語論理の論理式の例である。ここでは、測定部１１１が、１２通りのプロセッサ数ｐ＝１０，２０，３０，４０，５０，６０，７０，８０，９０，１００，１１０，１２０に対応して、１２個の計算時間ｄ1〜ｄ12を測定した場合を考える。
【００５７】
この論理式では、１２通りのプロセッサ数に対応する１２個の不等式が論理積によって結合されている。数式（６）において、定数ａは固定値であり、パラメータｃ1，ｃ2の値は上記ステップＳ２で決定したものである。閾値ｅには、残差の最大値Ｍａｘ（ｅi）を代入している。閾値ｅに他の値（例えば、下限値ｅm）を代入することも可能である。パラメータｃ1の変動量Δｃ1とパラメータｃ2の変動量Δｃ2は自由変数であり、閾値ｅは存在限量子が付された束縛変数となっている。この論理式は、１２個の残差それぞれの絶対値が、閾値ｅ以下の範囲で変動することを許容することを示している。
【００５８】
【数６】
0005765266.tif 000007
【００５９】
数式（６）に対して限量子消去法を適用すると、不等式の集合の解として数式（７）が算出される。数式（７）は、数式（６）で自由変数であった変動量Δｃ1，Δｃ2の取り得る値の範囲を示している。入力としての論理式が２個の自由変数を含むことから、出力としての式はこの２個の自由変数の間の関係を示している。等式および不等式で表された変動量Δｃ1と変動量Δｃ2との間の関係は、２次元平面上に可視化することができる。
【００６０】
【数７】
0005765266.tif 000008
【００６１】
図６は、パラメータの取り得る値の例を示すグラフである。数式（７）を変動量Δｃ1×変動量Δｃ2の２次元平面にマッピングすると、図６のようなグラフが生成される。変動量Δｃ1，Δｃ2の可動範囲を示す領域は、（Δｃ1，Δｃ2）＝（０．０００９４６０５１，−７．９６２７３×１０-8），（−０．０００１１５４５６，４．１４６３５×１０-8）の２点を端点としてもつ。この２つの端点は、数式（７）の先頭２行の解に相当する。２つの端点の一方が、正の誤差を最大にする変動量Δｃ1，Δｃ2の組み合わせを示し、他方が負の誤差を最大にする変動量Δｃ1，Δｃ2の組み合わせを示している。
【００６２】
このように、限量子消去の結果からグラフを生成して端点を検出することで、モデルの誤差を最大にする変動量Δｃjの組み合わせを判定できる。ただし、このような変動量Δｃjの組み合わせは、上記のステップＳ３で生成されるｎ個の不等式から限量子消去法によって確認することもできる。数式（８）に示すように、ｎ個の不等式に含まれる変数のうち、１つの変動量のみを自由変数として選択し、他の変動量および閾値ｅは存在限量子を付して束縛変数とする。この不等式の集合に対して、限量子消去法を適用して束縛変数を消去すると、選択した１つの変動量の取り得る値の範囲のみが算出される。このような数式（８）の計算を、変動量Δｃjそれぞれについて行う。
【００６３】
【数８】
0005765266.tif 000009
【００６４】
数式（６）の束縛変数を変動量Δｃ1と閾値ｅに変更して限量子消去を行い、また、数式（６）の束縛変数を変動量Δｃ2と閾値ｅに変更して限量子消去を行うことで、以下に示す数式（９）が算出される。変動量Δｃ1の上限値と変動量Δｃ2の下限値の組み合わせが、図６に示したグラフの１つの端点に相当し、変動量Δｃ1の下限値と変動量Δｃ2の上限値の組み合わせが、図６に示したグラフの他の端点に相当する。
【００６５】
【数９】
0005765266.tif 000010
【００６６】
前述のように、数式（６）の閾値ｅに、残差の最大値Ｍａｘ（ｅi）に代えて、不等式に解が存在する範囲での下限値ｅmを代入することもできる。下限値ｅmは、以下に示す数式（１０）に従って算出することができる。数式（１０）に示すように、ｎ個の不等式に含まれる変数のうち、閾値ｅのみを自由変数とし、全ての変動量に存在限定子を付して束縛変数とする。この不等式の集合に対して、限量子消去法を適用して束縛変数を消去すると、全ての変動量が消去されて閾値ｅの取り得る値の範囲のみが算出される。算出された式によって示される閾値ｅの最小値を、下限値ｅmとして採用する。
【００６７】
【数１０】
0005765266.tif 000011
【００６８】
図７は、計算時間の予測結果の例を示す第１のグラフである。図７にプロットされた点（×印）は、測定部１１１において測定された計算時間ｄiを示している。また、図７では、最小二乗法によって生成したモデルを示す曲線と、誤差の上限および下限を示す曲線と、閾値ｅとして下限値ｅmを用いて算出した楽観的な誤差を示す曲線とを描いている。図７に示すように、問題の規模および使用するプロセッサの数が、サンプルプログラムを実行したときと同程度である（十分に小さい）ときは、モデルから予測される計算時間の誤差は十分小さいように見える。しかし、問題の規模や使用するプロセッサの数が大きくなると、このモデルから予測される計算時間は大きな誤差を含み得る。
【００６９】
図８は、計算時間の予測結果の例を示す第２のグラフである。図８に示すようなグラフが、評価結果表示部１１５によってディスプレイ３２に表示され得る。図８のグラフは、図７のグラフの横軸を伸ばしたものであり、プロセッサ数が大きい区間の、生成したモデルを示す曲線と、誤差の上限および下限を示す曲線と、閾値ｅとして下限値ｅmを用いて算出した誤差を示す曲線とを含む。図８に示すように、小規模な問題に基づいて生成したモデルを大規模な問題に適用しようとすると、フィッティングの過程でパラメータ集合Ｃに発生する小さな誤差が、予測される計算時間に大きな影響を与える。例えば、ユーザは図８のようなグラフを見ることで、あるプロセッサ数に対応する予測される計算時間が、どの程度変動する可能性があるかを定量的に確認することができる。前述のように、評価結果表示部１１５は、何％の誤差が生じるかを計算してユーザに提示してもよい。
【００７０】
第２の実施の形態の情報処理システムによれば、測定した計算時間からモデル式のパラメータ集合Ｃの値を決定することでサーバ装置２１０〜２４０に応じたモデルを生成し、任意のプログラムに対する計算時間を予測することができる。また、パラメータ集合Ｃに生じる誤差を推定することで、生成したモデルがどの程度の精度で計算時間を予測できるかを定量的に評価することができる。このため、サンプル問題よりも大規模な問題を解くプログラムを大きなリソースを用いて並列処理システムに実行させるときでも、モデルによる計算時間の予測を効果的に利用できるようになる。
【００７１】
例えば、ユーザは、予測精度が許容できるとき、予測誤差を考慮して並列処理システムのリソースを予約することができる。一方、予測精度が許容できないとき、より予測精度の高いモデルを生成するために、測定情報の中から異常な測定データを探し、異常な測定データを除去してモデルを生成し直すといった措置をとることができる。
【００７２】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現でき、第２の実施の形態の情報処理は、シミュレーション装置１００にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体３４）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。
【００７３】
プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置（例えば、ＨＤＤ１０３）に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。
【符号の説明】
【００７４】
１０  情報処理装置
１１  記憶部
１１ａ  測定情報
１２  演算部
２０  計算機システム
【図１】
0005765266.tif 000012
【図２】
0005765266.tif 000013
【図３】
0005765266.tif 000014
【図４】
0005765266.tif 000015
【図５】
0005765266.tif 000016
【図６】
0005765266.tif 000017
【図７】
0005765266.tif 000018
【図８】
0005765266.tif 000019