(57)【特許請求の範囲】
【請求項１】
対角線上の第１の位置を基点としたとき、第１の軸の値が前記第１の位置と同じ第２および第３の位置と第２の軸の値が前記第１の位置と同じ第４および第５の位置とにノードが存在するように、座標が付与される複数のノードに、データ要素を配置し、
対角線上の各ノードを基点として、前記第１の位置のノードに配置された各データ要素を、前記第２および第４の位置のノードに送信すると共に、前記第３および第５の位置のノードの一方に選択的に送信する第１の送信処理と、前記第２の位置のノードに配置された各データ要素を、前記第１、第４および第５の位置のノードに送信する第２の送信処理と、前記第３の位置のノードに配置された各データ要素を、前記第１、第２および第４の位置のノードに送信する第３の送信処理とを実行し、
各ノードは、自ノードに配置されたデータ要素と、前記第１、第２および第３の送信処理を通じて受信したデータ要素とを用いてデータ処理を行う、分散処理方法。
【請求項２】
対角線上の各ノードは、自ノードを基点として収集した複数のデータ要素の間の組み合わせに対してデータ処理を行い、対角線上でない各ノードは、対角線上の１つのノードを基点として収集したデータ要素と対角線上の他のノードを基点として収集したデータ要素との間の組み合わせに対してデータ処理を行う、請求項１記載の分散処理方法。
【請求項３】
前記複数のノードには一辺のノード数が２Ｋ＋１（Ｋは１以上の整数）になるよう座標が付与され、前記第２、第３、第４および第５の位置のノードとしてそれぞれＫ個のノードが割り当てられる、請求項２記載の分散処理方法。
【請求項４】
対角線上の第１の位置を基点としたとき、第１の軸の値が前記第１の位置と同じ第２および第３の位置と第２の軸の値が前記第１の位置と同じ第４および第５の位置とにノードが存在するように、座標が付与される複数のノードを有し、
対角線上の各ノードを基点として、前記第１の位置のノードに配置された各データ要素を、前記第２および第４の位置のノードに送信すると共に、前記第３および第５の位置のノードの一方に選択的に送信する第１の送信処理と、前記第２の位置のノードに配置された各データ要素を、前記第１、第４および第５の位置のノードに送信する第２の送信処理と、前記第３の位置のノードに配置された各データ要素を、前記第１、第２および第４の位置のノードに送信する第３の送信処理とを実行し、
各ノードは、自ノードに配置されたデータ要素と、前記第１、第２および第３の送信処理を通じて受信したデータ要素とを用いてデータ処理を行う、分散処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は分散処理方法および分散処理システムに関する。
【背景技術】
【０００２】
現在、コンピュータなどのノードを複数用いて情報処理を行う分散処理システムが広く利用されている。複数のノードを並列に動作させて大量のデータを処理する分散処理システムは、並列データ処理システムと呼ぶこともできる。並列データ処理システムには、並列関係データベースや分散キーバリューストアなどの高レベルのデータ管理ソフトウェアを利用したものや、高レベルのデータ管理ソフトウェアを利用せずにユーザが実装した並列処理プログラムに従って動作するものが含まれる。
【０００３】
データ処理では、複数のデータ要素を含むデータ集合に対して、集合演算を行うことがある。例えば、関係データベースの分野で行われるジョイン演算では、２つのテーブルを指定し、一方のテーブル内の１つのタプル（データのレコード）と他方のテーブル内の１つのタプルとの組み合わせに対して、データ処理を行う。１つのテーブルを指定し、当該１つのテーブル内の２つのタプルの組み合わせに対して、データ処理を行うこともある。また、例えば、科学技術計算の分野では、行列として表現したベクトルの集合に対して、行列積などの行列演算を行うことがある。
【０００４】
大量のデータを処理する場合には、複数のノードを効率的に利用することが好ましい。例えば、ｎ次元の超立方体（ハイパーキューブ）型の並列演算装置であって、２つのデータ集合が複数のセルに均等に分散された状態から、各セルに配置されたデータを一定の範囲にブロードキャストすることで、２つのデータ集合の直積を演算するものが提案されている。また、処理エレメントの集合である三角形アレイを、複数の小さな三角形アレイに分割して、複数の三角形アレイを相互接続する並列コンピュータが提案されている。
【０００５】
また、第１段目のプロセッサ群が、データを分割して中間プロセッサ群に分配し、中間プロセッサ群が、同一種別のデータが集められるようにデータを分類して第２段目のプロセッサ群に分配する並列プロセッサ装置が提案されている。また、矩形状に配置された複数の処理要素それぞれが、ただ１つの受信ポートとただ１つの送信ポートとを備えるようにし、通信経路を制限したアレイプロセッサが提案されている。また、プロセッサ群を複数のグループに分割し、各グループ内でデータ転送を行った後、複数のステップに分けてグループ間でデータ転送を行う並列計算機システムが提案されている。
【０００６】
また、プロセッサ群を階層的に複数のサブシステムに分割し、計算問題を階層的に複数のサブ問題に分割して複数のサブシステムに割り当て、計算問題を解く分散処理システムが提案されている。この分散処理システムでは、２つのサブシステムが通信を行う場合、それらサブシステム内の対応関係にあるプロセッサ同士のみが通信を行う。例えば、一方のサブシステムがプロセッサ＃０００，＃００１を含み、他方のサブシステムがプロセッサ＃０１０，＃０１１を含む場合、プロセッサ＃０００とプロセッサ＃０１０が通信し、プロセッサ＃００１とプロセッサ＃０１１が通信する。各プロセッサは、例えば、最初にサブシステムを跨がる通信を行い、その後に同一サブシステム内で閉じた通信を行う。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平２−１６３８６６号公報
【特許文献２】特開平６−１９８６２号公報
【特許文献３】特開平９−６７３２号公報
【特許文献４】国際公開第９９／００７４３号
【特許文献５】特開２００３−６７３５４号公報
【非特許文献】
【０００８】
【非特許文献１】Shantanu Dutt and Nam Trinh, "Are There Advantages to High-Dimension Architectures?: Analysis of K-ary n-cubes for the Class for Parallel Divide-and-Conquer Algorithms", Proceedings of the 10th ACM (Association for Computing Machinery) International Conference on Supercomputing (ICS), 1996
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、前述のジョイン演算のように同じデータ要素が複数回使用されるデータ処理を、複数のノードを並列に用いて実行する場合には、データ要素を複製しノード間で送信する処理が発生し得る。このとき、各ノードが自分の使用するデータ要素を取得するために、どの様な手順でデータ送信を行えば効率的となるかが問題となる。
【００１０】
例えば、１つのデータ集合内の２つのデータ要素の組み合わせを全パターンについて処理するような、複数のノードへの処理の分割が単純ではないデータ処理では、データ要素の複製およびノード間での送信を効率化することも容易ではない。
【００１１】
一側面では、本発明は、データ処理に用いるデータ要素をノード間で効率的に送信できる分散処理方法および分散処理システムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
一側面では、分散処理方法が提供される。分散処理方法では、対角線上の第１の位置を基点としたとき、第１の軸の値が第１の位置と同じ第２および第３の位置と第２の軸の値が第１の位置と同じ第４および第５の位置とにノードが存在するように、座標が付与される複数のノードに、データ要素を配置する。対角線上の各ノードを基点として、第１の位置のノードに配置された各データ要素を、第２および第４の位置のノードに送信すると共に、第３および第５の位置のノードの一方に選択的に送信する第１の送信処理と、第２の位置のノードに配置された各データ要素を、第１、第４および第５の位置のノードに送信する第２の送信処理と、第３の位置のノードに配置された各データ要素を、第１、第２および第４の位置のノードに送信する第３の送信処理とを実行する。各ノードは、自ノードに配置されたデータ要素と、第１、第２および第３の送信処理を通じて受信したデータ要素とを用いてデータ処理を行う。
【００１３】
また、一側面では、対角線上の第１の位置を基点としたとき、第１の軸の値が第１の位置と同じ第２および第３の位置と第２の軸の値が第１の位置と同じ第４および第５の位置とにノードが存在するように、座標が付与される複数のノードを有する分散処理システムが提供される。分散処理システムは、対角線上の各ノードを基点として、第１の位置のノードに配置された各データ要素を、第２および第４の位置のノードに送信すると共に、第３および第５の位置のノードの一方に選択的に送信する第１の送信処理と、第２の位置のノードに配置された各データ要素を、第１、第４および第５の位置のノードに送信する第２の送信処理と、第３の位置のノードに配置された各データ要素を、第１、第２および第４の位置のノードに送信する第３の送信処理とを実行する。各ノードは、自ノードに配置されたデータ要素と、第１、第２および第３の送信処理を通じて受信したデータ要素とを用いてデータ処理を行う。
【発明の効果】
【００１４】
一側面によれば、データ処理に用いるデータ要素をノード間で効率的に送信できる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態の分散処理システムを示す図である。
【図２】第２の実施の形態の分散処理システムを示す図である。
【図３】第３の実施の形態の情報処理システムを示す図である。
【図４】ノードのハードウェア例を示すブロック図である。
【図５】虱潰しジョインを示す図である。
【図６】虱潰しジョインの実行結果の例を示す図である。
【図７】第３の実施の形態のノード関係を示す図である。
【図８】ノード行数とデータ送信量との関係を示すグラフである。
【図９】ノード間でのデータのリレー方法の例を示す図である。
【図１０】第３の実施の形態のソフトウェア例を示すブロック図である。
【図１１】第３の実施の形態のジョインの手順例を示すフローチャートである。
【図１２】第３の実施の形態のデータ配置例を示す図（その１）である。
【図１３】第３の実施の形態のデータ配置例を示す図（その２）である。
【図１４】第３の実施の形態のデータ配置例を示す図（その３）である。
【図１５】第４の実施の形態の情報処理システムを示す図である。
【図１６】第４の実施の形態のノード関係を示す図である。
【図１７】第４の実施の形態のソフトウェア例を示すブロック図である。
【図１８】第４の実施の形態のジョインの手順例を示すフローチャートである。
【図１９】第４の実施の形態のデータ配置例を示す図（その１）である。
【図２０】第４の実施の形態のデータ配置例を示す図（その２）である。
【図２１】第４の実施の形態のデータ配置例を示す図（その３）である。
【図２２】第４の実施の形態のデータ配置例を示す図（その４）である。
【図２３】三角ジョインを示す図である。
【図２４】三角ジョインの実行結果の例を示す図である。
【図２５】第５の実施の形態のノード関係を示す図である。
【図２６】第５の実施の形態のジョインの手順例を示すフローチャートである。
【図２７】第５の実施の形態のデータ配置例を示す図（その１）である。
【図２８】第５の実施の形態のデータ配置例を示す図（その２）である。
【図２９】第６の実施の形態のノード関係を示す図である。
【図３０】第６の実施の形態のジョインの手順例を示すフローチャートである。
【図３１】第６の実施の形態のデータ配置例を示す図（その１）である。
【図３２】第６の実施の形態のデータ配置例を示す図（その２）である。
【図３３】第７の実施の形態のノード関係を示す図である。
【図３４】第７の実施の形態のジョインの手順例を示すフローチャートである。
【図３５】第７の実施の形態のデータ配置例を示す図（その１）である。
【図３６】第７の実施の形態のデータ配置例を示す図（その２）である。
【図３７】第８の実施の形態のジョインの手順例を示すフローチャートである。
【図３８】第８の実施の形態のデータ配置例を示す図（その１）である。
【図３９】第８の実施の形態のデータ配置例を示す図（その２）である。
【図４０】第９の実施の形態のノード関係を示す図である。
【図４１】第９の実施の形態のジョインの手順例を示すフローチャートである。
【図４２】第９の実施の形態のデータ配置例を示す図（その１）である。
【図４３】第９の実施の形態のデータ配置例を示す図（その２）である。
【図４４】第９の実施の形態のデータ配置例を示す図（その３）である。
【図４５】第１０の実施の形態のノード関係を示す図である。
【図４６】第１０の実施の形態のジョインの手順例を示すフローチャートである。
【図４７】第１０の実施の形態のデータ配置例を示す図（その１）である。
【図４８】第１０の実施の形態のデータ配置例を示す図（その２）である。
【図４９】第１０の実施の形態のデータ配置例を示す図（その３）である。
【図５０】第１０の実施の形態のデータ配置例を示す図（その４）である。
【図５１】第１０の実施の形態のデータ配置例を示す図（その５）である。
【発明を実施するための形態】
【００１６】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の分散処理システムを示す図である。第１の実施の形態の分散処理システムは、ノード１ａ，１ｂ，１ｃ，１ｄおよび通信装置３ａ，３ｂを有する。
【００１７】
ノード１ａ，１ｂ，１ｃ，１ｄは、データ処理を行う情報処理装置である。ノード１ａ，１ｂ，１ｃ，１ｄは、例えば、ＣＰＵ（Central Processing Unit）などのプロセッサとＲＡＭ（Random Access Memory）やＨＤＤ（Hard Disk Drive）などの記憶装置とを備えるコンピュータであり、ＰＣ（Personal Computer）やワークステーションやブレードサーバと呼ばれるものでもよい。通信装置３ａ，３ｂは、レイヤ２スイッチなどのデータを転送するネットワーク中継装置である。通信装置３ａと通信装置３ｂとの間は、直接接続されていてもよいし、上位の通信装置を介して接続されていてもよい。
【００１８】
ノード１ａ，１ｂは、通信装置３ａに接続されており、ノードの集合であるグループ＃１に含まれる。ノード１ｃ，１ｄは、通信装置３ｂに接続されており、ノードの集合であるグループ＃２に含まれる。各グループは、３個以上のノードを含んでいてもよい。分散処理システムは、更に他のグループを有してもよい。グループは、複数のノードを仮想的に１つのノードと見なしたものと考えることもでき、仮想ノードと呼んでもよい。ここで、任意の２つのグループ間には、対応するノードが存在する。グループ＃１のノード１ａとグループ＃２のノード１ｃが一対一の対応関係にあり、グループ＃１のノード１ｂとグループ＃２のノード１ｄが一対一の対応関係にある。
【００１９】
ノード１ａ，１ｂ，１ｃ，１ｄには、データ集合に含まれるデータ要素が配置される。データ要素は、データ処理開始のコマンドが入力される前に配置してもよいし、コマンドが入力された後に分散処理システムが配置してもよい。データ要素は、好ましくは、データ処理に用いる複数のノードにできる限り均等に分散され、また、同じデータ要素が異なるノードに重複して配置されない（複製されていない）ようにする。配置されるデータ要素は、１種類のデータ要素（１つのデータ集合に含まれるもの）でもよいし、２種類以上のデータ要素（２以上のデータ集合に含まれるもの）であってもよい。
【００２０】
ノード１ａ，１ｂ，１ｃ，１ｄにデータ要素が配置されてから、ノード１ａ，１ｂ，１ｃ，１ｄが並列データ処理を開始するまでに、各ノードが自ノードで使用するデータ要素を取得するため、ノード間でデータ要素が複製される。第１の実施の形態の分散処理システムは、第１段階目としてグループ間でデータ要素を複製し、第２段階目としてグループを跨がらずに各グループ内でデータ要素を複製する。
【００２１】
第１段階目でグループ＃１がグループ＃２からデータ要素を受信するとき、ノード１ａは、通信装置３ａ，３ｂを介して自ノードに対応するノード１ｃと通信し、ノード１ｃに配置されたデータ要素を受信する。また、ノード１ｂは、通信装置３ａ，３ｂを介して自ノードに対応するノード１ｄと通信し、ノード１ｄに配置されたデータ要素を受信する。同様に、グループ＃２がグループ＃１からデータ要素を受信してもよい。その場合、通信装置３ａ，３ｂを介して、ノード１ｃがノード１ａに配置されたデータ要素を受信し、ノード１ｄがノード１ｂに配置されたデータ要素を受信する。
【００２２】
第２段階目でグループ＃１内でデータ要素を複製するとき、ノード１ａ，１ｂは、グループ＃１内の少なくとも１つの他のノードから、当該他のノードに配置されたデータ要素と、当該他のノードがグループ＃２を含む他グループから受信したデータ要素とを受信する。各ノードの通信相手は、グループ＃１内の複数のノードに対して付与された論理的な接続関係に応じて決まる。例えば、ノード１ａは、ノード１ｂから、ノード１ｂに配置されたデータ要素と、第１段階目でノード１ｂがノード１ｄから受信したデータ要素とを受信する。また、ノード１ｂは、ノード１ａから、ノード１ａに配置されたデータ要素と、第１段階目でノード１ａがノード１ｃから受信したデータ要素とを受信する。同様に、グループ＃２内において、ノード１ｃ，１ｄの間でデータ要素を複製してもよい。
【００２３】
ノード１ａ，１ｂ，１ｃ，１ｄは、以上の第１段階目および第２段階目の複製を通じて収集したデータ要素を用いて、データ処理を行う。各ノードは、自ノードに配置されたデータ要素と、第１段階目で他グループの対応するノードから受信したデータ要素と、第２段階目で同一グループ内の他のノードから受信したデータ要素とをもっている。例えば、各ノードは、データ集合に関して２つの部分集合を取得した場合、一方の部分集合に含まれる１つのデータ要素と他方の部分集合に含まれる１つのデータ要素との組み合わせ全てに対して、データ処理を行うことが考えられる。また、例えば、各ノードは、データ集合に関して１つの部分集合を取得した場合、その部分集合に含まれる２つのデータ要素の組み合わせ全てに対して、データ処理を行うことが考えられる。
【００２４】
第１の実施の形態の分散処理システムによれば、ノード１ａ，１ｂ，１ｃ，１ｄと通信装置３ａ，３ｂとの接続関係を考慮してグループを形成することで、データ処理に用いるデータ要素をノード間で効率的に複製し送信することができる。
【００２５】
例えば、他の方法として、ノード１ｃのデータ要素をノード１ｄ，ノード１ａ，ノード１ｂに巡回リレーし、ノード１ｄのデータ要素をノード１ａ，ノード１ｂ，ノード１ｃに巡回リレーするものが考えられる。しかし、この方法では、同一の通信装置下で行われるノード１ａ，１ｂ間およびノード１ｃ，１ｄ間の通信と、異なる通信装置に跨がって行われるノード１ｂ，１ｃ間およびノード１ｄ，１ａ間の通信とで、遅延時間が異なることになる。これに対し、第１段階目で異なる通信装置に跨がる通信を纏めて行い、第２段階目で同一の通信装置下の通信を纏めて行うことで、通信の並列化が容易となる。
【００２６】
なお、第１の実施の形態では、１階層のグループを形成する例を説明したが、グループを入れ子にして２階層以上のグループを形成するようにしてもよい。また、運用上などの理由から、通信装置３ａ，３ｂを同一の通信装置とし、当該同一の通信装置にグループ＃１のノード１ａ，１ｂとグループ＃２のノード１ｃ，１ｄを接続することもある。
【００２７】
もちろん、第１の実施の形態で述べたノードのグループ化の考え方は、第３の実施の形態以降で説明する虱潰しジョインや三角ジョインだけでなく、他の並列データ処理にも応用可能である。例えば、上記のノードのグループ化の考え方を、本出願の発明者の一人が発明した並列ソート方式（特許第２５０９９２９号）に応用することもできる。また、上記のノードのグループ化の考え方を、データベースの分野のハッシュジョイン、ハッシュ関数を用いたデータグループ化、データの重複除去、２つのデータ集合の共通集合や和集合を求める集合演算、ソートを用いたマージジョインなどにも応用できる。
【００２８】
すなわち、上記のノードのグループ化の考え方は、一般に、いわゆる分割統治法によって解くことができる計算問題であって、データ数が小さく元の問題と同種の複数の部分問題に分割可能であり、これらの部分問題を解くことによって全体を解くことができ、データをノード間で送信し合うことになるような計算問題に対して、適用可能である。
【００２９】
［第２の実施の形態］
図２は、第２の実施の形態の分散処理システムを示す図である。第２の実施の形態の分散処理システムは、ノード２ａ〜２ｉを有する。ノード２ａ〜２ｉは、データ処理を行う情報処理装置であり、例えば、ＣＰＵなどのプロセッサとＲＡＭやＨＤＤなどの記憶装置とを備えるコンピュータである。ノード２ａ〜２ｉは、１つの通信装置（例えば、レイヤ２スイッチ）に接続されてもよいし、複数の通信装置に分散して接続されてもよい。
【００３０】
ノード２ａ〜２ｉには、第１の軸（例えば、Ｘ軸）の値と第２の軸（例えば、Ｙ軸）の値とを含む座標が付与され、論理的に格子状の接続関係が付与される。ノード２ａ〜２ｉのうち、ノード２ａ，２ｅ，２ｉが対角線上にある。ここで、対角線上のある位置＃１を基点としたときに、第１の軸の値が位置＃１と同じ位置＃２，＃３と、第２の軸の値が位置＃１と同じ位置＃４，＃５とに、それぞれＫ個（Ｋは１以上の整数）のノードが存在する。ノード２ａを基点とした場合、位置＃２にノード２ｂがあり、位置＃３にノード２ｃがあり、位置＃４にノード２ｄがあり、位置＃５にノード２ｇがある。
【００３１】
ノード２ａ〜２ｉには、データ集合に含まれる１以上のデータ要素が配置される。データ要素は、データ処理開始のコマンドが入力される前に配置してもよいし、コマンドが入力された後に分散処理システムが配置してもよい。データ要素は、好ましくは、データ処理に用いる複数のノードにできる限り均等に分散され、また、同じデータ要素が異なるノードに重複して配置されない（複製されていない）ようにする。配置されるデータ要素は、好ましくは、１種類のデータ要素（１つのデータ集合に含まれるもの）である。
【００３２】
ノード２ａ〜２ｉにデータ要素が配置されてから、ノード２ａ〜２ｉが並列データ処理を開始するまでに、各ノードが自ノードで使用するデータ要素を取得するため、ノード間でデータ要素が複製される。第２の実施の形態の分散処理システムは、対角線上の各ノード（位置＃１）を基点として、以下の第１〜第３の送信処理を実行する。
【００３３】
第１の送信処理では、位置＃１のノードに配置された各データ要素を、位置＃２，＃４のノードに送信する。ノード２ａを基点とした場合、ノード２ａに配置された各データ要素が、ノード２ｂ，２ｄに複製される。更に、第１の送信処理では、位置＃１のノードに配置された各データ要素を、位置＃３のノードおよび位置＃５のノードの一方に選択的に送信する。ノード２ａを基点とした場合、ノード２ａに配置された各データ要素が、ノード２ｃまたはノード２ｇに複製される。すなわち、ノード２ａに配置された各データ要素が、ノード２ｂ，２ｄ，２ｃに複製されるか、または、ノード２ｂ，２ｃ，２ｇに複製される。ノード２ａに複数のデータ要素が配置されている場合、ノード２ｃに複製されるデータ要素の数とノード２ｇに複製されるデータ要素の数は、できる限り等しいことが好ましい。例えば、複製されるデータ要素数の差を高々１個にする。
【００３４】
第２の送信処理では、位置＃２のノードに配置されたデータ要素を、位置＃１，＃４，＃５のノードに送信する。ノード２ａを基点とした場合、ノード２ｂに配置されたデータ要素が、ノード２ａ，２ｄ，２ｇに複製される。第３の送信処理では、位置＃３のノードに配置されたデータ要素を、位置＃１，＃２，＃４のノードに送信する。ノード２ａを基点とした場合、ノード２ｃに配置されたデータ要素が、ノード２ａ，２ｂ，２ｄに複製される。
【００３５】
なお、位置＃２にＫ個のノードが存在する場合、位置＃２の各ノードから位置＃２の他のＫ−１個のノードにもデータが送信され得る。位置＃３についても同様である。
これにより、第１の軸の値が同じ位置＃１，＃２，＃３のノードに配置されたデータ要素が、対角線上の位置＃１のノードに集められたことになる。また、位置＃２，＃４のノードは、位置＃１に集められたデータ要素の全てをもち、位置＃３，＃５のノードは、位置＃１に集められたデータ要素を二分割した一方のみをそれぞれもつことになる。
【００３６】
各ノードは、自ノードに配置されたデータ要素と、上記の第１〜第３の送信処理を通じて受信したデータ要素とを用いて、データ処理を行う。例えば、対角線上の各ノードは、自ノードを基点として収集した複数のデータ要素の間の組み合わせに対してデータ処理を行うことができる。また、例えば、対角線上でない各ノードは、対角線上の１つのノードを基点として収集したデータ要素と対角線上の他のノードを基点として収集したデータ要素との間の組み合わせに対してデータ処理を行うことができる。
【００３７】
第２の実施の形態の分散処理システムによれば、データ処理に用いるデータ要素をノード２ａ〜２ｉに配置した状態から、データ要素をノード間で効率的に送信できる。特に、第２の実施の形態の分散処理システムは、１つのデータ集合に含まれる２つのデータ要素の組み合わせ全てに対して行うデータ処理を並列化するときに有効である。その場合、データ処理をノード２ａ〜２ｉにできる限り均等に割り振ることができ、また、各ノードに対し当該ノードが使用するデータ要素を過不足なく複製することができる。
【００３８】
［第３の実施の形態］
図３は、第３の実施の形態の情報処理システムを示す図である。この情報処理システムは、ノード１１〜１６、クライアント３１およびネットワーク４１を有する。
【００３９】
ノード１１〜１６は、ネットワーク４１に接続されたコンピュータであり、ＰＣやワークステーションやブレードサーバと呼ばれるものでもよい。ノード１１〜１６は、並列にデータ処理を実行することができる。ネットワーク４１は、データ要素やコマンドを転送する１またはそれ以上の通信装置（例えば、レイヤ２スイッチ）を備える。クライアント３１は、ユーザが操作する端末装置としてのコンピュータである。クライアント３１は、ネットワーク４１を介して、何れかのノードにデータ処理開始のコマンドを送信する。
【００４０】
図４は、ノードのハードウェア例を示すブロック図である。ノード１１は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信部１０７を有する。ノード１２〜１６およびクライアント３１も、ノード１１と同様のハードウェアを用いて実現できる。なお、ノード１１〜１６は、ブレードサーバのように、画像信号処理部１０４や入力信号処理部１０５を備えていなくてもよく、必要に応じて後から追加できるようにしてもよい。
【００４１】
ＣＰＵ１０１は、ノード１１を制御するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部を読み出し、ＲＡＭ１０２に展開してプログラムを実行する。なお、ノード１１は、複数のプロセッサを備えてもよい。
【００４２】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやデータを一時的に記憶する揮発性メモリである。なお、ノード１１は、ＲＡＭ以外の種類のメモリを備えてもよい。
ＨＤＤ１０３は、ＯＳ（Operating System）プログラムやアプリケーションプログラムなどの各種のプログラムおよびデータを記憶する不揮発性の記憶装置である。ＨＤＤ１０３は、ＣＰＵ１０１の命令に従って、内蔵の磁気ディスクに対してデータの読み書きを行う。なお、ノード１１は、ＨＤＤ以外の不揮発性の記憶装置（例えば、ＳＳＤなど）を備えてもよく、複数の記憶装置を備えていてもよい。
【００４３】
画像信号処理部１０４は、ＣＰＵ１０１の命令に従って、ノード１１に接続されたディスプレイ４２に画像を出力する。ディスプレイ４２としては、例えば、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイを用いることができる。
【００４４】
入力信号処理部１０５は、ノード１１に接続された入力デバイス４３から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス４３としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００４５】
ディスクドライブ１０６は、記録媒体４４に記録されたプログラムやデータを読み取る駆動装置である。記録媒体４４として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１の命令に従って、記録媒体４４から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００４６】
通信部１０７は、ネットワーク４１を介して、ノード１２〜１６やクライアント３１と通信する通信インタフェースである。通信部１０７は、有線通信インタフェースであってもよいし、無線通信インタフェースであってもよい。
【００４７】
次に、第３の実施の形態の情報処理システムが実行する「虱潰しジョイン」について説明する。なお、「虱潰しジョイン」は、単にジョインの一種として扱われることがある。
虱潰しジョインでは、数式（１）に示すように、２つのデータ集合Ａ，Ｂが与えられる。データ集合Ａは、ｍ個（ｍは正の整数）のデータ要素ａ1，ａ2，…，ａmを含み、データ集合Ｂは、ｎ個（ｎは正の整数）のデータ要素ｂ1，ｂ2，…，ｂnを含む。各データ要素は、好ましくは、一意な識別子を含んでおり、識別子と値の組となっている。虱潰しジョインの結果は、数式（２）に示すように、データ集合Ａのデータ要素ａとデータ集合Ｂのデータ要素ｂとの順序対（順序を考慮した組）全てに対して、ｍａｐ関数を適用することで得られるデータ集合である。ｍａｐ関数は、引数として与えられるデータ要素ａ，ｂによっては、結果のデータ要素を出力しないこともあるし、２以上の結果のデータ要素を出力することもある。
【００４８】
【数１】
0005790526.tif 000002
【００４９】
【数２】
0005790526.tif 000003
【００５０】
図５は、虱潰しジョインを示す図である。図５に示すように、虱潰しジョインは、データ集合Ａとデータ集合Ｂの直積に対してｍａｐ関数を適用する演算と言うこともできる。例えば、データ集合Ａから１つのデータ要素ａ1を選択し、データ集合Ｂから１つのデータ要素ｂ1を選択し、データ要素ａ1，ｂ1をｍａｐ関数の引数として与える。前述のように、ｍａｐ（ａ1，ｂ1）は結果を出力するとは限らない。例えば、データ要素ａ1，ｂ1が所定の条件を満たさないとき、ｍａｐ関数は結果を出力しない可能性がある。このようなｍａｐ関数の演算を、ｍ個×ｎ個の全ての順序対に対して実行する。
【００５１】
虱潰しジョインを実行するプログラムは、ネステッドループと呼ばれるアルゴリズムを用いて実装できる。例えば、外側のループでデータ集合Ａのデータ要素ａを１つ選択し、内側のループでデータ集合Ｂのデータ要素ｂを１つ選択する。この場合、データ集合Ａのあるデータ要素ａiに対して、ｎ個のデータ要素ｂ1，ｂ2，…，ｂnが順に組み合わせられて、内側ループの中で演算が実行される。ただし、図５に示す複数のｍａｐ関数の演算は、互いに独立に実行可能であるため、複数のノードを用いて並列化できる。
【００５２】
図６は、虱潰しジョインの実行結果の例を示す図である。図６の数値例では、データ集合Ａは４個のデータ要素ａ1〜ａ4を含み、データ集合Ｂは４個のデータ要素ｂ1〜ｂ4を含む。この数値例では、データ集合Ａ，Ｂの各データ要素は、人の氏名と年齢を表す。
【００５３】
虱潰しジョインを行うと、４個×４個＝１６個の順序対それぞれにｍａｐ関数が適用される。ただし、この数値例におけるｍａｐ関数には、結果を出力する条件として、データ要素ａの年齢がデータ要素ｂの年齢より大きく、かつ、データ要素ａ，ｂ間の年齢差が５以下であるという条件が定義されている。そのため、図６に示すように、ｍａｐ関数は、４つの順序対（ａ1，ｂ1），（ａ2，ｂ2），（ａ2，ｂ3），（ａ3，ｂ4）に対して結果のデータ要素を出力する一方、他の順序対に対してはデータ要素を出力しない。
【００５４】
ここで、データ集合としては、例えば、関係データベースのテーブル、キーバリューストアの（キー，バリュー）組の集合、ファイル、行列などが挙げられる。データ要素としては、例えば、テーブルに含まれるタプル、キーバリューストアの１つの組、ファイル中の１つのレコード、行列に含まれるベクトルやスカラ値などが挙げられる。
【００５５】
行列をベクトルの集合として扱って、上記の虱潰しジョインを適用する例を説明する。数式（３）に示すように、２つ行列Ａ，Ｂの行列積を計算するとき、行列Ａを行ベクトルの集合と見なし、行列Ｂを列ベクトルの集合と見なすことができる。すると、数式（４）に示すように、行列積ＡＢは、行列Ａの行ベクトルと行列Ｂの列ベクトルとの間の全ての組み合わせに対して、内積を計算した結果と言うことができる。よって、行列積ＡＢは、２つのベクトル集合に対する虱潰しジョインとして計算することが可能である。
【００５６】
【数３】
0005790526.tif 000004
【００５７】
【数４】
0005790526.tif 000005
【００５８】
図７は、第３の実施の形態のノード関係を示す図である。第３の実施の形態の虱潰しジョインでは、データ処理に用いる複数のノードを、論理的に矩形状に並べられたものとして扱う。ノード集合の縦方向にはｈ個のノードが並び（行数）、横方向にはｗ個のノードが並ぶ（列数）。ｉ行目・ｊ列目のノードはｎijと表すことができる。行数ｈと列数ｗは、以下に述べるように、データ処理の開始の際に情報処理システムが決定する。なお、行数ｈを縦の分割数、列数ｗを横の分割数と呼んでもよい。
【００５９】
並列データ処理を開始する際、データ集合Ａ，Ｂは、論理的に矩形状に並べられた複数のノードに分散して配置される。各ノードに配置したデータ要素を格納する記憶装置は、ＲＡＭ１０２のようなメモリでもよいし、ＨＤＤ１０３のようなディスク装置でもよい。ここで、データ集合Ａ，Ｂはそれぞれ、できる限りノード間でデータ量が偏らないように複数のノードに分散される（均等性）。また、データ集合Ａ，Ｂはそれぞれ、同じデータ要素が複数のノードに重複して配置されないように分散される（排反性）。
【００６０】
上記の均等性と排反性が完全に満たされるとすると、数式（５）に示すように、ノードｎijには部分集合Ａij，Ｂijが配置される。部分集合Ａijに含まれるデータ要素数は、データ集合Ａの要素数を全ノード数Ｎ＝ｈ×ｗで割ったものになり、部分集合Ｂijに含まれるデータ要素数は、データ集合Ｂの要素数を全ノード数Ｎで割ったものになる。
【００６１】
【数５】
0005790526.tif 000006
【００６２】
ここで、行部分集合Ａiを、行番号が同じノードｎi1，ｎi2，…，ｎiwに配置された部分集合Ａi1，Ａi2，…，Ａiwの集合和と定義する。また、列部分集合Ｂjを、列番号が同じノードｎ1j，ｎ2j，…，ｎhjに配置された部分集合Ｂ1j，Ｂ2j，…，Ｂhjの集合和と定義する。数式（６）に示すように、データ集合Ａは、ｈ個の行部分集合Ａiの集合和であり、データ集合Ｂは、ｗ個の列部分集合Ｂjの集合和である。
【００６３】
【数６】
0005790526.tif 000007
【００６４】
行部分集合Ａiと列部分集合Ｂjとを用いて表すと、虱潰しジョインは、数式（７）に示すように、ｈ×ｗ個の虱潰しジョインに分割できる。すなわち、ノードｎijに行部分集合Ａiと列部分集合Ｂjを用いた虱潰しジョインを実行させれば、ｈ×ｗ個のノードを並列に動作させて、データ集合Ａ，Ｂに対する虱潰しジョインを実現できる。その場合、ノードｎijは、データ集合Ａ，Ｂのデータ要素が均等性および排他性を満たして配置された状態から、行番号が同じ他のノードに配置されたデータ集合Ａの部分集合と、列番号が同じ他のノードに配置されたデータ集合Ｂの部分集合を受信することになる。
【００６５】
【数７】
0005790526.tif 000008
【００６６】
以上のように、各ノードが自ノードに格納したデータ要素を用いてローカルで虱潰しジョインを実行する前に、ノード間でデータ要素を複製することが発生する。そこで、情報処理システムは、虱潰しジョインに使用可能なノード数Ｎが与えられたとき、ノード間のデータ送信量が最小になるように、行数ｈと列数ｗを決定することにする。
【００６７】
行方向にデータ集合Ａの部分集合がリレーされ、列方向にデータ集合Ｂの部分集合がリレーされるとすると、各ノードのデータ送信量ｃ（＝データ受信量）は、数式（８）のように計算される。ただし、数学的モデルおよびアルゴリズムを簡単にするため、各ノードは、自ノードが送信したデータ要素を自身でも受信すると仮定する。Ｎ個のノードのデータ送信量ｃ（＝データ受信量）を合計した総データ送信量Ｃ（＝総データ受信量）は、数式（９）のように計算される。すなわち、使用可能なノード数Ｎとデータ集合Ａ，Ｂのデータ要素数が与えられたとき、総データ送信量Ｃは、行数ｈの関数となる。
【００６８】
【数８】
0005790526.tif 000009
【００６９】
【数９】
0005790526.tif 000010
【００７０】
図８は、ノード行数とデータ送信量との関係を示すグラフである。図８のグラフは、ノード数を１００００、データ集合Ａのデータ要素数を１００００、データ集合Ｂのデータ要素数を１００００として計算したものである。この例では、ｈ＝１００のとき総データ送信量Ｃが最小となる。総データ送信量Ｃが最小の行数ｈは、数式（９）を微分することで、数式（１０）のように算出される。ただし、実際の行数ｈはノード数Ｎの約数にすることになるため、最終的な行数ｈは以下のように決定する。数式（１０）により算出された値が１以下の場合はｈ＝１とし、算出された値がＮ以上の場合はｈ＝Ｎとし、それ以外の場合はＮの約数のうち算出された値に近いものをｈとする。算出された値に近い約数が２つある（算出された値より大きい約数と小さい約数がある）場合は、総データ送信量Ｃが小さくなる方をｈとする。
【００７１】
全ノード数Ｎは、例えば、使用可能なノード数、処理するデータの量、システムが要求される応答時間などに基づいて予め決定される。ただし、全ノード数Ｎは、上記のｈがＮの約数の中から選ばれることを考慮して、約数を多く含む数（例えば、２のべき乗）であることが望ましく、素数など約数が少ない数を避けることが望ましい。予め決められたＮがこの性質を満たさない場合、Ｎ以下で約数が多い数字にＮを変更するようにしてもよい。例えば、Ｎ以下の範囲で２のべき乗である最大の整数を、新たなＮとする。
【００７２】
【数１０】
0005790526.tif 000011
【００７３】
次に、ノード間でデータ要素をリレーする方法について説明する。以下の説明では、行方向のリレーの例を挙げるが、列方向のリレーについても同様に実現できる。
図９は、ノード間でのデータのリレー方法の例を示す図である。
【００７４】
（Ａ）方法Ａでは、ノードｎ11に配置された部分集合Ａ11をノードｎ12，…，ｎ1wに複製する場合、ノードｎ11は、部分集合Ａ11をノードｎ12に送信する。ノードｎ12は、ノードｎ11から受信した部分集合Ａ11を複製してノードｎ13に送信する。以下、右方向にノードｎ1wまで部分集合Ａ11が転送される。他のノードに配置された部分集合も、右方向にリレーできる。リレー方式によりデータ要素を複製することで、送信元のノードが複製先のノードと個別にコネクションを確立しなくてよく、隣接するノード間でのみコネクションを確立すればよい。このため、通信の負荷を低減できる。ただし、方法Ａでは、左方向のノードにデータ要素を複製するときはリレー方式を用いることができない。
【００７５】
（Ｂ）方法Ｂでは、右端のノードｎ1wから左端のノードｎ11へのコネクションが確立され、巡回したパスが形成される。任意のノードｎijは、自ノードに配置された部分集合Ａijを右隣のノードに送信することで、行番号が同じ他のノードに部分集合Ａijを複製することができる。ただし、データ要素が無限に巡回しないように、例えば、リレーされるデータ要素には、送信元のノードの識別情報（アドレスや座標など）が付加される。
【００７６】
（Ｃ）方法Ｃでは、左端のノードｎ11から右端のノードｎ1wに至る右方向のコネクションと、右端のノードｎ1wから左端のノードｎ11に至る左方向のコネクションとが、ノード間に確立される。例えば、左端のノードｎ11は、部分集合Ａ11を右隣のノードに送信する。右端のノードｎ1wは、部分集合Ａ1wを左隣のノードに送信する。それ以外のノードｎijは、部分集合Ａijを右隣のノードと左隣のノードの両方に送信する。方法Ｃにおいても、方法Ｂと同様に巡回したパスを形成してもよい。
【００７７】
なお、第３の実施の形態の虱潰しジョインでは、リレー方法として方法Ｂまたは方法Ｃを用いることが好ましい。また、あるデータ要素をもつノードと当該データ要素を受け取る複数のノードとが、同一のブロードキャストドメインに属する場合、ブロードキャストによりデータ要素を複製してもよい。ただし、ブロードキャストを採用する場合でも、データ総受信量を考慮すると、最適な行数ｈは数式（１０）と同様に算出できる。また、第１のノードから第２のノードへデータ要素が送信されたとき、その後に第２のノードから第１のノードに送信すべきデータ要素がある場合には、受信に対する応答メッセージ（ＡＣＫ（Acknowledgment）やＮＡＣＫ（Negative Acknowledgment））を独立に送信せず、後で送信されるデータ要素と合わせて送信してもよい。
【００７８】
図１０は、第３の実施の形態のソフトウェア例を示すブロック図である。
ノード１１は、受信部１１１、システム制御部１１２、ノード制御部１１４、実行部１１５およびデータ記憶部１１６を有する。ノード１２〜１６も、ノード１１と同様のブロック構成によって実現できる。例えば、ノード１２は、受信部１２１、ノード制御部１２４、実行部１２５およびデータ記憶部１２６を有する（図１０では、ノード１２のシステム制御部の記載を省略している）。クライアント３１は、要求部３１１を有する。データ記憶部１１６，１２６は、ＲＡＭやＨＤＤに確保された記憶領域として実現でき、他のブロックは、プログラムのモジュールとして実現できる。
【００７９】
要求部３１１は、ユーザ操作に応じて、データ処理開始のコマンドを送信する。コマンドは、ノード１１〜１６の何れに対して送信してもよい。以下の説明では、要求部３１１がノード１１にデータ処理開始のコマンドを送信した場合を考える。
【００８０】
受信部１１１は、クライアント３１や他のノードからコマンドを受信する。受信部１１１に対応するプロセスは、ノード１１で常時起動している。受信部１１１は、クライアント３１からコマンドを受信すると、システム制御部１１２を呼び出す。また、受信部１１１は、システム制御部１１２からコマンドを受信すると、ノード制御部１１４を呼び出す。ただし、ノード１１ではなく他のノードでシステム制御部が起動した場合、受信部１１１は、他のノードのシステム制御部からコマンドを受信し、ノード制御部１１４を呼び出す。なお、ノード１１は、各ノードの受信部に対応するプロセスのアドレス（例えば、ＩＰ（Internet Protocol）アドレス）を知っている。
【００８１】
システム制御部１１２は、虱潰しジョインのトランザクション全体を統括する。システム制御部１１２に対応するプロセスは、受信部１１１から呼び出されることで起動する。クライアント３１から要求されたデータ処理毎（トランザクション毎）に、データ処理に用いる複数のノードのうち１つのノードのみで、システム制御部が起動する。システム制御部１１２は、自身が起動すると、虱潰しジョインに用いるノードの受信部（例えば、受信部１１１，１２１）に、参加要求のコマンドを送信する。これにより、ノード１１ではノード制御部１１４が呼び出され、ノード１２ではノード制御部１２４が呼び出される。
【００８２】
また、システム制御部１１２は、ノード間の論理的な接続関係を決定し、データ要素をリレーする始点となるノードのノード制御部（例えば、ノード制御部１１４など）に、リレー指示のコマンドを送信する。リレー指示のコマンドには、リレーに用いるノードに関する情報が含まれる。また、システム制御部１１２は、データ要素の複製が完了した後に、虱潰しジョインに用いる全てのノードのノード制御部（例えば、ノード制御部１１４，１２４など）に、ジョイン指示のコマンドを送信する。また、虱潰しジョインが完了すると、システム制御部１１２は、クライアント３１に完了を報告する。
【００８３】
ノード制御部１１４は、虱潰しジョインで行われる情報処理のうちノード１１で行われる情報処理を統括する。ノード制御部１１４に対応するプロセスは、受信部１１１から呼び出されることで起動する。ノード制御部１１４は、システム制御部１１２から、リレー指示のコマンドを受信したときおよびジョイン指示のコマンドを受信したとき、実行部１１５を呼び出す。ただし、ノード１１ではなく他のノードでシステム制御部が起動した場合、ノード制御部１１４は、他のノードのシステム制御部からリレー指示およびジョイン指示のコマンドを受信し、実行部１１５を呼び出す。また、ノード制御部１１４は、他のノードの実行部から受信指示のコマンドを受信したとき、実行部１１５を呼び出す。
【００８４】
実行部１１５は、ノード制御部１１４から要求された情報処理を実行する。実行部１１５に対応するプロセスは、ノード制御部１１４から呼び出されることで起動する。ノード１１では、実行部１１５に対応するプロセスを複数起動することができる。これにより、データ集合Ａのリレーとデータ集合Ｂのリレーを並列に実行するなど、複数の情報処理を並列に実行することができる。これは、ノード１１が複数のプロセッサを備える場合や、複数コアを含むプロセッサを備える場合に、特に有効である。
【００８５】
実行部１１５は、リレー指示のコマンドに応じて呼び出されたとき、隣接するノードのノード制御部（例えば、ノード制御部１２４）に、受信指示のコマンドを送信する。これにより、隣接するノードでは、データ要素を受信するために実行部（例えば、実行部１２５）が呼び出される。そして、実行部１１５は、ノード１１に配置されたデータ要素をデータ記憶部１１６から読み出し、隣接するノードの実行部へ送信する。
【００８６】
また、実行部１１５は、受信指示のコマンドに応じて呼び出されたとき、他のノードの実行部からデータ要素を受信し、データ記憶部１１６に書き込む。そして、ノード１１がリレーの終点ではない場合、実行部１１５は、リレー指示のコマンドに応じて呼び出されたときと同様にして、受信したデータ要素を転送する。また、実行部１１５は、ジョイン指示のコマンドに応じて呼び出されたとき、データ記憶部１１６に記憶されたデータ要素の範囲内でローカルに虱潰しジョインを行い、結果をデータ記憶部１１６に書き込む。
【００８７】
データ記憶部１１６は、データ集合Ａ，Ｂの一部のデータ要素を記憶する。データ記憶部１１６には、まずノード１１に配置される部分集合Ａ11，Ｂ11に属するデータ要素が記憶される。そして、データ要素のリレーを通じて、データ記憶部１１６には、行部分集合Ａ1および列部分集合Ｂ1に属するデータ要素が記憶される。ノード１２のデータ記憶部１２６も、同様に、データ集合Ａ，Ｂの一部のデータ要素を記憶する。
【００８８】
なお、第１のモジュールが第２のモジュールにコマンドを送信し、第２のモジュールでコマンドに応じた情報処理が完了すると、第２のモジュールは第１のモジュールに完了通知を送信する。例えば、実行部１１５でローカルな虱潰しジョインが完了すると、実行部１１５はノード制御部１１４に完了通知を送信し、ノード制御部１１４はシステム制御部１１２に完了通知を送信する。システム制御部１１２は、虱潰しジョインに用いる全てのノードから完了通知を受信したとき、クライアント３１に完了を報告する。
【００８９】
ここで、システム制御部１１２、ノード制御部１１４および実行部１１５は、例えば、コマンド解析部と最適化部とコード実行部の３階層の内部構造として実装できる。コマンド解析部は、受信したコマンドの文字列を解析し、解析結果を解析木として出力する。最適化部は、コマンド解析部が出力した解析木に基づいて、コマンドで要求されている情報処理を実現するのに最適な中間コードを生成（または選択）する。コード実行部は、最適化部が生成した中間コードを実行する。
【００９０】
図１１は、第３の実施の形態のジョインの手順例を示すフローチャートである。なお、前述のように、システム全体のノード数に基づいて、データ処理に使用するノードの数Ｎを、ステップＳ１１の処理の前にシステム制御部１１２が決定してもよい。
【００９１】
（ステップＳ１１）システム制御部１１２は、クライアント３１から入力されたデータ集合Ａ，Ｂを、それぞれＮ個の部分集合Ａij，Ｂijに分割し、虱潰しジョインに用いるノード１１〜１６に配置する。ただし、データ集合Ａ，Ｂの配置は、ノード１１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従い、ノード１１〜１６が行っておいてもよい。また、データ集合Ａ，Ｂとして前のデータ処理の結果を利用する場合であって、当該データ処理の結果が既にノード１１〜１６に配置されている場合には、データ集合Ａ，Ｂの配置が完了しているものと取り扱ってもよい。
【００９２】
（ステップＳ１２）システム制御部１１２は、虱潰しジョインに用いるノードの数Ｎと入力されたデータ集合Ａ，Ｂそれぞれのデータ要素数とに基づいて、前述の数式（１０）のような計算方法を用いて、行数ｈおよび列数ｗを決定する。
【００９３】
（ステップＳ１３）システム制御部１１２は、ノード１１〜１６に、各ノードに配置された部分集合Ａijを行方向に複製し、部分集合Ｂijを列方向に複製するよう指示する。各ノードの実行部は、部分集合Ａijを行方向にリレーし、部分集合Ｂijを列方向にリレーする。リレー方法として、例えば、図９に示した方法Ｂまたは方法Ｃを用いる。この複製により、ノードｎijは、行部分集合Ａiと列部分集合Ｂjとを取得する。
【００９４】
（ステップＳ１４）システム制御部１１２は、虱潰しジョインに用いるノード１１〜１６全てに、ローカルな虱潰しジョインの実行を指示する。各ノードの実行部は、ステップＳ１３を通じて収集した行部分集合Ａiと列部分集合Ｂjとの間でローカルに（他のノードと通信せずに）虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。ローカルな虱潰しジョインは、例えば、ネステッドループとして実現できる。
【００９５】
（ステップＳ１５）システム制御部１１２は、虱潰しジョインに用いるノード１１〜１６全てでステップＳ１４のデータ処理が完了したことを確認すると、クライアント３１に虱潰しジョインの完了を報告する。このとき、システム制御部１１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。後者の場合、当該結果を次のデータ処理の入力として用いる場合に、データ配置処理を省略できることがある。
【００９６】
図１２は、第３の実施の形態のデータ配置例を示す図（その１）である。この例では、６個のノードｎ11，ｎ12，ｎ13，ｎ21，ｎ22，ｎ23（ノード１１〜１６）を、虱潰しジョインに用いる。また、データ集合Ａに６個のデータ要素ａ1〜ａ6が含まれ、データ集合Ｂに１２個のデータ要素ｂ1〜ｂ12が含まれる。各ノードｎijには、均等に、１個のデータ要素を含む部分集合Ａijと２個のデータ要素を含む部分集合Ｂijが配置される。例えば、ノードｎ11には、部分集合Ａ11＝｛ａ1｝と部分集合Ｂ11＝｛ｂ1，ｂ2｝が配置される。ノード数Ｎ＝６，データ集合Ａのデータ要素数＝６，データ集合Ｂのデータ要素数＝１２であるため、前述の数式（１０）に従い、行数ｈ＝２と算出される。
【００９７】
行数ｈおよび列数ｗが決定されると、行番号が同じノード間で（行方向に）部分集合Ａijが複製され、列番号が同じノード間で（列方向に）部分集合Ｂijが複製される。例えば、ノードｎ11に配置された部分集合Ａ11が、ノードｎ11からノードｎ12に複製され、ノードｎ12からノードｎ13に複製される。また、ノードｎ11に配置された部分集合Ｂ11が、ノードｎ11からノードｎ21に複製される。
【００９８】
図１３は、第３の実施の形態のデータ配置例を示す図（その２）である。上記のデータ要素の複製によって、ノードｎijは、行部分集合Ａiと列部分集合Ｂjを取得する。例えば、ノードｎ11，ｎ12，ｎ13は、行部分集合Ａ1＝｛ａ1，ａ2，ａ3｝を取得し、ノードｎ11，ｎ21は、列部分集合Ｂ1＝｛ｂ1，ｂ2，ｂ3，ｂ4｝を取得する。
【００９９】
図１４は、第３の実施の形態のデータ配置例を示す図（その３）である。ノードｎijは、上記のように取得した行部分集合Ａiと列部分集合Ｂjの間で、ローカルに虱潰しジョインを行う。例えば、ノードｎ11は、行部分集合Ａ1＝｛ａ1，ａ2，ａ3｝からデータ要素ａを１つ選択し、列部分集合Ｂ1＝｛ｂ1，ｂ2，ｂ3，ｂ4｝からデータ要素ｂを１つ選択することで、３個×４個＝１２通りの順序対に対してｍａｐ関数を適用する。図１４に示すように、ノードｎ11，ｎ12，ｎ13，ｎ21，ｎ22，ｎ23は、それぞれ均等に１２通りの順序対を処理している。また、データ集合Ａ，Ｂの間の６個×１２個＝７２通りの順序対が網羅されており、かつ、ノード間で重複して処理される順序対がない。
【０１００】
第３の実施の形態の情報処理システムによれば、データ集合Ａ，Ｂの間の虱潰しジョインを、複数のノードを用いて効率的に実行できる。特に、データ集合Ａ，Ｂそれぞれを、虱潰しジョインに用いる複数のノードに、均等（または、ほぼ均等）かつ重複なく分散した状態から、虱潰しジョインを実行できる。また、各ノードのデータ処理量が均等（または、ほぼ均等）になり、かつ、ノード間で重複するデータ処理が発生しない。このため、第３の実施の形態の虱潰しジョインは、通信のオーバヘッドを除いて、スケーラブルである（ノード数をＮ倍にすると処理時間が１／Ｎになる）と言える。
【０１０１】
［第４の実施の形態］
次に、第４の実施の形態を説明する。第３の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第４の実施の形態では、複数の通信装置が階層的に接続されている大規模な情報処理システムを用いて、虱潰しジョインを実行する。
【０１０２】
図１５は、第４の実施の形態の情報処理システムを示す図である。第４の実施の形態の情報処理システムは、仮想ノード２０，２０ａ，２０ｂ，２０ｃ，２０ｄ，２０ｅ、クライアント３１およびネットワーク４１を有する。
【０１０３】
仮想ノード２０，２０ａ，２０ｂ，２０ｃ，２０ｄ，２０ｅは、少なくとも１つのスイッチ（例えば、レイヤ２スイッチ）と当該スイッチに接続された複数のノードとを含む。例えば、仮想ノード２０は、ノード２１〜２４およびスイッチ２５を有する。仮想ノード２０ａは、ノード２１ａ〜２４ａおよびスイッチ２５ａを有する。各仮想ノードは、虱潰しジョインにおいて、仮想的に１つのノードとして取り扱われることがある。
【０１０４】
各仮想ノードは、同数のノードを含む。各仮想ノードのノード数は、通信装置との接続関係などを考慮して、予め定められている。ただし、各仮想ノード内でデータ処理に使用するノードの数は、第３の実施の形態で述べたように、予め定められたノード数以下の範囲で約数が最も多くなる数字に設定してもよい。仮想ノード間には、１対１のノードの対応関係が与えられている。例えば、ノード２１とノード２１ａとが対応し、ノード２２とノード２２ａとが対応し、ノード２３とノード２３ａとが対応し、ノード２４とノード２４ａとが対応する。なお、図１５には、１階層の仮想化の例を示したが、仮想ノードが別の仮想ノードを含むように、多階層の仮想化を行うことも可能である。
【０１０５】
図１６は、第４の実施の形態のノード関係を示す図である。第４の実施の形態の虱潰しジョインでは、複数の仮想ノードを、論理的に矩形状に並べられたものとして扱う。縦方向にはＨ個の仮想ノードが並び、横方向にはＷ個の仮想ノードが並ぶ。行数Ｈおよび列数Ｗは、前述の方法と同様に、仮想ノード数とデータ集合Ａ，Ｂそれぞれのデータ要素数とから決定できる。また、各仮想ノード内では、複数のノードを、論理的に矩形状に並べられたものとして扱う。縦方向にｈ個のノードが並び、横方向にｗ個のノードが並ぶ。行数ｈおよび列数ｗは、全ての仮想ノードに共通に決定され、仮想ノード１つ当たりのノード数とデータ集合Ａ，Ｂそれぞれのデータ要素数とから決定できる。
【０１０６】
ｉ行目・ｊ列目の仮想ノードはijｎと表すことができる。仮想ノードijｎ内におけるｉ行目・ｊ列目のノードはijｎijと表すことができる。虱潰しジョインを開始する際、データ集合Ａ，Ｂは、データ処理に用いる全ての仮想ノード11ｎ，…，HWｎに含まれる全てのノードｎ11，…，ｎhwに、均等（または、ほぼ均等）かつ重複なく分散される。
【０１０７】
ノード間でのデータ要素の複製は、後述するように、まず異なる２以上のスイッチを介して仮想ノード間で行われ、その後、各仮想ノード内で閉じて行われる。仮想ノード間でのデータ要素の複製と、各仮想ノード内でのデータ要素の複製とは、再帰的関係にある。すなわち、行番号が同じ仮想ノード間でデータ集合Ａの部分集合を複製し、列番号が同じ仮想ノード間でデータ集合Ｂの部分集合を複製する。その後、各仮想ノード内において、行番号が同じノード間でデータ集合Ａの部分集合を複製し、列番号が同じノード間でデータ集合Ｂの部分集合を複製する。仮想ノード間の通信は、「対応するノード」同士の通信として実現する。例えば、仮想ノード11ｎから仮想ノード12ｎにデータ要素を複製する場合、ノード11ｎ11からノード12ｎ11にデータ要素を送信し、ノード11ｎ12からノード12ｎ12にデータ要素を送信する。対応しないノード間では、通信は行われない。
【０１０８】
図１７は、第４の実施の形態のソフトウェア例を示すブロック図である。
ノード２１は、受信部２１１、システム制御部２１２、仮想ノード制御部２１３、ノード制御部２１４、実行部２１５およびデータ記憶部２１６を有する。ノード２２〜２４やノード２１ａ〜２４ａを含む他のノードも、ノード２１と同様のブロック構成によって実現できる。例えば、ノード２２は、受信部２２１、ノード制御部２２４、実行部２２５およびデータ記憶部２２６を有する（図１７では、ノード２２のシステム制御部や仮想ノード制御部の記載を省略している）。ノード２１ａは、受信部２１１ａおよび仮想ノード制御部２１３ａを有する（図１７では、ノード２１ａのシステム制御部やノード制御部、実行部、データ記憶部の記載を省略している）。ノード２２ａは、受信部２２１ａを有する（図１７では、ノード２２ａのシステム制御部や仮想ノード制御部、ノード制御部、実行部、データ記憶部の記載を省略している）。第３の実施の形態と同様、データ記憶部２１６，２２６は、ＲＡＭやＨＤＤに確保された記憶領域として実現でき、他のブロックは、プログラムのモジュールとして実現できる。
【０１０９】
以下の説明では、ノード２１が、クライアント３１から要求されたデータ処理を統括する場合を考える。また、ノード２１が、ノード２１の属する仮想ノード２０を統括し、ノード２１ａが、ノード２１ａの属する仮想ノード２０ａを統括する場合を考える。
【０１１０】
受信部２１１は、クライアント３１や他のノードからコマンドを受信する。受信部２１１に対応するプロセスは、ノード２１で常時起動している。受信部２１１は、クライアント３１からコマンドを受信すると、システム制御部２１２を呼び出す。また、受信部２１１は、システム制御部２１２からコマンドを受信すると、仮想ノード制御部２１３を呼び出し、仮想ノード制御部２１３からコマンドを受信すると、ノード制御部２１４を呼び出す。ただし、ノード２１ではなく他のノードでシステム制御部が起動した場合、受信部２１１は、他のノードのシステム制御部からコマンドを受信したとき、仮想ノード制御部２１３を呼び出す。また、他のノードで仮想ノード制御部が起動した場合、受信部２１１は、他のノードの仮想ノード制御部からコマンドを受信しノード制御部２１４を呼び出す。
【０１１１】
システム制御部２１２は、虱潰しジョインに用いる複数の仮想ノード全体を統括する。クライアント３１から要求されたデータ処理毎（トランザクション毎）に、データ処理に用いる複数のノードのうち１つのノードのみで、システム制御部が起動する。システム制御部２１２は、自身が起動すると、各仮想ノードの所定のノード（代表ノード）に、当該仮想ノードの制御を担当するノード（代理ノード）を問い合わせる。代理ノードは、ノード間で負荷が分散されるように、虱潰しジョインのトランザクション毎に選択される。そして、システム制御部２１２は、各仮想ノードの代理ノードの受信部に、代理指示のコマンドを送信する。これにより、例えば、ノード２１では仮想ノード制御部２１３が呼び出され、ノード２１ａでは仮想ノード制御部２１３ａが呼び出される。
【０１１２】
また、システム制御部２１２は、代理指示のコマンドを送信した後、各仮想ノードの仮想ノード制御部（例えば、仮想ノード制御部２１３，２１３ａなど）に、参加要求のコマンドを送信する。また、システム制御部２１２は、仮想ノード間およびノード間の論理的な接続関係を決定し、各仮想ノードの仮想ノード制御部に、リレー指示のコマンドを送信する。また、システム制御部２１２は、データ要素の複製が完了した後、各仮想ノードの仮想ノード制御部に、ジョイン指示のコマンドを送信する。また、虱潰しジョインが完了すると、システム制御部２１２は、クライアント３１に完了を報告する。
【０１１３】
仮想ノード制御部２１３は、仮想ノード２０に属する複数のノード２１〜２４を統括する。仮想ノード制御部２１３に対応するプロセスは、受信部２１１から呼び出されることで起動する。クライアント３１から要求されたデータ処理毎（トランザクション毎）かつ仮想ノード毎に、当該仮想ノードに属する複数のノードのうち１つのノードのみで、仮想ノード制御部が起動する。仮想ノード制御部２１３は、自身が起動すると、システム制御部２１２から参加要求のコマンドを受信したとき、仮想ノード２０内のデータ処理に用いるノードの受信部（例えば、受信部２１１，２２１など）に、参加要求のコマンドを送信する。これにより、ノード２１ではノード制御部２１４が呼び出され、ノード２２ではノード制御部２２４が呼び出される。
【０１１４】
また、仮想ノード制御部２１３は、システム制御部２１２からリレー指示のコマンドを受信すると、データ要素をリレーする始点となるノードのノード制御部（例えば、ノード制御部２１４など）に、リレー指示のコマンドを送信する。また、仮想ノード制御部２１３は、システム制御部２１２からジョイン指示のコマンドを受信すると、仮想ノード２０内のデータ処理に用いる全てのノードのノード制御部（例えば、ノード制御部２１４，２２４など）に、ジョイン指示のコマンドを送信する。
【０１１５】
ノード制御部２１４は、虱潰しジョインで行われる情報処理のうちノード２１で行われる情報処理を統括する。ノード制御部２１４に対応するプロセスは、受信部２１１から呼び出されることで起動する。ノード制御部２１４は、仮想ノード制御部２１３からリレー指示のコマンドを受信したときおよびジョイン指示のコマンドを受信したとき、実行部２１５を呼び出す。ただし、ノード２１ではなく他のノードで仮想ノード制御部が起動した場合、ノード制御部２１４は、他のノードの仮想ノード制御部からリレー指示およびジョイン指示のコマンドを受信し、実行部２１５を呼び出す。また、ノード制御部２１４は、他のノードの実行部から受信指示のコマンドを受信したとき、実行部２１５を呼び出す。
【０１１６】
実行部２１５は、ノード制御部２１４から要求された情報処理を実行する。実行部２１５に対応するプロセスは、ノード制御部２１４から呼び出されることで起動する。ノード２１では、実行部２１５に対応するプロセスを複数起動できる。実行部２１５は、リレー指示のコマンドに応じて呼び出されたとき、他のノードのノード制御部（例えば、ノード制御部２２４）に受信指示のコマンドを送信し、データ記憶部２１６からデータ要素を読み出して他のノードの実行部（例えば、実行部２２５）へ送信する。
【０１１７】
また、実行部２１５は、受信指示のコマンドに応じて呼び出されたとき、他のノードの実行部からデータ要素を受信し、データ記憶部２１６に書き込む。ノード２１がリレーの終点でない場合、実行部２１５は、受信したデータ要素を転送する。また、実行部２１５は、ジョイン指示のコマンドに応じて呼び出されたとき、収集されたデータ要素の範囲内でローカルに虱潰しジョインを行い、結果をデータ記憶部２１６に書き込む。
【０１１８】
データ記憶部２１６は、データ集合Ａ，Ｂの一部のデータ要素を記憶する。データ記憶部２１６には、まずノード２１に配置される部分集合に属するデータ要素が記憶される。そして、仮想ノード間および仮想ノード２０内でのデータ要素のリレーを通じて、データ記憶部２１６には、行部分集合および列部分集合に属するデータ要素が収集される。ノード２２のデータ記憶部２２６も、データ集合Ａ，Ｂの一部のデータ要素を記憶する。
【０１１９】
図１８は、第４の実施の形態のジョインの手順例を示すフローチャートである。なお、前述のように、システム全体のノード数や各仮想ノードのノード数に基づいて、データ処理に使用するノード数や各仮想ノード内で使用するノード数を、ステップＳ２１の前にシステム制御部２１２が決定してもよい。
【０１２０】
（ステップＳ２１）システム制御部２１２は、クライアント３１から入力されたデータ集合Ａ，Ｂをそれぞれ、虱潰しジョインに用いる仮想ノードの数分の部分集合に分割し仮想ノードに分配する。各仮想ノードの仮想ノード制御部は、分配された部分集合を、当該仮想ノード内の虱潰しジョインに用いるノード数分の部分集合に更に分割しノードに分配する。これにより、データ集合Ａ，Ｂが複数のノードに分散される。ただし、データ集合Ａ，Ｂの配置は、ノード２１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａ，Ｂとして前のデータ処理の結果を利用する場合には、データ集合Ａ，Ｂの配置が完了していることもある。
【０１２１】
（ステップＳ２２）システム制御部２１２は、虱潰しジョインに用いる仮想ノードの数とデータ集合Ａ，Ｂそれぞれのデータ要素数に基づいて、前述の数式（１０）のような計算方法を用いて、仮想ノードの行数Ｈおよび列数Ｗを決定する。
【０１２２】
（ステップＳ２３）システム制御部２１２は、各仮想ノードの代理ノードに、仮想ノード間でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、他の仮想ノードとの間でデータ要素を複製するよう指示する。各ノードの実行部は、データ集合Ａの部分集合を、行番号が同じ他の仮想ノードにある自ノードに対応するノードと通信することで、行方向にリレーする。また、各ノードの実行部は、データ集合Ｂの部分集合を、列番号が同じ他の仮想ノードにある自ノードに対応するノードと通信することで、列方向にリレーする。
【０１２３】
なお、仮想ノードが入れ子になっており多階層に仮想化されている場合は、ステップＳ２２，Ｓ２３の処理が再帰的に実行される。その場合、再帰処理に関しては、システム制御部２１２が行った上記処理を仮想ノード制御部が引き継ぐことで実現できる。ステップ２１の処理についても同様である。
【０１２４】
（ステップＳ２４）システム制御部２１２は、仮想ノード１つ当たりのノード数とその時点の仮想ノード１つ当たりのデータ集合Ａ，Ｂのデータ要素数に基づいて、前述の数式（１０）のような計算方法を用いて、ノードの行数ｈおよび列数ｗを決定する。
【０１２５】
（ステップＳ２５）システム制御部２１２は、各仮想ノードの代理ノードに、仮想ノード内でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、現在まで収集したデータ要素を仮想ノード内で複製するよう指示する。各ノードの実行部は、自ノードに配置されたデータ集合Ａの部分集合とステップＳ２３で他の仮想ノードから受信したデータ集合Ａの部分集合を、行方向に送信する。また、各ノードの実行部は、自ノードに配置されたデータ集合Ｂの部分集合とステップＳ２３で他の仮想ノードから受信したデータ集合Ｂの部分集合を、列方向に送信する。
【０１２６】
（ステップＳ２６）システム制御部２１２は、各仮想ノードの代理ノードに、ローカルな虱潰しジョインの実行を指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、ローカルな虱潰しジョインの実行を指示する。各ノードの実行部は、ステップＳ２３，Ｓ２５を通じて収集した行部分集合と列部分集合との間でローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０１２７】
（ステップＳ２７）システム制御部２１２は、虱潰しジョインに用いる全てのノードでステップＳ２６のデータ処理が完了したことを確認すると、クライアント３１に虱潰しジョインの完了を報告する。このとき、システム制御部２１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０１２８】
図１９は、第４の実施の形態のデータ配置例を示す図（その１）である。この例では、６個の仮想ノード11ｎ，12ｎ，13ｎ，21ｎ，22ｎ，23ｎ（仮想ノード２０，２０ａ，２０ｂ，２０ｃ，２０ｄ，２０ｅ）を、虱潰しジョインに用いる。データ集合Ａには、２４個のデータ要素ａ1〜ａ24が含まれ、データ集合Ｂには４８個のデータ要素ｂ1〜ｂ48が含まれる。仮想ノード数＝６，データ集合Ａのデータ要素数＝２４，データ集合Ｂのデータ要素数＝４８であるため、前述の数式（１０）に従い、仮想ノードの行数Ｈ＝２と算出される。各仮想ノードを仮想的に１つのノードと見ると、仮想ノードijｎには、部分集合Ａijと部分集合Ｂijが配置されていると言える。例えば、仮想ノード11ｎには、部分集合Ａ11と部分集合Ｂ11が配置されている。
【０１２９】
図２０は、第４の実施の形態のデータ配置例を示す図（その２）である。この例では、仮想ノード11ｎ，12ｎ，13ｎ，21ｎ，22ｎ，23ｎは、それぞれ４つのノードｎ11，ｎ12，ｎ21，ｎ22を含む。各ノードには、均等に、データ集合Ａに属する１個のデータ要素とデータ集合Ｂに属する２個のデータ要素が、部分集合として配置されることになる。例えば、ノード11ｎ11には、データ要素ａ1とデータ要素ｂ1，ｂ2が配置される。
【０１３０】
データ要素が配置されて仮想ノードの行数Ｈおよび列数Ｗが決定されると、行番号が同じ仮想ノード間で（行方向に）データ集合Ａの部分集合が複製され、列番号が同じ仮想ノード間で（列方向に）データ集合Ｂの部分集合が複製される。このとき、仮想ノード間のデータ要素の複製は、対応するノード同士のみが行う。例えば、ノード11ｎ11に配置されたデータ要素ａ1が、ノード11ｎ11からノード12ｎ11に複製され、ノード12ｎ11からノード13ｎ11に複製される。また、ノード11ｎ11に配置されたデータ要素ｂ1，ｂ2が、ノード11ｎ11からノード21ｎ11に複製される。この時点では、対応関係にないノード間ではデータ要素は複製されない。例えば、ノード11ｎ11に配置されたデータ要素ａ1は、この時点ではノード12ｎ12やノード13ｎ12には複製されない。
【０１３１】
図２１は、第４の実施の形態のデータ配置例を示す図（その３）である。この例では、ノード間の複製が完了した時点で、各ノードには、データ集合Ａに属する３個のデータ要素とデータ集合Ｂに属する４個のデータ要素が収集されている。例えば、ノード11ｎ11には、データ要素ａ1，ａ3，ａ5とデータ要素ｂ1，ｂ2，ｂ5，ｂ6が収集される。仮想ノード１個あたり、ノード数＝４，データ集合Ａのデータ要素数＝１２，データ集合Ｂのデータ要素数＝１６であるため、前述の数式（１０）に従い、行数ｈ＝２と算出される。
【０１３２】
仮想ノード内の行数ｈと列数ｗが決定されると、各仮想ノード内でデータ要素が複製される。すなわち、行番号が同じノード間で（行方向に）、他の仮想ノードから受信したデータ要素も含めて、データ集合Ａの部分集合が複製される。また、列番号が同じノード間で（列方向に）、他の仮想ノードから受信したデータ要素も含めて、データ集合Ｂの部分集合が複製される。例えば、ノード11ｎ11に収集されたデータ要素ａ1，ａ3，ａ5が、ノード11ｎ11からノード11ｎ12に複製される。また、ノード11ｎ11に収集されたデータ要素ｂ1，ｂ2，ｂ5，ｂ6が、ノード11ｎ11からノード11ｎ21に複製される。仮想ノード内での複製処理では、複数の仮想ノードに跨がる通信は行わなくてよい。
【０１３３】
図２２は、第４の実施の形態のデータ配置例を示す図（その４）である。上記のデータ要素の複製を通じて、各ノードは、データ集合Ａに関する行部分集合と、データ集合Ｂに関する列部分集合を取得する。例えば、ノード11ｎ11，11ｎ12，12ｎ11，12ｎ12，13ｎ11，13ｎ12は、行部分集合としてデータ要素ａ1〜ａ6を取得する。また、ノード11ｎ11，11ｎ21，21ｎ11，21ｎ21は、列部分集合としてデータ要素ｂ1〜ｂ8を取得する。これは、２４個のノードを複数の仮想ノードに分類しない場合と同じ結果となっている。
【０１３４】
各ノードは、自ノードが取得した行部分集合と列部分集合の間で、ローカルに虱潰しジョインを行う。例えば、ノード11ｎ11は、６個のデータ要素ａ1〜ａ6から１つ選択し、８個のデータ要素ｂ1〜ｂ8から１つ選択することで、６個×８個＝４８通りの順序対に対してｍａｐ関数を適用する。図２２に示すように、各ノードは、均等に４８通りの順序対を処理している。また、データ集合Ａ，Ｂの間の２４個×４８個＝１１５２通りの順序対が網羅されており、かつ、ノード間で重複して処理される順序対がない。
【０１３５】
第４の実施の形態の情報処理システムによれば、第３の実施の形態と同様の効果が得られる。更に、第４の実施の形態では、通信遅延の比較的大きい仮想ノード間の通信を纏めて行い、その後、通信遅延の比較的小さい仮想ノード内の通信のみを行うため、ノード間の物理的な通信距離を考慮しない場合と比べて、意図しない待ち時間を抑制し得る。そのため、通信の並列化が容易となり、データ要素の複製を一層効率化できる。
【０１３６】
［第５の実施の形態］
次に、第５の実施の形態を説明する。第３および第４の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第５の実施の形態では、虱潰しジョインに代えて、以下に説明する「三角ジョイン」を実行する。第５の実施の形態の情報処理システムは、図３，４，１０に示した第３の実施の形態と同様のシステム構成で実現できる。なお、三角ジョインは、単にジョインの一種として扱われることがある。
【０１３７】
三角ジョインでは、ｍ個（ｍは２以上の整数）のデータ要素ａ1，ａ2，…，ａmを含む１つのデータ集合Ａが与えられる。三角ジョインの結果は、数式（１１）に示すように、データ集合Ａに含まれる２つのデータ要素ａi，ａjの順序を考慮しない組み合わせ全てに対して、ｍａｐ関数を適用することで得られるデータ集合である。ｍａｐ関数は、虱潰しジョインと同様、引数として与えられるデータ要素ａi，ａjによっては、結果のデータ要素を出力しないこともあるし、２以上の結果のデータ要素を出力することもある。なお、数式（１１）の定義では、同じデータ要素同士の組み合わせ（ａi＝ａjの場合）にもｍａｐ関数が適用されるが、このような組み合わせを除外することも可能である。
【０１３８】
【数１１】
0005790526.tif 000012
【０１３９】
図２３は、三角ジョインを示す図である。三角ジョインは、順序を考慮しない２つのデータ要素の組み合わせ毎にｍａｐ関数を適用するものであるため、ｍａｐ（ａi，ａj）を計算すればｍａｐ（ａj，ａi）は計算しなくてよい。よって、縦軸と横軸にそれぞれデータ集合Ａのデータ要素を並べてマトリクスを形成すると、図２３に示すように、ｍａｐ関数の演算を行うべき領域が直角三角形として表現される。すなわち、ｍａｐ関数の演算は、ｍ（ｍ＋１）／２個またはｍ（ｍ−１）／２個の組み合わせに対して実行される。三角ジョインの代用としてデータ集合Ａとデータ集合Ａの間で虱潰しジョインを行う場合と比べて、データ処理量を約半分に低減することが可能となる。
【０１４０】
ローカルで（１つのノードに閉じて）実行される三角ジョインは、例えば、以下のような手順として実装できる。ブロック（１またはそれ以上のデータ要素を含む読み出しの単位）をＲＡＭ上にα個格納できるとき、ノードは、先頭からα−１個のブロックをＲＡＭに読み込む。例えば、ノードは、データ要素ａ1，ａ2をＲＡＭに読み込む。次に、ノードは、ＲＡＭ上のα−１個のブロック内で三角ジョインを実行する。例えば、ノードは、組み合わせ（ａ1，ａ1），（ａ1，ａ2），（ａ2，ａ2）にｍａｐ関数を適用する。
【０１４１】
次に、ノードは、ＲＡＭ上にあるブロックに続く１個のブロックをＲＡＭに読み込み、先に読み込んだα−１個のブロックと１個のブロックとの間で、虱潰しジョインを実行する。例えば、ノードは、データ要素ａ3をＲＡＭに読み込み、組み合わせ（ａ1，ａ3），（ａ2，ａ3）にｍａｐ関数を適用する。その後、ノードは、先頭のα−１ブロックをＲＡＭ上に保持したまま、最後のブロックに至るまで１ブロックずつ処理する。先頭のα−１ブロックと最後の１ブロックとの間の虱潰しジョインが終わると、ノードは、ＲＡＭ上にある先頭のα−１個のブロックをクリアし、それに続く新たなα−１のブロックをＲＡＭに読み込む。例えば、ノードは、データ要素ａ3，ａ4をＲＡＭに読み込む。その後、新たなα−１個のブロックを基準に、三角ジョインおよび虱潰しジョインを行う。以下、同様に、α−１個のブロックとして全てのブロックが読み込まれるまで、当該処理を繰り返す。なお、総ブロック数によっては、繰り返しの最後で、残りのブロックとしてα−１個以下のブロックを読み込むことになる場合がある。
【０１４２】
ただし、図２３に示す複数のｍａｐ関数の演算は、虱潰しジョインと同様、互いに独立に実行可能であるため、複数のノードを用いて並列化できる。
図２４は、三角ジョインの実行結果の例を示す図である。図２４の数値例では、データ集合Ａは４個のデータ要素ａ1〜ａ4を含む。各データ要素は、Ｘ軸の値とＹ軸の値とを含んでおり、平面上の点を表している。ｍａｐ関数は、２個のデータ要素から、２点間の距離を計算する。三角ジョインを行うと、４×（４＋１）／２＝１０個の組み合わせに対し、ｍａｐ関数が適用される。ただし、同じデータ要素同士の組み合わせを除外する場合には、４×（４−１）／２＝６個の組み合わせに対し、ｍａｐ関数が適用される。
【０１４３】
図２５は、第５の実施の形態のノード関係を示す図である。第５の実施の形態の三角ジョインでは、データ処理に用いる複数のノードを、論理的に直角二等辺三角形状に並べられたものとして扱う。ノード集合の縦方向および横方向には、それぞれ最大でｈ個のノードが並ぶ。ｉ行目にはｈ−ｉ＋１個のノードが横方向に並び、ｊ列目にはｊ個のノードが縦方向に並ぶ。ｉ行目・ｊ列目のノードはｎijと表すことができる。行数ｈは、データ処理に使用するノードの数Ｎに基づいて、情報処理システムが決定する。例えば、ｈ2＜＝Ｎを満たす最大の整数をｈとし、三角ジョインにｈ2個のノードを使用する。
【０１４４】
データ集合Ａは、直角二等辺三角形状に並べられた複数のノードのうち、ノードｎ11を含む対角線上にあるｈ個のノードｎ11，ｎ22，…，ｎhhに分散される。データ要素は、虱潰しジョインの場合と同様に、均等（または、ほぼ均等）かつノード間で重複がないよう配置される。対角線上のノード以外のノードには、データ要素は配置されない。例えば、数式（１２）に示すように、ノードｎiiに部分集合Ａiが配置される。部分集合Ａiのデータ要素数は、データ集合Ａのデータ要素数を行数ｈで割ったものになる。
【０１４５】
【数１２】
0005790526.tif 000013
【０１４６】
図２６は、第５の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ３１）システム制御部１１２は、三角ジョインに用いるノードの数に基づいて行数ｈを決定し、ノード間の論理的な接続関係を決定する。
【０１４７】
（ステップＳ３２）システム制御部１１２は、クライアント３１から入力されたデータ集合Ａを、ｈ個の部分集合Ａ1，Ａ2，…，Ａhに分割し、三角ジョインに用いるノードのうちノードｎ11を含む対角線上のｈ個のノードに配置する。ただし、データ集合Ａの配置は、ノード１１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合、データ集合Ａの配置が完了していることもある。
【０１４８】
（ステップＳ３３）システム制御部１１２は、対角線上のノードｎiiに、各ノードに配置された部分集合Ａiを右方向および上方向に複製するよう指示する。各ノードの実行部は、対角線上のノードｎiiを始点として、部分集合Ａiを右方向および上方向にリレーする。下方向および左方向にはリレーは行われない。リレー方法として、例えば、図９に示した方法Ａを用いる。この複製により、対角線上にないノードｎijは、ノードｎiiに配置された部分集合Ａi（Ａｘ）とノードｎjjに配置された部分集合Ａj（Ａｙ）を取得する。一方、対角線上のノードｎiiは、他のノードからデータ要素を受信しない。
【０１４９】
（ステップＳ３４）システム制御部１１２は、三角ジョインに用いるノードのうち対角線上のノードに、ローカルな三角ジョインの実行を指示する。対角線上のノードｎiiの実行部は、部分集合Ａiの中でローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。また、システム制御部１１２は、対角線上にないノードに、ローカルな虱潰しジョインの実行を指示する。対角線上にないノードｎijは、右方向のリレーで取得した部分集合Ａｘと上方向のリレーで取得した部分集合Ａｙとの間で、ローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０１５０】
（ステップＳ３５）システム制御部１１２は、三角ジョインに用いるノード全てでステップＳ３４のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部１１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０１５１】
図２７は、第５の実施の形態のデータ配置例を示す図（その１）である。この例では、６個のノードｎ11，ｎ12，ｎ13，ｎ22，ｎ23，ｎ33を三角ジョインに用いる。また、データ集合Ａに９個のデータ要素ａ1〜ａ9が含まれている。対角線上のノードｎiiには、３個のデータ要素を含む部分集合Ａiが配置される。例えば、ノードｎ11には、部分集合Ａ1＝｛ａ1，ａ2，ａ3｝が配置される。そして、対角線上のノードｎiiを始点として、部分集合Ａiが右方向のノードおよび上方向のノードに複製される。例えば、ノードｎ11に配置された部分集合Ａ1が、ノードｎ11からノードｎ12に複製され、ノードｎ12からノードｎ13に複製される。また、ノードｎ22に配置された部分集合Ａ2が、ノードｎ22からノードｎ12に複製されると共に、ノードｎ22からノードｎ23に複製される。
【０１５２】
図２８は、第５の実施の形態のデータ配置例を示す図（その２）である。上記のデータ要素の複製を行うと、対角線上のノードｎiiは、当初配置された部分集合Ａiのみを保持する。一方、対角線上にないノードｎijは、部分集合Ａiを左隣のノードから受信し、部分集合Ａjを下方向のノードから受信する。例えば、ノードｎ13は、部分集合Ａ1＝｛ａ1，ａ2，ａ3｝と部分集合Ａ3＝｛ａ7，ａ8，ａ9｝を取得する。
【０１５３】
対角線上のノードｎiiは、部分集合Ａiの中で、ローカルに三角ジョインを行う。例えば、ノードｎ11は、Ａ1＝｛ａ1，ａ2，ａ3｝から抽出される６通りの組み合わせに対してｍａｐ関数を適用する。また、対角線上にないノードｎijは、部分集合Ａiと部分集合Ａjの間で、ローカルに虱潰しジョインを行う。例えば、ノードｎ13は、部分集合Ａ1＝｛ａ1，ａ2，ａ3｝からデータ要素を１つ選択し、部分集合Ａ3＝｛ａ7，ａ8，ａ9｝からデータ要素を１つ選択することで、３個×３個＝９通りの順序対に対してｍａｐ関数を適用する。図２８に示すように、データ集合Ａから抽出される４５通りの組み合わせが網羅されており、かつ、ノード間で重複して処理される組み合わせがない。
【０１５４】
第５の実施の形態の情報処理システムによれば、データ集合Ａの三角ジョインを、ノード間で重複するデータ処理が発生しないように、効率的に実行できる。
［第６の実施の形態］
次に、第６の実施の形態を説明する。第３〜第５の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第６の実施の形態では、三角ジョインを、第５の実施の形態とは異なる方法で実行する。第６の実施の形態の情報処理システムは、図３，４，１０に示した第３の実施の形態と同様のシステム構成で実現できる。
【０１５５】
図２９は、第６の実施の形態のノード関係を示す図である。第６の実施の形態の三角ジョインでは、データ処理に用いる複数のノードを、論理的に正方形状に並べられたものとして扱う。ノード集合の縦方向および横方向には、それぞれｈ個のノードが並ぶ。行数ｈは、データ処理に使用するノードの数に基づいて、情報処理システムが決定する。例えば、ｈ2＜＝Ｎを満たす最大の整数をｈとし、三角ジョインにｈ2個のノードを使用する。データ集合Ａは、第５の実施の形態の三角ジョインと同様、ノードｎ11を含む対角線上にあるｈ個のノードｎ11，ｎ22，…，ｎhhに分散して配置される。
【０１５６】
図３０は、第６の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ４１）システム制御部１１２は、三角ジョインに用いるノードの数に基づいて行数ｈを決定し、ノード間の論理的な接続関係を決定する。
【０１５７】
（ステップＳ４２）システム制御部１１２は、クライアント３１から入力されたデータ集合Ａを、ｈ個の部分集合Ａ1，Ａ2，…，Ａhに分割し、三角ジョインに用いるノードのうちノードｎ11を含む対角線上のｈ個のノードに配置する。ただし、データ集合Ａの配置は、ノード１１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合、データ集合Ａの配置が完了していることもある。
【０１５８】
（ステップＳ４３）システム制御部１１２は、対角線上のノードｎiiに、各ノードに配置された部分集合Ａiを行方向および列方向に複製するよう指示する。対角線上のノードｎiiの実行部は、部分集合Ａiに含まれる全てのデータ要素を、右方向のノードと下方向のノードに送信する。また、対角線上のノードｎiiの実行部は、データ要素数ができる限り同じになるよう部分集合Ａiを二分割し、一方のデータ要素を左方向のノードに送信し、他方のデータ要素を上方向のノードに送信する。リレー方法として、例えば、図９に示した方法Ｃを用いる。この複製により、対角線上にないノードｎijは、ノードｎiiに配置された部分集合Ａi（Ａｘ）とノードｎjjに配置された部分集合Ａjの半分（Ａｙ）を取得するか、または、部分集合Ａiの半分（Ａｘ）と部分集合Ａj（Ａｙ）を取得する。一方、対角線上のノードｎiiは、他のノードからデータ要素を受信しない。
【０１５９】
（ステップＳ４４）システム制御部１１２は、三角ジョインに用いるノードのうち対角線上のノードに、ローカルな三角ジョインの実行を指示する。対角線上のノードｎiiの実行部は、部分集合Ａiの中でローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。また、システム制御部１１２は、対角線上にないノードに、ローカルな虱潰しジョインの実行を指示する。対角線上にないノードｎijは、行方向のリレーで取得した部分集合Ａｘと列方向のリレーで取得した部分集合Ａｙとの間で、ローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０１６０】
（ステップＳ４５）システム制御部１１２は、三角ジョインに用いるノード全てでステップＳ４４のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部１１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０１６１】
図３１は、第６の実施の形態のデータ配置例を示す図（その１）である。この例では、９個のノードｎ11，ｎ12，…，ｎ33を三角ジョインに用いる。また、データ集合Ａに９個のデータ要素ａ1〜ａ9が含まれている。第５の実施の形態で示した例と同様に、対角線上のノードｎiiには、３個のデータ要素を含む部分集合Ａiが配置される。
【０１６２】
そして、対角線上のノードｎiiを始点として、部分集合Ａiが右方向のノードおよび下方向のノードに複製される。また、部分集合Ａiを二分割した一方が左方向のノードに複製され、他方が上方向のノードに複製される。例えば、ノードｎ22に配置されたデータ要素ａ4，ａ5，ａ6の全部が、ノードｎ22からノードｎ23に複製されると共に、ノードｎ22からノードｎ32に複製される。また、データ要素ａ4，ａ5，ａ6の半分（正確には約半分）であるデータ要素ａ4が、ノードｎ22からノードｎ21に複製され、残りの半分であるデータ要素ａ5，ａ6が、ノードｎ22からノードｎ12に複製される。
【０１６３】
図３２は、第６の実施の形態のデータ配置例を示す図（その２）である。上記のデータ要素の複製を行うと、対角線上のノードｎiiは、当初配置された部分集合Ａiのみを保持する。一方、対角線上にないノードｎijは、行方向に隣接するノードから部分集合Ａｘ（ＡiまたはＡiの半分）を受信し、列方向に隣接するノードから部分集合Ａｙ（ＡjまたはＡjの半分）を受信する。例えば、ノードｎ13は、部分集合Ａ1内の全てのデータ要素ａ1，ａ2，ａ3と部分集合Ａ3内の一部のデータ要素ａ8，ａ9を取得する。
【０１６４】
対角線上のノードｎiiは、第５の実施の形態と同様、部分集合Ａiの中で、ローカルに三角ジョインを行う。一方、対角線上にないノードは、取得した部分集合Ａｘと部分集合Ａｙの間で、ローカルに虱潰しジョインを行う。例えば、ノードｎ13は、データ要素ａ1，ａ2，ａ3から１つ選択し、データ要素ａ8，ａ9から１つ選択することで、３個×２個＝６通りの順序対に対してｍａｐ関数を適用する。図３２に示すように、第６の実施の形態の方法は、第５の実施の形態の対角線上にないノードで行われるデータ処理を二分割して、分割した一方のデータ処理を対角線より下にあるノードに振り替えたものと言うことができる。また、データ集合Ａから抽出される４５通りの組み合わせが網羅されており、かつ、ノード間で重複して処理される組み合わせがない。
【０１６５】
第６の実施の形態の情報処理システムによれば、データ集合Ａの三角ジョインを、複数のノードを用いて効率的に実行できる。特に、第６の実施の形態では、データ処理の負荷を、できる限り均等に複数のノードに配分することが可能となる。
【０１６６】
［第７の実施の形態］
次に、第７の実施の形態を説明する。第３〜第６の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第７の実施の形態では、三角ジョインを、第５および第６の実施の形態とは異なる方法で実行する。第７の実施の形態の情報処理システムは、図３，４，１０に示した第３の実施の形態と同様のシステム構成で実現できる。
【０１６７】
図３３は、第７の実施の形態のノード関係を示す図である。第７の実施の形態の三角ジョインでは、データ処理に用いる複数のノードを、論理的に正方形状に並べられたものとして扱う。ノード集合の縦方向および横方向には、それぞれ２ｋ＋１個（ｋは１以上の整数）、すなわち、３個以上の奇数個のノードが並ぶ。行数ｈ＝２ｋ＋１は、データ処理に使用できるノードの数に基づいて、情報処理システムが決定する。例えば、ｈ2＜＝Ｎを満たす最大の奇数をｈとし、三角ジョインにｈ2個のノードを使用する。また、第７の実施の形態の三角ジョインでは、これら複数のノードを、論理的にトーラス状に接続されたものとして扱う。よって、ノードｎihの右側にノードｎi1が隣接し、ノードｎhjの下側にノードｎ1jが隣接しているものとして扱う。データ集合Ａは、ノードｎ11を含む対角線上にあるｈ個のノードｎ11，ｎ22，…，ｎhhに分散して配置される。
【０１６８】
図３４は、第７の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ５１）システム制御部１１２は、三角ジョインに使用できるノードの数に基づいて行数ｈ＝２ｋ＋１を決定し、ノード間の論理的な接続関係を決定する。
【０１６９】
（ステップＳ５２）システム制御部１１２は、クライアント３１から入力されたデータ集合Ａを、ｈ個の部分集合Ａ1，Ａ2，…，Ａhに分割し、三角ジョインに用いるノードのうちノードｎ11を含む対角線上のｈ個のノードに配置する。ただし、データ集合Ａの配置は、ノード１１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合、データ集合Ａの配置が完了していることもある。
【０１７０】
（ステップＳ５３）システム制御部１１２は、対角線上のノードｎiiに、各ノードに配置された部分集合Ａiを行方向および列方向に複製するよう指示する。対角線上のノードｎiiの実行部は、部分集合Ａiを右側および下側の隣接するノードに送信する。
【０１７１】
行方向のリレーで、ノードｎiiの右側にある１個目からｋ個目までの各ノードの実行部は、部分集合Ａiを左隣のノードから受信する（Ａｘ）。一方、ｋ＋１個目から２ｋ個目までの各ノードの実行部は、部分集合Ａiを二分割した一方を左隣のノードから受信する（Ａｘ）。列方向のリレーで、ノードｎiiの下側にある１個目からｋ個目までの各ノードの実行部は、部分集合Ａiを上の隣接ノードから受信する（Ａｙ）。一方、ｋ＋１個目から２ｋ個目までの各ノードの実行部は、部分集合Ａiを二分割した他方を上の隣接ノードから受信する（Ａｙ）。リレー方法として、例えば、図９に示した方法Ｂを用いる。
【０１７２】
この複製により、対角線上にないノードｎijは、ノードｎiiに配置された部分集合Ａi（Ａｘ）とノードｎjjに配置された部分集合Ａjの半分（Ａｙ）を取得するか、または、部分集合Ａiの半分（Ａｘ）と部分集合Ａj（Ａｙ）を取得する。一方、対角線上のノードｎiiは、他のノードからデータ要素を受信しない。
【０１７３】
（ステップＳ５４）システム制御部１１２は、三角ジョインに用いるノードのうち対角線上のノードに、ローカルな三角ジョインの実行を指示する。対角線上のノードｎiiの実行部は、部分集合Ａiの中でローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。また、システム制御部１１２は、対角線上にないノードに、ローカルな虱潰しジョインの実行を指示する。対角線上にないノードｎijは、行方向のリレーで取得した部分集合Ａｘと列方向のリレーで取得した部分集合Ａｙとの間で、ローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０１７４】
（ステップＳ５５）システム制御部１１２は、三角ジョインに用いるノード全てでステップＳ５４のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部１１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０１７５】
図３５は、第７の実施の形態のデータ配置例を示す図（その１）である。この例では、ｋ＝１として、３×３＝９個のノードｎ11，ｎ12，…，ｎ33を三角ジョインに用いる。また、データ集合Ａに９個のデータ要素ａ1〜ａ9が含まれている。対角線上のノードには、それぞれ３個のデータ要素を含む部分集合が配置される。
【０１７６】
対角線上のノードｎ11に配置されたデータ要素ａ1，ａ2，ａ3がノードｎ12に複製され、その半分（例えば、データ要素ａ3）がノードｎ13に複製される。また、データ要素ａ1，ａ2，ａ3がノードｎ21に複製され、その半分（例えば、データ要素ａ1，ａ2）がノードｎ31に複製される。同様に、対角線上のノードｎ22に配置されたデータ要素ａ4，ａ5，ａ6がノードｎ23に複製され、その半分（例えば、データ要素ａ4）がノードｎ21に複製される。また、データ要素ａ4，ａ5，ａ6がノードｎ32に複製され、その半分（例えば、データ要素ａ5，ａ6）がノードｎ12に複製される。対角線上のノードｎ33に配置されたデータ要素ａ7，ａ8，ａ9がノードｎ31に複製され、その半分（例えば、データ要素ａ7）がノードｎ32に複製される。また、データ要素ａ7，ａ8，ａ9がノードｎ13に複製され、その半分（例えば、データ要素ａ8，ａ9）がノードｎ23に複製される。
【０１７７】
図３６は、第７の実施の形態のデータ配置例を示す図（その２）である。上記のデータ要素の複製を行うと、対角線上のノードｎiiは、当初配置された部分集合Ａiのみを保持する。一方、対角線上にないノードｎijは、左隣のノードから部分集合Ａｘ（ＡiまたはＡiの半分）を受信し、上の隣接ノードから部分集合Ａｙ（ＡjまたはＡjの半分）を受信する。第５および第６の実施の形態と同様に、対角線上のノードｎiiは、部分集合Ａiの中でローカルに三角ジョインを行う。対角線上にないノードは、取得した部分集合Ａｘと部分集合Ａｙの間でローカルに虱潰しジョインを行う。
【０１７８】
第７の実施の形態の情報処理システムによれば、第６の実施の形態と同様の効果が得られる。更に、第７の実施の形態では、対角線上のノードのデータ送信量が均等（または、ほぼ均等）になる。例えば、図３５のノードｎ11，ｎ22，ｎ33のデータ送信量は、全て同じである。このため、ノード間でのデータ要素の複製が一層効率的となる。
【０１７９】
［第８の実施の形態］
次に、第８の実施の形態を説明する。第３〜第７の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第８の実施の形態では、三角ジョインを、第５〜第７の実施の形態とは異なる方法で実行する。第８の実施の形態の情報処理システムは、図３，４，１０に示した第３の実施の形態と同様のシステム構成で実現できる。
【０１８０】
第８の実施の形態の三角ジョインでは、データ処理に用いるノードの集合を、図３３に示した第７の実施の形態と同様の論理的な構成として扱う。ただし、第８の実施の形態では、データ集合Ａが、データ処理に用いる複数のノードに、均等（または、ほぼ均等）かつノード間で重複がないように、分散して配置される。例えば、数式（１３）に示すように、ノードｎijに部分集合Ａijが配置される。部分集合Ａijのデータ要素数は、データ集合Ａのデータ要素数をノード数Ｎ＝ｈ2＝（２ｋ＋１）2で割ったものになる。
【０１８１】
【数１３】
0005790526.tif 000014
【０１８２】
図３７は、第８の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ６１）システム制御部１１２は、三角ジョインに使用できるノードの数に基づいて行数ｈ＝２ｋ＋１を決定し、ノード間の論理的な接続関係を決定する。
【０１８３】
（ステップＳ６２）システム制御部１１２は、クライアント３１から入力されたデータ集合ＡをＮ＝（２ｋ＋１）2個の部分集合に分割し、複数のノードに配置する。ただし、データ集合Ａの配置は、ノード１１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合、データ集合Ａの配置が完了していることもある。
【０１８４】
（ステップＳ６３）システム制御部１１２は、対角線上の各ノードを基準とした「近ノードリレー」と「遠ノードリレー」を実行するよう、各ノードに指示する。各ノードの実行部は、２種類のパスでデータ集合Ａの部分集合をリレーする。なお、ここでは、対角線上のノードｎiiを基準として、右側の１個目からｋ個目までのノードｎi(i+1)〜ｎi(i+k)を近ノードと呼び、右側のｋ＋１個目から２ｋ個目までのノードｎi(i+k+1)〜ｎi(i+2k)を遠ノードと呼ぶ。前述の通り、論理的に正方形状に並べられた複数のノードは、トーラス状に接続されているものとして取り扱う。
【０１８５】
近ノードリレーは、データ要素を、ノードｎ(i+2k)iからノードｎiiを通ってノードｎi(i+k)に至る直角パス（パス＃１）に沿ってリレーするものである。遠ノードリレーは、データ要素を、ノードｎ(i+k)iからノードｎiiを通ってノードｎi(i+2k)に至る直角パス（パス＃２）に沿ってリレーするものである。対角線上のノードｎiiに配置された部分集合Ａiiは、データ要素数の差が高々１つになるように、均等（または、ほぼ均等）に二分割される。そして、分割した一方が近ノードリレーによりパス＃１を通過するノードに複製され、分割した他方が遠ノードリレーによりパス＃２を通過するノードに複製される。近ノードに配置された部分集合Ａi(i+1)〜Ａi(i+k)は、近ノードリレーによりパス＃１を通過するノードに複製される。遠ノードに配置された部分集合Ａi(i+k+1)〜Ａi(i+2k)は、遠ノードリレーによりパス＃２を通過するノードに複製される。
【０１８６】
上記の対角ノード・近ノード・遠ノードの部分集合のリレーは、それぞれ、対角線上のノードの数ｈ＝２ｋ＋１に相当する回数行われる。この複製により、各ノードには、第７の実施の形態の複製方法を用いた場合と同じ数のデータ要素が収集されることになる。すなわち、第８の実施の形態の複製方法では、三角ジョインに用いるノードに均等にデータ集合Ａを分散した状態から、行毎にデータ要素が対角線上のノードに集められ、第７の実施の形態と同様の複製結果になるようにデータ要素が複製されると言うこともできる。
【０１８７】
（ステップＳ６４）システム制御部１１２は、三角ジョインに用いるノードのうち対角線上のノードに、ローカルな三角ジョインの実行を指示する。対角線上のノードｎiiの実行部は、ノードｎiiを基点としたリレーによって収集した部分集合の中で、ローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。また、システム制御部１１２は、対角線上にないノードに、ローカルな虱潰しジョインの実行を指示する。対角線上にないノードｎijは、ノードｎiiを基点としたリレーによって収集した部分集合Ａｘと、ノードｎjjを基点としたリレーで取得した部分集合Ａｙとの間で、ローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０１８８】
（ステップＳ６５）システム制御部１１２は、三角ジョインに用いるノード全てでステップＳ６４のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部１１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０１８９】
図３８は、第８の実施の形態のデータ配置例を示す図（その１）である。この例では、ｋ＝１として、３×３＝９個のノードｎ11，ｎ12，…，ｎ33を三角ジョインに用いる。また、データ集合Ａに９個のデータ要素ａ1〜ａ9が含まれている。各ノードｎijには、１個のデータ要素を含む部分集合Ａijが配置される。
【０１９０】
ノードｎ11に配置された部分集合Ａ11は、近ノードリレーによりノードｎ12，ｎ21，ｎ31に複製される。この例では、部分集合Ａ11のデータ要素数が１であるため、遠ノードリレーは行われない。ノードｎ12に配置された部分集合Ａ12は、近ノードリレーによりノードｎ11，ｎ21，ｎ31に複製される。ノードｎ13に配置された部分集合Ａ13は、遠ノードリレーによりノードｎ11，ｎ12，ｎ21に複製される。
【０１９１】
ノードｎ22に配置された部分集合Ａ22は、近ノードリレーによりノードｎ23，ｎ32，ｎ12に複製される。この例では、部分集合Ａ22のデータ要素数が１であるため、遠ノードリレーは行われない。ノードｎ23に配置された部分集合Ａ23は、近ノードリレーによりノードｎ22，ｎ32，ｎ12に複製される。ノードｎ21に配置された部分集合Ａ21は、遠ノードリレーによりノードｎ22，ｎ23，ｎ32に複製される。
【０１９２】
ノードｎ33に配置された部分集合Ａ33は、近ノードリレーによりノードｎ31，ｎ13，ｎ23に複製される。この例では、部分集合Ａ33のデータ要素数が１であるため、遠ノードリレーは行われない。ノードｎ31に配置された部分集合Ａ31は、近ノードリレーによりノードｎ33，ｎ13，ｎ23に複製される。ノードｎ32に配置された部分集合Ａ32は、遠ノードリレーによりノードｎ33，ｎ31，ｎ13に複製される。
【０１９３】
図３９は、第８の実施の形態のデータ配置例を示す図（その２）である。上記のデータ要素の複製を行うと、対角線上のノードｎiiは、ｉ行目のノードｎi1〜ｎihに配置されたデータ要素の集合をもつ。一方、対角線上にないノードｎijは、ノードｎiiを基点としたリレーによって収集された部分集合Ａｘと、ノードｎjjを基点としたリレーによって収集された部分集合Ａｙをもつ。第５〜第７の実施の形態と同様に、対角線上のノードｎiiは、取得した１つの部分集合の中でローカルに三角ジョインを行う。対角線上にないノードは、取得した２つの部分集合の間でローカルに虱潰しジョインを行う。
【０１９４】
第８の実施の形態の情報処理システムによれば、第７の実施の形態と同様の効果が得られる。更に、第８の実施の形態では、対角線上のノードだけでなく対角線上にないノードにも、できる限り均等にデータ要素が配置される。このため、データ要素を複製する初期段階において対角線上のノード以外のノードが待ち状態になることを抑制でき、複数のノードを一層効率的に用いて、データ要素を複製できるようになる。
【０１９５】
［第９の実施の形態］
次に、第９の実施の形態を説明する。第３〜第８の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第９の実施の形態では、複数の通信装置が階層的に接続されている大規模な情報処理システムを用いて、三角ジョインを実行する。第９の実施の形態の情報処理システムは、図４に示したハードウェア構成および図１５，１７に示した第４の実施の形態と同様のシステム構成によって実現できる。
【０１９６】
図４０は、第９の実施の形態のノード関係を示す図である。第９の実施の形態の三角ジョインでは、複数の仮想ノードを、論理的に直角三角形状に並べられたものとして扱う。縦方向および横方向には、それぞれ最大でＨ個の仮想ノードが並ぶ。ｉ行目にはＨ−ｉ＋１個の仮想ノードが横方向に並び、ｊ列目にはｊ個の仮想ノードが縦方向に並ぶ。行数Ｈは、データ処理に使用する仮想ノードの数に基づいて、情報処理システムが決定する。例えば、Ｈ2＜＝仮想ノード数を満たす最大の整数をＨとし、三角ジョインにＨ2個の仮想ノードを使用する。なお、システムが有する仮想ノード総数や各仮想ノードのノード総数は、データ処理に使用できるノード数、通信装置との接続関係、処理すべきデータの量、システムに要求される応答時間などを考慮して、予め決定されている。
【０１９７】
また、対角線上の各仮想ノード内では、データ処理に用いる複数のノードを、論理的に直角三角形状に並べられたものとして扱う。縦方向および横方向には、それぞれ最大でｈ個のノードが並ぶ。仮想ノード内のｉ行目にはｈ−ｉ＋１個のノードが横方向に並び、ｊ列目にはｊ個のノードが縦方向に並ぶ。一方、対角線上にない各仮想ノード内では、複数のノードを、論理的に正方形状に並べられたものとして扱う。縦方向および横方向には、それぞれｈ個のノードが並ぶ。行数ｈは、全ての仮想ノードに共通に決定される。例えば、各仮想ノードのノード数をＭとすると、ｈ2＜＝Ｍを満たす最大の整数をｈとし、仮想ノード毎にｈ2個のノードを使用する。
【０１９８】
三角ジョインを開始する際、データ集合Ａは、データ処理に用いる全ての仮想ノード11ｎ，…，HHｎの全てのノードｎ11，…，ｎhhに、均等（または、ほぼ均等）かつ重複なく分散される。ノード間でのデータ要素の複製は、第４の実施の形態と同様、まず異なる２以上のスイッチを介して仮想ノード間で行われ、その後、各仮想ノード内で閉じて行われる。仮想ノード間の通信は、「対応するノード」同士の通信として実現する。なお、図４０には、１階層の仮想化の例を示したが、仮想ノードが別の仮想ノードを含むように多階層の仮想化を行うことも可能である。
【０１９９】
図４１は、第９の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ７１）システム制御部２１２は、三角ジョインに用いる仮想ノードの数に基づいて行数Ｈを決定し、仮想ノード間の論理的な接続関係を決定する。また、システム制御部２１２は、複数の仮想ノードに共通の行数ｈを決定する。
【０２００】
（ステップＳ７２）システム制御部２１２は、クライアント３１から入力されたデータ集合Ａを、対角線上の仮想ノードの数分の部分集合に分割し、それら仮想ノードに分配する。各仮想ノードの仮想ノード制御部は、分配された部分集合を、当該仮想ノード内の対角線上のノードの数分の部分集合に更に分割し、それらノードに分配する。これにより、データ集合Ａが複数のノードに分散配置される。ただし、データ集合Ａの配置は、ノード２１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合、データ集合Ａの配置が既に完了していることもある。
【０２０１】
（ステップＳ７３）システム制御部２１２は、対角線上の仮想ノード11ｎ，22ｎ，…，HHｎ内の代理ノードに、仮想ノード間でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、対角線上のノードｎ11，ｎ22，…，ｎhhに、データ要素を右方向および上方向の仮想ノードに複製するよう指示する。対角線上の各ノードの実行部は、右隣の仮想ノード内の自ノードに対応するノードに、データ要素を複製する（部分集合Ａｘ）。また、対角線上の各ノードの実行部は、上側の隣接する仮想ノード内の自ノードに対応するノードに、データ要素を複製する（部分集合Ａｙ）。
【０２０２】
（ステップＳ７４）システム制御部２１２は、対角線上の仮想ノード11ｎ，22ｎ，…，HHｎ内の代理ノードに、仮想ノード内でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、対角線上のノードｎ11，ｎ22，…，ｎhhに、データ要素を右方向および上方向に複製するよう指示する。各ノードの実行部は、対角線上のノードを始点に、データ要素を右方向および上方向にリレーする（部分集合Ａｘ，Ａｙ）。
【０２０３】
（ステップＳ７５）システム制御部２１２は、対角線上にない仮想ノード内の代理ノードに、データ要素を仮想ノード内で複製するよう指示する。各代理ノードの仮想ノード制御部は、対角線上のノードｎ11，ｎ22，…，ｎhhに、左隣の仮想ノードから受信した部分集合Ａｘを行方向に送信し、下側の隣接する仮想ノードから受信した部分集合Ａｙを列方向に送信するよう指示する。各ノードの実行部は、部分集合Ａｘを行方向にリレーし、部分集合Ａｙを列方向にリレーする。なお、仮想ノードが入れ子になっており多階層に仮想化されている場合は、ステップＳ７４，Ｓ７５の処理が再帰的に実行される。その場合、再帰処理に関しては、システム制御部２１２が行った上記処理を、仮想ノード制御部が引き継ぐことで実現できる。ステップＳ７２の処理についても同様である。
【０２０４】
（ステップＳ７６）システム制御部２１２は、対角線上の仮想ノード11ｎ，22ｎ，…，HHｎ内の代理ノードに、三角ジョインを指示する。当該代理ノードの仮想ノード制御部は、対角線上のノードｎ11，ｎ22，…，ｎhhに三角ジョインの実行を指示し、対角線上にないノードに虱潰しジョインの実行を指示する。対角線上のノードの実行部は、自ノードがもつ部分集合の中でローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。対角線上にないノードの実行部は、部分集合Ａｘ，Ａｙの間でローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０２０５】
また、システム制御部２１２は、対角線上にない仮想ノード内の代理ノードに、虱潰しジョインを指示する。当該代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに虱潰しジョインの実行を指示する。各ノードの実行部は、部分集合Ａｘ，Ａｙの間でローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０２０６】
（ステップＳ７７）システム制御部２１２は、三角ジョインに用いるノード全てでステップＳ７６のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部２１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０２０７】
図４２は、第９の実施の形態のデータ配置例を示す図（その１）である。この例では、３個の仮想ノード11ｎ，12ｎ，22ｎを、三角ジョインに用いる。対角線上の仮想ノード11ｎ，22ｎは３個のノードｎ11，ｎ12，ｎ22を含み、対角線上でない仮想ノード12ｎは４個のノードｎ11，ｎ12，ｎ21，ｎ22を含む。また、データ集合Ａには、４個のデータ要素ａ1〜ａ4が含まれている。対角線上の仮想ノード内の対角線上のノード11ｎ11，11ｎ22，22ｎ11，22ｎ22に、それぞれ１個のデータ要素が配置される。各仮想ノードを仮想的に１つのノードと見ると、仮想ノード11ｎには部分集合Ａ1＝｛ａ1，ａ2｝が配置され、仮想ノード12ｎには部分集合Ａ2＝｛ａ3，ａ4｝が配置されていると言える。
【０２０８】
仮想ノード間の複製では、ノード11ｎ11に配置されたデータ要素ａ1が、ノード11ｎ11に対応するノード12ｎ11に複製され、ノード11ｎ22に配置されたデータ要素ａ2が、ノード11ｎ22に対応するノード12ｎ22に複製される。また、ノード22ｎ11に配置されたデータ要素ａ3が、ノード22ｎ11に対応するノード12ｎ11に複製され、ノード22ｎ22に配置されたデータ要素ａ4が、ノード22ｎ22に対応するノード12ｎ22に複製される。この時点では、対応関係にないノード間ではデータ要素は複製されない。
【０２０９】
図４３は、第９の実施の形態のデータ配置例を示す図（その２）である。この例では、ノード間の複製が完了した時点で、対角線上にない仮想ノード12ｎの対角線上のノード12ｎ11，12ｎ22に、それぞれ２個のデータ要素が収集されている。
【０２１０】
対角線上の仮想ノード11ｎ内では、ノード11ｎ11がデータ要素ａ1をノード11ｎ12に複製し、ノード11ｎ22がデータ要素ａ2をノード11ｎ12に複製する。同様に、対角線上の仮想ノード22ｎ内では、ノード22ｎ11がデータ要素ａ3をノード22ｎ12に複製し、ノード22ｎ22がデータ要素ａ4をノード22ｎ12に複製する。
【０２１１】
一方、対角線上にない仮想ノード12ｎ内では、ノード12ｎ11が行方向のリレーで受信したデータ要素ａ1をノード12ｎ12に複製し、ノード12ｎ22が行方向のリレーで受信したデータ要素ａ2をノード12ｎ21に複製する。また、ノード12ｎ11が列方向のリレーで受信したデータ要素ａ3をノード12ｎ21に複製し、ノード12ｎ22が列方向のリレーで受信したデータ要素ａ4をノード12ｎ12に複製する。
【０２１２】
図４４は、第９の実施の形態のデータ配置例を示す図（その３）である。この例では、各仮想ノード内でのデータ要素の複製が完了すると、対角線上の仮想ノード内の対角線上のノード11ｎ11，11ｎ22，22ｎ11，22ｎ22はそれぞれ１個のデータ要素をもち、他のノードはそれぞれ２個のデータ要素をもっている。対角線上の仮想ノード内の対角線上の各ノードはローカルに三角ジョインを行い、他の各ノードはローカルに虱潰しジョインを行う。図４４に示すように、データ集合Ａから抽出される１０通りの組み合わせが網羅されており、かつ、ノード間で重複して処理される組み合わせがない。
【０２１３】
第９の実施の形態の情報処理システムによれば、第５の実施の形態と同様の効果が得られる。更に、第９の実施の形態では、通信遅延の比較的大きい仮想ノード間の通信を纏めて行い、その後、通信遅延の比較的小さい仮想ノード内の通信のみを行うため、ノード間の物理的な通信距離を考慮しない場合と比べて、意図しない待ち時間を抑制し得る。そのため、通信の並列化が容易となり、データ要素の複製を一層効率化できる。
【０２１４】
［第１０の実施の形態］
次に、第１０の実施の形態を説明する。第３〜第９の実施の形態との差異を中心に説明し、同様の事項については説明を省略する。第１０の実施の形態では、三角ジョインを、第９の実施の形態とは異なる方法で実行する。第１０の実施の形態の情報処理システムは、第９の実施の形態と同様のシステム構成で実現できる。
【０２１５】
図４５は、第１０の実施の形態のノード関係を示す図である。第１０の実施の形態の三角ジョインでは、複数の仮想ノードを、論理的に正方形状に並べられたものとして扱う。縦方向および横方向には、それぞれＨ＝２Ｋ＋１個（Ｋは１以上の整数）の仮想ノードが並ぶ。行数Ｈは、データ処理に使用できる仮想ノードの数に基づいて、情報処理システムが決定する。行数Ｈの決定方法は、第９の実施の形態で説明した方法を用いることができる。ただし、第１０の実施の形態では、行数Ｈは奇数であることに留意する。また、これら複数の仮想ノードを、論理的にトーラス状に接続されたものとして扱う。よって、仮想ノードiHｎの右側に仮想ノードi1ｎが隣接し、仮想ノードHjｎの下側に仮想ノード1jｎが隣接しているものとして扱う。
【０２１６】
また、各仮想ノード内では、複数のノードを、論理的に正方形状に並べられたものとして扱う。縦方向および横方向には、それぞれｈ＝２ｋ＋１個の仮想ノードが並ぶ。行数ｈは、複数の仮想ノードに共通であり、各仮想ノードに含まれるノードの数に基づいて、情報処理システムが決定する。行数ｈの決定方法は、第９の実施の形態で説明した方法を用いることができる。ただし、第１０の実施の形態では、行数ｈは奇数であることに留意する。また、これら複数のノードを、各仮想ノード内で論理的にトーラス状に接続されたものとして扱う。データ集合Ａは、データ処理に用いる全ての仮想ノード11ｎ，…，HHｎに含まれる全てのノードｎ11，…，ｎhhに、均等（または、ほぼ均等）かつ重複なく分散される。ノード間でのデータ要素の複製は、まず異なる仮想ノード間で行われ、その後、各仮想ノード内で閉じて行われる。
【０２１７】
図４６は、第１０の実施の形態のジョインの手順例を示すフローチャートである。
（ステップＳ８１）システム制御部２１２は、三角ジョインに使用可能な仮想ノードの数に基づいて行数Ｈを決定し、仮想ノード間の論理的な接続関係を決定する。また、システム制御部２１２は、複数の仮想ノードに共通の行数ｈを決定する。
【０２１８】
（ステップＳ８２）システム制御部２１２は、クライアント３１から入力されたデータ集合Ａを、三角ジョインに用いる仮想ノードの数分の部分集合に分割し、それら仮想ノードに分配する。各仮想ノードの仮想ノード制御部は、分配された部分集合を、当該仮想ノードのノード数分の部分集合に更に分割し、それらノードに分配する。これにより、データ集合Ａが複数のノードに分散配置される。ただし、データ集合Ａの配置は、ノード２１がデータ処理開始のコマンドを受け付ける前に、クライアント３１からの指示に従って行っておいてもよい。また、データ集合Ａとして前のデータ処理の結果を利用する場合には、データ集合Ａの配置が既に完了していることもある。
【０２１９】
（ステップＳ８３）システム制御部２１２は、各仮想ノードの代理ノードに、対角線上の各仮想ノードを基準とした「近ノードリレー」と「遠ノードリレー」を、仮想ノード間で実行するよう指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、上記の２種類のリレーを指示する。各ノードの実行部は、他の仮想ノード内の対応するノードとの間で、データ集合Ａの部分集合をリレーする。
【０２２０】
仮想ノード間の近ノードリレーは、データ要素を、仮想ノード(i+2k)iｎから仮想ノードiiｎを通って仮想ノードi(i+k)ｎに至る直角パス（パス＃１）に沿ってリレーするものである。仮想ノード間の遠ノードリレーは、データ要素を、仮想ノード(i+k)iｎから仮想ノードiiｎを通って仮想ノードi(i+2k)ｎに至る直角パス（パス＃２）に沿ってリレーするものである。対角線上の仮想ノードiiｎに配置された部分集合は、データ要素数の差が高々１つになるように、均等（または、ほぼ均等）に二分割される。そして、分割した一方が近ノードリレーによりパス＃１を通過する仮想ノードに複製され、分割した他方が遠ノードリレーによりパス＃２を通過する仮想ノードに複製される。仮想ノードi(i+1)ｎ〜i(i+k)ｎに配置された部分集合は、近ノードリレーによりパス＃１を通過する仮想ノードに複製される。仮想ノードi(i+k+1)ｎ〜i(i+2k)ｎに配置された部分集合は、遠ノードリレーによりパス＃２を通過する仮想ノードに複製される。
【０２２１】
（ステップＳ８４）システム制御部２１２は、対角線上の仮想ノード11ｎ，22ｎ，…，HHｎ内の代理ノードに、仮想ノード内でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、対角線上の各ノードを基準とした「近ノードリレー」と「遠ノードリレー」を実行するよう指示する。各ノードの実行部は、自ノードに配置されたデータ要素と他の仮想ノードから受信したデータ要素とを、第８の実施の形態と同様の方法で、仮想ノード内で複製する。
【０２２２】
（ステップＳ８５）システム制御部２１２は、対角線上にない仮想ノード内の代理ノードに、仮想ノード内でデータ要素を複製するよう指示する。各代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに、行方向および列方向のリレーを指示する。各ノードの実行部は、１つの仮想ノードを基点とした仮想ノード間のリレーにより取得した部分集合Ａｘを行方向にリレーし、他の仮想ノードを基点とした仮想ノード間のリレーにより取得した部分集合Ａｙを列方向にリレーする。すなわち、仮想ノード内で、虱潰しジョインと同様の方法によりデータ要素が複製される。なお、仮想ノードが入れ子になっており多階層に仮想化されている場合は、ステップＳ８４，Ｓ８５の処理が再帰的に実行される。その場合、再帰処理に関しては、システム制御部２１２が行った上記処理を、各仮想ノードの仮想ノード制御部が引き継ぐことで実現できる。ステップＳ８２の処理も同様である。
【０２２３】
（ステップＳ８６）システム制御部２１２は、対角線上の仮想ノード11ｎ，22ｎ，…，HHｎ内の代理ノードに、三角ジョインを指示する。当該代理ノードの仮想ノード制御部は、対角線上のノードｎ11，ｎ22，…，ｎhhに三角ジョインの実行を指示し、対角線上にないノードに虱潰しジョインの実行を指示する。対角線上のノードの実行部は、自ノードがもつ部分集合の中でローカルに三角ジョインを行い、結果を当該ノードのデータ記憶部に書き込む。対角線上にないノードの実行部は、１つのノードを基点としたリレーにより取得した部分集合Ａｘと他のノードを基点としたリレーにより取得した部分集合Ａｙの間でローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０２２４】
また、システム制御部２１２は、対角線上にない仮想ノード内の代理ノードに、虱潰しジョインを指示する。当該代理ノードの仮想ノード制御部は、仮想ノード内の各ノードに虱潰しジョインの実行を指示する。各ノードの実行部は、行方向のリレーにより取得した部分集合Ａｘと列方向のリレーにより取得した部分集合Ａｙの間でローカルに虱潰しジョインを行い、結果を当該ノードのデータ記憶部に書き込む。
【０２２５】
（ステップＳ８７）システム制御部２１２は、三角ジョインに用いるノード全てでステップＳ８６のデータ処理が完了したことを確認すると、クライアント３１に三角ジョインの完了を報告する。このとき、システム制御部２１２は、各ノードのデータ記憶部から結果を収集してクライアント３１に送信してもよいし、結果を収集せずに各ノードのデータ記憶部に格納されたままにしてもよい。
【０２２６】
図４７は、第１０の実施の形態のデータ配置例を示す図（その１）である。この例では、９個の仮想ノード11ｎ，12ｎ，…，33ｎが三角ジョインに用いられ、論理的に１辺に３個の仮想ノードが並べられる。データ集合Ａは、９個の仮想ノードに分散して配置される。各仮想ノードを仮想的に１つのノードと見ると、データ集合Ａが９個の部分集合Ａ1〜Ａ9に分割されて仮想ノード11ｎ，12ｎ，…，33ｎに配置されると言える。
【０２２７】
図４８は、第１０の実施の形態のデータ配置例を示す図（その２）である。各仮想ノードを仮想的に１つのノードと見ると、第８の実施の形態と同様のリレー方法によって、仮想ノード間でデータ要素が複製される。ただし、仮想ノード間のデータ要素の複製は、前述の通り、対応するノード間のデータ要素の複製として実現する。
【０２２８】
仮想ノード11ｎに配置された部分集合Ａ1は二分割され、一方が近ノードリレーにより仮想ノード12ｎ，21ｎ，31ｎに複製され、他方が遠ノードリレーにより仮想ノード12ｎ，13ｎ，21ｎに複製される。仮想ノード12ｎに配置された部分集合Ａ2は、近ノードリレーにより仮想ノード11ｎ，21ｎ，31ｎに複製される。仮想ノード13ｎに配置された部分集合Ａ3は、遠ノードリレーにより仮想ノード11ｎ，12ｎ，21ｎに複製される。
【０２２９】
仮想ノード22ｎに配置された部分集合Ａ5は二分割され、一方が近ノードリレーにより仮想ノード23ｎ，32ｎ，12ｎに複製され、他方が遠ノードリレーにより仮想ノード23ｎ，21ｎ，32ｎに複製される。仮想ノード23ｎに配置された部分集合Ａ6は、近ノードリレーにより仮想ノード22ｎ，32ｎ，12ｎに複製される。仮想ノード21ｎに配置された部分集合Ａ4は、遠ノードリレーにより仮想ノード22ｎ，23ｎ，32ｎに複製される。
【０２３０】
仮想ノード33ｎに配置された部分集合Ａ9は二分割され、一方が近ノードリレーにより仮想ノード31ｎ，13ｎ，23ｎに複製され、他方が遠ノードリレーにより仮想ノード31ｎ，32ｎ，13ｎに複製される。仮想ノード31ｎに配置された部分集合Ａ7は、近ノードリレーにより仮想ノード33ｎ，13ｎ，23ｎに複製される。仮想ノード32ｎに配置された部分集合Ａ8は、遠ノードリレーにより仮想ノード33ｎ，31ｎ，13ｎに複製される。
【０２３１】
図４９は、第１０の実施の形態のデータ配置例を示す図（その３）である。この例では、９個の仮想ノード11ｎ，12ｎ，…，33ｎは、それぞれ９個のノードｎ11，ｎ12，…，ｎ33を含む。また、データ集合Ａには８１個のデータ要素ａ1〜ａ81が含まれている。よって、各ノードには、均等に１個のデータ要素が配置される。例えば、ノード11ｎ11にデータ要素ａ1が配置され、ノード33ｎ33にデータ要素ａ81が配置される。
【０２３２】
データ要素が配置されると、対角線上の仮想ノード11ｎ，22ｎ，33ｎそれぞれを基点として、「近ノードリレー」と「遠ノードリレー」が、異なる仮想ノードの対応するノード間で行われる。例えば、ノード11ｎ11に配置されたデータ要素ａ1が、近ノードリレーによりノード12ｎ11，21ｎ11，31ｎ11に複製される。データ要素数が１であるため、遠ノードリレーは行われない。ノード12ｎ11に配置されたデータ要素ａ4が、近ノードリレーによりノード11ｎ11，21ｎ11，31ｎ11に複製される。ノード13ｎ11に配置されたデータ要素ａ7が、遠ノードリレーによりノード11ｎ11，12ｎ11，21ｎ11に複製される。
【０２３３】
図５０は、第１０の実施の形態のデータ配置例を示す図（その４）である。図４９のように配置されたデータ要素が仮想ノード間で複製されると、各ノードには、図５０に示すようにデータ要素が収集される。なお、図５０では、データ要素を識別するための添え字としての数字のみ記載している。例えば、ノード11ｎ11にはデータ要素ａ1，ａ4，ａ7が収集される。ノード12ｎ11にはデータ要素ａ1，ａ4，ａ7（部分集合Ａｘ）とデータ要素ａ31，ａ34（部分集合Ａｙ）が収集される。ノード13ｎ11にはデータ要素ａ7（部分集合Ａｘ）とデータ要素ａ55，ａ58，ａ61（部分集合Ａｙ）が収集される。仮想ノード間のデータ要素の複製が完了すると、各仮想ノード内でデータ要素が複製される。
【０２３４】
対角線上の仮想ノード11ｎ，22ｎ，33ｎでは、第８の実施の形態の三角ジョインと同様の方法で、データ要素が複製される。例えば、ノード11ｎ11に収集されたデータ要素ａ1，ａ4，ａ7のうちデータ要素ａ1，ａ4が近ノードリレーによりノード11ｎ12，11ｎ21，11ｎ31に複製され、データ要素ａ7が遠ノードリレーによりノード11ｎ12，11ｎ13，11ｎ21に複製され。ノード11ｎ12のデータ要素ａ2，ａ5，ａ8が、近ノードリレーによりノード11ｎ11，11ｎ21，11ｎ31に複製される。ノード11ｎ13のデータ要素ａ3，ａ6，ａ9が、遠ノードリレーによりノード11ｎ11，11ｎ12，11ｎ21に複製される。
【０２３５】
また、対角線上にない仮想ノードでは、第３の実施の形態の虱潰しジョインと同様の方法で、行方向および列方向にデータ要素が複製される。例えば、ノード12ｎ11に収集されたデータ要素ａ1，ａ4，ａ7（部分集合Ａｘ）が、行方向のリレーによりノード12ｎ12，12ｎ13に複製される。また、ノード12ｎ11に収集されたデータ要素ａ31，ａ34（部分集合Ａｙ）が、列方向のリレーによりノード12ｎ21，12ｎ31に複製される。
【０２３６】
図５１は、第１０の実施の形態のデータ配置例を示す図（その５）である。上記のデータ要素の複製の結果、各ノードには、図５１に示すようにデータ要素が収集される。例えば、ノード11ｎ11にはデータ要素ａ1〜ａ9が収集される。ノード11ｎ12にはデータ要素ａ1〜ａ9（部分集合Ａｘ）とデータ要素ａ11，ａ12，ａ14，ａ15，ａ18（部分集合Ａｙ）が収集される。ノード12ｎ11にはデータ要素ａ1〜ａ9（部分集合Ａｘ）とデータ要素ａ31，ａ34，ａ40，ａ43，ａ49，ａ52（部分集合Ａｙ）が収集される。
【０２３７】
対角線上の仮想ノード11ｎ，22ｎ，33ｎ内の対角線上のノードｎ11，ｎ22，ｎ33は、自ノードに収集された部分集合の中でローカルに三角ジョインを行う。一方、他のノードは、自ノードに収集された部分集合Ａｘ，Ａｙの間でローカルに虱潰しジョインを行う。例えば、ノード11ｎ11は、データ要素ａ1〜ａ9から抽出される４５通りの組み合わせに対してｍａｐ関数を適用する。ノード11ｎ12は、データ要素ａ1〜ａ9から１つ選択し、データ要素ａ11，ａ12，ａ14，ａ15，ａ18から１つ選択することで、９個×５個＝４５通りの順序対に対してｍａｐ関数を適用する。ノード12ｎ11は、データ要素ａ1〜ａ9から１つ選択し、データ要素ａ31，ａ34，ａ40，ａ43，ａ49，ａ52から１つ選択することで、９個×６個＝５４通りの順序対に対してｍａｐ関数を適用する。
【０２３８】
このように、第１０の実施の形態では、仮想ノード間では三角ジョインのデータ複製が行われる。対角線上の仮想ノード内では三角ジョインのデータ複製が再帰的に行われ、対角線上にない仮想ノード内では虱潰しジョインのデータ複製が行われる。そして、対角線上の仮想ノード内の対角線上のノード（仮想化なしと仮定した場合の対角線上のノード）ではローカルに三角ジョインが行われ、他のノードではローカルに虱潰しジョインが行われる。図５１の例では、データ集合Ａから抽出される３３２１通りの組み合わせが８１個のノードによって網羅され、かつ、ノード間で重複して処理される組み合わせがない。
【０２３９】
第１０の実施の形態の情報処理システムによれば、第９の実施の形態と同様に、複数の異なるスイッチの配下にある複数のノードを三角ジョインに使用する場合でも、通信の並列化が容易となりデータ要素の複製を効率化できる。また、第８の実施の形態と同様に、三角ジョインに用いる複数のノードにできる限り均等にデータ要素を配置でき、データ要素を複製する初期段階においても複数のノードを効率的に用いることができる。
【符号の説明】
【０２４０】
２ａ〜２ｉ  ノード
１１〜１６  ノード
３１  クライアント
４１  ネットワーク
１１１，１２１  受信部
１１２  システム制御部
１１４，１２４  ノード制御部
１１５，１２５  実行部
１１６，１２６  データ記憶部
３１１  要求部
【図１】
0005790526.tif 000015
【図２】
0005790526.tif 000016
【図３】
0005790526.tif 000017
【図４】
0005790526.tif 000018
【図５】
0005790526.tif 000019
【図６】
0005790526.tif 000020
【図７】
0005790526.tif 000021
【図８】
0005790526.tif 000022
【図９】
0005790526.tif 000023
【図１０】
0005790526.tif 000024
【図１１】
0005790526.tif 000025
【図１２】
0005790526.tif 000026
【図１３】
0005790526.tif 000027
【図１４】
0005790526.tif 000028
【図１５】
0005790526.tif 000029
【図１６】
0005790526.tif 000030
【図１７】
0005790526.tif 000031
【図１８】
0005790526.tif 000032
【図１９】
0005790526.tif 000033
【図２０】
0005790526.tif 000034
【図２１】
0005790526.tif 000035
【図２２】
0005790526.tif 000036
【図２３】
0005790526.tif 000037
【図２４】
0005790526.tif 000038
【図２５】
0005790526.tif 000039
【図２６】
0005790526.tif 000040
【図２７】
0005790526.tif 000041
【図２８】
0005790526.tif 000042
【図２９】
0005790526.tif 000043
【図３０】
0005790526.tif 000044
【図３１】
0005790526.tif 000045
【図３２】
0005790526.tif 000046
【図３３】
0005790526.tif 000047
【図３４】
0005790526.tif 000048
【図３５】
0005790526.tif 000049
【図３６】
0005790526.tif 000050
【図３７】
0005790526.tif 000051
【図３８】
0005790526.tif 000052
【図３９】
0005790526.tif 000053
【図４０】
0005790526.tif 000054
【図４１】
0005790526.tif 000055
【図４２】
0005790526.tif 000056
【図４３】
0005790526.tif 000057
【図４４】
0005790526.tif 000058
【図４５】
0005790526.tif 000059
【図４６】
0005790526.tif 000060
【図４７】
0005790526.tif 000061
【図４８】
0005790526.tif 000062
【図４９】
0005790526.tif 000063
【図５０】
0005790526.tif 000064
【図５１】
0005790526.tif 000065