サイエンティフィック・システム研究会
科学技術計算分科会 2014 年度会合 資料2014 年10 月 29 日

スーパーコンピュータを用いた大規模グラフ解析とGraph500 ベンチマーク
藤澤 克樹
九州大学 マス・フォア・インダストリ研究所[アブストラクト]
新しいスーパーコンピュータの応用として大規模なグラフ解析が注目を集めている。新しいスーパーコンピュータ(スパコン)の応用として大規模なグラフ解析やデータ処理が注目を集めている。グラフ解析の応用分野としては大規模災害等での避難誘導計画、社会公共政策や企業経営等のためソーシャル・ネットワーク等の大規模データの有効活用等が想定されているが、非常に計算量やデータ量さらに電力使用量などの規模が大きく従来の手法では処理が困難である。そのためハイパフォーマンスコンピューティング分野の技術を用いて大規模なグラフ解析を行う研究がさかんに行われており、その中から Graph500 ベンチマークとグラフ解析の性能について解説を行う。これまで国内のスパコン（京コンピュータ、東工大 TSUBAME, 東大 FX10 等）を活用して、以下の図2 のように京コンピュータで世界１位(第８回 Graph500 ベンチマーク)等の優れた成果を挙げた。
[キーワード] 最適化問題, グラフ解析, Graph500 ベンチマーク, HPC, オープンソース

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

2. 大規模グラフ探索と Graph500 ベンチマーク
スパコンのベンチマークテストでは Top 500 が有名である。Top 500 では主に数値計算能力が測定される。今日ではスパコンの応用が幅広い分野に及び、交通ネットワーク分析やソーシャル・ネットワーク解析で注目されている大規模グラフ解析などのビッグデータ処理用途においては Top 500 の結果を用いて計算機評価を行うことが難しくなっている。
そのため、スパコンの大規模データ処理性能を計測する Graph 500 （注１） ベンチマークテストが 2010 年より開始された。また、Green Graph500 （注２） は Graph500 と同じくグラフ探索性能を競うベンチマークテストであり、昨今の厳しい電力事情を考慮すると、性能と同時に省電力性も極めて重要であり、今回の省電力グラフ探索の技術の多方面への応用が期待されている。
応用分野

グラフStep2
グラフ解析

parameters ion Graphgenerat
ionInput paramet ers Input
Graphgenerat
Graphconst
ruct ionGraph const ruct
BFSion事象同士の関係交通ネットワーク
SCALE- SCALE(Rela -onships)
ソーシャルネットワーク
Input paramet ers
Graph generation- edgefactor- edgefactor
サイバーセキュリティ
バイオインフォマティクス- SCALE脳科学 - edgefactor
防災計画策定Step1

Graph const ruct ion

BFS

解析結果
BFS ionValidatValidat ion

TEPS
ratio

TEPS

ValidatResultions

Result s- SCALE- edgefactor
ResultsTEPS- BFSTimeratio- Traversed edges- SCALE - TEPS- SCALE- edgefactor- BFS Time- Traversed edges- TEPS- edgefactor- BFS Timeratio
64 Iterations
edges
64Iterations - Traversed

Step3- TEPS

分析と理解
64 Iterations

Twi erソーシャルネットワーク

6,160万点 & 14億7千万枝• 並列グラフ探索 (幅優先探索)• 最適化 (最短路, 最大フロー, 最小費用フロー)• クラスタリング (グラフ分割, コミュニティ抽出)
ニューラル・ネットワーク @ Human Brain Project
890億点 & 100 兆枝

全米道路ネットワーク

サイバーセキュリティ

2,400万点 & 5800万枝

150億/日 のアクセスログ

図 1: グラフ解析の利用方法と応用分野

共同研究チームは、次世代のスパコン上で大規模なグラフの高速な探索処理を行うソフトウェアの開発を 2011 年から進めてきた。
冗長なグラフ探索を削減するアルゴリズムの利用、数千〜数万台規模が高速なネットワークで接続された超並列計算機上での通信性能の最適化、マルチコアプロセッサ上でのメモリへのアクセス最適化、フラッシュデバイスの利用による大規模グラフ処理と高性能化の両立などの先進的なソフトウェア技術を高度に組み合わせることにより、モバイルデバイスからスパコンまでの様々なコンピュータ上での高速かつ省電力なグラフ処理を可能にしている。最近 (国際会議 ISC14, 2014 年 6 月)、独自に開発したソフトウェアを用いて、大規模なグラフを解くことでスパコン上のビッグデータ処理を計測する Graph500、及び、その省電力性を計測する Green Graph500 ベンチマークを様々な研究機関や企業の協力と支援によって実施した結果、両者において世界第 1 位の高成績を達成した。当 CREST チームでは国内のスパコン（京コンピュータ、東工大 TSUBAME, 東大 FX10 等）を活用して、以下の図 2のように京コンピュータで世界１位(第８回 Graph500 ベンチマーク)等の優れた成果を得た。

Graph500ベンチマークにおける
当CRESTチームの成果
Top 1
K-computer
TSUBAME 2.5 (2.0)
FX-10
SGI UV2000
TSUBAME-KFC
4-way Xeon server

16384

GTEPS (in logscale)

4096
1024

15363

15363

K com
p uter
17977

15363

17977
3541

FX 1 0#4#4#45524

5524

5524

993

1003

256609317 # 44621280 C PU o n ly
1003462462
131.4
SGI U V2 0 0 0

TSU BA M E-K FC

6444.0100 # 318104.3
45.7

4 -w ay X eo n server

7CPU o n ly

4

31.6

GPU16×3 .2 5

TSU BA M E 2 . 5358 # 3253

#1

8.2

10.5

11.1

1
1st
2nd
3rd
4th
5th
6th
7th
8th
Nov. 2010 June 2011 Nov. 2011 June 2012 Nov. 2012 June 2013 Nov. 2013 June 2014

図 2: Graph500 ベンチマークにおける当 CREST チームの成果

（注１）

（注２）

Graph500 ： 幅優先探索によって１秒間に探索したグラフのエッジ （枝） の数が指標として用いられる。具体的には単位指標は TEPS （Traversed Edges Per Second） が用いられ、TEPS 値が高ければ、高速にグラフ探索を行うことができることを意味する。Web サイト：http://www.graph500.org/
Green Graph500 ： 単位指標は TEPS / W (Traversed Edges Per Second / Watt) が用いられ、TEPS /W 値が高ければ、単位消費電力あたりのグラフ探索性能が高い、つまり省電力性能が高いことを意味する。Green Graph500
では処理する対象となるグラフの規模に応じてビッグデータ部門とスモールデータ部門に分かれている。Web サ
イト：http://green.graph500.org/