(57)【要約】【課題】  ジョブ内に複数回実行される集約処理が含まれている場合、ジョブを高速に処理し、過去に行ったことがある集約処理を効率的に実行する。【解決手段】  本発明は、資源管理ノードで集約処理を検出し、該集約処理を行うタスクを抽出し、タスクの入力データを有する計算ノードから取得したハッシュ値と実行ファイルを検索キーとして過去の計算結果を検索し、該当する計算結果がある場合は、該計算結果を保持する計算ノードで処理が終了したと見做して計算処理をスキップし、該当する計算結果がない場合は、タスクを実行する計算ノードを決定し、タスクを実行させる。計算ノードでは、資源管理ノードから割り当てられたタスクを実行し、該タスクの計算結果を一時記憶手段に格納する。ジョブが終了すると、検索キーに基づいて検索し、計算結果を保持している計算ノードから計算結果を取得して、該計算ノードと関連付けて該計算結果記憶手段に格納する。【選択図】  図６
2012242972.tif 000002
【特許請求の範囲】
【請求項１】
分散並列処理において、複数の計算ノードと、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、該複数の計算ノードから実行結果を入力して受け取り計算を行う資源管理ノードを有する集約処理システムであって、
前記資源管理ノードは、
ジョブの実行ファイルから集約処理を検出し、該集約処理を行うタスクを抽出する集約処理検出手段と、
前記タスクの入力データを有する計算ノードに対して該入力データのハッシュ値の計算を要求し、実行ファイルと共に取得するハッシュ値取得手段と、
前記ハッシュ値と実行ファイルを検索キーとして過去の計算結果が格納されている計算結果記憶手段を検索し、該当する計算結果がある場合は、該計算結果を保持する計算ノードで処理が終了したと見做して計算処理をスキップし、該当する計算結果がない場合は、タスクを実行する計算ノードを決定し、タスクを実行させるタスク管理手段と、
ジョブが終了すると、前記検索キーに基づいて前記計算結果記憶手段を検索し、計算結果を保持している計算ノードを特定し、該計算ノードから取得した計算結果を取得して、該計算ノードと関連付けて該計算結果記憶手段に格納する計算結果格納手段と、
を有し、
前記計算ノードは、
前記資源管理ノードからの要求により、前記入力データのハッシュ値を求めるハッシュ値計算手段と、
前記資源管理ノードから割り当てられた前記タスクを実行し、該タスクの計算結果を実行ファイル、入力データを関連付けて一時記憶手段に格納するタスク実行手段と、
前記ジョブが終了した時点で、前記資源管理ノードから要求があると、前記一時記憶手段から計算結果を読み出して該資源管理ノードに転送するデータ転送手段と、
を有することを特徴とする集約処理システム。
【請求項２】
前記計算ノードは、
前記資源管理ノードから集約処理の入力要求があると、当該計算ノードと同じ物理計算機内のデータノードから計算結果を取得し、集約処理の計算結果があることを該資源管理ノードに通知する手段を含み、
前記資源管理ノードは、
前記計算ノードから計算結果があることが通知されると、集約処理が終了したものと判断する手段を含む
請求項１記載の集約処理システム。
【請求項３】
前記資源管理ノードは、
前記タスクを実行した計算ノード以外の計算ノードの計算結果を前記データノードに転送するデータ格納手段を有し、
前記計算ノードと同じ物理計算機内のデータノードは、
データを格納するデータ記憶手段と、
前記資源管理ノードから転送された計算結果を前記データ記憶手段に格納する手段と、
を有する請求項１記載の集約処理システム。
【請求項４】
分散並列処理において、複数の計算ノードと、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、該複数の計算ノードから実行結果を入力して受け取り計算を行う資源管理ノードを有するシステムにおける集約処理方法であって、
前記資源管理ノードの集約処理検出手段が、ジョブの実行ファイルから集約処理を検出し、該集約処理を行うタスクを抽出する集約処理検出ステップと、
前記資源管理ノードのハッシュ値取得手段が、前記タスクの入力データを有する計算ノードに対して該入力データのハッシュ値の計算を要求するハッシュ値要求ステップと、
前記計算ノードのハッシュ値計算手段が、前記入力データのハッシュ値を求めるハッシュ値計算ステップと、
前記資源管理ノードの前記ハッシュ値取得手段が、前記計算ノードから取得したハッシュ値を実行ファイルと共に取得するハッシュ値取得ステップと、
前記資源管理ノードのタスク管理手段が、前記ハッシュ値と実行ファイルを検索キーとして過去の計算結果が格納されている計算結果記憶手段を検索し、該当する計算結果がある場合は、該計算結果を保持する計算ノードで処理が終了したと見做して計算処理をスキップし、該当する計算結果がない場合は、タスクを実行する計算ノードを決定し、タスクを実行させるタスク管理ステップと、
前記計算ノードのタスク実行手段が、前記資源管理ノードから割り当てられた前記タスクを実行し、該タスクの計算結果を実行ファイル、入力データを関連付けて一時記憶手段に格納するタスク実行ステップと、
前記資源管理ノードの計算結果格納手段が、ジョブが終了すると、前記検索キーに基づいて前記計算結果記憶手段を検索し、計算結果を保持している計算ノードを特定し、該計算ノードに計算結果を要求する計算結果要求ステップと、
前記計算ノードのデータ転送手段が、前記一時記憶手段から計算結果を読み出して前記資源管理ノードに転送するデータ転送ステップと、
前記資源管理ノードの計算結果格納手段が、前記計算ノードから取得した計算結果を取得して、該計算ノードと関連付けて該計算結果記憶手段に格納する計算結果格納ステップと、
を行うことを特徴とする集約処理方法。
【請求項５】
前記計算ノードにおいて、
前記資源管理ノードから集約処理の入力要求があると、当該計算ノードと同じ物理計算機内のデータノードから計算結果を取得し、集約処理の計算結果があることを該資源管理ノードに通知し、
前記資源管理ノードにおいて、
前記計算ノードから計算結果があることが通知されると、集約処理が終了したものと判断する
請求項４記載の集約処理方法。
【請求項６】
前記資源管理ノードにおいて、
前記タスクを実行した計算ノード以外の計算ノードの計算結果を前記データノードに転送し、
前記計算ノードと同じ物理計算機内のデータノードにおいて、
前記資源管理ノードから転送された計算結果をデータ記憶手段に格納する
請求項４記載の集約処理方法。
【請求項７】
分散並列処理において、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、複数の計算ノードから実行結果を入力して受け取り計算を行う資源管理ノードであって、
ジョブの実行ファイルから集約処理を検出し、該集約処理を行うタスクを抽出する集約処理検出手段と、
前記タスクの入力データを有する計算ノードに対して該入力データのハッシュ値の計算を要求し、実行ファイルと共に取得するハッシュ値取得手段と、
前記ハッシュ値と実行ファイルを検索キーとして過去の計算結果が格納されている計算結果記憶手段を検索し、該当する計算結果がある場合は、該計算結果を保持する計算ノードで処理が終了したと見做して計算処理をスキップし、該当する計算結果がない場合は、タスクを実行する計算ノードを決定し、タスクを実行させるタスク管理手段と、
ジョブが終了すると、前記検索キーに基づいて前記計算結果記憶手段を検索し、計算結果を保持している計算ノードを特定し、該計算ノードから取得した計算結果を取得して、該計算ノードと関連付けて該計算結果記憶手段に格納する計算結果格納手段と、
前記タスクを実行した計算ノード以外の計算ノードの計算結果を前記データノードに転送するデータ格納手段と、
を有することを特徴とする資源管理ノード。
【請求項８】
分散並列処理において、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、資源管理ノードからのタスク割り当てによりタスクを実行する計算ノードであって、
前記資源管理ノードからの要求により、前記入力データのハッシュ値を求めるハッシュ値計算手段と、
前記資源管理ノードから割り当てられた前記タスクを実行し、該タスクの計算結果を実行ファイル、入力データを関連付けて一時記憶手段に格納するタスク実行手段と、
前記ジョブが終了した時点で、前記資源管理ノードから要求があると、前記一時記憶手段から計算結果を読み出して該資源管理ノードに転送するデータ転送手段と、
を有することを特徴とする計算ノード。
【請求項９】
コンピュータを、
請求項７記載の資源管理ノードの各手段として機能させるための集約処理プログラム。
【請求項１０】
コンピュータを、
請求項８記載の計算ノードの各手段として機能させるための集約処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集約システム及び方法及び資源管理ノード及び計算ノード及び集約処理プログラムに係り、特に、過去に行ったジョブ中の集約処理がある場合に、当該集約処理をスキップするための集約システム及び方法及び資源管理ノード及び計算ノード及び集約処理プログラムに関する。
【背景技術】
【０００２】
分散処理フレームワークにおいて、PCクラスタ上にファイルを分割して保存する分散記憶装置を前提としたデータ解析基盤ソフトウェアがある。これは、図１に示すように、有向グラフの形式で動作フローを記述することで、互いに依存関係のない入力データに対して並列計算を行うプログラムを実行基盤とするものである。図１において、辺がデータの流れであり、頂点が行う処理内容を意味する。頂点上で実行される処理をタスクという。実行時は、分散ファイルシステムにアクセスし、入力ファイルを処理単位に分割する初期化処理を行い、分割したファイルが保存されているデータノードに近い計算ノードに、処理内容が記述されたプログラムを配置し、計算が完了したら結果を分散ファイルシステムに書き込むものである。なお、「計算ノード」とは、実際にタスクを実行する計算機を指す。
【０００３】
このような環境において、１つ前の頂点の処理結果を分割し、入力データとして処理する方法として、MapReduceを拡張し、ループ処理に特化させたシステムがある（例えば、非特許文献１、２参照）、Map処理、Reduceで記述されたプログラムを分散並列処理するシステム（例えば、特許文献1参照 ）や、非循環有向グラフ処理で記述されたプログラムを分散並列処理するシステム（例えば、特許文献２参照）がある。
【０００４】
また、各計算ノード間の通信量を測定し、ネットワーク全体に流れる通信量を削減し、計算機負荷及びネットワーク負荷を均等化するシステム（例えば、特許文献３参照）がある。
【０００５】
以下に従来の技術における分散並列処理キャッシュ処理を説明する。
【０００６】
図２は、従来技術の概略フローチャートである。
【０００７】
資源管理ノードがキャッシュを考慮しながら計算ノードにタスクを割り当て（ステップ２１０）、計算ノードが割り当てられたタスクを実行する（ステップ２２０）。タスクの実行結果を計算ノードに一時ファイルとして保存し（ステップ２３０）、ジョブが終了していない場合はステップ２１０に戻る。ジョブが終了したら計算ノードの一時ファイルを削除する。なお、ここで、「ジョブ」とは、動作フローを記述したプログラムが行う一連の処理を指し、各頂点で実行される処理と、データの流れを表現するデータフローで構成される。
【０００８】
上記の計算ノードにタスクを割り当てるステップ２１０の処理を図３に示す。
【０００９】
特許文献１の技術に基づいて資源管理ノードが次に実行すべきタスクを決定する（ステップ４１０）。次に、資源管理ノードが次に実行ジョブ中における再利用するデータの宣言を確認する（ステップ４２０）。ステップ４１０で選択したタスクの入力は再利用可能かを判定し、再利用可能であり、１回目の実行である場合は、計算結果を保持するノードで処理が終了したと見做し、計算をスキップし（ステップ４４０）、ステップ４１０の処理に戻る。一方、再利用ができない、または、２回目以降の実行である場合は、特許文献１の技術に基づいて実行する計算ノードを決定する（ステップ４６０）。
【００１０】
上記のステップ２３０では、図４に示すように、完了したタスクの計算結果を計算ノードの外部記憶装置（ローカルディスク）に保存する（ステップ６１０）。
【００１１】
最後に、ステップ２４０では、図５に示すように、完了したタスクの計算結果を計算ノードの外部記憶装置（ローカルディスク）に保存する（ステップ６１０）。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】United States Patent 7,650,331, System and method for efficient large-scale data processing (Map Reduce) Google, January 19, 2010.
【特許文献２】USPTO Applicaton #20080082644, Distributed Parallel Computing（Dryad)， Microsoft Corporation，September 29, 2006.
【特許文献３】特開2000-242609号公報．
【非特許文献】
【００１３】
【非特許文献１】HaLoop: Efficient Iterative Data Processing on Large Clusters, Yingyi Bu, Bill Howe, Magdalena Balazinska, Michael D. Ernst. In VLDB'10: The 36the International Conference on Very Large Data Bases, Singapore, 24-30, September, 2010.
【非特許文献２】Twister: A Runtime for Iterative MapReduce Jaliya Ekanayake, Hui Li, Bingjing Zhang, Thilina Gunarathne, Seung-Hee Bae, Judy Qiu, Geoffrey Fox, Twister: A Runtime for Iterative MapReduce. The first International Workshop on MapReduce and its Applications (MAPREDUCE'10) - HPDC2010.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、上記特許文献１，２，３、非特許文献１，２のシステムのよい箇所を組み合わせたシステムを構築した場合でも、以下のような問題がある。
【００１５】
過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合であっても、複数の計算ノードから入力を受け取り、計算を行うような処理の実行時間は以前の実行時間と同程度である。その原因としては、入力データが過去と一致している場合であっても、入力データを計算ノードに再転送し、再計算を行う必要があるためである。
【００１６】
また、ネットワークの入出力、ディスクの入出力が特定の計算ノードに集中し、輻輳が発生しうるという問題がある。
【００１７】
本発明は、上記の点に鑑みなされたもので、ジョブ内に複数回実行される集約処理が含まれている場合、ジョブを高速に処理すると共に、過去に行ったことがある集約処理を効率的に実行することが可能な分散並列処理における集約システム及び方法及び資源管理ノード及び計算ノード及び集約処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するため、本発明（請求項１）は、分散並列処理において、複数の計算ノードと、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、該複数の計算ノードから実行結果を入力して受け取り計算を行う資源管理ノードを有する集約処理システムであって、
前記資源管理ノードは、
ジョブの実行ファイルから集約処理を検出し、該集約処理を行うタスクを抽出する集約処理検出手段と、
前記タスクの入力データを有する計算ノードに対して該入力データのハッシュ値の計算を要求し、実行ファイルと共に取得するハッシュ値取得手段と、
前記ハッシュ値と実行ファイルを検索キーとして過去の計算結果が格納されている計算結果記憶手段を検索し、該当する計算結果がある場合は、該計算結果を保持する計算ノードで処理が終了したと見做して計算処理をスキップし、該当する計算結果がない場合は、タスクを実行する計算ノードを決定し、タスクを実行させるタスク管理手段と、
ジョブが終了すると、前記検索キーに基づいて前記計算結果記憶手段を検索し、計算結果を保持している計算ノードを特定し、該計算ノードから取得した計算結果を取得して、該計算ノードと関連付けて該計算結果記憶手段に格納する計算結果格納手段と、
を有し、
前記計算ノードは、
前記資源管理ノードからの要求により、前記入力データのハッシュ値を求めるハッシュ値計算手段と、
前記資源管理ノードから割り当てられた前記タスクを実行し、該タスクの計算結果を実行ファイル、入力データを関連付けて一時記憶手段に格納するタスク実行手段と、
前記ジョブが終了した時点で、前記資源管理ノードから要求があると、前記一時記憶手段から計算結果を読み出して該資源管理ノードに転送するデータ転送手段と、
を有することを特徴とする。
【００１９】
また、本発明（請求項２）は、前記計算ノードにおいて、
前記資源管理ノードから集約処理の入力要求があると、当該計算ノードと同じ物理計算機内のデータノードから計算結果を取得し、集約処理の計算結果があることを該資源管理ノードに通知する手段を含み、
前記資源管理ノードにおいて、
前記計算ノードから計算結果があることが通知されると、集約処理が終了したものと判断する手段を含む。
【００２０】
また、本発明（請求項３）は、前記資源管理ノードにおいて、
前記タスクを実行した計算ノード以外の計算ノードの計算結果を前記データノードに転送するデータ格納手段を有し、
前記計算ノードと同じ物理計算機内のデータノードは、
データを格納するデータ記憶手段と、
前記資源管理ノードから転送された計算結果を前記データ記憶手段に格納する手段と、を有する。
【発明の効果】
【００２１】
上記のように、過去に行ったジョブの入力一部を変更し、再度同じジョブを行う場合に、複数の計算ノードから実行結果を入力として受け取り計算を行うような集約処理を効率的に実行することができる。これにより、１つのジョブの中に集約処理が複数存在する場合において、ある集約処理の入力ファイルのキー{入力ファイルのハッシュ値＋バイナリ}による検索結果が集約処理の入力ファイル全てに対してヒットした場合は計算をスキップすることができる。また、集約処理を行う計算ノードにおけるネットワークの入出力回数及びディスクの入出力回数を削減することができる。
【図面の簡単な説明】
【００２２】
【図１】有向グラフ形式の動作フローである。
【図２】従来技術の概略フローチャートである。
【図３】図２のＳ２１０を詳細化したフローチャートである。
【図４】図２のＳ２３０を詳細化したフローチャートである。
【図５】図２のＳ２４０を詳細化したフローチャートである。
【図６】本発明の一実施の形態におけるシステム構成図である。
【図７】本発明の一実施の形態における概略フローチャートである。
【図８】本発明の一実施の形態における図７のＳ３１０の詳細化フローチャートである。
【図９】本発明の一実施の形態における図７のＳ３２０の詳細化フローチャートである。
【図１０】本発明の一実施の形態における図９のＳ６４０ｎｏ詳細化フローチャートである。
【図１１】本発明の一実施の形態における図１０のＳ７１０の詳細化フローチャートである。
【図１２】本発明の一実施の形態における図７のＳ３５０の詳細化フローチャートである。
【図１３】本発明の一実施の形態における全体動作のシーケンスチャートである。
【発明を実施するための形態】
【００２３】
以下図面と共に、本発明の実施の形態を説明する。
【００２４】
図６は、本発明の一実施の形態におけるシステム構成を示す。
【００２５】
同図に示すシステムは、資源管理ノード１０と複数の物理計算機２０から構成される。
【００２６】
資源管理ノード１０は、集約処理検出部１１、タスク管理部１２、検索部１３、ノード管理ＤＢ１４から構成され、タスク管理部１２、検索部１３には計算結果記憶部１が接続されている。計算結果記憶部１は、計算ノードに対応する計算結果、タスク実行に必要な入力データのハッシュ値、実行ファイルの組が格納され、ローカルディスクまたはメモリとして保持される。本実施の形態では、計算結果記憶部１はローカルディスク（外部記憶装置）として説明する。また、ノード管理ＤＢ１４には、物理計算機毎に計算ノードの識別情報及び当該計算ノードが有するタスクの入力データの識別情報、及び、データノードの識別情報を格納している。
【００２７】
物理計算機２０は、実際にタスクを実行する計算ノード２１、データを保存するデータノード２２を有する。計算ノード２１は、資源管理ノード１０からの要求によりハッシュ値を計算するハッシュ計算部２１１を有し、計算結果一時記憶部２と接続されている。当該計算結果一時記憶部２は、ローカルディスクまたはメモリとして保持される。本実施の形態ではローカルディスク（外部記憶装置）として説明する。データノードは、データ記憶部２２１を有する。計算ノード２１では、集約処理を行う。集約処理とは、他の計算ノードから転送された複数の入力ファイルを取得し、全部揃ったら計算を行い、計算結果を計算結果一時記憶部２に格納する。
【００２８】
図７は、本発明の一実施の形態における概略フローチャートである。
【００２９】
ステップ３１０）  資源管理ノード１０の集約処理検出部１１は、入力されたジョブから集約処理を検出する。当該処理の詳細は、図８にて後述する。
【００３０】
ステップ３２０）  資源管理ノード１０のタスク管理部１２は、タスクを計算ノード２１に割り当てる。当該処理の詳細は、図９にて後述する。
【００３１】
ステップ３３０）  計算ノード２１は、割り当てられたタスクを実行する。
【００３２】
ステップ３４０）  計算ノード２２１は、その計算結果を、実行ファイル、入力データと関連付けて計算結果一時記憶部２に格納すると共に、資源管理ノード１０に送出する。ジョブが終了した場合にはステップ３５０に移行し、終了していない場合はステップ３２０に移行する。
【００３３】
ステップ３５０）  資源管理ノード１０は、ジョブが終了すると、中間結果を再利用できるように、計算結果記憶部１のデータを永続化する。詳細な処理については図１２にて後述する。
【００３４】
次に、上記のステップ３１０の集約処理の検出処理について説明する。
【００３５】
図８は、本発明の一実施の形態における図７のＳ３１０の詳細化フローチャートである。
【００３６】
ステップ４１０）  資源管理ノード１０の集約処理検出部１１は、特許文献２の手法により、ジョブの実行ファイルから集約処理を検出する。当該特許文献２の手法では、プログラマによって記述された動作フローがプログラムに含まれており、動作フローの記述のうち、複数の入力をとる記述は限られているため、どのタスクが集約処理であるのかを判定することができる。
【００３７】
ステップ４２０）  集約処理検出部１１は、集約処理を行うタスクをマークし、メモリ（図示せず）に格納する。なお、本実施の形態では、当該マークが付与されたタスクはメモリに保存するものとして説明するが、ローカルディスクに保存してもよい。なお、当該マークは、資源管理ノード１０がタスクを計算ノード２１に割り当てる際に、そのタスクが集約処理であるかどうかの判断に用いられる。
【００３８】
次に、上記のステップ３２０のタスク割当処理について説明する。
【００３９】
図９は、本発明の一実施の形態における図７のＳ３２０の詳細化のフローチャートである。
【００４０】
ステップ６１０）  資源管理ノード１０のタスク管理部１２は、非特許文献２の手法を用いて次に実行すべきタスクを決定する。
【００４１】
ステップ６２０）  タスク管理部１２は、ステップ６１０で選択したタスクに基づいて、ノード管理ＤＢ１４から当該タスクの入力データを保持している計算ノードを検索し、当該計算ノード２１に対して、入力データのハッシュ値を計算するように要求する。これにより、当該計算ノード２１は、ハッシュ計算部２１１において、入力データのハッシュ値を計算し、資源管理ノード１０に返却する。
【００４２】
ステップ６３０）  資源管理ノード１０の検索部１３は、ステップ６２０で計算ノード２１から取得した入力データのハッシュ値と実行ファイルをキーとして、計算結果記憶部１から過去の計算結果の有無と場所を検索する。当該キーに該当する計算結果が計算結果記憶部１に存在するかを判定し、存在する場合は、ステップ６４０に移行し、存在しない場合はステップ６５０に移行する。
【００４３】
ステップ６４０）  タスク管理部１２は、計算結果が計算結果記憶部１に存在する場合は、計算結果を保持する計算ノード２１で処理が終了したものと見做し、計算処理をスキップし、ステップ６１０の処理に戻る。詳細は図１０にて後述する。
【００４４】
ステップ６５０）  計算結果が計算結果記憶部１に存在しない場合は、非特許文献２に基づいてタスクを実行する計算ノードを決定し、処理を終了する。
【００４５】
次に、上記の図９のステップ６４０の計算処理をスキップする場合の処理について説明する。
【００４６】
図１０は、本発明の一実施の形態における図９のＳ６４０の詳細化のフローチャートである。
【００４７】
ステップ７１０）  タスク管理部１２は、計算ノード２１に対して、今から実行するタスクの入力、実行ファイルから集約処理の入力（集約処理の入力ファイルの集合）を求める。集約処理の入力になるような計算結果が見つかった場合はステップ７２０に移行し、見つからない場合はステップ７４０に移行する。詳細な処理については図１１で後述する。
【００４８】
ステップ７２０）  計算ノード２１は、ステップ７１０で求めた計算結果を、計算結果を保持しているデータノード２２に要求する。これにより、データノード２２は、計算結果をデータ記憶部２２１から集約処理を実行する計算ノード２１へのコピーを開始する。但し、既に転送中の計算結果は転送しない。計算ノード２１は、複数の計算ノードから実行結果を入力として受け取り、集約処理に必要な入力が計算結果一時記憶部２にキャッシュされている計算結果にヒットしたかを判定し、ヒットした場合には、ステップ７３０に移行し、ヒットしない場合は当該処理を終了する。
【００４９】
ステップ７３０）  計算ノード２１は、ヒットした場合には、ヒットしたことをタスク管理部１２に通知し、タスク管理部１２は、ステップ７２０で開始したコピーを停止し、計算結果を保持している計算ノード２１で集約処理が終了したと見做し処理を終了する。
【００５０】
ステップ７４０）  タスク管理部１２は、ステップ７１０の処理において、集約処理の入力になるような計算結果が見つからない場合は、非特許文献２の手法に基づいて、タスクを実行する計算ノードを決定する。
【００５１】
上記のステップ７１０の処理について説明する。
【００５２】
図１１は、本発明の一実施の形態における図１０のＳ７１０の詳細化のフローチャートである。
【００５３】
ステップ８１０）  タスク管理部１２は、資源管理ノード１０が実行するタスクの入力データを保持するデータノード２２に対して入力データのハッシュ値を問い合わせる。
【００５４】
ステップ８２０）  データノード２２は、ハッシュ計算部２２２においてハッシュ値を計算し、タスク管理部１２に返却する。
【００５５】
ステップ８３０）  資源管理ノード１０の検索部１３は、入力データのハッシュ値、タスクに対する実行ファイルをキーとして計算結果記憶部１を検索し、対応する計算結果を取得する。キーに対応する計算結果が存在する場合、または、キーに対応する計算結果が存在せず、次の処理が集約処理である場合はステップ８４０に移行する。なお、集約処理であるか否かは、ステップ４２０で付与したマークがあるか否かで判定する。キーに対応する計算結果が存在せず、次の処理が存在しない場合、または、キーに対応する計算結果が存在し、かつ、次の処理が集約処理ではなく、次の処理が存在しない場合はステップ８５０に移行する。
【００５６】
ステップ８４０）  タスク管理部１２は、ステップ８３０で取得した計算結果が見つかったと見做し、処理を終了する。
【００５７】
ステップ８５０）  タスク管理部１２は、検索結果が見つからなかったと見做し、処理を終了する。
【００５８】
次に、図７のステップ３５０の処理について説明する。
【００５９】
図１２は、本発明の一実施の形態における図７のＳ３５０の詳細化のフローチャートである。
【００６０】
ステップ１０１０）  資源管理ノード１０の検索部１３は、計算結果記憶部１に保存した検索キー（入力データのハッシュ値と実行ファイル）に基づいて、ノード管理ＤＢ１４を検索し、当該検索キーに対応する計算結果を保持している計算ノードを求める。
【００６１】
ステップ１０２０）  タスク管理部１２は、集約処理を行ったノードの入力データのキー（入力データ群のハッシュ値と実行ファイル）と実行結果を保持している計算ノード２１とを関連付け、計算結果記憶部１に保存する。
【００６２】
ステップ１０３０）  集約処理以外の処理を行った計算ノードにある計算結果を、当該計算ノードと同じ物理計算機上で動作しているデータノードのデータ記憶部２２１に保存する。
【００６３】
図１３本発明の一実施の形態における全体動作のシーケンスチャートである。同図におけるステップ番号は前述のフローチャートのステップ番号に対応する。
【００６４】
上記のような処理を行うことにより、過去に行ったジョブの入力の一部を変更し、再度同じジョブを行う場合に、複数の計算ノードから実行結果を入力して受け取り計算を行うような処理（集約処理）を効率よく実行することができる。これにより、入力データが時系列に従って増えていくような処理を含む計算を高速に行うことができ、
（１）検索エンジンの更新が高速に行えるようになる；
（２）ユーザへのレコメンデーションが高速に更新できるようになる；
（３）ログ解析を高速に行うことができる。
【００６５】
なお、上記の資源管理ノード及び計算ノードの動作をプログラムとして構築し、資源管理ノード、計算ノードとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６７】
１  計算結果記憶部
２  計算結果一時記憶部
１０  資源管理ノード
１１  集約処理検出部
１２  タスク管理部
１３  検索部
１４  ノード管理ＤＢ
２０  物理計算機
２１  計算ノード
２２  データノード
２１１  ハッシュ計算部
２２１  データ記憶部
２２２  ハッシュ計算部
【図１】
2012242972.tif 000003
【図２】
2012242972.tif 000004
【図３】
2012242972.tif 000005
【図４】
2012242972.tif 000006
【図５】
2012242972.tif 000007
【図６】
2012242972.tif 000008
【図７】
2012242972.tif 000009
【図８】
2012242972.tif 000010
【図９】
2012242972.tif 000011
【図１０】
2012242972.tif 000012
【図１１】
2012242972.tif 000013
【図１２】
2012242972.tif 000014
【図１３】
2012242972.tif 000015