(57)【要約】  粒度の細かいランダムなアクセスが多く発生させることのない情報処理システム、データ処理方法を提供する。  主記憶部と識別子が付加されたデータを所定の単位で読み書き可能な記憶部とを有した情報処理装置に、データを所定量にまとめて処理させる情報処理システムであって、情報処理装置は、前記識別子を一つ以上まとめたグループに割り振る前処理部と、グループごとに設けられた所定の単位の大きさのバッファを有した主記憶部と、バッファに書き込まれたデータを所定の単位ごとおよびグループごとに記憶する記憶部と、グループごとに、そのグループに割り振られたデータを取得してバッファに書き込み、所定の単位分バッファに書き込んだか否かを判定し、所定の単位分バッファに書き込んだと判定した場合に、そのバッファに書き込まれたデータを記憶部に記憶させる書込み処理部、記憶させたデータをグループごとに主記憶部に読み出し、読み出したデータを取り出して処理を実行する読出処理部と、を備える。
2014196055.tif 000002
【特許請求の範囲】
【請求項１】
主記憶部と識別子が付加されたデータを所定の単位で読み書き可能な記憶部とを有した情報処理装置に、前記データを所定量にまとめて処理させる情報処理システムであって、
情報処理装置は、
前記識別子を一つ以上まとめたグループに割り振る前処理部と、
前記グループごとに設けられた前記所定の単位の大きさのバッファを有した前記主記憶部と、
前記バッファに書き込まれた前記データを前記所定の単位ごとおよび前記グループごとに記憶する前記記憶部と、
前記グループごとに、そのグループに割り振られた前記データを取得して前記バッファに書き込み、前記所定の単位分前記バッファに書き込んだか否かを判定し、前記所定の単位分前記バッファに書き込んだと判定した場合に、そのバッファに書き込まれたデータを前記記憶部に記憶させる書込処理部と、
記憶させた前記データを前記グループごとに前記主記憶部に読み出し、読み出したデータを取り出して前記処理を実行する読出処理部と、
を備えることを特徴とする情報処理システム。
【請求項２】
前記情報処理システムは複数の前記情報処理装置が互いにネットワークを介して接続され、
前記情報処理装置のそれぞれは、
前記データを処理する情報処理装置と前記データとを対応付けて記憶し、
前記読出処理部が前記処理を実行した後のデータを他の情報処理装置に前記ネットワークを介して送信し、
前記他の情報処理装置は、前記処理を実行した後のデータを受信し、受信した前記データを前記バッファに書き込み、前記所定の単位分前記バッファに書き込んだか否かを判定し、前記所定の単位分前記バッファに書き込んだと判定した場合に、そのバッファに書き込まれたデータを前記記憶部に記憶させる書込処理部と、
を備えることを特徴とする請求項１に記載の情報処理システム。
【請求項３】
前記記憶部は、不揮発性メモリから構成される、
ことを特徴とする請求項１または２に記載の情報処理システム。
【請求項４】
前記所定量は、前記不揮発性メモリの最小書き込み単位と同じサイズである、
ことを特徴とする請求項３に記載の情報処理システム。
【請求項５】
前記識別子が付加されているデータはグラフ処理におけるグラフデータであり、前記識別子がグラフの頂点を識別するための頂点ＩＤである、
ことを特徴とする請求項１〜４のいずれか１項に記載の情報処理システム。
【請求項６】
前記識別子が付加されているデータは、さらに前記グラフ処理における頂点間のメッセージデータを含み、前記識別子がグラフの頂点を識別するための頂点ＩＤである、
ことを特徴とする請求項５に記載の情報処理システム。
【請求項７】
主記憶部と識別子が付加されたデータを所定の単位で読み書き可能な記憶部とを有した情報処理装置に、前記データを所定量にまとめて処理させる情報処理システムで行われるデータ処理方法であって、
前記処理の対象となる前記データを前記所定量にまとめたグループに割り振る割り振りステップと、
前記グループごとに、そのグループに割り振られた前記データを取得して前記グループごとに設けられた前記所定の単位の大きさのバッファに書き込む送信書き込みステップと、
前記所定の単位分前記バッファに前記データを書き込んだか否かを判定する送信判定ステップと、
前記所定の単位分前記バッファに前記データを書き込んだと判定した場合に、そのバッファに書き込まれたデータを前記所定の単位ごとおよび前記グループごとに記憶する前記記憶部に記憶させる書込処理ステップと、
記憶させた前記データを前記グループごとに前記主記憶部に読み出し、読み出したデータを取り出して前記処理を実行する読出処理ステップと、
を含むことを特徴とするデータ処理方法。
【請求項８】
前記情報処理システムは複数の前記情報処理装置が互いにネットワークを介して接続され、
前記割り振りステップにおいて、前記データを処理する情報処理装置ごとおよび前記グループごとに前記データを割り振り、
前記読出処理ステップが実行された場合に、
前記処理を実行した後のデータを他の情報処理装置に前記ネットワークを介して送信する送信ステップと、
前記他の情報処理装置が前記処理を実行した後のデータを受信し、受信した前記データを前記バッファに書き込む受信書き込みステップと、
前記所定の単位分前記バッファに書き込んだか否かを判定する受信判定ステップと、
前記所定の単位分前記バッファに書き込んだと判定した場合に、そのバッファに書き込まれたデータを前記記憶部に記憶させる受信記憶ステップと、
をさらに含むことを特徴とする請求項７に記載のデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システムに関し、ストレージ、特に不揮発性メモリへのアクセスの効率化に関する。
【背景技術】
【０００２】
インターネットなどの通信技術の進歩とストレージ技術向上に伴う記録密度増大により、企業や個人が扱うデータ量が大きく増加し、近年はその大規模なデータの繋がり（ネットワークとも呼ばれる）を解析することが重要になってきた。特に、人間関係などの自然界で生じるデータの繋がりにはスケールフリーと呼ばれる特性を有するグラフが多く、このスケールフリー特性を有する大規模グラフの解析が重要になってきた（特許文献１）。【０００３】
グラフとは、図１に示すような頂点と辺から構成され、辺と頂点はそれぞれ値を持つことが出来る。頂点あたりの辺の数を次数とよび、スケールフリー特性を有するグラフでは次数ごとの頂点の存在確率がべき乗分布になる。すなわち、次数１の頂点が最も多く、次数が高くなるにつれて頂点の数が減少する。スケールフリー特性を有するような大規模グラフはその構造が一様な分布とは異なるため、その解析では、科学技術計算などでよく用いられる行列計算とは異なり、データに対して粒度の細かいランダムなアクセスが極めて多く発生する。【０００４】
グラフ解析の代表的な手法として、ＢＳＰ（ＢｕｌｋＳｙｎｃｈｒｏｎｏｕｓＰａｒａｌｌｅｌ）モデルを用いたグラフ処理がある（非特許文献１）。この手法では、各頂点が自らの頂点の値、繋がっている辺の値、辺で繋がっている頂点、頂点に送られてきたメッセージを元に計算を行い、計算結果に応じてメッセージを他頂点に送信する。処理は各頂点の計算1回ごとに同期で区切られており、その区切りスーパーステップという。このスーパーステップを繰り返すことで処理を行う。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−３１８８８４号公報
【非特許文献】
【０００６】
【非特許文献１】GrzegorzMalewicz, Pregel: A System for Large-Scale Graph Processing, PODC’09, August 10-13, 2009, Calgary, Alberta, Canada. ACM978-1-60558-396-9/09/08.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＢＳＰモデルを用いたグラフ処理では、あるスーパーステップで送信されたメッセージは次のスーパーステップで計算に使われるまで保存しておく必要がある。このメッセージとグラフデータ（例えば、図２に示すように、頂点ＩＤと値、辺で繋がる頂点の頂点ＩＤと辺の値のデータとが対応付けられている。）はグラフの規模が大きくなると計算機の主記憶に入りきらなくなってしまう。そこで、メッセージおよびグラフデータを大容量の不揮発性メモリに格納しておき、計算に必要な時に不揮発性メモリから主記憶に読みだすようにする。しかし、不揮発性メモリはブロックデバイスであり、不揮発性メモリの最小アクセス単位（ページサイズ）よりも細粒度のアクセスがあると性能が低下してしまう問題があり、グラフ処理ではそのような粒度の細かいランダムなアクセスが多く発生してしまう。【０００８】
本発明は、上記に鑑みてなされたものであって、粒度の細かいランダムなアクセスが多く発生させることのない情報処理システム、データ処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明にかかる情報処理システムは、主記憶部と識別子が付加されたデータを所定の単位で読み書き可能な記憶部とを有した情報処理装置に、前記データを所定量にまとめて処理させる情報処理システムであって、情報処理装置は、前記識別子を一つ以上まとめたグループに割り振る前処理部と、前記グループごとに設けられた前記所定の単位の大きさのバッファを有した前記主記憶部と、前記バッファに書き込まれた前記データを前記所定の単位ごとおよび前記グループごとに記憶する前記記憶部と、前記グループごとに、そのグループに割り振られた前記データを取得して前記バッファに書き込み、前記所定の単位分前記バッファに書き込んだか否かを判定し、前記所定の単位分前記バッファに書き込んだと判定した場合に、そのバッファに書き込まれたデータを前記記憶部に記憶させる書込処理部、記憶させた前記データを前記グループごとに前記主記憶部に読み出し、読み出したデータを取り出して前記処理を実行する読出処理部と、を備えることを特徴とする。【００１０】
また、本発明は、上記情報処理システムで行われるデータ処理方法である。
【発明の効果】
【００１１】
本発明によれば、粒度の細かいランダムなアクセスが多く発生させることのない情報処理システム、データ処理方法を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】一般的なグラフの構成例を示す図である。
【図２】一般的なグラフデータの構成例を示す図である。
【図３】情報処理システムの物理的な構成例を示す図である。
【図４Ａ】サーバ装置の機能的な構成を示すブロック図である。
【図４Ｂ】本実施例におけるグラフデータの構成例を示す図である。
【図５Ａ】頂点値が不揮発性メモリに書き込まれる場合のイメージ図である。
【図５Ｂ】隣接情報が不揮発性メモリに書き込まれる場合のイメージ図である。
【図６】メッセージが不揮発性メモリに書き込まれる場合のイメージ図である。
【図７】メッセージが不揮発性メモリから読み出される場合のイメージ図である。
【図８】メッセージをソート場合のイメージ図である。
【図９Ａ】ｋｅｙ−ｖａｌｕｅペアの不揮発性メモリへの書き込みの方法の例を示す図である。
【図９Ｂ】ｋｅｙ−ｖａｌｕｅペアのＳｏｒｔフェーズでの不揮発性メモリからの読み出し方法の例を示す図である。
【図１０】本システムで行われるグラフ処理の処理手順を示すフローチャートである。
【図１１】グラフデータＮＶＭ書込処理の処理手順を示すフローチャートである。
【図１２】ＮＶＭ読出処理の処理手順を示すフローチャートである。
【図１３】ソート処理の処理手順を示すフローチャートである。
【図１４】計算／メッセージ送信処理の処理手順を示すフローチャートである。
【図１５】メッセージ受信／ＮＶＭ書込処理の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下に添付図面を参照して、本発明にかかる情報処理システム、データ処理方法の実施の形態を詳細に説明する。なお、以下では、不揮発性メモリのことをＮＶＭ（Non-Volatile  Memory）と省略して記載する場合もある。
【００１４】
図３は、本発明の一実施例である情報処理システム３０１の物理的な構成例を示す図である。図３に示すように、情報処理システム３０１は、サーバ装置３０２−３０５と、共有ストレージ装置３０６が、ネットワーク３０７と、ストレージエリアネットワーク３０８を介してそれぞれ接続されている。以下では、サーバ装置が４台である前提で説明しているが、その台数は問わない。サーバ装置３０２−３０５のそれぞれは、ＣＰＵ３０９と、主記憶３１０と、ローカルストレージ装置である不揮発性メモリ３１１と、ネットワークインターフェース３１２と、ストレージネットワークインターフェース３１３とを有する。本実施例では、主記憶３１０はＤＲＡＭであり、不揮発性メモリ３１１はＮＡＮＤフラッシュメモリである前提で説明しているが、他の様々な記憶媒体に対して適用することができる。不揮発性メモリ３１１はブロックデバイスであり、ブロックサイズより小さい粒度でのランダムアクセスを行う場合は性能が低下する。本実施例では不揮発性メモリ３１１のブロックサイズは８ＫＢである。後述するように、共有ストレージ装置３０６にあらかじめ記憶されているグラフデータをサーバ装置３０２−３０５ごとのグループに分割し、各サーバ装置で振り分けられたグラフデータのグラフ処理を、ＢＳＰモデルにより行う。
【００１５】
図４Ａは、サーバ装置３０２−３０５のそれぞれのサーバ装置、および共有ストレージ装置３０６の機能的な構成を示すブロック図である。図４Ａに示すように、各サーバ装置は、前処理部３０９１と、グラフデータ読出処理部３０９２と、グラフデータ書込処理部３０９３と、メッセージ読出処理部３０９４と、メッセージ書込み処理部３０９５と、通信部３０９６とを有している。
【００１６】
前処理部３０９１は、全ての頂点について、グラフ処理させるサーバ装置を決定し、サーバ装置ごとに頂点をグループ化し、さらに所定量にまとめて計算を行うために複数まとめたサブグループを割り振って定義するとともに、各サブグループ内の頂点についてローカル頂点ＩＤを対応付ける。グラフデータ読出処理部３０９２は、共有ストレージ装置３０６からグラフデータを読み出し、グラフデータの各頂点のデータを前処理部３０９１で決定した処理をさせるサーバ装置へ通信部３０９６を介して送信する。グラフデータ書込み処理部３０９３は、送信されてきたグラフデータを通信部３０９６を介して受信し、グラフデータを不揮発性メモリ３１１に書き込む。
【００１７】
メッセージ読出処理部３０９４は、各サーバ装置に割り振られた頂点（識別子）を対象としたスーパーステップでの処理を実行し、その結果に応じてメッセージを通信部３０９６を介して他頂点に送信する。メッセージ書込処理部３０９５は、他頂点が割り振られた各サーバ装置から送信されたメッセージを通信部３０９６を介して受信し、メッセージを不揮発性メモリ３１１に書き込む。通信部３０９６は、他のサーバ装置との間で、メッセージやグラフデータ等の各種情報の送受信をする。これらの各部が行う具体的な処理については、フローチャートを用いて後述する。
【００１８】
図４Ｂは、グループ化およびサブグループ化したサーバ装置ごとのグラフデータの例を示す図である。図４Ｂに示すように、グラフデータは、メッセージの送信先となる頂点ＩＤとその値（頂点値）と、隣接情報（その頂点と辺で繋がる頂点の頂点ＩＤとその辺の値）とが対応付けて記憶されている。図４Ｂに示す例では、頂点ＩＤが「０」の頂点の頂点値が「Ｖａｌ０」であり、隣接情報に含まれる頂点値およびその頂点と結ばれる辺の値は、（Ｖ０−０、Ｅ０−０）、（Ｖ０−１、Ｅ０−１）…、であることわかる。また、これらの頂点は、サーバ装置ごとにグループ化され、どの頂点がどのグループに属するかが分かるようになっている。例えば、頂点ＩＤが「０」〜「３」の頂点は、サーバ装置３０２でグラフ処理されることを示している。さらに、各頂点は、計算を行うためにサブグループ化され、例えば、頂点ＩＤが「０」、「１」で示される頂点は、サブグループ１に属することを示している。そして、このサブグループ１に属する頂点には、そのサブグループ内で頂点を識別するためのＩＤとしてローカル頂点ＩＤが定められている。例えば、頂点ＩＤが「０」、「１」である頂点は、サブグループ１に属し、ローカル頂点ＩＤが「０」、「１」であることを示している。また、頂点ＩＤが「２」、「３」である頂点は、サブグループ２に属し、ローカル頂点ＩＤが「０」、「１」であることを示している。なお、メッセージは、頂点ＩＤに対応付けて送受信される。
【００１９】
図１０は、本システムで行われるグラフ処理の処理手順を示すフローチャートである。図１０に示すように、グラフ処理では、まず前処理部３０９１がグラフ処理の対象となる全てのグラフデータを、図４Ｂに示したように、サーバ装置の数で複数のグループに分割し、それぞれのサーバ装置３０２−３０５がどの頂点の計算を行うかを決定する。このとき、グループ化したサーバ装置ごとのグラフデータを、さらに所定量にまとめて計算を行うために複数まとめたグループ（サブグループ）を定義する。サブグループの定義方法としては、サブグループに含まれる頂点の数が、サブグループに含まれる頂点のグラフデータとサブグループに含まれる頂点を宛先とするメッセージの量が不揮発性メモリ３１１の最小アクセス単位であるページサイズ（所定の単位）よりも十分大きくかつ主記憶３１０の容量よりも小さくなるようにする。各サブグループ内の頂点には０から始まる連番のローカルな頂点のＩＤ（ローカル頂点ＩＤ）を付けておく。（ステップＳ１００１）そして、グラフデータ読出処理部３０９２が、共有ストレージ装置３０６からグラフデータを読み出して、グラフデータの各頂点のデータをその頂点の計算を行うサーバ装置に送信する（ステップＳ１００２）。 
そして、グラフデータ書込み処理部３０９３は、そのグラフデータを受信すると、グラフデータＮＶＭ書込処理を実行する（ステップＳ１００３）。図１１は、グラフデータＮＶＭ書込処理の処理手順を示すフローチャートである。図１１に示すように、各サーバ装置のメッセージ送信処理部３０９１は、まず、図５Ａおよび図５Ｂに示す頂点値と隣接情報用のそれぞれのデータ開始位置テーブル（頂点値データ開始位置テーブル、隣接情報データ開始位置テーブル）、それぞれのグループ数のエントリを持ったデータアドレステーブル（頂点値データアドレステーブル、隣接情報データアドレステーブル）を生成し、データアドレステーブルの各エントリのアドレスリストを空に初期化する（ステップＳ１１０１）。
【００２０】
例えば、図５Ａおよび図５Ｂに示すように、グラフデータ書込み処理部３０９３は、ローカル頂点ＩＤとそのローカル頂点ＩＤの頂点値の書き込み開始位置であるデータ位置とを対応付けた頂点値データ開始位置テーブル４０４１を生成する。また、グラフデータ書込み処理部３０９３は、頂点ＩＤとその頂点ＩＤの頂点値の書き込み開始位置であるデータ位置とを対応付けた隣接情報データ開始位置テーブル４０４２を生成する。さらに、グラフデータ書込み処理部３０９３は、後述する頂点値不揮発性メモリ書込みバッファ４０２１がいっぱいになったときに、頂点値不揮発性メモリ書込みバッファ４０２１のデータが不揮発性メモリ４０５に書込まれたアドレスを示す頂点値データアドレステーブル４０６１を生成する。同様に、グラフデータ書込み処理部３０９３は、後述する隣接情報不揮発性メモリ書込みバッファ４０２２がいっぱいになったときに、隣接情報不揮発性メモリ書込みバッファ４０２２のデータが不揮発性メモリ４０５に書込まれたアドレスを示す隣接情報データアドレステーブル４０６２を生成する。
【００２１】
さらに、各サーバ装置のグラフデータ書込み処理部３０９３は、頂点値と隣接情報用のそれぞれの不揮発性メモリ書込バッファ（頂点値不揮発性メモリ書込バッファ、隣接情報不揮発性メモリ書込バッファ）、それぞれの書込データ量カウンタ（頂点値書込データ量カウンタ、隣接情報書込データ量カウンタ）を生成し、各書込データ量カウンタはゼロで初期化する（ステップＳ１１０２）。
【００２２】
例えば、図５Ａおよび図５Ｂに示すように、グラフデータ書込み処理部３０９３は、ページサイズの大きさで主記憶３１０と不揮発性メモリ４０５との間で頂点値をまとめたデータを読み書きを行うための頂点値不揮発性メモリ書込バッファ４０２１をサブグループの数だけ生成する。また、グラフデータ書込み処理部３０９３は、同様に、ページサイズの大きさで主記憶３１０と不揮発性メモリ４０５との間で隣接情報の頂点値をまとめたデータを読み書きを行うための隣接情報不揮発性メモリ書込バッファ４０２２をサブグループの数だけ生成する。
【００２３】
また、グラフデータ書込み処理部３０９３は、書き込んだデータ量だけカウントアップさせるためのサブグループ数分の頂点値書込データ量カウンタ４０３１を生成する。同様に、グラフデータ書込み処理部３０９３は、書き込んだデータ量だけカウントアップさせるためのサブグループ数分の隣接情報書込データ量カウンタ４０３２を生成する。
【００２４】
その後、各サーバ装置のグラフデータ書込み処理部３０９３は、送信されてきたグラフデータから１頂点分の頂点ＩＤ、頂点値、隣接情報を受信し（ステップＳ１１０３）、その頂点ＩＤから、読み出した１頂点分の頂点ＩＤ、頂点値、隣接情報が属するサブグループのグループＩＤを計算する（ステップＳ１１０４）。
【００２５】
各サーバ装置のグラフデータ書込み処理部３０９３は、頂点データ開始位置テーブル４０４１に頂点ＩＤのエントリを追加し、計算したサブグループＩＤの頂点書込データ量カウンタ４０３１の値を書込み（ステップＳ１１０５）、その計算したサブグループＩＤの頂点値不揮発性メモリ書込バッファ４０３１に書き込む（ステップＳ１１０６）。図５Ａでは、例えば、グラフデータ書込み処理部３０９３は、頂点値を頂点値不揮発性メモリ書込バッファ４０２１に書き込む際に、頂点値データ開始位置テーブル４０４１に、頂点ＩＤ「Ｖ」と、その書き込み開始位置であるデータ位置（すなわち、頂点値書込みデータ量カウンタ４０３１のカウント値）「Ｃ」とを対応付けて記憶させる。なお、上述したカウント値「Ｃ」は、サブグループが同じ「２」に属するひとつ前の頂点の書き込みの際に、頂点値書込みデータ量カウンタ４０３１がＣまでカウントアップされていたことを示している。
【００２６】
そして、各サーバ装置のグラフデータ書込み処理部３０９３は、頂点値不揮発性メモリ書込バッファ４０２１が一杯になったか否かを判定し（ステップＳ１１０７）、頂点値不揮発性メモリ書込バッファ４０２１が一杯になったと判定した場合（ステップＳ１１０７；Ｙｅｓ）、その時点の頂点値不揮発性メモリ書込バッファ４０２１のデータを不揮発性メモリ４０５に書き出し、書き込んだ不揮発性メモリ４０５のアドレスを、頂点値データアドレステーブル４０６１のそのサブグループＩＤのエントリに追加する（ステップＳ１１０８）。一方、各サーバ装置のグラフデータ書込み処理部３０９３は、頂点値ＮＶＭ書込バッファが一杯になっていないと判定した場合（ステップＳ１１０７；Ｎｏ）、不揮発性メモリ４０５には書込みを行わず、頂点値ＮＶＭ書込みバッファに頂点値を書き込んだ後に、ステップＳ１１１１に進む。図５Ａでは、例えば、グラフデータ書込み処理部３０９３は、頂点値不揮発性メモリ書込バッファ４０２１がいっぱいになったときに、頂点値不揮発性メモリ書込バッファ４０２１のデータを不揮発性メモリ４０５に書込み、そのアドレスであるアドレスＡを計算したローカル頂点ＩＤのエントリに記憶させる。
【００２７】
その後、各サーバ装置のグラフデータ書込み処理部３０９３は、そのサブグループＩＤの頂点値不揮発性メモリ書込バッファ４０２１をクリアし（ステップＳ１１０９）、さらにその残りをそのサブグループＩＤの頂点値ＮＶＭ書込バッファに書き込み（ステップＳ１１１０）、そのサブグループＩＤの頂点値書込データ量カウンタの値を、頂点値のデータサイズ分だけ加算する（ステップＳ１１１１）。
【００２８】
各サーバ装置のグラフデータ書込み処理部３０９３は、隣接情報についてもステップＳ１１０５〜Ｓ１１１１までの処理と同様の処理を実行する。具体的には、各サーバ装置のグラフデータ書込み処理部３０９３３０９１は、頂点データ開始位置テーブル４０４１に頂点ＩＤのエントリを追加し、計算したサブグループＩＤの頂点書込データ量カウンタ４０３１の値を書込み（ステップＳ１１１２）、その計算したサブグループＩＤの隣接情報不揮発性メモリ書込バッファ４０２２に書き込む（ステップＳ１１１３）。図５Ｂでは、例えば、グラフデータ書込み処理部３０９３は、隣接情報を隣接情報不揮発性メモリ書込バッファ４０２２に書き込む際に、隣接情報データ開始位置テーブル４０４２に、頂点ＩＤ「Ｗ」と、その書き込み開始位置であるデータ位置（すなわち、隣接情報書込みデータ量カウンタ４０３２のカウント値）「Ｄ」とを対応付けて記憶させ、なお、上述したカウント値「Ｄ」は、サブグループが同じ「２」に属するひとつ前の頂点の書き込みの際に、隣接情報書込データ量カウンタ４０３２がＤまでカウントアップされていたことを示している。
【００２９】
そして、各サーバ装置のグラフデータ書込み処理部３０９３は、隣接情報不揮発性メモリ書込バッファ４０２２が一杯になったか否かを判定し（ステップＳ１１１４）、隣接情報不揮発性メモリ書込バッファ４０２２が一杯になったと判定した場合（ステップＳ１１１４；Ｙｅｓ）、その時点の隣接情報不揮発性メモリ書込バッファ４０２２のデータを不揮発性メモリ４０５に書き出し、書き込んだ不揮発性メモリ４０５のアドレスを、隣接情報データアドレステーブル４０６２のそのサブグループＩＤのエントリに追加する（ステップＳ１１１５）。一方、各サーバ装置のグラフデータ書込み処理部３０９３は、隣接情報不揮発性メモリ書込バッファ４０２２が一杯になっていないと判定した場合（ステップＳ１１１４；Ｎｏ）、ステップＳ１１１８に進む。
【００３０】
その後、各サーバ装置のグラフデータ書込み処理部３０９３は、そのサブグループＩＤの隣接情報不揮発性メモリ書込バッファ４０２２をクリアし（ステップＳ１１１６）、さらにその残りをそのサブグループＩＤの隣接情報不揮発性メモリ書込バッファ４０２２に書き込み（ステップＳ１１１７）、そのサブグループＩＤの隣接情報書込データ量カウンタ４０３３の値を、頂点値のデータサイズ分だけ加算する（ステップＳ１１１８）。なお、図１１に示すように、ステップＳ１１０５〜Ｓ１１１１までの処理およびステップＳ１１０５〜Ｓ１１１１までの処理は並行に実行することが可能である。
【００３１】
各サーバ装置のグラフデータ書込み処理部３０９３は、各サーバ装置に割り当てられた全頂点分のグラフデータの受信が完了したか否かを判定し（ステップＳ１１１９）、各サーバ装置に割り当てられた全頂点分のグラフデータの受信が完了していないと判定した場合（ステップＳ１１１９；Ｎｏ）、ステップＳ１１０３に戻って以降の処理を繰り返す。
【００３２】
一方、各サーバ装置のグラフデータ書込み処理部３０９３は、各サーバ装置に割り当てられた全頂点分のグラフデータの読み出しが完了したと判定した場合（ステップＳ１１１９；Ｙｅｓ）、各サーバ装置の全サブグループについて以下の処理を実行する（ステップＳ１１２０、Ｓ１１２３）。
【００３３】
各サーバ装置のグラフデータ書込み処理部３０９３は、頂点値データ開始位置テーブル４０４１に含まれる頂点ＩＤのエントリをサブグループごとにまとめたサブグループ頂点値データ開始位置テーブル４０５１を生成する（ステップＳ１１２１）。そして、各サーバ装置のグラフデータ書込み処理部３０９３は、そのサブグループ頂点値開始位置テーブル４０５１を不揮発性メモリ４０５に書き込み、各サブグループＩＤのサブグループ頂点値データ開始位置テーブル４０５１を書き込んだアドレスを、頂点値データアドレステーブルのサブグループＩＤのエントリに追加する（ステップＳ１１２２）。図５Ａでは、例えば、グラフデータ書込み処理部３０９３は、頂点値データ開始位置テーブル４０４１の頂点ＩＤをキーとして図４Ｂに示したグラフデータを参照し、その頂点ＩＤが属するサブグループごとに頂点値データ開始位置テーブル４０４１をサブグループで分割し、そのサブグループＩＤとそのサブグループに属する頂点ＩＤとそのデータ位置とを対応付けてサブグループ毎にまとめたサブグループ頂点値データ開始位置テーブル４０５１を生成する。図５Ａに示すように、サブグループ頂点値データ開始位置テーブル４０５１は、サブグループＩＤとそのサブグループの属する頂点の頂点ＩＤとそのデータ位置が対応付けて記憶され、例えば、サブグループＩＤ「２」のサブグループ頂点値データ開始位置テーブル４０５１には、頂点ＩＤ「Ｖ」とそのデータ位置「Ｃ」をはじめとするサブグループＩＤ「２」に属する複数の頂点のデータ位置が記憶されている。また、グラフデータ書込み処理部３０９３は、生成したサブグループ頂点値開始位置テーブル４０５１を不揮発性メモリ４０５に書き込んだときの各サブグループＩＤのアドレスを頂点値データアドレステーブル４０６１のサブグループＩＤのアドレスリストに追加する。図５Ａに示す例では、不揮発性メモリ４０５のアドレス「Ｘ」がサブグループＩＤ「２」のサブグループ頂点値データ開始位置テーブル５０４１のアドレスとして記憶されていることを示している。
【００３４】
また、各サーバ装置のグラフデータ書込み処理部３０９３は、頂点値の場合と同様に、隣接情報に含まれる頂点値についてもステップＳ１１２０〜Ｓ１１２３までの処理と同様の処理を実行する（ステップＳ１１２４、Ｓ１１２７）。具体的には、各サーバ装置のメッセージ送信処理部３０９１は、隣接情報データ開始位置テーブルに含まれる頂点ＩＤのエントリをサブグループごとにまとめたサブグループ隣接情報開始位置テーブル４０５２を生成する（ステップＳ１１２５）。そして、各サーバ装置のグラフデータ書込み処理部３０９３は、そのサブグループ隣接情報開始位置テーブルをＮＶＭに書き込み、各サブグループＩＤのサブグループ隣接情報データ開始位置テーブル４０５２を書き込んだアドレスを、隣接情報データアドレステーブル４０５２のサブグループＩＤのエントリに追加する（ステップＳ１１２６）。ステップＳ１１２３およびＳ１１２７の処理が終了すると、図１１に示したグラフデータＮＶＭ書込処理が終了する。図５Ｂでは、例えば、グラフデータ書込み処理部３０９３は、隣接情報データ開始位置テーブル４０４２の頂点ＩＤをキーとして図４Ｂに示したグラフデータを参照し、その頂点ＩＤが属するサブグループごとに隣接情報データ開始位置テーブル４０４２をサブグループで分割し、そのサブグループＩＤとそのサブグループに属する頂点ＩＤとそのデータ位置とを対応付けてサブグループ毎にまとめたサブグループ隣接情報データ開始位置テーブル４０５２を生成する。図５Ｂに示すように、サブグループ隣接情報データ開始位置テーブル４０５２は、サブグループＩＤとそのサブグループの属する頂点の頂点ＩＤとそのデータ位置が対応付けて記憶され、例えば、サブグループＩＤ「２」のサブグループ隣接情報データ開始位置テーブル４０５２には、頂点ＩＤ「Ｗ」とそのデータ位置「Ｄ」をはじめとするサブグループＩＤ「２」に属する複数の頂点のデータ位置が記憶されている。また、グラフデータ書込み処理部３０９３は、生成したサブグループ隣接情報開始位置テーブル４０５２を不揮発性メモリ４０５に書き込んだときの各サブグループＩＤのアドレスを隣接情報データアドレステーブル４０６２のサブグループＩＤのアドレスリストに追加する。図５Ｂに示す例では、不揮発性メモリ４０５のアドレス「Ｙ」がサブグループＩＤ「２」のサブグループ隣接情報データ開始位置テーブル４０５２のアドレスとして記憶されていることを示している。
【００３５】
図１０に示したグラフ処理においてステップＳ１００３の処理が終了すると、各サーバ装置の全サブグループについて、ステップＳ１００５〜Ｓ１００８の各処理を実行するとともに（ステップＳ１００４、Ｓ１００９）、ステップＳ１０１２の処理を実行する。ステップＳ１００４、Ｓ１００９の処理は各サーバ装置が不揮発性メモリから読出しを行って計算をしメッセージを送信する場合の処理であり、ステップＳ１０１２の処理は各サーバ装置がメッセージを受信して不揮発性メモリに書込みをする場合の処理である。
【００３６】
まず、各サーバ装置のメッセージ読出処理部３０９４は、ステップＳ１００５の不揮発性メモリ読出処理を実行する。図１２は、不揮発性メモリ読出処理の処理手順を示すフローチャートである。メッセージ読出処理部３０９４は、頂点値データアドレステーブル４０６１からサブグループＩＤのアドレスリストを見て、頂点値とサブグループ頂点値データ開始位置テーブル４０５１を不揮発性メモリ４０５から主記憶３１０に読み出す（ステップＳ１２０１）。
【００３７】
続いて、各サーバ装置のメッセージ読出処理部３０９４は、隣接情報データアドレステーブルからサブグループＩＤのアドレスリストを見て、隣接情報とサブグループ隣接情報データ開始位置テーブル４０５２を不揮発性メモリ４０５から主記憶３１０に読み出す（ステップＳ１２０２）。
【００３８】
各サーバ装置のメッセージ読出処理部３０９４は、前のスーパーステップで処理したメッセージの不揮発性メモリ４０５への書込みに使用した前スーパーステップメッセージデータアドレステーブル５０５からサブグループＩＤのアドレスリストのメッセージを主記憶３１０に読み出す（ステップＳ１２０３）。後述するように、サブグループ内のメッセージとローカル頂点ＩＤとは対応付けてメッセージ不揮発性メモリ書込みバッファ５０２１および不揮発性メモリ４０５に記憶されているため、不揮発性メモリ４０５からメッセージを読み出す際にはそのメッセージに対応するローカル頂点ＩＤがわかる。
【００３９】
なお、現スーパーステップメッセージデータアドレステーブル５０４は、あるスーパーステップで受信したメッセージは次のスーパーステップで計算に使われるため、メッセージを受信したスーパーステップでメッセージを書き込んだアドレスを記録しておくものであるが、前スーパーステップメッセージデータアドレステーブル５０５は、計算のための読出しに使われる前のスーパーステップ（すなわち直前のスーパーステップ）で受信してメッセージを書き込んだアドレスを記憶させておくためのものである。メッセージ読出処理部３０９４は、スーパーステップが切り替わるたびに、前スーパーステップメッセージデータアドレステーブル５０５の内容をクリアしてから、現スーパーステップメッセージデータアドレステーブル５０４と前ステップメッセージデータアドレステーブル５０５を入れ替える。このステップＳ１２０３の処理が終了すると、図１０におけるステップＳ１００５の処理が終了する。
【００４０】
図１０に示したグラフ処理においてステップＳ１００５の処理が終了すると、各サーバ装置は、ステップＳ１００６のソート処理を実行する。ソート処理を行う理由は、メッセージ読出処理部３０９４は、サブグループ単位で頂点値や隣接情報、メッセージを不揮発性メモリ４０５から読み出すが、メッセージ以外のデータ（頂点値、隣接情報）については、図５Ａおよび図５Ｂに示したように、各データ開始位置テーブルや各サブグループデータ開始位置テーブルによって各頂点のデータがサブグループ単位で読み出したデータ中のどの位置にあるかを知ることができる一方、メッセージの場合にはサブグループ内の各頂点宛のメッセージがばらばらに整列されずに書き込まれている。
【００４１】
例えば、図７に示すように、メッセージ読出処理部３０９４は、全スーパーステップメッセージデータアドレスリスト５０５に記憶されているサブグループＩＤに対応するアドレスリストを参照して、不揮発性メモリ４０５からそのアドレスのメッセージを主記憶３１０の領域６０３に読み出す。このとき、サブグループ内の各頂点宛のメッセージは整列されずに書き込まれているため、そのまま取り出しただけでは必ずしも正しい順序となっていない。このため、計算処理を始める前に頂点宛ごとにメッセージをソートして整列する必要がある。図７では、サブグループ「２」に対応するアドレスリストに「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」、「Ｅ」の各アドレスが記憶され、それぞれのアドレスから読み出してきたデータの中には、各頂点宛のメッセージが複数個ずつ整列されずに入っている。
【００４２】
図１３は、ソート処理の処理手順を示すフローチャートである。図１３に示すように、各サーバ装置のメッセージ読出処理部３０９４は、サブグループごとのローカル頂点ＩＤへのメッセージをカウントするためのメッセージカウントテーブル７０２を生成し、メッセージ数をゼロに初期化する（ステップＳ１３０１）。メッセージカウントテーブル７０２は、不揮発性メモリ４０５からサブグループのメッセージを読み出した主記憶３１０の領域６０３に含まれるメッセージの数を、ローカル頂点ＩＤごとにカウントするためのテーブルである。例えば、図８に示すように、メッセージカウントテーブル７０２には、ローカル頂点ＩＤとそのローカル頂点ＩＤに対応するメッセージの数とが対応付けて記憶され、例えば、ローカル頂点ＩＤ「２」へのメッセージ数が「Ｃ」個であることを示している。
【００４３】
各サーバ装置のメッセージ読出処理部３０９４は、不揮発性メモリ４０５から主記憶３１０に読み出したサブグループＩＤの全メッセージデータについて、ステップＳ１３０３の処理を行う（ステップＳ１３０２、Ｓ１３０４）。ステップＳ１３０３では、各サーバ装置のメッセージ読出処理部３０９４は、生成したメッセージカウントテーブル７０２のローカル頂点ＩＤへのメッセージ数をカウントアップする（ステップＳ１３０３）。
【００４４】
ローカル頂点ＩＤごとのメッセージ数がカウントアップされると、各サーバ装置のメッメッセージ読出処理部３０９４は、メッセージ書込インデックステーブル７０３を生成し、ローカル頂点ＩＤがｎの書込インデックスは、ｎが０である場合には０に初期化し、ｎが１以上である場合には、ステップＳ１３０１で生成したメッセージカウントテーブルのローカル頂点ＩＤが０からｎまでのメッセージ数の和に初期化する（ステップＳ１３０５）。
メッセージ書込インデックステーブル７０３は、主記憶３１０におけるローカル頂点ＩＤごとのメッセージの書込み位置を定めるためのテーブルであり、初期値はサブグループのメッセージをローカル頂点ＩＤでソートしたときの各ローカル頂点ＩＤの開始位置を示している。
【００４５】
その後、各サーバ装置のメッセージ読出処理部３０９４は、メッセージデータをサブグループ毎にローカル頂点ＩＤでソートするためのソート済みメッセージ領域７０４をサブグループの全メッセージ分生成し（ステップＳ１３０６）、不揮発性メモリ４０５から主記憶３１０に読み出したサブグループＩＤの全メッセージデータについて、ステップＳ１３０８〜Ｓ１３０９の処理を行う（ステップＳ１３０７、Ｓ１３１０）。
【００４６】
各サーバ装置のメッセージ読出処理部３０９４は、生成したソート済みメッセージ領域７０４の中で、メッセージ書込みインデックステーブル７０３でローカル頂点ＩＤに対応する書込みインデックスの位置に、メッセージを書き込み(ステップＳ１３０８)、メッセージ書込インデックステーブル７０３でローカル頂点ＩＤに対応する書込みインデックスをカウントアップする（ステップＳ１３０９）。例えば、図８に示すように、ローカル頂点ＩＤ「２」のメッセージは、ローカル頂点「０」と「１」のメッセージの数が「Ａ」と「Ｂ」のため、ソートしたときに「Ａ＋Ｂ」の位置から始まるので、書込みインデックスの初期値は「Ａ＋Ｂ」である。ローカル頂点ＩＤ「２」のメッセージを最初に書くときは、ソート済みメッセージ領域７０４の書込みインデックスの「Ａ＋Ｂ」の位置に書込み、書込みインデックスを「Ａ＋Ｂ＋１」にカウントアップする。次にローカルＩＤ「２」のメッセージを書くときは「Ａ＋Ｂ＋１」の位置に書き込まれる。最後に、各サーバ装置のメッセージ読出処理部３０９４は、カウントアップしたメッセージ書込インデックステーブル７０３を再初期化する（ステップＳ１３１１）。ステップＳ１３１１の処理が終了すると、図１０におけるソート処理が終了する。
【００４７】
図１０に示したグラフ処理においてステップＳ１００６の処理が終了すると、各サーバ装置のメッセージ読出処理部３０９４は、計算／メッセージ送信処理を実行する（ステップＳ１００７）。図１４は、計算／メッセージ送信処理の処理手順を示すフローチャートである。図１４に示すように、各サーバ装置のＣＰＵ３０９は、サブグループＩＤの全頂点について、ステップＳ１４０２〜Ｓ１４０９までの処理を行う（ステップＳ１４０１、Ｓ１４１０）。
【００４８】
そして、各サーバ装置のメッセージ読出処理部３０９４は、頂点ＩＤをキーとして、頂点値データ開始位置テーブル４０４１を参照して頂点値を取り出し（ステップＳ１４０２）、同様に、頂点ＩＤをキーとして、隣接情報データ開始位置テーブル４０４２を参照して隣接情報を取り出し（ステップＳ１４０３）、頂点ＩＤからローカル頂点ＩＤを計算して、計算したローカル頂点ＩＤをキーとして図１３のソート処理でローカル頂点ＩＤ毎に並べ替えたソート済みメッセージとメッセージ書込みインデックステーブルとを参照し、頂点宛のメッセージを取り出す（ステップＳ１４０４）。
【００４９】
各サーバ装置のメッセージ読出処理部３０９４は、取出した頂点値と隣接情報とメッセージを用いて、例えば、非特許文献１に記載された手法によりグラフ処理計算を行い（ステップＳ１４０５）、頂点宛のメッセージがあるか否かを判定し（ステップＳ１４０６）、メッセージがあると判定した場合（ステップＳ１４０６；Ｙｅｓ）、宛先の頂点ＩＤから送信先のサーバ装置を計算し（ステップＳ１４０７）、メッセージにその宛先頂点ＩＤを付加して送信先のサーバ装置に送信する（ステップＳ１４０８）。なお、メッセージ読出処理部３０９４は、頂点ＩＤからサーバ装置やローカル頂点ＩＤの計算を行う際には、図４Ｂに示した頂点ＩＤとサーバ装置とローカル頂点ＩＤとの対応関係により計算する。
【００５０】
一方、各サーバ装置のメッセージ読出処理部３０９４は、頂点宛のメッセージがないと判定した場合（ステップＳ１４０６；Ｎｏ）、グラフ処理計算で更新された頂点値を、ステップＳ１２０１で不揮発性メモリ４０５から主記憶３１０に読み出した頂点値に反映する(ステップＳ１４０９)。このステップＳ１４０９の処理が終了すると、図１０におけるステップＳ１００７の処理が終了する。
【００５１】
そして、各サーバ装置のメッセージ読出処理部３０９４は、ステップＳ１２０１で不揮発性メモリ４０５から主記憶３１０に読み出した頂点値を不揮発性メモリ４０５に書き戻し（ステップＳ１００８）、１つのスーパーステップにおける処理が終了したことを全サーバ装置３０２−３０５に通知する（ステップＳ１０１０）。サーバ装置３０２−３０５のＣＰＵ３０９は、その通知を全サーバ装置３０２−３０５から受けると、前スーパーステップメッセージデータアドレステーブル５０５の内容をクリアしてから、現スーパーステップメッセージデータアドレステーブル５０４と前ステップメッセージデータアドレステーブル５０５を入れ替え、全てのスーパーステップが終了したことによってグラフ処理が終了したか否かを判定し（ステップＳ１０１１）、グラフ処理が終了したと判定した場合（ステップＳ１０１１；Ｙｅｓ）、そのまま処理を終了させる。一方、グラフ処理が終了していないと判定した場合（ステップＳ１０１１；Ｎｏ）、ステップＳ１００４に戻って、以降の処理を繰り返す。
【００５２】
一方、ステップＳ１００３の処理が終了すると、各サーバ装置のメッセージ書込処理部３０９５は、ステップＳ１０１２の処理（メッセージ受信／ＮＶＭ書込処理）もあわせて実行する。図１５は、メッセージ受信／ＮＶＭ書込処理の処理手順を示すフローチャートである。図１５に示すように、各サーバ装置のメッセージ書込処理部３０９５は、まず、メッセージ書込み用のデータアドレステーブル（現スーパーステップメッセージデータアドレステーブル５０４）とメッセージ読出し用のデータアドレステーブル（前スーパーステップメッセージデータアドレステーブル５０５）を生成し、そのテーブルに含まれるアドレスリストを空に初期化する（ステップＳ１５０１）。
【００５３】
さらに、各サーバ装置のメッセージ書込処理部３０９５は、メッセージ用の不揮発性メモリ書込バッファ（メッセージ不揮発性メモリ書込みバッファ５０２１）をサブグループの数分生成し（ステップＳ１５０２）、宛先頂点ＩＤとメッセージを一組受信をする（ステップＳ１５０３）。各サーバ装置のメッセージ書込処理部３０９５は、図４Ｂに示した頂点ＩＤとサーバ装置とローカル頂点ＩＤとの対応関係により、宛先頂点ＩＤからサブグループＩＤとローカル頂点ＩＤを計算し（ステップＳ１５０４）、ローカル頂点ＩＤとメッセージとをそのサブグループＩＤのメッセージ不揮発性メモリ書込バッファ５０２１に書き込む（ステップＳ１５０５）。例えば、図６に示すように、メッセージ書込処理部３０９５、ページサイズの大きさのメッセージ不揮発性メモリ書込みバッファ５０２１をサブグループの数だけ生成する。そして、メッセージ書込処理部３０９５は、メッセージ５０１とその宛先頂点ＩＤを受信し、宛先頂点ＩＤからサブグループＩＤとローカル頂点ＩＤを計算し、メッセージ５０１にローカル頂点ＩＤを付加して、宛先頂点ＩＤが属するサブグループＩＤのメッセージ不揮発性メモリ書込みバッファ５０２１に書き込む。図６では、例えば、あるメッセージとローカル頂点ＩＤの組５０１１は、サブグループ２（サブＧｒ．２）のメッセージ不揮発性メモリ書込バッファ５０２１に書き込まれることを示している。
【００５４】
各サーバ装置のメッセージ書込処理部３０９５は、そのサブグループＩＤのメッセージ不揮発性メモリ書込バッファ５０２１が一杯になったか否かを判定し（ステップＳ１５０６）、そのサブグループＩＤのメッセージ不揮発性メモリ書込バッファ５０２１が一杯になったと判定した場合（ステップＳ１５０６；Ｙｅｓ）、その時点のメッセージ不揮発性メモリ書込バッファ５０２１を不揮発性メモリ４０５に書き出し、書き込んだ不揮発性メモリ４０５のアドレスを、現スーパーステップメッセージデータアドレステーブル５０４に含まれるそのサブグループＩＤのエントリに追加する（ステップＳ１５０７）。一方、各サーバ装置のＣＰＵ３０９は、頂点値ＮＶＭ書込バッファが一杯になっていないと判定した場合（ステップＳ１５０６；Ｎｏ）、ステップＳ１５１０に進む。例えば、図６では、現スーパーステップメッセージデータアドレステーブル５０４には、サブグループＩＤと、不揮発性メモリ４０５に書き込まれたアドレスを示すアドレスリストとが対応付けて記憶され、サブグループＩＤが「２」のアドレスリストには、不揮発性メモリ４０５における書込み位置「Ｗ」をはじめとする複数の書込み位置が記憶されている。
【００５５】
その後、各サーバ装置のメッセージ書込処理部３０９５は、そのサブグループＩＤのメッセージ不揮発性メモリ書込バッファ５０２１をクリアし（ステップＳ１５０８）、さらにその残りをそのサブグループＩＤのメッセージ不揮発性メモリ書込バッファ５０２１に書き込む（ステップＳ１５０９）。そして、各サーバ装置のメッセージ書込処理部３０９５は、全サーバ装置でスーパーステップでの処理が終了したか否かを判定し（ステップＳ１５１０）、全サーバ装置でスーパーステップでの処理が終了していないと判定した場合（ステップＳ１５１０；Ｎｏ）、ステップＳ１５０３に戻って、以降の処理を繰り返す。一方、各サーバ装置のメッセージ書込処理部３０９５は、全サーバ装置でスーパーステップでの処理が終了したと判定した場合（ステップＳ１５１０；Ｙｅｓ）、図１５に示したメッセージ受信／ＮＶＭ書込処理を終了させる。
【００５６】
各サーバ装置のメッセージ書込処理部３０９５は、図１０のステップＳ１０１２の処理が終了すると、グラフ処理が終了したか否かを判定し（ステップＳ１０１３）、グラフ処理が終了していないと判定した場合（ステップＳ１０１３；Ｎｏ）、グラフ処理が終了するまで、ステップＳ１０１２の処理を繰り返す一方、グラフ処理が終了したと判定した場合（ステップＳ１０１３；Ｙｅｓ）、図１０に示したグラフ処理を終了させる。
【００５７】
以上のようにＢＳＰモデルを用いたグラフ処理を行うことで、不揮発性メモリにグラフデータとメッセージを格納しながら、不揮発性メモリへのアクセスを全てページサイズで行うことができ、粒度の細かいランダムなアクセスが多く発生させることなく不揮発性メモリへのアクセスを効率的に行うことができる。すなわち、グラフ処理における計算に必要なデータは、グラフデータ（頂点の値、隣接情報（その頂点と辺で繋がる頂点のＩＤと辺の値））、その頂点宛てのメッセージのデータであるが、１頂点あたりのこれらのデータはページサイズよりも小さいため、複数頂点をまとめて頂点グループを定義し、グラフ処理の計算を頂点グループ単位で行い、頂点グループの計算に必要なデータをページサイズよりも十分大きくなるように頂点グループを定義することで、頂点グループの計算に必要なデータをページサイズ単位で不揮発性メモリ上に配置することができ、不揮発性メモリへのアクセスの粒度をページサイズにして不揮発性メモリアクセスの性能低下を抑えることができる。
【００５８】
なお、本実施例では、ＢＳＰモデルを用いたグラフ処理を例にメッセージを送信する場合について説明したが、ＭａｐＲｅｄｕｃｅにおいて、Ｍａｐフェーズで生成されるｋｅｙ−ｖａｌｕｅペアのサーバ装置３０２−３０５の1台あたりの総量が主記憶３１０のサイズよりも大きい場合のＳｈｕｆｆｌｅとＳｏｒｔフェーズについても適用することができる。
【００５９】
Ｓｈｕｆｆｌｅフェーズにおいて各サーバ装置は、メッセージ読出処理部３０９４が、Ｍａｐフェーズで生成したｋｅｙ−ｖａｌｕｅペアを受け取り不揮発性メモリ４０５に書き込む。ｋｅｙ−ｖａｌｕｅペアの不揮発性メモリ４０５への書き込みの方法を図９Ａに示す。まず、前処理部３０９１は、ｋｅｙを複数まとめてｋｅｙグループを定義する。ｋｅｙグループに含まれるｖａｌｕの数は、ｋｅｙグループに含まれるｋｅｙ−ｖａｌｕｅペアの総量が不揮発性メモリ３１１のページサイズよりも十分大きくかつ主記憶３１０の容量よりも小さくなるようにする。
【００６０】
図６に示した場合と同様に、メッセージ書込処理部３０９５は、ページサイズの大きさの不揮発性メモリ書込みバッファ８０２をｋｅｙグループの数だけ生成しておき、ｋｅｙ−ｖａｌｕｅペア８０１を、ｋｅｙが属するｋｅｙグループの不揮発性メモリ書込みバッファ８０２に書き込む。メッセージ書込処理部３０９５は、不揮発性メモリ書込みバッファ８０２がいっぱいになったときに、不揮発性メモリ書込みバッファ８０２の内容を不揮発性メモリ８０３に書込み、そのｋｅｙグループのデータがどこに書き込まれたかのアドレスリストを記憶しておくキーデータアドレステーブル８０４に、書き込んだアドレスを記録する。そして、メッセージ書込処理部３０９５は、不揮発性メモリバッファ８０２の内容が不揮発性メモリ４０５に書き込みが終了したら、不揮発性メモリ書込みバッファ８０２をクリアして、再度バッファの先頭から書き込みを始める。そして、メッセージ書込処理部３０９５は、すべてのｋｅｙ−ｖａｌｕｅペアを不揮発性メモリ４０５に書き込んだあとに、不揮発性メモリ４０５からｋｅｙ−ｖａｌｕｅペアを読み出しながらＳｏｒｔフェーズを行う。
【００６１】
ｋｅｙ−ｖａｌｕｅペアのＳｏｒｔフェーズでの不揮発性メモリからの読み出し方法を図９Ｂに示す。メッセージ書込処理部３０９５は、Ｓｈｕｆｆｌｅフェーズで作成したキーデータアドレステーブル８０４からひとつのｋｅｙグループを選んで、そのアドレスリストに基づいて不揮発性メモリ４０５からｋｅｙ−ｖａｌｕｅペアのデータを主記憶６０３に読み出す。メッセージ書込処理部３０９５は、主記憶３１０の領域６０３に読み出したデータをＳｏｒｔしてＲｅｄｕｃｅフェーズに渡す。メッセージ書込処理部３０９５は、ｋｅｙグループのＲｅｄｕｃｅの処理が終了したら別のｋｅｙグループを選んで同様の処理を繰り返す。
【００６２】
以上のようにＳｈｕｆｆｌｅとＳｏｒｔフェーズを行うことで、Ｍａｐフェーズで生成されるｋｅｙ−ｖａｌｕｅペアのサーバ装置３０２−３０５の1台あたりの総量が主記憶３１０のサイズよりも大きい場合に、不揮発性メモリを使ったＳｈｕｆｆｌｅとＳｏｒｔ処理を不揮発性メモリへのアクセスをすべてページサイズで行いながら処理することができる。
【００６３】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【符号の説明】
【００６４】
１０１  頂点
１０２  辺
３０１  情報処理システム
３０２―３０５  サーバ装置
３０６  共有ストレージ装置
３０７  ネットワーク
３０８  ストレージエリアネットワーク
３０９  ＣＰＵ
３０９１  前処理部
３０９２  グラフデータ読出処理部
３０９３  グラフデータ書込み処理部
３０９４  メッセージ読出処理部
３０９５  メッセージ書込処理部
３１０  主記憶
３１１  不揮発性メモリ
３１２  ネットワークインターフェース
３１３  ストレージネットワークインターフェース
４０１１  頂点値
４０１２  隣接情報
４０２１  頂点値不揮発性メモリ書込みバッファ
４０２２  隣接情報不揮発性メモリ書込みバッファ
４０３１  頂点値書込データ量カウンタ
４０３２  隣接情報書込データ量カウンタ
４０４１  頂点値データ開始位置テーブル
４０４２  隣接情報データ開始位置テーブル
４０５  不揮発性メモリ書込み領域
４０５１  サブグループ頂点値データ開始位置テーブル
４０５２  サブグループ隣接情報データ開始位置テーブル
４０６１  頂点値データアドレステーブル
４０６２  隣接情報データアドレステーブル
５０１  メッセージ
５０１１  メッセージとローカル頂点ＩＤの組
５０２  メッセージ不揮発性メモリ書込みバッファ
５０４  現スーパーステップデータアドレステーブル
５０５  前スーパーステップデータアドレステーブル
６０３  主記憶への不揮発性メモリからの読出し領域
７０２  メッセージカウントテーブル
７０３  メッセージ書込インデックステーブル
７０４  ソート済みメッセージ領域
８０１  ｋｅｙ−ｖａｌｕｅペア
８０２  不揮発性メモリ書込バッファ８０４  キーデータアドレステーブル
【図１】
2014196055.tif 000003
【図２】
2014196055.tif 000004
【図３】
2014196055.tif 000005
【図４Ａ】
2014196055.tif 000006
【図４Ｂ】
2014196055.tif 000007
【図５Ａ】
2014196055.tif 000008
【図５Ｂ】
2014196055.tif 000009
【図６】
2014196055.tif 000010
【図７】
2014196055.tif 000011
【図８】
2014196055.tif 000012
【図９Ａ】
2014196055.tif 000013
【図９Ｂ】
2014196055.tif 000014
【図１０】
2014196055.tif 000015
【図１１】
2014196055.tif 000016
【図１２】
2014196055.tif 000017
【図１３】
2014196055.tif 000018
【図１４】
2014196055.tif 000019
【図１５】
2014196055.tif 000020
【国際調査報告】
2014196055.tif 000021
2014196055.tif 000022
2014196055.tif 000023
2014196055.tif 000024