(57)【要約】【課題】ディスクのＩ／Ｏ性能を効率的に利用して並列分散処理の高速化を実現する。【解決手段】並列分散処理制御装置は、分割部と、割当部と、統合部とを備える。分割部は、受け付けたタスクを、演算部の数に応じた数のサブタスクに分割する。割当部は、サブタスクを演算部に割り当てる。統合部は、サブタスクを割り当てられた演算部において当該サブタスクを並列実行した処理結果を統合する。【選択図】図１
2014153935.tif 000002
【特許請求の範囲】
【請求項１】
受け付けたタスクを、演算部の数に応じた数のサブタスクに分割する分割部と、
前記サブタスクを前記演算部に割り当てる割当部と、
前記サブタスクを割り当てられた演算部において当該サブタスクを並列実行した処理結果を統合する統合部と、
を備える並列分散処理制御装置。
【請求項２】
複数の情報処理装置と、複数のコアを有するアクセラレータと、を備える並列分散処理制御システムであって、
前記複数の情報処理装置のうち１の情報処理装置は、
Mapタスクを、前記アクセラレータが有するコアの数に応じた数のサブタスクに分割する分割部と、
前記サブタスクを前記アクセラレータの複数のコアに割り当てる割当部と、
前記コアによる前記サブタスクの処理結果を統合する統合部と、
を備え、
前記アクセラレータは、前記複数のコアにおいて前記サブタスクを並列実行することを特徴とする並列分散処理制御システム。
【請求項３】
前記アクセラレータの複数のコアは各々、割り当てられたサブタスクの処理対象であるデータブロックを、情報処理装置配下の、当該データブロックを格納する記憶装置から直接読み出すことを特徴とする請求項２に記載の並列分散処理制御システム。
【請求項４】
前記アクセラレータの複数のコアは各々、割り当てられたサブタスクの処理対象であるデータブロックを、当該データブロックを格納する情報処理装置配下の記憶装置から当該情報処理装置のメモリを介して前記アクセラレータ上のメモリに転送された後に、前記アクセラレータ上のメモリから読み出して当該サブタスクを実行することを特徴とする請求項２に記載の並列分散処理制御システム。
【請求項５】
前記アクセラレータの複数のコアは、当該アクセラレータ上に各々に割り当てられる記憶領域を有し、前記サブタスクの実行により生成されたKey-Valueペアで当該記憶領域が満たされると、当該記憶領域に格納されたKey-Valueペアを、Keyをもとにソートして、ソート結果を、前記アクセラレータ上のグローバルバッファに記憶することを特徴とする請求項２から４のいずれか１項に記載の並列分散処理制御システム。
【請求項６】
前記分割部は、処理対象であるデータブロックのロード、ロードしたデータのデシリアライゼーション、Key-Valueペアの生成およびKey-Valueペアのソートのうち一部の処理を前記サブタスクに分割し、
前記割当部は、前記アクセラレータの複数のコア各々に割り当てられるサブタスクの処理対象ブロック数が略均等となるよう割り当てることを特徴とする請求項２から５のいずれか１項に記載の並列分散処理制御システム。
【請求項７】
複数の情報処理装置と、複数のコアを備えるアクセラレータと、を備える並列分散処理制御システムで実行される並列分散処理制御方法であって、
前記複数の情報処理装置のうち１の情報処理装置により、Mapタスクを、前記アクセラレータが有するコアの数に応じた数のサブタスクに分割する分割工程と、
前記１の情報処理装置により、前記サブタスクを前記アクセラレータの複数のコアに割り当てる割当工程と、
前記アクセラレータの複数のコアにより、前記サブタスクを並列実行する実行工程と、
前記１の情報処理装置により、前記サブタスクの処理結果を統合する統合工程と、
を含むことを特徴とする並列分散処理制御方法。
【請求項８】
コンピュータに、
Mapタスクを、アクセラレータが有するコアの数に応じた数のサブタスクに分割する分割ステップと、
前記サブタスクを前記アクセラレータの複数のコアに割り当てる割当ステップと、
前記アクセラレータの複数のコアに、前記サブタスクを並列実行させる実行ステップと、
前記コアによる前記サブタスクの処理結果を統合する統合ステップと、
を実行させるための並列分散処理制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列分散処理制御装置、並列分散処理制御システム、並列分散処理制御方法および並列分散処理制御プログラムに関する。
【背景技術】
【０００２】
従来、大容量のデータを高速に処理するために、データを分散して複数の情報処理装置に割り当て、複数の情報処理装置において並行して処理を実行する技術が知られている。たとえば、大規模分散処理技術の一つとして、Ｗｅｂのクロールデータやアクセスログなどの大量データ（ビッグデータ）を多数のコモディティサーバに分散させることで効率的にデータを処理するための技術が知られている。
【０００３】
中でも、分散化のフレームワークとして広く利用されている技術が、Googleにより提唱されたMapReduceである。MapReduceは、単純なプログラミングモデルを使用してコンピュータクラスタ上に大量のデータを分散させることができるフレームワークを提供する。Hadoop（登録商標）とは、MapReduceのオープンソースソフトウェア実装の一つである。Hadoopの中核をなすのは、大量データを分散して並列処理を可能にするフレームワークであるMapReduceと、高スループットのアプリケーションデータへのアクセスを実現する分散ファイルシステムであるＨＤＦＳ（Hadoop  Distributed  File  System（登録商標））である。
【０００４】
MapReduceでは、MapとReduceと呼ばれる２つの関数を記述することで、並列分散処理を実現する。まず、処理対象のデータを分割し、各Mapタスクに割り当てる。Mapタスクでは、割り当てられたデータを処理し、KeyとValueの組合せであるKey-Valueペアを生成する。そして、KeyごとにまとめられたデータをReduceタスクに渡す。Reduceタスクでは、Keyごとに処理を行い、結果を出力する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jeffrey  Dean  and  Sanjay  Ghemawat,  MapReduce:  Simplified  Data  Processing  on  Large  Clusters,  Proceedings  of  the  6th  Symposium  on  Operating  Systems  Design  and  Implementation  (OSDI  ’04)、２００４年１２月６日−８日
【非特許文献２】山田浩之、合田和生、喜連川優、「並列データインテンシブ処理基盤のＩ／Ｏ性能評価に関する実験的考察」、第４回データ工学と情報マネジメントに関するフォーラム（DEIM  2012）、D6-4,  ２０１２年３月
【非特許文献３】Matei  Zaharia,  Mosharaf  Chowdhury,  Tathagata  Das,  Ankur  Dave,  Justin  Ma,  Murphy  McCauley,  Michael  J.  Franklin,  Scott  Shenker,  Ion  Stoica,  Resilient  Distributed  Datasets:  A  Fault-Tolerant  Abstraction  for  In-Memory  Cluster  Computing,  Technical  Report  No.  UCB/EECS-2011-82,  July  19,  2011
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来は各Mapタスクの処理全体を単一のプロセス、単一のスレッドとして実行していた。各Mapタスクはたとえば、ディスク（記憶装置）からのデータロード、ロードしたデータのデシリアライゼーション、Key-Valueペアの生成、Keyによるソート、という一連の処理を含む。これらを単一のスレッドとして実行する場合、実行するＣＰＵ（Central  Processing  Unit）の性能によって処理速度が制限される。
【０００７】
また、処理を分散し複数のMapタスクを同時に並列して実行させて大量データを短時間で処理しようとした場合、並列して実行するMapタスクの数は、処理を行うサーバ等のＣＰＵのコア数程度までしか並列度を上げることによる性能向上は見込めない。このため、サーバに搭載するＣＰＵの数や性能等によって並列処理による性能向上が制約される。また、従来から、データをロードする際のデータのデシリアライゼーション等によってＣＰＵにかかる負荷が大きいことが知られている。
【０００８】
このように、従来の技術では、ＣＰＵ性能がボトルネックとなって、ディスクのＩ／Ｏ性能を十分に生かすことができない。すなわち、ディスクのＩ／Ｏ性能に余裕がある場合であっても、ＣＰＵ性能により処理量が制約され、ディスクのＩ／Ｏ性能を十分に生かすことができない。
【０００９】
従来、分散処理に使用していた磁気ハードディスクドライブ（ＨＤＤ：Hard  Disk  Drive）のＩ／Ｏ性能は、ＣＰＵの処理性能よりも低かったため、上述の問題は顕著ではなかった。しかし、ＳＳＤ（Solid  State  Drive）等のＩ／Ｏ性能の高いディスクがＨＤＤに取って代わると、上述の問題が顕著化する。
【００１０】
開示の実施の形態は、上記に鑑みてなされたものであって、ディスクのＩ／Ｏ性能を効率的に利用して並列分散処理の高速化を実現することができる並列分散処理制御装置、並列分散処理制御システム、並列分散処理制御方法および並列分散処理制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するために、本発明に係る実施の形態は、受け付けたタスクを、演算部の数に応じた数のサブタスクに分割し、サブタスクを演算部に割り当て、サブタスクを割り当てられた演算部において当該サブタスクを並列実行した処理結果を統合することを特徴とする。
【発明の効果】
【００１２】
本発明の実施の形態に係る並列分散処理制御装置、並列分散処理制御システム、並列分散処理制御方法および並列分散処理制御プログラムは、ディスクのＩ／Ｏ性能を効率的に利用して並列分散処理の高速化を実現することができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】図１は、第１の実施形態に係る並列分散処理制御装置の構成の一例を示す図である。
【図２】図２は、第１の実施形態に係る並列分散処理制御装置における処理の流れの一例を示すフローチャートである。
【図３】図３は、第２の実施形態に係る並列分散処理制御システムの構成の一例を示す図である。
【図４】図４は、第２の実施形態に係る並列分散処理制御システムにおけるMapReduce処理の流れの一例を示すフローチャートである。
【図５】図５は、第２の実施形態に係るスレーブおよびアクセラレータの構成の一例を示す図である。
【図６】図６は、第２の実施形態におけるMapタスク実行処理の流れの一例を示す図である。
【図７】図７は、第２の実施形態に係るアクセラレータにおけるサブタスク実行処理を説明するための図である。
【図８】図８は、第２の実施形態に係るMapサブタスクの処理の流れの一例を示すフローチャートである。
【図９】図９は、第２の実施形態に係るマージソートサブタスクの処理の流れの一例を示すフローチャートである。
【図１０】図１０は、第３の実施形態に係る並列分散処理制御システムにおけるMapタスクの処理を説明するための図である。
【図１１】図１１は、第３の実施形態における処理対象データの転送態様を説明するための図である。
【図１２】図１２は、並列分散処理制御システムにおける一連の処理を実行するプログラムである並列分散処理制御プログラムによる情報処理が、コンピュータを用いて具体的に実現されることを示す図である。
【発明を実施するための形態】
【００１４】
以下に、本発明にかかる並列分散処理制御装置、並列分散処理制御システム、並列分散処理制御方法および並列分散処理制御プログラムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。また、各実施の形態は適宜組み合わせることができる。
【００１５】
（第１の実施形態）
図１は、第１の実施形態に係る並列分散処理制御装置の構成の一例を示す図である。図１を参照して、第１の実施形態に係る並列分散処理制御装置の構成の一例について説明する。
【００１６】
［並列分散処理制御装置１０の構成の一例］
図１に示す並列分散処理制御装置１０は、制御部１１０と、記憶部１２０と、アクセラレータ１３０と、記憶装置（ディスク）１４０と、を備える。
【００１７】
制御部１１０は、並列分散処理制御装置１０内の処理を制御する。制御部１１０は、タスク分割部１１１と、サブタスク割当部１１２と、サブタスク起動部１１３と、統合部１１４と、を有する。
【００１８】
タスク分割部１１１は、並列分散処理制御装置１０に割り当てられたタスクをサブタスクに分割する。たとえば、タスク分割部１１１は、アクセラレータ１３０（後述）が有する演算部（たとえばＣＰＵ等のコア）の数に依存した数のサブタスクにタスクを分割する。タスク分割部１１１は、各サブタスクにおける処理対象データのブロック数が略均等になるようタスクを分割する。
【００１９】
サブタスク割当部１１２は、タスク分割部１１１での分割により得られたサブタスクを、アクセラレータ１３０が有する演算部に割り当てる。
【００２０】
サブタスク起動部１１３は、タスク分割部１１１での分割により得られたサブタスクを、サブタスク割当部１１２が当該サブタスクを割り当てた演算部において起動する。
【００２１】
統合部１１４は、サブタスク起動部１１３により起動されたサブタスク全ての実行が完了すると、記憶部１２０に格納された実行結果を統合して出力データを生成する。
【００２２】
記憶部１２０は、アクセラレータ１３０におけるサブタスクの実行の結果得られる結果データを記憶する。記憶部１２０に記憶された結果データは、全てのサブタスクが完了すると統合部１１４によって統合され、出力データが生成される。出力データは、記憶装置１４０に格納される。なお、記憶部１２０に記憶される各サブタスクの実行結果は、各演算部において統合処理の一部が実行され、部分的に統合された状態であってもよい。
【００２３】
アクセラレータ１３０は、複数の演算部を有するプロセッサである。アクセラレータ１３０としてたとえば、多数のＣＰＵを搭載するメニ−コアプロセッサや、再構成可能なＦＰＧＡ（Field-programmable  gate  array）等を利用することができる。図１中、アクセラレータ１３０は、並列分散処理制御装置１０の内部に配置されるものとして図示する。実際には、メニ−コアプロセッサを既存のサーバに増設する等、既存のサーバにＰＣＩバスを介してメニ−コアプロセッサのボードを接続すればよい。
【００２４】
記憶装置１４０は、並列分散処理制御装置１０における処理の対象となるデータや処理の結果生成されるデータを記憶する。記憶装置１４０はたとえば、ハードディスクドライブ（ＨＤＤ：Hard  Disk  Drive）やＳＤＤ（Solid  State  Drive）等である。
【００２５】
［並列分散処理制御装置１０における処理の流れ］
図２は、第１の実施形態に係る並列分散処理制御装置１０における処理の流れの一例を示すフローチャートである。まず、並列分散処理制御装置１０は、タスク実行要求を受け付ける（ステップＳ２０１）。すると、タスク分割部１１１は、当該タスクを複数のサブタスクに分割する（ステップＳ２０２）。サブタスク割当部１１２は、分割された複数のサブタスク各々を、アクセラレータ１３０の演算部に割り当てる（ステップＳ２０３）。そして、サブタスク起動部１１３は、サブタスクが割り当てられた演算部においてサブタスクを起動させる（ステップＳ２０４）。サブタスクが起動した演算部は各々、並列してサブタスクを実行し、処理結果を記憶部１２０に送り格納させる（ステップＳ２０５）。全ての演算部での処理が完了すると、統合部１１４は、記憶部１２０に格納された処理結果を統合して出力データを生成する（ステップＳ２０６）。統合部１１４により生成された出力データは、記憶装置１４０に記憶される（ステップＳ２０７）。これによって、並列分散処理制御装置１０における処理が終了する。
【００２６】
［第１の実施形態の効果］
このように第１の実施形態に係る並列分散処理制御装置１０は、受け付けたタスクを演算部の数に応じた数のサブタスクに分割する分割部と、サブタスクを演算部に割り当てる割当部と、サブタスクを割り当てられた演算部においてサブタスクを並列実行した処理結果を統合する統合部と、を備える。このため、一つのタスクによる処理量が多いときや、タスクを割り当てられた演算部の処理能力が低いときでも、処理をサブタスクに分割して複数の演算部において並列実行させることができる。このため、演算部の処理能力の制約に影響されずに記憶装置のＩ／Ｏ性能を効率的に利用して並列分散処理の高速化を実現することができる。また、アクセラレータの演算部を利用して処理を並列実行させるため、必要に応じてアクセラレータをＰＣＩバス等で接続して増設でき、柔軟に処理の高速化を図ることができる。
【００２７】
並列分散処理制御装置１０はたとえば、分散型ファイルシステムを構成するサーバとして適用できる。
【００２８】
（第２の実施形態）
次に、第２の実施形態として、Hadoop環境でMapReduceを実行するサーバにおいてMapサブタスクの並列処理を行う例を説明する。
【００２９】
従来のMapReduceでは、各Mapタスクが、「ディスクからのデータロード、Key-Valueペアの生成、出力ファイルのソート」までの処理全体を実行する。
【００３０】
これに対して、第２の実施形態では、まず、MapReduceのMap処理におけるディスクからのデータロード、データのデシリアライゼーション、Key-Valueペアの生成、出力ファイルのソートを二つの処理に分割する。すなわち、「ディスクからのデータロード、データのデシリアライゼーション、Key-Valueペアの生成、ソートの一部」と、出力ファイル（全体）のソートとの二つの処理に分割する。そして、前者の「ディスクからのデータロード、データのデシリアライゼーション、Key-Valueペアの生成、ソートの一部」の処理を並列実行することにより、処理を高速化する。
【００３１】
［並列分散処理制御システム１の構成の一例］
図３を参照し、第２の実施形態に係る並列分散処理制御システムの一例について説明する。図３は、第２の実施形態に係る並列分散処理制御システム１の構成の一例を示す図である。図３に示すように、並列分散処理制御システム１は、マスタ１００と、スレーブ２００Ａ〜２００Ｇ（以下、まとめてスレーブ２００とも称する）と、アクセラレータ３００Ａ〜３００Ｇ（以下、まとめてアクセラレータ３００とも称する）と、を備える。また、並列分散処理制御システム１は、記憶装置４００Ａ〜４００Ｈ（以下、まとめて記憶装置４００とも称する）を備える。
【００３２】
マスタ１００およびスレーブ２００Ａ〜２００Ｇは各々たとえばコモディティサーバ等の情報処理装置である。マスタ１００およびスレーブ２００Ａ〜２００Ｇは、ネットワークを介して互いに接続され、相互にデータを送受信する。また、スレーブ２００Ａ〜２００Ｇは、ＰＣＩバス等によって各々アクセラレータ３００Ａ〜３００Ｇと接続される。また、マスタ１００およびスレーブ２００Ａ〜２００Ｇは各々、記憶装置４００Ｈおよび記憶装置４００Ａ〜４００Ｇと接続され、配下の記憶装置にデータを記憶する。
【００３３】
図３には、１つのマスタと７つのスレーブ、７つのアクセラレータを示すが、これらの数はそれぞれ１、７、７に限定されるものではない。１０以上のサーバによってマスタおよびスレーブを構成してもよい。さらに、複数のデータセンタにまたがって処理制御システム１を構築し、インタークラウドシステムとしてもよい。
【００３４】
並列分散処理制御システム１は、データを複数のノードに分散して記憶する分散型ファイルシステムである。この分散型ファイルシステムでは、書き込みの対象となるデータをブロックに分割してサーバ（マスタ１００およびスレーブ２００Ａ〜２００Ｇ）配下の記憶装置４００Ａ〜４００Ｈに格納する。また、一つのブロックについて冗長性を確保するために、たとえば３つの同一のブロックを異なる複数のサーバ（マスタ１００およびスレーブ２００Ａ〜２００Ｇ）配下の記憶装置４００に格納する。データの格納場所についての情報はマスタ１００が管理する。そして、MapReduceを実行する際には、当該データを格納した記憶装置４００からデータを読み出して、複数のサーバ上でMapタスクを並列実行させる。実行結果はReduceタスクを実行するサーバにおいて統合され、最終的な出力ファイルが生成される。
【００３５】
マスタ１００はたとえば、ジョブトラッカー（Job  Tracker）およびネームノード（Namenode）として動作する。ジョブトラッカーは、ジョブの投入を受け付けて複数のタスクに分割し、分割したタスクをノードに割り当てる。ネームノードは、ＨＤＦＳの管理を行う。ネームノードは、書き込み対象データを各ノードに分配し、各ノードに格納されるファイル（データブロック）の位置等の情報を管理する。
【００３６】
スレーブ２００Ａ〜２００Ｇは各々、タスクトラッカー（Task  Tracker）およびデータノード（Datanode）として動作する。タスクトラッカーは、ジョブトラッカーに割り当てられたタスクの実行を管理する。データノードは、ネームノードから分配されたデータを、指定された場所から読み出して格納する。
【００３７】
［MapReduce処理の流れの一例］
次に、図４を参照してMapReduce処理の流れの一例を説明する。図４は、第２の実施形態に係る並列分散処理制御システム１におけるMapReduce処理の流れの一例を示すフローチャートである。
【００３８】
まず、マスタ１００はジョブを受け付ける（ステップＳ４０１）。すなわち、マスタ１００は、MapReduce処理の対象とするデータの指定を受け付ける。次に、マスタ１００は、受け付けたジョブを、並列実行するための複数のMapタスクに分割する（ステップＳ４０２）。すなわち、マスタ１００は、Mapタスク各々に処理対象データを割り当てる。一つのMapタスクに割り当てられたデータを、以下、入力スプリットともいう。そしてマスタ１００は、各Mapタスクを実行するスレーブ２００を選択し、選択したスレーブ２００にMapタスクを割り当てる（ステップＳ４０３）。
【００３９】
マスタ１００は、Mapタスクの割り当てにおいては、各スレーブ２００に、当該スレーブ配下の記憶装置４００（ローカルディスク）に格納されているデータを処理対象とするMapタスクを割り当てる。ただし、マスタ１００は、他のスレーブ配下の記憶装置に格納されているデータを処理対象とするMapタスクを割り当ててもよい。その場合、スレーブは、ネットワークを介して該当する記憶装置から処理対象データを読み出し、処理を実行する。
【００４０】
Mapタスクを割り当てられたスレーブ２００は、Mapタスクを実行する（ステップＳ４０４）。そして、Mapタスクの実行結果を、Reduceタスクを実行するスレーブに渡す。Reduceタスクは、Mapタスクと同様、マスタ１００によって所定のスレーブ２００に割り当てられる。
【００４１】
Reduceタスクを割り当てられたスレーブは、Reduceタスクを実行する（ステップＳ４０５）。そして、当該スレーブは、実行結果を出力ファイルとして出力する（ステップＳ４０６）。これによってMapReduce処理が終了する。
【００４２】
次に、第２の実施形態におけるMapタスクの処理（図４のステップＳ４０４）を説明する。第２の実施形態では、スレーブ２００に割り当てられたMapタスクをさらに分割して複数のMapサブタスクとする。そして、スレーブ２００は、複数のMapサブタスクをアクセラレータ３００が備える複数の処理部（後述）に割り当てて並列実行させる。まず、スレーブ２００およびアクセラレータ３００の構成について説明する。
【００４３】
［スレーブ２００の構成の一例］
図５は、第２の実施形態に係るスレーブ２００Ａおよびアクセラレータ３００Ａの構成の一例を示す図である。図５中、スレーブ２００Ａ〜２００Ｇに共通の構成の例としてスレーブ２００Ａの構成を示す。また、アクセラレータ３００Ａ〜３００Ｇに共通の構成の例としてアクセラレータ３００Ａの構成を示す。図５に示すように、スレーブ２００Ａは、制御部２１０と、記憶部２２０と、通信部２３０と、を備える。
【００４４】
制御部２１０は、スレーブ２００Ａにおける処理を制御する。制御部２１０はたとえば、コモディティサーバに搭載されたＣＰＵである。制御部２１０は、タスク分割部２１１、サブタスク割当部２１２、サブタスク起動部２１３および統合部２１４を備える。
【００４５】
タスク分割部２１１は、スレーブ２００Ａにおいて起動されたMapタスクを複数のMapサブタスクに分割する。タスク分割部２１１は、アクセラレータ３００Ａのコアの数より少なくとも１少ない数のMapサブタスクを生成する。また、タスク分割部２１１は、コア各々に割り当てられる処理対象ブロックの数が等しくなるようMapサブタスクを生成する。
【００４６】
ここで、サブタスクの数をアクセラレータ３００Ａのコア数よりも少ない数に設定するのは、少なくとも一つのコアにMapサブタスクの結果を統合するマージソートサブタスクを実行させるためである。
【００４７】
サブタスク割当部２１２は、タスク分割部２１１が生成したサブタスクを実行するコアを決定する。すなわち、サブタスク割当部２１２は、Mapサブタスクおよびマージソートサブタスクを割り当てるコアを決定する。
【００４８】
サブタスク起動部２１３は、タスク分割部２１１が生成したサブタスクが、サブタスク割当部２１２が決定したコアにおいて実行されるよう、サブタスクを起動する。
【００４９】
統合部２１４は、アクセラレータ３００Ａにおけるサブタスクの実行により生成され、記憶部２２０に格納されたKey-Valueペアを読み出してコピーする。さらに、統合部２１４は、コピーしたKey-ValueペアをKeyごとにソートする。統合部２１４はソートした結果を、記憶装置４００Ａに格納する。その後、格納された結果は、Reduceタスクが割り当てられたスレーブにより読み出される。
【００５０】
記憶部２２０は、アクセラレータ３００Ａでのサブタスクの実行結果を一時的に記憶する。
【００５１】
通信部２３０は、スレーブ２００Ａと、マスタ１００、スレーブ２００Ｂ〜２００Ｇとの間でデータ等を送受信するインタフェースである。たとえば、通信部２３０は、制御部２１０の処理により生成されるデータをマスタ１００に送信する。
【００５２】
［アクセラレータ３００Ａの構成の一例］
アクセラレータ３００Ａは、スレーブ２００Ａにおいて起動されたMapタスクを分割したサブタスクを実行する処理部である。アクセラレータ３００Ａはたとえば、多数のＣＰＵ（コア）を備えたメニーコアプロセッサや、再構成可能なＦＰＧＡなどを搭載した基板で構成する。図５では、アクセラレータ３００Ａを、１０個のコアＣ１〜Ｃ１０を有するメニーコアプロセッサとして示す。
【００５３】
また、アクセラレータ３００Ａは、ローカルバッファＬＢ１〜ＬＢ１０とグローバルバッファＧＢとを備える（図５参照）。コアＣ１〜Ｃ１０各々に対してローカルバッファＬＢ１〜ＬＢ１０が割り当てられる。グローバルバッファＧＢには、複数のコアの処理結果が統合的に格納される。
【００５４】
ここでは、アクセラレータ３００Ａとして、スレーブ２００Ａが備えるＣＰＵ（コア）の数よりも多数のＣＰＵ（コア）を備える装置を想定する。たとえば、タイレラ（Tilera）（登録商標）のメニーコアプロセッサやインテル（登録商標）Xeon  Phiなどを採用することができる。また、ＦＰＧＡを用いて、Mapサブタスクをハードウェア化して実行することも可能である。
【００５５】
［スレーブ２００ＡにおけるMapタスク実行処理の一例］
図６を参照し、スレーブ２００ＡにおけるMapタスク実行処理（図４のステップＳ４０４）について説明する。図６は、第２の実施形態におけるMapタスク実行処理の流れの一例を示す図である。
【００５６】
まず、スレーブ２００ＡにMapタスクが割り当てられ、Mapタスクが起動される（ステップＳ６０１）。スレーブ２００Ａのタスク分割部２１１は、MapタスクをMapサブタスクおよびマージソートサブタスクに分割する（ステップＳ６０２）。そして、サブタスク割当部２１２は、Mapサブタスクおよびマージソートサブタスクを割り当てるアクセラレータ３００Ａのコアを決定する（ステップＳ６０３）。そして、サブタスク起動部２１３は、Mapサブタスクおよびマージソートサブタスクを割り当てられたコアにおいてサブタスクを起動し、サブタスクを実行させる（ステップＳ６０４）。統合部２１４は、サブタスクの処理結果を統合する（ステップＳ６０５）。つまり、統合部２１４は、処理結果をコピーしてKeyごとに処理結果をソートする。ソートした処理結果は記憶装置４００に記憶される（ステップＳ６０６）。
【００５７】
［アクセラレータ３００Ａでのサブタスク実行処理の流れ］
次に、サブタスクを割り当てられたアクセラレータ３００Ａにおけるサブタスク実行処理（図６のステップＳ６０４）の流れを説明する。図７は、第２の実施形態に係るアクセラレータ３００Ａにおけるサブタスク実行処理を説明するための図である。図８は、第２の実施形態に係るMapサブタスクの処理の流れの一例を示すフローチャートである。図９は、第２の実施形態に係るマージソートサブタスクの処理の流れの一例を示すフローチャートである。図７乃至図９を参照して、アクセラレータ３００Ａにおけるサブタスク実行処理の一例について説明する。
【００５８】
まず、アクセラレータ３００Ａの各コアにおいてサブタスクが起動される（ステップＳ８０１）。サブタスクが起動すると、Mapサブタスクが割り当てられたコア（ここではコアＣ１として説明する）は、Mapサブタスクの対象データを読み込む（ステップＳ８０２）。たとえば、図７の例では、一つのMapタスクが４つのMapサブタスクとマージソートサブタスクとに分割され、Mapタスクの処理対象であった４ブロックのデータＢ１〜Ｂ４がそれぞれ１ブロックずつMapサブタスクの処理対象となっている。コアＣ１は、ブロックＢ１を読み込む。なお、第２の実施形態では、各コアは、処理対象のブロックをスレーブ２００Ａを介さず直接記憶装置４００Ａから読み出す。
【００５９】
そして、コアＣ１は、読み込んだブロックＢ１をデシリアライズする（ステップＳ８０３、図７の★）。次に、コアＣ１は、読み込んだブロックＢ１のデータを１レコードずつ取り出し、Key-Valueペアを生成する（ステップＳ８０４）。生成したKey-Valueペアは、コアＣ１に割り当てられたローカルバッファＬＢ１に格納される。
【００６０】
次にコアＣ１は、ローカルバッファＬＢ１が一杯になっているか否かを判定する（ステップＳ８０５）。ローカルバッファＬＢ１が一杯になっていないと判定した場合（ステップＳ８０５、否定）、コアＣ１は全てのレコードの処理が完了しているか否かを判定する（ステップＳ８０６）。全てのレコードの処理が完了していないと判定した場合（ステップＳ８０６、否定）、コアＣ１は、次のレコードを読み出して（ステップＳ８０７）、ステップＳ８０４に戻る。
【００６１】
他方、ステップＳ８０５においてローカルバッファＬＢ１が一杯になっていると判定した場合（ステップＳ８０５、肯定）およびステップＳ８０６において全てのレコードの処理が完了していると判定した場合（ステップＳ８０６、肯定）、ステップＳ８０８に進む。ステップＳ８０８において、コアＣ１は、領域ＬＢ１内のKey-ValueペアをKeyに基づいてソートし、結果をグローバルバッファＧＢに送って格納する（ステップＳ８０９）。そして、コアＣ１は、全てのレコードの処理が完了しているか否かを判定する（ステップＳ８１０）。全てのレコードの処理が完了していないと判定した場合（ステップＳ８１０、否定）、コアＣ１はステップＳ８０７に戻る。他方、全てのレコードの処理が完了したと判定した場合（ステップＳ８１０、肯定）、コアＣ１は、マージソートサブタスクを割り当てられたコア（ここではコアＣ１０とする）に処理を渡す（ステップＳ８１１）。これによってコアＣ１におけるMapサブタスクの処理は終了する。
【００６２】
コアＣ１におけるMapサブタスクの実行中、Mapサブタスクが割り当てられた他のコアＣ２〜Ｃ４（図７参照）も並行して上記ステップＳ８０１〜ステップＳ８１１の処理を実行する。
【００６３】
コアＣ１〜Ｃ４においてMapサブタスクが実行されている間、コアＣ１０はマージソートサブタスクを実行している（図７参照）。すなわち、図９に示すように、コアＣ１０は、所定時間ごとに、グローバルバッファＧＢが一杯になっているか否かを判定する（ステップＳ９０１）。グローバルバッファＧＢが一杯になっていないと判定した場合（ステップＳ９０１、否定）、コアＣ１０は、コアＣ１〜Ｃ４全部からMapサブタスクが完了した旨の通知を受け取ったか否かを判定する（ステップＳ９０２）。コアＣ１〜Ｃ４全部から受け取ってはいないと判定した場合（ステップＳ９０２、否定）、コアＣ１０は、所定時間待機した（ステップＳ９０３）後、ステップＳ９０１に戻る。
【００６４】
グローバルバッファＧＢが一杯であると判定した場合（ステップＳ９０１、肯定）およびコアＣ１〜Ｃ４全てから完了通知を受け取ったと判定した場合（ステップＳ９０２、肯定）、コアＣ１０は、ステップＳ９０４に進む。ステップＳ９０４では、コアＣ１０は、グローバルバッファＧＢに蓄積されたKey-Valueペアの情報を統合してKeyをもとにソートする（ステップＳ９０４）。コアＣ１０は、ソートした情報を、Mapサブタスクを割り当てたスレーブ２００へ送信する（ステップＳ９０５）。これによって、処理を終わる。
【００６５】
図８および図９に示すサブタスクの処理は、図７に示すようにアクセラレータ３００Ａにおいて実行される。そして、アクセラレータ３００ＡのコアＣ１０が生成した情報は、スレーブ２００Ａに送信される。
【００６６】
このように、コアＣ１０からスレーブ２００Ａには、グローバルバッファＧＢが一杯になるごとにKey-Valueペアのデータ（出力結果）が送られる。スレーブ２００Ａの統合部２１４は、こうして送信され蓄積される複数の出力結果をさらにKeyを基にして統合し、最終的なMapタスクの出力ファイルを生成する（図７参照）。
【００６７】
［第２の実施形態の効果］
このように、第２の実施形態に係る並列分散処理制御システム１は、複数の情報処理装置と、複数のコアを有するアクセラレータと、を備える。そして、複数の情報処理装置のうち１の情報処理装置は、Mapタスクを、アクセラレータが有するコアの数に応じた数のサブタスクに分割する分割部を備える。また、１の情報処理装置は、サブタスクをアクセラレータの複数のコアに割り当てる割当部と、サブタスクの処理結果を統合する統合部と、を備える。そして、アクセラレータは、複数のコアにおいてサブタスクを並列実行する。このため、コアの処理能力の制約に影響されずに記憶装置のＩ／Ｏ性能を効率的に利用して並列分散処理の高速化を実現することができる。また、アクセラレータが備えるコアを利用して処理を並列実行させるため、必要に応じてアクセラレータをＰＣＩバス等で接続して増設でき、柔軟に処理の高速化を図ることができる。
【００６８】
（第３の実施形態）
上記第２の実施形態では、アクセラレータ３００Ａのコアが処理対象データを格納する記憶装置４００Ａに直接アクセスしてデータを取得する例を説明した。第３の実施形態では、処理対象データを一端、Mapタスクが起動したスレーブ２００Ａの記憶部２２０に読み込む。そして、スレーブ２００Ａの記憶部２２０からさらに、アクセラレータ３００Ａ上のメモリに転送する。その後、サブタスクを実行するコアがアクセラレータ３００Ａ上のメモリから必要なデータを読み出して処理を実行する。その他の点では、第３の実施形態の並列分散処理制御システム２の構成および機能は、第２の実施形態の並列分散処理制御システム１と同様である。
【００６９】
図１０は、第３の実施形態に係る並列分散処理制御システム２におけるMapタスクの処理を説明するための図である。図１０を参照して、第３の実施形態におけるMapタスクの処理の一例を説明する。
【００７０】
まず、スレーブ２００ＡにおいてMapタスクが起動される（ステップＳ１００１）。すると、スレーブ２００Ａは記憶装置３００Ａから当該Mapタスクの処理対象である入力スプリットを読み出して記憶部２２０を経由して、アクセラレータ３００Ａに転送する。すなわち、記憶装置３００Ａから記憶部２２０に読み込み、アクセラレータ３００Ａへの送付を繰り返す（ステップS１００２）。このとき、データの転送にはダイレクトメモリアクセス（ＤＭＡ：Direct  Memory  Access）を用いる。
【００７１】
次に、スレーブ２００Ａのタスク分割部２１１は、Mapタスクを処理内容およびアクセラレータ３００Ａ上のコアの数に応じた数のサブタスクに分割する（ステップＳ１００３）。そして、サブタスク割当部２１２は、サブタスクを割り当てるコアを決定する（ステップＳ１００４）。このとき、サブタスク割当部２１２は、Mapタスクを分割して得たMapサブタスクの割当先とともに、マージソートサブタスクの割当先を決定する。
【００７２】
そして、サブタスク起動部２１３は、サブタスク割当部２１２が決定した割当先において該当するサブタスクを起動する（ステップＳ１００５）。サブタスクが起動した各コアは、アクセラレータ３００Ａ上のメモリにアクセスしてサブタスクの処理対象データを読み出し、サブタスクを実行する（ステップＳ１００６）。すなわち、データのデシリアライゼーション、Key-Valueペアの生成、Keyに基づくソート等が実行される。その後、全てのサブタスクが完了するとスレーブ２００Ａは処理結果を統合して結果を記憶装置４００Ａに格納する（ステップＳ１００７）。
【００７３】
このように、第３の実施形態では、アクセラレータ３００Ａ上のコアは直接スレーブ２００Ａ配下の記憶装置４００Ａから処理対象データを読み出すのではなく、アクセラレータ３００Ａ上のメモリからデータを読み出す。図１１は、第３の実施形態における処理対象データの転送態様を説明するための図である。図１１に示すように、記憶装置４００Ａに格納された処理対象データは、一端スレーブ２００Ａ上の記憶部２２０に転送される。このとき転送はダイレクトメモリアクセスで行う。さらに、スレーブ２００Ａ上の記憶部２２０からアクセラレータ３００Ａ上のメモリに、処理対象データが転送される。やはり転送はダイレクトメモリアクセスで行う。この後、Mapサブタスクを各コアが実行する際には、アクセラレータ３００Ａ上のメモリからデータを読み出してロードし、デシリアライゼーション、Key-Valueペアの生成等を実行する。
【００７４】
［第３の実施形態の効果］
このように、第３の実施形態では、処理対象データをいったんスレーブ２００Ａ上の記憶部２２０に転送してから、アクセラレータ３００Ａに転送し、各コアが対象データをアクセラレータ３００Ａ上のメモリから読み出して処理を実行する。このため、Mapタスクを割り当てられたスレーブ２００Ａから、処理対象データを自装置のファイルシステムとして扱えるようになる。したがって、管理者による処理の操作が容易になる。
【００７５】
なお、上記第２および第３の実施形態は、Hadoop環境において動作する分散型ファイルシステムを前提として説明したが、MapReduceを利用したシステムであればHadoopに限定されず、他のフレームワークにも適用することができる。
【００７６】
（第４の実施形態）
これまで本発明の実施形態について説明したが、本発明は上述した実施形態以外にも、その他の実施形態にて実施されてもよい。以下に、その他の実施形態を説明する。
【００７７】
［システム構成］
また、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００７８】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、図５に示す例では、タスク分割部２１１、サブタスク割当部２１２をスレーブ２００Ａ内に配置したが、これを分離して複数のスレーブのタスク分割部とサブタスク割当部とを統合する情報処理装置を配置し、当該情報処理装置がアクセラレータにおける機能の割当を管理するようにしてもよい。
【００７９】
［プログラム］
図１２は、並列分散処理制御システム１，２における一連の処理を実行するプログラムである並列分散処理制御プログラムによる情報処理が、コンピュータを用いて具体的に実現されることを示す図である。図１２に例示するように、コンピュータ３０００は、たとえば、メモリ３０１０と、ＣＰＵ（Central  Processing  Unit）３０２０と、ハードディスクドライブ３０８０と、ネットワークインタフェース３０７０とを有する。コンピュータ３０００の各部はバス５１００によって接続される。
【００８０】
メモリ３０１０は、図１２に例示するように、ＲＯＭ３０１１およびＲＡＭ３０１２を含む。ＲＯＭ３０１１は、たとえば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。
【００８１】
ここで、図１２に例示するように、ハードディスクドライブ３０８０は、たとえば、ＯＳ３０８１、アプリケーションプログラム３０８２、プログラムモジュール３０８３、プログラムデータ３０８４を記憶する。すなわち、開示の技術に係る並列分散処理制御プログラムは、コンピュータによって実行される指令が記述されたプログラムモジュール３０８３として、たとえばハードディスクドライブ３０８０に記憶される。たとえば、マスタ１００が備える制御部、スレーブ２００Ａが備える制御部２１０およびコアＣ１〜Ｃ１０の各部と同様の情報処理を実行する手順各々が記述されたプログラムモジュール３０８３が、ハードディスクドライブ３０８０に記憶される。
【００８２】
また、記憶部２２０、ローカルバッファＬＢおよびグローバルバッファＧＢに記憶されるデータのように、並列分散処理制御プログラムによる情報処理に用いられるデータは、プログラムデータ３０８４として、たとえばハードディスクドライブ３０８０に記憶される。そして、ＣＰＵ３０２０が、ハードディスクドライブ３０８０に記憶されたプログラムモジュール３０８３やプログラムデータ３０８４を必要に応じてＲＡＭ３０１２に読み出し、各種の手順を実行する。
【００８３】
なお、並列分散処理制御プログラムに係るプログラムモジュール３０８３やプログラムデータ３０８４は、ハードディスクドライブ３０８０に記憶される場合に限られない。たとえば、プログラムモジュール３０８３やプログラムデータ３０８４は、着脱可能な記憶媒体に記憶されてもよい。この場合、ＣＰＵ３０２０は、ディスクドライブなどの着脱可能な記憶媒体を介してデータを読み出す。また、同様に、プログラムモジュール３０８３やプログラムデータ３０８４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。この場合、ＣＰＵ３０２０は、ネットワークインタフェース３０７０を介して他のコンピュータにアクセスすることで各種データを読み出す。
【００８４】
［その他］
なお、本実施例で説明した並列分散処理制御プログラムは、インターネット等のネットワークを介して配布することができる。また、並列分散処理制御プログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読取可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【００８５】
１  並列分散処理制御システム
１０  並列分散処理制御装置
１００  マスタ
１１０  制御部
１１１  タスク分割部
１１２  サブタスク割当部
１１３  サブタスク起動部
１１４  統合部
１２０  記憶部
１３０  アクセラレータ
１４０  記憶装置
２００Ａ〜２００Ｇ  スレーブ
２１０  制御部
２１１  タスク分割部
２１２  サブタスク割当部
２１３  サブタスク起動部
２１４  統合部
２２０  記憶部
２３０  通信部
３００  アクセラレータ
４００  記憶装置
Ｃ１〜Ｃ１０  コア
ＧＢ  グローバルバッファ
ＬＢ１〜ＬＢ１０  ローカルバッファ
【図１】
2014153935.tif 000003
【図２】
2014153935.tif 000004
【図３】
2014153935.tif 000005
【図４】
2014153935.tif 000006
【図５】
2014153935.tif 000007
【図６】
2014153935.tif 000008
【図７】
2014153935.tif 000009
【図８】
2014153935.tif 000010
【図９】
2014153935.tif 000011
【図１０】
2014153935.tif 000012
【図１１】
2014153935.tif 000013
【図１２】
2014153935.tif 000014