(57)【要約】【課題】  従来のMap/Reduce型の分散計算処理システムは、物理的な計算機を想定して構成されていたため、システム仮想化技術を用いた環境下における計算処理の分散配置方法や、仮想マシン間における通信方法については考慮されておらず、計算処理性能の低下を生じていた。【解決手段】  第１の計算処理を構成する複数の第２の計算処理を、１又は複数の物理マシン上で動作する複数の仮想マシンに分散配置する分散計算制御装置及び方法において、複数の第２の計算処理を複数の仮想マシンに分散配置する各種の配置パターンを検出し、配置パターンごとのコストを計算し、当該計算の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従って複数の第２の計算処理を複数の仮想マシンに分散配置するようにした。【選択図】  図７
2010218307.tif 000002
【特許請求の範囲】
【請求項１】
第１の計算処理を構成する複数の第２の計算処理を、１又は複数の物理マシン上で動作する複数の仮想マシンに分散配置する分散計算制御装置において、
前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する各種の配置パターンを検出する配置パターン検出部と、
前記配置パターンごとのコストを計算するコスト計算部と、
前記コスト計算部の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従って前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する分散配置部と
を備えることを特徴とする分散計算制御装置。
【請求項２】
前記コスト計算部は、
前記実行時間、消費電力及びＩ／Ｏ量の少なくとも１つを条件として、前記配置パターンごとのコストをそれぞれ計算する
ことを特徴とする請求項１に記載の分散計算制御装置。
【請求項３】
前記物理マシンは、
当該物理マシン上で動作する複数の前記仮想マシンが共有する共有メモリを備え、
前記分散配置部は、
前記コスト計算部の計算結果に基づいて、入出力関係を有する複数の前記第２の計算処理を同一の前記物理マシン上で動作する前記仮想マシンに配置すると共に、当該入出力関係を有する複数の前記第２の計算処理が配置された前記仮想マシン間のデータ転送を前記共有メモリを介して行うように対応する前記物理マシンを設定する
ことを特徴とする請求項１に記載の分散計算制御装置。
【請求項４】
前記分散配置部は、
前記コスト計算部の計算結果に基づいて、入出力関係がある複数の前記第２の計算処理を１つの計算処理に融合して、前記仮想マシンに配置する
ことを特徴とする請求項１に記載の分散計算制御装置。
【請求項５】
第１の計算処理を構成する複数の第２の計算処理を、１又は複数の物理マシン上で動作する複数の仮想マシンに分散配置する分散計算制御方法において、
前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する各種の配置パターンを検出する第１のステップと、
前記配置パターンごとのコストを計算する第２のステップと、
当該計算の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従って前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する第３のステップと
を備えることを特徴とする分散計算制御方法。
【請求項６】
前記第１のステップでは、
前記実行時間、消費電力及びＩ／Ｏ量の少なくとも１つを条件として、前記配置パターンごとのコストをそれぞれ計算する
ことを特徴とする請求項５に記載の分散計算制御方法。
【請求項７】
前記物理マシンは、
当該物理マシン上で動作する複数の前記仮想マシンが共有する共有メモリを備え、
前記第３のステップでは、
前記コスト計算部の計算結果に基づいて、入出力関係がある複数の前記第２の計算処理を同一の前記物理マシン上で動作する前記仮想マシンに配置すると共に、当該入出力関係がある複数の前記第２の計算処理が配置された前記仮想マシン間のデータ転送を前記共有メモリを介して行うように対応する前記物理マシンを設定する
ことを特徴とする請求項５に記載の分散計算制御方法。
【請求項８】
前記第３のステップでは、
入出力関係がある複数の前記第２の計算処理を１つの計算処理に融合して、前記仮想マシンに配置する
ことを特徴とする請求項５に記載の分散計算制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は分散計算制御装置及び方法に関し、システム仮想化機能を用いて分散計算処理を行う分散計算システムに適用して好適なものである。
【背景技術】
【０００２】
近年、Webデータや、センサからの入力データ、音声データ及び動画データなどの大量かつ大規模なデータの処理要求が増大している。このような大量かつ大規模なデータを処理するための処理システムとして、Map/Reduce型の分散計算システムが存在する（非特許文献１参照）。
【０００３】
Map/Reduce型の分散計算システムでは、計算ノード上に仮想的な分散ファイルシステムを設け、１つの計算処理を複数の計算ノードで分散して行う。このとき、かかる分散計算システムでは、目的とする計算処理をMap処理及びReduce処理の２つの計算処理に分けて定義する。Map処理は、＜key, value＞の組で表わされたデータ集合を別の＜key', value'＞の組の集合へ変換する処理である。またReduce処理は、Map処理の処理結果を集計する処理である。
【０００４】
Map処理及びReduce処理間の入出力データは、分散計算システム上に構築された分散ファイルシステムを通してやり取りされる。分散ファイルシステムに対する操作は、分散ファイルシステムの管理プログラムと、Map/Reduce処理を実行するデータ処理プログラムとの間の通信により行われる。Map/Reduce型の分散計算処理では、分散ファイルシステム上のデータをデータブロックと呼ばれる単位に分割し、これらのデータブロックに対してMap処理及びReduce処理を順次適用する。
【０００５】
このようなMap/Reduce型の分散計算システムによれば、各データブロックに対する一連の計算処理を複数の計算ノードで同時に分散して実行することが可能となる。各計算ノードに対する処理の配置は、基本的に処理の完了順に処理を計算ノードに割り当てることにより行われる。
【０００６】
一方、近年では、物理的なマシン（以下、これを物理マシンと呼ぶ）上で複数の仮想的なマシンを稼動させる技術が知られている。このような仮想化技術はシステム仮想化技術と呼ばれ、物理マシン上で動作する仮想的なマシンは仮想マシンと呼ばれる。仮想マシンは、当該仮想マシン上で動作するソフトウェアからは物理マシンと同様に見える。
【非特許文献１】J. Dean他，「MapReduce: Simplified Data Processing on Large Clusters」，In Proceedings of OSDI'04, 2004
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のMap/Reduce型の分散計算システムは、Map処理やReduce処理を実行する個々の計算ノードが物理マシンであることを想定している。このため従来のMap/Reduce型の分散計算システムでは、システム仮想化技術を用いた環境下における計算処理の分散配置方法や、仮想マシン間における通信方法については何らの考慮もされていない。この結果、従来のMap/Reduce型の分散計算システムでは、システム仮想化技術を用いた環境下においては、システム全体として計算処理性能が低下するという事態が生じていた。
【０００８】
本発明は以上の点を考慮してなされたもので、システム仮想化技術を用いた環境下における計算処理性能を向上させ得る分散計算制御装置及び方法を提案しようとするものである。
【課題を解決するための手段】
【０００９】
かかる課題を解決するため本発明においては、第１の計算処理を構成する複数の第２の計算処理を、１又は複数の物理マシン上で動作する複数の仮想マシンに分散配置する分散計算制御装置において、前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する各種の配置パターンを検出する配置パターン検出部と、前記配置パターンごとのコストを計算するコスト計算部と、前記コスト計算部の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従って前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する分散配置部とを備えることを特徴とする。
【００１０】
また本発明においては、第１の計算処理を構成する複数の第２の計算処理を、１又は複数の物理マシン上で動作する複数の仮想マシンに分散配置する分散計算制御方法において、前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する各種の配置パターンを検出する第１のステップと、前記配置パターンごとのコストを計算する第２のステップと、当該計算の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従って前記複数の第２の計算処理を前記複数の仮想マシンに分散配置する第３のステップとを備えることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、システム仮想化技術を用いた環境下における計算処理性能を向上させることができる。
【発明を実施するための最良の形態】
【００１２】
以下図面について、本発明の一実施の形態を詳述する。
【００１３】
（１）第１の実施の形態
図１において、１００は全体として本実施の形態による分散計算システムを示す。この分散計算システム１００は、分散計算制御ノード１０１、第１及び第２の分散計算ノード１０２，１０３並びにネットワーク１０４から構成される。なお、図１では分散計算ノードが２台（第１及び第２の分散計算ノード１０２，１０３）存在する場合について例示しているが、分散計算システム１００内に３以上の分散計算ノードが存在する場合であっても本発明を適用することができる。
【００１４】
分散計算制御ノード１０１は、ハードウェア１１０及び外部記憶装置１１１を備えて構成される。ハードウェア１１０は、ＣＰＵ（Central Processing Unit）１１０Ａ及び共有メモリ等の情報処理資源を備えており、このハードウェア１１０上で分散計算制御システム１１２が動作する。
【００１５】
分散計算制御システム１１２は、ハードウェア１１０を構成するＣＰＵ１１０Ａが外部記憶装置１１１に格納された対応するプログラムを実行することにより実現される機能であり、外部記憶装置１１１に格納された分散計算定義１１３を読み込み、当該分散計算定義１１３に基づいて第１及び第２の分散計算ノード１０２，１０３に対する計算処理の分散配置を行う。分散計算制御システム１１２は、本分散計算システム１００の特徴的な処理であるジョブ配置処理を実行するための機能であるジョブ配置処理部１１４を備える。
【００１６】
第１及び第２の分散計算ノード１０２，１０３は、ハードウェア１２０，１３０と、外部記憶装置１２１，１３１とを備えて構成される。ハードウェア１２０，１３０は、ＣＰＵ（Central Processing Unit）１２０Ａ，１３０Ａ及び共有メモリ１２０Ｂ，１３０Ｂ等の情報処理資源を備えており、このハードウェア１２０，１３０上でシステム仮想化機能１２２，１３２が動作する。
【００１７】
システム仮想化機能１２２，１３２は、ハードウェア１２０，１３０を構成するＣＰＵ１２０Ａ，１３０Ａが同じ分散計算ノード１０２，１０３内の外部記憶装置１２１，１３１に格納された対応するプログラムを実行することにより実現される機能である。そして第１の分散計算ノード１０２のシステム仮想化機能１２２上で仮想マシン１２３，１２４が動作し、これら仮想マシン１２３，１２４上で分散処理アプリケーション１２５，１２６が動作する。また第２の分散計算ノード１０３のシステム仮想化機能１３２上では仮想マシン１３４，１３５が動作し、これら仮想マシン１３４，１３５上で分散処理アプリケーション１３６，１３６が動作する。なお図１では、システム仮想化機能１２２，１３２上で動作する仮想マシンの数がそれぞれ２つである場合について例示しているが、システム仮想化機能１２２，１３２上で動作する仮想マシンの数が３以上である場合でも本発明を適用することができる。
【００１８】
同一の分散計算ノード（第１又は第２の分散計算ノード１０２，１０３）上で動作する仮想マシン１２３，１２４又は１３４，１３５間は、その第１又は第２の分散計算ノード１０２，１０３内の共有メモリ１２０Ｂ，１３０Ｂを利用した通信路１２７，１３７によって高速にデータ転送を行うことができる。一方、別の分散計算ノード上で動作する仮想マシン１２３，１２４又は１３４，１３５間は、ネットワーク１０４を介したより低速な通信路１４０を介してデータ転送が行われる。
【００１９】
図２は、従来の分散計算システム２００の構成例を示す。この分散計算システム２００は、分散計算制御ノード２０１と、第１〜第４の分散計算ノード２０２〜２０５とがネットワーク２０６を介して接続されることにより構成されている。
【００２０】
分散計算制御ノード２０１は、ハードウェア２１０及び外部記憶装置２１１を備えて構成され、ハードウェア２１０上で分散計算制御システム２１２が動作する。分散計算制御システム２１２は、ハードウェア２１０を構成するＣＰＵが外部記憶装置２１１に格納された対応するプログラムを実行することにより実現される機能であり、外部記憶装置２１１に格納された分散計算定義２１３を読み込み、第１〜第４の分散計算ノード２０２〜２０５に対する計算処理の分散配置を行う。
【００２１】
第１〜第４の分散計算ノード２０２〜２０５は、それぞれハードウェア２２０，２３０，２４０，２５０と外部記憶装置２２１，２３１，２４１，２５１から構成される。ハードウェア２２０，２３０，２４０，２５０は、ＣＰＵ、メモリ及び通信インタフェース等の情報処理資源から構成されており、これらのハードウェア２２０，２３０，２４０，２５０上でそれぞれ分散計算アプリケーション２２２，２３２，２４２，２５２が動作する。分散計算アプリケーション２２２，２３２，２４２，２５２間におけるデータ転送は、比較的低速のネットワーク２０６を利用した通信路２６０を介して行われる。
【００２２】
図３は、本発明が対象としている分散計算処理の定義を示す。分散計算処理は、Map処理３０１及びReduce処理３０２からなる。Map処理３０１は、複数の＜key, value＞の対を各々の分散計算ノード１０２，１０３上の外部記憶装置１２１，１３１に格納された分散ファイルシステムのデータブロックから入力し、＜key, 1＞の対を出力する。Reduce処理では、各々のkeyについて、その出現回数を集計し、＜key, 集計値＞を出力する。なお、以下においては、個々のMap処理３０１及びReduce処理を、適宜、単位計算処理と呼ぶものとする。
【００２３】
かかる一連の計算処理を、図２について上述した従来の分散計算システム２００において分散配置する場合の配置例を図５に示す。図５の例では、第１〜第４の分散計算ノード２０２〜２０５内のハードウェア２２０，２３０，２４０，２５０において個々のデータ５０１に対するMap処理５０２及び又はReduce処理５０３が実行され、最終的な結果であるデータ５０４が出力される。
【００２４】
この場合において、第１〜第４の分散計算ノード２０２〜２０５はそれぞれ独立した存在であるため、ハードウェア２２０，２３０，２４０，２５０間のデータ転送はネットワーク２０６を利用した低速な通信路２６０を介して行う必要がある。例えば図５において、「BLK#1」というデータ５０１に対する「MAP#1」というMAP処理５０３の処理結果と、「BLK#2」というデータ５０１に対する「MAP#2」というMAP処理５０３の処理結果とを「RED#1」というReduce処理で利用するためには、「MAP#2」というMAP処理５０３の処理結果を「RED#1」というReduce処理を実行するハードウェア（ハードウェア２２０，２３０，２４０，２５０のいずれか）に転送する必要がある。
【００２５】
一方、図４（Ａ）及び（Ｂ）は、図３に示す一連の計算処理を、本実施の形態による分散計算システム１００（図１）において分散配置する場合の配置例を示す。
【００２６】
図４（Ａ）は、「MAP#1」及び「MAP#2」という２つのMap処理４０２と、これに続く「RED#1」というReduce処理４０３とを同一のハードウェア１２０上で実行し、「MAP#3」及び「MAP#4」という２つのMap処理４０３と、これに続く「RED#2」というReduce処理４０４とを同一のハードウェア１３０上で実行するパターン（パターン＃１）を示す。
【００２７】
また図４（Ｂ）は、「MAP#1」及び「MAP#2」という２つのMap処理４０３と、これに続く「RED#1」というReduce処理４０４とを別々のハードウェア１２０，１３０上で実行し、「MAP#3」及び「MAP#4」という２つのMap処理４０３と、これに続く「RED#2」というReduce処理４０４とを別々のハードウェア１３０，１２０上で実行するパターン（パターン＃２）を示す。
【００２８】
図４（Ａ）のパターン（パターン＃１）では、Map処理４０３の処理結果をReduce処理４０４で利用する際のデータ転送を高速な通信路１２７（図１）を介して行うことができるのに対し、図４（Ｂ）のパターン（パターン＃２）では、Map処理４０３の処理結果をReduce処理４０４で利用する際のデータ転送を低速な通信路１４０（図１）を介して行うことが必要となる。
【００２９】
図６は、図１の分散計算制御システム１１２の具体的な構成を示す。この図６に示すように、分散計算制御システム１１２は、分散計算処理全体の制御を行うジョブ制御部６０１と、個別の単位計算処理の制御を行うタスク制御部６０２と、分散ファイルシステム上の個別データの管理を行うデータ管理部６０３と、分散ファイルシステムの論理データの管理を行うメタデータ管理部６０４とから構成される。
【００３０】
タスク制御部６０２及びデータ管理部６０３は、第１及び第２の分散計算ノード１０２，１０３上に複数存在する。ジョブ制御部６０１は、本分散計算システム１００の特徴的な処理であるジョブ配置処理を実行するジョブ配置処理部１１４を備える。ジョブ配置処理部１１４は、分散計算定義１１３を入力として個々の分散計算処理をどの仮想マシンに配置するかを計算し、計算結果に基づいてタスク制御部６０２を制御する。
【００３１】
ジョブ配置処理部１１４により実行されるジョブ配置処理の処理手順を図７に示す。ジョブ配置処理部１１４は、例えばユーザ操作等に応じてこの図７に示すジョブ配置処理を開始し、まず、ユーザにより入力設定された計算処理のフローグラフ（以下、これを処理フローグラフＧと呼ぶ）と、そのとき利用可能な仮想マシンの集合（以下、これを仮想マシン集合Ｍと呼ぶ）とを求める（ＳＰ１）。
【００３２】
なお、処理フローグラフＧは、既存のコンパイラ実装技術により求めることができる。ステップＳＰ１の処理により、例えば図４（Ａ）及び（Ｂ）に示すような処理フローグラフＧを得ることができる。また仮想マシン集合Ｍは、分散計算システム１００内に存在するすべての仮想マシンの情報を収集し、これら仮想マシンの中から利用可能な仮想マシンを抽出することにより求めることができる。
【００３３】
続いてジョブ配置処理部１１４は、処理フローグラフＧの各要素（単位計算処理）を、それぞれ仮想マシン集合Ｍに属するいずれかの仮想マシンにランダムに配置したパターン（以下、これを配置パターンｑと呼ぶ）の集合（以下、これを配置パターン集合Ｑと呼ぶ）を求める（ＳＰ２）。そしてジョブ配置処理部１１４は、このようにして得られた配置パターン集合Ｑの情報をハードウェア１１０（図１）内の図示しないメモリに保存する。
【００３４】
図８は、図４に示す一連の計算処理を図１の分散計算システム１００で実行する場合における配置パターン集合Ｑを示す。この配置パターン集合Ｑには、「MAP#1」〜「MAP#4」という４つのMap処理と、「RED#1」及び「RED#2」という２つのReduce処理とを、それぞれ「VM#1」〜「VM#4」という４つの仮想マシン１２３，１２４，１３３，１３４に分散配置した場合の全配置パターンｑが含まれる。
【００３５】
図８では、各行が個々の配置パターンｑを表しており、例えば、項番が「１」の配置パターンｑは、すべての単位計算処理（４つのMap処理及び２つのReduce処理のすべて）を「VM#1」という仮想マシン１２３に配置した配置パターンを表し、項番が「２」の配置パターンｑは、４つのMap処理及び１つのReduce処理（「RED#1」）を「VM#1」という仮想マシン１２３に配置し、もう１つのReduce処理（「RED#2」）を「VM#2」という仮想マシン１２４に配置した配置パターンを表す。
【００３６】
次いでジョブ配置処理部１１４は、上述の配置パターン集合Ｑを構成する各配置パターンｑについて、そのコスト合計値Ｃｑをそれぞれ計算する（ＳＰ３）。さらにジョブ配置処理部１１４は、かかるコスト合計値Ｃｑが最低となるような配置パターンｑを選択し（ＳＰ４）、この後、このジョブ配置処理を終了する。
【００３７】
以上のジョブ配置処理のステップＳＰ３におけるジョブ配置処理部１１４の具体的な処理内容を図９に示す。ジョブ配置処理部１１４は、ジョブ配置処理のステップＳＰ３に進むと、この図９に示すコスト計算処理を開始し、まず、ジョブ配置処理のステップＳＰ２において求めた配置パターン集合Ｑの情報をメモリから読み出す（ＳＰ１０）。
【００３８】
続いてジョブ配置処理部１１４は、配置パターン集合Ｑが空集合であるか否かを判定し（ＳＰ１１）、配置パターン集合Ｑが空集合である場合には（ＳＰ１１：ＹＥＳ）、このコスト計算処理を終了してジョブ配置処理に戻る。
【００３９】
これに対してジョブ配置処理部１１４は、かかる配置パターン集合Ｑが空集合でない場合には（ＳＰ１１：ＮＯ）、配置パターン集合Ｑから要素（配置パターンｑ）を１つ取り出し、その配置パターンｑを配置パターン集合Ｑから削除する。またジョブ配置処理部１１４は、その配置パターンｑにおける個々の単位計算処理がそれぞれ割り当てられた仮想マシンの集合（以下、これを割当て仮想マシン集合Ｐと呼ぶ）を求める。さらにジョブ配置処理部１１４は、上述のコスト合計値Ｃｑを「０」に初期化する（ＳＰ１２）。
【００４０】
続いてジョブ配置処理部１１４は、割当て仮想マシン集合Ｐが空集合か否かを判断する（ＳＰ１３）。そしてジョブ配置処理部１１４は、かかる割当て仮想マシン集合Ｐが空集合でない場合には（ＳＰ１３：ＮＯ）、割当て仮想マシン集合Ｐから要素ｐ（単位計算処理が割り当てられた仮想マシン）を１つ選択し、選択した仮想マシンを割当て仮想マシン集合Ｐから除去する。またジョブ配置処理部１１４は、その選択した仮想マシンに関するコストＣｐを計算し、得られたコストＣｐをコスト合計値Ｃｑに加算する（ＳＰ１４）。
【００４１】
続いてジョブ配置処理部１１４は、ステップＳＰ１３に戻り、この後、そのとき対象としている配置パターンｑの割当て仮想マシン集合Ｐが空集合となるまで、同様の処理を繰り返す（ＳＰ１３−ＳＰ１４−ＳＰ１３）。
【００４２】
そしてジョブ配置処理部１１４は、やがてそのとき対象としている配置パターンｑの割当て仮想マシン集合Ｐに含まれる各仮想マシンに対するコストＣｐをすべて合計したコスト合計値Ｃｑを得ることによりステップＳＰ１３において肯定結果を得ると（ＳＰ１３：ＹＥＳ）、その配置パターンｑのコスト合計値Ｃｑを記憶した後（ＳＰ１５）、ステップＳＰ１１に戻る。
【００４３】
またジョブ配置処理部１１４は、この後、ステップＳＰ１１において肯定結果を得るまで同様の処理を繰り返す（ＳＰ１１〜ＳＰ１５）。そしてジョブ配置処理部１１４は、やがてステップＳＰ１０において取得した配置パターン集合Ｑを構成するすべての配置パターンｑについて同様の処理を終えることによりステップＳＰ１１において肯定結果を得ると、このコスト計算処理を終了する。
【００４４】
なお、上述のコスト計算処理のステップＳＰ１５における個々の単位計算処理に関するコスト計算処理時には、最適化したい対象に応じて、適宜、条件を設定することができる。かかる条件としては、実行時間、消費電力及び又はＩ／Ｏ量などを適用することが考えられる。このような条件の一例を図１０に示す。条件欄１０００に示す条件にマッチする場合、その処理をその仮想マシンに割り当てたときのコストがコスト欄１００１に示すコストとして計算される。
【００４５】
この場合において、本実施の形態においては、Map処理と、当該Map処理の処理結果を利用するReduce処理とを同一のハードウェア１２０，１３０上で動作する仮想マシンに割り当てることを目的として、このような関係を有するMap処理及びReduce処理が、同一のハードウェア１２０，１３０上で動作する１又は複数の仮想マシンに分散配置されているときのコストが低く設定され（図１０の項番「１」参照）、かかる関係を有するMap処理及びReduce処理が、異なるハードウェア１２０，１３０上で動作する１又は複数の仮想マシンに分散配置されているときのコスト高く設定されている（図１０の項番「２」参照）。
【００４６】
この結果、図４（Ａ）の配置パターンには図１０の項番「１」の条件のみが該当するため、この配置パターンのコストは「１」と計算することができる。また図４（Ｂ）の配置パターンには図１０の項番「２」〜「５」の条件が該当するため、この配置パターンのコストは「１８」と計算することができる。よって、図４（Ａ）及び（Ｂ）の例の場合、ジョブ配置処理部１１４は、図７のステップＳＰ４において図４（Ａ）の配置パターンを選択することとなり、より高性能な分散配置を行うことが可能となる。
【００４７】
以上の観点より、本実施の形態の場合、コスト計算時の条件が登録された図１０に示すような条件テーブルが外部記憶装置１１１に格納されており、ジョブ配置処理部１１４は、この条件テーブルを参照して、コスト計算処理のステップＳＰ１５におけるコスト計算処理を実行する。
【００４８】
図１１は、コスト計算処理のステップＳＰ１５において実行される、そのとき対象としている配置パターンｑの割当て仮想マシン集合Ｐの要素ｐごとのコスト計算処理について、実行時間を条件とした場合の処理内容の一例を示す。
【００４９】
ジョブ配置処理部１１４は、図９について上述したジョブ配置処理のステップＳＰ１５に進むと、この図１１に示す要素コスト計算処理を開始し、上述のコストＣｐ及び後述する合計通信時間ｐｔをそれぞれ「０」に初期化する（ＳＰ２０）。
【００５０】
続いて、ジョブ配置処理部１１４は、そのとき対象としている仮想マシン集合Ｐの要素ｐ（単位計算処理が割り当てられた仮想マシン）の通信先となる仮想マシン（以下、これを通信先仮想マシンと呼ぶ）の集合（以下、適宜、これを通信先集合Ｄと呼ぶ）を求め（ＳＰ２１）、この通信先集合Ｄが空集合であるか否かを判断する（ＳＰ２２）。
【００５１】
そしてジョブ配置処理部１１４は、かかる判断において否定結果を得ると（ＳＰ２３）、通信先集合Ｄの要素ｄ（通信先仮想マシン）を１つ取り出し、その通信先仮想マシンを通信先集合Ｄから削除する。またジョブ配置処理部１１４は、そのとき対象としている単位計算処理が割り当てられた仮想マシン（以下、適宜、これを通信元仮想マシンと呼ぶ）と、その通信先仮想マシンとの間における通信時間ｔを合計通信時間ｐｔに加算する（ＳＰ２３）。
【００５２】
続いてジョブ配置処理部１１４は、ステップＳＰ２２に戻り、この後、そのとき対象としている通信元仮想マシンについての通信先集合Ｄが空集合となるまで、同様の処理を繰り返す（ＳＰ２２−ＳＰ２３−ＳＰ２２）。
【００５３】
そしてジョブ配置処理部１１４は、やがてそのとき対象としている通信元仮想マシンと各通信先仮想マシンとの間の通信時間ｔの合計値である合計通信時間ｐｔを得ることによりステップＳＰ２２において肯定結果を得ると（ＳＰ２２：ＹＥＳ）、そのとき取得した合計通信時間ｐｔと、分散計算定義１１３に含まれる図１０について上述した条件とに基づいて、そのとき対象としている割当て仮想マシン集合Ｐの要素ｐについてのコストＣｐを取得し（ＳＰ２４）、この後、コスト計算処理（図９）に戻る。
【００５４】
なお、コスト計算の条件が消費電力及びＩ／Ｏ処理の場合についても、図１１と同様のアルゴリズムによってコスト計算を行うことが可能である。
【００５５】
以上のように本実施の形態による分散計算システム１００では、個々の単位計算処理を割り当て可能な仮想マシンに分散配置した配置パターンをすべて求め、これら配置パターンｐについてそれぞれコストを計算し、最もコストが低い配置パターンｐを選択するようにしたことにより、Map処理及び当該Map処理の処理結果を使用するReduce処理を、同一の物理マシン（第１又は第２の分散計算ノード１０２，１０３）上で動作する仮想マシンに分散配置することができる。かくするにつき、分散計算システム１００における分散計算処理の処理性能を向上させることができる。
【００５６】
（２）第２の実施の形態
第１の実施の形態によれば、Map処理及び当該Map処理の処理結果を使用するReduce処理を同一の物理マシン上で動作する仮想マシンに分散配置することができる。
【００５７】
この場合において、同一の物理マシン上で動作する仮想マシン間は、共有メモリ１２０Ｂ，１３０Ｂ（図１）を利用した高速な通信路１２７（図１）を利用したデータ転送を行うことができるため、かかるMap処理の処理結果をReduce処理に転送する際、共有メモリ１２０Ｂ，１３０Ｂを利用した通信路１２７（図１）を介して行うことにより分散計算処理の高速化を図ることができる。
【００５８】
図１２は、このような観点に基づいてジョブ配置処理部１１４により実行される、仮想マシン間の通信路を設定する処理（以下、これを通信路設定処理と呼ぶ）の処理内容を示す。ジョブ配置処理部１１４は、この図１２に示す通信路設定処理を、外部記憶装置１１１（図１）に格納されている対応するプログラムに基づいて実行する。
【００５９】
すなわちジョブ配置処理部１１４は、図７について上述したジョブ配置処理を終了すると、この図１２に示す通信路設定処理を開始し、まず、かかるジョブ配置処理のステップＳＰ４において選択した配置パターンｑの割当て仮想マシン集合Ｐを求める（ＳＰ３０）。
【００６０】
続いてジョブ配置処理部１１４は、その割当て仮想マシン集合Ｐが空集合であるか否かを判断し（ＳＰ３１）、当該割当て仮想マシン集合Ｐが空集合でない場合には（ＳＰ３１：ＮＯ）、割当て仮想マシン集合Ｐの要素ｐ（単位計算処理が割り当てられた仮想マシン）を１つ選択して、その通信先集合Ｄを求める（ＳＰ３２）。またジョブ配置処理部１１４は、これと併せてその要素ｐを割当て仮想マシン集合Ｐから削除する。
【００６１】
続いてジョブ配置処理部１１４は、かかる通信先集合Ｄが空集合であるか否かを判断し（ＳＰ３３）、否定結果を得ると（ＳＰ３３：ＮＯ）、かかる通信先集合Ｄの要素ｄ（通信先仮想マシン）を１つ選択して（ＳＰ３４）、かかる通信先仮想マシンとステップＳＰ３２において選択した仮想マシン（通信元仮想マシン）とが同一のハードウェア１２０，１３０上で動作するか否かを判断する（ＳＰ３５）。この際、ジョブ配置処理部１１４は、その要素ｄを通信先集合Ｄから削除する。
【００６２】
ジョブ配置処理部１１４は、かかる判断において肯定結果（ＳＰ３５：ＹＥＳ）を得ると、これら通信元仮想マシン及び通信先仮想マシン間の通信路として共有メモリ１２０Ｂ，１３０Ｂを利用した通信路１２７を設定する（ＳＰ３６）。そしてジョブ配置処理部１１４は、この後、ステップＳＰ３３に戻る。
【００６３】
これに対してジョブ配置処理部１１４は、ステップＳＰ３５の判断において否定結果（ＳＰ３５：ＮＯ）を得ると、かかる通信元仮想マシン及び通信先仮想マシン間の通信路としてネットワーク１０４（図１）を利用した通信路１４０（図１）を設定する（ＳＰ３７）。そしてジョブ配置処理部１１４は、この後、ステップＳＰ３３に戻る。
【００６４】
そしてジョブ配置処理部１１４は、やがてステップＳＰ３２において選択した仮想マシン（通信元仮想マシン）の通信先集合Ｄのすべての要素ｄについて同様の処理を終えることによりステップＳＰ３３において肯定結果を得るとステップＳＰ３１に戻り、この後、ステップＳＰ３１以降を同様に処理する。
【００６５】
そしてジョブ配置処理部１１４は、やがてジョブ配置処理（図７）のステップＳＰ４において選択した配置パターンｑの割当て仮想マシン集合Ｐのすべての要素ｐについて同様の処理を終えることによりステップＳＰ３１において肯定結果を得ると（ＳＰ３１：ＹＥＳ）、この通信路設定処理を終了する。
【００６６】
以上のように本実施の形態によれば、同一ハードウェア１２０，１３０上で動作する仮想マシン間におけるデータ転送の通信路として共有メモリ１２０Ｂ，１３０Ｂを利用した通信路１２７を設定することができるため、分散計算処理の高速化を図ることができる。
【００６７】
（３）第３の実施の形態
第１の実施の形態によれば、Map処理及び当該Map処理の処理結果を使用するReduce処理を同一の物理マシン上で動作する仮想マシンに分散配置することができるが、このような入出力関係を有するMap処理及びreduce処理を同一の仮想マシンにおいて実行することによって、より一層と分散計算処理の高速化を図ることができる。
【００６８】
図１３は、かかる入出力関係を有するMap処理及びReduce処理を１つの仮想マシンにまとめて配置するジョブまとめ処理の処理手順を示すフローチャートである。ジョブ配置処理部１１４は、この図１３に示すジョブまとめ処理を、外部記憶装置１１１（図１）に格納されたプログラムに基づいて、例えば図７について上述したジョブ配置処理の終了後であって、図１２について上述した通信路設定処理の実行前に実行する。
【００６９】
すなわちジョブ配置処理部１１４は、かかるジョブ配置処理が終了すると、このジョブまとめ処理を開始し、まず、かかるジョブ配置処理のステップＳＰ４において選択した配置パターンｐにおいて、Map処理及び当該Map処理の処理結果を使用するReduce処理の組の集合（以下、これを関連処理集合Ｙと呼ぶ）を求め（ＳＰ４０）、その関連処理集合Ｙが空集合であるか否かを判断する（ＳＰ４１）。
【００７０】
ジョブ配置処理部１１４は、この関連処理集合Ｙの要素ｙ（Map処理及びReduce処理の組）を１つ選択し（ＳＰ４２）、その要素ｙについて、Map処理を実行する仮想マシンと、Reduce処理を実行する仮想マシンとが同一ハードウェア１２０，１３０上で動作するか否かを判断する（ＳＰ４３）。
【００７１】
そしてジョブ配置処理部１１４は、この判断において否定結果を得るとステップＳＰ４１に戻り、これに対して肯定結果を得ると、かかるMap処理及びReduce処理を融合可能であるか否かを判断する（ＳＰ４４）。
【００７２】
ジョブ配置処理部１１４は、この判断において否定結果を得るとステップＳＰ４１に戻り、これに対して肯定結果を得ると、かかるMap処理及びReduce処理を融合し、この融合により得られた一連のMap/Reduce処理をそれまでそのMap処理又はReduce処理が割り当てられていたいずれかの仮想マシンに再割り当てした後（ＳＰ４５）、ステップＳＰ４１に戻る。
【００７３】
この後、ジョブ配置処理部１１４は、ステップＳＰ４１において肯定結果を得るまで同様の処理を繰り返す（ＳＰ４１〜ＳＰ４５−ＳＰ４１）。そしてジョブ配置処理部は、やがて関連処理集合Ｙに属するすべての要素ｙについて同様の処理を実行し終えることによりステップＳＰ４１において肯定結果を得ると、このジョブまとめ処理を終了する。
【００７４】
以上のように本実施の形態によれば、Map処理及び当該Map処理の処理結果を使用するReduce処理を同一の仮想マシンにまとめて配置することができるため、より一層と分散計算処理の高速化を図ることができる。
【００７５】
（４）他の実施の形態
なお上述の第１〜第３の実施の形態においては、本発明を図１のように構成された分散計算システム１００に適用するようにした場合について述べたが、本発明はこれに限らず、この他種々の構成の分散計算システムに広く適用することができる。
【００７６】
また上述の第１〜第３の実施の形態においては、Map処理及びReduce処理を複数の仮想マシンに分散配置する各種の配置パターンを検出する配置パターン検出部と、配置パターンごとのコストを計算するコスト計算部と、コスト計算部の計算結果に基づいて、コストが最小となる配置パターンを選択し、当該配置パターンに従ってMap処理及びReduce処理を複数の仮想マシンに分散配置する分散配置部との３つの機能を１つのジョブ配置処理部１１４により実現するようにした場合について述べたが、本発明はこれに限らず、例えば分散計算制御ノード１０１を複数用意し、かかる３つの機能をこれら複数の分散計算制御ノード１０１に分散させるようにしてもよい。
【産業上の利用可能性】
【００７７】
本発明は、システム仮想化機能を用いて分散計算処理を行う種々の構成の分散計算システムに適用することができる。
【図面の簡単な説明】
【００７８】
【図１】第１〜第３の実施の形態による分散計算システムの全体構成を示すブロック図である。
【図２】従来の分散計算システムの構成例を示すブロック図である。
【図３】分散処理の定義例を示すフロー図である。
【図４】（Ａ）及び（Ｂ）は、図１の分散計算システムにおける計算処理の分散配置例を示すフローグラフである。
【図５】図２の分散計算システムにおける計算処理の分散配置例を示すフローグラフである。
【図６】分散処理システムの構成例を示すブロック図である。
【図７】ジョブ配置処理の処理手順を示すフローチャートである。
【図８】配置パターン集合の説明に供する図表である。
【図９】コスト計算処理の処理手順を示すフローチャートである。
【図１０】条件テーブルの構成例を示す概念図である。
【図１１】実行時間を条件とする要素コスト計算処理の処理手順を示すフローチャートである。
【図１２】通信路設定処理の処理手順を示すフローチャートである。
【図１３】ジョブまとめ処理の処理手順を示すフローチャートである。
【符号の説明】
【００７９】
１００……分散計算システム、１０１……分散計算制御ノード、１０２，１０３……分散計算ノード、１０４……ネットワーク、１１０，１２０，１３０……ハードウェア、１１０Ａ，１２０Ａ，１３０Ａ……ＣＰＵ、１１２……分散計算制御システム、１１３……分散計算定義、１１４……ジョブは一処理部、１２０Ｂ，１３０Ｂ……共有メモリ、１１１，１２１，１３１……外部記憶装置、１２２，１３２……システム仮想化機能、１２３，１２４，１３３，１３４……仮想マシン、３０１，４０２……Map処理、３０２，４０３……Reduce処理。
【図１】
2010218307.tif 000003
【図２】
2010218307.tif 000004
【図３】
2010218307.tif 000005
【図４】
2010218307.tif 000006
【図５】
2010218307.tif 000007
【図６】
2010218307.tif 000008
【図７】
2010218307.tif 000009
【図８】
2010218307.tif 000010
【図９】
2010218307.tif 000011
【図１０】
2010218307.tif 000012
【図１１】
2010218307.tif 000013
【図１２】
2010218307.tif 000014
【図１３】
2010218307.tif 000015