(57)【要約】  管理装置は、複数のデータ装置を示す複数の第１頂点と、複数の処理装置を示す複数の第２頂点と、各データ装置から各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、各第１頂点から各第２頂点に至る複数の第１辺と、各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、各第２頂点から、各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成するモデル生成部と、このモデル情報に基づいて、処理装置と処理装置により処理されるデータを格納するデータ装置との複数組み合わせを決定する決定部と、を有する。
2013145512.tif 000002
【特許請求の範囲】
【請求項１】
データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成するモデル生成部と、
前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決め、該各辺の流量を満たす該概念モデル上の各経路を選択し、選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する決定部と、
を備える管理装置。
【請求項２】
データの識別子と該データを格納する前記データ装置の識別子とを対応付けて格納するデータ所在格納部と、
ジョブにより扱われる複数のデータに関する情報を格納するジョブ情報格納部と、
を更に備え、
前記モデル生成部は、前記ジョブ情報格納部に格納される情報に基づいて、前記ジョブを示す頂点と、該ジョブを示す頂点から該ジョブにより扱われる複数データを格納する複数のデータ装置を示す複数の頂点へそれぞれ至る複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記決定部は、前記選択された各経路に含まれる各頂点に応じて、前記ジョブと、前記ジョブにより扱われる少なくとも１つのデータを格納する前記データ装置と、該少なくとも１つのデータを処理する前記処理装置との複数組み合わせを決定し、該複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
請求項１に記載の管理装置。
【請求項３】
複数の複製データに多重化された元データの識別子と、該各複製データを格納する各データ装置の識別子とを対応付けて格納するデータ所在格納部を更に備え、
前記モデル生成部は、前記元データを示す頂点と、前記元データを示す頂点から前記各複製データを格納する各データ装置を示す第１頂点へそれぞれ至る複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記決定部は、前記選択された各経路に含まれる各頂点に応じて、前記元データと、前記複数の複製データの少なくとも１つのデータを格納する前記データ装置と、前記複数の複製データの少なくとも１つを処理する前記処理装置との複数組み合わせを決定し、該複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
請求項１又は２に記載の管理装置。
【請求項４】
前記決定部は、前記選択された各経路に関する前記単位時間当たりのデータ処理量を、該各経路に対応する前記各対応関係にそれぞれ更に含ませ、データの識別子が共通する前記対応関係が複数生成された場合に、該複数の対応関係で示される各処理装置に、該共通の識別子が示す前記元データの、該対応関係に含まれる前記単位時間当たりのデータ処理量に応じた割合のデータ量を対象にしてそれぞれ処理させることを決定する、
請求項３に記載の管理装置。
【請求項５】
前記モデル生成部は、複数のデータをそれぞれ扱う各ジョブのための各始点頂点と、該各ジョブのための各終点頂点と、該各始点頂点から該各ジョブを示す頂点にそれぞれ至る複数の辺と、前記処理装置を示す前記第２頂点から該各終点頂点にそれぞれ至る複数の辺であって、前記処理量制約条件の上限値が前記処理装置が該各ジョブに対してそれぞれ実行可能な単位時間当たりの処理量にそれぞれ設定される複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
請求項１から４のいずれか１項に記載の管理装置。
【請求項６】
前記モデル生成部は、
前記データ装置に格納されているデータが前記処理装置で受信されるまでに経由する中間機器を示す頂点を更に含むと共に、前記データ装置を示す前記第１頂点から前記データ装置の最寄りの中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が前記データ装置から該最寄りの中間機器への単位時間当たりの転送可能量に設定される辺、該中間機器を示す頂点から他の該中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が該中間機器から他の該中間機器への単位時間当たりの転送可能量に設定される辺、及び、前記処理装置の最寄りの中間機器を示す頂点から前記処理装置を示す前記第２頂点へ至る辺であって、前記転送量制約条件の上限値が該最寄りの中間機器から前記処理装置への単位時間当たりの転送可能量に設定される辺の少なくとも１つを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
請求項１から５のいずれか１項に記載の管理装置。
【請求項７】
前記モデル生成部は、前記中間機器を示す頂点を、前記中間機器への１以上の入力部を示す１以上の頂点と、前記中間機器の１以上の出力部を示す１以上の頂点と、データが転送され得る該入力部と該出力部との間を結ぶ１以上の辺とで構成する、
請求項６に記載の管理装置。
【請求項８】
前記各処理装置について、単位処理量当たりに費やされる処理負荷及び残負荷をそれぞれ格納するサーバ状態格納部を更に備え、
前記決定部は、前記概念モデルの各辺に設定された前記転送量制約条件及び前記処理量制約条件、並びに、前記各処理装置に関する前記処理負荷及び前記残負荷に応じた流量制限に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決める、
請求項１から７のいずれか１項に記載の管理装置。
【請求項９】
少なくとも１つのコンピュータが、
データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成し、
前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決定し、
前記各辺の流量を満たす前記概念モデル上の各経路を選択し、
前記選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する、
ことを含む分散処理管理方法。
【請求項１０】
少なくとも１つのコンピュータに、
データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成するモデル生成部と、
前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決め、該各辺の流量を満たす該概念モデル上の各経路を選択し、選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する決定部と、
を実現させる管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを格納するデータ装置とそのデータを処理する処理装置とが分散配置されてなる分散システムにおけるデータの分散処理の管理技術に関する。
【背景技術】
【０００２】
下記特許文献１には、複数の計算機に格納されたデータを処理させる計算サーバを決定する分散システムであって、個々のデータを格納する計算機から最も近傍な利用可能計算サーバを逐次決定することによって、全てのデータの通信経路を決定する分散システムが提案されている。下記特許文献２には、複数のファイル転送要求が同時にあっても蓄積側においてファイルを入出力する速度が低下しない技術が提案されている。下記特許文献３には、複数のディスクに格納されたファイル群を一括で管理できるアドレス空間を提供する分散ファイルシステムが提案されている。【０００３】
下記特許文献４には、分散データベ−スシステムにおけるネットワ−クの負荷を軽減するために、データベースのデータをクライアントに転送する際に、データ転送時間を考慮して、或る計算機に配置されていた中継サーバを他の計算機に移動させることが提案されている。下記特許文献５には、ファイルが転送される各転送経路の回線速度と負荷状況に応じて、ファイルを分割し、その分割されたファイルを転送する方法が提案されている。下記特許文献６には、様々な速度が指定されるストリーム入出力要求に対して、使用効率の良い資源の割り当てを短時間で決定するストリーム処理装置が提案されている。下記特許文献７には、Ｉ／Ｏノードを使用して計算ノードがファイルシステムへアクセスするコンピュータシステムにおいて、ジョブ毎に、当該ジョブの実行を停止させることなく、Ｉ／Ｏノードを動的に割り当てることで、Ｉ／Ｏ資源を効率的に利用する手法が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第７６５０３３１号明細書
【特許文献２】特開２００８−１１７０９１号公報
【特許文献３】特開２０１０−１４０５０７号公報
【特許文献４】特開平８−２０２７２６号公報
【特許文献５】特許第３３９０４０６号公報
【特許文献６】特開平８−１４７２３４号公報
【特許文献７】特許第４５６９８４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の各技術では、分散処理システムにおけるデータ転送時間の低減のみにフォーカスが当てられているため、システム全体での処理時間が必ずしも低減されるとは言い難い。なお、上述の特許文献３及び７では、複数のデータサーバに格納されたデータを一元的に扱う方法やファイルシステムにアクセスするために必要なＩ／Ｏノードの占有率を決定する方法が提案されているに過ぎない。【０００６】
本発明は、上述のような事情に鑑みてなされたものであり、データを格納するデータ装置とそのデータを処理する処理装置とが分散配置されてなる分散システムにおけるシステム全体でのデータ処理時間を低減させる技術を提供する。
【課題を解決するための手段】
【０００７】
本発明の各態様では、上述した課題を解決するために、それぞれ以下の構成を採用する。【０００８】
第１の態様は、管理装置に関する。第１態様に係る管理装置は、データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成するモデル生成部と、前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決め、該各辺の流量を満たす該概念モデル上の各経路を選択し、選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する決定部と、を備える。【０００９】
第２の態様は、分散処理管理方法に関する。第２態様に係る分散処理管理方法は、少なくとも１つのコンピュータが、データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成し、前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決定し、前記各辺の流量を満たす前記概念モデル上の各経路を選択し、前記選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する、ことを含む。【００１０】
なお、本発明の他の態様としては、上記第１態様における各構成を少なくとも１つのコンピュータに実現させる管理プログラムであってもよいし、このようなプログラムを格納するコンピュータが読み取り可能な記録媒体であってもよい。この記録媒体は、非一時的な有形の媒体を含む。
【発明の効果】
【００１１】
上記各態様によれば、データを格納するデータ装置とそのデータを処理する処理装置とが分散配置されてなる分散システムにおけるシステム全体でのデータ処理時間を低減させる技術を提供することができる。
【図面の簡単な説明】
【００１２】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００１３】
【図１Ａ】第１実施形態における分散システムの構成例を概念的に示す図である。
【図１Ｂ】分散システムの各構成例を概念的に示す図である。
【図２Ａ】分散システムの各構成例を概念的に示す図である。
【図２Ｂ】分散システムの各構成例を概念的に示す図である。
【図３】コンピュータ間の単位時間当たりの転送可能量を示す図である。
【図４】コンピュータの単位時間当たりの処理可能量を示す図である。
【図５】第１実施形態における分散システムの各装置の処理構成例を概念的に示す図である。
【図６】データ所在格納部に格納される情報の例を示す図である。
【図７】入出力通信路情報格納部に格納される情報の例を示す図である。
【図８】サーバ状態格納部に格納される情報の例を示す図である。
【図９Ａ】モデル情報の例を示す図である。
【図９Ｂ】モデル情報により構築される概念モデルの例を示す図である。
【図１０】データフロー情報の例を示す図である。
【図１１】決定情報の例を示す図である。
【図１２】分散システムの動作例の全体概要を示すフローチャートである。
【図１３】工程（Ｓ４０１）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１４】工程（Ｓ４０４）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１５】工程（Ｓ４０４−１０）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１６】工程（Ｓ４０４−２０）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１７】工程（Ｓ４０５）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１８】工程（Ｓ４０６）における第１実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図１９】第２実施形態における分散システムの各装置の処理構成例を概念的に示す図である。
【図２０】ジョブ情報格納部に格納される情報の例を示す図である。
【図２１】工程（Ｓ４０１）における第２実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２２】工程（Ｓ４０４）における第２実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２３】工程（Ｓ４０４−３０）における第２実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２４】第２実施形態の第１変形例におけるサーバ状態格納部が格納する情報の例を示す図である。
【図２５】図２２に示される工程（Ｓ４０４−２０）に関する、第２実施形態の第１変形例におけるマスタサーバの詳細動作を示すフローチャートである。
【図２６】工程（Ｓ４０４）における第３実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２７】工程（Ｓ４０４−４０）における第３実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２８】工程（Ｓ４０６）における第３実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図２９】第４実施形態における分散システムの各装置の処理構成例を概念的に示す図である。
【図３０】工程（Ｓ４０４）における第４実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図３１Ａ】工程（Ｓ４０４−１２−１０）における第４実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図３１Ｂ】工程（Ｓ４０４−１２−１０）における第４実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図３１Ｃ】工程（Ｓ４０４−１２−１０）における第４実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図３２】工程（Ｓ４０４−２０）（図２２参照）における第５実施形態のマスタサーバの詳細動作を示すフローチャートである。
【図３３】第６実施形態におけるサーバ状態格納部が格納する情報の例を示す図である。
【図３４】実施例１における分散システムの構成例を概念的に示す図である。
【図３５】実施例１におけるサーバ状態格納部に格納される情報を示す図である。
【図３６】実施例１における入出力通信路情報格納部に格納される情報を示す図である。
【図３７】実施例１におけるデータ所在格納部に格納される情報を示す図である。
【図３８】実施例１において生成されたモデル情報を示す図である。
【図３９】図３８により示されるモデル情報により構築される概念モデルを示す図である。
【図４０Ａ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｂ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｃ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｄ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｅ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｆ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４０Ｇ】実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４１】実施例１におけるデータフロー情報を示す図である。
【図４２】実施例１において実施されるデータ送受信を概念的に示す図である。
【図４３】実施例２におけるジョブ情報格納部に格納される情報を示す図である。
【図４４】実施例２におけるサーバ状態格納部に格納される情報を示す図である。
【図４５】実施例２におけるデータ所在格納部に格納される情報を示す図である。
【図４６】実施例２において生成されるモデル情報を示す図である。
【図４７】図４６に示されるモデル情報により構築される概念モデルを示す図である。
【図４８Ａ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４８Ｂ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４８Ｃ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４８Ｄ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４８Ｅ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４８Ｆ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ａ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｂ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｃ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｄ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｅ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｆ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｇ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｈ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｉ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図４９Ｊ】実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５０】実施例２において生成されたデータフロー情報を示す図である。
【図５１】実施例２において実施されるデータ送受信を概念的に示す図である。
【図５２】実施例３におけるデータ所在格納部に格納される情報を示す図である。
【図５３】第３実施例において生成されるモデル情報を示す図である。
【図５４】図５３により示されるモデル情報から構築される概念モデルを示す図である。
【図５５Ａ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｂ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｃ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｄ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｅ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｆ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５５Ｇ】第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図５６】実施例３におけるデータフロー情報を示す図である。
【図５７】実施例３において実施されるデータ送受信を概念的に示す図である。
【図５８】実施例４における分散システムの構成を概念的に示す図である。
【図５９】実施例４におけるサーバ状態格納部に格納される情報を示す図である。
【図６０】実施例４における入出力通信路情報格納部に格納される情報を示す図である。
【図６１】実施例４において生成されるモデル情報を示す図である。
【図６２】図６１により示されるモデル情報から構築される概念モデルを示す図である。
【図６３Ａ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｂ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｃ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｄ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｅ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｆ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６３Ｇ】実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６４】実施例４におけるデータフロー情報を示す図である。
【図６５】実施例４において実施されるデータ送受信を概念的に示す図である。
【図６６】実施例５におけるジョブ情報格納部に格納される情報を示す図である。
【図６７】実施例５において生成されるモデル情報を示す図である。
【図６８】図６７により示されるモデル情報から構築される概念モデルを示す図である。
【図６９Ａ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｂ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｃ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｄ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｅ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｆ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図６９Ｇ】実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７０】実施例５におけるデータフロー情報を示す図である。
【図７１】実施例５において実施されるデータ送受信を概念的に示す図である。
【図７２】実施例６におけるサーバ状態格納部に格納される情報を示す図である。
【図７３】実施例６において生成されるモデル情報を示す図である。
【図７４】図７３により示されるモデル情報から構築される概念モデルを示す図である。
【図７５Ａ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｂ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｃ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｄ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｅ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｆ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｇ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｈ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７５Ｉ】実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。
【図７６】実施例６におけるデータフロー情報を示す図である。
【図７７】実施例６において実施されるデータ送受信を概念的に示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について説明する。以下の各実施形態では、複数のデータサーバに格納されたデータを複数の処理サーバで並列に処理を行う分散システムが例示されるが、本発明は、その他、分散処理を行うデータベースシステムやバッチ処理システムにも適用可能である。以下に挙げる各実施形態は例示であり、本発明は以下の各実施形態の構成に限定されない。
【００１５】
［第１実施形態］
図１Ａは、第１実施形態における分散システムの構成例を概念的に示す図である。以下、図１Ａを参照しながら、第１実施形態における分散システム３５０の構成概要及び動作概要、並びに、第１実施形態と関連技術との相違点について説明する。
【００１６】
分散システム３５０は、相互にネットワーク３７０によって接続される、マスタサーバ３００、ネットワークスイッチ３２０、複数の処理サーバ３３０＃１から３３０♯ｎ、複数のデータサーバ３４０＃１から３４０♯ｎなどを含む。なお、分散システム３５０は、クライアント３６０、他のサーバ３９９等を含んでもよい。以降、データサーバ３４０♯１から３４０♯ｎは総称してデータサーバ３４０と表記される場合もあり、処理サーバ３３０♯１から３３０♯ｎは総称して処理サーバ３３０と表記される場合もある。
【００１７】
データサーバ３４０は、処理サーバ３３０による処理対象となり得るデータを格納する。処理サーバ３３０は、データサーバ３４０からそのデータを受信して、受信したデータに対して処理プログラムを実行することにより当該データを処理する。
【００１８】
クライアント３６０は、データ処理開始をマスタサーバ３００に要求するための情報である要求情報を送信する。要求情報は、処理プログラムとその処理プログラムが使用するデータを示す情報を含む。
【００１９】
マスタサーバ３００は、データサーバ３４０が格納するデータのうちの一以上のデータを処理する処理サーバ３３０をデータ毎に決定する。マスタサーバ３００は、決定された各処理サーバ３３０について、処理対象のデータとそのデータを記憶しているデータサーバ３４０とを示す情報及び単位時間当たりのデータ処理量を示す情報を含む決定情報をそれぞれ生成する。データサーバ３４０及び処理サーバ３３０は、当該決定情報に基づいてデータの送受信を行い、処理サーバ３３０は受信されたデータを処理する。
【００２０】
ここで、マスタサーバ３００、処理サーバ３３０、データサーバ３４０、クライアント３６０は、それぞれ個別に、専用の装置で実現されてもよいし、汎用のコンピュータで実現されてもよい。また、一台の専用装置又は一台のコンピュータにより、マスタサーバ３００、処理サーバ３３０、データサーバ３４０、クライアント３６０のうちの複数が実現されてもよい。以下、ハードウェアとしての一台の専用装置又は一台のコンピュータは総称して一台のコンピュータ装置と表記される。多くの場合、処理サーバ３３０及びデータサーバ３４０が当該一台のコンピュータ装置により実現される。
【００２１】
当該一台のコンピュータ装置は、例えば、バスで相互に接続される、ＣＰＵ（Central Processing Unit）、メモリ、入出力インタフェース（Ｉ／Ｆ）等を有する。メモリは、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク、可搬型記憶媒体等である。入出力Ｉ／Ｆは、ネットワーク３７０を介して他の装置と通信を行う通信装置等と接続される。入出力Ｉ／Ｆは、表示装置や入力装置等のようなユーザインタフェース装置と接続されてもよい。なお、本実施形態は、マスタサーバ３００、処理サーバ３３０、データサーバ３４０、クライアント３６０のハードウェア構成を限定しない。
【００２２】
図１Ｂ、図２Ａ及び図２Ｂは、分散システム３５０の各構成例を概念的に示す図である。これらの図では、処理サーバ３３０及びデータサーバ３４０は、コンピュータと表記されており、ネットワーク３７０は、スイッチを経由するデータ送受信経路として表記されている。なお、マスタサーバ３００は図示されていない。なお、スイッチとは、ハブ、ルータ等のようなネットワーク機器である。
【００２３】
図１Ｂにおいて、分散システム３５０は、例えば、複数のコンピュータ１１１及び１１２と、それらを相互に接続するスイッチ１０１から１０３を含む。図１Ｂの例では、複数のコンピュータ１１１及びスイッチ１０２はラック１２１に収容され、複数のコンピュータ１１２及びスイッチ１０３はラック１２２に収容されている。更に、ラック１２１及び１２２はデータセンタ１３１に収容されており、データセンタ１３１及び１３２の間は、拠点間通信網１４１にて接続されている。このように、図１Ｂは、スイッチとコンピュータをスター型に接続した分散システム３５０を例示する。
【００２４】
一方、図２Ａ及び図２Ｂは、カスケード接続されたスイッチにより構成された分散システム３５０を例示する。図２Ａ及び図２Ｂは、それぞれ、データサーバ３４０と処理サーバ３３０との間のデータ送受信の一例を示す。この例によれば、コンピュータ２０７から２１０がデータサーバ３４０として機能し、コンピュータ２０７及び２０９が処理サーバ３３０としても機能する。ここでは、例えば、コンピュータ２１０がマスタサーバ３００として機能する。
【００２５】
図２Ａ及び図２Ｂにおいて、スイッチ２０１及び２０２で接続されたコンピュータのうち、コンピュータ２０７及び２０９以外のコンピュータは、他の処理を実行中であることから、更なるデータ処理のために利用され得ない。利用不可能なコンピュータ２０８は、処理対象のデータ２１１及び２１２を記憶用ディスク２０４に記憶している。同様に、利用不可能なコンピュータ２１０は、処理対象のデータ２１３を記憶用ディスク２０６に記憶している。一方、利用可能なコンピュータ２０７は、処理プロセス２１４を実行しており、利用可能なコンピュータ２０９は、処理プロセス２１５を実行している。
【００２６】
図３は、コンピュータ間の単位時間当たりの転送可能量を示す図である。図３に示される表２２０によれば、上述のような処理対象のデータを他のコンピュータに転送する際の単位時間当たりの転送量が示されている。この例において、各処理プロセスは、割り当てられたデータに対して必要な処理を並列に実行可能であるとする。
【００２７】
図３の表２２０は具体的には次の内容を示す。コンピュータ２０８から処理対象のデータをコンピュータ２０７に転送する場合の、単位時間当たりの転送可能量は５０メガバイト毎秒（ＭＢ／ｓ）である。コンピュータ２０８とコンピュータ２０９とに関する当該転送可能量は５０ＭＢ／ｓであり、コンピュータ２１０とコンピュータ２０７とに関する当該転送可能量は５０ＭＢ／ｓであり、コンピュータ２１０とコンピュータ２０９とに関する当該転送可能量は１００ＭＢ／ｓである。
【００２８】
図４は、コンピュータの単位時間当たりの処理可能量を示す図である。図４に示される表２２１によれば、コンピュータ２０７が処理対象のデータを処理するための単位時間当たりの処理可能量は５０ＭＢ／ｓであり、コンピュータ２０９に関する当該処理可能量は１５０ＭＢ／ｓである。
【００２９】
ここで、データ処理のスループットは、処理対象のデータを転送する経路の単位時間当たりの転送可能量と、処理を行うコンピュータの単位時間当たりの処理可能量との間のどちらか小さい値となる。図２Ａでは、処理対象のデータ２１１は、データ転送経路２１６を介して伝送されて、利用可能なコンピュータ２０７で処理され、処理対象のデータ２１３は、データ転送経路２１７を介して伝送されて、利用可能なコンピュータ２０９で処理される。なお、処理対象のデータ２１２は、いずれの処理プロセスにも割り当てられず、待機状態となる。
【００３０】
一方、図２Ｂでは、処理対象のデータ２１１は、データ転送経路２３０を介して伝送されて、利用可能なコンピュータ２０７で処理され、処理対象のデータ２１２は、データ転送経路２３１を介して伝送されて、利用可能なコンピュータ２０９で処理され、処理対象のデータ２１３は、データ転送経路２３２を介して伝送されて、利用可能なコンピュータ２０９で処理される。
【００３１】
図２Ａにおけるデータ処理の総スループットは、処理対象のデータ２１１に関するスループット（５０ＭＢ／ｓ）と、処理対象のデータ２１３に関するスループット（１００ＭＢ／ｓ）との和となり、１５０ＭＢ／ｓである。処理対象のデータ２１１に関するスループット（５０ＭＢ／ｓ）は、データ転送経路２１６の当該転送可能量５０ＭＢ／ｓとコンピュータ２０７の当該処理可能量５０ＭＢ／ｓとの間の小さいほうの値である。処理対象のデータ２１３に関するスループット（１００ＭＢ／ｓ）は、データ転送経路２１７の当該転送可能量１００ＭＢ／ｓとコンピュータ２０９の当該処理可能量１５０ＭＢ／ｓの小さいほうの値である。
【００３２】
図２Ｂにおけるデータ処理の総スループットは、処理対象のデータ２１１に関するスループット（５０ＭＢ／ｓ）と、処理対象のデータ２１２に関するスループット（５０ＭＢ／ｓ）と、処理対象のデータ２１３に関するスループット（１００ＭＢ／ｓ）との和となり、２００ＭＢ／ｓである。処理対象のデータ２１１に関するスループット（５０ＭＢ／ｓ）は、データ転送経路２３０の当該転送可能量５０ＭＢ／ｓとコンピュータ２０７の当該処理可能量５０ＭＢ／ｓとの間の小さいほうの値である。処理対象のデータ２１２に関するスループット（５０ＭＢ／ｓ）は、データ転送経路２３１の当該転送可能量５０ＭＢ／ｓとコンピュータ２０９の当該処理可能量１５０ＭＢ／ｓとの間の小さいほうの値である。処理対象のデータ２１３に関するスループット（１００ＭＢ／ｓ）は、データ転送経路２３２の当該転送可能量１００ＭＢ／ｓとコンピュータ２０９の当該処理可能量１５０ＭＢ／ｓとの間の小さいほうの値である。
【００３３】
以上より、図２Ｂにおけるデータ処理は、図２Ａにおけるデータ処理に比べて総スループットが大きく、効率的である。
【００３４】
ところで、上述のような第１実施形態に関連する技術として、ネットワーク構成に基づく距離（例えば、ホップ数等）に基づいて、各処理対象のデータを逐次的に処理サーバに割り当てる分散システムが存在する。このような分散システムでは、図２Ａに示されるような非効率なデータ割り当てが行われる場合がある。このような関連技術では、コンピュータ間の転送可能量や、処理を実行するコンピュータの処理可能量を考慮することなく、ネットワーク構成に基づく距離のみで当該割り当てが行われるからである。
【００３５】
第１実施形態における分散システム３５０は、図２Ａ及び図２Ｂに例示した状況において、図２Ｂに示されるような効率的なデータ割り当てを行う。以下、第１実施形態における分散システム３５０について更に詳細を説明する。
【００３６】
〔第１実施形態における処理構成例〕
図５は、第１実施形態における分散システム３５０の各装置の処理構成例を概念的に示す図である。これら各処理部は、個々に又は複数組み合わせられて、ハードウェア構成要素として実現されてもよいし、ソフトウェア構成要素として実現されてもよいし、ハードウェア構成要素及びソフトウェア構成要素の組み合わせにより実現されてもよい。ハードウェア構成要素とは、例えば、フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、ゲートアレイ、論理ゲートの組み合わせ、信号処理回路、アナログ回路等のようなハードウェア回路である。ソフトウェア構成要素とは、１又は複数のメモリ上のデータ（プログラム）が１又は複数のプロセッサ（例えば、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）等）で実行されることにより実現される、タスク、プロセス、関数のようなソフトウェア部品（断片）である。なお、当該一台のコンピュータ装置が、マスタサーバ３００、処理サーバ３３０、データサーバ３４０の中の複数ノードを実現する場合には、実現される複数ノードの各処理構成を実現し、データ送受信部のように重複する処理構成を共用するようにしてもよい。
【００３７】
＜処理サーバ３３０＞
処理サーバ３３０は、処理サーバ管理部３３１、処理実行部３３２、処理プログラム格納部３３３、データ送受信部３３４等を有する。
【００３８】
＝＝＝処理サーバ管理部３３１＝＝＝
処理サーバ管理部３３１は、マスタサーバ３００からの処理割り当てに従って、処理実行部３３２に処理を実行させ、更に、現在実行中の処理の状態を管理する。具体的には、処理サーバ管理部３３１は、マスタサーバ３００から、データの識別子、そのデータが格納されているデータサーバ３４０の処理データ格納部３４２の識別子等を含む決定情報を受信する。処理サーバ管理部３３１は、受信された決定情報を処理実行部３３２に渡す。決定情報は、処理実行部３３２ごとに生成されても良い。また、決定情報には、処理実行部３３２を示す識別子が含まれており、処理サーバ管理部３３１は、決定情報に含まれる識別子で識別される処理実行部３３２に当該決定情報を渡しても良い。
【００３９】
処理サーバ管理部３３１は、処理実行部３３２がデータを処理する際に用いる処理プログラムの実行状態に関する情報を保持する。処理サーバ管理部３３１は、この処理プログラムの実行状態に関する情報を、当該処理プログラムの実行状態の変化に応じて更新する。処理プログラムの実行状態には、例えば、実行前状態、実行中状態、実行完了状態等がある。実行前状態とは、データを処理実行部３３２に割り当てる処理は終了したが、当該処理実行部３３２が、そのデータの処理を未だ実行していない状態を示す。実行中状態とは、処理実行部３３２がそのデータを実行している状態を示す。実行完了状態とは、処理実行部３３２がそのデータの処理を完了した状態を示す。処理プログラムの実行状態として、処理実行部３３２に割り当てられたデータの総量に対する、その処理実行部３３２による処理済みのデータ量の割合に基づいて定められる状態が利用されてもよい。
【００４０】
＝＝＝処理実行部３３２＝＝＝
処理実行部３３２は、処理サーバ管理部３３１の指示に従って、データ送受信部３３４を介してデータサーバ３４０から処理対象のデータを受信し、処理対象のデータに対し処理を実行する。具体的には、処理実行部３３２は、処理サーバ管理部３３１から、データの識別子とそのデータが格納されているデータサーバ３４０の処理データ格納部３４２の識別子とを受け取る。処理実行部３３２は、受け取った処理データ格納部３４２の識別子に対応するデータサーバ３４０に対し、当該データ識別子が示すデータの送信を要求する。処理実行部３３２は、当該データサーバ３４０から、その要求に応じて送信されるデータを受信し、そのデータに対し処理を実行する。処理実行部３３２は、複数の処理を並列に実行するために、処理サーバ３３０内に複数存在しても良い。
【００４１】
＝＝＝処理プログラム格納部３３３＝＝＝
処理プログラム格納部３３３は、他のサーバ３９９又はクライアント３６０から処理プログラムを受信し、その処理プログラムを格納する。
【００４２】
＝＝＝データ送受信部３３４＝＝＝
データ送受信部３３４は、他の処理サーバ３３０やデータサーバ３４０とデータの送受信を行う。
【００４３】
このように、処理サーバ３３０は、処理対象のデータを、マスタサーバ３００から指定されたデータサーバ３４０から、データサーバ３４０のデータ送受信部３４３、ネットワークスイッチ３２０のデータ送受信部３２２、及び、処理サーバ３３０のデータ送受信部３３４を介して受信する。処理サーバ３３０の処理実行部３３２は、受信された処理対象のデータを処理する。処理サーバ３３０がデータサーバ３４０と同一のコンピュータ装置で実現されている場合、処理サーバ３３０は、処理対象のデータを、処理データ格納部３４２から直接取得してもよい。また、データサーバ３４０のデータ送受信部３４３と処理サーバ３３０のデータ送受信部３３４とが、ネットワークスイッチ３２０のデータ送受信部３２２を介さず、直接通信してもよい。
【００４４】
＜データサーバ３４０＞
データサーバ３４０は、データサーバ管理部３４１、処理データ格納部３４２、データ送受信部３４３等を有する。
【００４５】
＝＝＝データサーバ管理部３４１＝＝＝
データサーバ管理部３４１は、マスタサーバ３００に対して、処理データ格納部３４２が格納するデータの所在情報を送信する。処理データ格納部３４２は、分散システム３５０において一意に識別されるデータを格納する。
【００４６】
＝＝＝処理データ格納部３４２＝＝＝
処理データ格納部３４２は、処理サーバ３３０に処理されるデータを、各データの識別子と共に格納する。処理データ格納部３４２は、ハード・ディスク・ドライブ（Hard Disc Drive; HDD）やソリッド・ステート・ドライブ（Solid State Drive; SSD）、ＵＳＢメモリ（Universal Serial Bus flash drive）、ＲＡＭ（Random Access Memory）ディスクなどのような記憶媒体上に実現される。処理データ格納部３４２に格納されるデータは、処理サーバ３３０が出力したもの又は出力中のものであっても良い。また、処理データ格納部３４２に格納されるデータは、処理データ格納部３４２が他のサーバ等から受信したものでも、処理データ格納部３４２が可搬型記憶媒体等から読み込んだものでも良い。
【００４７】
＝＝＝データ送受信部３４３＝＝＝
データ送受信部３４３は、他の処理サーバ３３０や他のデータサーバ３４０とデータの送受信を行う。
【００４８】
＜ネットワークスイッチ３２０＞
ネットワークスイッチ３２０は、データ送受信部３２２を有する。
データ送受信部３２２は、処理サーバ３３０及びデータサーバ３４０の間で送受信されるデータを中継する。
【００４９】
＜マスタサーバ３００＞
マスタサーバ３００は、データ所在格納部３０７０、サーバ状態格納部３０６０、入出力通信路情報格納部３０８０、モデル生成部３０１、決定部３０３等を有する。
【００５０】
＝＝＝データ所在格納部３０７０＝＝＝
データ所在格納部３０７０は、データの識別子と、そのデータを格納している格納装置（データサーバ３４０又はその処理データ格納部３４２）の識別子とを対応付けた状態で格納する。
【００５１】
データは、ディレクトリやデータの構造を規定する構造プログラムにおいて、識別名によって明示的に指定されても、指定された処理プログラムの出力結果等、他の処理結果に基づいて指定されても良い。構造プログラムは、処理プログラムが処理の対象とするデータを規定する情報である。構造プログラムは、あるデータを示す情報（名称や識別子）を入力として受け取り、その入力に対応するデータが格納されているディレクトリ名及び当該データを構成するファイルを示すファイル名を出力する。構造プログラムは、ディレクトリ名又はファイル名の一覧表などであっても良い。
【００５２】
処理プログラムが引数として受け取る情報の単位が、分散ファイルシステム（Distributed File System）における個々の分散ファイルである場合、当該データは各分散ファイルとなる。処理プログラムが引数として受け取る情報の単位が、行又はレコードである場合、当該データは、分散ファイル中の複数の行又は複数のレコードとなる。処理プログラムが引数として受け取る情報の単位が、リレーショナルデータベースにおけるテーブルの「行」である場合、当該データは、或るテーブルの集合から所定の検索によって得られる行の集合、又は、当該或るテーブルの集合から或る属性の範囲検索によって得られた行の集合等になる。当該データが、Ｃ＋＋やＪＡＶＡ（登録商標）等のプログラムのＭａｐやＶｅｃｔｏｒ等のコンテナであっても、そのコンテナの要素であってもよい。更に、当該データが行列であっても、その行列の行、列、或いは行列要素であっても良い。
【００５３】
一以上のデータの識別子がデータ所在格納部３０７０に登録されることにより、処理対象のデータが定まる。処理対象のデータの名称は、データの識別子と当該データの格納装置の識別子と対応付けられて、データ所在格納部３０７０に格納される。各データは、複数の部分集合（部分データ）に分割され、その複数の部分集合がそれぞれ複数の格納装置に分散配置されていても良い。また、或るデータが各々２以上の格納装置に多重化されて配置されていても良い。この場合、一つのデータから多重化されたデータは総称して分散データとも呼ばれる。処理サーバ３３０は、多重化されたデータを処理するために、分散データの何れか一つを処理データとして入力すれば良い。
【００５４】
図６は、データ所在格納部３０７０に格納される情報の例を示す図である。図６に示されるように、データ所在格納部３０７０は、データ名称３０７１、分散形態３０７３、データ記述３０７４又はデータ名称３０７７が対応付けられた情報であるデータ所在情報を複数格納する。
【００５５】
分散形態３０７３は、データの格納形態を示す情報である。データ（例えば、ＭｙＤａｔａＳｅｔ１）が単一形態で配置されている場合、そのデータに対応する行（データ所在情報）の分散形態３０７３に「単一」が設定される。データ（例えば、ＭｙＤａｔａＳｅｔ２）が分散形態で配置されている場合、そのデータに対応する行の情報（データ所在情報）の分散形態３０７３に「分散配置」が設定される。データ（例えば、ＭｙＤａｔａＳｅｔ３）が多重化されて配置されている場合、そのデータに対応する行の情報（データ所在情報）の分散形態３０７３に「ｎ重化（１／ｎ）」（ｎは２以上の整数）が設定される。
【００５６】
データ記述３０７４は、データ識別子３０７５、データの格納装置（データサーバ３４０又はその処理データ格納部３４２）の識別子３０７６、及び、処理状況３０７８を含む。データ識別子３０７５は、各データの格納装置においてそのデータを一意に示す識別子である。データ識別子３０７５によって特定される情報は、対象データの種類に応じて決まる。例えば、データがファイルの場合、データ識別子３０７５はファイル名を指定する情報である。データがデータベースのレコードの場合、データ識別子３０７５は、レコードを抽出するようなＳＱＬ（Structured Query Language）を指定する情報であっても良い。
【００５７】
格納装置の識別子３０７６は、各データを格納するデータサーバ３４０又は処理データ格納部３４２の識別子である。識別子３０７６は、分散システム３５０内における一意の情報でも良いし、各機器に割り当てられたＩＰ（Internet Protocol）アドレスでも良い。
【００５８】
処理状況３０７８は、データ識別子３０７５で特定されるデータの処理状況を示す情報である。処理状況３０７８には、当該データの全てが未処理であることを示す「未処理」や、当該データが処理サーバ３３０によって処理中であることを示す「処理中」、当該データの全てが処理済みであることを示す「処理済」が設定される。処理状況３０７８は、当該データの処理の進捗を示す情報（例えば、５０ＭＢ目以降は未処理である等）であっても良い。また、多重化などの場合で、全てのデータ識別子が示すデータの処理状況が等しい場合、まとめて記述しても良い。処理状況３０７８は、処理サーバ３３０による処理の進捗状況に応じて、マスタサーバ３００等によって更新される。
【００５９】
データの一部又は全てのデータが多重化されているとき、当該データに対応するデータの名称３０７１に対応付けられて、「分散配置」であることを示す記述（分散形態３０７３）、及びデータの名称３０７７（ＳｕｂＳｅｔ１等）が格納される。このとき、データ所在格納部３０７０は、前述の部分データ名３０７７のそれぞれをデータの名称３０７１として、それぞれ分散形態３０７３及びデータ記述３０７４と対応付けて格納する（例えば、図６の５行目）。データ（例えば、ＳｕｂＳｅｔ１）が多重化（例えば二重化）されている場合、当該データの名称３０７１は、分散形態３０７３、及びデータに含まれる多重化データ毎のデータ記述３０７４と対応付けられて、データ所在格納部３０７０に格納される。当該データ記述３０７４は、多重化されたデータを格納する格納装置の識別子３０７６及び当該格納装置内においてデータを一意に示す識別子（データ識別子３０７５）を含む。
【００６０】
データ所在格納部３０７０の各行の情報（各データ所在情報）は、対応するデータの処理が完了した際に、マスタサーバ３００、処理サーバ３３０又はデータサーバ３４０によって削除される。また、データ所在格納部３０７０の各行の情報（各データ所在情報）の削除の代わりに、各行の情報（各データ所在情報）に対してデータの処理完了と未完了を表す情報が追加されることで、データの処理の完了が記録されても良い。
【００６１】
なお、分散システム３５０が扱うデータの分散形態の種類が一種類である場合、データ所在格納部３０７０は、分散形態３０７３を含まなくてもよい。以下、説明を簡単にするために、原則的にデータの分散形態の種類が上述した何れか一種類の形態であると仮定される。複数の分散形態の組み合わせに対応するためには、マスタサーバ３００、データサーバ３４０及び処理サーバ３３０は、分散形態３０７３の記述に基づいて、以降説明する処理を切り替えるようにすればよい。
【００６２】
＝＝＝入出力通信路情報格納部３０８０＝＝＝
図７は、入出力通信路情報格納部３０８０に格納される情報の例を示す図である。入出力通信路情報格納部３０８０は、分散システム３５０を構成する各入出力通信路について、通信路ＩＤ３０８１、可用帯域３０８２、入力元装置ＩＤ３０８３及び出力先装置ＩＤ３０８４を対応付けた情報である入出力通信路情報をそれぞれ格納する。通信路ＩＤ３０８１は、入出力通信が発生する機器間の入出力通信路の識別子である。可用帯域３０８２は、入出力通信路で現在利用可能な帯域情報である。可用帯域は、一般に単位時間当たりのデータの転送可能量を示す。帯域情報は実測値であっても推測値であっても良い。入力元装置ＩＤ３０８３は、入出力通信路にデータを入力する装置の識別子である。出力先装置ＩＤ３０８４は、入出力通信路がデータを出力する装置の識別子である。入力元装置ＩＤ３０８３及び出力先装置ＩＤ３０８４で示される装置の識別子は、データサーバ３４０、処理サーバ３３０、ネットワークスイッチ３２０、及び処理データ格納部３４２等に割り当てられた、分散システム３５０内の一意の識別子でも良いし、各機器に割り当てられたＩＰアドレスでも良い。
【００６３】
入出力通信路は、データサーバ３４０のデータ送受信部３４３と処理サーバ３３０のデータ送受信部３３４との間の通信路であってもよいし、データサーバ３４０における処理データ格納部３４２とデータ送受信部３４３との間の通信路であってもよいし、データサーバ３４０のデータ送受信部３４３とネットワークスイッチ３２０のデータ送受信部３２２との間の通信路であっても良い。また、入出力通信路は、ネットワークスイッチ３２０のデータ送受信部３２２と処理サーバ３３０のデータ送受信部３３４との間の通信路であってもよいし、ネットワークスイッチ３２０のデータ送受信部３２２間の通信路であってもよい。ネットワークスイッチ３２０のデータ送受信部３２２を介さずに、直接データサーバ３４０のデータ送受信部３４３と処理サーバ３３０のデータ送受信部３３４との間で通信路が構成されている場合、当該入出力通信路もその通信路に含まれる。以降、このような入出力通信路を単に通信路とも表記する。
【００６４】
＝＝＝サーバ状態格納部３０６０＝＝＝
図８は、サーバ状態格納部３０６０に格納される情報の例を示す図である。サーバ状態格納部３０６０は、分散システム３５０内で稼働している各処理サーバ３３０及び各データサーバ３４０について、サーバＩＤ３０６１、負荷情報３０６２、構成情報３０６３、処理データ格納部情報３０６４及び処理可能量情報３０６５を対応付けた情報である処理サーバ状態情報をそれぞれ格納する。
【００６５】
サーバＩＤ３０６１は、処理サーバ３３０又はデータサーバ３４０の識別子である。処理サーバ３３０及びデータサーバ３４０の識別子は、分散システム３５０において一意の識別子でも良いし、それぞれに割り当てられたＩＰアドレスでも良い。負荷情報３０６２は、処理サーバ３３０又はデータサーバ３４０の処理負荷に関する情報を含む。負荷情報３０６２は、例えば、ＣＰＵの使用率、メモリ使用量、ネットワーク使用帯域等である。
【００６６】
構成情報３０６３は、処理サーバ３３０又はデータサーバ３４０の構成の状態情報を含む。構成情報３０６３は、例えば、処理サーバ３３０における、ＣＰＵ周波数、コア数、及び、メモリ量等のハードウェアの仕様、ＯＳ（Operating System）等のソフトウェアの仕様等である。処理データ格納部情報３０６４は、データサーバ３４０が有する処理データ格納部３４２の識別子を含む。処理可能量情報３０６５は、処理サーバ３３０が単位時間当たりに処理可能なデータ量を示す。
【００６７】
サーバ状態格納部３０６０、データ所在格納部３０７０及び入出力通信路情報格納部３０８０に格納される情報は、スイッチ３２０、処理サーバ３３０、データサーバ３４０等から送信される状態通知によって更新されてもよいし、マスタサーバ３００が問い合わせて得られた応答情報によって更新されてもよい。
【００６８】
ここで、サーバ状態格納部３０６０、データ所在格納部３０７０及び入出力通信路情報格納部３０８０に格納される情報の更新処理の例について説明する。スイッチ３２０は、自身の各ポートの通信のスループット及び各ポートの接続先の装置の識別子（ＭＡＣ（Media Access Control）アドレス、ＩＰアドレス等）を示す情報を生成し、生成された情報を上記状態通知としてマスタサーバ３００に送信する。マスタサーバ３００では、サーバ状態格納部３０６０、データ所在格納部３０７０、入出力通信路情報格納部３０８０が、その状態通知として送られた情報に基づいて、格納されている情報をそれぞれ更新する。他の例としては、処理サーバ３３０が、ネットワークインタフェースのスループットを示す情報、処理対象のデータの処理実行部３３２への割当状況を示す情報、及び処理実行部３３２の使用状況を示す情報を生成し、生成された情報を上記状態通知としてマスタサーバ３００に送信してもよい。他の例として、データサーバ３４０が、自身の処理データ格納部３４２（ディスク）やネットワークインタフェースのスループットを示す情報、及び自身が格納しているデータ要素の一覧を示す情報を生成し、生成された情報を上記状態通知としてマスタサーバ３００に送信してもよい。マスタサーバ３００は、上述のような状態通知を要求する情報を、スイッチ３２０、処理サーバ３３０、及び、データサーバ３４０に送信することで、上述のような状態通知を受信するようにしてもよい。
【００６９】
サーバ状態格納部３０６０、データ所在格納部３０７０、及び、入出力通信路情報格納部３０８０により格納される情報は、クライアント３６０や分散システム３５０の管理者によって予め与えられていても良い。また、これらの情報は、分散システム３５０を探索するクローラ等のプログラムによって収集されても良い。また、入出力通信路情報格納部３０８０及びデータ所在格納部３０７０は、分散ハッシュテーブル等の技術により、分散された装置に備えられていても良い。
【００７０】
＝＝＝モデル生成部３０１＝＝＝
モデル生成部３０１は、サーバ状態格納部３０６０、データ所在格納部３０７０及び入出力通信路情報格納部３０８０から取得される情報に基づいてモデル情報を生成する。モデル情報は、各データサーバ３４０から各処理サーバ３３０への各通信路を示す情報と、各データサーバ３４０から各処理サーバ３３０への単位時間当たりのデータ転送可能量を上限値として含む転送量制約条件と、処理サーバの単位時間当たりのデータ処理可能量を上限値として含む処理量制約条件とを含む。
【００７１】
図９Ａは、モデル情報の例を示す図である。モデル情報５００の各行（各エントリ）には、識別子、流量下限値、流量上限値及び次要素へのポインタが含まれる。識別子は、モデルに含まれるノードを特定するための情報である。モデルに含まれるノードには、データサーバ３４０及び処理サーバ３３０等のようなハードウェア要素に加えて、論理的なソフトウェア要素が設定されてもよい。本実施形態では、ハードウェア要素を示すノードとして、データサーバ３４０及び処理サーバ３３０が割り当てられるが、データサーバ３４０が有する記憶装置（データ装置）が割り当てられてもよいし、処理サーバ３３０が有するＣＰＵ等のような処理装置が割り当てられてもよい。論理的な要素については後述する。次の要素へのポインタには、対応する識別子が示すノードから繋がる他のノードを示す識別子が設定される。次の要素へのポインタには、各行を特定し得る行番号やメモリの番地情報が設定されてもよい。流量下限値及び流量上限値には、上記転送量制約条件又は上記処理量制約条件が設定される。
【００７２】
このようなモデル情報によれば、複数の頂点（ノード）と各頂点を結ぶ複数の辺とにより示される次のような概念モデルが構築され得る。この概念モデルは、ネットワークモデルやグラフ理論に基づく有向グラフ等と呼ばれる。各頂点は、図９Ａのモデル情報における各ノードに対応する。各辺は、各頂点で示されるハードウェア要素間を接続する入出力通信路（通信路）、又は、対象データに対する処理自体に対応する。データ転送経路を示す各辺には、上記転送量制約条件として、例えば、入出力通信路の可用帯域が設定される。対象データに対する処理自体を示す各辺には、上記処理量制約条件が設定される。この概念モデルでは、入出力通信路は、辺と辺の端点となるノードとにより構成される部分グラフで示される。
【００７３】
図９Ｂは、モデル情報により構築される概念モデルの例を示す図である。この概念モデルでは、分散システム３５０で実行されるジョブの処理対象データを、データサーバＤが送信し処理サーバＰが受信するまでの全通信路が示される。データサーバＤと処理サーバＰとを接続する辺は、対応する通信路の可用帯域を属性値（転送量制約条件）として持つ。処理サーバＰと論理的な頂点αとを接続する辺は、処理サーバＰの単位時間当たりの可能処理量を属性値（処理量制約条件）として持つ。特に、可用帯域や可能処理量の制限がない辺は、制約条件がない、即ち、可用帯域や可能処理量が無限大として扱われる。このような制約条件がない辺における可用帯域や可能処理量は、無限大以外の特別な値として扱われてもよい。また、データサーバＤを示す頂点の前段、データサーバＤと処理サーバＰとの間、及び、処理サーバＰと頂点αとの間に複数の頂点や辺が存在してもよい。また、分散システム３５０で実行されるジョブとは、例えば、分散システム３５０が実行要求されたプログラム処理の一単位である。
【００７４】
なお、モデル情報の形態は、図９Ａの符号５００の形態に制限されない。例えば、モデル情報は、頂点や辺の情報を格納するデータフィールド群を参照で連結する、連結リストで実現されてもよい。また、モデル生成部３０１は、ハードウェア要素の動作状態に応じてモデル情報の生成方法を変えてもよい。例えば、モデル生成部３０１は、ＣＰＵ使用率の高い処理サーバ３３０を利用不可能と判定し、そのような処理サーバ３３０をモデル情報の対象から除外してもよい。
【００７５】
＝＝＝決定部３０３＝＝＝
決定部３０３は、モデル生成部３０１により生成されたモデル情報に基づいて、分散システム３５０で実行されるジョブの処理時間が最小となるような、当該モデル情報から構築される概念モデルにおける各辺の流量をそれぞれ決定する。各辺の流量は、例えば、単位時間当たりのデータ処理量（データ転送量）を示す。言い換えれば、決定部３０３は、データサーバ３４０を示す第１頂点、処理サーバ３３０を示す第２頂点、第１頂点から第２頂点に至る第１辺、及び、第２頂点から第２頂点より後段の第３頂点に至る第２辺をそれぞれ含む概念モデル上の各経路に関する、その経路に含まれる第１辺及び第２辺に設定される転送量制約条件及び処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決める。当該概念モデルにおける当該各経路は、処理対象の或るデータが、データサーバ３４０の処理データ格納部３４２から処理サーバ３３０方向へ送出されてから、その処理サーバ３３０で処理されるまでの各データフローを示す。各辺の流量は、例えば、概念モデル上の各経路に関する単位時間当たりのデータ処理量の合計が最大となるように決められる。また、各辺の流量は、データ通信路の負荷を軽減するために、概念モデル上の複数経路から、各経路に含まれる辺の数（通信ホップ数）が最小となる経路が絞り込まれ、その絞り込まれた各経路に関する単位時間当たりのデータ処理量の合計が最大となるように決められる。
【００７６】
決定部３０３は、このように決定された各辺の流量を満たす概念モデル上の各経路を選択し、選択された各経路に含まれる各頂点に応じて、処理サーバ３３０と、この処理サーバ３３０により処理されるデータを格納するデータサーバ３４０との複数組み合わせを決定する。以降、当該概念モデルにおける上記第１辺及び上記第２辺を含む上記各経路、及び、各経路の流量を含む情報がデータフローＦｉ又はデータフロー情報と表記される場合もある。決定部３０３は、このようなデータフロー情報を生成する。
【００７７】
各辺の流量は、概念モデル上の全ての辺ｅにおいて以下の制約条件式を満たすような流量関数ｆ（ｅ）と表記することもできる。
制約条件式：ｌ（ｅ）≦ｆ（ｅ）≦ｕ（ｅ）
ｕ（ｅ）は、各辺ｅに設定された転送量制約条件又は処理量制約条件のうちの上限値（モデル情報の流量上限値）を出力する上方制約容量関数を示し、ｌ（ｅ）は、各辺ｅに設定された転送量制約条件又は処理量制約条件のうちの下限値（モデル情報の流量下限値）を出力する下方制約容量関数を示す。
【００７８】
即ち、決定部３０３は、分散システム３５０で実行されるジョブの処理時間が最小となるような流量関数ｆを決定する。流量関数ｆは、例えば、或る辺集合Ｅ'についてΣｅ∈Ｅ'（ｆ（ｅ））を目的関数として、目的関数を最大化することによって決定できる。目的関数の最大化は、線形計画法や最大流問題におけるフロー増加法、プリフロープッシュ法等を用いることによって実現できる。
【００７９】
なお、決定部３０３は、流量関数ｆを決定するために、モデル情報から構築される当該概念モデルに論理的な頂点や辺を追加してもよい。例えば、決定部３０３は、一組の始点と終点を持つネットワークモデルに対する解法アルゴリズムを適用するために、論理的な始点と、始点とデータサーバ３４０を示す頂点を接続する辺の集合と、論理的な終点と、処理サーバ３３０を示す頂点と終点とを接続する辺の集合とを、当該概念モデルにそれぞれ追加してもよい。このような論理的な頂点及び辺は、モデル生成部３０１により、モデル情報に含められてもよい。
【００８０】
以下の式（１）、（２）及び（３）は、最大フロー問題の形式でネットワークモデルが生成された場合の目的関数（式（１））及び制約関数（式（２）及び式（３））の例を示す。
【数１】
2013145512.tif 000003
【００８１】
Ｅはネットワークモデルを構成する辺の集合を示し、Ｖはネットワークモデルを構成する頂点の集合を示し、ｆ（ｅ）は辺ｅの流量関数を示し、ｓはネットワークモデルの始点を示し、ｔはネットワークモデルの終点を示し、δ−は或る頂点から出る辺の集合を示し、δ＋は或る頂点に入る辺の集合を示し、ｕ（ｅ）は辺ｅの流量上限値を出力する上方制約容量関数を示し、ｌ（ｅ）は辺ｅの流量下限値を出力する下方制約容量関数を示す。
【００８２】
決定部３０３は、決定されたデータフロー情報が分散システム３５０で実行可能となるように、制約条件を追加してもよい。例えば、モデル情報に、転送されるデータと処理されるデータの対応関係が矛盾するフローを解に含めないという制約条件を加えた状態で、流量関数ｆが決定されてもよい。
【００８３】
図１０は、データフロー情報の例を示す図である。上述したように、データフロー情報は、経路情報、及び、経路の流量の情報を含む。図１０の例によれば、経路の流量として、単位時間当たりの処理量（単位処理量）が設定されている。また、経路情報は、その経路に含まれる各頂点（データサーバＤ１、処理サーバＰ１及び論理頂点α）の情報により示されている。また、データフローＦｉを特定するための識別子（Flow1）が設定されている。なお、経路情報が同一のデータフローが複数存在する場合には、それらが統合されてもよい。
【００８４】
決定部３０３は、このように生成されたデータフロー情報に基づいて、処理サーバ３３０と、その処理サーバ３３０の処理対象データの取得先であるデータサーバ３４０との組み合わせが決定され、このような組み合わせを示す決定情報を生成する。生成された決定情報は、その組み合わせに含まれる各処理サーバ３３０により取得される。
【００８５】
図１１は、決定情報の例を示す図である。図１１に示されるように、決定情報には、データサーバＩＤ、処理データ格納部ＩＤ、データＩＤ、受信データ特定情報、単位時間当たりのデータ処理量が含まれる。データサーバＩＤは、処理サーバ３３０が処理すべきデータを格納するデータサーバ３４０の識別子であり、処理データ格納部ＩＤは、そのデータサーバ３４０の処理データ格納部３４２の識別子であり、データＩＤは、処理対象データの識別子である。
【００８６】
決定情報には、データＩＤが含まれていなくてもよい。この場合には、処理サーバ３３０は、データサーバＩＤ及び処理データ格納部ＩＤで特定されるデータサーバ３４０の処理データ格納部３４２に格納されるデータから、ジョブの処理対象となっている未処理のデータを取得するようにしてもよい。
【００８７】
受信データ特定情報は、或るデータサーバ３４０の或る処理データ格納部３４２に格納されている処理対象データが複数の処理サーバ３３０で処理される場合や、複数のデータサーバ３４０に多重化されて格納されている処理対象データが複数の処理サーバ３３０で処理される場合などに、設定される。受信データ特定情報として、例えば、データ内の所定の区間を指定する情報（例えば、区間の開始位置、処理量）が設定される。なお、上述のような場合以外では、決定情報には、受信データ特定情報が設定されなくてもよい。
【００８８】
決定情報に含まれ得る単位時間当たりのデータ処理量は、データフロー情報に含まれる単位処理量に基づいて設定される。決定情報に単位時間当たりのデータ処理量が含まれている場合には、処理サーバ３３０は、データサーバ３４０に対して、その決定情報で特定されるデータを、当該単位時間当たりのデータ処理量で転送するよう要求する。決定情報に単位時間当たりのデータ処理量が含まれていない場合には、処理サーバ３３０は、データサーバ３４０に対して、任意の処理量で転送するよう要求してもよい。
【００８９】
決定情報は、その組み合わせに含まれる各データサーバ３４０により取得されるようにしてもよい。この場合、決定情報には、データサーバＩＤに代えて、処理サーバ３３０の識別子である処理サーバＩＤが含まれれば良い。
【００９０】
処理サーバ３３０が当該決定情報に対応する処理プログラムを処理プログラム格納部３３３に格納していない場合、決定部３０３は、例えばクライアント３６０から受信された処理プログラムを処理サーバ３３０に配布しても良い。決定部３０３は、処理サーバ３３０に対して、決定情報に対応する処理プログラムを格納しているか否か問い合わせ、処理サーバ３３０が処理プログラムを格納していないと判定した場合に、クライアントから受信した処理プログラムを当該処理サーバ３３０に配布するようにしてもよい。
【００９１】
また、上述した概念モデル、制約条件、目的関数を指定するための情報は、構造プログラム等に記述され、その構造プログラム等がクライアント３６０からマスタサーバ３００に与えられても良い。また、当該概念モデル、制約条件、目的関数を指定するための情報は、起動パラメータ等としてクライアント３６０からマスタサーバ３００に与えられても良い。マスタサーバ３００が、データ所在格納部３０７０等を参照して当該概念モデルを決定しても良い。
【００９２】
マスタサーバ３００は、モデル生成部３０１により生成されたモデル情報等や、決定部３０３が生成したデータフロー情報等をメモリ等に保存し、当該モデル情報やデータフロー情報をモデル生成部３０１や決定部３０３の入力に与えても良い。この場合、モデル生成部３０１や決定部３０３は、当該モデル情報やデータフロー情報をモデル生成や最適配置計算に利用しても良い。また、マスタサーバ３００は、全ての概念モデル、制約条件、目的関数に対応可能に実現されてもよいし、特定の概念モデル等にのみ対応可能なように実現されてもよい。
【００９３】
〔第１実施形態における動作例〕
以下、第１実施形態における分散システム３５０の動作例について説明する。
図１２は、分散システム３５０の動作例の全体概要を示すフローチャートである。
【００９４】
マスタサーバ３００は、クライアント３６０から処理プログラムの実行要求である要求情報を受け取ると、次のような各情報をそれぞれ取得する（Ｓ４０１）。マスタサーバ３００は、分散システム３５０内の入出力通信路情報の集合、処理対象データとそのデータを格納するデータサーバ３４０とを対応付けたデータ所在情報の集合、利用可能な処理サーバ３３０の識別子の集合を取得する。
【００９５】
マスタサーバ３００は、取得された処理対象データの集合に未処理のデータが残っているか否か判定する（Ｓ４０２）。マスタサーバ３００は、取得された処理対象データの集合に未処理のデータが残っていないと判定した場合（Ｓ４０２；Ｎｏ）、処理を終了する。
【００９６】
一方、マスタサーバ３００は、取得された処理対象データ集合に未処理のデータが残っていると判定した場合（Ｓ４０２；Ｙｅｓ）、更に、取得された利用可能な処理サーバ３３０の識別子の集合の中に、追加で処理を実行可能な処理サーバ３３０があるか否か判定する（Ｓ４０３）。マスタサーバ３００は、追加で処理を実行可能な処理サーバ３３０が無いと判定した場合（Ｓ４０３；Ｎｏ）、上記（Ｓ４０１）に戻って処理をする。
【００９７】
マスタサーバ３００は、追加で処理を実行可能な処理サーバ３３０があると判定した場合（Ｓ４０３；Ｙｅｓ）、取得された処理サーバ３３０の識別子の集合と、データサーバ３４０の識別子の集合とをキーとして、入出力通信路情報及び処理サーバ状態情報を取得し、これらの情報に基づいてモデル情報を生成する（Ｓ４０４）。以降、追加で処理を実行可能な処理サーバ３３０は、利用可能な処理サーバ３３０とも表記される。
【００９８】
マスタサーバ３００は、生成されたモデル情報に基づいて、所定の制約条件下で所定の目的関数が最大となるような処理サーバ３３０とデータサーバ３４０との各組み合わせを決定する（Ｓ４０５）。マスタサーバ３００は、決定された各組み合わせを示すデータフロー情報を生成する。
【００９９】
マスタサーバ３００により（Ｓ４０５）で決定された組み合わせに対応する、各処理サーバ３３０及び各データサーバ３４０は、処理対象データを送信及び受信し、各処理サーバ３３０は、受信された処理対象データを処理する（Ｓ４０６）。その後、分散システム３５０の処理は、工程（Ｓ４０１）に戻る。
【０１００】
図１３は、工程（Ｓ４０１）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。マスタサーバ３００のモデル生成部３０１は、クライアント３６０からの要求情報で指定された処理対象データを格納するデータサーバ３４０の識別子の集合をデータ所在格納部３０７０から取得する（Ｓ４０１−１）。次に、モデル生成部３０１は、サーバ状態格納部３０６０から、データサーバ３４０の識別子の集合と、処理サーバ３３０の識別子の集合を取得する（Ｓ４０１−２）。なお、工程（Ｓ４０１−２）は、工程（Ｓ４０１−１）より前に実行されてもよい。
【０１０１】
図１４は、工程（Ｓ４０４）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。マスタサーバ３００のモデル生成部３０１は、入出力通信路情報格納部３０８０から、処理対象データを処理サーバ３３０が処理するための通信路を示す入出力通信路情報を取得する。モデル生成部３０１は、メモリ等に保持されるモデル情報（例えば、図９Ａの符号５００）に、取得された入出力通信路情報に基づいて、データサーバ３４０から処理サーバ３３０への通信路の情報を追加する（Ｓ４０４−１０）。
【０１０２】
続いて、モデル生成部３０１は、当該モデル情報に、処理サーバ３３０から後段の論理的頂点への論理的な通信路情報を追加する（Ｓ４０４−２０）。なお、工程（Ｓ４０４−２０）は工程（Ｓ４０４−１０）より前に実行されてもよい。
【０１０３】
図１５は、工程（Ｓ４０４−１０）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。モデル生成部３０１は、当該要求情報に基づいてデータ所在格納部３０７０から取得された情報を参照することにより、処理対象データを格納する各データサーバＤｉについて、工程（Ｓ４０４−１２）をそれぞれ実行する（Ｓ４０４−１１）。モデル生成部３０１は、利用可能な各処理サーバＰｊについて、工程（Ｓ４０４−１３）から工程（Ｓ４０４−１５）をそれぞれ実行する（Ｓ４０４−１２）。
【０１０４】
モデル生成部３０１は、当該モデル情報５００に、データサーバＤｉの名称（又は識別子）を含む行を追加する（Ｓ４０４−１３）。モデル生成部３０１は、その追加された行の次要素へのポインタに処理サーバＰｊの名称（又は識別子）を設定する（Ｓ４０４−１４）。なお、モデル情報５００の行の「識別子」及び「次要素へのポインタ」は、当該概念モデルにおける或るノードを特定し得る情報であればよい。
【０１０５】
モデル生成部３０１は、当該追加行の流量上限値に、データサーバＤｉと処理サーバＰｊとの間の通信路の可用帯域を設定し、当該追加行の流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−１５）。なお、工程（Ｓ４０４−１４）の前に、工程（Ｓ４０４−１５）が実行されてもよい。
【０１０６】
図１６は、工程（Ｓ４０４−２０）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。モデル生成部３０１は、当該要求情報に基づいてサーバ状態格納部３０６０から取得された利用可能な各処理サーバＰｊについて、工程（Ｓ４０４−２２）から工程（Ｓ４０４−２６）をそれぞれ実行する（Ｓ４０４−２１）。
【０１０７】
モデル生成部３０１は、モデル情報５００に、処理サーバＰｊの名称（又は識別子）を含む行を追加する（Ｓ４０４−２２）。モデル生成部３０１は、処理サーバの後段に頂点が存在するか否か判定する（Ｓ４０４−２３）。処理サーバの後段にある頂点とは、モデル情報５００の中で、任意の処理サーバの名称（又は識別子）を含む行の次要素へのポインタを辿ることで到達できる行の識別子を指す。
【０１０８】
モデル生成部３０１は、処理サーバの後段に頂点が存在しないと判定した場合（Ｓ４０４−２３；Ｎｏ）、モデル情報５００に含まれる識別子と一致しない任意の名称である識別子αを設定する（Ｓ４０４−２４）。なお、モデル生成部３０１は、処理サーバの後段に頂点が存在すると判定した場合（Ｓ４０４−２３；Ｙｅｓ）、工程（Ｓ４０４−２４）を実行しない。続いて、モデル生成部３０１は、当該追加行の次要素へのポインタに識別子αを設定する（Ｓ４０４−２５）。
【０１０９】
モデル生成部３０１は、当該追加行の流量上限値に、処理サーバＰｊの単位時間当たりの可能処理量を設定し、かつ、当該追加行の流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−２６）。なお、工程（Ｓ４０４−２５）は、工程（Ｓ４０４−２６）の後に実行されてもよい。また、工程（Ｓ４０４−２６）は、工程（Ｓ４０４−２２）の後のいずれかの時点で実行されてもよい。
【０１１０】
図１７は、工程（Ｓ４０５）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。マスタサーバ３００の決定部３０３は、上述のように生成されたモデル情報に基づいて構築され得る概念モデル（ここでは、有向グラフと表記する）を用いて、以下のように動作する。
【０１１１】
決定部３０３は、当該有向グラフに基づいて、分散システム３５０により実行されるジョブの処理時間が最小となるように、各辺の流量（データフローＦｉ）を決定する（Ｓ４０５−１）。各辺ｅの流量が流量関数ｆ（ｅ）で定義される場合には、決定部３０３は、ジョブの処理時間が最小となるように流量関数ｆ（ｅ）を生成する。決定部３０３は、例えば、モデル情報から構築されるネットワークモデルを基に目的関数（或る辺集合Ｅ'についてΣｅ∈Ｅ'（ｆ（ｅ）））を最大化する。決定部３０３は、線形計画法や最大流問題におけるフロー増加法等を用いて、当該目的関数の最大化の処理を行う。最大流問題におけるフロー増加法を用いた動作の具体例が実施例１として後述される。
【０１１２】
決定部３０３は、当該有向グラフにおける始点を示す頂点を頂点変数ｉに設定する（Ｓ４０５−２）。次に、決定部３０３は、メモリ上に経路情報配列と単位処理量とを格納する領域を確保し、単位処理量の値を無限大で初期化する（Ｓ４０５−３）。
【０１１３】
決定部３０３は、頂点変数ｉにより示される頂点が当該有向グラフの終点であるか否か判定する（Ｓ４０５−４）。以降、頂点変数ｉにより示される頂点は、単に、頂点変数ｉと表記される。決定部３０３は、頂点変数ｉが当該有向グラフの終点でないと判定した場合（Ｓ４０５−４；Ｎｏ）、当該有向グラフにおいて頂点変数ｉから出る通信路の中で、流量がゼロでない通信路が存在するか否かを判定する（Ｓ４０５−５）。決定部３０３は、流量がゼロでない通信路が存在しない場合（Ｓ４０５−５；Ｎｏ）、処理を終了する。
【０１１４】
一方、決定部３０３は、流量がゼロでない通信路が存在する場合（Ｓ４０５−５；Ｙｅｓ）、その通信路を選択する（Ｓ４０５−６）。続いて、決定部３０３は、メモリ上に確保された経路情報配列に頂点変数ｉを追加する（Ｓ４０５−７）。
【０１１５】
決定部３０３は、メモリ上に確保された単位処理量が、工程（Ｓ４０５−６）で選択された通信路の流量より小さい又は等しいか否かを判定し（Ｓ４０５−８）、当該単位処理量が当該通信路の流量より大きい場合（Ｓ４０５−８；Ｎｏ）、当該通信路の流量でメモリ上に確保された単位処理量を更新する（Ｓ４０５−９）。なお、決定部３０３は、当該単位処理量が当該通信路の流量より小さい又は等しい場合（Ｓ４０５−８；Ｙｅｓ）、工程（Ｓ４０５−９）を実行しない。
【０１１６】
決定部３０３は、工程（Ｓ４０５−６）で選択された通信路の他の端点となる頂点を頂点変数ｉに設定し（Ｓ４０５−１０）、工程（Ｓ４０５−４）に戻り、実行する。
【０１１７】
決定部３０３は、工程（Ｓ４０５−４）において、頂点変数ｉが当該有向グラフの終点であると判定した場合（Ｓ４０５−４；Ｙｅｓ）、経路情報配列に格納された経路情報と単位処理量とからデータフロー情報を生成し、そのデータフロー情報をメモリに格納する（Ｓ４０５−１１）。ここで生成されたデータフロー情報の経路情報には、当該有向グラフにおける始点から終点へ至る１つの経路に含まれる、データサーバ３４０を示す頂点及び処理サーバ３３０を示す頂点が少なくとも設定される。また、当該データフロー情報の単位処理量には、当該有向グラフにおける始点から終点へ至る１つの経路によって示される単位時間当たりのデータ処理量が設定される。
【０１１８】
決定部３０３は、経路情報に含まれる各頂点間を結ぶ各辺の流量を、元の流量から当該単位処理量を減じた値で更新する（Ｓ４０５−１２）。その後、決定部３０３は、工程（Ｓ４０５−２）に戻り、再度その工程を実行する。
【０１１９】
図１８は、工程（Ｓ４０６）における第１実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。決定部３０３は、利用可能な処理サーバ３３０の集合内の、各処理サーバＰｊについて、工程（Ｓ４０６−２）をそれぞれ実行する（Ｓ４０６−１）。
【０１２０】
決定部３０３は、処理サーバＰｊを含む経路情報の集合内の、各経路情報Ｆｊについて、工程（Ｓ４０６−３）から工程（Ｓ４０６−４）をそれぞれ実行する（Ｓ４０６−２）。各経路情報Ｆｊは、工程（Ｓ４０５）において生成されたデータフロー情報に含まれる。
【０１２１】
決定部３０３は、経路情報Ｆｊから、処理対象データを格納しているデータサーバ３４０の識別子を抽出する（Ｓ４０６−３）。決定部３０３は、処理サーバＰｊに対して、処理プログラム及び決定情報を送信する（Ｓ４０６−４）。ここで処理プログラムとは、当該処理対象データを格納しているデータサーバ３４０に当該データの転送を指示するための処理プログラムである。データサーバ３４０及び処理対象データは、決定情報に含まれる情報によって特定される。
【０１２２】
〔第１実施形態における作用及び効果〕
第１実施形態における分散システム３５０では、各データサーバ３４０と各処理サーバ３３０との任意の組み合わせ全体から、分散システム３５０内の各入出力通信路の通信帯域と各処理サーバ３３０の処理能力とを考慮したモデル情報が生成される。そして、そのモデル情報により構築され得る概念モデル（ネットワークモデル）に基づいて、処理サーバ３３０とその処理サーバ３３０の処理対象となるデータの取得先であるデータサーバ３４０との組み合わせが決定され、その組み合わせに従って、分散システム３５０で実行されるジョブを構成する処理対象データの送受信及び処理が実行される。
【０１２３】
これにより、第１実施形態によれば、複数のデータサーバ３４０と複数の処理サーバ３３０とを備える分散システム３５０全体で、通信帯域や処理サーバ能力のボトルネックによる効率低下を回避し、実行されるジョブの処理時間を最小化することができる。
【０１２４】
また、第１実施形態では、ネットワークモデルが分散システム３５０内の各入出力通信路の通信帯域を考慮して生成されるため、分散システム３５０において単位時間当たりの全処理サーバ３３０の総処理データ量を最大化するデータ転送経路に基づく処理サーバ３３０とデータサーバ３４０との組み合わせを決定することができる。
【０１２５】
［第１実施形態の第１変形例］
第１実施形態は、マスタサーバ３００が、決定部３０３で生成されたデータフロー情報を出力するように構成されてもよい。この場合、決定部３０３は、図１７の工程（Ｓ４０５−１１）の実行後、生成されデータフロー情報を出力する。決定部３０３は、例えば、図１０の例に示される情報を出力する。なお、この出力形態は限定されない。データフロー情報は、ファイルに出力されてもよいし、他の装置へ送信されてもよいし、表示装置へ表示されてもよいし、印刷装置へ送られてもよい。
【０１２６】
このように出力されたデータフロー情報は、より詳細なデータ処理の計画策定に利用することができる。例えば、マスタサーバ３００がこのデータフロー情報にデータ転送経路の情報を加えることにより、分散システム３５０は、処理の状況に応じて、データの転送経路を動的に決定できるようになる。
【０１２７】
［第２実施形態］
以下、第２実施形態における分散システム３５０について、第１実施形態とは異なる内容を中心に説明する。第１実施形態と同じ内容については適宜省略される。第２実施形態における分散システム３５０では、マスタサーバ３００が分散システム３５０に対して実行を要求された複数のプログラム処理を扱う。分散システムが実行要求されたプログラム処理の一単位は、ジョブと表記される。
【０１２８】
また、第２実施形態では、分散システム３５０に対して実行を要求されたプログラム処理において、処理対象データの部分に応じて単位時間当たりの処理量が変化する形態についてもサポートされる。このとき、ジョブは単位時間当たりの処理量が同一となる部分のデータの集合に置き換えて扱われる。このデータ集合を論理的データ集合と表記される場合がある。
【０１２９】
図１９は、第２実施形態における分散システム３５０の各装置の処理構成例を概念的に示す図である。第２実施形態におけるマスタサーバ３００は、第１実施形態の構成に加えて、ジョブ情報格納部３０４０を更に有する。
【０１３０】
＝＝＝ジョブ情報格納部３０４０＝＝＝
ジョブ情報格納部３０４０は、分散システム３５０に対して実行要求されたプログラム処理に関する構成情報を格納する。
【０１３１】
図２０は、ジョブ情報格納部３０４０に格納される情報の例を示す図である。ジョブ情報格納部３０４０に格納される各行（各エントリ）は、ジョブＩＤ３０４１、データの名称３０４２、最低単位処理量３０４３、最大単位処理量３０４４を含む。ジョブＩＤ３０４１には、分散システム３５０が実行するジョブ毎に割り当てられた、分散システム３５０内において一意の識別子が設定される。データの名称３０４２には、当該ジョブが扱うデータの名称（識別子）が設定される。最低単位処理量３０４３には、当該ジョブが扱うデータである当該論理データ集合に指定された、単位時間当たりの処理量の最低値である。最大単位処理量３０４４は、当該論理データ集合に指定された、単位時間当たりの処理量の最大値である。
【０１３２】
１つのジョブが複数の論理データ集合を扱う場合は、ジョブ情報格納部３０４０には、１つのジョブＩＤを持つ複数の行が格納され、これら各行では、異なる、データの名称３０４２、最低単位処理量３０４３及び最大単位処理量３０４４がそれぞれ格納されてもよい。
【０１３３】
第２実施形態では、マスタサーバ３００のモデル生成部３０１は、ジョブ情報格納部３０４０に格納されるジョブ構成情報をモデル情報５００に更に反映させる。この反映動作については、以下の動作例の項において説明する。これにより、モデル情報から構築され得る概念モデルでは、第１実施形態における構成に加えて、データサーバ３４０を示す頂点の前段に、ジョブを示す論理的な頂点、そのジョブの頂点からデータサーバ３４０へと至る論理的な通信路を示す辺、ジョブの頂点より前段の論理的な頂点、及び、ジョブより前段の頂点からジョブの頂点へ至る論理的な通信路を示す辺が少なくとも追加される。
【０１３４】
〔第２実施形態における動作例〕
【０１３５】
図２１は、工程（Ｓ４０１）における第２実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。図２１では、第１実施形態の詳細動作を示す図１３に、工程（Ｓ４０１−０）が加えられている。工程（Ｓ４０１−０）では、モデル生成部３０１は、ジョブ情報格納部３０４０から、実行中のジョブの集合を取得する。
【０１３６】
図２２は、工程（Ｓ４０４）における第２実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。図２２では、第１実施形態の詳細動作を示す図１４に、工程（Ｓ４０４−３０）が加えられている。工程（Ｓ４０４−３０）では、モデル生成部３０１は、モデル情報５００に、ジョブ情報格納部３０４０から取得されたジョブ集合の中の各ジョブへの論理的な通信路情報と、各ジョブから各ジョブで処理されるデータを格納しているデータサーバ３４０への論理的な通信路情報を追加する（Ｓ４０４−３０）。なお、図２２で示される各工程（Ｓ４０４−３０）、（Ｓ４０４−１０）及び（Ｓ４０４−２０）は、それぞれ順序が入れ替えられても良い。
【０１３７】
図２３は、工程（Ｓ４０４−３０）における第２実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。マスタサーバ３００のモデル生成部３０１は、取得したジョブの集合の中の各ジョブＪｉについて、工程（Ｓ４０４−３２）以降を実行する（Ｓ４０４−３１）。
【０１３８】
モデル生成部３０１は、ジョブＪｉの前段に頂点が存在するか否か判定する（Ｓ４０４−３２）。ジョブＪｉの前段の頂点は、モデル情報５００の中で、次要素へのポインタに或るジョブを示す情報（ジョブ名称）が設定されている行の識別子に対応する。モデル生成部３０１は、ジョブの前段に頂点が存在しない場合（Ｓ４０４−３２；Ｎｏ）、識別子βを設定する（Ｓ４０４−３４）。識別子βは、モデル情報５００に含まれる識別子と一致しない任意の名称である。一方、モデル生成部３０１は、ジョブＪｉの前段に頂点が存在すると判定した場合（Ｓ４０４−３２；Ｙｅｓ）、前段の頂点の識別子βを取得する（Ｓ４０４−３３）。
【０１３９】
モデル生成部３０１は、モデル情報５００に、βを識別子として含む行を追加する（Ｓ４０４−３５）。モデル生成部３０１は、当該追加行の次要素へのポインタにジョブＪｉの名称を設定する（Ｓ４０４−３６）。モデル生成部３０１は、当該追加行の流量上限値及び流量下限値に、ジョブＪｉに割り当てられた最大単位処理量及び最低単位処理量を設定する（Ｓ４０４−３７）。
【０１４０】
モデル生成部３０１は、ジョブＪｉが扱うデータを格納する各データサーバＤｊについて、工程（Ｓ４０４−３９）から工程（Ｓ４０４−３Ｂ）をそれぞれ実行する（Ｓ４０４−３８）。
【０１４１】
モデル生成部３０１は、モデル情報５００に、識別子がジョブＪｉを示す行を追加する（Ｓ４０４−３９）。モデル生成部３０１は、当該追加行の次要素へのポインタに、データサーバＤｊの名称（又は識別子）を設定する（Ｓ４０４−３Ａ）。モデル生成部３０１は、当該追加行の流量上限値に、ジョブＪｉがデータサーバＤｊに対して割り当て可能な転送量を設定し、当該追加行の流量下限値に０以上かつ流量上限値以下の値を設定する（Ｓ４０４−３Ｂ）。ジョブＪｉがデータサーバＤｊに対して割り当て可能な転送量は、例えば、ジョブＪｉが扱う各データに対して指定される要求処理量を示し、ユーザによって与えられても良いし、分散システム３５０により決定されてもよい。
【０１４２】
〔第２実施形態の作用及び効果〕
第２実施形態では、第１実施形態における、分散システム３５０内の各入出力通信路の通信帯域と各処理サーバ３３０の処理能力とに関する制約に加えて、各ジョブに指定される単位処理量の制約、各ジョブで扱われる各データに指定される単位処理量の制約が加味されたモデル情報が生成され、そのモデル情報に基づき構築され得るネットワークモデル（概念モデル）から、処理サーバ３３０とその処理サーバ３３０の処理対象となるデータの取得先であるデータサーバ３４０との組み合わせが決定される。
【０１４３】
これにより、第２実施形態によれば、分散システム３５０で実行されるジョブに対して指定された単位処理量が考慮されて、当該ジョブを構成する処理対象データの送受信及び処理が実行されるため、そのジョブの処理時間を最小化することができる。
【０１４４】
また、第２実施形態では、各ジョブに優先度が設定されている場合に、各優先度が、各ジョブに指定された単位処理量のジョブ間の比率として設定され得る。よって、第２実施形態によれば、各ジョブに優先度が設定されている場合においても、設定された優先度の制約を満たし、かつ、全体として処理時間を最小とするように、処理対象データの送受信及び処理を実行することができる。
【０１４５】
［第２実施形態の第１変形例］
第２実施形態の第１変形例におけるマスタサーバ３００は、モデル情報５００の処理サーバ３３０を示す識別子を含む行において、次要素へのポインタに、ジョブ毎の終端点を設定する。この場合、処理サーバ３３０を示す識別子を含む行の数は、ジョブの終端点の数と等しくなる。
【０１４６】
また、モデル情報５００における処理サーバ３３０を示す識別子を含む行の流量下限値及び流量上限値として、その処理サーバ３３０の各ジョブに対する単位時間当たりの可能処理量が設定されるようにしてもよい。図２４は、第２実施形態の第１変形例におけるサーバ状態格納部３０６０が格納する情報の例を示す図である。図２４に示されるように、サーバ状態格納部３０６０は、各処理サーバ３３０の処理可能量情報３０６５として、各ジョブについての処理可能量をそれぞれ格納する。
【０１４７】
以下、第２実施形態の第１変形例におけるマスタサーバ３００の詳細動作について、第２実施形態と異なる内容を中心に説明する。図２５は、図２２に示される工程（Ｓ４０４−２０）に関する、第２実施形態の第１変形例におけるマスタサーバ３００の詳細動作を示すフローチャートである。
【０１４８】
モデル生成部３０１は、当該要求情報に基づいてサーバ状態格納部３０６０から取得された利用可能な各処理サーバＰｉについて、工程（Ｓ４０４−２Ｂ）をそれぞれ実行する（Ｓ４０４−２Ａ）。
【０１４９】
モデル生成部３０１は、各ジョブＪｊについて、工程（Ｓ４０４−２Ｃ）から工程（Ｓ４０４−２Ｅ）をそれぞれ実行する（Ｓ４０４−２Ｂ）。
【０１５０】
モデル生成部３０１は、モデル情報５００に、処理サーバＰｉの名称（又は識別子）を含む行を追加する（Ｓ４０４−２Ｃ）。モデル生成部３０１は、当該追加行の次要素へのポインタに、ジョブＪｊの終端点を示す識別子を設定する（Ｓ４０４−２Ｄ）。モデル生成部３０１は、当該追加行の流量上限値に、処理サーバＰｉのジョブＪｊに関する単位時間当たりの可能処理量を設定し、当該追加行の流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−２Ｅ）。なお、工程（Ｓ４０４−２Ｅ）は、工程（Ｓ４０４−２Ｄ）の前に実行されてもよい。
【０１５１】
このように、第２実施形態の第１変形例によれば、処理サーバ３３０において処理可能量が異なるジョブも扱うことができ、処理サーバ３３０とデータサーバ３４０との組み合わせを決定するにあたり、各処理サーバ３３０におけるジョブ毎の処理可能量を加味することができる。よって、第２実施形態の第１変形例によれば、実行される各ジョブのシステム全体での処理時間をより精密に最小化することができる。
【０１５２】
［第２実施形態の第２変形例］
第２実施形態の第２変形例におけるマスタサーバ３００は、モデル情報５００の処理サーバ３３０を示す識別子を含む行において、次要素へのポインタに、ジョブを示す情報（名称）を設定する。この場合、処理サーバ３３０を示す識別子を含む行の数は、ジョブの数と等しくなる。第２実施形態の第２変形例では、上述の図２５の工程（Ｓ４０４−２Ｄ）において、次要素へのポインタがジョブＪｊの名称（又は識別子）に設定される。
【０１５３】
サーバ状態格納部３０６０が格納する情報は、第２実施形態の第１変形例と同様である。即ち、第２実施形態の第２変形例においても、モデル情報５００における処理サーバ３３０を示す識別子を含む行の流量下限値及び流量上限値として、その処理サーバ３３０の各ジョブに対する単位時間当たりの可能処理量が設定される。
【０１５４】
第２実施形態の第２変形例によれば、当該第１変形例に比べて、決定部３０３による各辺の流量の決定処理（図１７の工程（Ｓ４０５−１）参照）を容易化及び高速化することができる。これは、第１変形例は、モデル情報を多品種フローでモデル化するのに対して、第２変形例は、モデル情報を循環フローでモデル化するため、概念モデルのアルゴリズムの適用の可能性を高めることができるからである。
【０１５５】
モデル情報を循環フローでモデル化する形態は、他の各実施形態にも適用可能である。この場合、モデル情報において、処理サーバ３３０を示す識別子を含む行の次要素へのポインタには、データサーバ３４０を示す識別子やデータを示す識別子が設定される。このモデル情報により構築される概念モデルでは、処理サーバ３３０を示す頂点から、データサーバ３４０を示す頂点又はデータを示す論理的頂点に至る辺が設けられる。
【０１５６】
［第３実施形態］
以下、第３実施形態における分散システム３５０について、第１実施形態及び第２実施形態とは異なる内容を中心に説明する。第１実施形態及び第２実施形態と同じ内容については適宜省略される。第３実施形態における分散システム３５０では、マスタサーバ３００が、多重化された処理対象データも扱う。
【０１５７】
第３実施形態では、マスタサーバ３００のデータ所在格納部３０７０は、データのサイズ情報を更に格納する。
【０１５８】
図２６は、工程（Ｓ４０４）における第３実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。図２６では、第１実施形態の詳細動作を示す図１４に、工程（Ｓ４０４−４０）が加えられている。工程（Ｓ４０４−４０）では、モデル生成部３０１は、モデル情報５００に、データからデータサーバへの論理的な通信路情報を追加する。なお、図２６で示される各工程（Ｓ４０４−４０）、（Ｓ４０４−１０）及び（Ｓ４０４−２０）はそれぞれ順序が入れ替えられても良い。
【０１５９】
図２７は、工程（Ｓ４０４−４０）における第３実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。モデル生成部３０１は、当該要求情報に基づいて特定される処理対象データの集合内の各データｄｉについて、工程（Ｓ４０４−４２）をそれぞれ実行する（Ｓ４０４−４１）。
【０１６０】
モデル生成部３０１は、多重化されたデータｄｉを格納する各データサーバＤｊについて、工程（Ｓ４０４−４３）から工程（Ｓ４０４−４５）をそれぞれ実行する（Ｓ４０４−４２）。ここで、多重化されたデータｄｉは、多重化数分存在する。
【０１６１】
モデル生成部３０１は、ｄｉを識別子として含む行を追加する（Ｓ４０４−４３）。モデル生成部３０１は、当該追加行の次要素へのポインタに、データサーバＤｊの名称（又は識別子）を設定する（Ｓ４０４−４４）。モデル生成部３０１は、当該追加行における流量上限値及び流量下限値に、データサーバＤｊに対して指定されたデータｄｉの最大処理量及び最低処理量を設定する（Ｓ４０４−４５）。データサーバＤｊに対してデータｄｉの最大処理量又は最低処理量もしくはその両方が指定されていない場合、流量上限値と流量下限値はマスタサーバ３００が決定してもよい。この場合、マスタサーバ３００は、例えば、流量上限値に無限大を設定し、流量下限値に０を設定する。
【０１６２】
これにより、多重化されたデータには、モデル生成部３０１によって生成されたモデル情報５００において、共通の識別子ｄｉが付される。つまり、共通の識別子ｄｉが付された行は、データｄｉの多重化数分追加される。
【０１６３】
図２８は、工程（Ｓ４０６）における第３実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。第３実施形態では、異なるデータサーバ３４０に多重化されて格納される各データについて各処理サーバ３３０がそれぞれ割り当てられる。これにより、複数のデータフロー情報に、多重化された同一データを示す同一頂点が含まれる場合がある。
【０１６４】
マスタサーバ３００の決定部３０３は、処理対象データの集合内の、各データｄｉについて、工程（Ｓ４０６−２−１）及び工程（Ｓ４０６−３−１）をそれぞれ実行する（Ｓ４０６−１−１）。
【０１６５】
決定部３０３は、データｄｉを経路情報に含むデータフロー情報を特定し、特定された各データフロー情報に設定されている単位処理量を、当該各データフロー情報の経路情報に含まれる処理サーバ３３０毎に集計する。決定部３０３は、当該データｄｉをその集計された処理サーバ３３０毎の単位処理量の比で分割し、各分割データｄｉと、それを格納する各データサーバ３４０とを対応付ける（Ｓ４０６−２−１）。
【０１６６】
決定部３０３は、データｄｉを含む経路情報の集合内の各経路情報ｆｊについて、工程（Ｓ４０６−４−１）をそれぞれ実行する（Ｓ４０６−３−１）。決定部３０３は、経路情報ｆｊに含まれる処理サーバＰｋに対して、処理プログラム及び決定情報を送付する（Ｓ４０６−４−１）。ここで処理プログラムとは、当該データｄｉを格納するデータサーバ３４０から、データｄｉの分割部分を転送するよう指示するための処理プログラムである。データサーバ３４０及びデータは、決定情報に含まれる情報によって特定される。
【０１６７】
〔第３実施形態の作用及び効果〕
第３実施形態における分散システム３５０では、処理対象データが多重化されている場合には、多重化後の各データについて処理サーバ３３０をそれぞれ割り当て、多重化後の各データの処理のための通信帯域及び処理サーバ３３０の処理能力を考慮したモデル情報が生成される。そして、そのモデル情報により構築され得る概念モデル（ネットワークモデル）に基づいて、処理サーバ３３０とその処理サーバ３３０の処理対象となるデータの取得先であるデータサーバ３４０との組み合わせが決定される。このとき、多重化後の各データはそれぞれ重複して転送及び処理されるわけではなく、通信帯域及び処理能力に応じた量に分割された各データが各処理サーバ３３０にそれぞれ割り当てられ、システム全体として多重化対象のデータが転送及び処理されるように制御される。
【０１６８】
従って、第３実施形態によれば、処理対象データが多重化されている場合であっても、分散システム３５０全体としてジョブの処理時間を最小化することができる。
【０１６９】
［第４実施形態］
以下、第４実施形態における分散システム３５０について、第１実施形態から第３実施形態とは異なる内容を中心に説明する。第１実施形態から第３実施形態と同じ内容については適宜省略される。第４実施形態における分散システム３５０では、マスタサーバ３００が、データサーバ３４０から処理サーバ３３０への間を、その間に含まれる中間機器及び通信路により更に細かく定義し、それらの詳細の制約情報（可用帯域）を考慮してモデル情報を生成する。よって、第４実施形態では、データサーバ３４０から処理サーバ３３０への間を通信路（入出通信路）に代えデータ転送経路と表記し、そのデータ転送経路を形成するものを通信路と表記する。
【０１７０】
図２９は、第４実施形態における分散システム３５０の各装置の処理構成例を概念的に示す図である。第４実施形態におけるネットワークスイッチ３２０は、第１実施形態の構成に加えて、スイッチ管理部３２１を更に有する。第４実施形態では、中間機器として、ネットワークスイッチ３２０が存在する。
【０１７１】
＜処理サーバ３３０＞
処理サーバ管理部３３１は、マスタサーバ３００に対して、処理サーバ３３０のディスク可用帯域やネットワーク可用帯域等の状態情報を送信する。
【０１７２】
＜データサーバ３４０＞
データサーバ管理部３４１は、マスタサーバ３００に対して、データサーバ３４０のディスク可用帯域やネットワーク可用帯域等を含む状態情報を送信する。
【０１７３】
＜ネットワークスイッチ３２０＞
スイッチ管理部３２１は、ネットワークスイッチ３２０に接続される通信路の可用帯域等の情報を取得し、データ送受信部３２２を介してマスタサーバ３００に送信する。
【０１７４】
＜マスタサーバ３００＞
入出力通信路情報格納部３０８０は、データサーバ３４０から処理サーバ３３０へのデータ転送経路に含まれる、各機器間の通信路の情報を格納する。通信路情報には、接続元装置の識別子、接続先装置の識別子、当該通信路の可用帯域情報等が含まれる。
【０１７５】
モデル生成部３０１は、データサーバ３４０に格納されているデータが処理サーバ３３０で受信されるまでに経由する中間機器（例えばネットワークスイッチ３２０）を示す頂点を更に含むと共に、データサーバ３４０を示す頂点からそのデータサーバ３４０の最寄りの中間機器を示す頂点へ至る辺であって、転送量制約条件の上限値がデータサーバ３４０からその最寄りの中間機器への単位時間当たりの転送可能量に設定される辺、中間機器を示す頂点から他の中間機器を示す頂点へ至る辺であって、転送量制約条件の上限値がその中間機器から当該他の中間機器への単位時間当たりの転送可能量に設定される辺、及び、処理サーバ３３０の最寄りの中間機器を示す頂点から処理サーバ３３０を示す頂点へ至る辺であって、転送量制約条件の上限値がその最寄りの中間機器から処理サーバ３３０への単位時間当たりの転送可能量に設定される辺の少なくとも１つを更に含む概念モデルを構築し得るモデル情報を生成する。例えば、当該中間機器が１つ存在する場合には、その概念モデルは、その中間機器を示す頂点と、データサーバ３４０を示す頂点からその中間機器を示す頂点へ至る辺と、その中間機器を示す頂点から処理サーバ３３０を示す頂点へ至る辺とを含む。また、例えば、当該中間機器として、データサーバ３４０の最寄りの第１中間機器と、処理サーバ３３０の最寄りの第２中間機器とが存在する場合には、その概念モデルは、第１中間機器及び第２中間機器を示す２つの頂点と、データサーバ３４０を示す頂点から第１中間機器を示す頂点へ至る辺と、第１中間機器を示す頂点から第２中間機器を示す頂点へ至る辺と、第２中間機器を示す頂点から処理サーバ３３０を示す頂点へ至る辺とを含む。また、モデル生成部３０１は、後述の実施例４で示されるように、中間機器を示す頂点を、中間機器への１以上の入力部を示す１以上の頂点と、中間機器の１以上の出力部を示す１以上の頂点と、データが転送され得る入力部と出力部との間を結ぶ１以上の辺とで構成するようにしてもよい。
【０１７６】
〔第４実施形態における動作例〕
図３０は、工程（Ｓ４０４）における第４実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。マスタサーバ３００のモデル生成部３０１は、未処理の処理対象データを格納している各データサーバＤｉについて、工程（Ｓ４０４−１２−１０）をそれぞれ実行する（Ｓ４０４−１１）。
【０１７７】
モデル生成部３０１は、モデル情報５００に、データサーバＤｉから処理サーバ３３０へのデータ転送経路に関する行を追加する（Ｓ４０４−１２−１０）。
【０１７８】
図３１Ａ、図３１Ｂ及び図３１Ｃは、工程（Ｓ４０４−１２−１０）における第４実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。ここで、図３１Ａの処理の開始にあたり、デバイスＩＤｉには、初期値として、データサーバＤｉの名称（又は識別子）が設定されている。
【０１７９】
モデル生成部３０１は、入出力通信路情報格納部３０８０から、入力元装置ＩＤに、デバイスＩＤｉが設定されている行の情報（入出力通信路情報）を抽出する（Ｓ４０４−１２−１１）。モデル生成部３０１は、抽出された入出力通信路情報に含まれる出力先装置ＩＤの集合を特定する（Ｓ４０４−１２−１２）。
【０１８０】
モデル生成部３０１は、デバイスＩＤｉがスイッチを示すか否か判定する（Ｓ４０４−１２−１３）。モデル生成部３０１は、デバイスＩＤｉがスイッチを示すと判定した場合（Ｓ４０４−１２−１３；Ｙｅｓ）、図３１Ｂの処理を行う。図３１Ｂについては後述する。
【０１８１】
一方、モデル生成部３０１は、デバイスＩＤｉがスイッチを示さないと判定した場合（Ｓ４０４−１２−１３；Ｎｏ）、更に、デバイスＩＤｉを識別子として含む行が既にモデル情報５００に設定されているか否か判定する（Ｓ４０４−１２−１４）。モデル生成部３０１は、デバイスＩＤｉを識別子として含む行が既にモデル情報５００に設定されていると判定した場合（Ｓ４０４−１２−１４；Ｙｅｓ）、図３１Ａの処理を終了する。
【０１８２】
モデル生成部３０１は、デバイスＩＤｉを識別子として含む行が未だモデル情報５００に設定されていないと判定した場合（Ｓ４０４−１２−１４；Ｎｏ）、工程（Ｓ４０４−１２−１２）により特定された出力先装置ＩＤの集合内の各出力先装置ＩＤｊについて、工程（Ｓ４０４−１２−１６）をそれぞれ実行する（Ｓ４０４−１２−１５）。
【０１８３】
工程（Ｓ４０４−１２−１６）において、モデル生成部３０１は、出力先装置ＩＤｊがスイッチを示すか否か判定する。モデル生成部３０１は、出力先装置ＩＤｊがスイッチを示すと判定した場合（Ｓ４０４−１２−１６；Ｙｅｓ）、図３１Ｃの処理を行う。図３１Ｃについては後述する。
【０１８４】
一方、モデル生成部３０１は、出力先装置ＩＤｊがスイッチを示さないと判定した場合（Ｓ４０４−１２−１６；Ｎｏ）、モデル情報５００に、デバイスＩＤｉを識別子として含む行を追加する（Ｓ４０４−１２−１７）。モデル生成部３０１は、当該追加行における次要素へのポインタに出力先装置ＩＤｊを設定する（Ｓ４０４−１２−１８）。更に、モデル生成部３０１は、当該追加行における流量上限値に、デバイスＩＤｉで示される装置と当該出力先装置ＩＤｊで示される装置との間の入出力通信路の可用帯域を設定し、当該追加行における流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−１２−１９）。なお、工程（Ｓ４０４−１２−１９）は、工程（Ｓ４０４−１２−１８）の前に実行されてもよい。
【０１８５】
続いて、モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示すか否か判定する（Ｓ４０４−１２−１Ａ）。モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示さないと判定した場合（Ｓ４０４−１２−１Ａ；Ｎｏ）、図３１Ａの処理を再帰的に実行する（Ｓ４０４−１２−１Ｂ）。このとき、デバイスＩＤｉには、出力先装置ＩＤｊが初期値として設定される。これにより、モデル情報５００には、出力先装置ＩＤｊを識別子として含む行が追加される。なお、モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示すと判定した場合（Ｓ４０４−１２−１Ａ；Ｙｅｓ）、図３１Ａの処理の再帰実行を行わない。
【０１８６】
以下、図３１Ｂについて説明する。
図３１Ａの工程（Ｓ４０４−１２−１３）において、デバイスＩＤｉがスイッチを示すと判定された場合（Ｓ４０４−１２−１３；Ｙｅｓ）、モデル生成部３０１は、工程（Ｓ４０４−１２−１２）により特定された出力先装置ＩＤの集合内の各出力先装置ＩＤｊについて、工程（Ｓ４０４−１２−１Ｄ）をそれぞれ実行する（Ｓ４０４−１２−１Ｃ）。以降、スイッチを示すデバイスＩＤｉはスイッチｉと表記される場合もある。
【０１８７】
モデル生成部３０１は、スイッチｉにおける、出力先装置ＩＤｊへの出力口の識別子を含む行がモデル情報５００に存在するか否かを判定する（Ｓ４０４−１２−１Ｄ）。モデル生成部３０１は、モデル情報にその出力口の識別子を含む行が存在しないと判定した場合（Ｓ４０４−１２−１Ｄ；Ｎｏ）、モデル情報５００に、スイッチｉにおける出力先装置ＩＤｊへの出力口の識別子を含む行を追加する（Ｓ４０４−１２−１Ｅ）。
【０１８８】
モデル生成部３０１は、当該追加行における次要素へのポインタに、出力先装置ＩＤｊを設定する（Ｓ４０４−１２−１Ｆ）。更に、モデル生成部３０１は、当該追加行における流量上限値に、デバイスＩＤｉで示される装置と当該出力先装置ＩＤｊで示される装置との間の入出力通信路の可用帯域を設定し、当該追加行における流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−１２−１Ｇ）。なお、工程（Ｓ４０４−１２−１Ｇ）は、工程（Ｓ４０４−１２−１Ｆ）の前に実行されてもよい。一方、モデル生成部３０１は、モデル情報５００に当該出力口の識別子を含む行が存在すると判定した場合（Ｓ４０４−１２−１Ｄ；Ｙｅｓ）、上述の工程（Ｓ４０４−１２−１Ｅ）、（Ｓ４０４−１２−１Ｆ）及び（Ｓ４０４−１２−１Ｇ）を実行しない。
【０１８９】
モデル生成部３０１は、入力元装置ＩＤが当該出力先装置ＩＤｊとは異なる各スイッチｉにおける入力口の識別子ｋについて、工程（Ｓ４０４−１２−１Ｉ）をそれぞれ実行する（Ｓ４０４−１２−１Ｈ）。
【０１９０】
モデル生成部３０１は、モデル情報５００に対して、識別子ｋを含む行の中で、次要素へのポインタに当該出力先装置ＩＤｊへの出力口を示す識別子が設定されている行が存在するか否か判定する（Ｓ４０４−１２−１Ｉ）。モデル生成部３０１は、モデル情報５００に該当する行が存在しないと判定した場合（Ｓ４０４−１２−１Ｉ；Ｎｏ）、モデル情報５００に、ｋを識別子として含む行を追加する（Ｓ４０４−１２−１Ｊ）。
【０１９１】
モデル生成部３０１は、当該追加行における次要素へのポインタに、スイッチｉにおける当該出力先装置ＩＤｊへの出力口の識別子を設定する（Ｓ４０４−１２−１Ｋ）。モデル生成部３０１は、当該追加行における流量上限値に無限大を設定し、当該追加行における流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−１２−１Ｌ）。なお、工程（Ｓ４０４−１２−１Ｌ）は、工程（Ｓ４０４−１２−１Ｋ）の前に実行されてもよい。
【０１９２】
一方、モデル情報５００に該当する行が存在すると判定した場合（Ｓ４０４−１２−１Ｉ；Ｙｅｓ）、上述の工程（Ｓ４０４−１２−１Ｊ）、（Ｓ４０４−１２−１Ｋ）及び（Ｓ４０４−１２−１Ｌ）は実行されない。なお、工程（Ｓ４０４−１２−１Ｈ）が示す処理ループは、工程（Ｓ４０４−１２−１Ｄ）の前に実行されてもよい。
【０１９３】
続いて、モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示すか否か判定する（Ｓ４０４−１２−１Ｍ）。モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示さないと判定した場合（Ｓ４０４−１２−１Ｍ；Ｎｏ）、図３１Ａの処理を再帰的に実行する（Ｓ４０４−１２−１Ｎ）。このとき、デバイスＩＤｉは、出力先装置ＩＤｊが初期値として設定される。これにより、モデル情報５００には、出力先装置ＩＤｊを識別子として含む行が追加される。一方、モデル生成部３０１は、出力先装置ＩＤｊが処理サーバ３３０を示すと判定した場合（Ｓ４０４−１２−１Ｍ；Ｙｅｓ）、図３１Ａの処理の再帰実行を行わない。
【０１９４】
以下、図３１Ｃについて説明する。以降、スイッチを示す出力先装置ＩＤｊはスイッチｊと表記される場合もある。
【０１９５】
図３１Ａの工程（Ｓ４０４−１２−１６）において、出力先装置ＩＤｊがスイッチを示すと判定された場合（Ｓ４０４−１２−１６；Ｙｅｓ）、モデル生成部３０１は、出力先装置ＩＤがデバイスＩＤｉとは異なる各スイッチｊにおける出力口の識別子ｋについて、工程（Ｓ４０４−１２−１Ｐ）をそれぞれ実行する（Ｓ４０４−１２−１Ｏ）。
【０１９６】
モデル生成部３０１は、モデル情報５００において、次要素へのポインタに識別子ｋが設定されている行が存在するか否か判定する（Ｓ４０４−１２−１Ｐ）。モデル生成部３０１は、該当する行が存在しないと判定した場合（Ｓ４０４−１２−１Ｐ；Ｎｏ）、モデル情報５００に、スイッチｊにおけるデバイスＩＤｉからの入力口の識別子を含む行を追加する（Ｓ４０４−１２−１Ｑ）。
【０１９７】
モデル生成部３０１は、当該追加行における次要素へのポインタに、識別子ｋを設定する（Ｓ４０４−１２−１Ｒ）。更に、モデル生成部３０１は、当該追加行における流量上限値に無限大を設定し、当該追加行における流量下限値に０を設定する（Ｓ４０４−１２−１Ｓ）。なお、工程（Ｓ４０４−１２−１Ｓ）は、工程（Ｓ４０４−１２−１Ｒ）の前に実行されてもよい。一方、モデル生成部３０１は、該当する行が存在すると判定した場合（Ｓ４０４−１２−１Ｍ；Ｙｅｓ）、工程（Ｓ４０４−１２−１Ｑ）、（Ｓ４０４−１２−１Ｒ）及び（Ｓ４０４−１２−１Ｓ）を実行しない。
【０１９８】
続いて、モデル生成部３０１は、モデル情報５００に、デバイスＩＤｉを識別子として含む行を追加する（Ｓ４０４−１２−１Ｔ）。モデル生成部３０１は、当該追加行における次要素へのポインタに、デバイスＩＤｉにおけるスイッチｊからの入力口の識別子を設定する（Ｓ４０４−１２−１Ｕ）。更に、モデル生成部３０１は、当該追加行における流量上限値に、デバイスＩＤｉで示される装置と当該出力先装置ＩＤｊで示される装置（スイッチｊ）との間の入出力通信路の可用帯域を設定し、当該追加行における流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−１２−１Ｖ）。なお、工程（Ｓ４０４−１２−１Ｖ）は、工程（Ｓ４０４−１２−１Ｕ）の前に実行されてもよい。
【０１９９】
モデル生成部３０１は、図３１Ａの処理を再帰的に実行する（Ｓ４０４−１２−１Ｗ）。このとき、デバイスＩＤｉは、出力先装置ＩＤｊが初期値として設定される。これにより、モデル情報５００には、出力先装置ＩＤｊを識別子として含む行が追加される。
【０２００】
〔第４実施形態の作用及び効果〕
第４実施形態では、各データサーバ３４０と各処理サーバ３３０との間のデータ転送経路を構成する機器及び通信路の可用帯域が更に考慮されて、処理サーバ３３０とその処理サーバ３３０の処理対象となるデータの取得先であるデータサーバ３４０との組み合わせが決定される。よって、第４実施形態によれば、実行される各ジョブのシステム全体での処理時間をより精密に最小化することができる。
【０２０１】
［第５実施形態］
以下、第５実施形態における分散システム３５０について、上述の各実施形態とは異なる内容を中心に説明する。上述の各実施形態と同じ内容については適宜省略される。第５実施形態における分散システム３５０では、マスタサーバ３００が、処理サーバ３３０により複数のジョブの処理が並行して実行される場合の処理能力の低下を考慮してモデル情報を生成する。
【０２０２】
図３２は、工程（Ｓ４０４−２０）（図２２参照）における第５実施形態のマスタサーバ３００の詳細動作を示すフローチャートである。第５実施形態では、第２実施形態で生成される情報に加えて、複数のジョブの処理による処理サーバ３３０の処理能力の低下を示す辺がモデル情報に追加される。
【０２０３】
モデル生成部３０１は、当該要求情報に基づいてサーバ状態格納部３０６０から取得された利用可能な各処理サーバＰｉについて、工程（Ｓ４０４−２Ｇ）から工程（Ｓ４０４−２Ｊ）をそれぞれ実行する（Ｓ４０４−２Ｆ）。
【０２０４】
モデル生成部３０１は、モデル情報５００に、処理サーバＰｉの名称（又は識別子）を含む行を追加する（Ｓ４０４−２Ｇ）。モデル生成部３０１は、当該追加行における次要素へのポインタに、処理サーバＰｉを示す第２の名称（又は識別子）を設定する（Ｓ４０４−２Ｈ）。処理サーバＰｉを示す第２の名称（又は識別子）とは、モデル情報５００で一意となるＰｉと対応する名称（又は識別子）である。更に、モデル生成部３０１は、当該追加行における流量上限値に、処理サーバＰｉの単位時間当たりの可能処理量を設定し、当該追加行における流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−２Ｉ）。なお、工程（Ｓ４０４−２Ｉ）は、工程（Ｓ４０４−２Ｈ）の前に実行されてもよい。
【０２０５】
モデル生成部３０１は、各ジョブＪｊについて、工程（Ｓ４０４−２Ｋ）から工程（Ｓ４０４−２Ｍ）をそれぞれ実行する（Ｓ４０４−２Ｊ）。
【０２０６】
モデル生成部３０１は、モデル情報５００に、処理サーバＰｉを示す第２の名称（又は識別子）を含む行を追加する（Ｓ４０４−２Ｋ）。モデル生成部３０１は、当該追加行の次要素へのポインタに、ジョブＪｊの終端点を示す識別子を設定する（Ｓ４０４−２Ｌ）。更に、モデル生成部３０１は、当該追加行の流量上限値に、ジョブＪｊに対する処理サーバＰｉの単位時間当たりの可能処理量を設定し、当該追加行の流量下限値に、０以上かつ流量上限値以下の値を設定する（Ｓ４０４−２Ｍ）。なお、工程（Ｓ４０４−２Ｍ）は、工程（Ｓ４０４−２Ｌ）の前に実行されてもよい。
【０２０７】
〔第５実施形態の作用及び効果〕
第５実施形態の分散システム３５０では、処理サーバ３３０の、並列に実行される各ジョブについての各処理能力が制約条件としてモデル情報に更に付加され、このモデル情報により構築され得る概念モデル（ネットワークモデル）に基づいて、処理サーバ３３０とその処理サーバ３３０の処理対象となるデータの取得先であるデータサーバ３４０との組み合わせが決定される。
【０２０８】
従って、第５実施形態によれば、複数のジョブの処理による処理能力の低下が考慮された分散システム３５０のデータ送受信及びデータ処理を実現することができ、システム全体で処理時間を最小とすることができる。
【０２０９】
［第６実施形態］
以下、第６実施形態における分散システム３５０について、上述の各実施形態とは異なる内容を中心に説明する。上述の各実施形態と同じ内容については適宜省略される。第６実施形態における分散システム３５０では、マスタサーバ３００が、処理サーバ３３０により処理負荷の異なる複数のジョブの処理が並行して行われる場合の処理能力の低下を考慮してモデル情報を生成する。
【０２１０】
＜マスタサーバ３００＞
図３３は、第６実施形態におけるサーバ状態格納部３０６０が格納する情報の例を示す図である。図３３に示されるように、サーバ状態格納部３０６０は、負荷情報３０６２として残リソース情報を格納し、更に新たな処理負荷情報３０６６を格納する。残リソース情報は、処理の実行時に処理サーバ３３０が使用するリソースの残量を示す。処理負荷情報は、処理の実行時に使用する処理サーバ３３０のリソースの量を示す。処理負荷情報は、例えば、単位処理量あたりのリソース使用量で表される。
【０２１１】
第６実施形態におけるマスタサーバ３００の決定部３０３は、各辺の流量（流量関数ｆ（ｅ））を決定するにあたり（図１７の工程（Ｓ４０５−１））、サーバ状態格納部３０６０から取得される残リソース情報（負荷情報３０６２）及び処理負荷情報３０６６を更に考慮する。
【０２１２】
〔第６実施形態の作用及び効果〕
第６実施形態では、各処理サーバ３３０に関し、各ジョブの単位処理量当たりに費やされる処理負荷（リソース量）、及び、残負荷（リソース残量）がそれぞれ管理され、これらを制約条件にして概念モデルにおける経路が選択され、結果、各ジョブに関しデータをやりとりするデータサーバ３４０、処理サーバ３３０及び単位処理量の対応関係が決定される。即ち、第６実施形態では、処理負荷の異なるジョブが並列に処理される際の処理サーバ３３０の処理能力が更に加味される。
【０２１３】
従って、第６実施形態によれば、処理負荷の異なる複数のジョブの処理による処理能力の低下を考慮された分散システム３５０のデータ送受信及びデータ処理を実現することができ、システム全体で処理時間を最小とすることができる。
【０２１４】
なお、上述の第６実施形態では、サーバ状態格納部３０６０の処理負荷情報には、ジョブ毎の単位処理量当たりに費やされる処理負荷（リソース量）が格納されていたが、当該処理負荷情報には、ジョブ毎の区別をなくした単位処理量当たりに費やされる処理負荷が格納されてもよい。
【０２１５】
以下に実施例を挙げ、上述の各実施形態を更に詳細に説明する。なお、本発明は以下の各実施例から何ら限定を受けない。
【実施例１】
【０２１６】
実施例１では、上述の第１実施形態の具体例を示す。
図３４は、実施例１における分散システム３５０の構成例を概念的に示す図である。実施例１における本分散システム３５０は、スイッチｓｗ１及びｓｗ２、サーバｎ１からｎ４を有し、サーバｎ１からｎ４はスイッチｓｗ１及びｓｗ２を介して相互に接続される。サーバｎ１からｎ４は、状況に応じて処理サーバ３３０及びデータサーバ３４０として機能する。サーバｎ１からｎ４は、処理データ格納部３４２として、ディスクＤ１からＤ４を有する。実施例１では、サーバｎ１からｎ４のいずれか１つがマスタサーバ３００として機能する。サーバｎ１は利用可能な処理実行部３３２としてｐ１を有し、サーバｎ３は利用可能な処理実行部３３２としてｐ３を有する。【０２１７】
図３５は、実施例１におけるサーバ状態格納部３０６０に格納される情報を示す図である。実施例１では、サーバｎ１及びｎ３が利用可能な処理サーバ３３０となる。サーバｎ１の処理可能量は５０ＭＢ／ｓであり、サーバｎ３の処理可能量は１５０ＭＢ／ｓである。【０２１８】
図３６は、実施例１における入出力通信路情報格納部３０８０に格納される情報を示す図である。サーバｎ２からサーバｎ１へのデータ送信時の可用帯域、サーバｎ２からサーバｎ３へのデータ送信時の可用帯域、及び、サーバｎ４からサーバｎ１へのデータ送信時の可用帯域はそれぞれ５０ＭＢ／ｓであり、サーバｎ４からサーバｎ３へのデータ送信時の可用帯域は１００ＭＢ／ｓである。【０２１９】
図３７は、実施例１におけるデータ所在格納部３０７０に格納される情報を示す図である。処理対象データ（ＭｙＤａｔａＳｅｔ１）は、ファイルｄａ、ｄｂ及びｄｃに分割され格納されており、ファイルｄａ及びｄｂは、サーバｎ２のディスクＤ２内に格納され、ファイルｄｃは、サーバｎ４のディスクＤ４内に格納されている。このように、処理対象データ（ＭｙＤａｔａＳｅｔ１）は、分散配置されており、多重化されていないデータである。【０２２０】
マスタサーバ３００のサーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図３５、図３６及び図３７に示す状態である場合に、クライアント３６０によって処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用する処理プログラムの実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２２１】
マスタサーバ３００のモデル生成部３０１は、図３７のデータ所在格納部３０７０から、処理対象データが格納されているデータサーバ３４０の識別子の集合として｛ｎ２、ｎ４｝を得る。モデル生成部３０１は、図３５のサーバ状態格納部３０６０から、利用可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ３｝を得る。モデル生成部３０１は、これら取得された｛ｎ１、ｎ３｝及び｛ｎ２、ｎ４｝に関し、サーバ状態格納部３０６０に格納されている情報及び入出力通信路情報格納部３０８０に格納されている情報に基づいて、モデル情報を生成する。【０２２２】
図３８は、実施例１において生成されたモデル情報を示す図である。図３９は、図３８により示されるモデル情報により構築される概念モデル（有向グラフ、ネットワークモデル）を示す図である。図３９で示される概念モデル上の各辺に付された値は、その通信路における現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）、又は、その辺の始点に対応する処理サーバにおける現在の単位時間当たりのデータ処理量の最大値（処理量制約条件の上限値）を示す。【０２２３】
マスタサーバ３００の決定部３０３は、図３８のモデル情報に基づいて、当該要求情報に対応するジョブの処理時間がシステム全体で最小となるように、当該概念モデルにおける各辺の流量（流量関数ｆ）をそれぞれ決定する。実施例１では、分散システム３５０における単位時間当たりのデータ処理量が最大となるように流量関数ｆが決定される。図４０Ａから図４０Ｇは、実施例１における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。【０２２４】
決定部３０３は、図３８のモデル情報に基づいて、図４０Ａに示されるようなネットワークモデルを構築する。なお、ネットワークモデルの構築とは、ソフトウェア要素としての何かしらのデータ形態を生成するといった意味のみを持つものではなく、モデル情報が用いられて流量関数ｆが決定されるまでの処理を説明するための単なる概念の意味でも用いられる。このネットワークモデルでは、始点ｓが設定され、終点ｔが設定される。【０２２５】
ここで、図４０Ｂに示されるように、経路（ｓ、ｎ２、ｎ１、ｔ）に５０ＭＢ/ｓのフロー（流量）が与えられると、決定部３０３は、図４０Ｃに示されるネットワークの残余グラフを特定する。以降、残余グラフでは、流量０のフローは図示されない。【０２２６】
次に、決定部３０３は、図４０Ｃに示される残余グラフからフロー増加路を特定し、その経路に対してフローを付与する。ここでは、図４０Ｃに示される残余グラフに基づいて、図４０Ｄに示されるように、経路（ｓ、ｎ２、ｎ３、ｔ）に５０ＭＢ/ｓのフローが与えられる。結果、決定部３０３は、図４０Ｅに示されるネットワークの残余グラフを特定する。【０２２７】
決定部３０３は、図４０Ｅに示される残余グラフからフロー増加路を特定し、その経路に対してフローを与える。決定部３０３は、図４０Ｅに示される残余グラフに基づいて、図４０Ｆに示されるように、経路（ｓ、ｎ４、ｎ３、ｔ）に１００ＭＢ/ｓのフローを付与する。結果、決定部３０３は、図４０Ｇに示されるネットワークの残余グラフを特定する。【０２２８】
ここで、図４０Ｇに示されるようにこれ以上のフロー増加路は存在しないため、決定部３０３は処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０２２９】
図４１は、実施例１におけるデータフロー情報を示す図である。決定部３０３は、このように決定されたデータフロー情報に基づいて、処理プログラムをサーバｎ１及びｎ３に送信する。更に、決定部３０３は、処理サーバｎ１及びｎ３に、処理プログラムに対応する決定情報を送信することによって、データ受信と処理実行とを指示する。【０２３０】
図４２は、実施例１において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得されたデータの処理を実行する。処理サーバｎ３は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータの処理を実行する。また、処理サーバｎ３は、データサーバｎ４の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータの処理を実行する。
【実施例２】
【０２３１】
実施例２では、上述の第２実施形態の第１変形例の具体例を示す。実施例２における分散システム３５０の構成は実施例１と同様である（図３４参照）。また、実施例２における入出力通信路情報格納部３０８０の状態についても実施例１と同様である（図３６参照）。【０２３２】
図４３は、実施例２におけるジョブ情報格納部３０４０に格納される情報を示す図である。実施例２では、プログラムを実行する単位として、ジョブＭｙＪｏｂ１とジョブＭｙＪｏｂ２が投入される。ジョブＭｙＪｏｂ１の最大単位処理量は２５ＭＢ／ｓに設定され、ジョブＭｙＪｏｂ１の最低単位処理量は設定されていない。一方、ジョブＭｙＪｏｂ２の最低単位処理量が５０ＭＢ／ｓに設定されており、ジョブＭｙＪｏｂ２の最大単位処理量は設定されていない。【０２３３】
図４４は、実施例２におけるサーバ状態格納部３０６０に格納される情報を示す図である。実施例２では、サーバｎ１はジョブＭｙＪｏｂ１及びＭｙＪｏｂ２をそれぞれ５０ＭＢ／ｓで処理することが可能であり、サーバｎ３はジョブＭｙＪｏｂ１及びＭｙＪｏｂ２をそれぞれ１５０ＭＢ／ｓで処理することが可能である。【０２３４】
図４５は、実施例２におけるデータ所在格納部３０７０に格納される情報を示す図である。図４５に示されるように、データ所在格納部３０７０には、処理対象データＭｙＤａｔａＳｅｔ１及びＭｙＤａｔａＳｅｔ２についての各情報がそれぞれ格納されている。ＭｙＤａｔａＳｅｔ１はファイルｄａに格納されており、そのファイルｄａはサーバｎ２のディスクＤ２内に格納されている。ＭｙＤａｔａＳｅｔ２は、ファイルｄｂ、ｄｃ、及びｄｄに分割されて格納されており、ファイルｄｂ及びｄｃは、サーバｎ２のディスクＤ２内に格納されており、ファイルｄｄは、サーバｎ４のディスクＤ４内に格納されている。ＭｙＤａｔａＳｅｔ１及びＭｙＤａｔａＳｅｔ２は、分散配置されており、多重化されていないデータである。【０２３５】
マスタサーバ３００のジョブ情報格納部３０４０、サーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図４３、図４４、図３６、図４５に示す状態である場合に、クライアント３６０によって、処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用するジョブＭｙＪｏｂ１の実行を要求し、かつ、処理対象データ（ＭｙＤａｔａＳｅｔ２）を使用するジョブＭｙＪｏｂ２の実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２３６】
マスタサーバ３００のモデル生成部３０１は、図４３のジョブ情報格納部３０４０から、実行が指示されているジョブの集合として｛ＭｙＪｏｂ１、ＭｙＪｏｂ２｝を得る。モデル生成部３０１は、各ジョブに関する、ジョブが使用するデータの名称、最低単位処理量及び最大単位処理量をそれぞれ取得する。【０２３７】
モデル生成部３０１は、図４５のデータ所在格納部３０７０から、処理対象データが格納されているデータサーバ３４０の識別子の集合として｛Ｄ２、Ｄ４｝を得る。モデル生成部３０１は、図４４のサーバ状態格納部３０６０から、データサーバ３４０の識別子の集合として｛ｎ２、ｎ４｝を取得し、利用可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ３｝を得る。更に、モデル生成部３０１は、図４４のサーバ状態格納部３０６０から、利用可能な処理サーバｎ１及びｎ３の処理可能量情報を得る。【０２３８】
モデル生成部３０１は、このように取得された各集合及び図３６の入出力通信路情報格納部３０８０に格納された情報に基づいて、モデル情報を生成する。図４６は、実施例２において生成されるモデル情報を示す図である。図４７は、図４６に示されるモデル情報により構築される概念モデルを示す図である。図４７で示される概念モデル上の各辺に付された値は、その通信路における現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）、又は、その辺の始点に対応する処理サーバにおける現在の単位時間当たりのデータ処理量の最大値（処理量制約条件の上限値）を示す。【０２３９】
決定部３０３は、図４６のモデル情報に基づいて、ジョブの処理時間が最小となるように流量関数ｆを決定する。図４８Ａから図４８Ｆ及び図４９Ａから図４９Ｊは、実施例２における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。【０２４０】
図４８Ａから図４８Ｆは、下限流量制限を満たす初期フローの算出手順の一例を示す図である。まず、決定部３０３は、図４６のモデル情報に基づいて、図４８Ａに示されるネットワークモデルを構築する。このネットワークモデルでは、始点ｓ１及びｓ２が設定され、始点ｓ１に対応する終点ｔ１が設定され、始点ｓ２に対応する終点ｔ２が設定される。更に、決定部３０３は、図４８Ａに示されるネットワークモデルに対し、仮想始点ｓ＊及び仮想終点ｔ＊を設定する。決定部３０３は、流量制限が付与された辺の新たな流量上限値に、変更前の流量上限値と変更前の流量下限値との差分値を設定する。また、決定部３０３は、当該辺の新たな流量下限値に０を設定する。このような処理が図４８Ａに示されるネットワークモデルに対して行われることにより図４８Ｂに示されるネットワークモデルが構築される。【０２４１】
決定部３０３は、下限流量制限が付与されているｓ２とＭｙＪｏｂ２を接続する辺の終点と仮想始点ｓ＊との間、及び、ｓ２と仮想終点ｔ＊との間をそれぞれ接続する。具体的には、前述の各頂点の間に、所定の流量上限値が設定された辺が追加される。この所定の流量上限値とは、下限流量制限が付与されている当該辺に設定されていた変更前の流量下限値である。また、決定部３０３は、終点ｔ２と始点ｓ２との間を接続する。具体的には終点ｔ２と始点ｓ２との間に、流量上限値が無限大である辺を追加する。このような処理が図４８Ｂに示されたネットワークモデルに対して実行されることにより、図４８Ｃに示されるネットワークモデルが構築される。【０２４２】
決定部３０３は、図４８Ｃに示されるネットワークモデルに対して、ｓ＊から出る辺及びｔ＊に入る辺の流量が飽和するｓ＊−ｔ＊−フローを求める。なお、該当するフローが存在しないことは、下限流量制限を満たす解が元のネットワークモデルに存在しないことを示す。第２実施例では、図４８Ｄに示される経路（ｓ＊、ＭｙＪｏｂ２、ｎ４、ｎ３、ｔ２、ｓ２、ｔ＊）がｓ＊−ｔ＊−フローに該当する。【０２４３】
決定部３０３は、ネットワークモデルから、追加された頂点及び辺を削除し、流量制限が付与されている当該辺の流量制限値を変更前の元の値に戻す。そして、決定部３０３は、下限流量制限が付与されている当該辺に対し、流量下限値の分だけフローを与える。具体的には、決定部３０３は、図４８Ａに示されるネットワークにおいて、図４８Ｅに示されるように、追加された頂点及び辺が削除された現実の経路（ｓ２、ＭｙＪｏｂ２、ｎ４、ｎ３、ｔ２）に５０ＭＢ／ｓのフローを与える。結果、図４８Ｆに示されるネットワークの残余グラフが特定される。この経路（ｓ２、ＭｙＪｏｂ２、ｎ４、ｎ３、ｔ２）が、下限流量制限を満たす初期フロー（図４９Ａ）である。【０２４４】
決定部３０３は、図４９Ｂ（図４８Ｆと同様）に示される残余グラフからフロー増加路を特定し、その経路に対してフローを与える。具体的には、決定部３０３は、図４９Ｂに示される残余グラフに基づいて、図４９Ｃに示されるような経路（ｓ１、ＭｙＪｏｂ１、ｎ２、ｎ１、ｔ１）に２５ＭＢ／ｓのフローを与える。結果、決定部３０３は、図４９Ｄに示されるネットワークの残余グラフを特定する。【０２４５】
決定部３０３は、図４９Ｄに示される残余グラフからフロー増加路を特定し、その経路に対してフローを与える。決定部３０３は、図４９Ｄに示される残余グラフに基づいて、図４９Ｅに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ４、ｎ３、ｔ２）に５０ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図４９Ｆに示されるネットワークの残余グラフを特定する。【０２４６】
決定部３０３は、図４９Ｆに示される残余グラフからフロー増加路を特定し、その経路に対してフローを与える。これにより、決定部３０３は、図４９Ｆに示される残余グラフに基づいて、図４９Ｇに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ２、ｎ１、ｔ２）に５０ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図４９Ｈに示されるネットワークの残余グラフを特定する。【０２４７】
決定部３０３は、図４９Ｈに示される残余グラフからフロー増加路を特定し、その経路に対してフローを与える。決定部３０３は、図４９Ｈに示される残余グラフに基づいて、図４９Ｉに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ２、ｎ３、ｔ２）に５０ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図４９Ｊに示されるネットワークの残余グラフを特定する。【０２４８】
ここで、図４９Ｊに示されるようにこれ以上のフロー増加路は存在しないため、決定部３０３は処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０２４９】
図５０は、実施例２において生成されたデータフロー情報を示す図である。決定部３０３は、このように決定されたデータフロー情報に基づいて、処理プログラムをサーバｎ１及びｎ３に送信する。更に、決定部３０３は、処理サーバｎ１及びｎ３に、処理プログラムに対応する決定情報を送信することによって、データ受信と処理実行とを指示する。【０２５０】
図５１は、実施例２において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得されたデータに対しＭｙＪｏｂ１の処理を実行する。また、処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得されたデータに対し、ＭｙＪｏｂ２の処理を実行する。一方、処理サーバｎ３は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータに対しＭｙＪｏｂ２の処理を実行する。また、処理サーバｎ３は、データサーバｎ４の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータに対しＭｙＪｏｂ２の処理を実行する。
【実施例３】
【０２５１】
実施例３では、上述の第３実施形態の具体例を示す。実施例３における分散システム３５０の構成は実施例１と同様である（図３４参照）。また、実施例３におけるサーバ状態格納部３０６０の状態についても実施例１と同様である（図３５参照）。また、実施例３における入出力通信路情報格納部３０８０の状態についても実施例１と同様である（図３６参照）。【０２５２】
図５２は、実施例３におけるデータ所在格納部３０７０に格納される情報を示す図である。図５２によれば、処理対象データ（ＭｙＤａｔａＳｅｔ１）はファイルｄａ及びデータｄｂに分割され格納されている。ファイルｄａは、多重化されていない単一のファイルであり、サーバｎ２のディスクＤ２内に格納されている。一方、データｄｂはファイルｄｂ１及びファイルｄｂ２に２重化されており、ファイルｄｂ１はサーバｎ２のディスクＤ２に格納され、ファイルｄｂ２はサーバｎ４のディスクＤ４に格納されている。【０２５３】
マスタサーバ３００のサーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図３５、図３６及び図５２に示される状態である場合に、クライアント３６０によって処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用する処理プログラムの実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２５４】
モデル生成部３０１は、図５２のデータ所在格納部３０７０及び図３５のサーバ状態格納部３０６０から、処理対象データが格納されているデータサーバ３４０の識別子の集合として｛ｎ２、ｎ４｝を取得し、処理可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ３｝を取得する。モデル生成部３０１は、これら取得された各集合、図３５のサーバ状態格納部３０６０に格納されている情報、図３６の入出力通信路情報格納部３０８０に格納されている情報、及び、図５２のデータ所在格納部３０７０に格納されている情報に基づいて、モデル情報を生成する。【０２５５】
図５３は、第３実施例において生成されるモデル情報を示す図である。図５４は、図５３により示されるモデル情報から構築される概念モデルを示す図である。図５４で示される概念モデル上の各辺に付された値は、その通信路における現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）、又は、その辺の始点に対応する処理サーバにおける現在の単位時間当たりのデータ処理量の最大値（処理量制約条件の上限値）を示す。【０２５６】
決定部３０３は、図５３に示されるモデル情報に基づいて、ジョブの処理時間が最小となるように流量関数ｆを決定する。図５５Ａから図５５Ｇは、第３実施例における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。まず、決定部３０３は、図５３のモデル情報に基づいて図５５Ａに示されるネットワークモデルを構築する。このネットワークモデルでは、始点ｓが設定され、終点ｔが設定される。決定部３０３は、図５５Ｂに示されるように、経路（ｓ、ｄｂ、ｎ２、ｎ１、ｔ）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図５５Ｃに示されるネットワークの残余グラフを特定する。【０２５７】
決定部３０３は、図５５Ｃに示される残余グラフからフロー増加路を特定し、図５５Ｄに示されるように、経路（ｓ、ｄａ、ｎ２、ｎ３、ｔ）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図５５Ｅに示されるネットワークの残余グラフを特定する。【０２５８】
決定部３０３は、図５５Ｅに示される残余グラフからフロー増加路を特定し、図５５Ｆに示されるように、経路（ｓ、ｄｂ、ｎ４、ｎ３、ｔ）に１００ＭＢ／ｓのフローを与える。結果、決定部３０３は、図５５Ｇに示されるネットワークの残余グラフを特定する。【０２５９】
ここで、図５５Ｇに示されるようにこれ以上のフロー増加路は存在しないため、決定部３０３は処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０２６０】
図５６は、実施例３におけるデータフロー情報を示す図である。このようなデータフロー情報とデータ所在格納部３０７０に格納されているデータサイズの情報とに基づいて、決定部３０３は、２重化されているデータｄｂについて、各処理サーバ３３０が処理するデータを特定する。具体的には、決定部３０３は、データｄｂを経路情報に含むデータフロー情報（Ｆｌｏｗ１及びＦｌｏｗ３）を特定し、特定された各データフロー情報に設定されている単位処理量（５０ＭＢ／ｓ及び１００ＭＢ／ｓ）を、当該各データフロー情報の経路情報に含まれる処理サーバ３３０（ｎ１及びｎ３）毎に集計する。ここでは、処理サーバｎ１及びｎ３に関する各単位処理量が５０ＭＢ／ｓ及び１００ＭＢ／ｓとなる。決定部３０３は、データｄｂをその集計された処理サーバｎ１及びｎ３の各単位処理量の比（１：２）で分割し、分割データｄｂ（ｄｂ１；６ＧＢ×１／３＝２ＧＢ）とそれを格納するデータサーバｎ２とを対応付け、分割データｄｉ（ｄｂ２：６ＧＢ×２／３＝４ＧＢ）とそれを格納するデータサーバｎ４とを対応付ける。これにより、実施例３では、マスタサーバ３００は、処理サーバｎ１に、データサーバｎ２に格納されるファイルｄｂ１の０バイト目から２ギガバイト目までを処理させ、処理サーバｎ３に、データサーバｎ４に格納されるファイルｄｂ２の２ギガバイト目から６ギガバイト目までを処理させることを決定する。この情報は処理プログラムに対応する決定情報に含まれる。【０２６１】
図５７は、実施例３において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得されたデータの０バイト目から２ギガバイト目までに対し処理を実行する。処理サーバｎ３は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータの処理を実行する。処理サーバｎ３は、データサーバｎ４の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得されたデータの２ギガバイト目から６ギガバイト目までに対し処理を実行する。
【実施例４】
【０２６２】
実施例４では、上述の第４実施形態の具体例を示す。【０２６３】
図５８は、実施例４における分散システム３５０の構成を概念的に示す図である。実施例４における本分散システム３５０は、スイッチｓｗ、サーバｎ１からｎ４を有する。サーバｎ１からｎ４は、スイッチｓｗを介して相互に接続されている。サーバｎ１からｎ４は、状況に応じて処理サーバ３３０及びデータサーバ３４０として機能する。サーバｎ１からｎ４は、処理データ格納部３４２として、ディスクＤ１からＤ４をそれぞれ有する。実施例４では、サーバｎ１からｎ４のいずれか１つがマスタサーバ３００として機能する。サーバｎ１からｎ３は利用可能な処理実行部３３２としてｐ１からｐ３を有する。【０２６４】
図５９は、実施例４におけるサーバ状態格納部３０６０に格納される情報を示す図である。実施例４では、サーバｎ１からｎ３が利用可能な処理サーバ３３０であり、サーバｎ１からｎ３の各処理可能量は、５０ＭＢ／ｓ、５０ＭＢ／ｓ及び１００ＭＢ／ｓである。【０２６５】
図６０は、実施例４における入出力通信路情報格納部３０８０に格納される情報を示す図である。サーバｎ２のディスクＤ２及びサーバｎ４のディスクＤ４の各読み出し速度はそれぞれ１００ＭＢ／ｓである。サーバｎ２からスイッチｓｗへのデータ送信時の可用帯域及びサーバｎ４からスイッチｓｗへのデータ送信時の可用帯域は１００ＭＢ／ｓである。スイッチｓｗからサーバｎ１へのデータ送信時の可用帯域、スイッチｓｗからサーバｎ２へのデータ送信時の可用帯域、スイッチｓｗからサーバｎ３へのデータ送信時の可用帯域は１００ＭＢ／ｓである。【０２６６】
実施例４におけるデータ所在格納部３０７０の状態は、実施例１と同様である（図３７参照）。【０２６７】
マスタサーバ３００のサーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図５９、図６０及び図３７に示す状態である場合に、クライアント３６０によって処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用する処理プログラムの実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２６８】
マスタサーバ３００のモデル生成部３０１は、図３７のデータ所在格納部３０７０及び図５９のサーバ状態格納部３０６０から、処理対象データが格納されているデータサーバ３４０の識別子の集合として｛ｎ２、ｎ４｝を取得し、利用可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ２、ｎ３｝を取得する。モデル生成部３０１は、これら取得された各集合、図５９のサーバ状態格納部３０６０に格納されている情報、図６０の入出力通信路情報格納部３０８０に格納されている情報に基づいて、モデル上布を生成する。【０２６９】
図６１は、実施例４において生成されるモデル情報を示す図である。図６２は、図６１により示されるモデル情報から構築される概念モデルを示す図である。図６２で示される概念モデル上の各辺に付された値は、その通信路における現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）、又は、その辺の始点に対応する処理サーバにおける現在の単位時間当たりのデータ処理量の最大値（処理量制約条件の上限値）を示す。マスタサーバ３００の決定部３０３は、図６１のモデル情報に基づいてジョブの処理時間が最小となるように流量関数ｆを決定する。図６３Ａから６３Ｇは、実施例４における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。【０２７０】
決定部３０３は、図６１のモデル情報に基づいて図６３Ａに示されるネットワークモデルを構築する。このネットワークモデルでは、始点ｓが設定され、終点ｔが設定される。決定部３０３は、図６３Ｂに示されるように、経路（ｓ、Ｄ２、ＯＮ２、ｎ２、ｔ）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図６３Ｃに示されるネットワークの残余グラフを特定する。【０２７１】
決定部３０３は、図６３Ｃに示される残余グラフからフロー増加路を特定し、図６３Ｄに示されるように、経路（ｓ、Ｄ２、ＯＮ２、ｉ２ｓｗ、ｏ１ｓｗ、ｎ１、ｔ）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図６３Ｅに示されるネットワークの残余グラフを特定する。【０２７２】
決定部３０３は、図６３Ｅに示される残余グラフからフロー増加路を特定し、図６３Ｆに示されるように、経路（ｓ、Ｄ４、ＯＮ４、ｉ４ｓｗ、ｏ３ｓｗ、ｎ３、ｔ）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図６３Ｇに示されるネットワークの残余グラフを特定する。【０２７３】
ここで、図６３Ｇに示されるようにこれ以上のフロー増加路は存在しないため、決定部３０３は、処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０２７４】
図６４は、実施例４におけるデータフロー情報を示す図である。決定部３０３は、このように決定されたデータフロー情報に基づいて、処理プログラムを処理サーバｎ１からｎ３に送信する。更に、決定部３０３は、処理サーバｎ１からｎ３に、処理プログラムに対応する決定情報を送信することによって、データ受信と処理実行とを指示する。【０２７５】
図６５は、実施例４において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得したデータの処理を実行する。処理サーバｎ２は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ２は取得したデータの処理を実行する。処理サーバｎ３は、データサーバｎ４の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得したデータの処理を実行する。
【実施例５】
【０２７６】
実施例５では、上述の第５実施形態の具体例を示す。実施例５における分散システム３５０の構成は実施例１と同様である（図３４参照）。また、実施例５における入出力通信路情報格納部３０８０の状態についても実施例１と同様である（図３６参照）。実施例５におけるサーバ状態格納部３０６０の状態については実施例２と同様である（図４４参照）。実施例５におけるデータ所在格納部３０７０の状態については実施例２と同様である（図４５参照）。【０２７７】
図６６は、実施例５におけるジョブ情報格納部３０４０に格納される情報を示す図である。実施例５では、プログラムを実行する単位として、ジョブＭｙＪｏｂ１とジョブＭｙＪｏｂ２が投入されている。実施例５では、ジョブＭｙＪｏｂ１及びＭｙＪｏｂ２には最低単位処理量及び最大単位処理量が設定されていない。【０２７８】
マスタサーバ３００のジョブ情報格納部３０４０、サーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図６６、図４４、図３６及び図４５に示す状態である場合に、クライアント３６０によって、処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用するジョブＭｙＪｏｂ１及び処理対象データ（ＭｙＤａｔａＳｅｔ２）を使用するジョブＭｙＪｏｂ２の実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２７９】
モデル生成部３０１は、図６６のジョブ情報格納部３０４０から、現在実行が指示されているジョブの集合として｛ＭｙＪｏｂ１、ＭｙＪｏｂ２｝を取得し、更に、各ジョブについて、ジョブが使用するデータの名称、最低単位処理量及び最大単位処理量をそれぞれ取得する。更に、モデル生成部３０１は、図４５のデータ所在格納部３０７０及び図４４のサーバ状態格納部３０６０から、処理対象データを格納するデータサーバの識別子の集合として｛ｎ２、ｎ４｝を取得し、処理可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ３｝を取得する。また、モデル生成部３０１は、図４４のサーバ状態格納部３０６０から、各ジョブに関するサーバｎ１及びサーバｎ３の各処理可能量情報をそれぞれ得る。【０２８０】
モデル生成部３０１は、取得された各集合、図３６の入出力通信路情報格納部３０８０に格納された情報に基づいて、モデル情報を生成する。図６７は、実施例５において生成されるモデル情報を示す図である。実施例５で生成されるモデル情報には、各処理サーバｎ１及びｎ３の識別子が含まる行の次要素へのポインタに、各処理サーバｎ１及びｎ３の第２の識別子（ｎ１'及びｎ３'）が設定されている。また、各処理サーバｎ１及びｎ３の第２の識別子が含まれる行の次要素へのポインタに、各ジョブ（ＭｙＪｏｂ１、ＭｙＪｏｂ２）の終端を示す名称（ＭｙＪｏｂ１'、ＭｙＪｏｂ２'）が設定されている。【０２８１】
図６８は、図６７により示されるモデル情報から構築される概念モデルを示す図である。図６８で示される概念モデル上の各辺に付された値は、その通信路における現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）、又は、その辺の始点に対応する処理サーバにおける現在の単位時間当たりのデータ処理量の最大値（処理量制約条件の上限値）を示す。マスタサーバ３００の決定部３０３は、図６７のモデル情報に基づいてジョブの処理時間が最小となるように流量関数ｆを決定する。図６９Ａから６９Ｇは、実施例５における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。まず、決定部３０３は、図６７のモデル情報に基づいて図６９Ａに示されるネットワークモデルを構築する。このネットワークモデルでは、始点ｓ１及びｓ２が設定され、始点ｓ１（ＭｙＪｏｂ１）に対応する終点ｔ１が設定され、始点ｓ２（ＭｙＪｏｂ２）に対応する終点ｔ２が設定される。【０２８２】
決定部３０３は、図６９Ｂに示されるように、経路（ｓ１、ＭｙＪｏｂ１、ｎ２、ｎ１、ｎ１'、ｔ１）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図６９Ｃに示されるネットワークの残余グラフを特定する。【０２８３】
決定部３０３は、図６９Ｃに示される残余グラフからフロー増加路を特定し、図６９Ｄに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ２、ｎ３、ｎ３'、ｔ２）に５０ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図６９Ｅに示されるネットワークの残余グラフを特定する。【０２８４】
決定部３０３は、図６９Ｅに示される残余グラフからフロー増加路を特定し、図６９Ｆに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ４、ｎ３、ｎ３'、ｔ２）に１００ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図６９Ｇに示されるネットワークの残余グラフを特定する。【０２８５】
ここで、図６９Ｇに示されるようにこれ以上のフロー増加路は存在しないため、決定部３０３は処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０２８６】
図７０は、実施例５におけるデータフロー情報を示す図である。決定部３０３は、このように決定されたデータフロー情報に基づいて、処理プログラムを処理サーバｎ１及びｎ３に送信する。決定部３０３は、処理サーバｎ１及びｎ３に、処理プログラムに対応する決定情報を送信することによって、データ受信と処理実行とを指示する。【０２８７】
図７１は、実施例５において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２の処理データ格納部３４２内のデータを取得する。処理実行部ｐ１は取得されたデータの処理を実行する。処理サーバｎ３は、データサーバｎ２の処理データ格納部３４２内のデータ、及び、データサーバｎ４の処理データ格納部３４２内のデータを取得する。処理実行部ｐ３は取得された各データの処理を実行する。
【実施例６】
【０２８８】
実施例６では、上述の第６実施形態の具体例を示す。実施例６における分散システム３５０の構成は実施例１と同様である（図３４参照）。また、実施例６における入出力通信路情報格納部３０８０の状態についても実施例１と同様である（図３６参照）。実施例６におけるジョブ情報格納部３０４０の状態については実施例５と同様である（図６６参照）。また、実施例６におけるデータ所在格納部３０７０の状態は実施例２と同様である（図４５参照）。【０２８９】
図７２は、実施例６におけるサーバ状態格納部３０６０に格納される情報を示す図である。図７２に示されるように、サーバｎ１に関しては、処理に使用できるリソースが１残っており、ジョブＭｙＪｏｂ１及びＭｙＪｏｂ２の各処理に対して単位処理量（１ＭＢ／ｓ）当たり０．０１及び０．０２のリソースが利用される。一方、サーバｎ２に関しては、処理に使用できるリソースが０．５残っており、ジョブＭｙＪｏｂ１及びＭｙＪｏｂ２の処理に対して単位処理量（１ＭＢ／ｓ）当たり０．００２及び０．００４のリソースが利用される。【０２９０】
マスタサーバ３００のジョブ情報格納部３０４０、サーバ状態格納部３０６０、入出力通信路情報格納部３０８０、及び、データ所在格納部３０７０が、図６６、図７２、図３６及び図４５に示す状態である場合に、クライアント３６０によって、処理対象データ（ＭｙＤａｔａＳｅｔ１）を使用するジョブＭｙＪｏｂ１と、処理対象データ（ＭｙＤａｔａＳｅｔ２）を使用するジョブＭｙＪｏｂ２との実行を要求するための要求情報がマスタサーバ３００に送信されたと仮定する。以下、この状況における分散システム３５０の動作について説明する。【０２９１】
マスタサーバ３００のモデル生成部３０１は、図６６のジョブ情報格納部３０４０から、現在実行が指示されているジョブの集合として｛ＭｙＪｏｂ１、ＭｙＪｏｂ２｝を取得し、各ジョブに関し、ジョブが使用するデータの名称、最低単位処理量及び最大単位処理量をそれぞれ取得する。更に、モデル生成部３０１は、図４５のデータ所在格納部３０７０及び図７２のサーバ状態格納部３０６０から、処理対象データが格納されているデータサーバの識別子の集合として｛ｎ２、ｎ４｝を、処理可能な処理サーバ３３０の識別子の集合として｛ｎ１、ｎ３｝を取得する。また、モデル生成部３０１は、図７２のサーバ状態格納部３０６０から、サーバｎ１及びサーバｎ３に関する、リソース残量、処理可能量情報、及び、処理負荷情報をそれぞれ取得する。【０２９２】
モデル生成部３０１は、このように取得された各集合及び図３６の入出力通信路情報格納部３０８０に格納された情報に基づいて、モデル情報を生成する。図７３は、実施例６において生成されるモデル情報を示す図である。図７４は、図７３により示されるモデル情報から構築される概念モデルを示す図である。図７４で示される概念モデル上の各辺の値は、現在の単位時間当たりのデータ転送量の最大値（転送量制約条件の上限値）を示す。【０２９３】
マスタサーバ３００の決定部３０３は、図７３のモデル情報と、図７２のサーバ状態格納部３０６０から取得された、サーバｎ１及びｎ３に関するリソース残量、処理可能量情報及び処理負荷情報とに基づいて、ジョブの処理時間が最小となるように流量関数fを決定する。図７５Ａから図７５Ｉは、実施例６における最大流問題におけるフロー増加法による流量関数ｆの決定処理及びデータフロー情報の決定処理を概念的に示す図である。【０２９４】
まず、決定部３０３は、図７３のモデル情報の表を基に、図７５Ａに示されるネットワークモデルを構築する。このネットワークモデルでは、始点ｓ１及びｓ２が設定され、始点ｓ１に対応する終点ｔ１が設定され、始点ｓ２に対応する終点ｔ２が設定される。【０２９５】
ここで、決定部３０３は、図７５Ｂに示されるように、経路（ｓ１、ＭｙＪｏｂ１、ｎ２、ｎ１、ｔ１）に５０ＭＢ／ｓのフローを与える。結果、決定部３０３は、図７５Ｃに示されるネットワークの残余グラフを特定する。また、処理サーバｎ１のリソース残量は、ＭｙＪｏｂ１の５０ＭＢ／ｓのフローにより０．５（＝０．０１×５０）のリソースが利用されるため、０．５（＝１−０．５）となる。処理サーバｎ３のリソース残量は０．５のままである。【０２９６】
次に決定部３０３は、図７５Ｃに示される残余グラフからフロー増加路を特定し、図７５Ｄに示されるように、経路（ｓ２、ＭｙＪｏｂ２、ｎ４、ｎ３、ｔ２）に１００ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図７５Ｅに示されるネットワークの残余グラフを特定する。このとき、処理サーバｎ３のリソース残量は、ＭｙＪｏｂ２の１００ＭＢ／ｓのフローにより０．４（＝０．００４×１００）のリソースが利用されるため、０．１（＝０．５−０．４）となる。処理サーバｎ１のリソース残量は前回のまま０．５である。【０２９７】
決定部３０３は、図７５Ｅに示される残余グラフからフロー増加路を特定し、図７５Ｆに示されるように、経路（ｓ１、ＭｙＪｏｂ１、ｎ２、ｎ３、ｔ１）に５０ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図７５Ｇに示されるネットワークの残余グラフを特定する。このとき、処理サーバｎ３のリソース残量は、ＭｙＪｏｂ１の５０ＭＢ／ｓのフローにより０．１（＝０．００２×５０）のリソースが利用されるため、０（＝０．１−０．１）となる。処理サーバｎ１のリソース残量は前回のまま０．５である。【０２９８】
決定部３０３は、図７５Ｇに示される残余グラフからフロー増加路を特定し、図７５Ｈに示されるように、経路（ｓ１、ＭｙＪｏｂ２、ｎ４、ｎ１、ｔ２）に２５ＭＢ／ｓのフローを追加で与える。結果、決定部３０３は、図７５Ｉに示されるネットワークの残余グラフを特定する。このとき、処理サーバｎ１において、ＭｙＪｏｂ２の２５ＭＢ／ｓのフローにより０．５（＝０．０２×２５）のリソースが利用されるため、処理サーバｎ１及びｎ３のリソース残量はそれぞれ０及び０となる。【０２９９】
処理サーバｎ１及びｎ３のリソース残量が０になったので、頂点ｎ１又はｎ３を通過するフロー増加路は存在しない。これより、終点ｔ１又はｔ２に到達するフロー増加路は存在しないため、決定部３０３は処理を終了する。結果、得られた各経路及び各データ流量の組み合わせ情報がデータフロー情報となる。【０３００】
図７６は、実施例６におけるデータフロー情報を示す図である。決定部３０３は、このように決定されたデータフロー情報に基づいて、処理プログラムをサーバｎ１及びｎ３に送信する。更に、決定部３０３は、処理サーバｎ１及びｎ３に、処理プログラムに対応する決定情報を送信することによって、データ受信と処理実行とを指示する。【０３０１】
図７７は、実施例６において実施されるデータ送受信を概念的に示す図である。決定情報を受信した処理サーバｎ１は、データサーバｎ２及びｎ４の各処理データ格納部３４２内のデータをそれぞれ取得する。処理実行部ｐ１は取得された各データの処理をそれぞれ実行する。処理サーバｎ３は、データサーバｎ２及びｎ４の各処理データ格納部３４２内のデータをそれぞれ取得する。処理実行部ｐ３は取得された各データの処理をそれぞれ実行する。【０３０２】
なお、上述の説明で用いた複数のフローチャートでは、複数のステップ（処理）が順番に記載されているが、本実施形態で実行される処理ステップの実行順序は、その記載の順番に制限されない。本実施形態では、図示される処理ステップの順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態及び各変形例は、内容が相反しない範囲で組み合わせることができる。【０３０３】
上記の各実施形態及び各変形例の一部又は全部は、以下の付記のようにも特定され得る。但し、各実施形態及び各変形例が以下の記載に限定されるものではない。【０３０４】
（付記１）
データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成するモデル生成部と、
前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決め、該各辺の流量を満たす該概念モデル上の各経路を選択し、選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する決定部と、
を備える管理装置。【０３０５】
（付記２）
データの識別子と該データを格納する前記データ装置の識別子とを対応付けて格納するデータ所在格納部と、
ジョブにより扱われる複数のデータに関する情報を格納するジョブ情報格納部と、
を更に備え、
前記モデル生成部は、前記ジョブ情報格納部に格納される情報に基づいて、前記ジョブを示す頂点と、該ジョブを示す頂点から該ジョブにより扱われる複数データを格納する複数のデータ装置を示す複数の頂点へそれぞれ至る複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記決定部は、前記選択された各経路に含まれる各頂点に応じて、前記ジョブと、前記ジョブにより扱われる少なくとも１つのデータを格納する前記データ装置と、該少なくとも１つのデータを処理する前記処理装置との複数組み合わせを決定し、該複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
付記１に記載の管理装置。【０３０６】
（付記３）
複数の複製データに多重化された元データの識別子と、該各複製データを格納する各データ装置の識別子とを対応付けて格納するデータ所在格納部を更に備え、
前記モデル生成部は、前記元データを示す頂点と、前記元データを示す頂点から前記各複製データを格納する各データ装置を示す第１頂点へそれぞれ至る複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記決定部は、前記選択された各経路に含まれる各頂点に応じて、前記元データと、前記複数の複製データの少なくとも１つのデータを格納する前記データ装置と、前記複数の複製データの少なくとも１つを処理する前記処理装置との複数組み合わせを決定し、該複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
付記１又は２に記載の管理装置。【０３０７】
（付記４）
前記決定部は、前記選択された各経路に関する前記単位時間当たりのデータ処理量を、該各経路に対応する前記各対応関係にそれぞれ更に含ませ、データの識別子が共通する前記対応関係が複数生成された場合に、該複数の対応関係で示される各処理装置に、該共通の識別子が示す前記元データの、該対応関係に含まれる前記単位時間当たりのデータ処理量に応じた割合のデータ量を対象にしてそれぞれ処理させることを決定する、
付記３に記載の管理装置。【０３０８】
（付記５）
前記モデル生成部は、前記処理装置を示す前記第２頂点から、前記データ装置を示す前記第１頂点、データを示す頂点、又は、複数のデータを扱うジョブを示す頂点に至る辺であって、前記処理量制約条件が設定された１本以上の辺を更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
付記１から４のいずれか１つに記載の管理装置。【０３０９】
（付記６）
前記モデル生成部は、複数のデータをそれぞれ扱う各ジョブのための各始点頂点と、該各ジョブのための各終点頂点と、該各始点頂点から該各ジョブを示す頂点にそれぞれ至る複数の辺と、前記処理装置を示す前記第２頂点から該各終点頂点にそれぞれ至る複数の辺であって、前記処理量制約条件の上限値が前記処理装置が該各ジョブに対してそれぞれ実行可能な単位時間当たりの処理量にそれぞれ設定される複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
付記１から４のいずれか１つに記載の管理装置。【０３１０】
（付記７）
前記モデル生成部は、前記データ装置に格納されているデータが前記処理装置で受信されるまでに経由する中間機器を示す頂点を更に含むと共に、前記データ装置を示す前記第１頂点から前記データ装置の最寄りの中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が前記データ装置から該最寄りの中間機器への単位時間当たりの転送可能量に設定される辺、該中間機器を示す頂点から他の該中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が該中間機器から他の該中間機器への単位時間当たりの転送可能量に設定される辺、及び、前記処理装置の最寄りの中間機器を示す頂点から前記処理装置を示す前記第２頂点へ至る辺であって、前記転送量制約条件の上限値が該最寄りの中間機器から前記処理装置への単位時間当たりの転送可能量に設定される辺の少なくとも１つを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
付記１から６のいずれか１つに記載の管理装置。【０３１１】
（付記８）
前記モデル生成部は、前記中間機器を示す頂点を、前記中間機器への１以上の入力部を示す１以上の頂点と、前記中間機器の１以上の出力部を示す１以上の頂点と、データが転送され得る該入力部と該出力部との間を結ぶ１以上の辺とで構成する、
付記７に記載の管理装置。【０３１２】
（付記９）
前記各処理装置について、単位処理量当たりに費やされる処理負荷及び残負荷をそれぞれ格納するサーバ状態格納部を更に備え、
前記決定部は、前記概念モデルの各辺に設定された前記転送量制約条件及び前記処理量制約条件、並びに、前記各処理装置に関する前記処理負荷及び前記残負荷に応じた流量制限に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決める、
付記１から８のいずれか１つに記載の管理装置。【０３１３】
（付記１０）
前記モデル生成部は、前記概念モデルに含まれる少なくとも１つの辺に設定される前記転送量制約条件又は前記処理量制約条件には、データ転送量又はデータ処理量の下限値が更に設定される、
付記１から９のいずれか１つに記載の管理装置。【０３１４】
（付記１１）
前記各データ装置と前記各処理装置との間の入出力通信路情報を格納する通信路情報格納部と、
処理対象のデータの識別子と該データを格納する前記データ装置とを対応付けて格納するデータ所在格納部と、
前記各処理装置の単位時間当たりのデータ処理可能量を格納するサーバ状態格納部と、
を備える付記１から１０のいずれか１つに記載の管理装置と、
前記管理装置の前記決定部により決定される、前記処理装置と前記データ装置との各組み合わせに応じて、前記データ装置から取得されるデータを処理する前記処理装置と、
前記管理装置の前記決定部により決定される、前記処理装置と前記データ装置との各組み合わせに応じて、前記処理装置にデータを送信するデータ装置と、
を有する分散システム。【０３１５】
（付記１２）
少なくとも１つのコンピュータが、
データを格納する複数のデータ装置を示す複数の第１頂点と、データを処理する複数の処理装置を示す複数の第２頂点と、該各データ装置から該各処理装置への単位時間当たりのデータ転送可能量を上限値として含む各転送量制約条件がそれぞれ設定される、該各第１頂点から該各第２頂点に至る複数の第１辺と、該各処理装置の単位時間当たりのデータ処理可能量を上限値として含む各処理量制約条件がそれぞれ設定される、該各第２頂点から、該各第２頂点より後段の少なくとも１つの第３頂点に至る少なくとも１つの第２辺とを含む概念モデルを構築し得るモデル情報を生成し、
前記第１頂点、前記第２頂点、前記第１辺及び前記第２辺をそれぞれ含む前記概念モデル上の各経路に関する、該経路に含まれる該第１辺及び該第２辺に設定される前記転送量制約条件及び前記処理量制約条件に応じて実行可能な単位時間当たりのデータ処理量の合計を用いて、前記概念モデル上の各辺の流量を決定し、
前記各辺の流量を満たす前記概念モデル上の各経路を選択し、
前記選択された各経路に含まれる各頂点に応じて、前記処理装置と前記処理装置により処理されるデータを格納する前記データ装置との複数組み合わせを決定する、
ことを含む分散処理管理方法。【０３１６】
（付記１３）
前記少なくとも１つのコンピュータが、データの識別子と該データを格納する前記データ装置の識別子とを対応付けて格納するデータ所在格納部と、ジョブにより扱われる複数のデータに関する情報を格納するジョブ情報格納部と、を備え、
前記モデル情報の生成は、前記ジョブ情報格納部に格納される情報に基づいて、前記ジョブを示す頂点と、該ジョブを示す頂点から該ジョブにより扱われる複数データを格納する複数のデータ装置を示す複数の頂点へそれぞれ至る複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記複数組み合わせの決定は、前記選択された各経路に含まれる各頂点に応じて、前記ジョブと、前記ジョブにより扱われる少なくとも１つのデータを格納する前記データ装置と、該少なくとも１つのデータを処理する前記処理装置との複数組み合わせを決定し、
前記少なくとも１つのコンピュータが、
前記複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
ことを更に含む付記１２に記載の分散処理管理方法。【０３１７】
（付記１４）
前記少なくとも１つのコンピュータが、複数の複製データに多重化された元データの識別子と、該各複製データを格納する各データ装置の識別子とを対応付けて格納するデータ所在格納部を備え、
前記モデル情報の生成は、前記元データを示す頂点と、前記元データを示す頂点から前記各複製データを格納する各データ装置を示す第１頂点へそれぞれ至る複数の辺とを更にを含む前記概念モデルを構築し得る前記モデル情報を生成し、
前記複数組み合わせの決定は、前記選択された各経路に含まれる各頂点に応じて、前記元データと、前記複数の複製データの少なくとも１つのデータを格納する前記データ装置と、前記複数の複製データの少なくとも１つを処理する前記処理装置との複数組み合わせを決定し、
前記少なくとも１つのコンピュータが、
前記複数組み合わせの情報及び前記データ所在格納部に格納される情報に基づいて、前記処理装置と、前記処理装置により処理されるデータの識別子と、前記処理装置により処理されるデータを格納する前記データ装置との対応関係を示す情報を生成する、
ことを更に含む付記１２又は１３に記載の分散処理管理方法。【０３１８】
（付記１５）
前記複数組み合わせの決定は、前記選択された各経路に関する前記単位時間当たりのデータ処理量を、該各経路に対応する前記各対応関係にそれぞれ更に含ませ、データの識別子が共通する前記対応関係が複数生成された場合に、該複数の対応関係で示される各処理装置に、該共通の識別子が示す前記元データの、該対応関係に含まれる前記単位時間当たりのデータ処理量に応じた割合のデータ量を対象にしてそれぞれ処理させることを決定する、
付記１４に記載の分散処理管理方法。【０３１９】
（付記１６）
前記モデル情報の生成は、複数のデータをそれぞれ扱う各ジョブのための各始点頂点と、該各ジョブのための各終点頂点と、該各始点頂点から該各ジョブを示す頂点にそれぞれ至る複数の辺と、前記処理装置を示す前記第２頂点から該各終点頂点にそれぞれ至る複数の辺であって、前記処理量制約条件の上限値が前記処理装置が該各ジョブに対してそれぞれ実行可能な単位時間当たりの処理量にそれぞれ設定される複数の辺とを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
付記１２から１５のいずれか１つに記載の分散処理管理方法。【０３２０】
（付記１７）
前記モデル情報の生成は、前記データ装置に格納されているデータが前記処理装置で受信されるまでに経由する中間機器を示す頂点を更に含むと共に、前記データ装置を示す前記第１頂点から前記データ装置の最寄りの中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が前記データ装置から該最寄りの中間機器への単位時間当たりの転送可能量に設定される辺、該中間機器を示す頂点から他の該中間機器を示す頂点へ至る辺であって、前記転送量制約条件の上限値が該中間機器から他の該中間機器への単位時間当たりの転送可能量に設定される辺、及び、前記処理装置の最寄りの中間機器を示す頂点から前記処理装置を示す前記第２頂点へ至る辺であって、前記転送量制約条件の上限値が該最寄りの中間機器から前記処理装置への単位時間当たりの転送可能量に設定される辺の少なくとも１つを更に含む前記概念モデルを構築し得る前記モデル情報を生成する、
付記１２から１６のいずれか１つに記載の分散処理管理方法。【０３２１】
（付記１８）
前記モデル情報の生成は、前記中間機器を示す頂点を、前記中間機器への１以上の入力部を示す１以上の頂点と、前記中間機器の１以上の出力部を示す１以上の頂点と、データが転送され得る該入力部と該出力部との間を結ぶ１以上の辺とで構成する、
付記１７に記載の分散処理管理方法。【０３２２】
（付記１９）
少なくとも１つのコンピュータに、付記１２から１８のいずれか１つに記載の管理方法を実行させるプログラム。【０３２３】
（付記２０）
付記１９に記載のプログラムをコンピュータに読み取り可能に記録する記録媒体。【０３２４】
この出願は、２０１２年３月３０日に出願された日本出願特願２０１２−０８２６６５号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１Ａ】
2013145512.tif 000004
【図１Ｂ】
2013145512.tif 000005
【図２Ａ】
2013145512.tif 000006
【図２Ｂ】
2013145512.tif 000007
【図３】
2013145512.tif 000008
【図４】
2013145512.tif 000009
【図５】
2013145512.tif 000010
【図６】
2013145512.tif 000011
【図７】
2013145512.tif 000012
【図８】
2013145512.tif 000013
【図９Ａ】
2013145512.tif 000014
【図９Ｂ】
2013145512.tif 000015
【図１０】
2013145512.tif 000016
【図１１】
2013145512.tif 000017
【図１２】
2013145512.tif 000018
【図１３】
2013145512.tif 000019
【図１４】
2013145512.tif 000020
【図１５】
2013145512.tif 000021
【図１６】
2013145512.tif 000022
【図１７】
2013145512.tif 000023
【図１８】
2013145512.tif 000024
【図１９】
2013145512.tif 000025
【図２０】
2013145512.tif 000026
【図２１】
2013145512.tif 000027
【図２２】
2013145512.tif 000028
【図２３】
2013145512.tif 000029
【図２４】
2013145512.tif 000030
【図２５】
2013145512.tif 000031
【図２６】
2013145512.tif 000032
【図２７】
2013145512.tif 000033
【図２８】
2013145512.tif 000034
【図２９】
2013145512.tif 000035
【図３０】
2013145512.tif 000036
【図３１Ａ】
2013145512.tif 000037
【図３１Ｂ】
2013145512.tif 000038
【図３１Ｃ】
2013145512.tif 000039
【図３２】
2013145512.tif 000040
【図３３】
2013145512.tif 000041
【図３４】
2013145512.tif 000042
【図３５】
2013145512.tif 000043
【図３６】
2013145512.tif 000044
【図３７】
2013145512.tif 000045
【図３８】
2013145512.tif 000046
【図３９】
2013145512.tif 000047
【図４０Ａ】
2013145512.tif 000048
【図４０Ｂ】
2013145512.tif 000049
【図４０Ｃ】
2013145512.tif 000050
【図４０Ｄ】
2013145512.tif 000051
【図４０Ｅ】
2013145512.tif 000052
【図４０Ｆ】
2013145512.tif 000053
【図４０Ｇ】
2013145512.tif 000054
【図４１】
2013145512.tif 000055
【図４２】
2013145512.tif 000056
【図４３】
2013145512.tif 000057
【図４４】
2013145512.tif 000058
【図４５】
2013145512.tif 000059
【図４６】
2013145512.tif 000060
【図４７】
2013145512.tif 000061
【図４８Ａ】
2013145512.tif 000062
【図４８Ｂ】
2013145512.tif 000063
【図４８Ｃ】
2013145512.tif 000064
【図４８Ｄ】
2013145512.tif 000065
【図４８Ｅ】
2013145512.tif 000066
【図４８Ｆ】
2013145512.tif 000067
【図４９Ａ】
2013145512.tif 000068
【図４９Ｂ】
2013145512.tif 000069
【図４９Ｃ】
2013145512.tif 000070
【図４９Ｄ】
2013145512.tif 000071
【図４９Ｅ】
2013145512.tif 000072
【図４９Ｆ】
2013145512.tif 000073
【図４９Ｇ】
2013145512.tif 000074
【図４９Ｈ】
2013145512.tif 000075
【図４９Ｉ】
2013145512.tif 000076
【図４９Ｊ】
2013145512.tif 000077
【図５０】
2013145512.tif 000078
【図５１】
2013145512.tif 000079
【図５２】
2013145512.tif 000080
【図５３】
2013145512.tif 000081
【図５４】
2013145512.tif 000082
【図５５Ａ】
2013145512.tif 000083
【図５５Ｂ】
2013145512.tif 000084
【図５５Ｃ】
2013145512.tif 000085
【図５５Ｄ】
2013145512.tif 000086
【図５５Ｅ】
2013145512.tif 000087
【図５５Ｆ】
2013145512.tif 000088
【図５５Ｇ】
2013145512.tif 000089
【図５６】
2013145512.tif 000090
【図５７】
2013145512.tif 000091
【図５８】
2013145512.tif 000092
【図５９】
2013145512.tif 000093
【図６０】
2013145512.tif 000094
【図６１】
2013145512.tif 000095
【図６２】
2013145512.tif 000096
【図６３Ａ】
2013145512.tif 000097
【図６３Ｂ】
2013145512.tif 000098
【図６３Ｃ】
2013145512.tif 000099
【図６３Ｄ】
2013145512.tif 000100
【図６３Ｅ】
2013145512.tif 000101
【図６３Ｆ】
2013145512.tif 000102
【図６３Ｇ】
2013145512.tif 000103
【図６４】
2013145512.tif 000104
【図６５】
2013145512.tif 000105
【図６６】
2013145512.tif 000106
【図６７】
2013145512.tif 000107
【図６８】
2013145512.tif 000108
【図６９Ａ】
2013145512.tif 000109
【図６９Ｂ】
2013145512.tif 000110
【図６９Ｃ】
2013145512.tif 000111
【図６９Ｄ】
2013145512.tif 000112
【図６９Ｅ】
2013145512.tif 000113
【図６９Ｆ】
2013145512.tif 000114
【図６９Ｇ】
2013145512.tif 000115
【図７０】
2013145512.tif 000116
【図７１】
2013145512.tif 000117
【図７２】
2013145512.tif 000118
【図７３】
2013145512.tif 000119
【図７４】
2013145512.tif 000120
【図７５Ａ】
2013145512.tif 000121
【図７５Ｂ】
2013145512.tif 000122
【図７５Ｃ】
2013145512.tif 000123
【図７５Ｄ】
2013145512.tif 000124
【図７５Ｅ】
2013145512.tif 000125
【図７５Ｆ】
2013145512.tif 000126
【図７５Ｇ】
2013145512.tif 000127
【図７５Ｈ】
2013145512.tif 000128
【図７５Ｉ】
2013145512.tif 000129
【図７６】
2013145512.tif 000130
【図７７】
2013145512.tif 000131
【国際調査報告】
2013145512.tif 000132
2013145512.tif 000133