(57)【要約】【課題】通信が不安定な状況であっても、高い確度で通信時間を予測し、最適な処理の分担を行うことができる処理分担制御装置を提供する。【解決手段】第１、第２の演算装置のそれぞれが全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１、第２の個別処理資源推定値を保持する処理資源推定部と、第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された第１の通信資源推定値、及び第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された第２の通信資源推定値を保持する通信資源推定部と、第１の個別処理資源推定値、第２の個別処理資源推定値、第１の通信資源推定値及び第２の通信資源推定値に基づいて、第１の演算装置及び第２の演算装置への個別処理の分担を決定する処理分担パターン生成部と、を備える。【選択図】  図１
2013196174.tif 000002
【特許請求の範囲】
【請求項１】
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成部と、
を備えることを特徴とする処理分担制御装置。
【請求項２】
前記第１の通信資源推定値及び前記第２の通信資源推定値は、前記個別処理の実行開始前及び完遂後の各々について求められる
を備えることを特徴とする請求項１に記載の処理分担制御装置。
【請求項３】
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値は、前記第１の演算装置及び前記第２の演算装置の各々が前記個別処理を実行したときの、全処理能力に対する、使用された処理能力の比である処理能力使用率とに基づいて求められる
を備えることを特徴とする請求項１又は２に記載の処理分担制御装置。
【請求項４】
前記個別処理は、前記全体処理の入力情報のうちの所定の分担量の処理であり、
前記第１の個別処理資源推定値及び前記第２の個別処理資源推定値は、前記分担量に基づいて求められる
ことを特徴とする請求項１乃至３のいずれかに記載の処理分担制御装置。
【請求項５】
前記第１の通信資源推定値及び前記第２の通信資源推定値は、前記分担量に対する前記個別処理の結果として出力される出力情報量に基づいて求められる
ことを特徴とする請求項４に記載の処理分担制御装置。
【請求項６】
前記分担を、前記第１の演算装置及び前記第２の演算装置に出力する処理分担パターン配信部
を備えることを特徴とする請求項１乃至５のいずれかに記載の処理分担制御装置。
【請求項７】
演算部と、
前記演算部が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び外部の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、
前記演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記演算装置との間に必要な通信資源である通信資源推定値を保持する通信資源推定部と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、及び前記通信資源推定値に基づいて、前記演算部及び前記演算装置への前記個別処理の分担を決定する処理分担パターン生成部と、
含む処理分担制御装置と、
を備えることを特徴とする演算装置。
【請求項８】
第１の演算装置と、
第２の演算装置と、
前記第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び前記第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部、前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部、並びに前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成部を含む処理分担制御装置と、
を備えることを特徴とする演算システム。
【請求項９】
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源値を推定して第１の個別処理資源推定値を求め、
第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値を推定して第２の個別処理資源推定値を求め、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて前記第１の演算装置との間に必要な通信資源を推定して、第１の通信資源推定値を求め、
前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて前記第２の演算装置との間に必要な通信資源を推定して、第２の通信資源推定値を求め、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する
ことを特徴とする処理分担制御方法。
【請求項１０】
処理分担制御装置が備えるコンピュータを、
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定手段と、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定手段と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成手段
として機能させることを特徴とする処理分担制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の演算装置への処理の分担の制御を行う処理分担制御装置、演算装置、演算システム、処理分担制御方法、及び処理分担制御プログラムに関し、特に、使用される資源の推定値に基づいて処理の分担を決定する処理分担制御装置、演算装置、演算システム、処理分担制御方法、及び処理分担制御プログラムに関する。
【背景技術】
【０００２】
複数の演算装置を備える演算システムを用いて、処理を分担して実行する技術が知られている。処理の分担のさせ方によって、演算システム全体としての処理性能が大きく影響を受ける。そのため、演算システム全体の処理性能を最大化するためには、処理の分担の最適化が求められる。
【０００３】
ところが、一般に、複数の演算装置の各々の処理性能や使用可能な資源の量は必ずしも等しくない。また、処理を分担するには、演算装置間の情報の通信が必要である。
【０００４】
従って、複数の演算装置への処理の分担を決定するときは、各演算装置の性能や資源等を考慮しなければならない。  複数の計算手段が通信手段で接続された演算装置において、複数の計算手段の間で処理を分担させる方法が、特許文献１、特許文献２、特許文献３に開示されている。
【０００５】
特許文献１の技術では、端末やサーバの種類が限定されている場合に、あらかじめ処理分担パターンを定めておくことで、複数の処理ユニットの間での処理分担を行う。その際、処理ユニットの処理時間が考慮される。
【０００６】
特許文献２の技術では、複数のＣＰＵ（Central Processing Unit）コアの各々において処理を行う場合に処理にかかる時間を推測する。そして、推測された処理時間を元に、全体として処理時間が最小になるように、複数のＣＰＵコアの間で処理を分担する。その際、ＣＰＵコア間の通信時間及び各ＣＰＵの処理時間が考慮される。
【０００７】
特許文献３記載の技術では、演算装置（ノード）間の通信量や通信時間、演算装置が演算を実行するときに要する時間などを取得し、それらを用いてタスク割り付けのパターンごとの性能を予測する。そして、予想された性能に基づいて、タスク割り付けを行う。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開昭６３−１８１０８２号公報  （第３頁、第３図）
【特許文献２】特開２０１０−７９６２２号公報  （第１１−１３頁、図１０、１１）
【特許文献３】特開２０１０−２５７０５６号公報  （第６−７頁、図２）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１乃至３の技術には、「通信時間」の取り扱い又はその推定方法に課題がある。
【００１０】
特許文献１記載の技術では、処理ユニットにおける処理速度の推測のみを利用して処理の分担を行おり、通信時間を考慮していない。前述のように、処理を分担するためには、他の処理ユニットとの間で、入出力データの送受信等の通信が必要である。
【００１１】
処理の分担の良否は、例えば、分担された各処理についての処理時間の合計である、全体としての処理時間を用いて評価することができる。そのため、処理ユニットの処理速度だけでなく、通信に要する時間も考慮して処理分担を行わななければ、全体としての処理時間は必ずしも最小にならない。このように、特許文献１の技術には、「通信時間」を考慮しないために、最適な処理の分担を行うことができないというという課題がある。
【００１２】
特許文献２記載の技術においては、処理パターンを決定する際にＣＰＵコア間の通信時間を考慮することは記載されている。考慮される対象の通信時間が、同一チップ内、同一基板内、あるいは同一装置内におけるＣＰＵコア間の通信時間であれば、高い確度での予測が可能と考えられる。ところが、異なる装置内のＣＰＵコア間の通信時間の予測は、必ずしも容易ではない。例えば、端末とサーバとが無線通信によって接続されている場合、無線通信という特性上、通信が不安定になることがある。そのため、端末内のＣＰＵとサーバ内のＣＰＵとの間の通信時間は、通信を行うごとに変動する可能性がある。従って、特許文献２の技術では、通信時間も考慮されて処理分担が決定されるものの、通信が安定していない場合には、最適な処理分担が得られない可能性があるという課題がある。
【００１３】
特許文献３記載の技術についても同様であり、通信が安定していない場合への適用に課題がある。
（発明の目的）
本発明は上記のような技術的課題に鑑みて行われたもので、通信が不安定な状況であっても、高い確度で通信時間を予測し、最適な処理の分担を行うことができる、処理分担制御装置、演算装置、演算システム、処理分担制御方法、及び処理分担制御プログラムを提供することを特徴とする。
【課題を解決するための手段】
【００１４】
本発明の処理分担制御装置は、第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部と、第１の個別処理資源推定値、第２の個別処理資源推定値、第１の通信資源推定値及び第２の通信資源推定値に基づいて、第１の演算装置及び第２の演算装置への個別処理の分担を決定する処理分担パターン生成部と、を備えることを特徴とする。
【００１５】
本発明の演算装置は、演算部と、演算部が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び外部の演算装置が個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、演算装置との間に必要な通信資源である通信資源推定値を保持する通信資源推定部と、第１の個別処理資源推定値、第２の個別処理資源推定値、及び通信資源推定値に基づいて、演算部及び演算装置への個別処理の分担を決定する処理分担パターン生成部と、含む処理分担制御装置と、を備えることを特徴とする。
【００１６】
本発明の演算システムは、第１の演算装置と、第２の演算装置と、第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部、第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部、並びに第１の個別処理資源推定値、第２の個別処理資源推定値、第１の通信資源推定値及び第２の通信資源推定値に基づいて、第１の演算装置及び第２の演算装置への個別処理の分担を決定する処理分担パターン生成部を含む処理分担制御装置と、を備えることを特徴とする。
【００１７】
本発明の処理分担制御方法は、第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源値を推定して第１の個別処理資源推定値を求め、第２の演算装置が個別処理を完遂するために必要な処理資源の推定値を推定して第２の個別処理資源推定値を求め、第１の演算装置との間の過去の通信に用いられた通信資源に基づいて第１の演算装置との間に必要な通信資源を推定して、第１の通信資源推定値を求め、第２の演算装置との間の過去の通信に用いられた通信資源に基づいて第２の演算装置との間に必要な通信資源を推定して、第２の通信資源推定値を求め、第１の個別処理資源推定値、第２の個別処理資源推定値、第１の通信資源推定値及び第２の通信資源推定値に基づいて、第１の演算装置及び第２の演算装置への個別処理の分担を決定することを特徴とする。
【００１８】
本発明の処理分担制御プログラムは、処理分担制御装置が備えるコンピュータを、第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定手段と、第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定手段と、第１の個別処理資源推定値、第２の個別処理資源推定値、第１の通信資源推定値及び第２の通信資源推定値に基づいて、第１の演算装置及び第２の演算装置への個別処理の分担を決定する処理分担パターン生成手段として機能させることを特徴とする。
【発明の効果】
【００１９】
本発明によると、通信が不安定な状況であっても、高い確度で通信時間を予測し、最適な処理分担を行うことができる。
【図面の簡単な説明】
【００２０】
【図１】第１の実施形態の処理分担制御装置の構成を示すブロック図である。
【図２】第１の実施形態の処理分担制御装置のハードウェア構成を示すブロック図である。
【図３】第１の実施形態の個別処理資源推定値表の具体例である。
【図４】第１の実施形態の個別通信資源推定値表の具体例である。
【図５】第１の実施形態の処理分担パターン図の具体例である。
【図６】第１の実施形態の処理分担制御装置の動作を示すフローチャートの例である。
【図７】第１の実施形態の資源推定要求処理の具体例である。
【図８】第１の実施形態の処理分担制御装置における、動的計画法による処理分担パターンの生成動作を示すフローチャートの例である。
【図９】第２の実施形態の処理分担制御装置の構成を示すブロック図である。
【図１０】第２の実施形態の処理分担パターン管理部の内部構成の具体例を示すブロック図である。
【図１１】第２の実施形態の個別装置用処理分担パターン図の具体例である。
【図１２】第２の実施形態の処理分担制御装置の動作を示すフローチャートの例である。
【図１３】第３の実施形態の演算装置が実行するソフトウェアの構成を示すブロック図である。
【図１４】第３の実施形態の演算装置の動作を示すフローチャートの例である。
【図１５】第４の実施形態の演算システムの構成を示すブロック図である。
【発明を実施するための形態】
【００２１】
（第１の実施形態）
次に、本発明の実施の形態について、図面を参照して詳細に説明する。本実施の形態では、各演算装置にどのように処理を分担させるかを指定するデータである処理分担パターンを生成する処理分担制御装置について説明する。
【００２２】
図１は、第１の実施形態の処理分担制御装置の構成を示すブロック図である。以下、処理分担制御装置１に含まれるソフトウェア構成について説明する。
【００２３】
本実施形態の処理分担制御装置１は、処理資源推定部１１と、通信資源推定部１２と、処理分担パターン生成部１３を備える。
【００２４】
図２は、図１の処理分担制御装置のハードウェア構成の一例を示す。処理分担制御装置１は、ＣＰＵ５、メモリ６、通信手段７とを備える。処理分担制御装置１は、ＣＰＵ５等の計算手段を用いて、メモリ６に格納されているプログラムやデータを随時読み出し、必要に応じて通信手段７を用いて外部の演算装置との通信処理を行う。
【００２５】
処理資源推定部１１は、分担対象の処理を行うために必要な資源である計算資源の推定値を保持する。計算資源の推定値とは、具体的には、データ処理において、あらかじめ区切られた部分的な処理である部分処理の各々を個別に処理するために要する処理資源である「個別処理資源」である。本実施形態の説明では、データ処理があらかじめＰ個（Ｐは１以上の整数）の「個別処理」に分割されているものとする。以降、個別処理と対比して表現する必要があるときは、分割前のデータ処理を「全体処理」という。
【００２６】
なお、分担される対象の個別処理は、全体処理の一部であればよく、必ずしも、全体処理のすべてが分担対象である必要はない。つまり、分担対象の個別処理は、全体処理に含まれるものであればよい。
【００２７】
また、個別処理が複数存在する場合、それぞれの個別処理は、並列に処理されてもよいし、順次、処理されてもよい。後述のように、個別処理の分担の良否を判断する基準は、システムに求められる要件によって、任意に設定される。従って、個別処理が並列に処理される場合と、順次、処理される場合とでは、個別処理の分担は変化する可能性がある。
【００２８】
推定によって求められる個別処理資源は、実際に演算装置が処理を分担し、実際に処理を行うときに必要と推測される処理資源である。この個別処理資源は次のようにして推定することができる。すなわち、分担させる演算装置の各々に、実験的に個別処理を実行させ、そのとき処理に要した資源を実測する。例えば、資源が処理時間である場合は、個々の演算装置が処理に要した時間あるいはクロック数等を実測することにより、実際の運用時にも同等の処理時間を要すると推定することができる。
【００２９】
個別処理資源の推定結果を示す個別処理資源推定値表の具体例を、図３に示す。個別処理資源推定値表は、全体処理を構成する各部分処理に対して、どれくらいの計算資源が必要であるかを推測した結果を示す。推測値の具体例は、後述する。
【００３０】
通信資源推定部１２は、処理分担パターン生成部１３が生成した処理分担パターンに従って、演算装置間の処理を切り替える際、切り替えに必要なデータを送受信するために必要な資源である個別通信資源を推定する。
【００３１】
他の演算装置へ個別処理を分担させるときは、処理に使用する入力データあるいは処理の実行を指示する制御情報等の入力情報を送信してもよい。個別処理が終了したときは、処理の結果としての出力データあるいは処理の終了を通知する制御情報等の出力情報を受信してもよい。従って、個別通信資源は、個別処理の開始前の通信及び個別処理の完遂後の通信の両方について推定してもよい。
【００３２】
推定によって求められる個別通信資源は、実際に通信を行うときに必要と推測される通信資源である。この個別通信資源は次のようにして推定することができる。すなわち、実験的に処理分担制御装置１と演算装置との間で通信を行い、そのとき処理に要した資源を実測する。例えば、資源が通信時間である場合は、演算装置間の通信時間を実測することにより、実際の運用時にも同等の通信時間を要すると推定することができる。
【００３３】
ところで、通信時間はデータ量によって変化する。他の演算装置に分担させる前に送信する、個別処理のための入力情報のデータ量、及び個別処理の終了後に受信する、個別処理の結果としての出力情報のデータ量は、個別処理の内容から推定することができる。そこで、その推定データ量のデータを送受信するときの通信時間を測定してもよい。あるいは、演算装置間の、単位データ量当りの通信時間を測定し、推定データ量で換算することによって、通信時間を推定してもよい。
【００３４】
個別通信資源の推定結果を示す個別通信資源推定値表の具体例を、図４に示す。個別通信資源推定値表は、各部分処理の開始前に入力情報を送信するために必要な通信資源、及び各部分処理の終了後の出力情報、すなわち、他の演算装置が後続の処理を行う際に用いる情報を受信するために必要な通信資源を推測した結果を示す。推測値の具体例は、後述する。
【００３５】
処理分担パターン生成部１３は、処理資源推定部１１及び通信資源推定部１２から推定値を入力する。さらに、外部の演算装置が備える処理資源推定部１１及び通信資源推定部１２から、個別処理資源と個別通信資源の推定値を入力してもよい。
【００３６】
処理分担パターン生成部１３は、あらかじめ定められた評価基準を最適化する処理分担を決定し、「処理分担パターン」として生成する。
【００３７】
加えて、処理分担パターン生成部１３は、処理分担パターンの生成に必要な装置ＩＤ（Identification Data）を設定する。装置ＩＤは、処理分担制御装置１と、処理分担制御装置１に接続される演算装置（図１における演算装置２、・・・、Ｎ（Ｎは１以上の整数））を一意に対応付けるために設定される。演算装置と装置ＩＤとの対応付けは、あらかじめ与えてられても良いし、処理分担制御装置１の動作の開始時もしく動作中に、その都度設定されても良い。
【００３８】
なお、処理分担を決定する具体的な手段の一例として、動的計画法を利用することができるが、これに限られない。
【００３９】
処理分担パターンの一例を、図５に示す。処理分担パターンは、装置ＩＤをＰ個並べた数値の列である。処理分担パターンは、個別処理とそれを実行する演算装置とを対応付ける。すなわち、処理分担パターンの左からｉ（ｉは１≦ｉ≦Ｐの整数）番目の要素が、個別処理ｉ（１≦ｉ≦Ｐ）を分担することを示す。例えば、図５の例では、個別処理の１番目を装置ＩＤが”１”の装置が、個別処理のＰ番目を装置ＩＤが”２”の装置が分担することが指定されていることを示す。
（動作の説明）
次に本実施形態の動作を説明する。
【００４０】
図６は、本実施形態の動作を示すフローチャートの一例を示す。本実施形態の処理分担制御装置１は、処理分担生成開始要求入力処理（ステップＳ１１）、資源推定要求処理（ステップＳ１２）、資源推定結果獲得処理（ステップＳ１３）、処理分担パターン生成処理Ｓ（ステップ１４）の順に動作する。
【００４１】
まず、処理パターン生成部１３が、外部からの処理分担生成要求を入力する（処理分担生成開始要求入力、ステップＳ１１）。
【００４２】
次に、処理パターン生成部１３が、資源推定要求処理（ステップＳ１２）を行う。具体的には、ステップＳ１２は、個別処理資源の推定要求と、個別通信資源の推定要求とを含む。
【００４３】
資源推定要求処理（ステップＳ１２）の動作の一例を図７に示す。具体的には、まず、処理パターン生成部１３が、処理資源推定部１１に対して個別処理資源の推定を要求する（ステップＳ１２１）。次に、処理パターン生成部１３が、通信資源推定部１２に対して個別通信資源の推定を要求する（ステップＳ１２２）。推定を要求された処理資源推定部１１及び通信資源推定部１２の各々は、内部に保持する推定値を出力するか、あるいはその時点で所定の測定等を行って推定を行い、推定値を出力する。
【００４４】
なお、個別処理資源の推定（ステップＳ１２１）は、個別処理１、・・・Ｐについて行われる。個別通信資源の推定は、処理分担制御装置１と通信手段を介して接続されている外部の演算装置２、・・・、Ｎの各々に対して行われる。外部の演算装置は、複数台あっても、１台であっても良い。
【００４５】
再び、図６のフローチャートを参照する。次に、処理生成パターン生成部１３は、資源推定結果獲得処理（ステップＳ１３）を行う。すなわち、処理生成パターン生成部１３は、処理資源推定部１１及び通信資源推定部１２からの推定結果の受信まで待機する。ここで、資源推定要求を行ってから、あらかじめ定められた一定時間経過しても結果が返されない場合は、待機を打ち切ってもよい。
【００４６】
次に、処理分担パターン生成部１３は、処理分担パターンを生成する（ステップＳ１４）。処理分担パターンを求めるには、推定された個別処理ごとの計算資源を利用して、貪欲法、動的計画法などの最適化手法を利用する。もちろん、すべての処理分担の可能性を総当たりで調べ上げることで、最適な処理分担パターンを求めても構わない。
【００４７】
最適な分担処理パターンを求める方法の例としては、例えば、「貪欲法」、「動的計画法」がある。以下に、それぞれの方法による具体的な分担処理パターンの決定方法を説明する。
（１）貪欲法
「貪欲法」は、問題を複数の部分問題に分割し、それぞれに対して独立に評価を行い、評価値の高い順に選択することによって、解を得るという方法である。従って、貪欲法は、個別処理１から個別処理Ｐまでが独立に処理可能である場合に好適な方法である。
【００４８】
次に述べる例では、処理分担制御装置１上にあるデータを複数の演算装置で分担して処理する例を考える。
【００４９】
この場合、個別通信資源は、個別処理に必要なデータを、処理分担制御装置１から各演算装置へ送信するために必要な通信時間推定値（個別通信資源推定値）と、個別処理結果を各演算装置から処理分担制御装置１へ送信するために必要な通信時間である個別結果通信資源の推定値との和である。個別結果通信資源の推定に関しては、個別通信資源の推定と同様の構成・動作で実現可能である。
【００５０】
適切な処理分担を定めるために、例えば、初期状態では、すべての個別処理をすべて演算装置２で処理するものとする。すなわち、処理分担パターンを、（２，２，２，・・・，２）とする。そして、処理分担パターンを逐次的に変更し、評価関数値
ｍａｘ（ｔ２，ｔ３，ｔ４，・・・，ｔｎ）
が可能な限り小さくなるときの、処理分担パターンを求める。
【００５１】
ここで、ｔ２，ｔ３，・・・，ｔＮは、演算装置ｎ（２≦ｎ≦Ｎ）が行う個別処理に関する個別通信資源と個別結果通信資源及び個別処理資源の総和である。
【００５２】
初期状態では処理分担パターンが（２，２，２，・・・，２）なので、
ｍｉｎ（ｔ２，ｔ３，ｔ４，・・・，ｔｎ）＝ｔ２≧０
であり、
ｔ３＝・・・＝ｔＮ＝０
である。
【００５３】
なお、通信資源が時間で、処理資源が消費電力である場合のように、資源の量を表現する単位が異なる場合は、適当な係数を用いて換算し、総計を求めればよい。
【００５４】
具体的には、以下のような動作を行う。
１）処理分担パターン（２，２，２，・・・，２）として、部分処理を分担している演算装置の中で、評価関数値ｍａｘ（ｔ２，ｔ３，ｔ４，・・・，ｔＮ）の値を最も大きく減少させるように、１つの個別処理の分担を、演算装置２から他の演算装置の分担へと変更する。
２）部分処理１からＰまで、順次、上述の（１）の手続きを繰り返し、分担を変更する。
３）評価関数値を減少させるような分担変更がない場合は、（２，２，２，・・・，２）を処理分担結果とする。
【００５５】
処理分担パターンに対して、上述の１）−３）の手続きを繰り返し変更することにより、部分処理ごとに、分担に適した演算装置が判定され、最終的に処理分担パターンを生成することができる。
（２）動的計画法
「動的計画法」は、問題を複数の段階に分解して、各段階で順次処理される複数の部分問題に分解し、ある段階までの最適解以外を破棄しながら、最適解を求める方法である。従って、動的計画法は、全体処理を個別処理１から個別処理Ｐまでに分割し、各個別処理を順番に行う必要がある場合に、好適である。
【００５６】
以下の例は、処理分担制御装置１上にあるデータを入力データとして、個別処理１から個別処理Ｐまでを順番に処理して、最終結果を処理分担制御装置１上に返す例を考える。
【００５７】
ここで、装置ＩＤが、１≦ｊ≦Ｐなるｊ（ｊは整数）である装置について、個別通信資源Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））と個別処理資源Ｅ（ｊ，ｂ（ｊ））を定義する。
【００５８】
Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））は、個別処理ｊを行うために、個別処理（ｊ−１）において演算装置ａ（ｊ）で処理された結果を、演算装置ｂ（ｊ）に送信する個別通信資源の値を示す。Ｅ（ｊ，ｂ（ｊ））は、個別処理ｊを演算装置ｂで処理するための個別処理資源の値を示す。
【００５９】
便宜上、個別処理１の実行前に、すなわち、最初の個別処理の実行前に、演算装置ｂ（ｊ）（ｂ（ｊ）は２，３，・・・，Ｎのいずれか）への通信に要する時間（個別通信資源）をＣ（０，ａ（０），ｂ（０））とする。個別処理Ｐの実行後に、すなわち、最終の個別処理の終了後に、結果を処理分担制御装置１へ送る時間（個別通信資源）をＣ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１））とする。
【００６０】
ａ（０）≠１に対して、Ｃ（０，ａ（０），ｂ（０））は、後述の、評価関数の値を最小化する値と比べて、十分に大きな数を設定する。このことを
Ｃ（０，ａ（０），ｂ（０））＝∞
と表記する。
【００６１】
また、ｂ（Ｐ＋１）≠１に対して、
Ｃ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１））＝∞
である。
【００６２】
なお、Ｅ（０，ｂ（０））及びＥ（ｊ＋１，ｂ（Ｐ＋１））は０とするのが一例であるがこれに限られない。
【００６３】
ここで、評価関数値として、Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））＋Ｅ（ｊ，ｂ（ｊ））の、Ｊ＝０からＰ＋１までの総和      Σ（Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））＋Ｅ（ｊ，ｂ（ｊ）））
を求める。ただし、ａ（ｊ）とｂ（ｊ）の組み合わせに関して、
ｂ（ｊ−１）＝ａ（ｊ）
すなわち、個別処理ｊに先立って行われる通信の送信元ａ（ｊ）と、個別処理ｊ−１を行った演算装置ｂ（ｊ−１）が一致している組み合わせに関してのみ、総和を求める。
【００６４】
そして、上記の評価関数の値をできるだけ小さくするようなｂ（ｊ）（ｊ＝１，・・・，Ｐ）を求める。
【００６５】
次に、処理資源Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））を定義する。Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））は、「演算装置ａ（ｊ）から演算装置ｂ（ｊ）への通信を行い、かつ、個別処理ｊを演算装置ｂ（ｊ）が処理する」という条件の下で最小の処理資源の値である。
【００６６】
Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））は、ｂ（ｊ−１）＝ａｊなる条件の下、Ｖ（ｊ−１，ａ（ｊ−１），ｂ（ｊ−１））＋Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））＋Ｅ（ｊ，ｂ（ｊ））の値が最小になるときの、ａ（ｊ）、ｂ（ｊ）である。すなわち、
Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））
＝ｍｉｎ（ａ（ｊ）、ｂ（ｊ）；Ｖ（ｊ−１，ａ（ｊ−１），ｂ（ｊ−１））＋Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））＋Ｅ（ｊ，ｂ（ｊ）））
である。ただし、ここでの関数ｍｉｎ（ｘ；ｙ）は、ｙが最小になるときの、ｘを意味する。
【００６７】
分担処理パターンを求めるためには、まず、ｊ＝０からＰ＋１まで順番に、Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））を逐次的に計算することにより、Ｖ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１））を求める。
【００６８】
次に
ｍｉｎ（ｂ（Ｐ＋１）；Ｖ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１）））
の値を求める。このｂ（Ｐ＋１）が、個別通信資源と個別処理資源の総和を最小化する値となる。
【００６９】
次に、最小化を実現したａ（ｊ）及びｂ（ｊ）を計算する。これは、Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））が計算された過程を、ｊ＝Ｐ＋１からｊ＝０へ追跡することによって、求めることができる。このようにすると、分担処理パターンは（ｂ（１），ｂ（２），・・・，ｂ（Ｐ））として求めることができる。
【００７０】
図８は、本実施形態の処理分担制御装置において、動的計画法を用いて処理分担パターンを生成するときの動作を示すフローチャートの例である。図８では、処理分担制御装置が１個、演算装置がＰ＝２個の場合の、個別通信資源と個別処理資源の例を示す。装置ＩＤｊは、処理分担制御装置が１、２個の演算装置がそれぞれ、２、３である。以下では、それぞれの装置を、処理分担制御装置１、演算装置２、３と表す。
【００７１】
前処理では、処理前の、仮の処理結果を、処理分担制御装置１から、演算装置２又は演算装置３へ送信するから、個別通信資源は、
Ｃ（０、１、２）、Ｃ（０、１、３）
となる。それぞれに対応する個別処理資源は、
Ｅ（０、２）、Ｅ（０、３）
である。
【００７２】
処理１の実行前には、前処理を行った演算装置で処理１を再び実行するか、又は他方の演算装置で前処理の結果を送信するから、個別通信資源は、
Ｃ（１、２、２）、Ｃ（１、２、３）、Ｃ（１、３、２）、Ｃ（１、３、３）
となる。そして、演算装置２、３は、処理１を実行する。
【００７３】
上記のそれぞれの個別通信資源に対応する個別処理資源は、処理１を処理するための個別処理資源と、その処理を行った演算装置の装置ＩＤから、
Ｅ（１、２）、Ｅ（１、３）Ｅ（１、２）、Ｅ（１、３）
となる。
【００７４】
以降同様にして、後処理まで、順次、Ｃ（ｊ，ａ（ｊ），ｂ（ｊ））とＥ（ｊ，ｂ（ｊ））を求める。そして、ｊ＝０からＰ＋１まで順番に、Ｖ（ｊ，ａ（ｊ），ｂ（ｊ））を逐次的に計算することにより、Ｖ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１））を求め、ｍｉｎ（ｂ（Ｐ＋１）；Ｖ（Ｐ＋１，ａ（Ｐ＋１），ｂ（Ｐ＋１）））の値を求める。
【００７５】
図８中の矢印は、個別通信資源と個別処理資源の総和を最小化した値を追跡した結果を示している。この場合、処理パターンは、（２，３，・・・，２）となる。
【００７６】
最適化の程度は、推定された個別処理ごとの計算資源を利用して、全体処理に必要な計算資源を推測することによって評価することができる。この場合、最適化の程度を評価するための評価基準の好適な例としては、推定された計算資源の総計の最小化、最大化を採用する方法がある。すなわち、計算資源の総計が最小又は最大になるように個別処理の分担を決定する方法がある。
【００７７】
処理資源推定部１１及び通信資源推定部１２が行う資源の推定方法の具体例を示す。処理資源推定部１１が行う処理資源の推定方法には、例えば、あらかじめ準備された推定値のテーブルから処理資源を取得する方法がある。さらに、現在の処理資源の利用状況を考慮して、取得した推定値を補正して使用しても良い。
【００７８】
通信資源推定部１２が行う通信資源の推定方法には、例えば、あらかじめ準備された推定値のテーブルから通信資源を取得する方法がある。さらに、現在の通信資源の利用状況を考慮して、取得した推定値を補正して使用しても良い。
【００７９】
推定値テーブルに保持される個別処理資源及び個別通信時間に関する推定値は、過去の値を参照して、あらかじめ推測された値でもよい。
【００８０】
例えば、個別処理資源として、個別処理に要する処理時間を用いる場合は、個別処理時間の履歴を保存する。そして、過去の個別処理時間から、実際の処理時に個別処理時間を推測する。
【００８１】
具体的には、個別処理の実行回数を示す番号をｉ（ｉは１以上の整数）、処理した回数をＮ（Ｎはｉ以上の整数）として、個別処理に要した処理時間の平均値
（Σ（ｉ番目の処理の個別処理時間））／Ｎ
を求め、個別処理資源の推定値とすればよい。
【００８２】
個別処理に要した処理時間に加え、ＣＰＵ使用率に関する履歴も保存してもよい。この場合は、ＣＰＵ使用率を１００％とした場合に期待される処理時間を計算し、個別処理資源の推定値とすることができる。
【００８３】
具体的には、処理の回数を示す番号をｉ、処理した回数をＮとして、
（Σ（ｉ番目の処理の個別処理時間）×（ｉ番目の処理の際のＣＰＵ使用率［％］）／１００））／Ｎ
を求め、個別処理資源の推定値とすればよい。
【００８４】
なお、個別処理に要した処理時間及びＣＰＵ使用率の履歴の中でも、分担を決定する直前の値を用いれば、さらに、確度の高い個別処理資源の推定値を求めることができる。
【００８５】
通信時間に関しても同様である。すなわち、過去の通信時間の履歴から、平均値を求め、個別通信資源の推定値としてもよい。このとき、通信時間の履歴の中でも、分担を決定する直前の通信時間を用いれば、さらに、確度の高い個別通信資源の推定値を求めることができる。
【００８６】
次に本実施形態の効果を説明する。上述のように、処理分担制御装置１は、処理資源及び通信資源の履歴を用いて、演算装置に対する処理資源及び通信資源を推定する。そして、取得した資源の推定値を用いて、処理分担を決定する。従って、高い確度で、最適な処理の分担を行うことができるという効果がある。
（第２の実施形態）
本発明の第２の実施形態の処理分担制御装置について説明する。第２の実施形態の処理分担制御装置Ｂ１は、第１の実施形態の処理分担制御装置１の機能に加えて、生成された処理分担パターンを通信手段で接続された他の演算装置に出力する機能を備える。
【００８７】
本実施形態の処理分担制御装置Ｂ１の主要部分の構成及びその動作は、第１の実施形態の処理分担制御装置１の構成及び動作と共通である。そのため、本実施形態の処理分担制御装置Ｂ１と第１の実施形態の処理分担制御装置１の構成及び動作との、異なる点のみについて説明する。
【００８８】
図９は、第２の実施形態の処理分担制御装置Ｂ１の構成の一例を示したブロック図である。処理分担制御装置Ｂ１と第１の実施形態の処理分担制御装置１との、構成の相違点は、処理分担制御装置１の処理分担パターン生成部１３が処理分担パターン管理部Ｂ１３に置き換えられている点のみである。
【００８９】
図１０は、第２の実施形態の処理分担パターン管理部Ｂ１３の構成の一例を示したブロック図である。処理分担パターン管理部Ｂ１３は、処理分担パターン生成部Ｂ１３１と処理分担パターン配信部Ｂ１３２とを備える。処理分担パターン生成部Ｂ１３１は、第１の実施形態の構成における処理分担パターン生成部１３と同一であるので説明を省略する。
【００９０】
処理分担パターン配信部Ｂ１３２は、生成された処理分担パターンを、他の演算装置２、・・・、Ｎ向けに変換した後に、変換されたパターンを配信する。
【００９１】
図５の処理分担の例を用いて説明する。装置ＩＤ＝２で指定される演算装置２向けには、処理分担パターンのうち要素が”２”となっている要素、すなわち、装置ＩＳ＝２として演算装置２が指定されている要素のみをピックアップする。図５の例では、個別処理１及び個別処理３を行う装置ＩＤが”２”なので、この２つの要素の値を”２”のままとし、それ以外の要素の値を”０”とするようなパターンを生成する。そして、生成したパターンを装置ＩＤ＝２で指定される演算装置２に配信する。このパターンを「個別装置用処理分担パターン」と呼ぶ。図１１は、装置ＩＤ＝２で指定される演算装置２に配信される個別装置用処理分担パターンの一例を示す。以上の個別装置用処理分担パターンの生成処理は、すべての演算装置２、・・・Ｎに関して行われる。
【００９２】
なお、処理分担制御装置１が演算機能を持つ演算部（図示なし）を備え、装置ＩＤ＝１の演算装置として、一部の処理の分担を行ってもよい。この場合は、個別装置用処理分担パターンは、処理分担制御装置１の内部で、演算部へ送信すればよい。
【００９３】
次に、第２の実施形態の動作について説明する。図１２は、第２の実施の形態の動作を示すフローチャートである。ここで、処理分担生成開始要求入力処理（ステップＳＢ１１）、資源推定要求処理（ステップＳＢ１２）、資源推定結果獲得処理（ステップＳＢ１３）、処理分担パターン生成処理（ステップＳＢ１４）は、それぞれ、図６の、処理分担生成開始要求入力処理（ステップＳ１１）、資源推定要求処理（ステップＳ１２）、資源推定結果獲得処理（ステップＳ１３）、処理分担パターン生成処理（ステップＳ１４）と同一である。
【００９４】
第２の実施形態の動作と第１の実施形態の動作とで異なるのは、処理分担パターン生成処理（ステップＳ１４）の終了後に、処理分担パターン配信処理（ステップＳＢ１５）が行われる点である。ステップ（ステップＳＢ１５）では、処理分担パターン配信部Ｂ１３２が他の各演算装置に個別装置用処理分担パターンを配信する。
【００９５】
本実施形態の効果について説明する。第１の実施形態の処理分担制御装置は、処理分担のパターンを生成する機能のみを備える。それに対して、第２の実施形態の処理分担制御装置は、個別処理が分担される各演算装置に対して、どの処理を分担すべきかを指示することができる。これにより、演算装置間で、個別処理を分担して実行することができる。
（第３の実施形態）
次に、本発明の第３の実施形態として、上述のように生成された処理分担パターンを入力して、処理分担を行う演算装置Ａ１について、その構成と動作を説明する。演算装置Ａ１は、処理分担制御装置Ｂ１からの、処理分担パターンによる指示によって、個別処理を分担する。
【００９６】
まず、第３の実施形態の構成について、処理を主にソフトウェアの形態で実現する例について説明する。本実施の形態における処理分担制御装置Ｂ１の構成は、第１の実施形態の処理分担制御装置１の構成と同様であるので説明を省略する。
【００９７】
次に、演算装置Ａ１が実行する処理のソフトウェア構成について説明する。図１３は、第３の実施形態の演算装置Ａ１が実行するソフトウェアの構成を示すブロック図である。演算装置Ａ１の処理は、個別装置用処理分担パターン入力部Ａ１１と個別処理実行部Ａ１２とを含む。
【００９８】
個別装置用処理分担パターン入力部Ａ１１は、個別装置用処理分担パターンを入力し、個別処理用処理分担パターンにて演算装置Ａ１に割り振られた処理の実行を個別処理実行部Ａ１２に対して要求する。
【００９９】
個別処理実行部Ａ１２は、個別装置用処理分担パターン入力部Ａ１１から要求された処理を実行する。
【０１００】
次に、第３の実施形態の動作について説明する。図１４は、第３の実施の形態の動作を示すフローチャートである。まず、個別装置用処理分担パターン入力部Ａ１１が個別処理用処理分担パターン入力処理（ステップＳＡ１１）を行う。次に、個別装置用処理分担パターン入力部Ａ１１が処理実行要求処理（ステップＳＡ１２）を行う。次に、個別処理実行部Ａ１２が個別処理実行処理（ステップＳＡ１３）を行う。
【０１０１】
演算装置Ａ１は、第２の実施形態の処理分担制御装置Ｂ１に接続され、利用されるのが好適である。このとき、処理分担制御装置Ｂ１に接続されるすべての演算装置には、同一の全体処理プログラムが搭載されていてもよい。この場合、各演算装置では、個別処理の単位で一部の処理を省略したり、機能が同等で性能の異なる別の処理に置き換えたりすることも可能である。また、すべての演算装置に同一の全体処理プログラムが搭載されていれば、個別処理を分担するごとに、分担される個別処理のプログラムを分担先の演算装置へ転送する必要がない。
【０１０２】
次に、本実施形態の効果について説明する。上述のように、各演算装置は、処理分担パターン生成部１３によって生成された処理分担パターンに応じて個別処理を分担する。従って、各演算装置は、必要な処理のみを行うことができる。
（第４の実施形態）
次に、上述した各実施形態の具体例を示す。
【０１０３】
第４の実施形態では、第２の実施形態の処理分担制御装置Ｂ１−１、Ｂ１−２と２つの第３の実施形態の演算装置Ａ１−１、Ａ１−２から構成される演算システムの例を示す。図１５は、第４の実施形態の演算システムの構成を表すブロック図である。演算装置Ａ１−１と処理分担制御装置Ｂ１−１は、１つのユニットである統合演算装置Ｃ１として構成される。同様に、演算装置Ａ１−２と処理分担制御装置Ｂ１−２は、１つのユニットである統合演算装置Ｃ２として構成される。処理分担制御装置Ｂ１−１と、演算装置Ａ１−１、処理分担制御装置Ｂ１−１、及び演算装置Ａ１−２の各々との間は通信手段で接続される。
【０１０４】
本実施形態では、統合演算装置Ｃ１をホストとした動作が行われる。すなわち、統合演算装置Ｃ１処理分担パターンを計算する主体であり、あわせて演算装置Ａ１−１の個別計算資源、個別通信資源を推定する。
【０１０５】
一方、統合演算装置Ｃ２は、演算装置Ａ１−２の個別計算資源、個別通信資源を推定する。そして、統合演算装置Ｃ２は、演算装置Ａ１−２の個別計算資源及び個別通信資源の推定値を、統合演算装置Ｃ１へ送信する。
【０１０６】
統合演算装置Ｃ１は、演算装置Ａ１−１の個別計算資源及び個別通信資源の推定値、並びに演算装置Ａ１−２の個別計算資源及び個別通信資源の推定値を用いて、演算装置Ａ１−１、Ａ１−２への処理の分担を指定する処理分担パターンを計算する。
【０１０７】
本実施形態では、資源として処理時間を考える。個別計算資源は、演算装置Ａ１−１、Ａ１−２及び処理分担制御Ｂ１−２における処理時間である。個別通信資源は処理分担制御Ｂ１−１と、演算装置Ａ１−１、Ａ１−２及び処理分担制御Ｂ１−２との間の通信時間である。
【０１０８】
「個別処理時間」は、統合演算装置Ｃ１及び統合演算装置Ｃ２に含まれる処理資源推定部１１によって、それぞれの統合演算装置に関して、次のように推定される。本実施例では、処理資源推定に関する推定値のテーブルとして、演算装置Ａ１−１、Ａ１−２の各々が備えるＣＰＵの処理性能が１００％利用できると仮定した際の推定値をあらかじめテーブル形式で保持しておくこととする。
【０１０９】
処理資源の推定は、例えば、処理資源が処理時間である場合は、あらかじめ個別処理を、演算装置Ａ１−１、Ａ１−２２の各々が備えるＣＰＵに実行させ、処理に要する時間を測定することによって行うことができる。このとき、個別処理の実行時のＣＰＵ使用率も同時に測定する。そして、処理資源推定要求時に、各演算装置におけるＣＰＵ使用率を取得する。そして、ＣＰＵ使用率が１００％であった場合の処理資源を求め、処理資源推定値とする。なぜなら、ＣＰＵ使用率が低い状態で測定された処理時間は、個別処理の実際の負荷を正確に表していないと考えられるためである。そのため、ＣＰＵ使用率が１００％であった場合に換算して、処理資源推定値とする。
【０１１０】
以上のような処理を付加し、ＣＰＵ使用率により、処理時間の推定値を補正する。
【０１１１】
具体的には、ある演算装置における個別処理の実行時のＣＰＵ使用率をα［％］とすると、この演算装置において必要と推定される処理時間は、
（保持する個別処理時間推定値）×α／１００
と推定することができる。推定されるのは、演算装置Ａ１−１に関する個別処理時間推定値、及び、演算装置Ａ１−２に関する個別処理時間推定値である。
【０１１２】
「個別通信時間」は、統合演算装置Ｃ１及び統合演算装置Ｃ２に含まれる通信資源推定部１１によって次のように推定される。本実施例では、処理資源推定に関する推定値のテーブルとして、例えば、通信速度が１Ｍｂｐｓの通信速度とした場合の処理時間を保持しておく。また、処理資源推定要求時に、各演算装置における通信速度を取得する。すなわち、処理の分担を決定する前に、あらかじめ個別処理ごとに定められたサイズのダミーデータを送信し、送信にかかった時間を求めることにより、その時点での通信速度を測定することができる。ここで得られた通信速度をβＭｂｐｓとすると、個別通信にかかる処理時間は、
（保持する個別通信時間推定値）／β
と推定することができる。推定されるのは、演算装置Ａ１−１に関する個別通信時間推定値（演算装置Ａ１−１から演算装置Ａ１−２へデータを通信するための個別通信時間）及び演算装置Ａ１−２に関する個別通信時間推定値（演算装置Ａ１−２から演算装置Ａ１−１へデータを通信するための個別通信時間）である。
【０１１３】
また、前述のように、個別処理のためのデータ量は、個別処理の内容により異なる可能性がある。さらに、個別処理のための入力情報のデータ量、又は個別処理の結果としての出力情報のデータ量も、必ずしも同じではない。従って、上記の個別通信時間推定値を、単位データ量の通信を行うときの推定値として取り扱い、その推定値に、実際に通信されるデータ量を乗算して通信時間を推定してもよい。
【０１１４】
処理分担パターンを定めるには、個別処理時間と個別通信時間の和を評価基準として用いる。すなわち、個別処理時間と個別通信時間の和を最小にするように、最適化手法を用いればよい。このときの最適化手法には、例えば、動的計画法を利用することができる。その際、分担を決定する直前の、各演算装置のＣＰＵ使用率を、各演算装置から取得し、それも考慮してもよい。すなわち、ＣＰＵ使用率が高いＣＰＵへの処理の分担は行わない、あるいは負荷の軽い個別処理を分担させる等の制御を行ってもよい。
【０１１５】
なお、個別通信時間を考慮するのは、例えば、ある個別処理をＡ１−１で実行し、これに続く個別処理をＡ１−２で行う場合、処理に必要なデータをＡ１−１からＡ１−２に転送する必要があるからである。続く２つの個別処理を同一の第３の実施形態の演算装置で実行する場合には、個別通信時間は０もしくはあらかじめ与えられた十分に小さい値を用いればよい。
【０１１６】
以上のように、本実施形態では、処理分担を決定する前に、処理資源や通信資源がどの程度使用可能かを推定する。そのため、演算装置が高負荷状態にあるときや通信が不安定な状態にあるときでも、その時点での状況に応じた最適な処理分担を定めることができるという効果がある。
（第５の実施形態）
全体処理が画像処理である場合は、画像の性質を利用して推定処理時間の補正を行うことができる。第５の実施形態では、全体処理が画像処理である場合の、具体的な処理資源の推定例と、それを利用した処理の分担の例を示す。例えば、個別処理の処理時間が、画像の面積に比例する場合は、単位面積あたりの個別処理資源の推定値、すなわち、推定処理時間をあらかじめテーブル形式で保持すればよい。処理資源推定要求時に取得できる画像の面積を、単位面積あたりの推定処理時間に乗じることにより、その画像に個別処理を施したときの推定処理時間を求めることができる。
【０１１７】
また、個別処理によって画像から特徴点の数を計算するときに、特徴点の数に比例した処理時間がかかる場合も、上記と同様の処理が可能である。すなわち、１個の特徴点を求めるための個別処理の推定処理時間をあらかじめ用意し、特徴点の個数をその推定処理時間に乗じることにより、その画像の特徴点に個別処理を施したときの推定処理時間を求めることができる。
【０１１８】
以上のように、一例として、画像面積や特徴点の数に、個別処理の処理時間が比例する場合を例にとって説明した。しかし、画像面積や特徴点の数といった画像に関する特徴量と処理時間との増減との対応関係が規定可能なものであれば、対応関係は比例関係に限らず、他の対応関係の場合にも適用可能である。
【０１１９】
また、最適化問題の解法は、第１の実施形態に記載したものをそのまま適用可能である。
【０１２０】
上記以外にも、各演算装置のメモリ容量を考慮し、メモリ量に関する制限つき最適化問題を解くことにより容易に求められる。例えば、ある個別処理のために、あらかじめ保持しておく必要があるメモリの容量が、演算装置のメモリ容量を超えることが想定される場合、その個別処理をその演算装置に行わせないという判断も可能である。
【０１２１】
また、個別処理時間、個別通信時間の代わりに、個別処理に要する消費電力、個別通信に要する消費電力を判断基準（パラメータ、生成情報）として採用してもよい。その場合は、全体として最も低い消費電力を達成するような処理分担パターンの生成が可能である。
【０１２２】
以上、上述した処理分担制御装置は、主にソフトウェアの形態で実現させることを例に説明してきたが、構成要素の一部もしくは全部をハードウェア化してもよい。
【０１２３】
なお、上記の各プログラムは、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、フラッシュメモリ等の半導体記憶装置、光ディスク、磁気ディスク、光磁気ディスク等、非一時的な媒体に格納されてもよい。
【０１２４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成部と、
を備えることを特徴とする処理分担制御装置。
（付記２）
前記第１の通信資源推定値及び前記第２の通信資源推定値は、前記個別処理の実行開始前及び完遂後の各々について求められる
を備えることを特徴とする付記１に記載の処理分担制御装置。
（付記３）
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値は、前記第１の演算装置及び前記第２の演算装置の各々が前記個別処理を実行したときの、全処理能力に対する、使用された処理能力の比である処理能力使用率とに基づいて求められる
を備えることを特徴とする付記１又は２に記載の処理分担制御装置。
（付記４）
前記個別処理は、前記全体処理の入力情報のうちの所定の分担量の処理であり、
前記第１の個別処理資源推定値及び前記第２の個別処理資源推定値は、前記分担量に基づいて求められる
ことを特徴とする付記１乃至３のいずれかに記載の処理分担制御装置。
（付記５）
前記第１の通信資源推定値及び前記第２の通信資源推定値は、前記分担量に対する前記個別処理の結果として出力される出力情報量に基づいて求められる
ことを特徴とする付記４に記載の処理分担制御装置。
（付記６）
前記分担を、前記第１の演算装置及び前記第２の演算装置に出力する処理分担パターン配信部
を備えることを特徴とする付記１乃至５のいずれかに記載の処理分担制御装置。
（付記７）
前記第１の個別処理資源推定値及び前記第２の個別処理資源推定値は、それぞれ前記第１の演算装置、前記第２の演算装置が前記個別処理を完遂するために割り当て可能なメモリ容量の推測値であり、
前記第１の通信資源推定値及び前記第２の通信資源推定値は、それぞれ前記第１の演算装置、前記第２の演算装置との間で通信を行うために割り当て可能なメモリ容量の推測値であり、
前記処理分担パターン生成部は、前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、メモリの割り当てが可能となるように前記処理分担パターンを生成する
ことを特徴とする付記１乃至６のいずれかに記載の処理分担制御装置。
（付記８）
前記第１の個別処理資源推定値及び前記第２の個別処理資源推定値は、それぞれ前記第１の演算装置、前記第２の演算装置が前記個別処理を完遂するために消費する電力の推測値であり、
前記第１の通信資源推定値及び前記第２の通信資源推定値は、それぞれ前記第１の演算装置、前記第２の演算装置との間で通信を行うために消費する電力の推測値であり、
前記処理分担パターン生成部は、前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記個別処理が完遂されるために消費される電力が最小となるように前記処理分担パターンを生成する
ことを特徴とする付記１乃至６のいずれかに記載の処理分担制御装置。
（付記９）
演算部と、
前記演算部が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び外部の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部と、
前記演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記演算装置との間に必要な通信資源である通信資源推定値を保持する通信資源推定部と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、及び前記通信資源推定値に基づいて、前記演算部及び前記演算装置への前記個別処理の分担を決定する処理分担パターン生成部と、
含む処理分担制御装置と、
を備えることを特徴とする演算装置。
（付記１０）
第１の演算装置と、
第２の演算装置と、
前記第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び前記第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定部、前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定部、並びに前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成部を含む処理分担制御装置と、
を備えることを特徴とする演算システム。
（付記１１）
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源値を推定して第１の個別処理資源推定値を求め、
第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値を推定して第２の個別処理資源推定値を求め、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて前記第１の演算装置との間に必要な通信資源を推定して、第１の通信資源推定値を求め、
前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて前記第２の演算装置との間に必要な通信資源を推定して、第２の通信資源推定値を求め、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する
ことを特徴とする処理分担制御方法。
（付記１２）
処理分担制御装置が備えるコンピュータを、
第１の演算装置が全体処理に含まれる個別処理を完遂するために必要な処理資源の推定値である第１の個別処理資源推定値、及び第２の演算装置が前記個別処理を完遂するために必要な処理資源の推定値である第２の個別処理資源推定値を保持する処理資源推定手段と、
前記第１の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第１の演算装置との間に必要な通信資源である第１の通信資源推定値、及び前記第２の演算装置との間の過去の通信に用いられた通信資源に基づいて推定された、前記第２の演算装置との間に必要な通信資源である第２の通信資源推定値を保持する通信資源推定手段と、
前記第１の個別処理資源推定値、前記第２の個別処理資源推定値、前記第１の通信資源推定値及び前記第２の通信資源推定値に基づいて、前記第１の演算装置及び前記第２の演算装置への前記個別処理の分担を決定する処理分担パターン生成手段
として機能させることを特徴とする処理分担制御プログラム。
【産業上の利用可能性】
【０１２５】
本発明の活用例として、クライアント−サーバ間における連携処理の最適化がある。すなわち、クライアントとサーバの全体を１つの演算装置とみなし、その演算装置に所定の処理を実行させる。そのとき、その演算装置が全体として行う処理（全体処理）は、部分的な処理（個別処理）に分割できる処理であれば、処理の内容は任意である。例えば、全体処理は入力された画像の照合を行う処理で、個別処理はその画像の一部の照合を行う処理であってもよい。
【符号の説明】
【０１２６】
１、Ｂ１、Ｂ１−１、Ｂ１−２    処理分担制御装置
２、・・・、Ｎ、Ａ１、Ａ１−１、Ａ１−２    演算装置
１１    処理資源推定部
１２    通信資源推定部
１３、Ｂ１３１    処理分担パターン生成部
Ａ１１    個別装置用処理分担パターン入力部
Ａ１２    個別処理実行部
Ｂ１３    処理分担パターン管理部
Ｂ１３２    処理分担パターン配信部
Ｃ１、Ｃ２    統合演算装置
５    ＣＰＵ
６    メモリ
７    通信手段
【図１】
2013196174.tif 000003
【図２】
2013196174.tif 000004
【図３】
2013196174.tif 000005
【図４】
2013196174.tif 000006
【図５】
2013196174.tif 000007
【図６】
2013196174.tif 000008
【図７】
2013196174.tif 000009
【図８】
2013196174.tif 000010
【図９】
2013196174.tif 000011
【図１０】
2013196174.tif 000012
【図１１】
2013196174.tif 000013
【図１２】
2013196174.tif 000014
【図１３】
2013196174.tif 000015
【図１４】
2013196174.tif 000016
【図１５】
2013196174.tif 000017