(57)【要約】【課題】MapReduceフレームワークにおけるデータ処理の最適化のためのデバイスおよび方法を提供することを目的とする。【解決手段】大規模データ処理のためのマップリデュースフレームワークは、マスターノードにより実装され得る本発明の方法により最適化される。この方法は、ワーカーノードにより実行されたタスクの入力データを示す読み取りポインタ位置についてのデータをワーカーノードから受信し、これらのタスクから作業を横取りすることを有する。作業は、作業が横取りされるタスクによりまだ処理されていない入力データに適用される。【選択図】図１０
2014123365.tif 000002
【特許請求の範囲】
【請求項１】
マップリデュースフレームワークにおいてデータを処理する方法であり、マスターノードにより実行される方法であって、
入力データを入力データセグメントに分割するステップと、
前記入力データセグメントを処理するタスクをワーカーノードに割り当てるステップであり、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられるステップと、
前記タスクを実行するワーカーノードから受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かを判定するステップと、
新たなタスクを空きのワーカーノードに割り当てるステップであり、前記新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していない前記タスクによりまだ処理されていない前記入力データセグメントの部分（分割部分と呼ばれる）とされ、前記分割部分は、前記現在の読み取りポインタの位置の後に位置する前記入力データセグメントの部分であるステップと
を有する方法。
【請求項２】
請求項１に記載の方法の最後のステップは、
前記タスクから受信した前記データから、タスク毎の入力データ処理速度を判定するステップと、
データ処理速度がデータ処理速度閾値より下のタスク毎に、請求項１の最後のステップを実行するステップと
を下位に置き、
前記データ処理速度は、前記ワーカーノードから受信した前記データから取得された次の読み取りポインタから判定される、請求項１に記載の方法。
【請求項３】
入力データセグメントの終了の前の前記所定の閾値にまだ到達していないタスクを実行するメッセージをワーカーノードに送信するステップを更に有し、
前記メッセージは、前記メッセージが送信されたワーカーノードにより実行されるタスクについて入力データセグメントの終了を更新する情報を含む、請求項１又は２に記載の方法。
【請求項４】
入力データの処理を制限するためにタスクに提供される入力データストリームのファイル終了マーカを、前記分割部分の前に位置する入力データセグメントの部分に挿入するステップを更に有する、請求項１又は２に記載の方法。
【請求項５】
前記マスターノードのスケジューリングテーブルを更新するステップを更に有し、
前記スケジューリングテーブルは、割り当てられたタスクとワーカーノードとの関係を許可し、割り当てられた前記タスクの入力データセグメント部分の開始及び終了を規定する情報を有する、請求項１ないし４のうちいずれか１項に記載の方法。
【請求項６】
入力データセグメントの重複していない部分を処理するタスクの投機的実行を更に有する、請求項１ないし５のうちいずれか１項に記載の方法。
【請求項７】
マップリデュースフレームワークにおいてデータを処理するマスターデバイスであって、
入力データを入力データセグメントに分割する手段と、
入力データセグメントを処理するタスクをワーカーノードに割り当てる手段であり、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられる手段と、
前記タスクを実行するワーカーノードから受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かを判定する手段と、
新たなタスクを空きのワーカーノードに割り当てる手段であり、前記新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していない前記タスクによりまだ処理されていない前記入力データセグメントの部分（分割部分と呼ばれる）とされ、前記分割部分は、前記現在の読み取りポインタの位置の後に位置する前記入力データセグメントの部分である手段と
を有するマスターデバイス。
【請求項８】
前記タスクから受信した前記データから、タスク毎の入力データ処理速度を判定する手段と、
データ処理速度がデータ処理速度閾値より下であるか否かを判定する手段と
を更に有し、
前記データ処理速度は、前記ワーカーノードから受信した前記データから取得された次の読み取りポインタから判定される、請求項７に記載のマスターデバイス。
【請求項９】
入力データセグメントの終了の前の前記所定の閾値にまだ到達していないタスクを実行するメッセージをワーカーノードに送信する手段を更に有し、
前記メッセージは、前記メッセージが送信されたワーカーノードにより実行されるタスクについて入力データセグメントの終了を更新する情報を含む、請求項７又は８に記載のマスターデバイス。
【請求項１０】
入力データの処理を制限するためにタスクに提供される入力データストリームのファイル終了マーカを、前記分割部分の前に位置する入力データセグメントの部分に挿入する手段を更に有する、請求項７又は８に記載のマスターデバイス。
【請求項１１】
マスターノードのスケジューリングテーブルを更新する手段を有し、
前記スケジューリングテーブルは、割り当てられたタスクとワーカーノードとの関係を許可し、割り当てられた前記タスクの入力データセグメント部分の開始及び終了を規定する情報を有する、請求項７ないし１０のうちいずれか１項に記載のマスターデバイス。
【請求項１２】
入力データセグメントの重複していない部分を処理するタスクの投機的実行を行う手段を有する、請求項７ないし１１のうちいずれか１項に記載のマスターデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、MapReduceフレームワークにおけるデータ処理に関する。MapReduceモデルは、大規模なデータ処理を可能にする１つの方法として、Google  Inc.で開発された。
【背景技術】
【０００２】
MapReduceは、大規模なデータセットを処理するためのプログラミングモデルであり、Googleによるモデルの実装名である。MapReduceは、典型的にはコンピュータのクラスタで分散した計算を行うために使用される。このモデルは、関数型プログラミングで一般的に使用される“マップ（map）”及び“リデュース（reduce）”関数により引き起こされる。MapReduceは、マスターノードが特定の部分問題をそれぞれ扱うマップタスクへの問題の分割を定め、これらのマップタスクをワーカーノード（worker  node）に割り当てる“マップ”ステップを有する。このマスタータスクはまた、“スケジューリング”タスクとも呼ばれる。このため、マスターは、問題入力データを分割し、それぞれの入力データ部分をマップタスクに割り当てる。ワーカーノードは、部分問題を処理し、マップタスクの終了時にマスターノードに通知する。MapReduceは、マスターノードが“リデュース”動作をいくつかのワーカーノードに割り当てる“リデュース”ステップを更に有する。いくつかのワーカーノードは、全ての部分問題への解答を集め、出力（元から解決しようとしていた問題への回答）を形成するために、これらを何らかの方法で結合する。
【０００３】
MapReduceは、マップ及びリデュース動作の分散処理を可能にする。それぞれのマッピング動作が互いに独立していると仮定すると、マップは並列に実行可能である。同様に、一式の“リデューサ（reducer）”がリデュース段階を実行可能である。この処理は、連続的なアルゴリズムに比べて非効率であるように見えるが、MapReduceは“商品（commodity）”のサーバが扱うことができるものよりかなり大きいデータセットに適用可能である。大規模なサーバファームは、数時間のみでペタバイトのデータをソートするためにMapReduceを使用することができる。MapReduceは、典型的には、“巨大なデータ（big  data）”の処理に適している。並列処理はまた、動作中のサーバ又は記憶装置の部分的な故障から回復する可能性も提供する。１つのマッパ（mapper）又はリデューサ（reducer）が故障した場合、入力データが依然として利用可能であることを仮定すると、作業は再スケジューリング可能である。MapReduceの一般的なオープンソースの実装は、Apache  Hadoopである（出典：Wikipedia）。
【０００４】
MapReduceは、マスターによるスケジューリングを容易にし、耐故障性を向上するために、タスクの“静的（static）”な分離に依存する。タスクの静的な分離は、マスターノードの“スケジューラ（scheduler）”タスクにより処理される。“静的”という用語は、この文脈において、タスクが実行前に同じサイズの小さいタスクに分割されることを意味する。タスクは、プログラム／関数と入力データとの組み合わせであり、タスクの分割は、入力データを部分に分割し、様々な分割されたデータ部分でプログラムを提供する複数のタスクを生成することを含む。
【０００５】
Blumofe他は、プロセッサが他のプロセッサから作業を横取りする作業の横取り（work  stealing）の利点を、FOCS  1994（an  Annual  IEEE  Symposium  on  Foundations  of  Computer  Science）の文献“Scheduling  Multithreaded  Computations  by  Work  Stealing””に記載している。この技術は、異種のタスクを処理することにうまく適合する。しかし、これは、依存しているタスク（例えば、スレッドの間で共有メモリを用いた単一の機械で実行されるタスク）の間の作業の横取りに限定されている。この技術は、MapReduceに適用できない。この理由は、MapReduceの枠組みは、タスクが独立しており、スケーリング及び耐故障性を向上させるために入力データの静的な分割を可能にするという仮定に依存するからである。
【０００６】
“落伍者（stragglers）”（すなわち、遅く計算し、データ処理システムの性能を低減する機械）に対処するため、MapReduceは、タスクの１つが他より速く実行されることを期待して、タスクのコピーの同時実行を有する“投機的実行（speculative  execution）”として知られる機構を有する。この改善は、異種のリソースが使用される環境における性能の利得を可能にする。これは、タスクの不均一性（すなわち、或るタスクが他より多くの計算能力を必要とし得ること）に対処するのには適していない。
【０００７】
Indiana  University  of  Bloomington,  USAのGuo他は、文献“Improving  MapReduce  Performance  in  Heterogenous  Network  Environments  and  Resource  Utilisation”において、MapReduceでのマップ及びリデュースのタスクがワーカーノードによりホストされるマップ及びリデュース“スロット（slot）”に割り当てられることを記載している。各ワーカーは、タスクが割り当てられるユーザ設定可能な数のマップ及びリデューススロットを有する。基礎となるリソースの部分は、スロット毎に確保される。全てのスロットが同時に使用される場合、リソースの利用は最適になる。しかし、数千のノードのGoogle生成クラスタの収集された利用データは、CPU利用がほとんどの時間で最適からかけ離れていることを示している。著者は、Hadoopに適用されたときのMapReduceの枠組みのリソース利用は、全てのタスクスロットを埋めるのに十分なタスクが存在しない場合に非効率になることを認識した。各ワーカーノードは、ノード毎にユーザにより設定可能な複数のマップ及びリデューススロットを有する。全てのタスクスロットを埋めるのに十分なタスクが存在しない場合、確保されたリソースは浪費される。MapReduceの性能を改善するために、Guo他は、リソースの横取りを提案しており、実行デバイスの不均一性に対処するため、動作中のタスクが“投機的実行”（すなわち、同じタスクの並列実行（“コピー”又は“競合”タスク））のための確保された“アイドル”リソースを横取りすることを可能にしている。複数のタスクT1〜Tnのそれぞれについて、タスクの総数がスロットの数に等しくなるように、タスクが再実行（前述の“投機的実行”）される。タスクの再実行は、“アイドル”スロットに確保されたリソースを使用する。
【０００８】
処理速度を改善するためのこれらの従来技術の取り組みは、前述の静的な分割を通じて限定されている。MapReduceの現在の手法は、負荷バランシングを改善して最終的にデータ処理の性能を改善するために、この静的な分割に関するパラメータを調整することである。しかし、この方策は、熟練した人の介入を必要とする。この理由は、処理される入力データの正確な認識を必要とするからである。入力データがサイズで小さすぎるブロックに分割されないように注意が払われなければならない。この理由は、マップタスクの追加は、分割タスク毎に必要なオーバーヘッドを増加させるからである。オーバヘッドの例は、同期のための時間、タスクの転送及び開始のための時間、結果の送信、全ての結果のマージである。
【０００９】
性能を改善するための更に他の方策は、Guoにより議論されている“リソースの横取り（resource  stealing）”に対して、“作業の横取り（work  stealing）”と呼ばれるものである。Al-Obaidi他は、文献“A  partial  multi  stealing  scheduling  model  for  divide  and  conquer  problems””,    ICCCE  2012,  3-5  July  2012で作業の横取りを議論している。しかし、Al-Obaidi他により議論されている作業の横取りは、マルチコアプロセッサアーキテクチャを対象としており、未使用のプロセッサコアに与えるためにタスクスレッドの横取りによる作業の横取りを議論している。この作業の横取りの方策は、マルチスレッドのタスク及びマルチコアプロセッサのために設計されており、マルチスレッドでないタスク又は単一コアのノードの高速な実行をもたらさない。更に、この方策は、複数の未使用のプロセッサコアに制限される。最後に、Al-Obaidi他は、Blumofe他と同様である。全てのこれらの欠点は、これらの方策がMapReduceモデルのアプリケーションに適さないようにしている。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来技術は、タスクの実行の最適化に関する。すなわち、タスクへの静的な分割が行われている。静的な分割は、異なる分割されたタスクの間の不均一性及び異なる実行ノードの間の不均一性を考慮しないため、最適ではない。タスク及びノードの不均一性の双方に動的に適合するMapReduceに基づく方法を提案することが有利である。
【００１１】
従って、従来技術の対策の更なる最適化の必要がある。
【００１２】
本発明は、従来技術のいくつかの不都合な点を軽減することを目的とする。
【課題を解決するための手段】
【００１３】
このため、本発明は、マップリデュースフレームワークにおいてデータを処理する方法を有し、この方法はマスターノードにより実行され、入力データを入力データセグメントに分割し、入力データセグメントを処理するタスクをワーカーノードに割り当て、ここで、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられ、タスクを実行するワーカーノードから受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かを判定し、新たなタスクを空きのワーカーノードに割り当てることを有する。新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクによりまだ処理されていない入力データセグメントの部分（分割部分と呼ばれる）とされ、分割部分は、現在の読み取りポインタの位置の後に位置する入力データセグメントの部分である。
【００１４】
本発明の変形実施例によれば、この方法の最後のステップは、タスクから受信したデータから、タスク毎の入力データ処理速度を判定するステップと、データ処理速度がデータ処理速度閾値より下のタスク毎に、請求項１の最後のステップを実行するステップとを下位に置き、データ処理速度は、ワーカーノードから受信したデータから取得された次の読み取りポインタから判定される。
【００１５】
本発明の変形実施例によれば、この方法は、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクを実行するメッセージをワーカーノードに送信するステップを更に有し、メッセージは、メッセージが送信されたワーカーノードにより実行されるタスクについて入力データセグメントの終了を更新する情報を含む。
【００１６】
本発明の変形実施例によれば、この方法は、入力データの処理を制限するためにタスクに提供される入力データストリームのファイル終了マーカを、分割部分の前に位置する入力データセグメントの部分に挿入するステップを更に有する。
【００１７】
本発明の変形実施例によれば、この方法は、マスターノードのスケジューリングテーブルを更新することを更に有し、スケジューリングテーブルは、割り当てられたタスクとワーカーノードとの関係を許可し、割り当てられたタスクの入力データセグメント部分の開始及び終了を規定する情報を有する。
【００１８】
本発明の変形実施例によれば、この方法は、入力データセグメントの重複していない部分を処理するタスクの投機的実行を更に有する。
【００１９】
本発明はまた、マップリデュースフレームワークにおいてデータを処理するマスターデバイスに該当し、このデバイスは、入力データを入力データセグメントに分割する手段と、入力データセグメントを処理するタスクをワーカーノードに割り当て、ここで、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられる手段と、タスクを実行するワーカーノードから受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かを判定する手段と、新たなタスクを空きのワーカーノードに割り当てる手段とを有する。新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクによりまだ処理されていない入力データセグメントの部分（分割部分と呼ばれる）とされ、分割部分は、現在の読み取りポインタの位置の後に位置する入力データセグメントの部分である。
【００２０】
本発明によるデバイスの変形実施例によれば、このデバイスは、タスクから受信したデータから、タスク毎の入力データ処理速度を判定する手段と、データ処理速度がデータ処理速度閾値より下であるか否かを判定する手段とを更に有し、データ処理速度は、ワーカーノードから受信したデータから取得された次の読み取りポインタから判定される。
【００２１】
本発明によるデバイスの変形実施例によれば、このデバイスは、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクを実行するメッセージをワーカーノードに送信する手段を更に有し、メッセージは、メッセージが送信されたワーカーノードにより実行されるタスクについて入力データセグメントの終了を更新する情報を含む。
【００２２】
本発明によるデバイスの変形実施例によれば、このデバイスは、入力データの処理を制限するためにタスクに提供される入力データストリームのファイル終了マーカを、分割部分の前に位置する入力データセグメントの部分に挿入する手段を更に有する。
【００２３】
本発明によるデバイスの変形実施例によれば、このデバイスは、マスターノードのスケジューリングテーブルを更新する手段を更に有し、スケジューリングテーブルは、割り当てられたタスクとワーカーノードとの関係を許可し、割り当てられたタスクの入力データセグメント部分の開始及び終了を規定する情報を有する。
【００２４】
本発明によるデバイスの変形実施例によれば、このデバイスは、入力データセグメントの重複していない部分を処理するタスクの投機的実行を行う手段を更に有する。
【図面の簡単な説明】
【００２５】
【図１】従来技術のMapReduce方法の原理を示すブロック図
【図２】MapReduceの枠組みに従ったデータ処理のための従来技術の大規模データ処理システムのブロック図
【図３】MapReduce方法によるデータ処理の従来技術の方法のフローチャート
【図４】マスターノードにより行われるマッピングタスクを示す図３のフローチャートの詳細
【図５】入力データを処理するワーカーを表すブロック図
【図６】本発明の非限定的な変形実施例によるマッピングタスクのフローチャート
【図７】本発明の非限定的な実施例による入力データファイルの分割を示すブロック図
【図８】本発明によるデバイスの非限定的な実施例のブロック図
【図９】本発明による方法の非限定的な実施例を示すシーケンス図
【図１０】非限定的な実施例による本発明の方法のフローチャート
【発明を実施するための形態】
【００２６】
本発明の更なる利点は、本発明の特定の非限定的な実施例の説明を通じて明らかになる。実施例について図面を参照して説明する。
【００２７】
理解を助けるため、図面に共通する同一の要素を示すために、可能である場合には同一の参照符号が使用される。
【００２８】
図１は、従来技術のMapReduce方法の原理を示すブロック図である（出典：Wikipedia）。
【００２９】
“マスター”ノード101は、（矢印1000を介して）入力データ（“問題データ”）100を取得し、“マップ”ステップ1010において、これを“ワーカー”ノード102〜105に分配される小さい部分問題に分割する（矢印1001、1003、1005）。ワーカーノードは、小さい問題を処理し（矢印1002、1004、1006）、タスクの完了をマスターノードに通知する。“リデュース”ステップ1011において、マスターノードは、いくつかのワーカーノードに“リデュース”動作を割り当てる。これは、全ての部分問題への解答を収集し、（矢印1007を介して）出力（“解答データ”）106を形成するために、これらを何らかの方法で組み合わせる。
【００３０】
図２は、MapReduceの枠組みによる従来技術の大規模データ処理システムのブロック図である。図１と共通する要素は、その図面について既に説明しており、ここでは再び説明しない。マスター処理201は、ファイルF1〜Fn（1000）に格納された問題データ100を分割する。これは、ワーカーノード202〜205に割り当てるタスクにされる。マスター処理はまた、リデュースタスクをワーカーノード（ワーカーノード210及び211等）に割り当てる役目もする。ノード202〜205は、中間データ値2000を生成する。中間データ値2000は収集され、中間ファイルa（206）、b（207）〜n（209）に書き込まれる。中間結果が取得されたことをマスターが通知された場合、マスターは、リデュースタスクをワーカーノード210〜211に割り当てる。これらの処理は、中間ファイル206〜209からの入力データを取得し（2001）、データをマージ及び結合し、結果の解答データ106を格納する（2002）。MapReduceにより扱われるのに適した典型的な問題は、ショッピングウェブサイトの顧客の性別及び平均年齢のカウントである。この場合、入力データ100は、ショッピングウェブサイトの顧客購入データベースである。商業上で大成功したウェブサイトは、その顧客データも大きい（数テラバイトのデータ）。データは、ファイルF1〜Fnに格納される。マスターは、各ファイルを64Mbyteのセグメントに分割する。ワーカーノードのリストを用いて、マスターは、入力データの各セグメントをタスク及びワーカーノードに帰属させるスケジューリングテーブルを確立する。発明者のシナリオによれば、ワーカーノードにより実行されるタスクは、２つ（男性／女性の購入者の数の計算及び購入者の平均年齢の計算）である。各ワーカーノード202〜205は、その中間結果を中間ファイル206〜209の１つに格納する。例えば、中間ファイル“a”206は、ファイルF1の第１のセグメントからの女性の顧客の数と、顧客の平均年齢とを有する。一方、中間ファイル“b”207は、ファイルF1の第２のセグメントの顧客のクライアントの数及び平均年齢を有し、中間ファイル“n”は、ファイル“n”の第nのセグメントで計算された女性の顧客の数及び顧客の平均年齢を有する。タスクが終了したワーカー202〜205についてマスターが通知された場合、リデュースタスクをワーカーノード（ワーカー210及び211）に割り当てる。これらのワーカーは、リデュースタスクを実行し、中間ファイル“a”〜“n”の内容を読み取り、２つの結果（すなわち、女性の顧客の数及び顧客の平均年齢）の出力を生成し、これが解答データ106に格納される。
【００３１】
図３は、マスター処理のフローチャートである。
【００３２】
初期化ステップ310において、処理に必要な変数及びパラメータが初期化される。ステップ302において、マスターノードは、入力ファイルを、典型的には数十メガバイト（例えば、16又は64Mbyte）のセグメント（任意選択のパラメータを介してユーザにより制御可能な選択肢）に分割する。次にステップ303において、マスターは、アイドルのワーカーが存在するか否かを確認する。存在しない場合、このステップがループする。アイドル（又は“空き”）のワーカーが存在する場合、ステップ305において、マスターは、アイドルのワーカーに対して行うべきマップタスクが依然として存在するか否かを確認する。存在する場合、マスターは、アイドルのワーカーに対してこれらのマップタスクを開始するように命令し（矢印3001及びステップ304）、矢印3000を介してステップ303に戻る。行われるべきマップが存在しない場合、リデュースタスクがステップ306で開始される。これらが行われると、処理はステップ307で終了する。
【００３３】
以下の表１は、マスターにより保持される従来技術のマスターノードのタスクスケジューリングテーブルの例を提供する。
【００３４】
【表１】
2014123365.tif 000003
マップタスクM1は、例えば、顧客データベースにおける顧客の平均顧客年齢の計算に対応する。マップタスクM2は、例えば、女性の顧客の数の計算に対応する。ワーカーW1は、タスクM1を実行し、ファイルF1のバイト0〜16Mbyteから入力データセグメントを取得しなければならない。ワーカーW2は、同じファイルの同じセグメントからタスクM2を実行する。ワーカーW3は、ファイルF2のセグメント16〜32Mbyteから入力データによってタスクM1を実行する。W4は、ワーカーW3と同じ入力データでタスクM2を実行する。ワーカーW5は、ワーカーW1により実行されたタスクM1のコピーを実行する（すなわち、投機的実行のため）。ワーカーW6は、W4により実行されるタスクと同じタスクを投機的に実行する。
【００３５】
図４は、図３のステップ304の従来技術の実装のフローチャートである。ステップ304aは、マップタスクが開始されるステップを表す。ステップ304aの入力は、ステップ305から生じる矢印3001である。出力は、ステップ303の入力に向かう矢印3000である。
【００３６】
ステップ3040において、全てのタスクが開始されたか否かが確認される。そうでない場合、ステップ3041において、まだ開始されていないタスクが開始され、ステップ304aはステップ303に戻る。全てのタスクが開始された場合、ステップ3045においてタスクが複数回開始されたか否か（すなわち、投機的実行）が確認される。そうでない場合、投機的に実行されておらず、まだ終了していないタスクは、アイドルのワーカーノードで同時に開始される。すなわち、ステップ3046において、これらのタスクは投機的に実行され（投機的実行の概念は前述した）、これにより、時間が得られる可能性を増加させる。ステップ304aは、ステップ303に続く。ステップ3045において、全てのタスクが複数回投機的に実行されたことが確認された場合、ステップ304aはステップ303に続く。
【００３７】
ワーカーにおけるタスクの開始は、ワーカーがタスク（実行する関数／プログラム）及びその入力データを取得するように命令するマスターにより行われる。例えば、表１に戻り、マスターは、ワーカーノードW1に対してマップタスクM1を実行し、ファイルF1のセグメント0〜16Mbyteからその入力データを取得するように命令する。他のマップタスクについても処理は同一である。
【００３８】
図５は、入力データを処理するワーカーで実行するタスクを表すブロック図である。特に、これは、それぞれワーカーノードW1、W2、W3及び4で実行するタスクT1（500）、T2（503）、T3（510）及びT4（513）と、それぞれセグメント505、506及び515、516を有するファイルF1（502）及びF2（512）とを表す（ワーカーノード毎に１つのタスクの分配は、限定的ではなく単なる例である。ワーカーノードは、その構成及び性能に従って複数のタスクを実行してもよい）。タスクを表すブロック500、503、510及び513の中に、読み取りポインタの位置のファイルからの入力ラインを読み取り、読み取られた入力ラインを渡すプログラム／関数（例えば、‘avg_age’又は‘female_clients’）を実行する処理が示されている。矢印501、504、511及び514は、読み取りポインタを表す。プログラム／関数“read_entry”は、セグメントの終了までの入力データファイルを読み取る（例えば、0から16Mbyteのセグメントの終了までのT1及び16〜32MbyteのT2）。
【００３９】
図６は、別の実施例による図３のステップ304のフローチャートである。これは、本発明の特定の非限定的な実施例を示している。
【００４０】
前の図面と共通する要素は、これらの図面について既に説明しているため、ここでは説明は繰り返さない。
【００４１】
背景技術で説明したように、従来技術は、タスクの実行の最適化に関する（すなわち、タスクの静的な分割が行われている）。静的な分割は、異なる分割されたタスク及び異なるワーカーノードの間の不均一性（すなわち、タスクは他より複雑でもよく、ワーカーノードは他より遅くてもよい）を考慮していないため、最適ではない。
【００４２】
従って、ステップ304bは、可能な場合には動的な作業の横取りの更なるステップを有する。ステップ3040において全てのタスクが開始されたことが確認された場合、ステップ3042において、入力データセグメントの終了から依然として所定の閾値の前にある読み取りポインタを有するタスクが存在するか否かが判定される。入力データセグメントは更に分割されてもよい。すなわち、入力データファイルからの入力データは、他のワーカーに移転（すなわち、‘横取り（stolen）’）されてもよい。例えば、所定の量は、例えば1Mbyteに設定されたユーザ設定可能なパラメータである。ステップ3042のこの判定は、タスクの読み取りポインタを確認することにより行われてもよく、又は、ワーカーがワーかにより実行されているタスク毎に読み取りポインタの通知をマスターに定期的に送信し、更新され続けるようにしてもよい。前の例では、ステップ3042において、例えば、ワーカーW1により実行されたタスクM1の入力データ読み取りポインタ501が依然として15Mbyteの閾値の前にあるか否かが判定される。依然として入力データセグメントの終了から所定の閾値の前にある読み取りポインタを有するタスクが存在しない場合、ステップ3042はステップ3045に続く。しかし、このようなタスクが存在する場合、ステップ3044が実行され、ここで新たな（“コピー”）タスクが生成され、新たなタスクがアイドルのワーカーに割り当てられて開始される。新たなタスクは、元のタスクによりまだ処理されていない‘元の’タスク（すなわち、新たな“コピー”タスクが生成された元のタスク）の入力データセグメントの入力データ部分として自分を取得する。次にステップ3044は（矢印3001を介して）ステップ303に続く。変形実施例では、ステップ3042とステップ3044との間に判定ステップ3043が挿入され、横取りが可能であるか否かが判定される。すなわち、ステップ3042において判定されたワーカーが、そのタスクの読み取りポインタ値を取得するためにマスターにより明示的に問い合わされる。場合によって、このような問い合わせは、ワーカーがそのタスクを一時停止することを必要とする。この変形は、ステップ3042に判定がもはや正確でない読み取りポインタ値に基づくことを回避するという利点を有する。
【００４３】
作業がタスクから横取りされると、マスターはスケジューリングテーブルを更新する。例えば、以下の表２を参照のこと。表１に表されるスケジューリングテーブルへの適合がイタリック体の下線の印刷で記されている。
【００４４】
【表２】
2014123365.tif 000004
認識できるように、タスクM1はタスクM1及びM1’に分割される。タスクM1の入力データファイルの終了は、10Mbyteに設定されるように変更され、ワーカーW7で実行する新たな“分割”タスクM1’が生成される。ワーカーW7は、10Mbyteで開始して16Mbyteで終了するセグメントの入力ファイル1として有する
図７は、本発明の更なる変形実施例のフローチャートである。前の図面に共通する要素は、ここでは再び説明しない。
【００４５】
ステップ3040において全てのタスクが開始されたことが確認された場合、ステップ3047において、複雑なタスク又は遅いワーカーで実行されているタスクが存在するか否か（すなわち、“落伍者”タスクが存在するか否か）が判定される。これは、ワーカーからマスターにより収集された統計に基づいてマスターにより判定されてもよい。これらの統計に基づいて、入力データ処理速度は、タスクが各入力ファイルを順次に処理するときのタスクによる時間でのデータ読み取り量を確認することにより推測されてもよい。入力データ処理速度は、次の読み取りポインタ値から取得されてもよく、例えば、Kbyte/sで表されるビットレートである。入力データ処理速度が閾値より下であるか否かが判定されてもよい。一例として、このような閾値は、平均処理速度に所定の許容範囲を加えたものから判定されてもよい。この情報に基づいて、入力ファイル処理速度がほとんどのタスクについてほぼ同じであるが、いくつかが他よりかなり遅い場合、遅いタスクが実行されているワーカーノードが遅い可能性があり、その場合、投機的実行が最善の対策であると思われる。これにより、ステップ3045に続く。同じタスクが異なるノードで投機的に実行され、投機的に実行されたタスクの入力データ処理速度が依然として前述の閾値より下に留まる場合、このタスクは平均のタスクよりおそらく複雑であり、作業の横取りが非常に役に立つ可能性が高い。これにより、ステップ3042に続く。全てのタスクが入力データ処理速度における大きい分散で実行するが、実行環境が似ている場合（例えば、同じハードウェア、同じ負荷等）、作業の横取りが同様に役に立つ可能性が高く、ステップ3047はステップ3042に続く。入力データ処理速度が全てのタスクについてほぼ同じである場合（すなわち、複雑なタスク又は他より遅いノードが存在しない場合）、ステップ3047はステップ3045に（すなわち、図７の‘n/a’（該当なし）で印を付けられたステップ3047の出口を介して）続き、作業の横取りが投機的実行より役に立つという明確な証拠なしに投機的実行の初期設定の方策を適用する。この目的は、手持ちの状況に最も適合された方策（すなわち、全体のタスク処理を高速化する可能性が高いもの）を採用することである。変形実施例によれば、初期設定の方策は、作業の横取りを適用することである。初期設定の方策は、ユーザ設定可能なパラメータ設定により指定されてもよい。
【００４６】
図８は、本発明によるマスターノードデバイスの非限定的な実施例のブロック図である。このデバイスは、CPU若しくは中央処理装置又はプロセッサ810と、クロックユニット811と、ネットワークインタフェース812と、I/Oインタフェース813と、不揮発性メモリ815と、揮発性メモリ816とを有する。全てのこれらの要素は、データ又は通信バス814により相互接続される。デバイスは、接続8000を介して通信ネットワークに接続されてもよく、接続8001を介して外部入出力デバイス（例えば、キーボード、スクリーン、外部データ記憶装置）に接続されてもよい。CPU810は、本発明の方法を実装する命令のようなコンピュータ可読命令を実行可能である。不揮発性メモリ815は、コンピュータ可読命令のコピーをメモリ領域8151に格納する。不揮発性メモリ815は、電力停止から再起動するときにデバイスを既知の状態に戻すために使用されるため、永続的に保存される必要がある変数及びパラメータのような永続的データをメモリ領域8152に更に格納する。揮発性メモリ816は、不揮発性メモリ815のメモリ領域8151に格納されたコンピュータ可読命令のコピーを有するメモリ領域8161を有する。この命令は、デバイスの起動時にメモリ領域8161にコピーされる。揮発性メモリ816は、例えばメモリ領域8161に格納されたコンピュータ可読命令の実行中に使用される変数のための、一時的な永続的でないデータ記憶に使用されるメモリ領域8162を更に有する。クロックユニット811は、タイミング及び同期のために異なる要素810及び812〜816により使用されるクロック信号を提供する。
【００４７】
デバイス800は、入力データを入力データセグメントに分割する手段（CPU810）と、入力データセグメントを処理するタスクをワーカーノードに割り当て、ここで、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられる手段（CPU810）と、タスクを実行するワーカーノードから受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かを判定する手段（CPU810）と、新たなタスクを空きのワーカーノードに割り当てる手段（CPU810）とを有する。新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクによりまだ処理されていない入力データセグメントの部分（分割部分と呼ばれる）とされ、分割部分は、現在の読み取りポインタの位置の後に位置する入力データセグメントの部分である。
【００４８】
このデバイスの変形実施例によれば、このデバイス800は、タスクから受信したデータから、タスク毎の入力データ処理速度を判定する手段（CPU810）と、データ処理速度がデータ処理速度閾値より下であるか否かを判定する手段（CPU810）とを更に有し、データ処理速度は、ワーカーノードから受信したデータから取得された次の読み取りポインタから判定される。
【００４９】
このデバイスの変形実施例によれば、このデバイス800は、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクを実行するメッセージをワーカーノードに送信する手段（ネットワークインタフェース812）を更に有し、メッセージは、メッセージが送信されたワーカーノードにより実行されるタスクについて入力データセグメントの終了を更新する情報を含む。
【００５０】
このデバイスの変形実施例によれば、このデバイス800は、入力データの処理を制限するためにタスクに提供される入力データストリームのファイル終了マーカを、分割部分の前に位置する入力データセグメントの部分に挿入する手段（CPU810）を更に有する。
【００５１】
このデバイスの変形実施例によれば、このデバイス800は、マスターノードのスケジューリングテーブルを更新する手段（CPU810）を更に有し、スケジューリングテーブルは、割り当てられたタスクとワーカーノードとの関係を許可し、割り当てられたタスクの入力データセグメント部分の開始及び終了を規定する情報を有する。
【００５２】
このデバイスの変形実施例によれば、このデバイス800は、入力データセグメントの重複していない部分を処理するタスクの投機的実行を行う手段（CPU810）を更に有する。
【００５３】
図９は、本発明による方法の非限定的な変形実施例を示すシーケンス図である。垂直の線900、901、902及び903は、それぞれマスターノード、ワーカーノードW1、ワーカーノードW3及びワーカーノードW7を表す。矢印910〜915は、ノードの間で交換されるメッセージを表す。T0〜T3は、異なる時点を表す。T0において、マスターノードのマップタスクのスケジューリングテーブルが表１で表される。T0において、ワーカーノードW1  901及びW3  902により実行されたタスクの読み取りポインタが、メッセージ910及び911をこれらのノードに送信することにより取得される。例えば、このようなメッセージは、タスクの入力データ読み取りポインタの位置を送信する要求を有する。変形実施例によれば、新たなタスクが生成されるべきかを判定するときに（例えば、図６に示すステップ3042〜3044の間に、又は図７の3047を含むステップ3042〜3044の間に）読み取りポインタが進まないことをマスターが確保するため、要求は、実行されるマップタスクの実行を一時停止する。T1において、データは、W1で実行するタスクM1から受信され（矢印912）、ワーカーノードW3で実行するタスクM1から受信される（矢印913）。これらのデータから、マスターノードがこれらのワーカーで実行するタスクの読み取りポインタを判定してもよい。読み取りポインタは、これらのタスクの入力データである各入力データセグメントにおける位置を示す。マスターノードは、読み取りポインタが各入力データセグメントの終了の前の所定の閾値（例えば、1Mbyte）にあるか否かを判定する。図示のシナリオによれば、表１と一致して、これはW1により実行されたタスクM1の場合であり、マスターは、マップタスクのスケジューリングテーブルのエントリを更新し、表２を生じる（“更新”という用語は、新たなエントリの生成と、既存のエントリの変更とを有する）。T2において、マスターは、マップタスクM1が再開されることを示し、タスクM1の入力データセグメントの終了が更新されること（前の16Mbyteが現時点で10Mbyteに更新されること）をW1に通知するメッセージ914をW1に送信する。T3において、マスターは、新たなタスクM1’が帰属されることを示し、その入力データがファイルF1のセグメント10〜16Mbyte（すなわち、W1で実行しているタスクM1によりまだ処理されていない入力データの第２の部分）であることを通知するメッセージ（矢印915）を空き（又は“アイドル”）のW7（903）に送信する。図６に示すステップ3042〜3044又は図７に示すステップ3047を含むステップ3042〜3044は、所定の閾値に到達するまで（すなわち、入力データの異なる部分で動作する新たなタスクが生成され得るまで）繰り返されてもよい。例えば、ワーカーノード7の読み取りポインタが依然としてゆっくり進み、従って、タスクM1’の入力ファイルデータ処理速度が閾値より下である場合、空きのワーカーノードで実行される新たなタスクM1’’が生成されてもよい。新たなタスクM1’’は、W7に割り当てられ、そのノードによりまだ処理されていないセグメントの部分を入力データとして有する。
【００５４】
変形実施例によれば、入力データ処理速度が他のタスクより遅いという理由で（落伍者タスク）、新たなマップタスクの生成の候補であるワーカーノードは変更されないままであるが、タスクにより処理された入力データの各処理部分が変更されないままである新たなタスクが生成される。以下の表３を用いて例を示す。
【００５５】
【表３】
2014123365.tif 000005
例えば、タスクM1が落伍者タスクであることを検討すると、M1は変更されないままであるが、２つの更なるコピー（又は“競合”）タスクM1’及びM1’’が生成される。M1’及びM1’’のそれぞれは、M1により扱われる入力データの一部を扱う。他者の前に終了したタスク（コピー又は元のもの）は、扱う入力データに応じて他のタスクの実行をキャンセルする。これにより、リソースの浪費を回避する。例えば、W2が最初に終了した場合、W1及びW3はキャンセルされる。W3が最初に終了した場合、W2はキャンセルされる。従って、タスクが終了し、終了したタスクと重複する入力データを有する同じタスク（すなわち、“重複”するタスク）が存在する場合（同じプログラム／関数を実行することを意味する）、重複するタスクはキャンセルされる。従って、この方策は、作業の横取りと投機的実行との組み合わせであり、双方の利点を組み合わせる（すなわち、入力データセグメントの重複していない部分を処理するタスクの投機的実行）。タスク入力データ処理を高速化し得るという見込みで空きのリソースを同時に使用しつつ、実行されているタスクを変更しないままにする複数の理由が存在する。１つの理由は、タスクの入力データ処理速度が所与の時点で遅く、その入力データ速度が以前は十分であり、入力データ処理速度が改善すると予測する十分な理由が存在することである。他の理由は、例えば、ワーカーが実行しているタスクの入力データ読み取りポインタの位置を送信するマスターの要求に特定の遅延内に応答できなかったことである。更に他の理由は、タスクが重要であり、中断されてはならないと考えられることである。更に他の理由は、タスクM1がW2及びW1で投機的に実行されており、横取りが実行された場合、W1のみがセグメントの新たな終了を通知され、W2がW3と重複して変更されないままになることである。
【００５６】
図１０は、非限定的な実施例による本発明の方法の論理図である。
【００５７】
第１のステップ10000において、方法に使用される変数及びパラメータが初期化される。ステップ10001において、入力データは、入力データセグメントに分割される。ステップ10002において、入力データセグメントを処理するタスクは、ワーカーノードに割り当てられ、各ワーカーノードは、入力データセグメントを処理するタスクを割り当てられる。ステップ10003において、タスクを実行するワーカーノード（901、902、903）から受信したデータから、タスクにより処理された入力データセグメントの現在の読み取り位置を示す読み取りポインタが入力データセグメントの終了の前の所定の閾値にまだ到達していないか否かが判定される。ステップ10004において、新たなタスクが空きのワーカーノードに割り当てられる。新たなタスクは、入力データセグメントの終了の前の所定の閾値にまだ到達していないタスクによりまだ処理されていない入力データセグメントの部分（分割部分と呼ばれる）とされ、分割部分は、現在の読み取りポインタの位置の後に位置する入力データセグメントの部分である。分割する更なるタスクを見つけるため及び／又は空きのワーカーノードが利用可能になるときに、方法は、ステップ10003にループバックする。
【００５８】
本発明の実装は、図示の実施例に限定されない。読者は、図８が本発明を実装するマスターデバイス（又はマスター“ノード”）の非限定的な実施例であることを理解する。特に、本発明を実装するデバイスは、図示のものより多い要素又は少ない要素（例えば、複数の機能を実装する少ない要素又は更に基本的な機能を実装する多くの要素等）を有してもよい。
【００５９】
同様に、読者は、この方法又は本発明の実装が図面に示す実装に限定されず、方法のステップが異なる順序で又は並列して（例えば、処理時間を増すために）実行可能であることを理解する。
【００６０】
前述の変形は別々に使用されてもよく、本発明の特に有利な変形実施例を提供するためにこれらの間で組み合わされてもよい。
【００６１】
記載の実施例のいくつかはハードウェア要素の使用を説明しているが、ハードウェアにより実装されるものとして提示されたいくつかの機能は、本発明を実装するデバイスの製造コストを低減するために、代わりにソフトウェアで実装されてもよい。
【００６２】
或いは、本発明は、ハードウェアコンポーネントとソフトウェアコンポーネントとの組み合わせを使用して実装されてもよい。専用のハードウェアコンポーネントは、別法ではソフトウェアで実行される機能を提供する。特定の実施例によれば、本発明は、完全にハードウェアで、例えば、専用コンポーネントとして（例えば、ASIC（Application  Specific  Integrated  Circuit）、FPGA（Field-Programmable  Gate  Array）又はVLSI（Very  Large  Scale  Integration）として）実装され、或いは、デバイスに統合された別個の電子部品として又はハードウェア及びソフトウェアの組み合わせの形式で実装される。
【図１】
2014123365.tif 000006
【図２】
2014123365.tif 000007
【図３】
2014123365.tif 000008
【図４】
2014123365.tif 000009
【図５】
2014123365.tif 000010
【図６】
2014123365.tif 000011
【図７】
2014123365.tif 000012
【図８】
2014123365.tif 000013
【図９】
2014123365.tif 000014
【図１０】
2014123365.tif 000015
【外国語明細書】
2014123365000001.pdf