(57)【特許請求の範囲】
【請求項１】
複数の計算ノードを有する並列計算機システムでの並列処理方法であって、
第１のグループ分けで処理対象を分割して各計算ノードに配置して処理し、
処理結果にそれぞれが属する第２のグループ毎の宛先を与え、
該宛先毎に異なるストレージ装置に該処理結果を保存し、
保存された処理結果を前記第１のグループ分けに従って各計算ノードに送信することを特徴とする並列処理方法。
【請求項２】
請求項１に記載の並列処理方法において、
該処理結果が保存される各ストレージ装置は、各計算ノード上に配置されていることを特徴とする並列処理方法。
【請求項３】
請求項１に記載の並列処理方法において、
前記保存された処理結果を前記第１のグループ分けに従って各計算ノードに送信する際に、
前記保存された処理結果を前記第２のグループ分け毎に時間差をおいて送信することを特徴とする並列処理方法。
【請求項４】
請求項１に記載の並列処理方法において、
前記第１のグループ分けの任意の一のグループに含まれる処理対象は、前記第２のグループ分けのそれぞれのグループに少なくとも一つ含まれるように分散されていることを特徴とする並列処理方法。
【請求項５】
請求項１に記載の並列処理方法において、
前記処理対象はグラフ構造データであることを特徴とする並列処理方法。
【請求項６】
複数の計算ノードを有する並列計算機システムであって、
第１のグループ分けで処理対象を分割して各計算ノードに配置して処理し、
処理結果にそれぞれが属する第２のグループ毎の宛先を与え、
該宛先毎に異なるストレージ装置に該処理結果を保存し、
保存された処理結果を前記第１のグループ分けに従って各計算ノードに送信することを特徴とする並列計算機システム。
【請求項７】
請求項６に記載の並列計算機システムにおいて、
該処理結果が保存される各ストレージ装置は、各計算ノード上に配置されていることを特徴とする並列計算機システム。
【請求項８】
請求項６に記載の並列計算機システムにおいて、
前記保存された処理結果を前記第１のグループ分けに従って各計算ノードに送信する際に、
前記保存された処理結果を前記第２のグループ分け毎に時間差をおいて送信することを特徴とする並列計算機システム。
【請求項９】
請求項６に記載の並列計算機システムにおいて、
前記第１のグループ分けの任意の一のグループに含まれる処理対象は、前記第２のグループ分けのそれぞれのグループに少なくとも一つ含まれるように分散されていることを特徴とする並列計算機システム。
【請求項１０】
請求項６に記載の並列計算機システムにおいて、
前記処理対象はグラフ構造データであることを特徴とする並列計算機システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理方法、および並列計算機システムに関し、特に、処理結果の送信に関する。
【背景技術】
【０００２】
並列計算装置の上で効率よく計算をする汎用的な方式として、非特許文献１では、図２に示したＭａｐＲｅｄｕｃｅと呼ばれる計算モデルを開示している。なお、後述するように、ここでＭａｐＲｅｄｕｃｅを取り上げるのは単に技術説明の例とするためであり、本願における発明自体はＭａｐＲｅｄｕｃｅ計算モデルをその前提としているわけでない。【０００３】
図２に示したように、ＭａｐＲｅｄｕｃｅ計算モデルは、Ｍａｐフェーズと、Ｓｏｒｔフェーズと、Ｒｅｄｕｃｅフェーズと、の３つのフェーズによって構成される計算モデルである。Ｍａｐフェーズでは、入力データが多数の処理単位に分割されて読み込まれ、Ｍａｐプロセスに入力され、Ｍａｐプロセスは処理単位ごとになんらかの計算あるいは処理を行って、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を出力する。続くＳｏｒｔフェーズでは、Ｍａｐフェーズで出力された＜Ｋｅｙ，Ｖａｌｕｅ＞の組が、Ｋｅｙ毎に分類（整列）され、各Ｋｅｙに対して複数のＶａｌｕｅを組にしたものが出力される。Ｒｅｄｕｃｅフェーズでは、各Ｋｅｙに複数のＶａｌｕｅを組にしたものが、Ｒｅｄｕｃｅプロセスに入力され、Ｒｅｄｕｃｅプロセスが入力された該組になんらかの計算あるいは処理を行って最終的な結果を出力する。【０００４】
ここで、Ｍａｐフェーズ、およびＲｅｄｕｃｅフェーズにおいて、各Ｍａｐプロセス、および各Ｒｅｄｕｃｅプロセスは、他のＭａｐプロセスおよびＲｅｄｕｃｅプロセスとの依存関係はないため、並列に実行することが可能である。したがって、ＭａｐＲｅｄｕｃｅ計算モデルを用いることで、複数の計算ノードで構成される並列計算装置で並列的に計算（処理）を行うことができる。【０００５】
図３は、複数の計算ノードで構成される並列計算装置上で、ＭａｐＲｅｄｕｃｅ計算モデルを動作させた様子を示す模式図である。前述のように、Ｍａｐフェーズにおける複数のＭａｐプロセス、および、Ｒｅｄｕｃｅフェーズにおける複数のＲｅｄｕｃｅプロセスは、それぞれ並列に実行することが可能である。したがって、これらのプロセスを複数の計算ノードに割り振って並列に実行させることができる。なお、ＭａｐフェーズとＲｅｄｕｃｅフェーズは、必ずしも同一の並列計算装置で行われる必要はない。ところで、多くの場合、Ｍａｐプロセス、およびＲｅｄｕｃｅプロセスの総数は、計算ノードの総数に比べて多い。その場合、必然的に、各計算ノードは、それぞれ、複数のＭａｐプロセス、およびＲｅｄｕｃｅプロセスを担当することとなる。Ｒｅｄｕｃｅプロセスの総数（Ｍａｐフェーズで出力されるＫｅｙの種類の総数）が、計算ノードの総数に比べて多い場合を考える。この場合、図２におけるＳｏｒｔフェーズは、Ｓｈｕｆｆｌｅフェーズ（計算ノード間通信フェーズ）、およびＬｏｃａｌ  Ｓｏｒｔフェーズ（受信側整列フェーズ）、の２つのフェーズに細分化されることになる。Ｓｈｕｆｆｌｅフェーズでは、Ｍａｐフェーズで出力された＜Ｋｅｙ，Ｖａｌｕｅ＞の組が、Ｋｅｙ毎に一意に定まるＲｅｄｕｃｅプロセスを担当する計算ノードに送信される。各計算ノードが複数のＲｅｄｕｃｅプロセス（複数のＭａｐ出力Ｋｅｙ）を担当する場合、Ｓｈｕｆｆｌｅフェーズで送られた＜Ｋｅｙ，Ｖａｌｕｅ＞の組は、受信側の計算ノードでＫｅｙ毎に分類（整列）される必要がある。この分類（整列）が行われるのがＬｏｃａｌ  Ｓｏｒｔフェーズ（受信側整列フェーズ）である。【０００６】
以上のように、ＭａｐＲｅｄｕｃｅ計算モデルを用いることで、複数の計算ノードで構成される並列計算装置で並列的に計算（処理）を行うことができる。さらに、複数の計算ノードで構成される並列計算装置でＭａｐＲｅｄｕｃｅ計算モデルを用いる場合、実際の計算および処理を行うのは、Ｍａｐプロセス、およびＲｅｄｕｃｅプロセスのみであり、Ｓｈｕｆｆｌｅフェーズ、およびＬｏｃａｌ  Ｓｏｒｔフェーズはアプリケーションの処理内容によらず共通である。したがって、Ｓｈｕｆｆｌｅフェーズ、およびＬｏｃａｌ  Ｓｏｒｔフェーズをあらかじめ共通フレームワークとして作成しておくことで、ＭａｐプロセスおよびＲｅｄｕｃｅプロセスの処理内容のみを変更することで、複数のアプリケーションを簡単に作成することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】ジェフリー・ディーン（Ｊｅｆｆｒｅｙ  Ｄｅａｎ）、サンジェイ・ゲマワット（Ｓａｎｊａｙ  Ｇｈｅｍａｗａｔ）、「マップリデュース：ラージクラスタ上の単純化データ処理（ＭａｐＲｅｄｕｃｅ：  Ｓｉｍｐｌｉｆｉｅｄ  Ｄａｔａ  Ｐｒｏｃｅｓｓｉｎｇ  ｏｎ  Ｌａｒｇｅ  Ｃｌｕｓｔｅｒｓ）」、ＯＳＤＩ’０４：第６回オペレーティングシステムの設計と実装シンポジウムの紀要（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＯＳＤＩ’０４：  ６ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）、２００４年、ｐ．１３７−１４９
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前述のように、ＭａｐＲｅｄｕｃｅ計算モデルを用いることで、複数の計算ノードで構成される並列計算装置で並列的に計算（処理）を行うことができる。しかしながら、処理すべきデータ量が大きくなるにつれて、とくに、Ｒｅｄｕｃｅプロセスの総数が、計算ノードの総数に比べて多くなるにつれて、Ｌｏｃａｌ  Ｓｏｒｔフェーズ（受信側整列フェーズ）が重たい処理となり、全体の処理時間の大部分を占めてしまう。これは、Ｍａｐフェーズ、Ｒｅｄｕｃｅフェーズ、およびＳｈｕｆｆｌｅフェーズが、処理すべきデータ量に比例する時間がかかるのに対して、Ｌｏｃａｌ  Ｓｏｒｔフェーズでは、単純な整列アルゴリズムを用いると、データ量Ｎに対して、Ｎ×Ｌｏｇ（Ｎ）に比例する時間がかかるためである。【０００９】
さらに悪いことに、Ｌｏｃａｌ  Ｓｏｒｔフェーズで行われるデータの並び替えは、一般に記憶装置へのランダムアクセスを必要とする。通常、各計算ノードが備える一時記憶装置であるランダムアクセスメモリ（ＲＡＭ）は小容量であるため、扱うべきデータ量が大きい場合には、Ｌｏｃａｌ  Ｓｏｒｔフェーズの処理に、高速にランダムアクセスが可能な一時記憶装置であるＲＡＭだけではなく、大容量ではあるが特にランダムアクセス速度が低速な、フラッシュメモリやハードディスクドライブなどの記憶装置を使う必要がある。したがって、扱うべきデータ量が一時記憶装置であるＲＡＭの容量よりも大きくなると、Ｌｏｃａｌ  Ｓｏｒｔに必要な時間がさらに急激に増加することになる。【００１０】
本願の発明は、このようなことを鑑みてなされたものであり、その目的の一つは、Ｍａｐフェーズ、およびＳｈｕｆｆｌｅフェーズで、Ｋｅｙ毎の分類（整列）処理、あるいはその一部を行うことで、Ｓｈｕｆｆｌｅフェーズにおいて受信側の計算ノードに、なるべくＫｅｙ毎に分類（整列）済みのデータが届くようにする手段を提供し、それを用いて、Ｌｏｃａｌ  Ｓｏｒｔフェーズの処理時間を短縮する手段を提供することにある。本願の発明の前記並びにその他の目的と新規な特徴は、本明細書の記述及び添付図面から明らかになるであろう。【００１１】
なお、本願の発明が解決しようとする課題は、複数の計算ノードで複数の処理単位を並列処理するときに一般的に発生する課題であって、ここでＭａｐＲｅｄｕｃｅを取り上げたのは単に説明の例とするためである。したがって、本願の発明は、ＭａｐＲｅｄｕｃｅ計算モデルのみならず、複数の計算ノードで複数の処理単位を並列処理する場合の多くに適用が可能である。図４に、ＭａｐＲｅｄｕｃｅとは別の、本願の発明が適用可能な複数の計算ノードで複数の処理単位を並列処理する例として、グラフ問題を並列計算装置で計算する場合の模式図を示した。【００１２】
グラフ問題の並列計算とは、複数の頂点と頂点間を結ぶエッジとで構成されるグラフ構造を所与として、その上で種々の計算を行うものである。図４では、計算ノード１〜４が、それぞれに与えられたグラフの部分についての処理を行う例を示した。通常、グラフ問題は、複数の計算ステップにより構成されており、各計算ステップで、全頂点に関して、前ステップにおける自頂点に向かうエッジを持つ頂点の計算結果を入力としてなんらかの計算が行われる。グラフ問題を複数の計算ノードで構成される並列計算装置で計算する場合、各頂点が独立に計算できることを考えると、各計算ノードに頂点を割り当てて並列処理するのが自然である。このとき、各計算ステップが終了するごとに、計算結果をエッジのつながり先の頂点に送信し、受信側の計算ノードでは、受信したデータを宛先頂点毎に分類（整列）する必要がある。これは、前述のＭａｐＲｅｄｕｃｅ計算モデルにおける、Ｓｈｕｆｆｌｅフェーズ、およびＬｏｃａｌ  Ｓｏｒｔフェーズと同様の処理であり、頂点の数が多くなるほど、すなわち大規模なグラフ問題になるほど、受信側計算ノードにおける宛先頂点毎の分類（整列）処理に時間がかかることが課題となる。
【課題を解決するための手段】
【００１３】
本発明は、複数の計算ノードを有する並列計算機システムで、第１のグループ分けで処理対象を分割して各計算ノードに配置して処理し、第２のグループ分けに基づいてストレージ装置群に該処理結果を保存し、保存された処理結果を第１のグループ分けに従って各計算ノードに送信することで、前述の課題を解決する。
【発明の効果】
【００１４】
本発明により、受信側の計算ノードで行う分類（整列）処理に要する時間を削減することが可能となる。ひいては、並列計算を高速化することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施例である情報処理システムの構成を示すブロック図である。
【図２】非特許文献１で開示されたＭａｐＲｅｄｕｃｅと呼ばれる計算モデルを説明する図である。
【図３】非特許文献１で開示されたＭａｐＲｅｄｕｃｅ計算モデルを、並列計算装置上で動作させた場合の概念図である。
【図４】本発明が解決する課題の一例として、グラフ問題を並列計算装置上で動作させた場合の概念図である。
【図５（ａ）】本発明を考える端緒となったバケットソートによる受信側整列（Ｌｏｃａｌ  Ｓｏｒｔ）高速化について説明する図である。
【図５（ｂ）】本発明を考える端緒となったバケットソートによる受信側整列（Ｌｏｃａｌ  Ｓｏｒｔ）高速化について説明する図である。
【図６】各計算ノード間でバケツを共有することでバケットソートに必要な記憶装置の数を削減することを概念的に説明する図である。
【図７】本発明の第１の実施例による並列処理方法および並列計算機システムの動作を説明する図である。
【図８】本発明の第２の実施例による並列処理方法および並列計算機システムの動作を説明する図である。
【図９】本発明の第３の実施例による並列処理方法および並列計算機システムの動作を説明する図である。
【発明を実施するための形態】
【００１６】
以下の実施の形態においては便宜上その必要があるときは、複数のセクションまたは実施の形態に分割して説明するが、特に明示した場合を除き、それらは互いに無関係なものではなく、一方は他方の一部または全部の変形例、詳細、補足説明等の関係にある。また、以下の実施の形態において、要素の数等（個数、数値、量、範囲等を含む）に言及する場合、特に明示した場合および原理的に明らかに特定の数に限定される場合等を除き、その特定の数に限定されるものではなく、特定の数以上でも以下でも良い。
【００１７】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【実施例１】
【００１８】
図１は、本発明の実施例である情報処理システム１０１の構成を示すブロック図である。情報処理システム１０１は、複数の計算ノードＣＡＬＣ＿ＮＯＤＥ＿ｘ（ｘ＝１，２，３・・・）と、その間の通信を仲介する通信スイッチＣＯＭ＿ＳＷと、を備える並列計算機システムである。【００１９】
各計算ノードＣＡＬＣ＿ＮＯＤＥ＿ｘは、中央演算処理装置（ＣＰＵ）と、一時記憶装置ＭＥＭと、記憶装置ＳＴＯＲと、通信デバイスＣＯＭ＿ＤＥＶと、ＣＰＵ、記憶装置ＳＴＯＲ、および通信デバイスＣＯＭ＿ＤＥＶを接続するバスＢＵＳと、を備える。各計算ノードＣＡＬＣ＿ＮＯＤＥ＿ｘにおいて、ＣＰＵは、記憶装置ＳＴＯＲから必要な入力データを読み出して計算を行い、必要であれば通信デバイスＣＯＭ＿ＤＥＶを用いて、入力データ、あるいは計算結果を、他の計算ノードに送信する。一連の処理の間、ＣＰＵは必要に応じて、一時的に必要なデータや、計算の途中経過等を一時記憶装置ＭＥＭに記憶する。また、後述のように、計算ノードＣＡＬＣ＿ＮＯＤＥ＿ｘの内の一つは、再送管理ノードとして働く。【００２０】
ここで、一時記憶装置ＭＥＭには、ランダムアクセスメモリ（ＲＡＭ）を用いる。一方、記憶装置ＳＴＯＲには、フラッシュメモリ、相変化メモリやハードディスクドライブを用いる。したがって、一時記憶装置ＭＥＭは、記憶装置ＳＴＯＲに比べて、高速なアクセスが可能であるが小容量である。また、一時記憶装置ＭＥＭは高速にランダムアクセス可能であるのに対して、記憶装置ＳＴＯＲは、シーケンシャルアクセスのみでランダムアクセスは不可能、あるいは、シーケンシャルアクセス速度に比べてランダムアクセス速度が非常に遅い、といった特徴をもつことになる。【００２１】
なお、図１に示した並列計算機システムにおいて、各計算ノードが備える、ＣＰＵ、一時記憶装置ＭＥＭ、記憶装置ＳＴＯＲ、および通信デバイスＣＯＭ＿ＤＥＶは、必ずしも同じものであるとは限らず、計算ノードごとに大きさや性能が異なる場合もある。また、ＣＰＵ、一時記憶装置ＭＥＭ、記憶装置ＳＴＯＲ、および、通信デバイスＣＯＭ＿ＤＥＶの全てを備えていない計算ノードが存在する場合も、本願において開示される発明の考慮の対象としている。【００２２】
図５（ａ）および図５（ｂ）は、前述した課題の解決にあたって、本願の発明を考える端緒となったバケットソート（バケツソート）方式について説明する図である。例えば、Ｍａｐフェーズで出力されるＫｅｙが０以上の整数番号である場合を考える。なお、ここで、Ｋｅｙが０以上の整数番号である場合をとりあげたのは、説明の例にするためであり、Ｋｅｙが文字列等、整数以外のものであっても、あらかじめ各バケツの割り当て方を決めておけば、同様の方式が適用可能である。【００２３】
ここで、並列計算の一部を担当する計算ノードＣＡＬＣ＿ＮＯＤＥ＿１が処理を担当するＲｅｄｕｃｅプロセスのＫｅｙ番号が、０から９９９までの１０００種類であるとする。図５（ａ）に、このときの、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１内の処理フローを示す図を示す。Ｓｈｕｆｆｌｅフェーズで、ＣＡＬＣ＿ＮＯＤＥ＿１は、Ｋｅｙ番号が０〜９９９までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信する。受信する＜Ｋｅｙ，Ｖａｌｕｅ＞の組の順序については何も取り決めがないため、後の分類（整列）処理に備えて、受信した＜Ｋｅｙ，Ｖａｌｕｅ＞の組をいったん全て記憶装置ＳＴＯＲに記憶する必要がある。計算ノードＣＡＬＣ＿ＮＯＤＥ＿１は、全ての＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信し終わった後に、記憶装置ＳＴＯＲに記憶された全ての＜Ｋｅｙ，Ｖａｌｕｅ＞の組を読み出して、Ｋｅｙ毎に分類（整列）し、Ｒｅｄｕｃｅ処理を行う。【００２４】
ところが、図５（ａ）に示した方式では、Ｋｅｙ毎に分類（整列）する処理を、自計算ノードが受信した全ての＜Ｋｅｙ，Ｖａｌｕｅ＞の組を対象に行う必要があるため、分類（整列）に時間がかかるという問題がある。そこで、図５（ｂ）に示すように記憶装置を複数用意してバケットソート（バケツソート）を行うことも考えた。【００２５】
図５（ｂ）において、ＣＡＬＣ＿ＮＯＤＥ＿１は、記憶装置をＳＴＯＲ１〜ＳＴＯＲ１０までの１０台備えており、これらの記憶装置がバケツ群を構成している。計算ノードＣＡＬＣ＿ＮＯＤＥ＿１は、受信した＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、Ｋｅｙ番号に応じて１０台の記憶装置に振り分けて記憶する。この振り分けは、例えば、Ｋｅｙ番号が０から９９までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組はＳＴＯＲ１に、Ｋｅｙ番号が１００から１９９までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組はＳＴＯＲ２に、といった手段で行う。Ｓｈｕｆｆｌｅフェーズが終了し、全ての＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信し終わった後、最初に、記憶装置ＳＴＯＲ１に記憶された＜Ｋｅｙ，Ｖａｌｕｅ＞の組を読み出してＫｅｙ毎に分類（整列）してＲｅｄｕｃｅ処理する。記憶装置ＳＴＯＲ１内の＜Ｋｅｙ，Ｖａｌｕｅ＞の組を全て処理し終わったら、次に、記憶装置ＳＴＯＲ２に記憶された＜Ｋｅｙ，Ｖａｌｕｅ＞の組を読み出してＫｅｙ毎に分類（整列）してＲｅｄｕｃｅ処理する。その後も同様に、ＳＴＯＲ３からＳＴＯＲ１０までを順番に分類（整列）、Ｒｅｄｕｃｅ処理すればよい。【００２６】
図５（ｂ）で示した方式では、Ｋｅｙ毎に分類（整列）する処理は、記憶装置ＳＴＯＲ１からＳＴＯＲ１０ごとに行えばよいため、図５（ａ）に比べて分類（整列）処理の時間を短縮することが可能である。ここで、各記憶装置（バケツ）ＳＴＯＲ１からＳＴＯＲ１０へのアクセスは、シーケンシャルなアクセスのみであり、ランダムアクセスが低速な記憶装置を用いることができる。また、多ポート同時にシーケンシャルアクセス可能な記憶装置が使用可能な場合には、各アクセスポートを異なるＫｅｙ番号範囲（バケツ）に対応させることで、１台の記憶装置でバケツ群を構成することも可能である。なお、ここでは、バケツ群（記憶装置ＳＴＯＲ１からＳＴＯＲ１０）をＫｅｙの小さい順に割り当てたたが、Ｋｅｙ番号と記憶装置（バケツ）の対応関係が定まっていれば十分であり、必ずしもＫｅｙ番号の小さい順に割り当てる必要はない。また、Ｓｈｕｆｆｌｅフェーズを終了後に記憶装置（バケツ）を処理する順番は任意である。【００２７】
しかしながら、図５（ｂ）に示した方式では、各計算ノードに多数の記憶装置（バケツ）を用意する必要があるという問題がある。それに対して、本願発明者らは、次の構成を見出した。【００２８】
図６に、情報処理システム１０１の１０台の計算ノードＣＡＬＣ＿ＮＯＤＥ＿１〜１０がそれぞれ、１０００種類のＫｅｙ番号のＲｅｄｕｃｅ処理を担当する場合の例を示す。図５（ｂ）で示したバケットソート方式で、各計算ノードに１０台ずつの記憶装置（バケツ）を配置すると、並列計算装置全体では、１００台の記憶装置（バケツ）が必要となる。ところで、前述のように、図５（ｂ）で示したバケットソート方式では、Ｓｈｕｆｆｌｅフェーズ終了後に、自計算ノードにあるバケツを、Ｋｅｙ番号が小さい＜Ｋｅｙ，Ｖａｌｕｅ＞の組を記憶しているバケツから順に分類（整列）およびＲｅｄｕｃｅ処理を行う。Ｍａｐフェーズで出力されるＫｅｙの分布が極端にばらついていなければ、ＣＡＬＣ＿ＮＯＤＥ＿１がＫｅｙ番号０から９９のバケツを処理するのに必要な時間と、ＣＡＬＣ＿ＮＯＤＥ＿２がＫｅｙ番号１０００から１０９９のバケツを処理するのに必要な時間は、ほぼ同じであると考えられる。したがって、ＣＡＬＣ＿ＮＯＤＥ＿１がＫｅｙ番号１００から１９９のバケツの処理を始める時刻と、ＣＡＬＣ＿ＮＯＤＥ＿２がＫｅｙ番号１１００から１１９９のバケツの処理を始める時刻と、はほぼ同時刻である。本願発明者等は、このほぼ同時刻に必要となる、すなわち、ほぼ同時刻に分類（整列）・Ｒｅｄｕｃｅ処理が始まるバケツ同士を、計算ノードをまたがって共有することで、並列計算全体で必要とするバケツの数を削減することができることを見出した。【００２９】
図７は、情報処理システム１０１での、並列処理の動作の例を説明する図である。図７では、実施の形態の説明にあたって、ＣＡＬＣ＿ＮＯＤＥ＿１からＣＡＬＣ＿ＮＯＤＥ＿１０の１０台の計算ノードで並列処理が実行され、それぞれの計算ノードが、１０００種類のＫｅｙ番号のＲｅｄｕｃｅ処理を担当する場合の例を示した。しかしながら、前述のように、Ｋｅｙが整数の番号であることや、Ｒｅｄｕｃｅ処理あるいはバケツの割り当て方等は、任意である。【００３０】
図７に示した並列処理の動作では、Ｍａｐフェーズで出力される＜Ｋｅｙ，Ｖａｌｕｅ＞の組を一時的に記憶する１０台の記憶装置（バケツ）ＢＳＴＯＲ１からＢＳＴＯＲ１０と、Ｒｅｄｕｃｅ処理を行う１０台の計算ノードＣＡＬＣ＿ＮＯＤＥ＿１からＣＡＬＣ＿ＮＯＤＥ＿１０と、バケツの再送管理を行うコントローラＢＵＣＫＥＴ＿ＣＯＮＴと、が機能する。【００３１】
計算ノードＣＡＬＣ＿ＮＯＤＥ＿１〜１０は、記憶装置ＳＴＯＲ１〜１０と、ＭＡＰ処理、Ｋｅｙ毎の分類（整列）、およびＲｅｄｕｃｅ処理を行う機能を実現する。図７に示したように、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１の記憶装置ＳＴＯＲをＳＴＯＲ１、計算ノードＣＡＬＣ＿ＮＯＤＥ＿２の記憶装置ＳＴＯＲをＳＴＯＲ２、のように対応づけた。【００３２】
＜Ｋｅｙ，Ｖａｌｕｅ＞の組を一時的に記憶するバケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０は、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１の記憶装置ＳＴＯＲをＢＳＴＯＲ１、計算ノードＣＡＬＣ＿ＮＯＤＥ＿２の記憶装置ＳＴＯＲをＢＳＴＯＲ２、計算ノードＣＡＬＣ＿ＮＯＤＥ＿３の記憶装置ＳＴＯＲをＢＳＴＯＲ３、のように並列処理で計算を実行する計算ノードの記憶装置ＳＴＯＲと兼用させて実現する。このようにすることで、少資源で並列計算を実行できる。また、例えば、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１１の記憶装置ＳＴＯＲをＢＳＴＯＲ１、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１２の記憶装置ＳＴＯＲをＢＳＴＯＲ２、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１３の記憶装置ＳＴＯＲをＢＳＴＯＲ３、のように並列処理では計算を実行しない計算ノードの記憶装置ＳＴＯＲで実現してもよい。また、バケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０と、Ｒｅｄｕｃｅ処理を行う計算ノード群ＣＡＬＣ＿ＮＯＤＥ＿１からＣＡＬＣ＿ＮＯＤＥ＿１０は、それぞれ数が異なっていてもよい。バケツ群と、計算ノード群の数が異なっており、かつ計算ノード上にバケツを配置する構成では、計算ノードあたりに０以上の整数台の記憶装置（バケツ）が配置されることになる。【００３３】
バケツの再送管理を行うコントローラＢＵＣＫＥＴ＿ＣＯＮＴは、計算ノードＣＡＬＣ＿ＮＯＤＥ＿ｘの内の一つである再送管理ノードで実現される。ここで、再送管理ノードは、並列処理に寄与する計算ノードと兼用する形で実現してもよいし、並列処理の計算には関係しない計算ノードを別途用いてもよい。【００３４】
図７に示した並列処理方式では、前述のＳｈｕｆｆｌｅフェーズ（計算ノード間通信）が、さらに、バケツ送信フェーズと、バケツ再送フェーズと、の２つのフェーズに細分化される。バケツ送信フェーズでは、Ｍａｐ処理で出力される＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、Ｋｅｙに対応するＲｅｄｕｃｅ処理を行う計算ノードに直接送信するかわりに、並列処理全体で共有するバケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０に送信する。このとき、Ｋｅｙ番号を１０００で割った余りが０から９９であればＢＳＯＴＲ１に、Ｋｅｙ番号を１０００で割った余りが１００から１９９であればＢＳＯＴＲ２に、以下同様の規則にしたがって送信先のバケツを定める。このように、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１〜１０でのＭａｐ処理の結果である＜Ｋｅｙ，Ｖａｌｕｅ＞の組に対して、各計算ノードは、ＢＳＴＯＲ１〜１０のいずれかへの宛先を与える。【００３５】
Ｍａｐフェーズで出力される全ての＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、バケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０に記憶し終わると、バケツ再送フェーズに移行する。バケツ再送フェーズでは、コントローラＢＵＣＫＥＴ＿ＣＯＮＴの指示にしたがって、各バケツに記憶されている＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に再送する。具体的には、まず、バケツＢＳＴＯＲ１に記憶されている＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に再送する。このとき各計算ノードＣＡＬＣ＿ＮＯＤＥ＿１〜１０は、受信した＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、自計算ノードが備える記憶装置ＳＴＯＲ（例えば、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１であればＳＴＯＲ１が対応）に記憶する。バケツＢＳＴＯＲ１に記憶されている＜Ｋｅｙ，Ｖａｌｕｅ＞の組の再送信が完了すると、コントローラＢＵＣＫＥＴ＿ＣＯＮＴは、それを各計算ノードＣＡＬＣ＿ＮＯＤＥ＿１からＣＡＬＣ＿ＮＯＤＥ＿１０に通知する。すると、各計算ノードＣＡＬＣ＿ＮＯＤＥ＿１からＣＡＬＣ＿ＮＯＤＥ＿１０は、記憶装置ＳＴＯＲ１からＳＴＯＲ１０に記憶されている＜Ｋｅｙ，Ｖａｌｕｅ＞の組を読み出してＫｅｙ毎に分類（整列）し、Ｒｅｄｕｃｅ処理を行う。全計算ノードがＲｅｄｕｃｅ処理を終了して記憶装置ＳＴＯＲ１からＳＴＯＲ１０が空になると、コントローラＢＵＣＫＥＴ＿ＣＯＮＴは、次のバケツＢＳＴＯＲ２の再送を開始する。以下同様に、最後のバケツＢＳＴＯＲ１０まで、再送とＲｅｄｕｃｅ処理を、バケツ毎に順次行っていく。【００３６】
以上のように、図７に示した並列処理方式では、第１のグループ分けで、各計算ノードがＭＡＰ処理をするのに対し、処理結果が第２のグループ分けでＢＳＴＯＲ１〜１０の各記憶装置に送信され、さらに第１のグループ分けに従って各記憶装置から各計算ノードに再送信がなされる。これにより、並列処理全体で１０個のバケツＢＳＴＯＲ１からＢＳＴＯＲ１０を用意することで、各計算ノードにおける分類（整列）処理にかかる時間を、各計算ノードそれぞれに１０個のバケツを用意した場合（図５（ｂ）の構成）と同等まで短縮することが可能である。その一方で、計算ノード間の通信が、バケツ送信フェーズおよび、バケツ再送フェーズの２回行われるため、通信量が増大する。しかしながら、一般に、データ量Ｎに対して、計算ノード間通信に必要な時間はＮに比例するのに対して、分類（整列）にかかる時間は、Ｎ×Ｌｏｇ（Ｎ）に比例するため、データ量が大きくなるほど、分類（整列）の処理時間の短縮は全体の処理時間短縮に効果的になる。【００３７】
なお、上記の説明で、各計算ノードへのＲｅｄｕｃｅ処理を担当するＫｅｙの割り当ては単純にＫｅｙ番号の小さい順に１０００個ずつとし、各バケツへのＫｅｙの割り当て方はＫｅｙ番号を１０００で割った余りで定めたが、この決め方には任意性があり、他の割り当て方も適用可能である。一方で、本発明の効果をより高めるためには、図６に示したように、各計算ノードへのＲｅｄｕｃｅ処理を担当するＫｅｙの割り当て方と、各バケツへの割り当て方は、なるべく互いに直交の関係になるようにするのが望ましい。すなわち、第１のグループ分けの任意の一のグループに含まれる処理対象は、第２のグループ分けのそれぞれのグループに少なくとも一つ含まれるように分散されていることが望ましい。さらに、望ましい割り当て方は、Ｍａｐフェーズで出力されるＫｅｙの分布に依存しており、アプリケーションや入力データ毎に異なる。したがって、アプリケーションの設計者やユーザーが、各計算ノードへのＲｅｄｕｃｅ処理を担当するＫｅｙの割り当て方、および、各バケツへの割り当て方を、設定できるようにすることが考えられる。また、バケツの再送管理を行うコントローラＢＵＣＫＥＴ＿ＣＯＮＴをおかずに、各バケツ、および、計算ノード間で、必要な情報を都度やりとりすることで、フェーズ間の状態遷移を行うことも可能である。【００３８】
また、前述のように、情報処理システム１０１の処理対象としては、グラフ構造データもあり得る。グラフ構造データの場合には、並列処理を行う計算ノードの台数分にグラフが分割され各計算ノードに割当てられる。各計算ノードでは、割当てられた頂点群の処理が行われる。
【実施例２】
【００３９】
図８は、情報処理システム１０１での、並列処理の動作の第２の例を説明する図である。本実施例の方式は、バケットソートを複数回行うことでより精密な整列を行う方法である基数ソート（Ｒａｄｉｘ  Ｓｏｒｔ）という方法の考え方を応用し、同一のバケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０を再利用して２回バケットソートを行うことで、実質的に、バケツの数が２乗になったのと同等の効果を得ることができる。本実施例では、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を一時的に記憶するバケツ群ＢＳＴＯＲ１からＢＳＴＯＲ１０を、計算ノードＣＡＬＣ＿ＮＯＤＥ＿１の記憶装置ＳＴＯＲをＢＳＴＯＲ１、計算ノードＣＡＬＣ＿ＮＯＤＥ＿２の記憶装置ＳＴＯＲをＢＳＴＯＲ２、計算ノードＣＡＬＣ＿ＮＯＤＥ＿３の記憶装置ＳＴＯＲをＢＳＴＯＲ３、のように並列処理で計算を実行する計算ノードの記憶装置ＳＴＯＲと兼用させて実現する形式を例として説明する。【００４０】
図８に示した、処理方式では、Ｍａｐフェーズで出力される＜Ｋｅｙ，Ｖａｌｕｅ＞の組が、Ｋｅｙ番号を１００で割った余りに基づいて定まるバケツＢＳＴＯＲ１からＢＳＴＯＲ１０に送信される。この通信が全て完了後、各計算ノードは、バケツＢＳＴＯＲ１の記憶内容を読み出して、再び別のバケツＢＳＴＯＲ１からＢＳＴＯＲ１０に送信する。このとき、Ｋｅｙ番号を１０００で割った余りに基づいて送り先のバケツが定められる。バケツＢＳＴＯＲ１の再送が完了後、同様に、バケツＢＳＴＯＲ２からバケツＢＳＴＯＲ１０まで順に再送がなされる。全てのバケツの再送が完了後、再び、各計算ノードは、バケツＢＳＴＯＲ１の記憶内容を読み出して、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に再々送し、各計算ノードでＬｏｃａｌ  ＳｏｒｔおよびＲｅｄｕｃｅ処理を行う。バケツＢＳＴＯＲ１の処理が完了後、同様に、バケツＢＳＴＯＲ２からバケツＢＳＴＯＲ１０まで順に再々送、および各計算ノードでのＬｏｃａｌ  ＳｏｒｔおよびＲｅｄｕｃｅ処理が行われる。【００４１】
以上のように、図８に示した、処理方式では、各計算ノードにおける分類（整列）処理にかかる時間を、各計算ノードそれぞれに１００個のバケツを用意した場合と同等まで短縮することが可能である。なお、バケツ送信および再送信の回数を２回より多くすることも可能である。再送信の回数を増やすことで、各計算ノードでのＫｅｙ毎の分類（整列）にかかる時間が減少する一方で、計算ノード間の通信量が増加するので、アプリケーションおよび入力データに応じて最適なバケツ再送信の回数が存在する。したがって、アプリケーションの設計者やユーザーが、バケツ再送信の回数を設定できるようにすることが考えられる。
【実施例３】
【００４２】
図９は、情報処理システム１０１での、並列処理の動作の第２の例を説明する図である。本実施例の方式は、前述の図７に示した本発明の実施例１においては、バケツの再送信は、バケツ送信フェーズが完了した後、すなわち、Ｍａｐフェーズで出力される＜Ｋｅｙ，Ｖａｌｕｅ＞の組が、全てのバケツＢＳＴＯＲ１からＢＳＴＯＲ１０に記憶された後、に開始される。したがって、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）は、バケツ再送信フェーズが開始するまで、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を一切受け取ることができない。しかしながら、もし、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）が、早い段階から＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信することができれば、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信しながら、平行して（オンラインで）少しずつＫｅｙ毎の分類（整列）の処理を行うことで、全体の処理時間を短縮できる可能性があると本願発明者らは考えた。【００４３】
図９に示した、処理方式においては、各バケツＢＳＴＯＲ１からＢＳＴＯＲ１０に、それぞれ、Ｋｅｙ番号を１０００で割った余りが９１から１８１、１８２から２７２、以下同様に、９０個または９１個のＫｅｙ番号を割り当てる。９０または９１は、１つの計算ノードがＲｅｄｕｃｅ処理を担当するＫｅｙの数（１０００個）を、バケツ群の個数（１０台）＋１、で割った数に相当する。また、全てのＭａｐ処理が完了するのに必要な時間をあらかじめ見積もっておき、全てのＭａｐ処理が完了する時間の１／１０の時間が経過するごとに、順にバケツＢＳＴＯＲ１からＢＳＴＯＲ１０の記憶内容を読み出して、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に再送信する。こうすることで、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）が、早い段階から＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信することができ、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信しながら、平行して（オンラインで）少しずつＫｅｙ毎の分類（整列）の処理を行うことができる。【００４４】
具体的には、Ｍａｐフェーズの開始に先立って、全てのＭａｐ処理にかかる時間Ｔｍａｐをなんらかの手段で見積もっておく。通常、Ｍａｐプロセスの個数や、処理内容はあらかじめ分かっているためＭａｐ処理全体の処理時間の見積りは可能である。また、この見積もり時間は多少誤差があっても、以下の動作には支障がない。【００４５】
Ｍａｐフェーズ開始後、Ｍａｐフェーズで出力される＜Ｋｅｙ，Ｖａｌｕｅ＞の組を、もしＫｅｙ番号に対応するバケツが存在するならそのバケツにあてて、もしＫｅｙ番号に対応するバケツが存在しないのであれば、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）にあてて送信する。したがって、Ｋｅｙ番号が０から９０までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組は、バケツ群に送られることなく、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に向けて直接送信されることになる。【００４６】
その後、Ｍａｐフェーズ開始からＴｍａｐ／１０の時間が経過したタイミングで、バケツＢＳＴＯＲ１の記憶内容を読み出して本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）にあてて再送信する。これ以降は、Ｍａｐ処理で出力された＜Ｋｅｙ，Ｖａｌｕｅ＞の組は、対応するバケツが存在しないＫｅｙ番号が０から９０までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組に加えて、バケツＢＳＴＯＲ１が担当していたＫｅｙ番号が９１から１８１までの＜Ｋｅｙ，Ｖａｌｕｅ＞の組も、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に向けて直接送信する。その後、さらにＴｍａｐ／１０だけ時間が経過して、Ｍａｐフェーズ開始から（Ｔｍａｐ／１０）×２の時間が経過したタイミングで、バケツＢＳＴＯＲ２の記憶内容を読み出して本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）にあてて再送信する。これ以降は、Ｍａｐ処理で出力された＜Ｋｅｙ，Ｖａｌｕｅ＞の組は、Ｍａｐ処理でバケツＢＳＴＯＲ２が担当していた＜Ｋｅｙ，Ｖａｌｕｅ＞の組が出力された場合にも、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に向けて直接送信する。以下同様に、さらにＴｍａｐ／１０だけ時間が経過するたびにバケツを本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）に向けて再送信し、それ以降、Ｍａｐ処理で出力された＜Ｋｅｙ，Ｖａｌｕｅ＞の組は、Ｋｅｙに対応するバケツが存在して、かつ、そのバケツが再送信済みでない場合には、そのバケツにあてて、そうでない場合には、直接、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）にあてて送信する。【００４７】
以上の説明では、簡単のために、各バケツが担当するＫｅｙの数を全て同じにし、また、バケツの再送信を、全てのＭａｐ処理にかかる時間Ｔｍａｐを等間隔に分割したタイミングで行うことにしたが、実際には、これではバケツ再送信のタイミングで各バケツが記憶している＜Ｋｅｙ，Ｖａｌｕｅ＞の組の数がバケツによって異なるため記憶装置の利用効率や、ネットワークの効率が低下する場合がある。なぜなら、バケツＢＳＴＯＲ１はＴｍａｐ／１０の時間しか＜Ｋｅｙ，Ｖａｌｕｅ＞の組の記憶を行わないのに対して、バケツＢＳＴＯＲ１０はＴｍａｐの時間＜Ｋｅｙ，Ｖａｌｕｅ＞の組の記憶を行う。したがって、もし、Ｍａｐフェーズで出力されるＫｅｙの分布が一様であるならば、バケツの再送信のタイミングで、バケツＢＳＴＯＲ１は、バケツＢＳＴＯＲ１０の１／１０の＜Ｋｅｙ，Ｖａｌｕｅ＞の組しか記憶していないことになる。バケツ再送信のタイミングでの各バケツが記憶している＜Ｋｅｙ，Ｖａｌｕｅ＞の組の数をなるべく同じにするには、各バケツが担当するＫｅｙの数を、バケツＢＳＴＯＲ１では多くし、バケツＢＳＴＯＲ１０では少なくすることが考えられる。あるいは、バケツ再送信のタイミングを単純に、Ｔｍａｐを等分割するのではなく、前のバケツを再送信してから次のバケツを再送信するまでの時間を、だんだん短くしていくといった方策をとってもよい。【００４８】
以上のように、図９に示した、本発明の第３の実施例による処理方式では、Ｍａｐ処理と並行してバケツを順に再送信することで、本来の宛先計算ノード（Ｒｅｄｕｃｅ処理を行う計算ノード）が、早い段階から＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信することができ、＜Ｋｅｙ，Ｖａｌｕｅ＞の組を受信しながら、平行して（オンラインで）少しずつＫｅｙ毎の分類（整列）の処理を行うことができ、全体の処理時間を短縮することができる。
【符号の説明】
【００４９】
１０１：情報処理システム、ＣＡＬＣ＿ＮＯＤＥ＿ｘ：計算ノード、ＣＯＭ＿ＳＷ：通信スイッチ、ＭＥＭ：一時記憶装置、ＳＴＯＲ：記憶装置、ＣＯＭ＿ＤＥＶ：通信デバイス、ＳＴＯＲ：記憶装置、ＢＵＳ：バス、ＢＳＴＯＲ１〜１０：記憶装置（バケツ）、ＢＵＣＫＥＴ＿ＣＯＮＴ：バケツの再送管理を行うコントローラ。
【図１】
0005965498.tif 000002
【図２】
0005965498.tif 000003
【図３】
0005965498.tif 000004
【図４】
0005965498.tif 000005
【図５（ａ）】
0005965498.tif 000006
【図５（ｂ）】
0005965498.tif 000007
【図６】
0005965498.tif 000008
【図７】
0005965498.tif 000009
【図８】
0005965498.tif 000010
【図９】
0005965498.tif 000011