(57)【要約】並列処理と逐次処理とを含むデータ処理の全体の処理時間を最適化するデータ処理システム等が開示される。係るデータ処理システムは、複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割するタスク分割手段と、前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる割り当て手段と、を有する。
2014068950.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割するタスク分割手段と、
前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる割り当て手段と、
を有するデータ処理システム。
【請求項２】
複数のレコードの集合であるデータセットに対して前記データ処理を実行するジョブを受け付けるジョブ受付手段と
前記ジョブの処理対象であるデータセットを複数のレコードセットへと細分化することにより、前記ジョブを複数のタスクへと分割するジョブ分割手段と、
を更に含み、
前記タスク分割手段は、前記分割された複数のタスクを受け付ける
請求項１に記載のデータ処理システム。
【請求項３】
前記タスク分割手段は、タスクの処理時間が、最も長い逐次処理の処理時間より短い場合、前記タスクに含まれる並列処理を分割しない
請求項１または２に記載データ処理システム。
【請求項４】
前記タスク分割手段は、サブタスクの処理するレコードの数が異なるように前記並列処理を分割し、前記割り当て手段は、前記並列処理の後処理である逐次処理が割り当てられる計算機に、他のサブタスクよりも多くのレコードを処理するサブタスクを割り当てる
請求項１から３のいずれか１項に記載のデータ処理システムであって、データ処理システム。
【請求項５】
前記割り当て手段は、前記並列処理の後処理である逐次処理が割り当てられる計算機に、前記逐次処理が処理する最初のレコードを処理対象に含むサブタスクを割り当てる
請求項１から４のいずれか１項に記載のデータ処理システム。
【請求項６】
前記割り当て手段は、前記タスク、前記サブタスクおよび前記サブタスクの後処理である逐次処理のそれぞれに、割当先の計算機と優先順位とを対応付けたスケジュールデータを、前記複数の計算機から参照可能な形態で出力し、
前記計算機は、
前記スケジュールデータを取得するスケジュールデータ取得手段と、
割り当てられたタスクを、前記スケジュールデータに含まれる優先順位の高い順に実行するタスク処理手段と、
を備え、
前記タスク処理手段は、前記割り当てられたタスクが実行済みであって、他の計算機に割り当てられたタスクが未実行である場合に、前記未実行のタスクを実行する
請求項１から５のいずれか１項に記載のデータ処理システム。
【請求項７】
前記割り当て手段は、前記タスク、前記サブタスクおよび前記サブタスクの後処理である逐次処理のそれぞれに、割当先の計算機と処理対象であるレコードとを対応付けたスケジュールデータを、前記複数の計算機から参照可能な形態で出力し、
前記計算機は、
レコードを取得するレコード取得手段と、
前記スケジュールデータを取得するスケジュールデータ取得手段と、
前記取得したスケジュールデータに基づいて、前記取得したレコードを、前記レコードを処理対象とする処理の割当先である計算機に対して送信するレコード送信手段と、
を備える
請求項１から５のいずれか１項に記載のデータ処理システム。
【請求項８】
複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割する分割ステップと、
前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる割り当てステップと、
を含むデータ処理方法。
【請求項９】
コンピュータに、
複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割する手順と、
前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる手順と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理におけるデータ処理システム、データ処理方法およびプログラムに関する。
【背景技術】
【０００２】
コンピュータによるデータ処理において、並列処理技術は一般に良く知られている。特許文献1は、ハッシュ結合に関して工夫をして並列処理を実行する技術を開示する。特許文献1が開示する技術は、テーブルの結合キーの出現頻度に基づいて、ハッシュ結合を複数のタスクに分割し、複数のタスクを複数の計算機に割り当てる。結合キーの出現頻度の偏りにより各タスクの処理量が均一にならない場合、特許文献1が開示する技術は、さらに、処理量が多いタスクをより細かい複数のサブタスクに分割する。特許文献1が開示する技術は、各計算機の処理量が均等になるように、各計算機に、タスクとサブタスクとを割り当てる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特公平７−１１１７１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１が開示する技術は、並列処理の処理時間を最適化するに過ぎない。特許文献１が開示する技術が、並列処理と逐次処理との両方を含むデータ処理に適用された場合、データ処理全体の処理時間を必ずしも最適化しないという課題がある。【０００５】
本発明は、並列処理と逐次処理とを含むデータ処理の全体の処理時間を最適化するデータ処理システムを提供することを１つの目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決する第１の発明は、複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割するタスク分割手段と、前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる割り当て手段と、を有するデータ処理システムである。
【０００７】
上述した課題を解決する第２の発明は、複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割する分割ステップと、前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる割り当てステップと、を含むデータ処理方法である。
【０００８】
上述した課題を解決する第３の発明は、コンピュータに、複数の計算機が並列して実行可能な並列処理と前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理を、複数のレコードの集合であるレコードセットに対して実行する複数のタスクを受け付け、前記タスクに含まれる逐次処理のうち、他の逐次処理と比較して処理に時間がかかると見込まれる逐次処理の前処理である並列処理について、前記並列処理の処理対象であるレコードセットを細分化することにより、前記並列処理を複数のサブタスクに分割する手順と、前記並列処理を含むタスク以外のタスクが実行される前に、前記複数のサブタスクが実行されるように、前記複数のサブタスクを、前記複数の計算機に割り当てる手順と、を実行させるためのプログラムである。
【０００９】
また、本発明の目的は、上記のプログラムが格納されたコンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００１０】
本発明によれば、並列処理と逐次処理とを含むデータ処理の全体の処理時間を最適化することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明のデータ処理システム１０００のハードウェア構成図である。
【図２】本発明の第１の実施形態におけるデータ処理システム１０００のブロック図である。
【図３】本発明におけるタスクの概念を説明する図である。
【図４】本発明におけるサブタスクの概念を説明する図である。
【図５】本発明におけるタスク割り当ての概念を説明する図である。
【図６】本発明におけるデータ処理システム１０００の動作を説明するフローチャート図である。
【図７】本発明の第２の実施形態におけるデータ処理システム１０００のブロック図である。
【図８】本発明の第２の実施形態におけるデータ処理システム１０００の動作を説明するフローチャート図である。
【図９】本発明の第３の実施形態におけるタスク分割部１０の動作を説明する図である。
【図１０】本発明の第３の実施形態におけるタスク分割部１０の動作を説明する図である。
【図１１】本発明の第３の実施形態におけるタスク分割部１０の動作を説明する図である。
【図１２】本発明の第４の実施形態におけるタスク分割部１０および割り当て部２０の動作を説明する図である。
【図１３】本発明の第４の実施形態におけるタスク分割部１０および割り当て部２０の動作を説明する図である。
【図１４】本発明の第４の実施形態の効果を説明するための図である。
【図１５】本発明の第５の実施形態における割り当て部２０の動作を説明する図である。
【図１６】本発明の第５の実施形態の効果を説明するための図である。
【図１７】本発明の第５の実施形態の効果を説明するための図である。
【図１８】本発明の第５の実施形態の効果を説明するための図である。
【図１９】本発明のテーブル、レコードセット、レコードの具体例を説明する図である。
【図２０】本発明の統計情報の具体例を説明する図である。
【図２１】本発明の第６の実施形態におけるデータ処理システム１０００のブロック図である。
【図２２】本発明の第６の実施形態におけるデータ処理システム１０００のブロック図である。
【図２３】本発明の第７の実施形態におけるデッドラインを説明する図である。
【図２４】本発明の第７の実施形態におけるデッドラインを説明する図である。
【図２５】本発明の第７の実施形態におけるデータ処理システム１０００の動作を説明するフローチャート図である。
【図２６】本発明の第８の実施形態におけるデータ処理システム１０００のブロック図である。
【図２７】本発明の第８の実施形態におけるタスク実行部２００のブロック図である。
【図２８】本発明の第８の実施形態におけるスケジュールデータの具体例を説明する図である。
【図２９】本発明の第８の実施形態におけるスケジュールデータの具体例を説明する図である。
【図３０】本発明の第８の実施形態におけるタスク実行部２００の動作を説明するフローチャート図である。
【図３１】本発明の第８の実施形態におけるスケジュールデータの具体例を説明する図である。
【図３２】本発明の第８の実施形態の変形例におけるタスク実行部２００の動作を説明する図である。
【図３３】本発明の第９の実施形態におけるデータ処理システム１０００のブロック図である。
【図３４】本発明の第９の実施形態におけるタスク実行部４００のブロック図である。
【図３５】本発明の第９の実施形態におけるシャッフルキーの具体例を説明する図である。
【発明を実施するための形態】
【００１２】
本発明が対象とするデータ処理は、並列処理と逐次処理とを含む。並列処理は、複数の計算機が並列して実行可能な処理である。逐次処理は、並列処理の後処理として実行される。
【００１３】
並列処理では、計算機の数が増えるほど、処理時間は短縮される。他方、逐次処理は、１つの計算機により実行される処理である。計算機の数が増えても、逐次処理の処理時間は短縮されない。このため、複数の計算機が、並列処理と逐次処理との両方を含むデータ処理を実行する場合、逐次処理の処理時間は、データ処理全体の処理時間のボトルネックとなりやすい。
【００１４】
次に、本発明の実施の形態を説明するための、用語の定義およびその関係を以下に示す。「テーブル」とは、データ処理が実行される対象となるデータである。テーブルは、複数のレコードセットを含む。「レコードセット」とは、複数のレコードの集合であり、一つの計算機により逐次処理が実行される単位である。「ジョブ」とは、テーブルに対するデータ処理である。「タスク」とは、レコードセットに対するデータ処理である。ジョブは、その処理対象がテーブルからレコードセットに細分化されることにより、複数のタスクに分割される。
【００１５】
タスクは、並列処理可能タスクと逐次処理タスクに分割され得る。「並列処理可能タスク」とは、レコードセットに対して並列処理を実行する処理である。「逐次処理タスク」とは、レコードセットに対して並列処理の後処理である逐次処理を実行する処理である。
【００１６】
並列処理可能タスクは、その処理対象がレコードセットからより細かいレコードの集合に細分化されることにより、複数の「サブタスク」に分割され得る。つまり、一つのタスクは、複数のサブタスクと一つの逐次処理タスクに分割され得る。
【００１７】
「サブタスクと逐次処理タスクとが対応している」とは、サブタスクと逐次処理タスクとが同一のタスクから分割されたことを意味する。「大きいタスク」とは、実行対象のレコードセットに含まれるレコード数が多いタスクを意味する。タスクの処理時間は、おおむね処理対象であるレコードセットに含まれるレコード数によって決まる。大きいタスクは、処理時間の長いタスクである。
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００１８】
＜第１の実施形態＞
図１は、第１の実施形態にかかるデータ処理システム１０００のハードウェア構成図である。図１に示すように、データ処理システム１０００は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２、ハードディスクドライブ３、通信インタフェース４、入力装置５、出力装置６等を含む。
【００１９】
データ処理システム１０００の機能は、例えば、ＣＰＵ１が、プログラムをＲＡＭ２に読み出し、実行することによって実現される。データ処理システム１０００による情報の送受信は、例えばＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）が提供する機能を使ってアプリケーションプログラムが通信インタフェース４を制御することによって実現される。入力装置５は、例えばキーボードやマウスである。出力装置６は、例えばディスプレイである。なお、入力装置５と出力装置６とは、例えばタッチパネルとして一体化されていてもよい。
【００２０】
尚、本実施形態および後述する各実施形態を例として説明される本発明は、係るプログラムが格納されたコンパクトディスク等の不揮発性の記憶媒体８によっても構成される。記憶媒体８が格納するプログラムは、例えばドライブ装置７により読み出される。
【００２１】
データ処理システム１０００は、２つ以上の物理的に分離した装置が有線または無線で通信可能に接続されることによって構成されていてもよい。
【００２２】
図２は、第１の実施形態にかかるデータ処理システム１０００のブロック図である。図２に示すように、データ処理システム１０００は、タスク分割部１０と、割り当て部２０とを含む。
【００２３】
データ処理システム１０００において、タスク分割部１０は、複数のタスクの実行要求を受け付ける。そしてタスク分割部１０は、受け付けた複数のタスクのそれぞれについて、タスクに含まれる逐次処理タスクの処理時間を算出する。タスク分割部１０は、例えば、タスクの処理対象であるレコードセットが含むレコードの数に基づいて、タスクの処理時間を算出する。タスク分割部１０は、他の逐次処理タスクと比較して大きい逐次処理タスクの前処理である並列処理可能タスクを、複数のサブタスクに分割する。
【００２４】
割り当て部２０は、分割された並列処理可能タスクを含むタスク以外のタスクが実行される前に、複数のサブタスクが実行されるように、複数のサブタスクを、複数の計算機に割り当てる。
【００２５】
図３は、データ処理システム１０００により処理されるタスクの概念を説明する図である。図３には３つの長方形が示されている。３つの長方形はそれぞれ、タスクＡ、タスクＢおよびタスクＣ）を表している。すなわち、図３は、タスクＡ、タスクＢおよびタスクＣの３つのタスクを表している。それぞれのタスクは、並列処理可能タスク（横線で塗りつぶした部分）と、逐次処理タスク（白色の部分）とを含む。図３に示す長方形（タスク）の長さは、タスクを単一の計算機で実行した場合における当該タスクの処理時間を表す。処理時間は、おおむねタスクが処理するレコードセットのサイズに比例すると考えてよい。図３に示すように、タスクＡの逐次処理タスクは、タスクＢやタスクＣの逐次処理タスクより大きい。
【００２６】
図４は、図３に示されるタスクＡの並列処理可能タスクがサブタスクに分割された様子を説明する図である。図４に示すように、タスク分割部１０は、タスクＡの並列処理可能タスクを、複数のサブタスク(格子で塗りつぶした部分)に分割する。具体的には、タスク分割部１０は、並列処理可能タスクを、ジョブを実行する計算機の数量分のサブタスクに分割する。例えば、ジョブが３台の計算機で実行される場合、タスク分割部１０は、タスクＡの並列処理可能タスクを、３つのサブタスクに分割する。
【００２７】
図５は、図４に示されるタスクが、３台の計算機に割り当られた様子を説明する図である。図５に示すように、割り当て部２０は、タスクＡのサブタスク、タスクＡの逐次処理タスク、タスクＢ、タスクＣを３台の計算機に割り当てる。割り当て部２０は、タスクＡのサブタスクが、タスクＢやタスクＣが実行される前に実行されるように、割り当てる。
【００２８】
図５に示すように、計算機１は、タスクＡのサブタスクを実行してからタスクＡの逐次処理タスクを実行する。計算機２は、タスクＡのサブタスクを実行してから、その実行結果を計算機１に送信し、次いでタスクＢを実行する。計算機３は、タスクＡのサブタスクを実行してから、その実行結果を計算機１に送信し、次いでタスクＣを実行する。
【００２９】
図６は、データ処理システム１０００の動作を説明するフローチャートである。図６に示すように、タスク分割部１０は、複数のタスクの実行要求を受け付ける（Ａ１００）。タスク分割部１０は、実行要求を受け付けた各タスクの処理対象であるレコードセットに含まれるレコードの数にもとづいて、各タスクに含まれる逐次処理タスクの処理時間を算出する（Ａ１１０）。
【００３０】
タスク分割部１０は、大きい逐次処理タスクを含むタスクを、並列処理可能タスクと逐次処理タスクに分割し、さらに、並列処理可能タスクを複数のサブタスクに分割する（Ａ１２０）。割り当て部２０は、複数のサブタスクが、大きい逐次処理タスクを含むタスク以外のタスクが実行される前に実行されるように、タスク、サブタスク、逐次処理タスクを複数の計算機に割り当てる（Ａ１３０）。
【００３１】
以上に説明したように、本実施形態にかかるデータ処理システム１０００は、複数の計算機が並列して実行可能な並列処理と、前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理全体の処理時間を、最適化するデータ処理システム、データ処理方法およびプログラムを提供できる。その理由は、データ処理システム１０００が、データ処理全体のボトルネックとなりやすい大きい逐次処理タスクができるだけ早く実行されるように、ジョブの実行をスケジューリングするからである。その結果、大きい逐次処理タスクが、他のタスクと重ね合わせて実行されるため、データ処理全体の処理時間が最適化される。
【００３２】
＜第２の実施形態＞
図７は、第２の実施形態にかかるデータ処理システム１０００のブロック図である。図７に示すように、第２の実施形態にかかるデータ処理システム１０００は、第１の実施形態にかかるデータ処理システム１０００に加えてさらに、ジョブ受付部３０とジョブ分割部４０とを含む。
【００３３】
ジョブ受付部３０は、ジョブの実行要求を受け付ける。ジョブ分割部４０は、ジョブの処理対象であるテーブルを、複数のレコードセットに細分化することにより、ジョブを複数のタスクに分割する。タスク分割部１０は、ジョブ分割部４０から複数のタスクを受け付け、第１の実施形態と同様に動作する。
【００３４】
図８は、データ処理システム１０００の動作を説明するフローチャートである。なお、図８に示された各処理のうち、図６に示された処理と実質的に同一のものには同一の符号が付されている。図８に示すように、ジョブ受付部３０は、ジョブの実行要求を受け付ける（Ｂ１００）。ジョブ分割部４０は、実行要求を受け付けたジョブを、複数のタスクに分割する（Ｂ１１０）。以降、Ａ１１０〜Ａ１３０の処理が、第１の実施形態と同様にして実行される。
【００３５】
以上に説明したように、本実施形態にかかるデータ処理システム１０００は、複数の計算機が並列して実行可能な並列処理と、前記並列処理の後処理であって１つの計算機により実行される逐次処理とを含むデータ処理全体の処理時間を、最適化するデータ処理システム、データ処理方法およびプログラムを提供できる。その理由は、データ処理システム１０００が、データ処理全体のボトルネックとなりやすい大きい逐次処理タスクができるだけ早く実行されるように、ジョブの実行をスケジューリングするからである。その結果、大きい逐次処理タスクが、他のタスクと重ね合わせて実行されるため、データ処理全体の処理時間が最適化される。
【００３６】
＜第３の実施形態＞
第３の実施形態にかかるデータ処理システム１０００では、タスク分割部１０の動作が、第１または第２の実施形態にかかるタスク分割部１０の動作と異なる。タスク分割部１０は、最も大きい逐次処理タスクよりも大きいタスクについては、タスクに含まれる並列処理可能タスクを分割する。タスク分割部１０は、最も大きい逐次処理タスクよりも小さいタスクについては、タスクに含まれる並列処理可能タスクを分割しない。
【００３７】
以下、３つのタスクに分割され得るジョブを、Ｎ台の計算機で処理する場合を例に、第３の実施形態におけるタスク分割部１０の動作を説明する。図９、図１０および図１１は、第３の実施形態におけるタスク分割部１０の動作を説明する図である。
【００３８】
図９は、３つのタスク（タスクＡ、タスクＢおよびタスクＣ）を示している。図９に示すように、最も大きい逐次処理タスクは、タスクＡの逐次処理タスクである。タスク分割部１０は、タスクＡ〜Ｃの処理時間を、タスクＡの逐次処理タスクの処理時間と比較する。タスクＡおよびタスクＢは、タスクＡの逐次処理タスクよりも大きい。よって、タスク分割部１０は、タスクＡの並列処理可能タスクをＮ個のサブタスクに分割し、タスクＢの並列処理可能タスクをＮ個のサブタスクに分割する。一方、タスクＣは、タスクＡの逐次処理タスクの処理時間よりも小さい。よって、タスク分割部１０は、タスクＣの並列処理可能タスクを分割しない。
【００３９】
図１０は、図９に示されるタスクＡの並列処理可能タスクと、タスクＢの並列処理可能タスクが、サブタスクに分割された様子を説明する図である。図１０に示すように、タスクＡの並列処理可能タスクはＮ個のサブタスクに分割され、タスクＢの並列処理可能タスクもＮ個のサブタスクに分割される。以降、タスクＡの並列処理可能タスクから分割されたサブタスクを「タスクＡのサブタスク」と記載する。タスクＢの並列処理可能タスクから分割されたサブタスクを「タスクＢのサブタスク」と記載する。
【００４０】
図１１は、図１０に示されるタスクが、Ｎ台の計算機に割り当てられた様子を示した図である。図１１に示すように、割り当て部２１は、タスクＡのサブタスク、タスクＡの逐次処理タスク、タスクＢのサブタスク、タスクＢの逐次処理タスクおよびタスクＣを、複数の計算機１〜Ｎに割り当てる。
タスク分割部１０がタスクＣを分割しない理由は、以下の通りである。図１１に示すように、ジョブ全体の処理時間のボトルネックは、タスクＡの逐次処理タスクの処理時間である。計算機の数がいくら増えようと、タスクＡの逐次処理タスクの処理時間は、短縮されることはない。よって、タスク分割部１０が、仮に、タスクＡの逐次処理タスクよりも処理時間が短いタスクＣを並列化したとしても、ジョブ全体の処理時間は短くならない。
【００４１】
第３の実施形態におけるタスク分割部１０は、最も大きい逐次処理タスクよりも小さいタスクについては、タスクに含まれる並列処理可能タスクを分割しない。第３の実施形態におけるデータ処理システム１０００は、かかる構成を有することにより、不要な並列化を抑止し、不要な並列化によるオーバヘッドの発生を防止することができる。
【００４２】
なお、タスクＡおよびタスクＢがタスクＡの逐次処理タスクよりも大きく、かつ、タスクAがタスクBよりも十分に大きい場合には、タスク分割部１０は、タスクBの並列処理可能タスクの分割数を、タスクAの並列処理可能タスクの分割数よりも少なくしてもよい。このとき、割り当て部２０は、タスクAの逐次処理タスクを処理する計算機に、タスクBのサブタスクを割り当てないようにスケジュールする。
【００４３】
具体的には、タスクAの一つのサブタスクとタスクAの逐次処理タスクとの合計処理時間が、タスクAの一つのサブタスクとタスクBの一つのサブタスクとタスクBの逐次処理タスクとの合計処理時間よりも長くなるのであれば、タスク分割部１０は、タスクBのタスクBの並列処理可能タスクの分割数を、タスクAの並列処理可能タスクの分割数よりも少なくする。
【００４４】
例えば、タスクAの並列処理可能タスクがN個のサブタスクに分割され、タスクBの並列処理可能タスクがN−１個のサブタスクに分割された場合、割り当て部２０は、タスクAの逐次処理タスクを処理する計算機（計算機１）には、タスクBのサブタスクを割り当てない。このようにスケジューリングすると、ジョブ全体の処理時間のボトルネックであるタスクAの逐次処理タスクの実行をさらに早めることができ、ジョブ全体の実行時間をさらに短くすることができる。
【００４５】
＜第４の実施形態＞
第４の実施形態にかかるデータ処理システム１０００では、タスク分割部１０と割り当て部２０の動作が、第１、第２および第３の実施形態とは異なる。タスク分割部１０は、タスクＡの並列処理可能タスクを複数のサブタスクに分割する際、各サブタスクの処理するレコードの数が異なるように分割する。割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機に、他のサブタスクよりも多くのレコードを処理するサブタスクを割り当てる。割り当て部２０は、それ以外の計算機には、サブタスクを割り当てない場合がある。
【００４６】
図１２、図１３および図１４は、第４の実施形態における、タスク分割部１０および割り当て部２０の動作を説明する図である。図１２〜図１４に示すように、本例は、５つのタスクに分割され得るジョブを４台の計算機で処理する場合を扱う。
【００４７】
図１２は、５つのタスク（タスクＡ〜Ｅ）を示している。図１２に示すように、タスクＡの逐次処理タスクは、タスクＢ〜タスクＥの逐次処理タスクより大きい。タスク分割部１０は、タスクＡの並列処理可能タスクを、複数のサブタスクに分割する。
【００４８】
図１３は、タスク分割部１０が、図１２に示されるタスクＡの並列処理可能タスクを、サブタスクの処理するレコードの数が異なるように分割し、割り当て部２０が、タスクＡの逐次処理タスクが割り当てられる計算機（計算機１）に、他のサブタスクよりも多くのレコードを処理するサブタスクを割り当てた様子を示す図である。図１３に示す例では、タスクＡの並列処理可能タスクは３つのサブタスクに分割され、３つのサブタスクは、それぞれ計算機１、計算機２、および計算機３に割り当てられている。図１３に示す例では、計算機１に割り当てられたサブタスクは、計算機２および計算機３に割り当てられたサブタスクの２倍の大きさである。
【００４９】
割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機（計算機１）以外の計算機の中から、サブタスクを割り当てない計算機を選択する。図１３に示す例では、計算機４にサブタスクが割り当てられていない。よって、計算機４は、サブタスクの実行結果を計算機１に転送する必要がない。割り当て部２０は、逐次処理を実行する計算機（計算機１）へのデータ転送コストが高い計算機を、サブタスクを割り当てない計算機として選択することが好ましい。
【００５０】
図１４は、本実施形態の効果を説明する図である。ここでは、図１２に示されるタスクＡの並列処理可能タスクが、サブタスクの処理するレコードの数が互いに等しくなるように分割された場合を想定する。図１４に示すように、タスクＡの並列処理可能タスクは４つのサブタスクに分割され、４つのサブタスクはそれぞれ計算機１ないし４に割り当てられる。図１４に示すように、タスクＡのサブタスク、タスクＡの逐次処理タスクおよびタスクＢ〜Ｅが、４台の計算機（計算機１〜４）に割り当てられる。計算機２、３および４は、タスクＡのサブタスクを実行すると、サブタスクの実行結果を計算機１に転送しなければならない。この場合、図１３に示すようにタスクスケジュールした場合と比較して、計算機４のデータ通信コストが増大してしまう。
【００５１】
このように、第４の実施形態におけるタスク分割部１０は、サブタスクの処理するレコードの数が異なるように、並列処理可能タスクを分割する。第４の実施形態にかかる割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機に、他のサブタスクよりも多くのレコードを処理するサブタスクを割り当てる。割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機以外の計算機の中から、サブタスクを割り当てない計算機を選択する。第４の実施形態におけるデータ処理システム１０００は、かかる構成を有することにより、サブタスクが割り当てられない計算機のデータ転送コストを抑えることができる。
【００５２】
＜第５の実施形態＞
第５の実施形態にかかるデータ処理システム１０００では、タスク分割部１０および割り当て部２０の動作が、第１、第２、第３および第４の実施形態とは異なる。本実施形態にかかるデータ処理システム１０００は、レコードセットに含まれるレコードを所定の順序で処理する逐次処理タスクを扱う。
【００５３】
データ処理システム１０００において、タスク分割部１０は、タスクの実行命令を受け付ける際に、レコードの処理順序を定める情報を受け付ける。タスク分割部１０は、タスクに含まれる逐次処理タスクの処理実行時間を、タスクの処理対象であるレコードセットが含むレコードの数に基づいて算出する。タスク分割部１０は、他の逐次処理タスクと比較して大きい逐次処理タスクの前処理である並列処理可能タスクを複数のサブタスクに分割する。タスク分割部１０は、レコードの処理順序に従って、レコードセットをより細かいレコードの集合に細分化する。
【００５４】
例えば、２００件のレコードを処理対象とするタスクを、４台の計算機により処理する場合、タスク分割部１０は、５０件のレコードを含む４つの集合にレコードセットを分割する。この場合、タスク分割部１０は、最初に処理されるレコードから５０番目に処理されるレコードまでを、１つ目のサブタスクが処理するレコードの集合とする。タスク分割部１０は、５１番目に逐次処理されるレコードから１００番目に逐次処理されるレコードまでを、２つ目のサブタスクが処理するレコードの集合とする。タスク分割部１０は、１０１番目に逐次処理されるレコードから１５０番目に逐次処理されるレコードまでを、３つ目のサブタスクが処理するレコードの集合とする。タスク分割部１０は、１５１番目に逐次処理されるレコードから２００番目に逐次処理されるレコードまでを、４つ目のサブタスクが処理するレコードの集合とする。
【００５５】
割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機に、逐次処理タスクが処理する最初のレコードを処理対象に含むサブタスクを割り当てる。
【００５６】
図１５は、割り当て部２０が、逐次処理タスクが割り当てられる計算機（計算機１）に、逐次処理タスクが処理する最初のレコードを処理対象に含むサブタスクを割り当てた様子を示す図である。図１６は、第５の実施形態の効果を説明するための図である。図１５および図１６において、計算機１に割り当てられたサブタスクは、「最初に処理されるレコードを処理対象に含むサブタスク（図１５ないし図１８においてαと記載）」である。図１５において、計算機２、３および４に割り当てられたサブタスクは、「最初に処理されるレコードを処理対象に含まないサブタスク（図１５ないし図１８においてβと記載）」である。
【００５７】
図１６は、図１５に示されるようにスケジュールされた場合において、計算機２によるサブタスクの実行に遅延が発生した様子を示している。図１６に示すように、計算機２の遅延は、ジョブ全体の処理時間に何ら影響していない。なぜなら、計算機１が最初のレコードを処理対象に含むサブタスクの実行を完了した時点で、計算機１は、逐次処理タスクの実行を開始できるからである。計算機２は、計算機１が逐次処理タスクを実行している間に、計算機２に割り当てられたサブタスクの実行を完了し、実行結果を計算機１に送信する。この場合、計算機２によるサブタスクの実行の遅延は、ジョブ全体の処理時間に影響を及ぼさない。
【００５８】
図１７および図１８は、第５実施形態に係る効果を説明するための図である。図１７および図１８においても、「最初に処理されるレコードを処理対象に含むサブタスク」を図においてαと記載し、「最初に処理されるレコードを処理対象に含まないサブタスク」を図においてβと記載している。図１７は、割り当て部２０が、最初に処理されるレコードを処理対象に含むサブタスクを、逐次処理タスクが割り当てられた計算機（計算機１）に割り当てなかった場合の様子を示す図である。図１７に示すように、最初に処理されるレコードを処理対象に含むサブタスクは、計算機２に割り当てられている。
【００５９】
図１８は、図１７に示されるようにスケジュールされた場合において、計算機２によるサブタスクの実行に遅延が発生した様子を示している。図１８に示すように、計算機２の遅延は、ジョブ全体の処理時間を遅延させている。なぜなら、計算機２によるサブタスクの実行が終了しないと、計算機１は、逐次処理タスクの実行を開始できないからである。
【００６０】
このように、第５の実施形態における割り当て部２０は、並列処理可能タスクの後処理である逐次処理タスクが割り当てられる計算機に、逐次処理タスクが処理する最初のレコードを処理対象に含むサブタスクを割り当てる。第５の実施形態におけるデータ処理システム１０００は、かかる構成を有することにより、例えば誤差やシステム障害などによるタスクの再実行などの影響で遅延が発生した場合においても、逐次処理タスクの開始時間に影響が及ぶことを防止することができる。
【００６１】
なお、第５の実施形態におけるデータ処理システム１０００では、タスク分割部１０の代わりに、ジョブ受付部３０が、レコードの処理順序を定める情報の入力を受け付けても良い。
【００６２】
＜第６の実施形態＞
第６の実施形態にかかるデータ処理装置１０００は、結合（ＪＯＩＮ）処理と、結合処理の後処理である走査処理と、を含むデータ処理を、テーブルに対して実行する。
【００６３】
図１９は、第６の実施形態にかかるデータ処理装置１０００における、テーブル、レコードセット、レコードの一例を示す図である。図１９は、あくまで説明をわかりやすくするための一例に過ぎず、テーブル、レコードセット、レコードを限定的に解釈するためのものではない。
【００６４】
図１９に例示するように、レコードは、レコード識別子（ＩＤ）、支店名、顧客ＩＤおよび取引時刻を含む。ここで、レコードＩＤ、支店名、顧客ＩＤおよび取引時刻は、レコードの属性である。レコードが有する属性は、「逐次処理が実行される単位を決定する属性」を含む。
【００６５】
「逐次処理が実行される単位を決定する属性」の値は、レコードがどのレコードセットに属するかを決定する。例えば、「支店名」という属性が、「逐次処理が実行される単位を決定する属性」である場合、支店名の値が共通するレコードの集合がレコードセットである。
【００６６】
本実施形態にかかる並列処理は、例えば、図１９に示される取引テーブルと、図示しないマスタテーブルとを、支店名をキーとして結合する。そして、本実施形態にかかる逐次処理は、例えば、結合後のレコードに対して、同じ支店名を有するレコードセットの中で、レコードを取引時刻順に走査する。
【００６７】
図２０は、図１９に示されるテーブルに関する統計情報（以下、統計情報と記載）の一例である。図２０に示すように、統計情報の一例は、逐次処理が実行される単位を決定する属性（図２０に示す例では、支店名）の値ごとのレコード数を示すヒストグラムである。図２０に示す統計情報は、あくまで説明をわかりやすくするための一例に過ぎず、統計情報を限定的に解釈するものではない。統計情報は、例えば、レコードの総量や、逐次処理が実行される単位を決定する属性の値ごとのレコード数の偏りなどの情報を含んでいても良い。
【００６８】
また、レコードは、逐次処理が実行される順序を決定する属性を含んでいても良い。例えば、取引時刻が、逐次処理が実行される順序を決定する属性である場合、逐次処理は、レコードセットの中で取引時刻が早い順に実行されるとしてもよい。前述した統計情報は、逐次処理が実行される順序を決定する属性の値ごとの分布などの情報を含んでいても良い。
【００６９】
図２１は、第６の実施形態にかかるデータ処理システム１０００のブロック図である。なお、図２１に示された各構成のうち、図２および図７に示された構成と実質的に同一のものには同一の符号が付されている。図２１に示すように、第６の実施形態にかかるデータ処理システム１０００は、タスク分割部１０、レコード情報収集部１１０、割り当て部２０、ジョブ受け付け部３０、ジョブ分割部４０、およびデータ格納部３００を含む。
【００７０】
ジョブ受付部３０は、ジョブの実行要求を受け付ける。ジョブの実行要求は、データ処理の内容を特定する情報と、処理対象であるテーブルを特定する情報とを含む。データ処理の内容を特定する情報は、例えば、ジョブ処理時間のどれくらいの割合が並列実行可能かのパラメータを含む。ジョブ受付部３０は、ジョブの実行要求に含まれる、処理対象であるテーブルを特定する情報をレコード情報収集部１１０に対して出力する。
【００７１】
レコード情報収集部１１０は、処理対象であるテーブルを特定する情報に基づいて、データ格納部３００から、統計情報を取得する。レコード情報収集部１１０は、データ格納部３００に格納されているテーブルを読み込んで、統計情報を算出するとしてもよい。あるいは、レコード情報収集部１１０は、データ格納部３００がテーブルとともに予め格納している統計情報を取得するとしてもよい。レコード情報収集部１１０は、統計情報をジョブ分割部４０に対して出力する。
【００７２】
ジョブ分割部４０は、統計情報に基づいて、ジョブ受付部３０が受け付けたジョブを、複数のタスクに分割する。例えば、ジョブ受付部３０が、図１９に示すテーブルを処理対象とするジョブを受け付けた場合を説明する。図１９に示すテーブルには、６００件のレコードが含まれている。
【００７３】
支店名の値が共通するレコードの集合がレコードセットである場合、ジョブ分割部４０は、６００件のレコードを含むテーブルを、２００件のレコードを含むレコードセット１つ（東京支店）と、１００件のレコードを含むレコードセット２つ（札幌支店、仙台支店）と、５０件のレコードを含むレコードセット２つ（横浜支店、大阪支店）と、２５件のレコードを含むレコードセット４つ（京都支店、神戸支店、広島支店、福岡支店）とに分割する。
【００７４】
タスク分割部１０は、分割された複数のタスクの実行要求を受け付ける。そして、タスク分割部１０は、データ処理の内容を特定する情報と、統計情報とに基づいて、タスクおよびタスクに含まれる逐次処理タスクの処理時間を算出する。例えば、タスク分割部１０は、タスクの処理対象であるレコードセットが含むレコードの数と、ジョブ受付部３０が受け付けたデータ処理の内容を特定する情報と、を入力として、タスクの処理時間を算出する。タスク分割部１０は、タスクを複数のサブタスクと一つの逐次処理タスクに分割する。
【００７５】
割り当て部２０は、サブタスクが、対応する逐次処理タスクや他のタスクが実行されるより前に実行されるように、複数のサブタスクを、複数の計算機に割り当てる。
【００７６】
第６の実施形態におけるデータ処理システム１０００は、かかる構成を有することにより、結合処理と結合処理の後処理である走査処理とを含むデータ処理をテーブルに対して実行するジョブの処理時間を、最適化するデータ処理システム、データ処理方法およびプログラムを提供できる。
【００７７】
＜第７の実施形態＞
第７の実施形態にかかるデータ処理装置１０００は、ジョブ分割部４１と、タスク分割部１１と、割り当て部２１の動作が、第６の実施形態と異なる。第７の実施形態にかかるデータ処理装置１０００は、デッドラインを考慮しながら、タスクの分割と割り当てを行う。
【００７８】
図２２は、第７の実施形態にかかるデータ処理システム１０００のブロック図である。なお、図２２に示された各構成のうち、図２１に示された構成と実質的に同一のものには同一の符号が付されている。
【００７９】
ジョブ分割部４１は、デッドラインを算出する。デッドラインは、例えば、ジョブの処理時間を計算機の数で平均した時間である。タスク分割部１１は、タスクの処理時間がデッドラインを超える場合、タスクを分割する。割り当て部２１は、後述するように、デッドラインの位置の調整を行う。
【００８０】
以下、４つのタスクに分割され得るジョブを、４台の計算機で処理する場合を例に、デッドラインを説明する。図２３は、４つのタスク（タスクＡ〜Ｄ）を、４台の計算機に割り当てた様子を示した図である。図２３に示される点線は、全タスク（Ａ〜Ｄ）の処理時間を、計算機の数（４台）で平均した時間（平均処理時間）を示している。ジョブが理想的にスケジューリングされれば、ジョブの実行は、この平均処理時間内で完了する。そこで、ジョブ分割部４０Ａは、この平均処理時間をデッドラインとして設定する。
【００８１】
タスク分割部１０Ａは、最も大きいタスクＡの処理時間を算出する。タスクＡの処理時間は、デッドラインを超える。図２３に示すように、このままでは、タスクＡの処理時間がジョブ全体の処理時間のボトルネックになる。そこで、タスク分割部１０Ａは、タスクＡを分割する。割り当て部２０は、タスクＡのサブタスクを、計算機１〜４に割り当てる。
【００８２】
図２４は、このように割り当てられたタスクの様子を示した図である。しかし、図２４に示されるように、タスク分割部１０ＡがタスクＡを分割したとしても、タスクＡの処理時間はデッドラインを超えてしまう。図２４に示す例では、どのようにタスクを分割してもタスクＡの逐次処理タスクがデッドラインを超えてしまうため、ジョブの実行をデッドライン内で完了させるようなスケジューリングはできない。そこで、割り当て部２０は、デッドラインの位置を全タスクの平均処理時間（旧デッドライン）から、タスクＡの逐次処理サブタスクの完了時間（新デッドライン）に変更する。
【００８３】
２番目に大きいタスクＢの処理時間は、旧デッドラインを超えているが、新デッドラインを超えていない。よって、タスク分割部１０は、タスクＢを分割しない。タスク分割部１０が、タスクＢを分割したとしても、ジョブ全体の処理時間は新デッドラインよりも早くならないためである。  
［動作の説明］図２５は、データ処理システム１０００の動作を説明するフローチャートである。図２５に示すように、ジョブ受付部３０は、ジョブの実行要求を受け付ける（Ｃ１００）。レコード情報収集部１１０は、ジョブ受付部３０が受け付けたジョブの実行要求に含まれる処理対象であるテーブルを特定する情報に基づいて、データ格納部３００から、ジョブの処理対象である統計情報を取得する（Ｃ１１０）。
【００８４】
次に、ジョブ分割部１０は、ジョブの実行要求に含まれるデータ処理の内容を特定する情報と、取得した統計情報等に基づいて、ジョブの処理時間を算出する。そして、ジョブ分割部１０は、ジョブの処理時間を計算機の数で平均することにより、デッドラインを算出する（Ｃ１２０）。
【００８５】
ジョブ分割部４０は、統計情報に基づいて、ジョブを複数のタスクに分割する。タスク分割部１０は、分割したタスクを大きい順に未スケジュールタスクキューに格納する（Ｃ１３０）。そして、タスク分割部１０は、未スケジュールタスクキューが空になるまで以下の処理を繰り返す（Ｃ１４０）。
【００８６】
タスク分割部１０は、未スケジュールタスクキューからタスクを取り出し、その処理時間を算出する（Ｃ１５０）。タスク分割部１０は、算出した処理時間がデッドラインを超えるかどうかを判定する。（Ｃ１６０）。処理時間がデッドラインを超える場合、タスク分割部１０は、そのタスクを分割する（Ｃ１７０）。処理時間がデッドラインを越えない場合、データ処理システム１０００は、Ｃ１８０の処理に進む。
【００８７】
割り当て部２０は、タスク、サブタスクおよび逐次処理タスクを、サブタスクが、他のタスクおよび逐次処理タスクより前に実行されるように、計算機に割り当てる（Ｃ１８０）。
【００８８】
割り当て部２０は、スケジュールした結果、逐次処理タスクの処理時間がデッドラインを超えているかを判定する（Ｃ１９０）。逐次処理タスクの処理時間がデッドラインを超えていた場合、割り当て部２０は、当該逐次処理タスクが完了する時間を新デッドラインとする（Ｃ２００）。
【００８９】
第７の実施形態にかかるデータ処理装置１０００は、デッドラインを考慮しながら、タスクの分割と割り当てを行う。かかる構成により、第７の実施形態にかかるデータ処理システム１０００は、不要な並列化を抑止し、不要な並列化によるオーバヘッドの発生を防止することができる。
【００９０】
＜第８の実施形態＞
第８の実施形態にかかるデータ処理装置１０００では、割り当て部２０が出力した結果に基づいて、タスク実行部２００がタスクを実行する。
【００９１】
図２６は、第８の実施形態にかかるデータ処理システム１０００のブロック図である。なお、図２６に示された各構成のうち、図２１に示された構成と実質的に同一のものには同一の符号が付されている。図２６に示すように、第８の実施形態にかかるデータ処理システム１０００は、タスク分割部１０、レコード情報収集部１１０、割り当て部２０、ジョブ受け付け部３０、ジョブ分割部４０、タスク実行部２００Ａ〜２００Ｎ、およびデータ格納部３００を含む。なお、タスク実行部２００Ａ〜２００Ｎは、タスク実行部２００と略記することがある。
【００９２】
割り当て部２０は、タスク、サブタスク、逐次処理タスクをタスク実行部２００に割り当てた結果を、スケジュールデータとして出力する。タスク実行部２００は、割り当てられたタスクを実行する。
【００９３】
図２７は、図２６に示されるタスク実行部２００の構成を示すブロック図である。図２７に示すように、タスク実行部２００は、スケジュールデータ取得部２１０、タスク処理部２２０、進捗共有部２３０、および出力部２４０を含む。
【００９４】
スケジュールデータ取得部２１０は、割り当て部２０により出力されるスケジュールデータを取得する。スケジュールデータ取得部２１０は、割り当て部２０からスケジュールデータを入力しても良いし、割り当て部２０により参照可能な場所に出力されたスケジュールデータを読み込んでも良い。タスク処理部２２０は、割り当てられたタスクを実行する。
【００９５】
進捗共有部２３０は、割り当てられたタスクの進捗（例えば、未実行、実行中、実行済み）を、他のタスク実行部２００と共有する。進捗共有部２３０は、他のタスク実行部２００と通信することにより、進捗を共有しても良いし、スケジュールデータにタスクの進捗を書き込み、スケジュールデータからタスクの進捗を読み出すことにより、進捗を共有しても良い。出力部２４０は、割り当てられたタスクの処理結果であるデータを出力する。
【００９６】
図２８は、割り当て部２０が出力するスケジュールデータの一例を示す図である。図２８に示される例は、あくまで説明をわかりやすくするための一例に過ぎず、スケジュールデータを限定的に解釈するためのものではない。
【００９７】
以下、タスク実行部２００に割り当てられた、タスク、サブタスクおよび逐次処理タスクを、まとめて「タスク」と略記することがある。
【００９８】
図２８に示すスケジュールデータは、図２９に示したタスクの割り当ての様子に対応している。図２８に示すように、スケジュールデータは、例えば、タスクＩＤ、割当先ＩＤ、処理対象レコード、優先度、タスク種別および集約先タスクＩＤを含む。
【００９９】
タスクＩＤは、あるタスクを他のタスクから識別する識別子である。割り当て先ＩＤは、当該タスクを処理するタスク実行部２００を識別する情報である。処理対象レコードは、タスクの処理対象であるレコードを示す情報である。優先度は、タスク実行部２００に複数のタスクが割り当てられた場合の、タスクが処理される順番を示す情報である。図２８に示される例では、優先度は、小さい値ほど優先度が高いことを表している。タスク種別は、当該タスクが、分割されていないタスクなのか（Normal）、サブタスクなのか(Parallelized)、あるいは逐次処理タスクなのか(Sequential)を示す情報である。集約先タスクＩＤは、サブタスクに対応する逐次処理タスクのタスクＩＤである。
【０１００】
処理対象レコードは、例えば、逐次処理が実行される単位を決定する属性（支店名）の値もしくは値域や、逐次処理が実行される順序を決定する属性（取引時刻）の値もしくは値域、またはその組み合わせで指定されていても良い。
【０１０１】
サブタスク(Parallelized)の処理対象レコードは、サブタスクに対応するタスクの処理対象であるレコードを、タスク実行部２００の数でハッシュ分散することにより決定されてもよい。例えば、サブタスクの処理対象であるレコードは、ハッシュ値の辞書順で、各タスク実行部２００に振り分けられても良い。
【０１０２】
図３０は、タスク実行部２００の動作を説明するフローチャートである。図３０に示すように、タスク実行部２００は、割り当て部２０により割り当てられたタスクがなくなるまで以下の処理を繰り返す（Ｄ１００）。
【０１０３】
タスク実行部２００は、割り当てられたタスクのうち優先度の高いタスクを一つ取り出す。そしてタスク実行部２００は、取り出したタスクが逐次処理タスク(Sequential)であるかを判定する（Ｄ１１０）。取り出したタスクが逐次処理タスク(Sequential)であれば、Ｄ１５０の処理に進む。取り出したタスクが逐次処理タスクでなければ（Normal または Parallelized）、タスク実行部２００は、取り出したタスクの処理対象レコードをデータ格納部３００より取得し、当該タスクを実行する（Ｄ１２０）。
【０１０４】
タスク実行部２００は、取り出したタスクがサブタスク(Parallelized)であるかを判定する（Ｄ１３０）。取り出したタスクがサブタスク(Parallelized)であれば、サブタスクを実行後、集約先タスクＩＤに対応する逐次処理タスクに対して、処理の完了を通知する（Ｄ１４０）。取り出したタスクがサブタスク(Parallelized)でなければ（Normal）、Ｄ１００の処理に戻り、次に優先度の高いタスクを取り出す。
【０１０５】
Ｄ１１０の処理で、タスク実行部２００が、逐次処理タスク(Sequential)を取り出した場合、タスク実行部２００は、当該逐次処理タスクに対応するサブタスクの実行が完了するまで待ち（Ｄ１５０）、逐次処理タスクを実行できるところまで実行する（Ｄ１６０）。タスク実行部２００が、逐次処理タスクの実行を完了したか否かを判定する（Ｄ１７０）。タスク実行部２００が、逐次処理タスクの実行を完了した場合、Ｄ１００の処理に進み、逐次処理タスクの実行を完了していないなら、対応するサブタスクの実行完了を待つ（Ｄ１５０）。
【０１０６】
以上に説明したように、第８の実施形態にかかるデータ処理装置１０００では、割り当て部２０により出力された結果に基づいて、タスク実行部２００がタスクを実行する。
【０１０７】
＜第８の実施形態の変形例＞
なお、タスク処理部２２０は、割り当てられたタスクを実行する際、他のタスク処理部２００と、タスクの進捗状況を共有しても良い。図３１は、タスクの進捗状況が共有される場合のスケジュールデータの一例を示す図である。図３１に示されるように、スケジュールデータは、タスクＩＤ毎に、例えば、未実行、実行中、実行完了の三状態を保持する進捗の項目を含む。
【０１０８】
第８の実施形態の変形例にかかるタスク処理部２２０は、割り当てられたタスクが実行済みであって、他のタスク実行部２００に割り当てられたタスクが未実行である場合に、前記未実行のタスクを代わりに実行する。例えば図３２に示される例では、タスク実行部２００Ａが、タスクＩＤ「Ｆ」に対応するタスクの実行を完了した時点で、他に割り当てられたタスクが無い。そこで、タスク実行部２００Ａは、タスク実行部２００ＢからタスクＩＤ「Ｇ」に対応するタスクを代わりに実行しても良い。
【０１０９】
第８の実施形態の変形例にかかるデータ処理システム１０００は、かかる構成を有することにより、たとえ、実行時にシステム障害やタスクの見積もり誤差のため、タスクの処理時間が増減したとしても、動的にタスクの実行を平準化することができる。さらに、割り当て部２０が、処理時間が長いタスクを優先して実行するようにスケジュールすると、タスク処理部２２０間で、細かいタスクで再分配するので、タスクの実行は、より平準化されやすくなる。
【０１１０】
＜第９の実施形態＞
第９の実施形態にかかるデータ処理システム１０００は、分散並列実行基盤の上で実行される。図３３は、第９の実施形態にかかるデータ処理システム１０００のブロック図である。なお、図３３に示された各構成のうち、図２１に示された構成と実質的に同一のものには同一の符号が付されている。
【０１１１】
図３３に示すように、第９の実施形態にかかるデータ処理システム１０００は、スケジューリング部１００と、タスク実行部４００Ａ〜Ｎと、データ格納部５００Ａ〜Ｎとを含む。なお、タスク実行部４００Ａ〜Ｎは、タスク実行部４００と略記することがある。また、データ格納部５００Ａ〜Ｎは、データ格納部５００と略記することがある。
【０１１２】
図３３に示すように、データ処理システム１０００において、スケジュール部１００は、タスク分割部１０、割り当て部２０、ジョブ受付部３０、ジョブ分割部４０、レコード情報収集部１１０を含む。
【０１１３】
図３４は、図３３に示されるタスク実行部４００の構成を示すブロック図である。図３４に示されるように、第９の実施形態にかかるタスク実行部４００は、スケジュールデータ取得部４１０、レコード取得部４２０、シャッフルキー付与部４３０、レコード送信部４４０、レコード受信部４５０  タスク処理部４６０、出力部４７０を含む。
【０１１４】
スケジュールデータ取得部４１０は、スケジュール部１００により出力されたスケジュールデータを取得する。レコード取得部４２０は、スケジュールデータとは無関係に、当該タスク実行部４００の近傍にあるデータ格納部５００が記憶するレコードを取得する。シャッフルキー付与部４３０は、レコード取得部４２０が取得したレコードに、スケジュールデータに基づいたシャッフルキーを付与する。レコード送信部４４０は、レコードに付与されたシャッフルキーに基づいて、レコードを他のタスク処理部４００のレコード受信部４５０に対して送信する。
【０１１５】
レコード受信部４５０は、他のタスク処理部４００から、シャッフルキーが付与されたレコードを受信する。タスク処理部４６０は、レコードに付与されたシャッフルキーに基づいて、レコードに対してタスクを実行する。出力部４７０は、処理結果を出力する。
【０１１６】
図３５は、シャッフルキーの一例を説明する図である。図３５に示す例は、あくまで説明をわかりやすくするための一例に過ぎず、シャッフルキーを限定的に解釈するためのものではない。図３５に示したシャッフルキーは、図２９に示されるスケジュールデータに対応している。
【０１１７】
第９の実施形態にかかるデータ処理システム１０００では、各タスク実行部４００は、分配されたレコードに付与されたシャッフルキーの辞書順でタスクを実行する。そこで、シャッフルキー付与部４３０は、各タスク実行部４００が、スケジューリングされた順番通りに個々のタスクを実行するように、以下のようにシャッフルキーを構成する。
【０１１８】
シャッフルキー付与部４３０は、タスクの種別を示すタグをレコードの先頭に付与する。この時、サブタスクに対するレコードであるほうが、そうでないタスクに対するレコードよりも辞書順で先に並ぶようにタグを決める。図３５に示される例では、サブタスクに対するレコードであれば「0」を、分割されていないタスクであれば「１」を付与している。こうすることで、サブタスクがより先に実行されるようになる。
【０１１９】
そして、シャッフルキー付与部４３０は、実行の優先度を表すタグをレコードに付与する。図３５に示す例では、優先度の数字が小さいほど優先度が高いように表現してある。この情報は、タスク処理時間が長いものだけ付与してもよい。というのは、タスクの処理時間が短いものは、数が多くなりやすく、その順序はあまり影響を与えないからである。
【０１２０】
シャッフルキー付与部４３０は、タスク識別子を表すタグをレコードに付与する。この時、サブタスクのタスク識別子は「Ａ−１」、「Ａ−２」、「Ａ−３」…「Ａ−Ｎ」のようにナンバリングする。例えば「Ａ−１」のサブタスクを割り当てられたタスク実行部４００が、対応する逐次処理タスクも担当する、というルールが、予め設定されていても良い。
【０１２１】
図３５に示される例では、シャッフルキー自身に、割当先のタスク実行部４００を識別するタグが付与されている。しかし、シャッフルキーは必ずしもこのように構成されている必要はない。例えば、レコード送信部４４０が、逐次処理が実行される単位を決定する属性（支店名）の値を参照して、レコードを送信する先のタスク実行部４００を判断しても良い。レコード送信部４４０は、レコードの統計情報等の情報を用いて、レコードを送信する先のタスク実行部４００を判断しても良い。
【０１２２】
タスク処理部４５０は、シャッフルキーの辞書順でタスク識別子単位ごとにレコードを処理すればよい。
【０１２３】
次に、逐次処理タスクを担当するタスク実行部４００が、対応するサブタスクの実行が完了したか否かを判断する方法を説明する。例えば、タスク実行部４００が、タスク識別子を名前にもつ中間ファイルの生成有無を確認するという方法がある。他の方法には、例えば、データ処理システム１０００に、タスクの進捗状態を管理するマスタサーバを導入するという方法がある。逐次処理タスクを担当するタスク実行部４００は、例えば上記のような方法で、他のタスク実行部４００で実行されたサブタスクの進捗状況を認識し、計算に必要な中間データを適宜取得して、逐次処理タスクを実行すればよい。
【０１２４】
以上に説明したように、第９の実施形態にかかるデータ処理システム１０００によれば、分散並列実行基盤の上で動作する、並列処理と逐次処理とを含むデータ処理全体の処理時間を最適化するデータ処理システム、データ処理方法およびプログラムを提供できる。
【０１２５】
発明を実施するための形態に記載したテーブルは、請求の範囲に記載したデータセットに相当する。発明を実施するための形態に記載したタスク実行部２００またはタスク実行部４００は、請求の範囲に記載した計算機に相当する。
【０１２６】
この出願は、２０１２年１０月３１日に出願された日本出願特願２０１２−２３９７８２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１２７】
本発明の活用例として、企業の基幹システムのバッチ処理の高速化をあげることができる。
【符号の説明】
【０１２８】
１  ＣＰＵ
２  ＲＡＭ
３  ＨＤＤ
４  通信インタフェース
５  入力装置
６  出力装置
１０  タスク分割部
２０  割り当て部
２１  割り当て部
３０  ジョブ受付部
３１  ジョブ受付部
４０  ジョブ分割部
４１  ジョブ分割部
１００  スケジュール部
１１０  レコード情報収集部
２００Ａ〜Ｎ  タスク実行部
２１０  スケジュールデータ取得部
２２０  タスク処理部
２３０  進捗共有部
２４０  出力部
３００  データ格納部
４００Ａ〜Ｎ  タスク実行部
４１０  スケジュールデータ取得部
４２０  レコード取得部
４３０  シャッフルキー付与部
４４０  レコード送信部
４５０  レコード受信部
４６０  タスク処理部
４７０  出力部
５００Ａ〜Ｎ  データ格納部
１０００  データ処理システム
【図１】
2014068950.tif 000003
【図２】
2014068950.tif 000004
【図３】
2014068950.tif 000005
【図４】
2014068950.tif 000006
【図５】
2014068950.tif 000007
【図６】
2014068950.tif 000008
【図７】
2014068950.tif 000009
【図８】
2014068950.tif 000010
【図９】
2014068950.tif 000011
【図１０】
2014068950.tif 000012
【図１１】
2014068950.tif 000013
【図１２】
2014068950.tif 000014
【図１３】
2014068950.tif 000015
【図１４】
2014068950.tif 000016
【図１５】
2014068950.tif 000017
【図１６】
2014068950.tif 000018
【図１７】
2014068950.tif 000019
【図１８】
2014068950.tif 000020
【図１９】
2014068950.tif 000021
【図２０】
2014068950.tif 000022
【図２１】
2014068950.tif 000023
【図２２】
2014068950.tif 000024
【図２３】
2014068950.tif 000025
【図２４】
2014068950.tif 000026
【図２５】
2014068950.tif 000027
【図２６】
2014068950.tif 000028
【図２７】
2014068950.tif 000029
【図２８】
2014068950.tif 000030
【図２９】
2014068950.tif 000031
【図３０】
2014068950.tif 000032
【図３１】
2014068950.tif 000033
【図３２】
2014068950.tif 000034
【図３３】
2014068950.tif 000035
【図３４】
2014068950.tif 000036
【図３５】
2014068950.tif 000037
【国際調査報告】
2014068950.tif 000038
2014068950.tif 000039