藤澤研究室│九州大学 マス・フォア・インダストリ研究所 藤澤研究室│九州大学 マス・フォア・インダストリ研究所
English / 日本語

研究概要

IACR



IACR



IACR



IACR



 新しいスーパーコンピュータの応用として大規模なグラフ解析が注目を集めている。グラフは点集合と枝集合から構成される。具体的には図1のように様々な応用分野おいて解析の対象とする事象の関係(Relationships)を点と枝で表現していく。例えば道路交通ネットワークでは点は交差点、枝は交差点間の道路に該当する。またTwitterなどのソーシャルネットワークの解析では、点はユーザ、枝はユーザ間のフォロー関係(あるいはメッセージ送信)などに関連させることが多い。さらに各枝を連結させてグラフを構成して(Step 1)、目的に応じて最短路検索などのグラフ解析を行う(Step 2)。またグラフ解析の結果は元の応用問題の分析や理解のために使用される(Step 3)。実際にカーナビゲーションシステムでは道路ネットワークがグラフデータとして 内蔵されていて、ユーザの指示に応じて出発地点と目的地点間の最短路検索を行っている。このように社会における実データをグラフデータに変換して、計算機で高速処理する需要が非常に高まっている。

 グラフ解析に関しては数年以内に数千万規模の並列性を備えたポストペタスパコン上での高性能な超大規模グラフ処理技術が確立され、ストレージの階層性が深化したポストペタスパコン上での高性能な超大規模グラフ処理技術が開発されていくと予想されている。これによって防災計画の策定、災害時の避難と誘導及び情報収集と解析、スマートグリッドによる高度かつ安定な電力供給など、安全安心な社会基盤実現に貢献することが可能となる。以下の 分野に対してグラフ解析を適用することを想定している(図2)。
1.交通データに対する経路探索:動的に変化する交通量等から高速な重要度判定を行うことによって、交通管制等に活用する。
2.ソーシャルネットワークデータ(マイクロブログやSNSなど)やウェブデータに対する動的な重要度、影響度の判定。各点の周辺、及び広域内における影響(情報の伝播力)を推定する。
3.その他:疫病の拡散、人口の増減、経済動向等の分析。ライフライン等の基盤計画(電力、水、食料)。生命科学系(創薬、遺伝子)。ビジネス系(金融、 データマイニング)。安全保障分野(組織構成の解明、事件事故の事前予測)。

 従来は計算中心であった高性能計算(ハイパフォーマンスコンピューティング)の分野においても大規模なデータ処理を中心に扱うアプリケーション(データ・インテンシブアプリケーション)が増加している。
Graph500は並行探索、最短路探索をはじめとする最 適化、極大独立集合などのグラフ解析、などの複数のグラフ処理カーネルからなるべンチマークにより計算機の性能を評価しランキングを行う。グラフ解析はサイバーセキュリティ、創薬、データマイニング、ネットワーク解析などの分野において必要とされる重要な計算カーネルとして位置づけられている。

 このGraph500に対するBFSの高速実装は図3のようにTwitterネットワークの解析等に用いることができる。図3ではTwitterのユーザとフォロー関係を表したFellowship network 2009(点数:4100万、枝数24億)を用いて特定のユーザからBFSを行い、そのユーザを根(root)とするBFS木を構築している。これによって、あるユーザから何ホップ以内に何人のユーザが存在しているかについて高速に探索することが可能になる。この場合では24億枝のグラフに対してわずか0.069秒でBFS木の構築に成功している。また最適化問題の高速計算と実社会への応用にも取り組んでおり、例えば半正定値計画問題(SDP)は組合せ最適化、システムと制御、データ科学、金融工学、量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。SDPに対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算(行列要素の計算と行列のCholesky分解)が大きなボトルネックとなっている。最近の結果では多数GPUの活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの1つである線形方程式系のCholesky分解の高速化と世界最大規模のSDPを高速に解くことに成功した(最大で1.713PFlopsの性能を達成 : 図4)。

PAGETOP