(57)【要約】【課題】並列に演算を行う複数の演算部を含む並列処理装置において、並列度を適切に制御する。【解決手段】並列処理装置３０１は、演算部３１１−１〜演算部３１１−Ｎ及び制御部３１２を含む。演算部３１１−１〜演算部３１１−Ｎは、データに対する演算を並列に実行する。制御部３１２は、データの第１部分に対する演算の終了時に、そのデータに対する演算処理の目標時間と、そのデータのうち演算が行われていない残りのデータのデータ量とに基づいて、第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求める。次に、制御部３１２は、第１部分に対する演算の第１並列度と、第１部分に対する演算の演算時間の計測値と、求めた推定演算時間とに基づいて、第２部分に対する演算の第２並列度を求める。そして、制御部３１２は、第２並列度が示す個数の演算部３１１−ｉに、第２部分に対する演算を実行させる。【選択図】図３
2019028829.tif 000002
【特許請求の範囲】
【請求項１】
データに対する演算を並列に実行する複数の演算部と、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる制御部と、
を備えることを特徴とする並列処理装置。
【請求項２】
前記制御部は、前記データに対する演算処理の処理時間が前記目標時間以下となり、かつ、前記処理時間が前記目標時間に近づくように、前記推定演算時間を決定し、前記データの複数の部分各々を前記第１部分とみなして、最後の部分に対する演算が終了するまで、前記第２並列度が示す個数の演算部に前記第２部分に対する演算を実行させる制御を繰り返すことを特徴とする請求項１記載の並列処理装置。
【請求項３】
前記制御部は、前記第１部分よりも前の演算対象である第３部分に対する演算の演算時間の計測値と、前記第３部分に対する演算の第３並列度と、前記第１部分に対する演算の演算時間の計測値と、前記第１並列度とに基づいて、前記第１部分に対する演算処理の予測処理時間と前記第１部分に対する演算処理の実処理時間との差分を求め、前記差分が第１閾値よりも大きい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも減少させることを特徴とする請求項１又は２記載の並列処理装置。
【請求項４】
前記制御部は、前記差分が前記第１閾値よりも小さな第２閾値よりも小さい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも増加させることを特徴とする請求項３記載の並列処理装置。
【請求項５】
データに対する演算を並列に実行する複数の演算部を含む並列処理装置において、
コンピュータが、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、
前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、
前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる、
ことを特徴とする並列処理方法。
【請求項６】
データに対する演算を並列に実行する複数の演算部を含む並列処理装置におけるコンピュータのためのプログラムであって、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、
前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、
前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる、
処理を前記コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理装置、並列処理方法、及びプログラムに関する。
【背景技術】
【０００２】
Field-Programmable Gate Array（ＦＰＧＡ）に論理マクロの機能及び論理マクロ間の配線を書き込むことによって、所望の論理回路を作製することができる。近年におけるＦＰＧＡの回路集積度及び動作周波数の向上により、従来ではCentral Processing Unit（ＣＰＵ）が行っていた演算処理をＦＰＧＡに実行させる用途も考案されている。これにより、演算処理システムの処理性能を向上させることができる。
【０００３】
ＣＰＵが行っていた演算処理をＦＰＧＡに実行させる場合、ＦＰＧＡ内に同一の演算回路を複数個設けて、それらの演算回路が並列に演算を実行することで、処理性能がさらに向上する。並列に演算を行う演算回路の個数は、並列度又は並列数と呼ばれることがある。
【０００４】
全ジョブの終了が揃うように各ジョブの並列度を調整する並列計算制御装置、及び処理単位に区切られたデータに対する演算を複数のプロセッサを用いて処理する並列処理装置も知られている（例えば、特許文献１及び２を参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１３−１４０４９０号公報
【特許文献２】特開２０１０−２７７５７９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
データ処理のための複数の演算回路を含むＦＰＧＡにおいて、最大の並列度で演算を実行した場合、電力効率が低下し、運用コストが増大する可能性がある。また、事前に決められた所定の並列度で演算を実行した場合、ユーザが希望する目標時間内にデータ処理が完了しない可能性がある。
【０００７】
なお、かかる問題は、複数の演算回路を含むＦＰＧＡに限らず、並列に演算を行う複数の演算部を含む他の並列処理装置においても生ずるものである。
【０００８】
１つの側面において、本発明は、並列に演算を行う複数の演算部を含む並列処理装置において、並列度を適切に制御することを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、並列処理装置は、複数の演算部及び制御部を含む。複数の演算部は、データに対する演算を並列に実行する。
【００１０】
制御部は、データの第１部分に対する演算の終了時に、そのデータに対する演算処理の目標時間と、そのデータのうち演算が行われていない残りのデータのデータ量とに基づいて、第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求める。次に、制御部は、第１部分に対する演算の第１並列度と、第１部分に対する演算の演算時間の計測値と、求めた推定演算時間とに基づいて、第２部分に対する演算の第２並列度を求める。そして、制御部は、複数の演算部のうち第２並列度が示す個数の演算部に、第２部分に対する演算を実行させる。
【発明の効果】
【００１１】
１つの実施形態によれば、並列に演算を行う複数の演算部を含む並列処理装置において、並列度を適切に制御することができる。
【図面の簡単な説明】
【００１２】
【図１】ＦＰＧＡの並列度、電力、及び性能の関係を示す図である。
【図２】電力、性能、及び性能／電力の変化を表すグラフを示す図である。
【図３】並列処理装置の機能的構成図である。
【図４】制御処理のフローチャートである。
【図５】並列処理装置の第１の具体例を示す機能的構成図である。
【図６】ＦＰＧＡの回路構成図である。
【図７】制御部の機能的構成図である。
【図８】データ量を表す複数のパラメータの関係を示す図である。
【図９】ＦＰＧＡの演算時間以外の処理時間を示す図である。
【図１０】時間を表す複数のパラメータの関係を示す図である。
【図１１】制御処理の具体例を示すフローチャートである。
【図１２】データ処理におけるパラメータの具体例を示す図である。
【図１３】データ処理における消費電力及び消費電力量を示す図である。
【図１４】データ処理における消費電力量と経過時間の関係を示す図である。
【図１５】データ量を減少させる決定処理のフローチャートである。
【図１６】データ量を増減させる決定処理のフローチャートである。
【図１７】並列処理装置の第２の具体例を示す機能的構成図である。
【図１８】並列計算機の構成図である。
【図１９】情報処理装置の構成図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、実施形態を詳細に説明する。
ＦＰＧＡ内の複数の演算回路が並列に演算を実行する場合、並列度と単位電力当たりの性能との間にはトレードオフの関係が存在する。性能を示す指標としては、例えば、単位時間当たりに実行される演算回数等を用いることができる。
【００１４】
並列演算では、並列に実行される演算処理の間の同期処理、処理対象のデータの通信処理等のオーバヘッドのために、Ｎ個の演算回路が並列に演算を実行したとしても、性能がＮ倍になるわけではない。したがって、ＦＰＧＡの性能は、並列度に比例しない。一方、ＦＰＧＡの消費電力は、並列度におおむね比例する。
【００１５】
図１は、１万件のデータを処理する場合のＦＰＧＡの並列度、電力、及び性能の関係の例を示している。この例では、並列度が１、２、４、８、１６、及び３２それぞれの場合の電力（Ｗ）、性能、性能／電力、処理時間（ｈ）、及び電力量（Ｗｈ）が示されている。
【００１６】
電力は、ＦＰＧＡの消費電力を表し、性能／電力は、単位電力当たりのＦＰＧＡの性能を表し、処理時間は、ＦＰＧＡが１万件のデータを処理する時間を表し、電力量は、ＦＰＧＡの消費電力量を表す。並列度が増加するに連れて性能が増加するため、処理時間は減少する。しかし、並列度が増加するに連れて電力も増加するため、性能／電力は減少し、電力量が増加する。
【００１７】
図２は、図１の並列度の変化に対する電力、性能、及び性能／電力の変化を表すグラフの例を示している。図２の横軸は並列度を表し、縦軸は電力、性能、又は性能／電力を表す。折れ線２０１は、並列度の変化に対する電力の変化を示し、折れ線２０２は、並列度の変化に対する性能の変化を示している。性能のスケールは、電力のスケールと同じである。折れ線２０３は、並列度の変化に対する性能／電力の変化を示している。
【００１８】
図２のグラフから、並列度が増加するに連れて性能も増加するが、電力の増加率が性能の増加率を上回るため、性能／電力は減少することが分かる。
【００１９】
ところで、所定件数のデータ処理に対してユーザが希望する性能は、目標時間内にデータ処理を完了することである場合が多い。例えば、夜間に実行されるバッチ処理は、翌日の営業開始時刻までに完了していればよく、それ以上高速化する必要はない。このように、必ずしも高速処理が要求されていないデータ処理において、並列度をＦＰＧＡの最大値に固定した場合、短時間で処理を完了することができるが、単位電力当たりの性能は低下するため、消費電力量は増加する。その結果、電力効率が低下し、運用コストが増大する。
【００２０】
また、処理対象のデータによって処理の内容が変化するデータ処理では、処理対象のデータに応じて処理時間が変動する。このようなデータ処理では、事前に決められた並列度で演算を実行した場合、目標時間内にデータ処理が完了しない可能性がある。
【００２１】
例えば、画像検索処理においては、第１段階ですべての画像に対して粗いマッチング処理を行い、第１段階で高い類似度が得られた画像のみを対象として、第２段階で詳細なマッチング処理を行うことがある。これにより、検索精度を向上させることができる。
【００２２】
このような画像検索処理では、検索対象の画像集合に類似度が低い画像が多く含まれている場合は、処理時間が短くなり、検索対象の画像集合に類似度が高い画像が多く含まれている場合は、処理時間が長くなる。したがって、事前に決められた並列度で演算を実行した場合、目標時間内に画像検索処理が完了しない可能性がある。
【００２３】
図３は、実施形態の並列処理装置の機能的構成例を示している。図３の並列処理装置３０１は、演算部３１１−１〜演算部３１１−Ｎ（Ｎは２以上の整数）及び制御部３１２を含む。演算部３１１−１〜演算部３１１−Ｎは、データに対する演算を並列に実行する。制御部３１２は、演算部３１１−１〜演算部３１１−Ｎが行う演算の並列度を制御する。
【００２４】
図４は、図３の制御部３１２が行う制御処理の例を示すフローチャートである。まず、制御部３１２は、データの第１部分に対する演算の終了時に、第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求める（ステップ４０１）。このとき、制御部３１２は、データに対する演算処理の目標時間と、そのデータのうち演算が行われていない残りのデータのデータ量とに基づいて、推定演算時間を求める。
【００２５】
次に、制御部３１２は、第１部分に対する演算の第１並列度と、第１部分に対する演算の演算時間の計測値と、求めた推定演算時間とに基づいて、第２部分に対する演算の第２並列度を求める（ステップ４０２）。そして、制御部３１２は、第２並列度が示す個数の演算部３１１−ｉ（ｉ＝１〜Ｎ）に、第２部分に対する演算を実行させる（ステップ４０３）。図３の並列処理装置３０１によれば、並列度を適切に制御することができる。
【００２６】
図５は、図３の並列処理装置３０１の第１の具体例を示している。図５の並列処理装置５０１は、制御部５１１、記憶部５１２、及びＦＰＧＡ５１３を含む。制御部５１１は、図３の制御部３１２に対応し、ＦＰＧＡ５１３の動作を制御する。記憶部５１２は、処理対象のデータと、ＦＰＧＡ５１３の制御に用いられる制御情報とを記憶する。
【００２７】
ＦＰＧＡ５１３は、複数のサイクル各々において、制御部５１１により指定される並列度で動作し、制御部５１１により指定される演算回数の演算を行う。１つのサイクルは、ＦＰＧＡ５１３が同じ並列度で行う演算処理に対応し、各サイクルの時間は、並列度、処理されるデータ量等に応じて変化する。並列処理装置５０１が行うデータ処理は、画像検索処理、科学技術分野の行列演算、気候変動又は流体のシミュレーション処理等であってもよい。
【００２８】
図６は、図５のＦＰＧＡ５１３の回路構成例を示している。図６のＦＰＧＡ５１３は、制御回路６０１、入力回路６０２、演算処理回路６０３、及び出力回路６０４を含む。
【００２９】
制御回路６０１は、レジスタ６１１を含む。レジスタ６１１は、制御部５１１により指定される並列度及び演算回数を記憶する。そして、制御回路６０１は、演算処理回路６０３が指定された並列度で指定された演算回数の演算を実行するように、入力回路６０２、演算処理回路６０３、及び出力回路６０４へ制御信号を出力する。
【００３０】
入力回路６０２は、入力バッファ６２１及びバッファ６２２−１〜バッファ６２２−Ｎを含み、演算処理回路６０３は、演算器６３１−１〜演算器６３１−Ｎを含む。出力回路６０４は、バッファ６４１−１〜バッファ６４１−Ｎ及びデータ統合回路６４２を含む。演算器６３１−ｉ（ｉ＝１〜Ｎ）は、論理演算回路である。
【００３１】
入力バッファ６２１は、記憶部５１２から出力されるデータを受信する。そして、入力バッファ６２１は、制御回路６０１から出力される制御信号に従って、バッファ６２２−１〜バッファ６２２−Ｎのうち、指定された並列度が示す個数のバッファ６２２−ｉに、受信したデータを振り分ける。そして、各バッファ６２２−ｉは、演算器６３１−ｉへデータを出力する。
【００３２】
演算器６３１−１〜演算器６３１−Ｎは、図３の演算部３１１−１〜演算部３１１−Ｎに対応する。演算器６３１−１〜演算器６３１−Ｎのうち、指定された並列度が示す個数の演算器６３１−ｉは、制御回路６０１から出力される制御信号に従って、指定された演算回数の演算を実行する。このとき、各演算器６３１−ｉは、バッファ６２２−ｉから出力されるデータに対する演算を実行して、演算結果をバッファ６４１−ｉへ出力する。
【００３３】
バッファ６４１−１〜バッファ６４１−Ｎのうち、指定された並列度が示す個数のバッファ６４１−ｉは、演算器６３１−ｉから出力される演算結果を受信し、データ統合回路６４２へ出力する。データ統合回路６４２は、バッファ６４１−ｉから出力される演算結果を統合して、制御部５１１へ送信する。
【００３４】
図７は、図５の制御部５１１の機能的構成例を示している。図７の制御部５１１は、受付部７０１、主制御部７０２、出力部７０３、データ量決定部７０４、並列度決定部７０５、送信部７０６、指示部７０７、計測部７０８、及び受信部７０９を含む。
【００３５】
受付部７０１は、データ処理の開始から完了までの目標時間を、ユーザから受け付ける。主制御部７０２は、データ処理全体の流れを制御し、すべてのデータの処理が完了したか否かをチェックする。
【００３６】
未処理のデータが残っている場合、主制御部７０２は、データ量決定部７０４に処理の継続を指示する。そして、すべてのデータの処理が完了した場合、主制御部７０２は、出力部７０３に処理結果の出力を指示する。また、主制御部７０２は、データ処理を開始してから現在までの経過時間、１サイクル当たりの処理時間等を監視する。
【００３７】
データ量決定部７０４は、処理対象のデータのうち、次のサイクルにおいて処理されるデータのデータ量を決定する。以下では、各サイクルにおいて処理されるデータを、部分データと呼ぶことがある。処理対象のデータの第１部分及び第２部分は、部分データに対応する。目標時間に近い時間でデータ処理を完了するためには、このデータ量が重要なパラメータとなる。
【００３８】
並列度決定部７０５は、目標時間と、演算が行われていない残りのデータのデータ量と、前のサイクルにおけるＦＰＧＡ５１３の演算時間とに基づいて、ＦＰＧＡ５１３が次のサイクルの部分データに対する演算を実行する推定演算時間を求める。この推定演算時間は、データ処理の開始から完了までの総処理時間が目標時間以下となり、かつ、総処理時間が目標時間に近づくように決定される。
【００３９】
そして、並列度決定部７０５は、前のサイクルの部分データに対する演算の並列度と、前のサイクルにおける演算時間の計測値と、次のサイクルにおける推定演算時間とに基づいて、次のサイクルの部分データに対する演算の並列度を求める。これにより、次のサイクルの並列度を、ユーザが希望する目標時間内にデータ処理を完了し、かつ、電力効率を向上させるために最適な値に設定することが可能になる。
【００４０】
送信部７０６は、データ量決定部７０４が決定したデータ量の部分データを、記憶部５１２からＦＰＧＡ５１３へ転送する。指示部７０７は、並列度決定部７０５が決定した並列度と、部分データに対する演算回数とをＦＰＧＡ５１３へ出力し、並列演算の実行をＦＰＧＡ５１３に指示する。そして、指示部７０７は、ＦＰＧＡ５１３における演算の完了を監視する。計測部７０８は、ＦＰＧＡ５１３が演算を開始してから完了するまでの演算時間を計測し、受信部７０９は、部分データに対する演算結果をＦＰＧＡ５１３から受信して、受信した演算結果を主制御部７０２へ出力する。
【００４１】
こうして１サイクルの演算処理が終了すると、次のサイクルの演算処理が開始され、すべてのデータの処理が完了した場合、出力部７０３は、それぞれの部分データに対する演算結果を含む処理結果を出力する。
【００４２】
図７の制御部５１１によれば、サイクル毎にＦＰＧＡ５１３の並列度を調整して、各サイクルの並列度を最適化することができる。
【００４３】
次に、並列度決定部７０５が前のサイクルの並列度から次のサイクルの並列度を決定する方法の例について説明する。並列度の計算においてＦＰＧＡ５１３の制御情報として用いられるパラメータは、以下の通りである。
【００４４】
ＳＴ：処理対象のデータのデータ量
Ａ（ｋ）：データ量ＳＴに対する、ｋ番目（ｋは１以上の整数）のサイクルの部分データのデータ量の割合（０≦Ａ（ｋ）≦１）
ＳＲ：ｋ番目のサイクルが終了したときの残りのデータのデータ量
ＴＧ：処理対象のデータのデータ処理に対する目標時間
ＴＣ（ｋ）：データ処理の開始からｋ番目のサイクルの終了までの経過時間（ＦＰＧＡ５１３における演算時間以外の処理時間を含む）
ΔＴ（ｋ）：ｋ番目のサイクルにおけるＦＰＧＡ５１３の演算時間
ΔＴα：１サイクル当たりのＦＰＧＡ５１３の演算時間以外の処理時間
ＣＲ：ｋ番目のサイクルが終了したときの残りのサイクル数
ＴＰ：ｋ番目のサイクルが終了したときの残りのデータに対する推定演算時間
ΔＴＰ：ｋ番目のサイクルが終了したときに推定される、ｋ＋１番目のサイクルの部分データに対する推定演算時間
Ｍ（ｋ）：ｋ番目のサイクルにおける並列度
【００４５】
図８は、データ量を表す複数のパラメータの関係の例を示している。処理対象のデータのデータ量ＳＴから、１番目〜ｋ番目のサイクルにおいて演算が終了した部分データのデータ量の総和を減算することで、残りのデータのデータ量ＳＲを求めることができる。
【００４６】
ｊ番目（ｊ＝１〜ｋ）のサイクルの部分データのデータ量はＳＴ＊Ａ（ｊ）であるから、１番目〜ｋ番目のサイクルにおいて演算が終了した部分データのデータ量の総和は、ＳＴ＊ΣＡ（ｊ）となる。ただし、ΣＡ（ｊ）は、ｊ＝１〜ｋの範囲におけるＡ（ｊ）の総和を表す。このとき、ＳＲは、次式により求めることができる。
【００４７】
ＳＲ＝ＳＴ−ＳＴ＊ΣＡ（ｊ）＝ＳＴ＊（１−ΣＡ（ｊ））      （１）
ΣＡ（ｊ）＝Ａ（１）＋Ａ（２）＋・・・＋Ａ（ｋ）            （２）
【００４８】
図９は、ＦＰＧＡ５１３の演算時間以外の処理時間ΔＴαの例を示している。ΔＴαは、１サイクルの処理時間からＦＰＧＡ５１３の演算時間を減算した値に相当する。ＦＰＧＡ５１３が部分データに対する演算を開始する際、以下のような前処理が行われる。
【００４９】
（Ｐ１）制御回路６０１は、並列度に応じて、演算に使用される演算器６３１−ｉを選択し、各演算器６３１−ｉの実行回数を設定する。
（Ｐ２）制御回路６０１は、入力回路６０２、演算処理回路６０３、及び出力回路６０４を初期化する。
（Ｐ３）制御部５１１は、部分データを記憶部５１２からＦＰＧＡ５１３へ転送する。
【００５０】
このうち、（Ｐ３）のデータ転送の時間が最も長いが、データ転送とＦＰＧＡ５１３における演算は並行して行われるため、サイクルの開始から演算の開始までの一部のデータ転送時間が、ΔＴαとして現れる。サイクル毎のΔＴαのバラツキが小さい場合、事前に決められた所定値をΔＴαとして用いることができる。
【００５１】
また、残りのデータのデータ量ＳＲを、ｋ＋１番目のサイクルの部分データのデータ量ＳＴ＊Ａ（ｋ＋１）で除算することで、残りのサイクル数ＣＲを求めることができる。
【００５２】
ＣＲ＝Ｃｅｉｌ（ＳＲ／（ＳＴ＊Ａ（ｋ＋１）））      （３）
【００５３】
式（３）のＣｅｉｌ（ｘ）は、実数ｘを、ｘと同じか又はｘよりも大きい整数のうち最小の整数に変換する関数である。式（１）を用いると、式（３）は次式のように書き換えられる。
【００５４】
ＣＲ＝Ｃｅｉｌ（ＳＴ＊（１−ΣＡ（ｊ））／（ＳＴ＊Ａ（ｋ＋１）））      （４）
【００５５】
図１０は、時間を表す複数のパラメータの関係の例を示している。ｋ番目のサイクルにおける演算処理の処理時間は、ＦＰＧＡ５１３の演算時間ΔＴ（ｋ）と、演算時間以外の処理時間ΔＴαとの和であり、経過時間ＴＣ（ｋ）は、ｊ＝１〜ｋの範囲におけるΔＴ（ｊ）＋ΔＴαの総和である。
【００５６】
各サイクルのΔＴαが同じ値であると仮定すると、目標時間ＴＧは、ｋ番目のサイクルまでの経過時間ＴＣ（ｋ）と、残りのデータに対する推定演算時間ＴＰと、ＣＲ＊ΔＴαとの総和で表される。
【００５７】
ＴＧ＝ＴＣ（ｋ）＋ＴＰ＋ＣＲ＊ΔＴα      （５）
【００５８】
式（５）を変形すると、次式が得られる。
【００５９】
ＴＰ＝ＴＧ−ＴＣ（ｋ）−ＣＲ＊ΔＴα      （６）
【００６０】
ＴＰ≦０の場合は、既に目標時間ＴＧが経過していることになる。式（６）のＴＰをＣＲで除算することで、ｋ＋１番目のサイクルの部分データに対する推定演算時間ΔＴＰを求めることができる。
【００６１】
ΔＴＰ＝ＴＰ／ＣＲ
＝（ＴＧ−ＴＣ（ｋ）−ＣＲ＊ΔＴα）／ＣＲ
＝（ＴＧ−ＴＣ（ｋ））／ＣＲ−ΔＴα          （７）
【００６２】
ここで、ＦＰＧＡ５１３の演算時間と並列度が反比例するものと仮定する。この場合、推定演算時間ΔＴＰに対するｋ番目のサイクルの演算時間ΔＴ（ｋ）の比率と、ｋ番目のサイクルの並列度Ｍ（ｋ）との積を計算することで、ｋ＋１番目のサイクルの並列度Ｍ（ｋ＋１）を求めることができる。
【００６３】
Ｍ（ｋ＋１）＝Ｃｅｉｌ（（ΔＴ（ｋ）／ΔＴＰ）＊Ｍ（ｋ））      （８）
【００６４】
ｋ番目のサイクルが終了したとき、式（８）を用いて、次のｋ＋１番目のサイクルにおける最適な並列度Ｍ（ｋ＋１）が求められる。ただし、ΔＴＰ≦０の場合は、既に目標時間ＴＧが経過しているため、Ｍ（ｋ＋１）として並列度の最大値が用いられる。また、式（８）のＭ（ｋ＋１）が並列度の最大値を超えた場合も、そのＭ（ｋ＋１）の値が最大値に変更される。
【００６５】
並列度として選択可能な整数が連続していない場合は、式（８）の右辺の値と同じか又はその値よりも大きい整数のうち、選択可能な最小の整数が、Ｍ（ｋ＋１）として用いられる。
【００６６】
式（３）、式（７）、及び式（８）より、ＳＲ、ＳＴ＊Ａ（ｋ＋１）、ＴＧ、ＴＣ（ｋ）、ΔＴα、ΔＴ（ｋ）、及びＭ（ｋ）が既知であれば、Ｍ（ｋ＋１）を計算することができる。
【００６７】
図１１は、図７の制御部５１１が行う制御処理の具体例を示すフローチャートである。まず、ユーザは、並列処理装置５０１に目標時間ＴＧを入力し、受付部７０１は、入力された目標時間ＴＧを受け付ける（ステップ１１０１）。次に、並列度決定部７０５は、最初のサイクルの並列度Ｍ（１）を初期値に設定する（ステップ１１０２）。例えば、図６のＦＰＧＡ５１３の場合、演算器６３１−ｉの総数Ｎが並列度Ｍ（１）として設定される。
【００６８】
次に、ユーザは、並列処理装置５０１に処理対象のデータのデータ量ＳＴを入力し、受付部７０１は、入力されたデータ量ＳＴを受け付ける（ステップ１１０３）。そして、データ量決定部７０４は、最初のサイクルで処理される部分データの割合Ａ（１）を決定する（ステップ１１０４）。これにより、最初の部分データのデータ量ＳＴ＊Ａ（１）が決定される。
【００６９】
次に、主制御部７０２は、サイクルを示す変数ｋを１に設定し、送信部７０６は、データ量ＳＴ＊Ａ（ｋ）の部分データを、記憶部５１２からＦＰＧＡ５１３へ転送する（ステップ１１０５）。そして、指示部７０７は、並列度Ｍ（ｋ）と、データ量ＳＴ＊Ａ（ｋ）の部分データに対する演算回数とを指定する、制御信号をＦＰＧＡ５１３へ出力し、並列演算の実行をＦＰＧＡ５１３に指示する（ステップ１１０６）。部分データに対する演算回数は、並列度Ｍ（ｋ）とデータ量ＳＴ＊Ａ（ｋ）とから決定することができる。例えば、Ｃｅｉｌ（ＳＴ＊Ａ（ｋ）／Ｍ（ｋ））を演算回数として用いてもよい。
【００７０】
ＦＰＧＡ５１３は、受信した制御信号が指定する並列度Ｍ（ｋ）及び演算回数に従って、記憶部５１２から転送される部分データに対して、ｋ番目のサイクルの演算処理を実行する。
【００７１】
計測部７０８は、ＦＰＧＡ５１３における演算時間ΔＴ（ｋ）を計測し（ステップ１１０７）、受信部７０９は、ｋ番目のサイクルの演算結果をＦＰＧＡ５１３から受信して、その演算結果を主制御部７０２へ出力する（ステップ１１０８）。そして、主制御部７０２は、データ処理の開始からｋ番目のサイクルの終了までの経過時間ＴＣ（ｋ）を計測する。
【００７２】
次に、主制御部７０２は、ＦＰＧＡ５１３が処理した部分データが最後の部分データであるか否かをチェックする（ステップ１１０９）。例えば、残りのデータのデータ量ＳＲが０である場合、ＦＰＧＡ５１３が処理した部分データが最後の部分データであると判定される。
【００７３】
ＦＰＧＡ５１３が処理した部分データが最後の部分データではない場合（ステップ１１０９，ＮＯ）、データ量決定部７０４は、ｋ＋１番目のサイクルで処理される部分データのデータ量ＳＴ＊Ａ（ｋ＋１）を決定する（ステップ１１１１）。そして、並列度決定部７０５は、式（８）を用いてｋ＋１番目のサイクルの並列度Ｍ（ｋ＋１）を決定する。
【００７４】
次に、主制御部７０２は、変数ｋを１だけインクリメントし、制御部５１１は、次のサイクルについてステップ１１０５以降の処理を繰り返す。
【００７５】
そして、ＦＰＧＡ５１３が処理した部分データが最後の部分データである場合（ステップ１１０９，ＹＥＳ）、出力部７０３は、すべてのデータに対する処理結果を出力する（ステップ１１１０）。
【００７６】
ステップ１１０２において、演算器６３１−ｉの総数Ｎを並列度Ｍ（１）として用いることで、最初のサイクルにおいて最大の並列度Ｎで高速に演算が行われる。このため、短い目標時間ＴＧが指定された場合であっても、目標時間ＴＧ内にデータ処理を完了することが可能になる。なお、すべてのデータに対する演算を並列度Ｎで実行した場合の総処理時間が目標時間ＴＧ以上である場合は、すべてのデータに対する演算が並列度Ｎで実行される。
【００７７】
図１１の制御処理によれば、処理対象のデータの特徴が未知である場合であっても、少しずつデータを処理しながら、部分データの演算処理にかかった時間から、次に処理する部分データのデータ量及び並列度を決定することができる。そして、部分データに対する演算処理をサイクル毎に繰り返すことで、データの特徴にバラツキがある場合であっても、総処理時間を目標時間に近づけることが可能になる。
【００７８】
また、総処理時間が目標時間以下となる範囲内で、並列度を最小化することができるため、ＦＰＧＡ５１３の消費電力を抑えることが可能になる。
【００７９】
図１２は、データ処理におけるパラメータの具体例を示している。この例では、処理対象のデータのデータ量ＳＴは４万件であり、目標時間ＴＧは４８時間であり、ＦＰＧＡ５１３の演算時間以外の処理時間ΔＴαは０時間である。また、各サイクルで処理される部分データのデータ量ＳＴ＊Ａ（ｋ）は１万件に固定されている。したがって、処理対象のデータは４つの部分データに分割され、４サイクルですべてのデータの演算処理が完了する。
【００８０】
ＦＰＧＡ５１３の演算器６３１−ｉの総数Ｎは３２個であり、ＦＰＧＡ５１３の並列度としては、２ｍ（ｍ＝０，１，２，３，４，５）を選択することができる。したがって、選択可能な並列度は、１、２、４、８、１６、又は３２である。
【００８１】
例えば、最初のサイクルにおいて、並列度Ｍ（１）は３２に設定され、１万件の部分データに対する演算が並列度３２で実行される。最初のサイクルが終了したとき、残りのデータのデータ量ＳＲは３万件であり、次のサイクルにおける部分データのデータ量ＳＴ＊Ａ（２）は１万件である。また、経過時間ＴＣ（１）は５．３時間であり、最初のサイクルの演算時間ΔＴ（１）も５．３時間である。
【００８２】
このとき、式（３）より、残りのサイクル数ＣＲは３になり、式（６）より、残りのデータに対する推定演算時間ＴＰは４３時間になり、式（７）より、次のサイクルの部分データに対する推定演算時間ΔＴＰは１４時間になる。したがって、式（８）の右辺の値が１３になるため、１３以上の整数のうち選択可能な並列度の最小値である１６が、次のサイクルの並列度Ｍ（２）として設定される。
【００８３】
２番目のサイクルにおいて、１万件の部分データに対する演算が並列度１６で実行され、ＳＲは２万件になり、ＳＴ＊Ａ（３）は１万件になる。また、ＴＣ（２）は１４．８時間であり、ΔＴ（２）は９．５時間である。このとき、式（３）よりＣＲは２になり、式（６）よりＴＰは３３時間になり、式（７）よりΔＴＰは１７時間になる。したがって、式（８）の右辺の値は９になるため、９以上の整数のうち選択可能な並列度の最小値である１６が、次のサイクルの並列度Ｍ（３）として設定される。
【００８４】
３番目のサイクルにおいて、１万件の部分データに対する演算が並列度１６で実行され、ＳＲは１万件になり、ＳＴ＊Ａ（４）も１万件になる。また、ＴＣ（３）は２４．３時間であり、ΔＴ（３）は９．５時間である。このとき、式（３）よりＣＲは１になり、式（６）よりＴＰは２４時間になり、式（７）よりΔＴＰも２４時間になる。したがって、式（８）の右辺の値が７になるため、７以上の整数のうち選択可能な並列度の最小値である８が、次のサイクルの並列度Ｍ（４）として設定される。
【００８５】
そして、４番目のサイクルにおいて、最後の１万件の部分データに対する演算が並列度８で実行され、すべてのデータに対する演算が終了する。このとき、ＴＣ（４）は４１．４時間であり、目標時間の４８時間に近い総処理時間で、すべてのデータに対する演算が完了していることが分かる。
【００８６】
図１３は、データ処理における消費電力及び消費電力量の例を示している。図１３の並列度可変の場合の演算時間は、図１２の各サイクルにおけるΔＴ（ｋ）に対応し、電力及び電力量は、各サイクルにおけるＦＰＧＡ５１３の消費電力及び消費電力量を表す。４つのサイクルの消費電力量の合計は６１０．４Ｗｈである。
【００８７】
一方、図１３の並列度固定の場合の演算時間、電力、及び電力量は、図１２のデータ処理において各サイクルの並列度を３２に固定した場合の数値を表している。この場合、４つのサイクルの消費電力量の合計は６７８．４Ｗｈである。図１１の制御処理を適用してサイクル毎に並列度を変更することで、並列度を最大値に固定した場合よりも、消費電力量が６８Ｗｈ（約１０％）削減されることが分かる。
【００８８】
図１４は、データ処理における消費電力量と経過時間の関係の例を示している。経過時間は、図１２のＴＣ（ｋ）に対応する。図１４（ａ）は、図１３の並列度可変の場合における消費電力量と経過時間の関係を示している。折れ線１４０１−ｋ（ｋ＝１〜４）は、ｋ番目のサイクルにおける消費電力量と経過時間の変化を表す。
【００８９】
図１４（ｂ）は、図１３の並列度固定の場合における消費電力量と経過時間の関係を示している。折れ線１４０２−ｋ（ｋ＝１〜４）は、ｋ番目のサイクルにおける消費電力量と経過時間の変化を表す。
【００９０】
並列度を最大値に固定した場合、サイクル毎に並列度を変更する場合よりも短時間でデータ処理を完了することができるが、消費電力量の合計は多くなる。一方、目標時間に応じて分割したデータを最適な並列度で処理することにより、消費電力量を最小化するデータ処理を実現することができる。
【００９１】
ところで、処理対象のデータによって処理の内容が変化するデータ処理では、同じデータ量の部分データであっても、データの特徴に依存して演算時間が変動する。このため、目標時間に近い時間でデータ処理を完了するためには、各サイクルで処理される部分データのデータ量を固定するのではなく、サイクル毎に部分データのデータ量を変化させることが望ましい。
【００９２】
前のサイクルの演算時間から予測した次のサイクルの処理時間（予測処理時間）と、次のサイクルにおける実際の処理時間（実処理時間）との間に差分が存在する場合、その差分を補正することで、総処理時間を目標時間に近づけることができる。
【００９３】
しかし、１サイクル当たりのデータ量が多い場合、すべてのデータを処理するためのサイクル数が減少するため、並列度を調整する機会が減少する。したがって、予測処理時間と実処理時間との差分が大きい場合、その差分を補正することが難しくなる。逆に、１サイクル当たりのデータ量が少ない場合、サイクル数が増加するため、並列度を調整する機会が増加する。したがって、予測処理時間と実処理時間との差分が小さくなり、残りのサイクルにおいて、その差分を補正することが容易になる。ただし、サイクル数が増加した分だけ、ＦＰＧＡ５１３の演算時間以外の処理時間が余分に発生する。
【００９４】
次のサイクルの予測処理時間は、前のサイクルにおいて計測された演算時間から計算することができる。この場合、前のサイクルの部分データと次のサイクルの部分データとの間で、データの特徴のバラツキが大きい場合、予測処理時間が実処理時間から大きく外れる可能性がある。
【００９５】
そこで、予測処理時間と実処理時間との差分が大きい場合は、部分データのデータ量を減少させ、サイクル数を増加させることで、並列度を調整する機会を増加させる制御方法が考えられる。逆に、予測処理時間と実処理時間との差分が小さい場合は、データの特徴のバラツキが小さいと推定できるため、部分データのデータ量を増加させても構わない。
【００９６】
まず、ｋ番目のサイクルの実処理時間ＴＡ（ｋ）は、ｋ番目のサイクルの演算時間ΔＴ（ｋ）を用いて、次式により求められる。
【００９７】
ＴＡ（ｋ）＝ΔＴ（ｋ）＋ΔＴα      （１１）
【００９８】
また、ＦＰＧＡ５１３の演算時間と並列度が反比例するものと仮定すると、ｋ−１番目のサイクルの演算時間ΔＴ（ｋ−１）から予測されるｋ番目のサイクルの演算時間ΔＴＸ（ｋ）は、次式により求められる。
【００９９】
ΔＴＸ（ｋ）＝（Ｍ（ｋ−１）／Ｍ（ｋ））＊ΔＴ（ｋ−１）      （１２）
【０１００】
ｋ番目のサイクルの予測処理時間ＴＸ（ｋ）は、式（１２）のΔＴＸ（ｋ）を用いて、次式により求められる。
【０１０１】
ＴＸ（ｋ）＝ΔＴＸ（ｋ）＋ΔＴα
＝（Ｍ（ｋ−１）／Ｍ（ｋ））＊ΔＴ（ｋ−１）＋ΔＴα      （１３）
【０１０２】
式（１１）及び式（１３）より、ｋ番目のサイクルの予測処理時間ＴＸ（ｋ）と実処理時間ＴＡ（ｋ）との差分ΔＶは、次式により求められる。
【０１０３】
ΔＶ＝｜ＴＡ（ｋ）−ＴＸ（ｋ）｜
＝｜（ΔＴ（ｋ）＋ΔＴα）
−（（Ｍ（ｋ−１）／Ｍ（ｋ））＊ΔＴ（ｋ−１）＋ΔＴα）｜
＝｜ΔＴ（ｋ）−（Ｍ（ｋ−１）／Ｍ（ｋ））＊ΔＴ（ｋ−１）｜      （１４）
【０１０４】
データ量決定部７０４は、式（１４）の差分ΔＶに基づいてデータ量を増減することができる。
【０１０５】
図１５は、図１１のステップ１１１１においてデータ量を減少させる決定処理の例を示すフローチャートである。まず、データ量決定部７０４は、ｋ番目のサイクルの予測処理時間ＴＸ（ｋ）と実処理時間ＴＡ（ｋ）との差分ΔＶを、式（１４）により計算し（ステップ１５０１）、ΔＶ／ΔＴ（ｋ）を計算する（ステップ１５０２）。
【０１０６】
次に、データ量決定部７０４は、ΔＶ／ΔＴ（ｋ）を閾値ＴＨ１と比較する（ステップ１５０３）。ΔＶ／ΔＴ（ｋ）がＴＨ１よりも大きい場合（ステップ１５０３，ＹＥＳ）、データ量決定部７０４は、ｋ＋１番目のサイクルの部分データのデータ量ＳＴ＊Ａ（ｋ＋１）を減少させる（ステップ１５０４）。
【０１０７】
この場合、データ量決定部７０４は、ｋ＋１番目のサイクルの部分データのデータ量の割合Ａ（ｋ＋１）を、次式により計算する。
【０１０８】
Ａ（ｋ＋１）＝Ａ（ｋ）−ΔＡ      （１５）
【０１０９】
式（１５）のΔＡは、０＜ΔＡ≦Ａ（ｋ）の範囲の所定値である。そして、データ量決定部７０４は、ＳＴとＡ（ｋ＋１）とを乗算することでＳＴ＊Ａ（ｋ＋１）を計算する。これにより、ＳＴ＊Ａ（ｋ＋１）が所定値ＳＴ＊ΔＡだけ減少する。
【０１１０】
次に、並列度決定部７０５は、データ量決定部７０４が計算したＳＴ＊Ａ（ｋ＋１）を用いて、式（３）、式（７）、及び式（８）により、ｋ＋１番目のサイクルの並列度Ｍ（ｋ＋１）を計算する（ステップ１５０５）。
【０１１１】
一方、ΔＶ／ΔＴ（ｋ）がＴＨ１以下である場合（ステップ１５０３，ＮＯ）、データ量決定部７０４は、ＳＴ＊Ａ（ｋ＋１）を変更しない（ステップ１５０６）。この場合、データ量決定部７０４は、Ａ（ｋ）をそのままＡ（ｋ＋１）として用いて、ＳＴ＊Ａ（ｋ＋１）を計算し、並列度決定部７０５は、ステップ１５０５の処理を行う。
【０１１２】
ステップ１５０３においてΔＶ／ΔＴ（ｋ）を閾値ＴＨ１と比較することは、ＴＨ１＊ΔＴ（ｋ）を閾値として用いて、ΔＶをＴＨ１＊ΔＴ（ｋ）と比較することと等価である。ΔＶ／ΔＴ（ｋ）がＴＨ１よりも大きい場合は、ΔＶがＴＨ１＊ΔＴ（ｋ）よりも大きい場合に相当し、ΔＶ／ΔＴ（ｋ）がＴＨ１以下である場合は、ΔＶがＴＨ１＊ΔＴ（ｋ）以下である場合に相当する。
【０１１３】
図１５の決定処理によれば、予測処理時間と実処理時間との差分ΔＶがＴＨ１＊ΔＴ（ｋ）よりも大きい場合に、ＳＴ＊Ａ（ｋ＋１）を減少させて、並列度を調整する機会を増加させることができる。
【０１１４】
図１６は、図１１のステップ１１１１においてデータ量を増減させる決定処理の例を示すフローチャートである。ステップ１６０１〜ステップ１６０５の処理は、図１５のステップ１５０１〜ステップ１５０５の処理と同様である。
【０１１５】
ΔＶ／ΔＴ（ｋ）がＴＨ１以下である場合（ステップ１６０３，ＮＯ）、データ量決定部７０４は、ΔＶ／ΔＴ（ｋ）を、閾値ＴＨ１よりも小さな閾値ＴＨ２と比較する（ステップ１６０６）。ΔＶ／ΔＴ（ｋ）がＴＨ２よりも小さい場合（ステップ１６０６，ＹＥＳ）、データ量決定部７０４は、ＳＴ＊Ａ（ｋ＋１）を増加させる（ステップ１６０７）。この場合、データ量決定部７０４は、Ａ（ｋ＋１）を次式により計算し、ＳＴとＡ（ｋ＋１）とを乗算することでＳＴ＊Ａ（ｋ＋１）を計算する。
【０１１６】
Ａ（ｋ＋１）＝Ａ（ｋ）＋ΔＡ      （１６）
【０１１７】
これにより、ＳＴ＊Ａ（ｋ＋１）が所定値ＳＴ＊ΔＡだけ増加する。そして、並列度決定部７０５は、ステップ１６０５の処理を行う。
【０１１８】
一方、ΔＶ／ΔＴ（ｋ）がＴＨ２以上である場合（ステップ１６０６，ＮＯ）、データ量決定部７０４は、ＳＴ＊Ａ（ｋ＋１）を変更しない（ステップ１６０８）。この場合、データ量決定部７０４は、Ａ（ｋ）をそのままＡ（ｋ＋１）として用いて、ＳＴ＊Ａ（ｋ＋１）を計算し、並列度決定部７０５は、ステップ１６０５の処理を行う。
【０１１９】
ステップ１６０６においてΔＶ／ΔＴ（ｋ）を閾値ＴＨ２と比較することは、ＴＨ２＊ΔＴ（ｋ）を閾値として用いて、ΔＶをＴＨ２＊ΔＴ（ｋ）と比較することと等価である。ΔＶ／ΔＴ（ｋ）がＴＨ２よりも小さい場合は、ΔＶがＴＨ２＊ΔＴ（ｋ）よりも小さい場合に相当し、ΔＶ／ΔＴ（ｋ）がＴＨ２以上である場合は、ΔＶがＴＨ２＊ΔＴ（ｋ）以上である場合に相当する。
【０１２０】
図１６の決定処理によれば、予測処理時間と実処理時間との差分ΔＶがＴＨ２＊ΔＴ（ｋ）よりも小さい場合に、ＳＴ＊Ａ（ｋ＋１）を増加させて、サイクル数を減少させることができる。サイクル数が減少した分だけ、ＦＰＧＡ５１３の演算時間以外の処理時間の総和が削減されるため、残りのサイクルの演算をより少ない並列度で実行することが可能になる。
【０１２１】
図５の並列処理装置では、ＦＰＧＡ５１３がデータに対する並列演算を行っているが、並列演算を行う他の装置をＦＰＧＡ５１３の代わりに用いることも可能である。並列演算を行う他の装置として、例えば、Graphics Processing Unit（ＧＰＵ）、並列計算機等が挙げられる。
【０１２２】
図１７は、並列処理装置の第２の具体例を示している。図１７の並列処理装置１７０１は、図５のＦＰＧＡ５１３を並列計算機１７１１に置き換えた構成を有する。並列計算機１７１１は、複数のサイクル各々において、制御部５１１により指定される並列度で動作し、制御部５１１により指定される演算回数の演算を行う。
【０１２３】
図１８は、図１７の並列計算機１７１１の構成例を示している。図１８の並列計算機１７１１は、分配部１８０１、プロセッサ１８０２−１〜プロセッサ１８０２−Ｎ、及び集約部１８０３を含む。プロセッサ１８０２−１〜プロセッサ１８０２−Ｎは、図３の演算部３１１−１〜演算部３１１−Ｎに対応する。
【０１２４】
分配部１８０１は、制御部５１１から並列度及び演算回数を受信し、記憶部５１２からデータを受信する。そして、分配部１８０１は、プロセッサ１８０２−１〜プロセッサ１８０２−Ｎのうち、受信した並列度が示す個数のプロセッサ１８０２−ｉ（ｉ＝１〜Ｎ）に対して、受信したデータを振り分け、受信した演算回数の演算を実行するように指示する。
【０１２５】
分配部１８０１からデータを振り分けられたプロセッサ１８０２−ｉは、指示された演算回数の演算を実行して、演算結果を集約部１８０３へ出力する。集約部１８０３は、プロセッサ１８０２−ｉから出力される演算結果を集約して、制御部５１１へ送信する。
【０１２６】
図３の並列処理装置３０１、図５の並列処理装置５０１、及び図１７の並列処理装置１７０１の構成は一例に過ぎず、並列処理装置の用途又は条件に応じて、一部の構成要素を省略又は変更してもよい。
【０１２７】
図６のＦＰＧＡ５１３、図７の制御部５１１、及び図１８の並列計算機１７１１の構成は一例に過ぎず、並列処理装置の用途又は条件に応じて、一部の構成要素を省略又は変更してもよい。
【０１２８】
図４、図１１、図１５、及び図１６のフローチャートは一例に過ぎず、並列処理装置の構成又は条件に応じて一部の処理を省略又は変更してもよい。例えば、図１１のステップ１１０１及びステップ１１０３において、受付部７０１は、ユーザが入力した目標時間及びデータ量を受け付ける代わりに、外部の装置から目標時間及びデータ量を取得してもよい。ステップ１１０２において、並列度決定部７０５は、演算器６３１−ｉの総数Ｎよりも小さい整数を、最初のサイクルの並列度Ｍ（１）として設定してもよい。
【０１２９】
図１及び図２の並列度、電力、性能、性能／電力、処理時間、及び電力量は一例に過ぎず、これらの数値は、並列処理装置の構成又は条件に応じて変化する。図８〜図１０のパラメータの関係は一例に過ぎず、別のパラメータを用いても構わない。図１２のパラメータと図１３及び図１４の電力及び電力量は一例に過ぎず、これらの数値は、並列処理装置の構成又は条件、及び処理対象のデータに応じて変化する。
【０１３０】
式（１）〜式（１６）は一例に過ぎず、制御部５１１は、別の計算式を用いて制御処理を行っても構わない。
【０１３１】
図１９は、図３の並列処理装置３０１及び図５の並列処理装置５０１として用いられる情報処理装置（コンピュータ）の構成例を示している。図１９の情報処理装置は、ＦＰＧＡ５１３、ＣＰＵ１９０１、メモリ１９０２、入力装置１９０３、出力装置１９０４、補助記憶装置１９０５、媒体駆動装置１９０６、及びネットワーク接続装置１９０７を含む。これらの構成要素はバス１９０８により互いに接続されている。
【０１３２】
メモリ１９０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを格納する。メモリ１９０２は、図５の記憶部５１２として用いることができる。
【０１３３】
ＣＰＵ１９０１（プロセッサ）は、例えば、メモリ１９０２を利用してプログラムを実行することにより、図３の制御部３１２及び図５の制御部５１１として動作する。
【０１３４】
ＣＰＵ１９０１は、メモリ１９０２を利用してプログラムを実行することにより、図７の受付部７０１、主制御部７０２、及び出力部７０３としても動作する。ＣＰＵ１９０１は、メモリ１９０２を利用してプログラムを実行することにより、データ量決定部７０４、並列度決定部７０５、送信部７０６、指示部７０７、計測部７０８、及び受信部７０９としても動作する。送信部７０６、指示部７０７、及び受信部７０９として動作する場合、ＣＰＵ１９０１は、ＦＰＧＡドライバを用いてＦＰＧＡ５１３にアクセスする。
【０１３５】
入力装置１９０３は、例えば、キーボード、ポインティングデバイス等であり、オペレータ又はユーザからの指示及び情報の入力に用いられる。出力装置１９０４は、例えば、表示装置、プリンタ、スピーカ等であり、オペレータ又はユーザへの問い合わせ又は指示、及びデータ処理の処理結果の出力に用いられる。
【０１３６】
補助記憶装置１９０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。補助記憶装置１９０５は、ハードディスクドライブ又はフラッシュメモリであってもよい。情報処理装置は、補助記憶装置１９０５にプログラム及びデータを格納しておき、それらをメモリ１９０２にロードして使用することができる。補助記憶装置１９０５は、図５の記憶部５１２として用いることができる。
【０１３７】
媒体駆動装置１９０６は、可搬型記録媒体１９０９を駆動し、その記録内容にアクセスする。可搬型記録媒体１９０９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。可搬型記録媒体１９０９は、Compact Disk Read Only Memory（ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、Universal Serial Bus（ＵＳＢ）メモリ等であってもよい。オペレータ又はユーザは、この可搬型記録媒体１９０９にプログラム及びデータを格納しておき、それらをメモリ１９０２にロードして使用することができる。
【０１３８】
このように、処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体は、メモリ１９０２、補助記憶装置１９０５、又は可搬型記録媒体１９０９のような、物理的な（非一時的な）記録媒体である。
【０１３９】
ネットワーク接続装置１９０７は、Local Area Network、Wide Area Network等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェース回路である。情報処理装置は、プログラム及びデータを外部の装置からネットワーク接続装置１９０７を介して受け取り、それらをメモリ１９０２にロードして使用することができる。
【０１４０】
なお、情報処理装置が図１９のすべての構成要素を含む必要はなく、用途又は条件に応じて一部の構成要素を省略することも可能である。例えば、情報処理装置がオペレータ又はユーザと対話を行わない場合は、入力装置１９０３及び出力装置１９０４を省略してもよい。また、可搬型記録媒体１９０９又は通信ネットワークを利用しない場合は、媒体駆動装置１９０６又はネットワーク接続装置１９０７を省略してもよい。
【０１４１】
図１９の情報処理装置は、図１７の並列処理装置１７０１としても用いることができる。この場合、ＦＰＧＡ５１３の代わりに、並列計算機１７１１がバス１９０８に接続される。
【０１４２】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【０１４３】
図１乃至図１９を参照しながら説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）
データに対する演算を並列に実行する複数の演算部と、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる制御部と、
を備えることを特徴とする並列処理装置。
（付記２）
前記制御部は、前記データに対する演算処理の処理時間が前記目標時間以下となり、かつ、前記処理時間が前記目標時間に近づくように、前記推定演算時間を決定し、前記データの複数の部分各々を前記第１部分とみなして、最後の部分に対する演算が終了するまで、前記第２並列度が示す個数の演算部に前記第２部分に対する演算を実行させる制御を繰り返すことを特徴とする付記１記載の並列処理装置。
（付記３）
前記制御部は、前記第１部分よりも前の演算対象である第３部分に対する演算の演算時間の計測値と、前記第３部分に対する演算の第３並列度と、前記第１部分に対する演算の演算時間の計測値と、前記第１並列度とに基づいて、前記第１部分に対する演算処理の予測処理時間と前記第１部分に対する演算処理の実処理時間との差分を求め、前記差分が第１閾値よりも大きい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも減少させることを特徴とする付記１又は２記載の並列処理装置。
（付記４）
前記制御部は、前記差分が前記第１閾値よりも小さな第２閾値よりも小さい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも増加させることを特徴とする付記３記載の並列処理装置。
（付記５）
前記制御部は、前記第１部分に対する演算の演算時間の計測値の前記推定演算時間に対する比率と、前記第１並列度との積に基づいて、前記第２並列度を求めることを特徴とする付記１乃至４のいずれか１項に記載の並列処理装置。
（付記６）
前記複数の演算部は、複数の論理演算回路であることを特徴とする付記１乃至５のいずれか１項に記載の並列処理装置。
（付記７）
前記複数の演算部は、複数のプロセッサであることを特徴とする付記１乃至５のいずれか１項に記載の並列処理装置。
（付記８）
データに対する演算を並列に実行する複数の演算部を含む並列処理装置において、
コンピュータが、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、
前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、
前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる、
ことを特徴とする並列処理方法。
（付記９）
前記コンピュータは、前記データに対する演算処理の処理時間が前記目標時間以下となり、かつ、前記処理時間が前記目標時間に近づくように、前記推定演算時間を決定し、前記データの複数の部分各々を前記第１部分とみなして、最後の部分に対する演算が終了するまで、前記第２並列度が示す個数の演算部に前記第２部分に対する演算を実行させる制御を繰り返すことを特徴とする付記８記載の並列処理方法。
（付記１０）
前記コンピュータは、前記第１部分よりも前の演算対象である第３部分に対する演算の演算時間の計測値と、前記第３部分に対する演算の第３並列度と、前記第１部分に対する演算の演算時間の計測値と、前記第１並列度とに基づいて、前記第１部分に対する演算処理の予測処理時間と前記第１部分に対する演算処理の実処理時間との差分を求め、前記差分が第１閾値よりも大きい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも減少させることを特徴とする付記８又は９記載の並列処理方法。
（付記１１）
前記コンピュータは、前記差分が前記第１閾値よりも小さな第２閾値よりも小さい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも増加させることを特徴とする付記３記載の並列処理方法。
（付記１２）
データに対する演算を並列に実行する複数の演算部を含む並列処理装置におけるコンピュータのためのプログラムであって、
前記データの第１部分に対する演算の終了時に、前記データに対する演算処理の目標時間と、前記データのうち演算が行われていない残りのデータのデータ量とに基づいて、前記第１部分の次の演算対象である第２部分に対する演算の推定演算時間を求め、
前記第１部分に対する演算の第１並列度と、前記第１部分に対する演算の演算時間の計測値と、前記推定演算時間とに基づいて、前記第２部分に対する演算の第２並列度を求め、
前記複数の演算部のうち前記第２並列度が示す個数の演算部に、前記第２部分に対する演算を実行させる、
処理を前記コンピュータに実行させるためのプログラム。
（付記１３）
前記コンピュータは、前記データに対する演算処理の処理時間が前記目標時間以下となり、かつ、前記処理時間が前記目標時間に近づくように、前記推定演算時間を決定し、前記データの複数の部分各々を前記第１部分とみなして、最後の部分に対する演算が終了するまで、前記第２並列度が示す個数の演算部に前記第２部分に対する演算を実行させる制御を繰り返すことを特徴とする付記１２記載のプログラム。
（付記１４）
前記コンピュータは、前記第１部分よりも前の演算対象である第３部分に対する演算の演算時間の計測値と、前記第３部分に対する演算の第３並列度と、前記第１部分に対する演算の演算時間の計測値と、前記第１並列度とに基づいて、前記第１部分に対する演算処理の予測処理時間と前記第１部分に対する演算処理の実処理時間との差分を求め、前記差分が第１閾値よりも大きい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも減少させることを特徴とする付記１２又は１３記載のプログラム。
（付記１５）
前記コンピュータは、前記差分が前記第１閾値よりも小さな第２閾値よりも小さい場合、前記第２部分のデータ量を前記第１部分のデータ量よりも増加させることを特徴とする付記１４記載のプログラム。
【符号の説明】
【０１４４】
２０１〜２０３、１４０１−１〜１４０１−４、１４０２−１〜１４０２−４  折れ線
３０１、５０１、１７０１  並列処理装置
３１１−１〜３１１−Ｎ  演算部
３１２、５１１  制御部
５１２  記憶部
５１３  ＦＰＧＡ
６０１  制御回路
６０２  入力回路
６０３  演算処理回路
６０４  出力回路
６１１  レジスタ
６２１  入力バッファ
６２２−１〜６２２−Ｎ、６４１−１〜６４１−Ｎ  バッファ
６３１−１〜６３１−Ｎ  演算器
６４１  バッファ
６４２  データ統合回路
７０１  受付部
７０２  主制御部
７０３  出力部
７０４  データ量決定部
７０５  並列度決定部
７０６  送信部
７０７  指示部
７０８  計測部
７０９  受信部
１７１１  並列計算機
１８０１  分配部
１８０２−１〜１８０２−Ｎ  プロセッサ
１８０３  集約部
１９０１  ＣＰＵ
１９０２  メモリ
１９０３  入力装置
１９０４  出力装置
１９０５  補助記憶装置
１９０６  媒体駆動装置
１９０７  ネットワーク接続装置
１９０８  バス
１９０９  可搬型記録媒体
【図１】
2019028829.tif 000003
【図２】
2019028829.tif 000004
【図３】
2019028829.tif 000005
【図４】
2019028829.tif 000006
【図５】
2019028829.tif 000007
【図６】
2019028829.tif 000008
【図７】
2019028829.tif 000009
【図８】
2019028829.tif 000010
【図９】
2019028829.tif 000011
【図１０】
2019028829.tif 000012
【図１１】
2019028829.tif 000013
【図１２】
2019028829.tif 000014
【図１３】
2019028829.tif 000015
【図１４】
2019028829.tif 000016
【図１５】
2019028829.tif 000017
【図１６】
2019028829.tif 000018
【図１７】
2019028829.tif 000019
【図１８】
2019028829.tif 000020
【図１９】
2019028829.tif 000021