(57)【要約】【課題】  並列処理を効率的に実行させる並列処理管理プログラム、並列処理管理方法、及び、並列処理管理装置を提供する。【解決手段】  それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列管理処理をコンピュータに実行させるコンピュータ読み取り可能な並列処理管理プログラムであって、処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する。【選択図】図１４
2015075830.tif 000002
【特許請求の範囲】
【請求項１】
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列管理処理をコンピュータに実行させるコンピュータ読み取り可能な並列処理管理プログラムであって、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する並列処理管理プログラム。
【請求項２】
請求項１において、
前記制御工程では、さらに、前記算出したノードの総数が基準数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を、並列処理の対象とする並列処理管理プログラム。
【請求項３】
請求項２において、
前記制御工程では、さらに、前記処理対象ノードからの分岐数が基準分岐数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を並列処理の対象とする並列処理管理プログラム。
【請求項４】
請求項１乃至３のいずれかにおいて、
前記制御工程では、さらに、前記算出した開始ノードに連なるノードの総数と、前記処理済みのノード数とに基づいて、未処理のノード数を算出する並列処理管理プログラム。
【請求項５】
請求項１乃至４のいずれかにおいて、
前記制御工程では、前記各処理済みノード及び前記処理対象ノードの段数と分岐数とに基づいて、第１の段数のノード数と、前記第１の段数のノード各々からの分岐数の平均値との乗算によって算出される、前記第１の段数の１つ下位の第２の段数のノード数を累計し、前記開始ノードに連なるノードの総数を算出する並列処理管理プログラム。
【請求項６】
請求項１乃至５のいずれかにおいて、
前記制御工程では、前回の前記処理済みノードから、前記各処理済みノードの段数と分岐数とを受信し、次回、処理対象となるノードに、前記処理対象ノードの段数と分岐数とを付加した、前記各処理済みノード及び前記処理対象ノードの段数と分岐数とを送信する並列処理管理プログラム。
【請求項７】
請求項１乃至６のいずれかにおいて、
前記開始ノードからノード間の関連に基づいて、深さ優先でノードがたどられる並列処理管理プログラム。
【請求項８】
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列処理管理方法であって、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する並列処理管理方法。
【請求項９】
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列処理管理装置において、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御手段、を有する並列処理管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理管理プログラム、並列処理管理方法、及び、並列処理管理装置に関する。
【背景技術】
【０００２】
近年、ビジネスで扱う情報の範囲および量が飛躍的に増大し、次々と発生する大量のデータ（big data）を用いたデータ処理が行われる。
【０００３】
大量のデータの処理の方式には、例えば、バッチ（一括式）方式とインクリメンタル（順次）方式がある。バッチ方式は、蓄積されたデータ全体を対象として処理する方式である。また、インクリメンタル方式は、新たなデータ（以下、新着データと称する）が到着すると、当該データに関連するデータを対象として順次処理する方式である。大量データにおける、新着データを活用した分析処理には、インクリメンタル方式が有用である。
【０００４】
また、分散処理を行う並列計算のモデルとして、アクターモデルが知られる。大量データのインクリメンタル処理では、例えば、データを複数のディスクに分散して保持し、アクターモデルにしたがって、順次、関連するデータを処理する。アクターモデルでは、アクターと呼ばれる計算実体それぞれが、１）受け取ったメッセージを処理するとともに必要に応じて内部状態を更新する、２）他のアクターに有限個のメッセージを送信する、３）有限個の新たなアクターを生成する、という動作を行うことで、分散処理が行われる。
【０００５】
また、近年、ソーシャルデータ（ＳＮＳ：social networking service等）を対象とする処理が増加している。ソーシャルデータは、例えば、特徴として、一つのデータの要素（以下、ノードデータと称する）に関連して、他のノードデータを有する。関連するノードデータの数は、ノードデータに応じて異なる。ノードデータ間の関連を有するデータは、例えば、特許文献１に記載される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−１３４６８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
インクリメンタル方式で大量データを処理する場合、新着データの発生後、データ処理に要する時間を短縮するために、データ処理の量に応じて並列処理が適用される。
【０００８】
ソーシャルデータ等のノードデータ間の関連を有するデータの処理では、前述したとおり、関連するノードデータの数は、ノードデータに応じて異なる。また、データ処理では、起点となる開始ノードデータに続いて、開始ノードデータから分岐するノードデータ、及び、当該ノードデータから分岐するノードデータが順次たどられ、処理される。したがって、関連するノードデータの合計数が把握できず、データ処理の量の見積もりが困難である。
【０００９】
そこで、例えば、分岐するノードデータの処理に並列処理が適用される。しかし、並列処理が行われる場合、分岐数に応じたプロセスの生成とメッセージのコピーが発生し、リソースの消費量が増加する。したがって、並列度が膨大である場合、リソース枯渇が生じる。
【００１０】
１つの側面は、並列処理を効率的に実行させる並列処理管理プログラム、並列処理管理方法、及び、並列処理管理装置を提供することにある。
【課題を解決するための手段】
【００１１】
第１の側面は、それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列管理処理をコンピュータに実行させるコンピュータ読み取り可能な並列処理管理プログラムであって、処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する。
【発明の効果】
【００１２】
第１の側面によれば、並列処理を効率的に実行可能になる。
【図面の簡単な説明】
【００１３】
【図１】本実施の形態例における並列処理管理システムの構成を説明する図である。
【図２】図１の並列処理管理システムにおける並列処理管理装置の構成の一例を説明する図である。
【図３】図１の並列処理管理システムにおける並列処理管理装置のブロック図である。
【図４】要素が他の要素と関連を有するデータを説明する図である。
【図５】ノードデータ間で関連を有するデータを処理する場合の、処理対象のノードデータを有するツリー構造を表す図である。
【図６】ノードデータの処理を逐次処理する場合の例を説明する図である。
【図７】ノードデータの処理を並列処理する場合の例を説明する図である。
【図８】合計処理数に基づいた、データ処理に対する並行処理の適用例を説明する図である。
【図９】合計処理数に基づいた、データ処理のターンアラウンド時間の短縮例を説明する図である。
【図１０】図１の端末装置におけるデータ生成をトリガとして実行されるデータ処理を説明するフローチャート図である。
【図１１】インクリメンタル処理エンジンのデータ処理部の処理を説明するフローチャート図である。
【図１２】図１０、図１１のフローチャート図で説明したデータ処理における、並列処理管理装置間のメッセージの伝搬の概要を説明する。
【図１３】本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第１の図である。
【図１４】本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第２の図である。
【図１５】本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第３の図である。
【図１６】合計処理数の見積もり数の遷移を説明する図である。
【発明を実施するための形態】
【００１４】
以下、図面にしたがって本発明の実施の形態を説明する。ただし、本発明の技術的範囲はこれらの実施の形態に限定されず、特許請求の範囲に記載された事項とその均等物まで及ぶものである。
【００１５】
［並列処理管理システムの構成］
図１は、本実施の形態例における並列処理管理システムの構成を説明する図である。図１の並列処理管理システムは、例えば、相互に通信可能な複数の並列処理管理装置１０ａ〜１０ｎを有する。また、例えば、並列処理管理装置１０ａ〜１０ｎの各々は、インターネットを介して、複数の端末装置３０ａ〜３０ｃと接続する。並列処理管理装置１０ａ〜１０ｎの各々は、インクリメンタル処理エンジン２１（２１ａ〜２１ｎ）と、データ記憶部２０（２０ａ〜２０ｎ）とを有する。本実施の形態例における並列処理管理システムは、処理対象のデータを、複数の並列処理管理装置１０ａ〜１０ｎのデータ記憶部２０ａ〜２０ｎに、分散して保持する。インクリメンタル処理エンジン２１ａ〜２１ｎとデータ記憶部２０ａ〜２０ｎについては、図２にて説明する。
【００１６】
図１の並列処理管理システムは、新着データに応答して、アクターモデルに従って、新着データに関連する処理対象のデータを示すメッセージを、当該データを保持する並列処理管理装置１０ａ〜１０ｎに順次、伝搬して処理する。
【００１７】
アクターモデルは、並列計算モデルの１つであり、アクターとよばれる計算実体の集合により表現される。ここで、アクターは、例えば、並列処理管理装置１０ａ〜１０ｎが実行するインクリメンタル処理エンジン２１ａ〜２１ｎの各処理プロセスを示す。個々のアクター（処理プロセス）は、次のような振る舞いをする。アクター（処理プロセス）は、他のアクター（処理プロセス）に有限個のメッセージを送信する。アクター（処理プロセス）は、有限個の新たなアクター（処理プロセス）を生成する。アクター（処理プロセス）は、メッセージを受信するとそれを処理し、必要に応じて内部状態を更新する。
【００１８】
図１の並列処理管理システムに対応して説明する。端末装置３０ａ〜３０ｃは、例えば、Ｗｅｂサービス等においてユーザから入力されたデータを取得し、データを含むメッセージをいずれかの並列処理管理装置１０（１０ａ〜１０ｎ）に送信する。メッセージを受信した並列処理管理装置１０は、処理対象のデータがデータ記憶部２０に記憶されている場合、処理プロセスを生成してデータを処理すると共に、処理対象のデータに関連する１つまたは複数のデータの情報を含むメッセージを生成し送信する。一方、処理対象のデータがデータ記憶部２０に記憶されていない場合、並列処理管理装置１０は、データを保持する並列処理管理装置１０にメッセージを転送する。
【００１９】
［並列処理管理装置の構成］
図２は、図１の並列処理管理システムにおける並列処理管理装置１０の構成の一例を説明する図である。図２では、並列処理管理装置１０ａの構成を例示するが、他の並列処理管理装置１０ｂ〜１０ｎの構成も同様である。図２の並列処理管理装置１０ａは、例えば、入力装置１１、表示装置１２、通信インタフェース１３、プロセッサ１４、記憶媒体１５、メモリ１６を有する。各部は、バス１７を介して互いに接続される。入力装置１１は、例えば、キーボードやマウス等を示し、表示装置１２は、例えば、ディスプレイ等の表示画面を示す。また、並列処理管理装置１０は、通信インタフェース１３を介して、図１の端末装置３０ａ〜３０ｃ、及び、他の並列処理管理装置１０ｂ〜１０ｎとの通信を行う。
【００２０】
また、記憶媒体１５は、データ記憶部２０ａを有する。データ記憶部２０ａは、処理対象のデータ、及び、新着データを記憶する。図１において前述したとおり、本実施の形態例における並列処理管理システムは、データを、複数の並列処理管理装置のデータ記憶部２０ａ〜２０ｎに分散して保持する。また、メモリ１６には、本実施の形態例におけるインクリメンタル処理プログラム（並列処理管理プログラムに対応）２１ａが記憶される。インクリメンタル処理プログラム２１ａは、プロセッサ１４と協働して、本実施の形態例におけるデータ処理の並列管理処理を実現する。
【００２１】
［並列処理管理装置のブロック図］
図３は、図１の並列処理管理システムにおける並列処理管理装置のブロック図である。図２と同様にして、図３では、並列処理管理装置１０ａの構成を例示するが、他の並列処理管理装置１０ｂ〜１０ｎの構成も同様である。
【００２２】
図３の並列処理管理装置のインクリメンタル処理エンジン２１ａは、例えば、データ処理部２２、処理数見積もり部２３、メッセージ制御部２４を有する。データ処理部２２は、受信したメッセージに基づいて、データ記憶部２０ａからデータを読み出すと共に、読み出したデータに対して所定の処理を行い、処理結果をデータ記憶部２０ａに記憶する。また、処理数見積もり部２３は、データ記憶部２０ａを参照して取得した情報と、メッセージに含まれる情報とに基づいて、データ処理の合計量を示す合計処理数を見積もる。メッセージ制御部２４は、メッセージの生成、及び、送受信を制御する。
【００２３】
［要素間で関連を有するデータ］
本実施の形態例における並列処理管理システムが処理の対象とするデータは、例えば、データの要素が他の要素と関連を有するデータである。要素が他の要素と関連を有するデータとは、例えば、ソーシャルデータ（ＳＮＳ：social networking service等）である。ここで、要素間の関連を有するデータを説明する。
【００２４】
図４は、要素が他の要素と関連を有するデータを説明する図である。図４において、要素はユーザである。また、線で結ばれたユーザは、互いに友人登録しているユーザを示す。図４に示すように、ユーザＵ１〜Ｕ７は、ユーザＵ１を友達登録しているユーザである。また、ユーザＵ２１〜Ｕ２５は、ユーザＵ２を友達登録しているユーザである。他のユーザについても、同様である。
【００２５】
図４に示すように、ユーザによって、友達登録したユーザの数は異なる。したがって、ユーザの友達の友達の範囲は、ユーザによって異なる。例えば、範囲Ｇ１は、ユーザＵ１の友達の友達の範囲を示す。範囲Ｇ１は、ユーザＵ１の友達であるユーザＵ２〜Ｕ７、及び、ユーザＵ２〜Ｕ７の友達であるユーザＵ２１〜Ｕ２５、Ｕ３１、Ｕ４１、Ｕ４２、Ｕ６１、Ｕ７１、Ｕ７２を含む。したがって、例えば、ユーザの友達の友達の範囲を対象としてデータ処理を行う場合、処理対象の要素（ユーザ）の数は、ユーザによって異なる。
【００２６】
図４に示すような要素間で関連を有するデータを処理する場合、例えば、並列処理管理システムが、起点となる要素（図４では、ユーザＵ１）から要素間の関連に基づいてたどる要素の経路は、途中で分岐する。このため、ノード間で関連を有するデータを処理する場合の、処理対象の要素は、例えば、ツリー構造で表すことが可能である。以下、データの各要素を、ノードデータと称する。
【００２７】
図５は、ノードデータ間で関連を有するデータを処理する場合の、処理対象のノードデータを有するツリー構造を表す図である。図５のツリー構造におけるノードデータＡｎＡは、起点となる開始ノードデータである。また、開始ノードデータＡｎＡは、ノードデータＢｎＢ〜ＦｎＦそれぞれと関連を有する。さらに、ノードデータＢｎＢは、ノードデータＧｎＧ、ＨｎＨと関連を有する。他のノードデータＣｎＣ〜ＦｎＦも同様にして、１つまたは複数のノードデータと関連を有する。
【００２８】
並列処理管理システムは、例えば、開始ノードデータを起点として、関連を有するノードデータをツリー構造の深さ優先でたどり、ノードデータに対する処理を順次行う。即ち、図５の例において、並列処理管理システムは、点線の矢印で示すように、例えば、ノードデータＡｎＡ、ノードデータＢｎＢ、ノードデータＧｎＧ、ノードデータＨｎＨ、ノードデータＣｎＣの順にたどり、処理を行う。
【００２９】
図６は、ノードデータの処理を逐次処理する場合の例を説明する図である。図６の（Ａ）に示すツリー構造は、処理対象のノードデータが１５個であるツリー構造、図６の（Ｂ）に示すツリー構造は、処理対象のノードデータが９個であるツリー構造である。
【００３０】
図６の（Ａ）のツリー構造が有する１５個のノードデータｎＡ〜ｎＯを逐次処理する場合、並列処理管理システムは、例えば、点線の矢印で示す順に処理を行う。同様にして、図６の（Ｂ）のツリー構造が有する９個のノードデータｎＰ〜ｎＸを逐次処理する場合、並列処理管理システムは、例えば、点線の矢印で示す順に処理を行う。
【００３１】
ここで、データ処理に要する処理時間について説明する。図１、図２で示したとおり、本実施の形態例における並列処理管理システムは、ノードデータを、例えば、ディスク等の記憶媒体（データ記憶部２０ａ〜２０ｎ）に記憶する。ディスク等の記憶媒体に記憶されたノードデータに対する処理時間は、記憶媒体の入出力時間に相当する。即ち、ノードデータに対する処理時間は、いずれのノードデータに対しても、ほぼ一定である。したがって、図６の（Ａ）（Ｂ）に係るデータの処理時間は、ツリー構造が有するノードデータの総数に対応する。
【００３２】
具体的に、図６の（Ａ）のツリー構造が有する１５個のノードデータＡｎＡ〜ＯｎＯを逐次処理する場合、処理時間は「１５」となる。一方、図６の（Ｂ）のツリー構造が有する９個のノードデータＰｎＰ〜ＸｎＸを逐次処理する場合、処理時間は「９」となる。このように、開始ノードデータ（ノードデータＡｎＡ、ＰｎＰ）によって処理対象となるノードデータの数が異なるため、データ処理に要する時間が異なる。つまり、開始ノードデータＡｎＡに係るデータ処理と、開始ノードデータＰｎＰに係るデータ処理との間で、処理時間の不均衡が生じる。並列処理管理システムは、例えば、ノードデータから分岐する処理を並列化することによって、処理時間の不均衡を解消する。
【００３３】
［並列処理］
図７は、ノードデータの処理を並列処理する場合の例を説明する図である。図６の例と同様にして、図７の（Ａ）に示すツリー構造は、処理対象のノードデータが１５個であるツリー構造、図７の（Ｂ）に示すツリー構造は、処理対象のノードデータが９個であるツリー構造である。
【００３４】
図７の例では、並列処理管理システムは、ノードデータから分岐する各ノードデータの処理を並列処理の対象とする。具体的に、並列処理管理システムは、例えば、図７の（Ａ）において、点線の矢印で示すように、ノードデータＢｎＢ〜ＦｎＦの処理を並列化する共に、ノードデータＢｎＢ〜ＦｎＦから分岐する各ノードデータＧｎＧ〜ＯｎＯの処理を並列化する。この場合、並列度は８となり、処理時間は３となる。また、並列処理管理システムは、例えば、図７の（Ｂ）において、点線の矢印で示すように、ノードデータｎＰ〜ｎＸを並列化する。この場合、並列度は５となり、処理時間は３となる。
【００３５】
図７に示すように、一部のノードデータの処理を並列化することにより、処理対象となるノードデータの総数が異なる場合であっても、データ処理に要する処理時間の均一化（図７の例では、３）が可能になる。ただし、ノードデータの処理を並列化することにより、並列数に応じて、プロセスの生成、及び、送信メッセージの複写が生じ、リソースが消費される。したがって、分岐したノードデータの数が膨大であるとき、リソースの枯渇が生じる可能性がある。
【００３６】
そこで、本実施の形態例における並列処理管理装置は、データ処理における処理対象のノードデータ数を見積もり、処理時間の不均衡を抑制する。または、並列処理管理装置は、処理対象のノードデータに基づく残りのノードデータ数（残りの処理数）に基づいて、ターンアラウンド時間の平均値を短縮する。詳細については、図８、図９において説明する。
【００３７】
具体的に、本実施の形態例における並列処理管理装置は、処理対象ノードデータに対するデータの処理を行うと共に、各処理済みノードデータ及び処理対象ノードデータの段数と分岐数とに基づいて、開始ノードに連なるノードデータの総数を算出する。伝搬された処理済みのノードデータの情報と、処理対象のノードデータの情報とに基づくことにより、並列処理管理装置は、データの処理の途中であっても、開始ノードデータに連なるノードデータの総数、即ち、処理対象のノードデータ数（以下、合計処理数と称する）を見積もることができる。ノードデータの段数とは、例えば、開始ノードからの距離を示す。
【００３８】
そして、並列処理管理装置は、さらに、合計処理数が基準数を超える場合に、処理対象ノードから分岐するノードに対する処理を並列処理の対象とする。並列処理管理装置は、データ処理の合計処理数が多い場合に、一部のノードデータの処理を並列化の対象とすることによって、処理時間のデータ処理間の不均衡を抑制することができる。
【００３９】
図８は、合計処理数に基づいた、データ処理に対する並行処理の適用例を説明する図である。ツリー構造は、図６、図７の例と同様である。図８の例では、例えば、並列処理管理システムは、合計処理数が１０以上である場合に、３つ以上に分岐するノードデータの処理を並列化の対象とする。
【００４０】
図８の（Ａ）の例において、並列処理管理装置１０が、ノードデータＤｎＤを処理する際に、見積もった合計処理数は１０以上の値であるものとする。そして、ノードデータＤｎＤから３つのノードデータＪｎＪ〜ＬｎＬに分岐することから、並列処理管理装置１０は、３つのノードデータＪｎＪ〜ＬｎＬに対する処理を並列処理の対象とする。ノードデータＪｎＪ〜ＬｎＬの処理が並列化される場合、並列度は３、処理時間は１２となる。図８の（Ａ）に示すように、並列処理管理装置１０は、一部のノードデータの処理を並列処理の対象とすることにより、スループットを向上させる（１５→１２）。
【００４１】
一方、図８の（Ｂ）の例において、並列処理管理装置１０が見積もった合計処理数は、常に１０未満であるものとする。したがって、並列処理管理装置１０は、ノードデータＰｎＰ〜ＸｎＸの処理を、並列処理の対象としない。ノードデータＰｎＰ〜ＸｎＸが逐次処理される場合、処理時間は９となる。図８の（Ｂ）に示すように、並列処理管理装置１０は、処理時間が短いデータ処理に並列化を適用しないことにより、リソースの消費量を減少させ、リソースの圧迫を回避する。
【００４２】
図８に示すように、並列処理管理装置１０は、合計処理数に基づいて、データ処理に対する並列化の有無を判定することにより、処理時間の不均衡を改善することができると共に、リソースの枯渇を回避することができる。
【００４３】
図９は、合計処理数に基づいた、データ処理のターンアラウンド時間の短縮例を説明する図である。ターンアラウンド時間は、データ処理が発生してから終了するまでの時間を指す。図９では、合計処理数が１０のデータ処理Ｘと、合計処理数が３のデータ処理Ｙを例示する。また、図９の例において、並列処理管理システムは、複数のデータ処理を並列して処理しない。
【００４４】
図９の（Ａ）は、データ処理が、到着順にしたがって、順次スケジューリングされる場合の例である。データ処理Ｘは時刻０に開始し、時刻１０に終了する。このとき、データ処理Ｘのターンアラウンド時間は、１０（時刻０→時刻１０）である。また、データ処理Ｙは時刻１に発生する。しかし、データ処理Ｙは、データ処理Ｘの実行中には実行されないため、データ処理Ｘが終了した時刻１０に開始し、時刻１３に終了する。このとき、データ処理Ｙのターンアラウンド時間は、１２（時刻１→時刻１３）である。したがって、データ処理Ｘ、Ｙのターンアラウンド時間の平均は１１（＝（１０＋１２）／２）である。
【００４５】
一方、図９の（Ｂ）は、データ処理が、合計処理数に基づく残り処理時間にしたがって、順次スケジューリングされる場合の例である。残り処理時間は、算出した合計処理数が処理済みのノードデータの数を減算することによって算出される。図９の（Ｂ）の例では、並列処理管理システムは、残り処理時間が短いデータ処理を優先して実行することによって、ターンアラウンド時間の平均値を短縮する。
【００４６】
具体的に、図９の（Ｂ）において、データ処理Ｘは、時刻０に開始するものの、時刻１での、データ処理Ｘより残り処理時間の短いデータ処理Ｙの到着に応答して、処理が中断される。そして、データ処理Ｙが、時刻１に開始され時刻４に終了する。データ処理Ｙが終了すると、中断中のデータ処理Ｘが再開し、時刻１３に終了する。図９の（Ｂ）において、データ処理Ｘのターンアラウンド時間は、１３（時刻０→時刻１３）であって、データ処理Ｙのターンアラウンド時間は３（時刻１→時刻４）である。したがって、データ処理Ｘ、Ｙのターンアラウンド時間の平均は８（＝（１３＋３）／２）である。
【００４７】
図９に示すように、並列処理管理システムは、合計処理数に基づく残りの処理時間にしたがって、データ処理を実行制御することによって、データ処理のターンアラウンド時間の平均値を短縮することができる（１１→８）。
【００４８】
ここで、本実施の形態例における並列処理管理システムにおける処理の流れを説明する。
【００４９】
［フローチャート］
図１０は、図１の端末装置３０ａ〜３０ｃにおけるデータ生成をトリガとして実行されるデータ処理を説明するフローチャート図である。初めに、端末装置３０ａ〜３０ｃにおいて、Ｗｅｂサービス上の情報の入力等に基づいてデータが生成される（Ｓ１１）。続いて、端末装置３０ａ〜３０ｃは、生成したデータに基づいてメッセージを生成する（Ｓ１２）。具体的に、端末装置３０ａ〜３０ｃは、処理対象のデータ（以下、ノードデータと称する）を一意に識別するキー（ノードデータ名など）、及び、処理内容を表す関数名を含むメッセージを生成する。
【００５０】
次に、端末装置３０ａ〜３０ｃは、生成したメッセージを、ネットワークを経由して任意の並列処理管理装置１０に送信する（Ｓ１３）。端末装置３０ａ〜３０ｃは、生成したメッセージをいずれかの並列処理管理装置１０に送信する。メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１のメッセージ制御部２４は、メッセージを解析し、メッセージに含まれるキー情報に基づいて、処理対象のノードデータが自身のデータ記憶部２０に記憶されているか否かを判定する（Ｓ１４）。
【００５１】
処理対象のノードデータが自身のデータ記憶部２０に記憶されていない場合（Ｓ１４のＮＯ）、メッセージ制御部２４は、処理対象のノードデータをデータ記憶部２０に記憶する並列処理管理装置１０に、アドレスに基づいてメッセージを送信する（Ｓ１５）。そして、処理対象のノードデータをデータ記憶部２０に記憶する並列処理管理装置１０のインクリメンタル処理エンジン２１のデータ処理部２２は、メッセージに基づいてノードデータ処理を行う（Ｓ１６）。処理の詳細については、図１１のフローチャート図で後述する。
【００５２】
そして、工程Ｓ１６の処理の結果、１つ以上のメッセージが生成される場合（Ｓ１７のＹＥＳ）、並列処理管理装置１０のインクリメンタル処理エンジン２１のメッセージ制御部２４は、生成されたメッセージを、メッセージに含まれるキー情報に基づいて、ノードデータをデータ記憶部２０に記憶する並列処理管理装置１０に送信する（Ｓ１８）。
【００５３】
続いて、図１０のフローチャート図における各並列処理管理装置１０におけるインクリメンタル処理エンジン２１の処理（図１０のＳ１６）を、フローチャートに基づいて説明する。
【００５４】
図１１は、インクリメンタル処理エンジン２１のデータ処理部２２の処理を説明するフローチャート図である。インクリメンタル処理エンジン２１のデータ処理部２２は、端末装置３０ａ〜３０ｃ、または、他の並列処理管理装置１０のインクリメンタル処理エンジン２１から、メッセージを受信する（Ｓ２１）。
【００５５】
メッセージを受信すると、データ処理部２２は、メッセージを解析し、処理対象のノードデータを示すキー情報、及び、処理内容を表す関数名を取得する（Ｓ２２）。次に、データ処理部２２は、キー情報に基づいて、データ記憶部２０から処理対象のノードデータを読み出す（Ｓ２３）。続いて、データ処理部２２は、取得した関数名に基づいて関数を呼び出し、読み出したノードデータに対して処理を行う（Ｓ２４）。データ処理部２２は、処理の実行結果を、データ記憶部２０に書き込む（Ｓ２５）。
【００５６】
また、データ処理部２２は、メッセージに含まれる処理数見積もり情報に基づいて、開始ノードデータに連なるノードデータの総数を算出し、合計処理数の見積もりを行う（Ｓ２６）。合計処理数の見積もり処理の詳細については、図１３〜図１５で後述する。
【００５７】
そして、データ処理部２２は、算出した合計処理数に基づいて、処理対象のノードデータから分岐するノードデータに対する処理を、並列化の対象とするか否かを判定する（Ｓ２７）。続いて、データ処理部２２は、処理対象のノードデータから分岐するノードデータのメッセージを生成し、次に処理対象となるノードデータを保持する並列処理管理装置１０にメッセージを送信する（Ｓ２８）。このとき、後続のノードデータが並列処理の対象となる場合、データ処理部２２は、複数の並列処理管理装置１０にメッセージを送信する。
【００５８】
続いて、図１０、図１１のフローチャート図で説明したデータ処理における、並列処理管理装置１０間のメッセージの伝搬の概要を説明する。
【００５９】
［メッセージ伝搬の流れ］
図１２は、図１０、図１１のフローチャート図で説明したデータ処理における、並列処理管理装置１０間のメッセージの伝搬の概要を説明する図である。まず、並列処理管理装置１０ａは、端末装置３０ａ〜３０ｃから処理対象のノードデータの情報（ノードデータＡ）を含むメッセージＭ０を受信する（図１１のＳ２１）。
【００６０】
図１２の例において、並列処理管理装置１０ａのデータ記憶部２０ａは、ノードデータＡを保持していない。したがって、並列処理管理装置１０ａのインクリメンタル処理エンジン２１ａは、ノードデータＡを保持する並列処理管理装置１０ｂに、メッセージＭ１を送信する。このとき、メッセージＭ１は、処理対象のノードデータＡを示す情報（Ｋｅｙ＝Ａ）と、ノードデータに対する処理内容ｐ１とを含む。
【００６１】
なお、インクリメンタル処理エンジン２１は、例えば、ノードデータと、当該ノードデータを保持する並列処理管理装置１０との対応表を有し、対応表を参照することによって、ノードデータが保持される並列処理管理装置１０を検知してもよい。このとき、並列処理管理装置１０は、それぞれ、対応表を保持する。
【００６２】
または、インクリメンタル処理エンジン２１は、ノードデータを一意に識別可能なノードデータＩＤ等のハッシュ値を算出し、算出されたハッシュ値に基づいて、ノードデータを保持する並列処理管理装置１０を検知してもよい。
【００６３】
例えば、インクリメンタル処理エンジン２１は、ノードデータＩＤのハッシュ値を並列処理管理装置１０の台数で除算した余り値に基づいて、ノードデータを保持する並列処理管理装置１０を検知する。ノードデータＩＤのハッシュ値が「１０５」であって、並列処理管理装置１０の台数が「１０」である場合を例示する。この場合、ハッシュ値を並列処理管理装置１０の台数で除算した余り値「５（＝１０５÷１０）」の識別番号に対応する並列処理管理装置１０が、ノードデータＩＤのノードデータを保持する並列処理管理装置１０に該当する。即ち、識別番号５に対応する並列処理管理装置１０が保持するノードデータには、ハッシュ値が「１０」で除算した際の余りが値「５」になるようにノードデータＩＤが付与される。
【００６４】
図１２に戻り、並列処理管理装置１０ｂのインクリメンタル処理エンジン２１ｂは、受信したメッセージＭ１を解析し、処理対象のノードデータＡと、ノードデータＡに対する処理内容ｐ１とを特定する（Ｓ２２）。インクリメンタル処理エンジン２１ｂは、データ記憶部２０ｂにアクセスして、ノードデータＡ、及び、ノードデータＡの接続先（分岐先）の情報（ノードデータＢ〜ノードデータＦ）ｎ１を取得すると共に、ノードデータＡに対して処理ｐ１を実行する（Ｓ２３、Ｓ２４）。そして、インクリメンタル処理エンジン２１は、ノードデータＡに対する処理ｐ１の結果を、自身のデータ記憶部２０ｂに書き込む（Ｓ２５）。
【００６５】
また、インクリメンタル処理エンジン２１ｂは、処理数見積もり情報に基づいて、ノードデータＡに連なるノードデータの総数を算出し、合計処理数の見積もりを行う（Ｓ２６）。このとき、処理数見積もり情報は、ノードデータＡの段数、及び、ノードデータＡからの分岐数を有する。合計処理数の見積もり処理の詳細については、図１３〜図１５に基づいて後述する。
【００６６】
次に、インクリメンタル処理エンジン２１ｂは、ノードデータＡの分岐先であるノードデータＢ〜ノードデータＦの各メッセージを生成すると共に、次に処理対象となるノードデータＢを保持する並列処理管理装置１０ｃに、メッセージＭ２を送信する（Ｓ２８）。メッセージＭ２は、処理対象のノードデータＢを示す情報（Ｋｅｙ＝Ｂ）、ノードデータに対する処理内容ｐ１、残りのノードデータの情報（ノードデータＣ〜Ｆ）、処理数見積もり情報を含む。
【００６７】
同様にして、並列処理管理装置１０ｃのインクリメンタル処理エンジン２１ｃは、受信したメッセージＭ２を解析し、処理対象のノードデータＢと、ノードデータＢに対する処理内容ｐ１とを特定する（Ｓ２２）。また、インクリメンタル処理エンジン２１ｃは、データ記憶部２０ｃにアクセスして、ノードデータＢ、及び、ノードデータＢの接続先（分岐先）の情報（ノードデータＧ、ノードデータＨ）ｎ２を取得すると共に、ノードデータＢに対して処理ｐ１を実行する（Ｓ２３、Ｓ２４）。そして、インクリメンタル処理エンジン２１は、ノードデータＢに対する処理ｐ１の結果を、自身のデータ記憶部２０ｃに書き込む（Ｓ２５）。
【００６８】
また、インクリメンタル処理エンジン２１ｃは、処理数見積もり情報に基づいて、ノードデータＡに連なるノードデータの総数を算出し、合計処理数の見積もりを行う（Ｓ２６）。このとき、処理数見積もり情報は、ノードデータＡ、Ｂの段数、及び、ノードデータＡ、Ｂからの分岐数を有する。そして、インクリメンタル処理エンジン２１ｃは、ノードデータＢの分岐先であるノードデータＧ、ノードデータＨの各メッセージを生成すると共に、次に処理対象となるノードデータＧを保持する並列処理管理装置１０に、メッセージＭ３を送信する（Ｓ２８）。
【００６９】
そして、終了条件に達するまで、図１２にて説明した処理が繰り返される。終了条件は、例えば、データ処理の内容に対応して設定される。終了条件は、例えば、所定の変数が閾値以下になった場合や、開始ノードデータからの分岐数が閾値に達した場合等である。終了条件の情報は、例えば、各メッセージの処理内容（図１２の例では、処理ｐ１）に含まれる。
【００７０】
［具体例］
図１３は、本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第１の図である。具体例では、ノードデータＡｎＡを開始ノードデータとする１５のノードデータＡｎＡ〜ＯｎＯに対して処理を行う場合を例示する。また、図１３の例では、深さ優先で関連するノードデータが辿られる。
【００７１】
また、具体例における並列処理の判定条件は、「ノードデータ総数が１０以上且つ分岐数が３以上」である。並列処理管理装置１０は、例えば、ツリー構造のリーフ（末端）にたどり着いた後、ノードデータ総数の見積もり処理によって算出されたノードデータ総数が１０以上であって、処理対象のノードデータからの分岐数が３以上である場合に、処理対象のノードデータから分岐するノードデータに対する処理を並列化の対象とする。
【００７２】
［具体例：ノードデータＡ］
具体例において、開始ノードデータに対応するノードデータは、ノードデータＡｎＡである。図１１、図１２のフローチャート図で説明したとおり、並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＡｎＡに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【００７３】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＡｎＡにアクセスし、ノードデータＡｎＡの接続先のノードデータ（ノードデータＢｎＢ〜ノードデータＦｎＦ）を取得し、ノードデータＡｎＡからの分岐数「５」を取得する。したがって、インクリメンタル処理エンジン２１は、０段目Ｌ０から１段目Ｌ１への分岐数を「５」と想定し、１段目Ｌ１のノードデータ数「５」を算出する。また、開始ノードデータであるノードデータＡｎＡが属する０段目Ｌ０のノードデータ数は「１」である。
【００７４】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０と１段目Ｌ１のノードデータ数を加算し、合計ノードデータ数６（＝１＋５）を算出する。また、このとき、ノードデータＡｎＡが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「６」から処理済みノードデータ数「１」を減算し、未処理ノードデータ数「５（＝６−１）」を算出する。
【００７５】
続いて、インクリメンタル処理エンジン２１は、ノードデータＡｎＡの分岐先である５つのノードデータのメッセージを生成し、次に処理対象となるノードデータを保持する並列処理管理装置１０にメッセージを送信する（図１１のＳ２８）。前述したとおり、具体例において、深さ優先で順次ノードデータがたどられる。したがって、インクリメンタル処理エンジン２１は、ノードデータＢｎＢを保持する並列処理管理装置１０にメッセージを送信する。
【００７６】
［具体例：ノードデータＢ］
メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＢｎＢに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【００７７】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＢｎＢにアクセスし、ノードデータＢｎＢの接続先のノードデータ（ノードデータＧｎＧ、ノードデータＨｎＨ）、及び、ノードデータＢｎＢからの分岐数「２」を取得する。したがって、インクリメンタル処理エンジン２１は、１段目Ｌ１から２段目Ｌ２への分岐数を「２」と想定して、１段目Ｌ１のノードデータ数「５」と１段目Ｌ１から２段目Ｌ２への分岐数「２」とを乗算し、２段目Ｌ２のノードデータ数「１０（＝５×２）」を算出する。
【００７８】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数「１６（＝１＋５＋１０）」を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１６」から処理済みノードデータ数「２」を減算し、未処理ノードデータ数「１４（＝１６−２）」を算出する。
【００７９】
続いて、インクリメンタル処理エンジン２１は、ノードデータＢｎＢの分岐先である２つのノードデータのメッセージを生成し、次に処理対象となるノードデータＧｎＧを保持する並列処理管理装置１０にメッセージを送信する（図１１のＳ２８）。
【００８０】
［具体例：ノードデータＧ］
メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＧｎＧに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【００８１】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＧｎＧにアクセスし、ノードデータＧｎＧの接続先のノードデータ（接続先なし）、及び、ノードデータＧｎＧからの分岐数「０」を取得する。したがって、インクリメンタル処理エンジン２１は、２段目Ｌ２から３段目への分岐数を「０」と想定し、３段目のノードデータ数「０」を算出する。
【００８２】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数「１６（＝１＋５＋１０）」を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１６」から処理済みノードデータ数「３」を減算し、未処理ノードデータ数「１３（＝１６−３）」を算出する。
【００８３】
そして、処理対象のノードデータがリーフに到達したため、インクリメンタル処理エンジン２１は、算出した合計処理数に基づいて、処理対象のノードデータから分岐するノードデータに対する処理を並列化の対象とするか否かを判定する（図１１のＳ２７）。具体的に、インクリメンタル処理エンジン２１は、算出した合計処理数が１０以上であって、処理対象のノードデータからの分岐数が３以上である場合、処理対象のノードデータから分岐するノードデータに対する処理が並列化の対象となる。この場合、ノードデータＧｎＧは分岐しないリーフのノードデータであるため、インクリメンタル処理エンジン２１は、後続の処理を並列化の対象としない。
【００８４】
続いて、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＨｎＨを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にメッセージを送信する（Ｓ２８）。
【００８５】
図１３で説明したように、本実施の形態例における並列処理管理装置１０は、処理済みのノードデータの段数と分岐数を、次回、処理対象となるノードデータに伝搬する。そして、並列処理管理装置１０は、伝搬された処理済みのデータノードの段数及び分岐数、処理対象のデータノードの段数及び分岐数に基づくことにより、データ処理の途中であっても、データ処理の合計処理数を見積もることができる。
【００８６】
図１４は、本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第２の図である。
【００８７】
［具体例：ノードデータＨ］
同様にして、メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＨｎＨに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【００８８】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＨｎＨにアクセスし、ノードデータＨｎＨの接続先のノードデータ（接続先なし）、及び、ノードデータＨｎＨからの分岐数「０」を取得する。したがって、インクリメンタル処理エンジン２１は、２段目Ｌ２から３段目への分岐数を「０」と想定し、３段目のノードデータ数「０」を算出する。
【００８９】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数「１６（＝１＋５＋１０）」を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１６」から処理済みノードデータ数「４」を減算し、未処理ノードデータ数「１２（＝１６−４）」を算出する。
【００９０】
また、インクリメンタル処理エンジン２１は、ノードデータＨからの分岐数が３未満であるため、後続の処理を並列化の対象としない。続いて、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＣｎＣを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にメッセージを送信する（Ｓ２８）。
【００９１】
［具体例：ノードデータＣ］
同様にして、メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＣｎＣに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＣｎＣにアクセスし、ノードデータＣｎＣの接続先のノードデータ（ノードデータＩｎＩ）、及び、ノードデータＣｎＣからの分岐数「１」を取得する。
【００９２】
ノードデータＣｎＣと同様の１段目Ｌ１に属するノードデータＢｎＢからの分岐数は「２」であるため、インクリメンタル処理エンジン２１は、１段目Ｌ１から２段目Ｌ２への分岐数を平均値である「１．５＝（（２＋１）／２）」と想定して、１段目Ｌ１の算出ノードデータ数「５」と１段目Ｌ１から２段目Ｌ２への分岐数「１．５」とを乗算し、２段目Ｌ２のノードデータ数「７．５（＝５×１．５）」を算出する。そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数「１３．５（＝１＋５＋７．５）」を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨ、ＣｎＣが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１３．５」から処理済みノードデータ数「５」を減算し、未処理ノードデータ数「８．５（＝１３．５−５）」を算出する。
【００９３】
また、インクリメンタル処理エンジン２１は、処理対象のノードデータＣｎＣからの分岐数が３未満であるため、後続の処理を並列化の対象としない。続いて、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＩｎＩを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にメッセージを送信する（Ｓ２８）。
【００９４】
［具体例：ノードデータＩ］
同様にして、メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＩｎＩに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【００９５】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＩｎＩにアクセスし、ノードデータＩｎＩの接続先のノードデータ（接続先なし）、及び、ノードデータＩｎＩからの分岐数「０」を取得する。したがって、インクリメンタル処理エンジン２１は、２段目Ｌ２から３段目への分岐数を「０」と想定し、３段目のノードデータ数「０」を算出する。
【００９６】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数「１３．５（＝１＋５＋７．５）」を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨ、ＣｎＣ、ＩｎＩが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１３．５」から処理済みノードデータ数「６」を減算し、未処理ノードデータ数「７．５（＝１３．５−６）」を算出する。
【００９７】
また、ノードデータＩｎＩは分岐しないリーフのノードデータであるため、インクリメンタル処理エンジン２１は、後続の処理を並列化の対象としない。続いて、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＤｎＤを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にメッセージを送信する（Ｓ２８）。
【００９８】
図１４で説明したように、本実施の形態例における並列処理管理装置１０は、伝搬された処理済みのデータノードの段数及び分岐数に加えて、処理対象のデータノードの段数及び分岐数に基づいて合計処理数を再計算する。即ち、並列処理管理装置１０は、処理済みのノードデータに基づく各段数の分岐数と、処理対象のノードデータに基づく段数の分岐数が異なる場合に、処理済みのデータノード、及び、処理対象のデータノードの段数及び分岐数に基づいて、合計処理数を再計算する。したがって、並列処理管理装置１０は、最新の情報に基づいて合計処理数を再計算するため、合計処理数を補正し、誤差を小さくしていくことができる。したがって、並列処理管理装置１０は、より早い段階に、より高い精度の合計処理数を取得することができる。
【００９９】
また、本実施の形態例における並列処理管理装置１０は、伝搬された処理済みのデータノードの段数及び分岐数に加えて、処理対象のデータノードの段数及び分岐数に基づくことにより、処理対象のノードデータの分岐数が一定ではない場合であっても、徐々に合計処理数の精度を上げていくことができる。
【０１００】
また、本実施の形態例における並列処理管理システムでは、深さ優先で、関連するノードデータをたどる。深さ優先でたどられることによって、リーフのノードデータまで早くたどり着くため、並列処理管理システムは、ツリー構造におけるすべての段数の分岐数を早い段階で取得することができる。各段数の分岐数を早い段階で取得可能になることによって、並列処理管理装置１０は、データ処理の過程の早期の段階で、合計処理数を見積もることができる。
【０１０１】
図１５は、本実施の形態例におけるノードデータ総数の見積もり処理の具体例を説明する第３の図である。
【０１０２】
［具体例：ノードデータＤ］
同様にして、メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＤｎＤに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【０１０３】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＤｎＤにアクセスし、ノードデータＤｎＤの接続先のノードデータ（ノードデータＪｎＪ〜ＬｎＬ）、及び、ノードデータＤｎＤからの分岐数「３」を取得する。そこで、インクリメンタル処理エンジン２１は、１段目Ｌ１から２段目Ｌ２への分岐数を平均値である「２＝（（２＋１＋３）／２）」と想定して、１段目Ｌ１の算出ノードデータ数「５」と１段目Ｌ１から２段目Ｌ２への分岐数「２」とを乗算し、２段目Ｌ２のノードデータ数「１０（＝５×２）」を算出する。
【０１０４】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数１６（＝１＋５＋１０）を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨ、ＣｎＣ、ＩｎＩ、ＤｎＤが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数１６から処理済みノードデータ数７を減算し、未処理ノードデータ数９（＝１６−７）を算出する。
【０１０５】
また、インクリメンタル処理エンジン２１は、合計処理数が１０以上であって、処理対象のノードデータＤｎＤからの分岐数が３以上であるため、ノードデータＪｎＪ〜ＬｎＬの処理を並列化の対象とする。そこで、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＪｎＪ、ノードデータＫｎＫ、ノードデータＬｎＬを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にそれぞれメッセージを送信する（Ｓ２８）。
【０１０６】
［具体例：ノードデータＪ］
ここでは、ノードデータＪｎＪの処理を説明するが、ノードデータＫｎＫ、ノードデータＬｎＬの処理も、ノードデータＪｎＪの処理と同様である。同様にして、メッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＪｎＪに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【０１０７】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＪｎＪにアクセスし、ノードデータＪｎＪの接続先のノードデータ（接続先なし）、及び、ノードデータＪｎＪからの分岐数「０」を取得する。したがって、インクリメンタル処理エンジン２１は、２段目Ｌ２から３段目への分岐数を「０」と想定し、３段目のノードデータ数「０」を算出する。
【０１０８】
したがって、インクリメンタル処理エンジン２１は、２段目Ｌ２から３段目への分岐数を「０」と想定し、３段目のノードデータ数「０」を算出する。そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数１６（＝１＋５＋１０）を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨ、ＣｎＣ、ＩｎＩ、ＤｎＤ、ＪｎＪが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数「１６」から処理済みノードデータ数「８」を減算し、未処理ノードデータ数「８（＝１６−８）」を算出する。
【０１０９】
また、ノードデータＪｎＪは分岐しないリーフのノードデータであるため、インクリメンタル処理エンジン２１は、後続の処理を並列化の対象としない。また、インクリメンタル処理エンジン２１は、ノードデータＪｎＪの接続先が存在しないため、メッセージを送信しない。
【０１１０】
［具体例：ノードデータＥ］
そして、ノードデータＤを保持する並列処理管理装置１０からメッセージを受信した並列処理管理装置１０のインクリメンタル処理エンジン２１は、ノードデータＥｎＥに対して処理を行うと共に（図１１のＳ２２〜Ｓ２５）、処理数見積もり情報に基づいて、開始ノードデータＡに連なる総ノードデータ数、即ち、合計処理数の見積もり処理を行う（Ｓ２６）。
【０１１１】
具体的に、インクリメンタル処理エンジン２１は、データ記憶部２０内のノードデータＥｎＥにアクセスし、ノードデータＥｎＥの接続先のノードデータ（ノードデータＭｎＭ）、及び、ノードデータＥｎＥからの分岐数「１」を取得する。そして、インクリメンタル処理エンジン２１は、１段目Ｌ１のみなしノードデータ数「５」と１段目Ｌ１から２段目Ｌ２への分岐数の平均値「１．７５＝（（２＋１＋３＋１）／２）」とを乗算し、２段目Ｌ２のノードデータ数「８．７５（＝５×１．７５）」を算出する。
【０１１２】
そして、インクリメンタル処理エンジン２１は、０段目Ｌ０〜２段目Ｌ２のノードデータ数を加算し、合計ノードデータ数１４．７５（＝１＋５＋８．７５）を算出する。また、このとき、ノードデータＡｎＡ、ＢｎＢ、ＧｎＧ、ＨｎＨ、ＣｎＣ、ＩｎＩ、ＢｎＢ、ＪｎＪ〜ＬｎＬ、ＥｎＥが処理済みであることから、インクリメンタル処理エンジン２１は、合計ノードデータ数１４．７５から処理済みノードデータ数１１を減算し、未処理ノードデータ数３．７５（＝１４．７５−１１）を算出する。
【０１１３】
また、インクリメンタル処理エンジン２１は、分岐数が３未満であるため、ノードデータノードデータＥｎＥから分岐するノードデータＭｎＭに対する処理を並列化の対象としない（図１１のＳ２７）。続いて、インクリメンタル処理エンジン２１は、次に処理対象となるノードデータＭｎＭを保持する並列処理管理装置１０のインクリメンタル処理エンジン２１にメッセージを送信する（Ｓ２８）。続く処理は、図１３〜図１５で説明した処理と同様である。
【０１１４】
図１５で説明したように、本実施の形態例における並列処理管理装置１０は、見積もったノードデータの総数の値（合計処理数）が基準値（図１５の例では、１０）以上である場合に、処理対象のノードデータの分岐先のノードデータの処理を並列化処理の対象とする。したがって、並列処理管理装置１０は、合計処理数が多いノードデータ処理を並列処理の対象とし、合計処理数が少ないノードデータ処理を並列化しないことにより、合計処理数の異なるノードデータ処理間の処理時間の差異を狭めることができる。即ち、並列処理管理装置１０は、合計処理数に応じてデータ処理における並列処理対象のノードデータを管理することによって、合計処理数の異なるノードデータ処理間の処理時間の差異を小さくすることができる。
【０１１５】
なお、並列処理管理装置１０は、残りの処理数が基準値以上である場合に、処理対象のノードデータの分岐先のノードデータの処理を並列化処理の対象としてもよい。これにより、並列処理管理装置１０は、合計処理数が多く、且つ、残りの処理数が多い場合に、未処理のノードデータ処理を並列処理の対象とすることができる。
【０１１６】
また、本実施の形態例における並列処理管理装置１０は、見積もった合計処理数が基準値以上である場合に、さらに、分岐数が基準分岐数（図１５の例では３）以上である場合に、処理対象のノードデータの分岐先のノードデータの処理を並列化処理の対象とする。本実施の形態例における並列処理管理システムは、さらに、分岐数に応じて、並列化の有無を判定することによって、より柔軟に並列処理の管理を行うことができる。
【０１１７】
なお、図１３〜図１５の例において、並列処理管理システムは、さらに、合計処理数から算出される残りの処理数に基づくことにより、データ処理の実行を制御して、ターンアラウンド時間を短縮する制御を行うことができる。
【０１１８】
図１６は、合計処理数の見積もり数の遷移を説明する図である。図１６の（Ａ）は、例えば、ノードデータの平均分岐数とツリー構造の深さに基づいて、合計処理数を見積もった場合における残り処理数と実際の残り処理数の差とを説明する図である。図１６の（Ａ）の例において、例えば、見積もりによって算出された残り処理時間は５である。これに対し、実際の残り処理時間は１５である。したがって、見積もりによる残り処理時間と、実際の残り処理時間との間の誤差は−１０である。
【０１１９】
一方、図１６の（Ｂ）は、本実施の形態例における並列処理管理装置１０が合計処理数に基づいて見積もった残り処理数と、実際の残り処理数の差を説明する図である。本実施の形態例において、データ処理におけるそれぞれのノードデータの処理の度に、残り処理時間が再計算される。図１６の（Ｂ）の例において、例えば、見積もられた残り処理時間は、６→１６→・・・→１６→１３．５のように遷移する。これに対し、実際の残り処理時間は１５である。したがって、本実施の形態例の並列処理管理装置１０が見積もった残り処理時間と、実際の残り処理時間との間に誤差は、−９→＋１→・・・→＋１→−１．５のように遷移する。即ち、本実施の形態例の並列処理管理装置１０が見積もった残り処理時間と、実際の残り処理時間との間に誤差は徐々に小さくなっていく。
【０１２０】
図１６に示すように、本実施の形態例における並列処理管理装置１０、データ処理の度に、伝搬された処理済みのデータノードの段数及び分岐数と、処理対象のデータノードとの段数及び分岐数に基づいて合計処理数を再計算することによって、合計処理数を補正し、誤差を小さくしていくことができる。したがって、並列処理管理装置１０は、データ処理の都度、最新の情報に基づいて合計処理数を再計算することによって、データ処理の過程において、より早い段階で、より高い精度の合計処理数を取得することができる。
【０１２１】
以上のように、本実施の形態例における並列処理管理プログラムは、処理対象ノードに対するデータの処理を行うと共に、各処理済みノード及び処理対象ノードの、開始ノードからの距離を示す段数と、各処理済みノード及び処理対象ノードからの分岐数とに基づいて、開始ノードに連なるノードの総数を算出する制御工程、を有する。
【０１２２】
本実施の形態例における並列処理管理プログラムによると、伝搬された処理済みのデータノードの段数及び分岐数、処理対象のデータノードの段数及び分岐数に基づくことにより、データ処理の途中であっても、データ処理の合計処理数を見積もることができる。したがって、並列処理管理プログラムによると、データ処理の途中であっても、合計処理数に基づいたデータノードの制御が可能になる。
【０１２３】
また、本実施の形態例における並列処理管理プログラムによると、データ処理の都度、伝搬され、蓄積された処理済みのデータノードの段数及び分岐数と、処理対象のデータノードの段数及び分岐数とに基づいて合計処理数を再計算することにより、データ処理の過程で合計処理数を補正し誤差を逓減させていくことが可能になる。したがって、本実施の形態例における並列処理管理プログラムによると、伝搬によって蓄積されたノードデータの関連情報に基づくことにより、データ処理の過程におけるより早い段階に、精度の高い合計処理数を取得することが可能になる。
【０１２４】
また、本実施の形態例における並列処理管理プログラムによると、伝搬によって蓄積された処理済みのデータノードの段数及び分岐数と、処理対象のデータノードの段数及び分岐数とに基づいて、合計処理数を見積もることにより、処理対象のノードデータの分岐数が一定ではない場合であっても、より高い精度の合計処理数を見積もることが可能になる。
【０１２５】
また、本実施の形態例における並列処理管理プログラムの制御工程では、さらに、算出したノードの総数が基準数を超える場合に、処理対象ノードから分岐するノードに対する処理を、並列処理の対象とする。
【０１２６】
また、本実施の形態例における並列処理管理プログラムによると、見積もったノードデータの総数の値（合計処理数）が基準値（図１５の例では、１０）以上である場合に、処理対象のノードデータの分岐先のノードデータの処理を並列化処理の対象とすることにより、合計処理数の異なるノードデータ処理間の処理時間の差異を小さくすることができる。具体的に、並列処理管理プログラムは、合計処理数が多いノードデータ処理を並列処理の対象とし、合計処理数が少ないノードデータ処理を並列化しないことにより、合計処理数の異なるノードデータ処理間の処理時間の差異を狭めることができる。
【０１２７】
また、本実施の形態例における並列処理管理プログラムの制御工程では、さらに、処理対象ノードからの分岐数が基準分岐数を超える場合に、処理対象ノードから分岐するノードに対する処理を並列処理の対象とする。本実施の形態例における並列処理管理プログラムによると、さらに、分岐数が基準分岐数（図１５の例では３）以上である場合に、処理対象のノードデータの分岐先のノードデータの処理を並列化処理の対象とすることにより、分岐数に応じた並列化の有無の判定を可能にし、より柔軟な並列処理の管理を可能にする。
【０１２８】
また、本実施の形態例における並列処理管理プログラムの制御工程では、さらに、算出した開始ノードに連なるノードの総数と、処理済みのノード数とに基づいて、未処理のノード数を算出する。本実施の形態例における並列処理管理プログラムによると、合計処理数に基づく残りの処理時間が特定可能になる。したがって、並列処理管理プログラムによって算出された、残りの処理時間に基づいてデータ処理を実行制御することによって、データ処理のターンアラウンド時間の平均値の短縮が可能になる。
【０１２９】
また、本実施の形態例における並列処理管理プログラムの制御工程では、前回の処理済みノードから、各処理済みノードの段数と分岐数とを受信し、次回、処理対象となるノードに、処理対象ノードの段数と分岐数とを付加した、各処理済みノード及び処理対象ノードの段数と分岐数とを送信する。本実施の形態例における並列処理管理プログラムによると、処理済みのノードデータの段数と分岐数を、次回、処理対象となるノードデータに伝搬することにより、データ処理の途中であっても、データ処理の合計処理数を見積もることが可能になる。
【０１３０】
また、本実施の形態例における並列処理管理プログラムでは、開始ノードからノード間の関連に基づいて、深さ優先でノードがたどられる。本実施の形態例における並列処理管理プログラムによると、深さ優先でたどられることによって、ツリー構造におけるすべての段数の分岐数を早い段階で取得することが可能になるため、データ処理の早期の段階で、合計処理数を見積もることが可能になる。
【０１３１】
以上の実施の形態をまとめると、次の付記のとおりである。
【０１３２】
（付記１）
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列管理処理をコンピュータに実行させるコンピュータ読み取り可能な並列処理管理プログラムであって、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する並列処理管理プログラム。
【０１３３】
（付記２）
付記１において、
前記制御工程では、さらに、前記算出したノードの総数が基準数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を、並列処理の対象とする並列処理管理プログラム。
【０１３４】
（付記３）
付記２において、
前記制御工程では、さらに、前記処理対象ノードからの分岐数が基準分岐数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を並列処理の対象とする並列処理管理プログラム。
【０１３５】
（付記４）
付記１乃至３のいずれかにおいて、
前記制御工程では、さらに、前記算出した開始ノードに連なるノードの総数と、前記処理済みのノード数とに基づいて、未処理のノード数を算出する並列処理管理プログラム。
【０１３６】
（付記５）
付記１乃至４のいずれかにおいて、
前記制御工程では、前記各処理済みノード及び前記処理対象ノードの段数と分岐数とに基づいて、第１の段数のノード数と、前記第１の段数のノード各々からの分岐数の平均値との乗算によって算出される、前記第１の段数の１つ下位の第２の段数のノード数を累計し、前記開始ノードに連なるノードの総数を算出する並列処理管理プログラム。
【０１３７】
（付記６）
付記１乃至５のいずれかにおいて、
前記制御工程では、前回の前記処理済みノードから、前記各処理済みノードの段数と分岐数とを受信し、次回、処理対象となるノードに、前記処理対象ノードの段数と分岐数とを付加した、前記各処理済みノード及び前記処理対象ノードの段数と分岐数とを送信する並列処理管理プログラム。
【０１３８】
（付記７）
付記１乃至６のいずれかにおいて、
前記開始ノードからノード間の関連に基づいて、深さ優先でノードがたどられる並列処理管理プログラム。
【０１３９】
（付記８）
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列処理管理方法であって、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御工程、を有する並列処理管理方法。
【０１４０】
（付記９）
付記８において、
前記制御工程では、さらに、前記算出したノードの総数が基準数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を、並列処理の対象とする並列処理管理方法。
【０１４１】
（付記１０）
付記８または９において、
前記制御工程では、さらに、前記算出した開始ノードに連なるノードの総数と、前記処理済みのノード数とに基づいて、未処理のノード数を算出する並列処理管理方法。
【０１４２】
（付記１１）
それぞれのノードが他のノードとの関連を有するデータ集合に対し、開始ノードからノード間の関連に基づいてたどられるノードにおけるデータの処理の並列処理管理装置において、
処理対象ノードに対する前記データの処理を行うと共に、各処理済みノード及び前記処理対象ノードの、前記開始ノードからの距離を示す段数と、前記各処理済みノード及び前記処理対象ノードからの分岐数とに基づいて、前記開始ノードに連なるノードの総数を算出する制御手段、を有する並列処理管理装置。
【０１４３】
（付記１２）
付記１１において、
前記制御手段は、さらに、前記算出したノードの総数が基準数を超える場合に、前記処理対象ノードから分岐する前記ノードに対する処理を、並列処理の対象とする並列処理管理装置。
【０１４４】
（付記１３）
付記１１または１２において、
前記制御手段は、さらに、前記算出した開始ノードに連なるノードの総数と、前記処理済みのノード数とに基づいて、未処理のノード数を算出する並列処理管理装置。
【符号の説明】
【０１４５】
１０ａ〜１０ｎ：並列処理管理装置、２１ａ〜２１ｎ：インクリメンタル処理エンジン（インクリメンタル処理プログラム）、２０ａ〜２０ｎ：データ記憶部、３０ａ〜３０ｃ：端末装置
１１：入力装置１１、１２：表示装置１２、１３：通信インタフェース、１４：プロセッサ、１５：記憶媒体、１６：メモリ、１７：バス
【図１】
2015075830.tif 000003
【図２】
2015075830.tif 000004
【図３】
2015075830.tif 000005
【図４】
2015075830.tif 000006
【図５】
2015075830.tif 000007
【図６】
2015075830.tif 000008
【図７】
2015075830.tif 000009
【図８】
2015075830.tif 000010
【図９】
2015075830.tif 000011
【図１０】
2015075830.tif 000012
【図１１】
2015075830.tif 000013
【図１２】
2015075830.tif 000014
【図１３】
2015075830.tif 000015
【図１４】
2015075830.tif 000016
【図１５】
2015075830.tif 000017
【図１６】
2015075830.tif 000018