(57)【要約】  複数の計算ノードを用いたグラフ処理の場合に、処理対象となるグラフの規模が大きくなるほど、計算ノード間で転送される中間データ量が多くなるために、中間データの転送に要する時間が長くなり、ひいてはグラフ処理全体の速度が遅くなるという問題がある。  本発明は、複数の計算ノードによるグラフ処理での、送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組を有する中間データの転送を、各計算ノードに中間データを蓄積する送信バッファを設け、送信元のグラフ頂点の情報または送信先のグラフ頂点の情報に基づいて、蓄積された中間データの群の中の中間データの並びをソートし、中間データの群を転送することで、前述の課題を解決する。
2014006735.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算ノードによるグラフ処理での中間データの転送方法であって、
各計算ノードは送信バッファを有し、
各計算ノードには、処理対象のグラフ頂点が割当てられ、
前記中間データには、送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組が含まれ、
前記中間データを前記送信バッファに蓄積し、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートし、
前記中間データの群を転送することを特徴とするグラフ処理の中間データの転送方法。
【請求項２】
請求項１に記載のグラフ処理の中間データの転送方法において、
各計算ノードは受信バッファを有し、
各計算ノードは、
転送された前記中間データの群が前記送信元のグラフ頂点の情報に基づいてソートされている場合には、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートすることを特徴とするグラフ処理の中間データの転送方法。
【請求項３】
請求項１に記載のグラフ処理の中間データの転送方法において、
前記ソート後に、蓄積された前記中間データの群を圧縮することを特徴とするグラフ処理の中間データの転送方法。
【請求項４】
請求項３に記載のグラフ処理の中間データの転送方法において、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートする際に、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報のいずれかソート後に圧縮率が高くなる方に基づいて、ソートを行うことを特徴とするグラフ処理の中間データの転送方法。
【請求項５】
請求項１に記載のグラフ処理の中間データの転送方法において、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理の中間データの転送方法。
【請求項６】
複数の計算ノードによるグラフ処理での中間データの転送方法であって、
各計算ノードは送信バッファを有し、
各計算ノードには、処理対象のグラフ頂点が割当てられ、
前記中間データには、送信元のグラフ頂点の情報、送信先のグラフ頂点の情報、および前記送信元のグラフ頂点と前記送信先のグラフ頂点の間の依存関係の情報の組が含まれ、
前記中間データを前記送信バッファに蓄積し、
前記送信元のグラフ頂点の情報、前記送信先のグラフ頂点の情報、または前記依存関係の情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートし、
前記中間データの群を転送することを特徴とするグラフ処理の中間データの転送方法。
【請求項７】
請求項６に記載のグラフ処理の中間データの転送方法において、
各計算ノードは受信バッファを有し、
各計算ノードは、
転送された前記中間データの群が前記送信元のグラフ頂点の情報または前記依存関係の情報に基づいてソートされている場合には、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートすることを特徴とするグラフ処理の中間データの転送方法。
【請求項８】
請求項６に記載のグラフ処理の中間データの転送方法において、
前記ソート後に、蓄積された前記中間データの群を圧縮することを特徴とするグラフ処理の中間データの転送方法。
【請求項９】
請求項８に記載のグラフ処理の中間データの転送方法において、
前記送信元のグラフ頂点の情報、前記送信先のグラフ頂点の情報、または前記依存関係の情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートする際に、
前記送信元のグラフ頂点の情報、前記送信先のグラフ頂点の情報、または前記依存関係の情報のいずれかソート後に圧縮率が最も高くなる情報に基づいて、ソートを行うことを特徴とするグラフ処理の中間データの転送方法。
【請求項１０】
請求項６に記載のグラフ処理の中間データの転送方法において、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理の中間データの転送方法。
【請求項１１】
複数の計算ノードを有するグラフ処理システムであって、
各計算ノードは、
送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組を有するグラフ処理の中間データを保存する送信バッファと、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報に基づいて、前記送信バッファに蓄積された前記中間データの群の中の前記中間データの並びをソートするモジュールと、
前記中間データの群を転送するモジュールとを有することを特徴とするグラフ処理システム。
【請求項１２】
請求項１１に記載のグラフ処理システムにおいて、
各計算ノードは、
受信バッファと、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートするモジュールとを有することを特徴とするグラフ処理システム。
【請求項１３】
請求項１１に記載のグラフ処理システムにおいて、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の計算ノードを用いたグラフ処理に関し、特にグラフ情報の計算ノード間での転送に関するものである。
【背景技術】
【０００２】
グラフ処理における情報圧縮技術として、非特許文献１に記載されている技術がある。非特許文献１に記載の技術は、非ゼロの値を格納したベクトルＡ、非ゼロの箇所の列番号を格納したベクトルＢ、各行の先頭の非ゼロの箇所がベクトルＡの何番目の値に対応するかを格納したベクトルＣでグラフ構造データを表現することで情報を圧縮するものである。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】リチャード・バレット（Ｒｉｃｈａｒｄ  Ｂａｒｒｅｔｔ）、外９名著、「線形システムのソリューション向けテンプレート：反復法のためのビルディングブロック（Ｔｅｍｐｌａｔｅｓ  ｆｏｒ  ｔｈｅ  Ｓｏｌｕｔｉｏｎ  ｏｆ  Ｌｉｎｅａｒ  Ｓｙｓｔｅｍｓ：  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋｓ  ｆｏｒ  Ｉｔｅｒａｔｉｖｅ  Ｍｅｔｈｏｄｓ）」、ソサイエティ・フォー・インダストリアル・アンド・アプライド・マスマティクス（Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｉｎｄｕｓｔｒｉａｌ  ａｎｄ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ）、（米国）、１９９４年、ｐｐ．６４−６５
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載の技術では、グラフ構造データを圧縮することは可能であるが、グラフ処理時の中間データであるグラフの頂点間を伝搬する情報は圧縮できない。本願発明者らは、複数の計算ノードを用いたグラフ処理の場合に、処理対象となるグラフの規模が大きくなるほど、計算ノード間で転送される中間データ量が多くなるために、中間データの転送に要する時間が長くなり、ひいてはグラフ処理全体の速度が遅くなるという問題があることを見出した。【０００５】
そこで本発明は、効率的なグラフ処理の中間データの転送を目的とする。
【課題を解決するための手段】
【０００６】
本発明は、複数の計算ノードによるグラフ処理での、送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組を有する中間データの転送を、各計算ノードに中間データを蓄積する送信バッファを設け、送信元のグラフ頂点の情報または送信先のグラフ頂点の情報に基づいて、蓄積された中間データの群の中の中間データの並びをソートし、中間データの群を転送することで、前述の課題を解決する。
【発明の効果】
【０００７】
本発明によれば、複数計算ノードでグラフ処理を行う際に、効率的な中間データの転送を実現できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施例に係るグラフ処理システムを示す図である。
【図２】図１のＡｐサーバのシステム構成を示す図である。
【図３】図２のサーバ装置の内部構成を示すブロック図である。
【図４】図３のメモリ装置上に用意された送信バッファや受信バッファを示す図である。
【図５】処理対象のグラフの例を示す図である。
【図６】図５のグラフを行列形式で表現した図である。
【図７】図５のグラフをＣＳＲ形式で表現した図である。
【図８】頂点間の転送情報の構成を示した図である。
【図９】頂点割当て情報の例を示す図である。
【図１０】グラフ処理の例を示すフローチャートである。
【図１１】図１０の圧縮処理の詳細を示すフローチャートである。
【図１２】図１０の伸長処理の詳細を示すフローチャートである。
【図１３】図５のグラフの各頂点がどのサーバで処理されるかの例を示した説明図である。
【図１４】図１３に対し頂点間の情報の伝搬を示した図である。
【図１５（ａ）】サーバ装置４２０からサーバ装置４３０へ転送される情報のソート前の例を示す説明図である。
【図１５（ｂ）】サーバ装置４２０からサーバ装置４３０へ転送される情報のソート後の例を示す説明図である。
【図１５（ｃ）】サーバ装置４２０からサーバ装置４３０へ転送される情報の圧縮後の例を示す説明図である。
【発明を実施するための形態】
【実施例１】
【０００９】
図１は、本発明の実施の形態に係るグラフ処理システム１０の構成を概略的に示す図である。図１に示されるように、グラフ処理システム１０は、インターネット２００を介して通信可能なＰＣや携帯端末といったクライアント１００、インターネット２００を介してクライアント１００からの要求を受け付けるウェブサーバ（Ｗｅｂサーバ）３００、Ｗｅｂサーバ３００からの要求によりグラフ解析を行うアプリケーションサーバ（Ａｐサーバ）４００、およびデータベースへのアクセスを行うデータベースサーバ（ＤＢサーバ）５００を有している。但し、クライアント１００とＷｅｂサーバ３００を結ぶネットワークはインターネット２００に限定されず、例えばＬＡＮでも良い。また、本実施例では、Ｗｅｂサーバ３００、Ａｐサーバ４００、およびＤＢサーバ５００を備えるウェブ３層構成のシステムを記載しているが、本発明はこの構成に限定されるものではない。例えばグラフ解析も行うＷｅｂサーバ３００とＤＢサーバ５００の２層構成などでも良い。【００１０】
図２は、図１のＡｐサーバ４００のシステム構成を示す図である。図２に示されるようにＡｐサーバ４００はサーバ装置４２０、４３０、４４０、４５０と、それらを結ぶネットワーク装置４１０とを有している。サーバ装置４２０−４５０のそれぞれは、グラフ処理における計算ノードとして働く。サーバ装置の台数はサーバ装置の性能やタスクの負荷によって決められるものであるため、４台の構成に制限されず他の台数であっても良い。サーバ装置４２０−４５０は、並列処理を行い互いに通信しながら、最短経路問題を解く等のグラフ処理を実行する。サーバ装置４２０−４５０には、それぞれサーバ識別情報（サーバＩＤ）が与えられる。本実施例では、３台のサーバ装置をグラフ処理に用い、サーバ装置４２０のサーバＩＤは「１」、サーバ装置４３０のサーバＩＤは「２」、サーバ装置４４０のサーバＩＤは「３」である。【００１１】
図３は、図２に示されるサーバ装置４２０の内部構成を示すブロック図である。サーバ装置４３０、４４０、４５０の内部構成は、サーバ装置４２０の内部構成と同等の機能を有していれば良く、例えば、サーバ毎に異なるメーカや性能であってもかまわない。以降、サーバ装置４２０を代表として取り上げて説明する。【００１２】
サーバ装置４２０は、中央処理装置（ＣＰＵ）６００、メモリ装置６１０、ストレージ装置６２０、入力装置６３０、出力装置６４０、ネットワークインタフェース（Ｉ／Ｆ）６５０、およびバス６６０を備える。サーバ装置４２０内の構成要素間のデータ転送は主にバス６６０を介して行われる。ＣＰＵ６００はメモリ装置６１０を使用してグラフ解析プログラムを実行するとともにサーバ装置４２０全体の動作を制御する。メモリ装置６１０は、ＳＤＲＡＭなどの１次記憶装置であり、ＣＰＵ６００がプログラムを実行する際に必要な命令やデータを保持する。ストレージ装置６２０は、ＨＤＤやＳＳＤといった２次記憶装置であり、プログラムやデータを長期間保持する他、メモリ装置６１０のスワップ領域としても利用される。入力装置６３０は、マウスやキーボードなどであり、出力装置６４０は表示装置やスピーカーなどである。ネットワークインタフェース６５０は他のサーバ装置との通信に利用されるものであり、ＩｎｆｉｎｉＢａｎｄなどを用いることができる。【００１３】
図４は、メモリ装置６１０のメモリ領域に確保された送信バッファ６１１と、受信バッファ６１２と、処理キュー６１３と、グラフ演算モジュール６１４と、頂点割当て情報６１５と、次の回の処理を蓄積するＮＥＸＴキュー６１６と、圧縮モジュール６１７と、伸長モジュール６１８とを示す図である。送信バッファ６１１は、サーバ装置間で通信を行う際に送信するデータを一時保管するためのメモリ領域である。受信バッファ６１２は、サーバ装置間で通信を行う際に受信するデータを一時保管するためのメモリ領域である。サーバ装置間で転送されるグラフ処理の中間データは、送信バッファ６１１や受信バッファ６１２に一時保管される。送信バッファ６１１に蓄えられたデータは、ＣＰＵ６００の送信指示によりネットワークインタフェース６５０へ転送された後、ネットワーク装置４１０を介して別のサーバ装置へ送信される。送信データは、別のサーバ装置のネットワークインタフェース６５０で受信された後、別のサーバ装置の受信バッファ６１２に蓄えられる。処理キュー６１３は、グラフ処理のあるフェーズにおいて演算可能なデータを一時保管するためのメモリ領域であり、ＮＥＸＴキュー６１６は、その次のフェーズにおいて演算可能なデータを一時保管するためのメモリ領域である。グラフ演算モジュールは、最短経路探索などのグラフ処理の演算を行うプログラムモジュールである。圧縮モジュール６１７は、後述するが、サーバ装置間で転送されるグラフ処理の中間データを圧縮するプログラムモジュールである。伸長モジュール６１８は、後述するが、サーバ装置間で転送されるグラフ処理の中間データを伸長するプログラムモジュールである。頂点割当て情報６１５は、後述するが、複数のサーバ装置に対するグラフ処理の割当てを示す情報である。【００１４】
図５は、本実施例のグラフ処理システム１０の動作を説明するために具体例としてあげたグラフの図である。図５中の円はグラフの頂点を表しており、円内には頂点の識別番号（以下、頂点番号）を示している。頂点間の線はグラフの辺である。グラフは様々な事柄の関係性を表現するのに適している。例えば、グラフの頂点を駅や交差点とみなすと辺は線路や道路を表し、頂点を人や企業とみなした場合には、辺は人や企業間の相互関係を示す。辺は頂点間の関係を示す重みを持ち、前者の例では時間や距離、後者の例では結びつきの強さを示す。【００１５】
図６および図７は、図５に示したグラフをグラフ構造データとして表現したもので、図５のグラフと同じグラフ構造を示している。図６は図５のグラフを行列形式で表現したものであり、図７は図５のグラフをＣＳＲ（Ｃｏｍｐｒｅｓｓｅｄ  Ｓｐａｒｓｅ  Ｒｏｗ）形式で表現したものである。図６の表中の値は辺の重みを示し、値が０（最短経路問題など解くべき問題によっては∞と表現した方が都合の良いものもある）の箇所は辺が存在しないことを意味する。図７のＣＳＲ形式は、非ゼロの値を格納したｖａｌｕｅｓ、非ゼロの箇所の列番号を格納したｃｏｌｕｍｎｓ、各行の先頭の非ゼロの箇所がｖａｌｕｅｓの何番目の値に対応するかを格納したｒｏｗｉｎｄｅｘから成る。ＣＳＲ形式は本図のような疎行列を表現するのに適している。行列形式ではｎ×ｍの行列を表現するのにｎ×ｍの記憶容量が必要になるが、ＣＳＲ形式では、非ゼロの数をｌとすると２×ｌ＋ｎ＋１の記憶容量で済む。例えば、ビッググラフに代表されるスケールフリー性を持っているグラフは、疎行列となるため、一般にＣＳＲ形式やＣＳＣ（Ｃｏｍｐｒｅｓｓｅｄ  Ｓｐａｒｓｅ  Ｃｏｌｕｍｎ）形式（ＣＳＲ形式に対して行と列を入れ替えたもの）といった圧縮格納形式でグラフ構造データが保存される。【００１６】
図８は、頂点間で転送される情報を示したもので、各行は送信先の頂点（ｔａｒｇｅｔ頂点）の頂点番号（ｔａｒｇｅｔ）、送信元の頂点（ｓｏｕｒｃｅ頂点）の頂点番号（ｓｏｕｒｃｅ）、送信データ（ｄａｔａ）の組で構成される。ここでは、例として頂点３から頂点７、８、９へ転送される情報を示している。ｔａｒｇｅｔと送信先のサーバ装置、およびｓｏｕｒｃｅと送信元サーバ装置の関係は、頂点割当て情報６１５として各サーバ装置のメモリ装置６１０に保存されている。【００１７】
図９は、本実施例の頂点割当て情報６１５を示す図である。頂点割当て情報６１５は、頂点番号と該頂点番号の頂点の演算が割り当てられているサーバ装置のサーバＩＤとの組をエントリとする。頂点割当て情報６１５は、各サーバ装置への頂点の割当ての際に生成することができる。本実施例では、サーバＩＤの昇順に、頂点番号が若い頂点の群を配置しているが、頂点の配置の構成はこれに限定されず、頂点が各サーバに分散配置されていれば本発明を適用できる。【００１８】
図１０に本実施例のグラフ処理システム１０によるグラフ処理の動作例をフローチャートで示す。本実施例では、図７のグラフ構造データが処理対象としてストレージ装置６２０に格納されており、各サーバ装置のメモリ装置６１０に図７のグラフ構造データが転送された状態で、図９に示した割当てで各サーバ装置にそれぞれが演算する頂点が割当てられているとして説明する。各サーバ装置で演算する頂点の割当ては、各サーバ装置のメモリ装置６１０に頂点割当て情報６１５として、保存されている。また、グラフ解析の始点となる頂点は、サーバ装置４２０に割当てられるとして説明する。【００１９】
まず、サーバ装置４２０のグラフ演算モジュール６１４が、グラフ解析の始点となる頂点をｔａｒｇｅｔ頂点として選択する（ステップＳ１００、Ｓ１０１）。次に、サーバ装置４２０のグラフ演算モジュール６１４が、選択したｔａｒｇｅｔ頂点に対するｓｏｕｒｃｅ頂点とｄａｔａの組を作り、処理キュー６１３へ入れる（ステップＳ１０２）。ここでは、ｔａｒｇｅｔ頂点が始点であるため、ｓｏｕｒｃｅ頂点、ｄａｔａはダミーデータ（例えば、ｓｏｕｒｃｅ＝ｔａｒｇｅｔ、ｄａｔａ＝Ｚ）とする。【００２０】
ステップＳ１０３では、各サーバ装置のグラフ演算モジュール６１４が、各サーバ装置の処理キュー６１３が空であるか否かの判定を行い、各サーバ装置の動作は、空であればステップＳ１０８へ進み、空でなければステップＳ１０４へ進む。ステップＳ１０４では、各サーバ装置のグラフ演算モジュール６１４が、各サーバ装置の処理キュー６１３から（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）情報の組を取り出し、ｔａｒｇｅｔ頂点に対する演算を実施する。【００２１】
次に、ステップＳ１０５で各サーバ装置のグラフ演算モジュール６１４が、処理キュー６１３にあったｔａｒｇｅｔ頂点を次のｓｏｕｒｃｅ頂点として選択し、メモリ装置６１０にある図７のグラフ構造データを参照して、グラフ処理の中間データとなる、ｓｏｕｒｃｅ頂点と、グラフ構造データから読み出したｔａｒｇｅｔ頂点と、ｄａｔａの組を生成する。ステップ１０６で、各サーバ装置のグラフ演算モジュール６１４が、ステップ１０５で生成した組のｔａｒｇｅｔ頂点を自サーバ装置が処理する場合は生成した組の情報をＮｅｘｔキュー６１６に入れ、他サーバが処理する場合は生成した組の情報を送信バッファ６１１へ入れる。送信バッファ６１１は、ｔａｒｇｅｔ頂点を処理するサーバ装置毎に分けておくことが望ましい。【００２２】
ステップＳ１０７では、送信情報をまとめて効率よく転送するために、各サーバ装置で、送信バッファ６１１に格納された情報の量が予め設定された送信基準サイズを超えたか否かの判定が行われる。基準のサイズを超えた場合は送信を開始するために、各サーバ装置の動作はステップＳ２００へ進み、基準のサイズを超えていない場合はステップＳ１０３へ戻る。ステップ１０８では、各サーバ装置で、処理キュー６１３が空になった状態で未送信の情報が送信バッファ６１１に残っているか否かの判定が行われる。送信バッファ６１１が空でない場合は未送信情報を送信するために、各サーバ装置の動作はステップＳ２００へ進み、送信バッファが空の場合は未送信情報がないため、受信を開始するためにステップＳ３００へ進む。【００２３】
図１１に、ステップＳ２００の詳細なステップであるステップＳ２０１−Ｓ２０５を示す。まず、ステップＳ２００では、各サーバ装置の圧縮モジュール６１７が、送信バッファ６１１内のｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点、ｄａｔａのカラム毎に共通な値の数をカウントアップする（ステップＳ２０１、ステップＳ２０２）。その後、各サーバ装置の圧縮モジュール６１７は、各カラムで共通な値は連続するものとしてランレングス符号化を行った場合に最も圧縮率の高いカラムをキーとして送信バッファ６１１内のデータのソートを行う（ステップＳ２０３）。この際、ｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点、ｄａｔａの組の対応は保持した形でソートが行われる。このように、送信バッファ６１１に蓄積されている中間データであるｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点、ｄａｔａの組の群の中で、組の並びのソートが行われることで、効率的な送信データの圧縮が可能となり、効率的なデータ転送を実現でき、ひいてはグラフ処理を高速化できる。さらに、ｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点、ｄａｔａの内で最も圧縮率が高くなるカラムをキーとすることで、さらに効率的な送信データの圧縮が可能となる。なお、ｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点のカラム毎に共通な値の数をカウントアップし、ｔａｒｇｅｔ頂点またはｓｏｕｒｃｅ頂点のいずれか圧縮率の高い方のカラムをキーとしてソートしてもよい。例えば、辺に重みが無いグラフ処理の場合には、ｄａｔａの送信は不要である。【００２４】
各サーバ装置の圧縮モジュール６１７は、ソートを行った後、キーとしたカラムに対しランレングス符号化を行う（ステップＳ２０４）。予めソートがおこなわれることで、共通の数値が連続するようになり、ランレングス符号化での圧縮率を高めることができる。また、伸長モジュール６１８による復号時にどのカラムをキーとして圧縮を行ったかが分かるように、各サーバ装置の圧縮モジュール６１７は、送信情報の先頭にキーとしたカラムを示す情報を付加する。ステップＳ２００に続くステップＳ１０９では、各サーバ装置は、ステップＳ２００で処理された送信データを、頂点割当て情報６１５を参照し、Ｔａｒｇｅｔ頂点の演算を割当てられているサーバ装置へ送信する。【００２５】
図１２に、ステップＳ３００の詳細なステップであるステップＳ３０１−Ｓ３０６を示す。伸長処理ステップＳ３００では、各サーバ装置の伸長モジュール６１８が、まず受信バッファ６１２から情報を取り出し、その先頭の情報からどのカラムに復号を行えば良いかの特定を行う（ステップＳ３０１、Ｓ３０２）。伸長モジュール６１８は、特定したカラムに対し、ランレングス複合化を行い、もとの情報に伸長する（ステップＳ３０３）。ステップＳ３０４では、伸長モジュール６１８は、特定したカラムがｔａｒｇｅｔ頂点か否かの判定を行う。特定したカラムがｔａｒｇｅｔ頂点でない場合は、伸長モジュール６１８は、ｔａｒｇｅｔ頂点をキーとしてソートを行う（ステップＳ３０５）。この際も、ｔａｒｇｅｔ頂点、ｓｏｕｒｃｅ頂点、ｄａｔａの組の対応は保持した形でソートが行われる。このように、受信バッファ６１２に到着した中間データの群の中で、中間データの並びのソートが行われる。特定したカラムがｔａｒｇｅｔ頂点の場合は、送信前に既にソート済みであるためソートは行われず処理が終了する（Ｓ３０６）。【００２６】
ステップＳ１１０では、各サーバ装置は、別のサーバ装置から送信された情報を受信バッファ６１２から取り出してＮｅｘｔキュー６１６へ入れる。各サーバ装置は、受信する情報が無い場合はステップＳ１１０で何もしない。ここには記載しないが、受信すべき情報があるか否かは別途サーバ装置間で通信し合う。その後ステップＳ１１１では、各サーバ装置は、グラフ処理を行っている全サーバ装置でＮｅｘｔキュー６１６が空か否かの判定を行う。グラフ処理を行っている全サーバ装置でＮｅｘｔキュー６１６が空か否かは、サーバ装置のそれぞれが、自身のＮｅｘｔキュー６１６が空になった場合に、他のサーバ装置に自身のＮｅｘｔキュー６１６が空になったことを通知することで、各サーバ装置が判定できる。Ｎｅｘｔキュー６１６が空でない場合は、各サーバ装置は、Ｎｅｘｔキュー６１６から処理キュー６１３へ情報を移動させ（ステップＳ１１２）、各サーバ装置の動作はステップＳ１０３へ戻る。全サーバ装置のＮｅｘｔキュー６１６が空の場合は、全ての頂点に対する処理が完了する（ステップＳ１１３）。【００２７】
ステップＳ２００とステップＳ３００の圧縮・伸長の処理により、受信した情報はｔａｒｇｅｔ頂点をキーとしてソートされた状態で処理キュー６１３へ入れられる。処理キュー６１３への格納順は頂点に対する各サーバ装置の演算順となるため、ｔａｒｇｅｔ頂点順としておくことで、同じｔａｒｇｅｔ頂点に対する処理が連続に行われる。連続に処理が行われることで、中間データがＣＰＵ６００のキャッシュからメモリ装置６１０へリプレースされたり、メモリ装置６１０からストレージ装置６２０へのスワップが発生したりする確率を下げることができる。以降、具体例を用いて圧縮・伸長動作について説明する。【００２８】
図１３は、図５のグラフの各頂点がどのサーバ装置で処理されるかの例を示した図である。この図では頂点１〜１０をグループ７００、頂点１１〜１５をグループ７１０、頂点１６〜２５をグループ７２０に分割している。本実施例では、グループ７００はサーバ装置４２０で、グループ７１０はサーバ装置４３０で、グループ７２０はサーバ装置４４０で処理する場合を考える。【００２９】
図１４は、図１３に対し、頂点３を始点としてグラフ解析を行った場合の頂点間の情報の流れを矢印で示した図である。以下、頂点３を始点としたグラフ解析について処理の流れを説明する。まず、サーバ装置４２０のグラフ演算モジュール６１４が、頂点３をｔａｒｇｅｔ頂点として選択し、（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（３、３、Ｚ）（ｓｏｕｒｃｅおよびｄａｔａはダミーデータ）を処理キュー６１３へ入れる。サーバ装置４２０のグラフ演算モジュール６１４は、処理キュー６１３から（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（３、３、Ｚ）を取り出し、頂点３に対する演算を実行する。サーバ装置４２０のグラフ演算モジュール６１４は、頂点３をｓｏｕｒｃｅ頂点としてグラフ構造データを参照し、次に処理すべきｔａｒｇｅｔ頂点が頂点７、８、９であることを得る。頂点７、８、９は全てグループ７００に属しているため、サーバ装置４２０のグラフ演算モジュール６１４は、自身のＮｅｘｔキュー６１６に（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（７、３、ｃ）、（８、３、ｄ）、（９、３、ｅ）を入れる。送受信される情報は存在しないため、サーバ装置４２０のグラフ演算モジュール６１４は、Ｎｅｘｔキュー６１６の内容を処理キュー６１３へ移動させ、頂点７、８、９について演算を行い、グラフ構造データを参照する。各頂点が所属するグループの分類により、サーバ装置４２０のグラフ演算モジュール６１４は、頂点７ではＮｅｘｔキュー６１６へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（１、７、ａ）、（２、７、ｂ）、送信バッファ６１１へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（１１、７、ｉ）、頂点８では送信バッファ６１１へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（１１、８、ｊ）、頂点９ではＮｅｘｔキュー６１６へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（４、９、ｆ）、送信バッファ６１１へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）＝（１２、９、ｌ）、（１１、９、ｋ）を入れる。サーバ装置４２０の圧縮モジュール６１７は、処理キュー６１３が空になったため、送信バッファ６１１の内容を圧縮して転送を行う。【００３０】
図１５（ａ）に送信バッファ６１１の内容のソート前の状態、図１５（ｂ）に送信バッファ６１１の内容をソート後の状態、図１５（ｃ）に送信バッファ６１１の内容をソートし圧縮した後の状態をそれぞれ示す。送信開始に先立ち、サーバ装置４２０の圧縮モジュール６１７は、（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）の各カラムをソートしてランレングス符号化を行った場合に最も圧縮率の高いものを選択する。ここでは、ｔａｒｇｅｔが頂点１１に対し３個共通、ｓｏｕｒｃｅが頂点９に対し２個共通、ｄａｔａは共通なしであり、ｔａｒｇｅｔをロウ方向に圧縮することが選択される。その後、サーバ装置４２０の圧縮モジュール６１７は、ロウ方向のソートを行い（図１５（ｂ））、ｔａｒｇｅｔに対してランレングス符号化を行う（図１５（ｃ））。図１５（ｃ）では頂点１１が３個共通ということを１１ｘ３と表現しているが、これを例えば、最上位ビットが１となっている数を繰り返し数として表現することができる。ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ、繰り返し数をそれぞれ４バイトの変数で表現した場合、圧縮前のサイズが４８バイトに対し、圧縮後のサイズは４４バイトとなる。さらに転送情報の先頭にｔａｒｇｅｔを圧縮したという情報が１バイト付加され、４５バイトの情報がサーバ装置４３０へ送信される。サーバ装置４３０では、受理した情報の伸長が行われ、伸長されたデータがＮｅｘｔキュー６１６へ入れられる。サーバ装置４２０、４３０では、Ｎｅｘｔキュー６１６から処理キュー６１３へ（ｔａｒｇｅｔ、ｓｏｕｒｃｅ、ｄａｔａ）情報が移動され、別の頂点についても処理が進められる。以後、各頂点に対する上述の処理の繰り返しなので、説明は省略する。【００３１】
なお、各頂点に対する演算は上述のように処理キュー６１３から取り出されたｔａｒｇｅｔ頂点の順に行われるが、同じｔａｒｇｅｔ頂点に対する演算が連続に行われない場合、他のｔａｒｇｅｔ頂点への演算により、中間データがキャッシュからメモリ装置にリプレースされたり、メモリ装置からストレージ装置へのスワップが発生したりすることで処理性能が低下してしまう。そこで、ｓｏｕｒｃｅまたはｄａｔａで圧縮が行われた場合は、受信側で伸長を行った後に、ｔａｒｇｅｔでソートが行われるフローとしている。【００３２】
以上のように、本実施例の転送方法では、グラフ頂点間で転送される中間データの群の中で、中間データの並びのソートが行われることで、効率的な送信データの圧縮が可能となり、効率的なデータ転送を実現でき、ひいてはグラフ処理を高速化できる。さらに、各カラムをロウ方向ソートして圧縮した場合の圧縮率の比較を行うことで、サーバ間で転送される情報の量をさらに効率よく削減することができる。また、カラムのうち、ｓｏｕｒｃｅまたはｄａｔａをキーとしてソートし、圧縮をかけて転送した場合には、受信側で伸長後にｔａｒｇｅｔで再ソートを行うことでメモリ装置やストレージ装置に待避する中間データ量を減らし、グラフ解析をさらに高速に行うことが可能になる。
【符号の説明】
【００３３】
１００：クライアント、２００：インターネット、３００：Ｗｅｂサーバ、４００：Ａｐサーバ、５００：ＤＢサーバ、４１０：ネットワーク装置、４２０〜４５０：サーバ装置、６００：ＣＰＵ、６１０：メモリ装置、６１１：送信バッファ、６１２：受信バッファ、６１３：処理キュー、６１４：グラフ演算モジュール、６１５：頂点割当て情報、６１６：ＮＥＸＴキュー、６１７：圧縮モジュール、６１８：伸長モジュール、６２０：ストレージ装置、６３０：入力装置、６４０：出力装置、６５０：ネットワークインタフェース、６６０：バス
【図１】
2014006735.tif 000003
【図２】
2014006735.tif 000004
【図３】
2014006735.tif 000005
【図４】
2014006735.tif 000006
【図５】
2014006735.tif 000007
【図６】
2014006735.tif 000008
【図７】
2014006735.tif 000009
【図８】
2014006735.tif 000010
【図９】
2014006735.tif 000011
【図１０】
2014006735.tif 000012
【図１１】
2014006735.tif 000013
【図１２】
2014006735.tif 000014
【図１３】
2014006735.tif 000015
【図１４】
2014006735.tif 000016
【図１５（ａ）】
2014006735.tif 000017
【図１５（ｂ）】
2014006735.tif 000018
【図１５（ｃ）】
2014006735.tif 000019
【手続補正書】
【提出日】平成27年8月20日(2015.8.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の計算ノードによるグラフ処理での中間データの転送方法であって、
各計算ノードは送信バッファを有し、
各計算ノードには、処理対象のグラフ頂点が割当てられ、
前記中間データには、送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組が含まれ、
前記中間データを前記送信バッファに蓄積し、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報のいずれかソート後に圧縮率が高くなる情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートし、
前記ソート後に、蓄積された前記中間データの群を圧縮し、
前記中間データの群を転送することを特徴とするグラフ処理の中間データの転送方法。
【請求項２】
請求項１に記載のグラフ処理の中間データの転送方法において、
各計算ノードは受信バッファを有し、
各計算ノードは、
転送された前記中間データの群が前記送信元のグラフ頂点の情報に基づいてソートされている場合には、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートすることを特徴とするグラフ処理の中間データの転送方法。
【請求項３】
請求項１に記載のグラフ処理の中間データの転送方法において、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理の中間データの転送方法。
【請求項４】
複数の計算ノードによるグラフ処理での中間データの転送方法であって、
各計算ノードは送信バッファを有し、
各計算ノードには、処理対象のグラフ頂点が割当てられ、
前記中間データには、送信元のグラフ頂点の情報、送信先のグラフ頂点の情報、および前記送信元のグラフ頂点と前記送信先のグラフ頂点の間の依存関係の情報の組が含まれ、
前記中間データを前記送信バッファに蓄積し、
前記送信元のグラフ頂点の情報、前記送信先のグラフ頂点の情報、または前記依存関係の情報のいずれかソート後に圧縮率が最も高くなる情報に基づいて、蓄積された前記中間データの群の中の前記中間データの並びをソートし、
前記ソート後に、蓄積された前記中間データの群を圧縮し、
前記中間データの群を転送することを特徴とするグラフ処理の中間データの転送方法。
【請求項５】
請求項４に記載のグラフ処理の中間データの転送方法において、
各計算ノードは受信バッファを有し、
各計算ノードは、
転送された前記中間データの群が前記送信元のグラフ頂点の情報または前記依存関係の情報に基づいてソートされている場合には、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートすることを特徴とするグラフ処理の中間データの転送方法。
【請求項６】
請求項４に記載のグラフ処理の中間データの転送方法において、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理の中間データの転送方法。
【請求項７】
複数の計算ノードを有するグラフ処理システムであって、
各計算ノードは、
送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組を有するグラフ処理の中間データを保存する送信バッファと、
前記送信元のグラフ頂点の情報または前記送信先のグラフ頂点の情報のいずれかソート後に圧縮率が高くなる情報に基づいて、前記送信バッファに蓄積された前記中間データの群の中の前記中間データの並びをソートするモジュールと、
前記ソート後に、蓄積された前記中間データの群を圧縮するモジュールと、  前記中間データの群を転送するモジュールとを有することを特徴とするグラフ処理システム。
【請求項８】
請求項７に記載のグラフ処理システムにおいて、
各計算ノードは、
受信バッファと、
前記送信先のグラフ頂点の情報に基づいて、前記受信バッファに到着した前記中間データの群の中の前記中間データの並びをソートするモジュールとを有することを特徴とするグラフ処理システム。
【請求項９】
請求項７に記載のグラフ処理システムにおいて、
前記計算ノードは、サーバ装置であることを特徴とするグラフ処理システム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
本発明は、複数の計算ノードによるグラフ処理での、送信元のグラフ頂点の情報と送信先のグラフ頂点の情報の組を有する中間データの転送を、各計算ノードに中間データを蓄積する送信バッファを設け、送信元のグラフ頂点の情報または送信先のグラフ頂点の情報のいずれかソート後に圧縮率が高くなる情報に基づいて、蓄積された中間データの群の中の中間データの並びをソートし、ソート後に、蓄積された中間データの群を圧縮し、中間データの群を転送することで、前述の課題を解決する。
【国際調査報告】
2014006735.tif 000020
2014006735.tif 000021
2014006735.tif 000022
2014006735.tif 000023
2014006735.tif 000024
2014006735.tif 000025