スーパーコンピュータを用いた	
  大規模グラフ解析と 	  Graph500	
  ベンチマーク	
戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

Core Research for Evolutional Science and Technology

藤澤 克樹

戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

九州大学マス・フォア・インダストリ研究所＆ JST CREST

共同研究者：上野 晃司（東工大),	  	
  安井 雄一郎(九大),	
  鈴村 豊太郎（University	
  College	
  Dublin),	
  佐藤 仁,	  岩渕 圭太,	
  溝手 竜(東工大)	
戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

2014年10月29日
サイエンティフィック・システム研究会 科学技術計算分科会 2014年度会合	
次世代HPCを支える技術	

戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

Core Research for Evolutional Science and Technology

ホーテルオークラ神戸
戦略的創造研究推進事業

Core Research for Evolutional Science and Technology

当 CREST	
  の研究計画の概要	
• 次世代ポストペタスパコンでの解決すべき課題の特定	  – 並列数の爆発的増大、不均質化、高密度化	
  – 記憶装置の多階層化・大容量化	
  – アルゴリズム的、システム的に様々な解決すべき課題と困難が存在	
  • 大規模グラフ解析及び数理最適化システム 	  – 緊急に取り組むべき課題と実社会へのインパクト	  – Graph500(Green	  Graph500)ベンチマーク	  (巨大グラフ,	
  BFS)	
  	
  	
  	
  

• ISC12	
  :	
  358GTEPS	  (世界３位)	
  ,	
  8.15GTEPS	  (1ノード世界1位)	
  • SC12	
  :	
  5524GTEPS(世界４位),	
  10.495GTEPS(1ノード世界1位)	
  • ISC13	
  :	
  6.119GTEPS/kW	
  (世界1位)	
  	
  • SC13	
  :	
  6.72GTEPS/kW	  (BigData	  1位),	
  	
  153.17GTEPS/kW	
  (SmallData	  1位)	  
• ISC14	
  :	
  17977GTEPS(世界１位),	
  59.12GTEPS/kW	  (BigData	  1位)	  

– 数理計画問題（SDP):	
  (世界記録更新：233万制約 ;	
  1.713PFlops)	
  • SC12(Tech.	
  paper)	
  ,	
  IPDPS14	
  など： 疎&密データ計算(24,480CPUコア &	
  4080GPU) ： 日本オペレーションズリサーチ学会研究賞、NVIDIA	  GTC	  Japan	
  最優秀ポスター発表賞等	
  • 最適化とHPC系研究者のポストペタスパコン上でのCo-­‐design	
  による解決	  • ポストペタスパコン上での基盤ソフトの整備に貢献すると共に安心
安全な社会の実現を目指す	  超大規模グラフ最適化システムの提案	
防災計画策定	

交通・災害復興・	
避難・ロジスティクス	

ソーシャル
ネットワーク解析	

エネルギー・省電力	

超大規模グラフ最適化システム	
超大規模センサー	
• 観測データ• スマートグリッド• 交通・輸送• SNS (Twitter)

大規模グラフ可視化	
‘03	

‘05	

リアルタイム大規模グラフ
ストリーム処理	
中心性	
  
解析	
  

データソース	Indexing	
  

クラスタ	
  
リング	
  

リアルタイム	  ストリーム処理系	
データソース	‘07	
グラフ探索及び数理最適化
‘09	
‘11	

ライブラリによる大規模グ
ラフ処理	

最短経路
問題	
  

最速	
  
フロー問題	
  

半正定値
計画問題	
  

混合整数	
  
計画問題	
  

X10言語処理系	

100PF級ヘテロジニアススパコン	

大規模グラフストア		  Step2	
グラフ	
Input
parameters
generation
Graph construction
BFS
Graph
generation Graph
Graphconstruction
グラフ解析	
事象同士の関係	  Step1	- SCALE(RelaXonships)	

応用分野	
Input parameters

交通ネットワーク	  - SCALE
ソーシャルネットワーク	
  Input parameters
Graph generation- edgefactor- edgefactor
サイバーセキュリティ	  バイオインフォマティクス	  - SCALE脳科学	
  - edgefactor
防災計画策定	Twi]er	ソーシャルネットワーク	

6,160万点 &	  	
  14億7千万枝	  Graph construction

解析結果	
BFS
Validation

BFS

Validation

Step3	

TEPS

分析と理解	TEPS
ratio

64 Iterations
ratio

Valida-S-e
Result-B-T- SCALE - T- edgefactor- BFS Time
64 Ite- Traversede- TEPS

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

サイバーセキュリティ	2,400万点 &	
  5800万枝	

150億/日 のアクセスログ	
  大規模グラフ解析：緊急に取り組むべき課題と実社会へのインパクト	
防災計画策定	

交通・災害復興・	
避難・ロジスティクス	

エネルギー・省電力	

ソーシャル
ネットワーク解析	

インターネットマップ
ニューラルネットワーク

ソーシャルネットワーク サイバーセキュリティ

交通(時空間)ネットワーク

スモールワールドやスケールフリー性などの特性を持つ超巨大グラフ(1兆点以上) 上での高速探索技術（アルゴリズム、実装技術、高速計算）

45	

京スパコン:	
  65536ノード	
  Graph500:	
  17977	
  GTEPS	
Human Brain Project	
 Graph500 (Huge)	
Symbolic
Network
Graph500 (Large)	

1 兆枝

40	

Graph500 (Medium)	

(	
m	
)	
l	
o	
g	
2	

グラフの枝数35	Graph500 (Small)	
Graph500 (Mini)	

1０億枝
30	

Graph500 (Toy)	
USA-road-d.USA.gr	

25	

USA-road-d.LKS.gr	

20	

Twitter (tweets / day)USA-road-d.NY.gr 	
15	

20	

Android	
  携帯 :	
  SONY	
  SO-­‐01F	
  Snapdragon	
  S4	
  1.7GHz	
  4コア:	
  2GB	
  RAM	
  1.03GTEPS:	
  235.06MTEPS/W	

全米道路ネットワーク

１兆点

Twitter (バルス:2013/08/02)
25	

30	
log	
2	
(n)	

グラフの点数

35	

１０億点

40	

45	

全米横断の最短路： 2400万点,	
  5800万枝 à	
  約2秒で計算(3W)	
  サンディエゴから北東部のメーン州までの最短路	
  （赤：最短距離、青：最短時間）:	
  h]p://opt.imi.kyushu-­‐u.ac.jp/	

超大規模ネットワークにおける高速探索技術の開発コアとなるアルゴリズムやソフトウェアのカーネル部分の実装と評価• 超大規模ネットワークデータ（点数１0億以上)が対象• 最短路(1対全), グラフ探索(深さ優先、幅優先等)• グラフ探索の局所的な評価では優先キュー(ヒープ木)を用い
る 実行時間、メモリ消費量が安定的• 実行時間(1対全最短路計算: CPU : Intel Xeon 5670 2.93GHz)– 全米グラフ 3秒（点数 n = 23,947,347、枝数 m = 58,333,344）– 超大規模グラフ 870秒 (点数 n = 10億, 枝数 m = 20億)

• 多くの応用(交通ネットワーク, e-コミュニティのネッ
トワーク、ロジスティクスネットワーク)

始点 横浜
終点 東京
始点 新宿
終点 千葉
始点 川崎
終点 大宮
始点 東京
終点 ディ
始点 沖縄
北海
終点 道

スレッ
消費メモリ 実行時間 実行時間/クエリ(マイ 確認リン usec/
ド数
クエリ数 MB
(秒)
クロ秒)
ク数
#arcs
コスト
48224911
100
564.545.564
55640
4280860.130019108
7579958100
1815.59
2.139
21390
4280860.050019108
10852241
100
564.5435.794357940 4046406
0.088534493
4174499
8
100
1815.59
7.610
76100 4046406
0.018834493
6616991
100564.5417.954
179540 2072075
0.086630527
1576725
8100
1815.59
3.905
39050 2072075
0.018830527
23216661
100
564.5410.190101900 1026584
0.099319002
2617848
100
1815.593.160
31600 1026584
0.0308
19002
377
1
72
564.54257.4213575292 44595172
0.0802 17264925
9065116

8

72

1815.5944.871623208 44595172

0.0140 17264925

点の重要性• グラフの特徴を示す指標– 中心性、PageRank …

• 中心性指標が広く利用されている– 近年は中心性が盛んに研究されている• 中心性指標にもいくつか種類がある– 各点に接続されている枝数（Degree Centrality）– 各点が最短路に含まれる回数（Betweenness Centrality）– 最も遠い点までの最短距離（Graph Centrality）– 各点までの最短距離（Closeness Centrality）

中心性の定義v-t 間最短路長• Closeness Centrality

closenessgraph

stressstress(対数)• Graph Centrality• Stress Centrality• Betweenness Centralityv を通る s-t 間最短路数

s-t 間最短路数

betweenness全米グラフに対する重要性(中心性)の計算	
• ネットワーク内での各点の重要度を推定	
  • 各点の周辺、及び広域内における影響（情報の伝播力)を推定する	
  • 超大規模ネットワークデータ上での短時間に大量のグラフ探索を行う必要がある	
  Closeness	
Graph	

Stress(対数)	

Betweenness	

The	
  U.S.	
  Electric	  Grid	  hDp://www.npr.org/templates/story/story.php?storyId=110997398

Electrical	
  Centrality	
  Measures	
  for	  	
  Electric	
  Power	  Grid	  Vulnerability	
  Analysis	  	
  Wang,	
  Z.;	
  Scaglione,	
  A.;	
  Thomas,	
  R.	
  J.	
  2010	  	全米道路ネットワークに対する全対全最短路問題
点数 n = 23,947,347, 枝数 m = 58,333,344
4-way Opteron 6174 2.3 GHz (12 cores x 4), 256 GB, GCC-4.6.0

アルゴリズム	
Dijkstra’s algorithm	

全対全最短路	
 高速化率	
 各2点間の最短路長を
1.1ns で求めることができる
512 年	--	Δ-stepping	

9.1 年	

60 倍	Multi-Level Buckets	

4.9 年	

110 倍	MSLC + NUMAを考慮した最適化	

7.8 日	
 24,000 倍	

厳密な
全対全最短路長を
約7.8日で計算

五大湖周辺道路ネットワーク最短路を用いた中心性計算
点数 n = 2,758,119, 枝数 m = 6,885,658
4-way Opteron 6174 2.3 GHz (12 cores x 4), 256 GB, GCC-4.6.0

重みを考慮しない中心性 : 19.35 時間
closenessstressgraph

betweenness

既存の GraphCT では
BC のみの計算で20.6 日かかる

NYデータに対する	
中心性(BC)の計算	
結果（最短路問題）	
	○サーバ１ (2CPU x 4 コア = 8 コア)	実行時間 1957.652 秒 : 8スレッド		CPU : AMD Opteron 2356 2.3GHz x 2	メモリ : 32GB	
OS : Vine Linux 5.1 for X86_64	
		
○サーバ２ (1CPU x 4 コア = 4 コア)	実行時間 2058.443 秒 : 4スレッド		CPU : Intel Core i7 965 3.2GHz x 1	
メモリ : 12GB	
OS : CentOS 5.5 for x86_64	
		
○サーバ３ (4 CPU x 6 コア = 24 コア)	実行時間 632.859 秒 : 24スレッド		CPU : AMD Opteron 8439 2.80GHz x 4	Memory : 128GB	
OS : Fedora 13 for x86_64	
		○ サーバ４ (2 CPU x 4 コア = 8 コア)	実行時間 1319.054 秒 : 8スレッド		CPU : Intel Xeon 5550 2.66GHz x 2	Memory : 72GB	
OS : Fedora 13 for x86_64	

全米横断の最短路： 2400万点,	
  5800万枝 à	
  約2秒で計算(3W)	
  サンディエゴから北東部のメーン州までの最短路	
  （赤：最短距離、青：最短時間）:	
  h]p://opt.imi.kyushu-­‐u.ac.jp/	ジョージ・ワシントン橋,	
  ニューヨークを	  通過する全米横断最短路

Graph500・Green Graph500◯ Graph500・Green Graph500 ベンチマーク• パラメータ SCALE と edgefactor (=16) から、点数 n=2SCALE, 枝数
m=edgefactor・n となる Kroncekr graph を生成• 幅優先探索 (BFS) での1秒辺りの探索枝数 TEPS により、Graph500 リストを作成• 消費電力あたりの TEPS（TEPS/W) により、Green Graph500 リストを作成
Hybrid Algorithm for Parallel BFS◯ 高速な幅優先探索の実装
BFS[Beamer,2012]
Direction Optimizing Breadth-First Search•◯ Green Graph500 (June 2013)

計算機性能を引き出す汎用的な高速化

探索領域 (frontier) の大きさによって, 探索方針を切り替える.

⇔

forward-search (top-down step)
探索領域が小さいとき

領域 (小)

backward-search (bottom-up step)
探索領域が大きいとき

上位独占

1位

thm for Parallel BFS      



探索
Breadth-First Top-down
Search
2位

針を切り替える.

⇔backward-search (bottom-up step)
探索領域が大きいとき

Chuo University’s
GraphCREST-Tegra3

領域 (大)
3位

メモリ階層構造を考慮した大規模グラフ処理の高速化   

日本数式処理学会

No.2

in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
64.119 MTEPS/W on Scale 20
on the first Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
53.818 MTEPS/W on Scale 23
on the first Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

1位

Congratulations from the Green Graph 500 Chair

2位

22 / 31
Chuo University’s
GraphCREST-Mac-miniBottom-up 探索

is ranked

No.1

Congratulations from the Green Graph 500 Chair

安井 (中央大学, CREST)

Chuo University’s
GraphCREST-Intel-NUC

is ranked

Chuo University’s
GraphCREST-MBA13

is ranked

No.4

in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
53.472 MTEPS/W on Scale 24on the first Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
52.017 MTEPS/W on Scale 23
on the first Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

Congratulations from the Green Graph 500 Chair

4位

is ranked

No.3

3位

Congratulations from the Green Graph 500 Chair

4位

Graph500ベンチマークの実⾏行行順
2

Graph  Generation（枝リストを⽣生成）

Kernel  1

Kernel  2

1

3

2
2

Graph  Construction(枝リストをBFSで探索索するためのデータ(CSR  or  CSC)に変換)  Breadth  First  Search
Validation(５つのルールでBFSツリーを検証）

3

1

始点をランダムに64個選択

64回
繰り返す

※CSR:  Compressed  Sparse  Row,  CSC:  Compressed  Sparse  Column
18Graph500技術の応用
Twitter ネットワークの解析• フォロー・ネットワーク– ユーザ数（点数）
41,652,230– フォロー関係（枝数）2,405,026,092

ユーザ 21,804,357 からの幅優先探索の結果
ホップ数2009 年に取得したフォロー数が1以上のユーザ•

Graph500 ベンチマーク– 幅優先探索の性能「１秒間に通過した枝数 TEPS」を用いて、コン
ピュータの性能を比較する

合計

ユーザ数

割合 (%)

累積割合 (%)

0

1

0.00

0.00

1

7

0.00

0.00

2

6,188

0.01

0.01

3

510,515

1.23

1.24

4

29,526,508

70.89

72.13

5

11,314,238

27.16

99.29

6

282,456

0.68

99.97

7

11536

0.03

100.00

8

673

0.00

100.00

9

68

0.00

100.00

10

19

0.00

100.00

11

10

0.00

100.00

12

5

0.00

100.00

13

2

0.00

100.00

14

2

0.00

100.00

15

2

0.00

100.0041,652,230

100.00-0.069 秒で探索可能
21.28 GTEPS（109 TEPS）

グラフ処理と幅優先探索
Step2
応用分野Input parameters InputGraph
グラフ
BFS
generation Graph
Graphconstruction
parameters
generation
Graph construction
•
•
•
•

交通
関係性
Input parametersGraph-generation
SCALE- SCALESocial network- edgefactor- edgefactor
Cyber-security- SCALE- edgefactor
生命科学

グラフ処理
BFS

Graph construction

ratio

Step1

TEPS
ratio

Step3
応用分野の理解• 中心性指標• 最大流

64 Iterations• コミュニティ検出• クラスタリング

グラフ処理

Level 3

始点

- SCALE- edgefact- BFS Time- Traverse- TEPS64

64 Iterations

出力：始点からの各点の距離（ホップ
数）

BFS

始点

Resu

Validation• 最も重要かつ基本的なグラフ処理の一つ• 他のアルゴリズムのサブルーチン• 演算量に比べて、不連続なメモリアクセスが多いことが問題

入力：
グラフと始点

Valid

TEPS

• 幅優先探索• 最短路問題• 極大独立集合

幅優先探索

結果
Validation
BFS

Level 1 Level 2

Level-synchronized parallel BFS (Top-down)ns (timed).:Thisfrom
step iterates
the vertex
timed• Started
sourceuntimedverify-phase
64 following
times. The BFSandexecutestwo
BFS foreach source,
and the level
verify-phase
phasesfor each
ut of the BFS.
k is based on the TEPS ratio, which isTraversal … ﬁnds unvisited
ven graphand the BFS
output. Submission
adjacency
vertices
from
F
hmark
must
reportfive
TEPS
ratios:current frontier Q and theuartile,median, to
third
quartile, andappendneighbor
QN maxi-

ARALLEL BFS A LGORITHM Neighborized Parallel BFS

QN

the input of a BFS is a graph G = (V, E)
Frontier
et of vertices
V and a set of edges E.
FQ
f G are contained
as pairs (v, w),Level
where
k+1
Level ket of edges E corresponds to a set ofwhere an adjacency list A(v) containsthes (v,Swapw) ∈ E …
for swaps
each vertexv ∈ V. A
F
frontier
Q andvariousedges spanning
all theother vertices
Nneighbor
he sourcevertex sQ∈ Vforin anext
given level
graph
predecessor map π, which is a map from

Algorithm 1: Level-synchronized Parallel BFS.
Input

: G = (V, A) : unweighted directed graph.
s : source vertex.
Variables: QF : frontier queue.
QN : neighbor queue.
visited : vertices already visited.
Output : π(v) : predecessor map of BFS tree.
π(v) ← −1, ∀v ∈ V
2 π(s) ← s
3 visited ← {s}F
4 Q ← {s}
N
5 Q
←∅
F
6 while Q ̸= ∅ do7
for v ∈ QF in parallel do
8
for w ∈ A(v) do
Traversal
9
if w ̸∈ visited atomic then
10π(w) ← v
11
visited ← visited ∪ {w}12
QN ← QN ∪ {w}
1

13
14

QF ← QN
QN ← ∅

Swap

Hybrid-BFS (Direction-optimizing BFS)
Chooses one from Top-down or Bottom-up for frontier size at each level

前方探索と後方探索でのデータアクセスの観察
Bottom-up algorithm
Top-down algorithm
前方探索と後方探索でのデータアクセスの観察• Eﬃcient for small-frontier• 前方探索でのデータの書込み• Uses out-going edges• 前方探索でのデータの書込み• Eﬃcient for large-frontier
Uses in-coming edges•• 後方探索でのデータの書込み• 後方探索でのデータの書込み

Neighbors
Level	
  k+1
w
w

v v

Frontierv→
wLevel	  v→
w kBeamer2012vv

Candidates ofw
w neighbors

Frontierw→
wLevel	  → vvk

Level	
  k+1

neighbors

F
Input: Directed
graph
GG
==
(V,(V,AFA)F, )Queue
Input: Directedgraph, QueueQQF
Data
QNQ, Nvisited,
Tree
π(v)
Data: Queue: Queue, visited,
Tree
π(v)

FF
Input
graph G
G ==(V,(V, AABB),),Queue
QueueQQ
Input :: Directed
Directed graphData
visited,Tree
Treeπ(v)π(v)
Data :: Queue
Queue QNN ,, visited,

N
QN Q←
∅← ∅
Current frontier
F QF in parallel doforv∈
for v ∈ Q in parallel doF(v)
for forw ∈wA∈F A(v)dodo
! visitedatomicthen
if wif!wvisited
atomic
then
π(w)
π(w)
←←
v v
Unvisited
visitedvisited{w}
visited←←visited∪∪{w}neighbors
NQN ← NQN ∪ {w}
Q ← Q ∪ {w}F
N←NQ
QF Q← QQQNN ←← ∅∅for w
w ∈∈ V
V \ visited inin parallel
paralleldo
doforfor vv ∈∈ AB (w) do
for
do
F
F
∈ Q thenifif v ∈
then
π(w)
←
π(w) ← vv
visited ←visited← visited
visited∪∪{w}{w}
NN
N ← Q N ∪ {w}Q
Q ← Q ∪ {w}
break
break
F
N
←Q
QN
QQF ←

Candidates ofneighbors

Current frontier

Skips unnecessary edge traversalHybrid-BFS (Direction-optimizing BFS)
Chooses one from Top-down or Bottom-up
for a number of traversed edges at each level

Beamer2012

探索に対する前方探索(Top-down)(Bottom-up)
Number of traversal edgesof Kronecker と後方探索
graph with SCALE
26
Top-­‐down
26
30|V| = 2 , |E| = 2
Distance from source

Level
0
1
2
3
4
5
6
Total
Ratio

Top-down
2
66,206
346,918,235
1,727,195,615
29,557,400
82,357221
2,103,820,036
100.00%Bottom-up
2,103,840,895
1,766,587,029
52,677,691
12,820,854
103,184
21,467
21,2403,936,072,360
187.09%Hybrid2
66,20652,677,691
12,820,854
103,184
21,467
227
65,689,631
3.12%

= |E|
Hybrid-BFS reduces
unnecessary edge traversals

Bottom-­‐up	
  Top-­‐down

NUMA アーキテクチャの構成• 4-way Intel Xeon E5-4640 (Sandybridge-EP)– 4 (CPU ソケット数)– 8 (CPU ソケットあたりの物理コア数)– 2 (物理コアあたりのスレッド数)

NUMAノード最大

4 x 8 x 2 = 64 スレッド
（ハイパースレッディング）

ローカルメモリへのアクセス（アクセスコスト小）

processor core & L2 cache

NUMAノード
RAM

RAM

RAM

CPUソケット（16 論理コア）
ローカルメモリRAMshared L3 cache

リモートメモリへのアクセス（アクセスコスト大）8-core Xeon E5 4640

データアクセスが不均一であるため• 並列時の偏りが生じるため、並列効率を向上することが難しい• 本来の性能を予想することが難しい

NUMA-optimized BFS• Clearly separated to accessing for local and remote memory– Edge traversal on Local RAM– All-gather of local queues and bitmaps for Remote RAM
Traversal on local RAM

At each level,
No

Swap on Remote RAM

NUMA-­‐optimized	  Top-­‐down

Aggregates	
  local	
  frontier	
  queues

Large	
  frontier?
Yes

NUMA-­‐optimized	  Bottom-­‐up

Q N0• Searches	
  local	
  neighbors	
  from	
  local	
  copied	
  frontier	
  

Q N1
Q N2

NUMA-opt. requires two CSR graphs• Out-going edges for Top-down• In-coming edges for Bottom-up※	
  Not	
  same	  for	
  undirected	
  graph

Q N3
QF

Q N2

QF

NUMA-­‐opt.	
  Column-­‐wise	
  Graph	  ParXXoning	• divides	
  G=(V,A)	
  into	  parRal	
  Gk=(Vk,	  Ak)	
  and	
  binds	
  local	  RAM	
  k.	
  
– Ak	
  is	
  a	
  set	  of	
  adjacency	
  list	  that	  holds	
  incoming	
  edges	  to	
  Vk.	

Column-­‐wise	
  graph	  parXXoning	Row-­‐wise	
  graph	  parXXoning	

j	
Vk	

j	
A0

A0

i	

A1

i	

A1

Vk	

A2

A2

A3

Adjacency	
  matrix	

A3

i	

j	

O(m)	
  Local	  memory	
  accesses	
  only	Level	  k	FronXer	  Adjacency	
  matrix	

i	

j	

O(m)	
  mostly	
  non-­‐local	
  memory	
  accesses	

Neighbors	

Neighbors	  Level	
  k+1	

Level	
  k+1	

Level	  k	FronXer	NUMA-opt. parallel hybrid BFS（Graph500 1ノード最速）• 計算の大部分をローカルなメモリアクセス上で実行
BFS の主要な計算（ローカルなメモリアクセス）

レベル内の計算の例	
  Frontier	
  から次のレベルの	
  frontier	
  を探索

NUMA	
  unit	  0
NUMA	
  unit	  1All-­‐gather

Level	
  1 Level	
  2

QF0 QN0

Level	
  1 Level	
  2
QF1 QN1

Unvisited	  vertices

Level	
  2

Frontier	
  QF

NUMA	
  unit	  2
NUMA	
  unit	  3Level	
  1 Level	
  2
QN2

QF2
Level	
  1
Frontier	
  QF

Level	
  2

Neighbors	
  QN

Level	
  1 Level	
  2
QF3 QN3

Y.	
  Yasui	
  et	
  al.	  :	  NUMA-­‐optimized	
  Parallel	
  Breadth-­‐ﬁrst	
  Search	
  on	
  Multicore	
  Single-­‐node	
  Systemprocessor core & L2 cache

Local Edge Traversal

RAM
processor
core
processor
core && L2
L2 cachecache
0th NUMA
node

V0

V

RAM
RAM
RAM

A0
QF

V

RAM
RAM

A3
V3

QN

visited0

0

RAM
RAM

shared L3 cache8-core Xeon E5 4640

visited3

Q N3

8-core4640
8-core Xeon
Xeon E5
E5 2nd4640 NUMA node

1

A1

QF

RAM
RAM

sharedL3
1st NUMA
node
sharedL3 cachecache
慮したグラフ領域の分割
V

V

RAM
3th NUMA node

U ソケット (ℓ-個の RAM) を持つ計算機を想定

V
部分点集合
V
と隣接リストの部分集合
A
に配置
k
k
Q
visited Q
k-­‐th	  !
" NUMA	  ! node	  holds	  "V = V0 | V1 | · · · | Vℓ−1 , AF = A0 | A1 | · · · | Aℓ−1 ,
F

1

N

1

• Local	
  copied	
  frontier	
  Q
Vk は単純な
1 v次元分割• partial	
  ertices	
  Vk(n: 点数, ℓ: CPU ソケット数)#$%&kn (k + 1)nVk = v j ∈ V | j ∈
,
,
ℓ
ℓ

QF

• partial	
  edges	
  (vi	
  ,	
  vj	
  ),	
  (v2i	   種類の隣接リストを定義	  V	
  and	
  vj	
   	
  Vk)
U ソケットを持つ計算機上に
B

A2

V2

visited2

Q N2

Intel Xeon v.s. SGI Altix UV1000• Graph500 (SCALE29)– 536.9 million vertices, 8.59 billion edges
Median TEPS: 21.81 GE/s

Median TEPS: 31.81 GE/sIntel Xeon (Sandybridge-EP arch.)

SGI Altix UV1000 (Westmere-EX arch.)

Intel Xeon E5-4650 @ 2.70GHz
64-threads = 8-cores x 2-threads x 4-nodes
512 GBytes RAM
300

250

200

for	
  Remote	
  RAM

150

100

BottomUpfor	
  Local	
  RAM

50

CPU time (ms)CPU time (ms)

250

300

Traversal (local)
Swap (all-gather)

64 threads
400 GBIntel Xeon E7-8837 @ 2.67GHz
512-threads = 8-cores x 64-nodes
4.0 TBytes RAM

200

for	
  Remote	
  RAM

150

100

for	
  Local	
  RAM

50

BottomUp

Traversal (local)
Swap (all-gather)

512 threads
1.0 TBytes

BottomUp
BottomUp

BottomUp
BottomUp

0
Init

Lv.0

Lv.1

Lv.2

Lv.3
Level

Lv.4

Lv.5

Lv.6

BottomUp
BottomUp

0
Lv.7

Init

Lv.0

Lv.1

Lv.2

Lv.3
Level

Lv.4

Lv.5

Lv.6

Lv.7

Intel Xeon v.s. SGI Altix UV1000
Rank.50• Graph500 (SCALE30)

Fastest of single-node
on current list

– 1.07 billion vertices, 17.18 billion edges

Median TEPS: 37.70 GE/sIntel Xeon (Sandybridge-EP arch.)

SGI Altix UV1000 (Westmere-EX arch.)

Intel Xeon E5-4650 @ 2.70GHz
64-threads = 8-cores x 2-threads x 4-nodes
512 GBytes RAM

Intel Xeon E7-8837 @ 2.67GHz
512-threads = 8-cores x 64-nodes
4.0 TBytes RAM
300

Out of memory

CPU time (ms)250

Traversal (local)
Swap (all-gather)

512 threads
2.0 TBytesfor	
  Remote	
  RAM

200

150

for	
  Local	
  RAM

100
BottomUp
BottomUp

50

BottomUp
BottomUp

0
Init

Lv.0

Lv.1

Lv.2

Lv.3
Level

Lv.4

Lv.5

Lv.6

Lv.7

Strong scaling on SGI Altix UV1000
Rank.50• Graph500 (SCALE30)

Fastest of single-node
on current list

– 1.07 billion vertices, 17.18 billion edges• As the number of threads increases,– local traversal on Local memory : Improvement– swap operation on Remote memory : Keep
L : R = 80% : 20%
600

Traversal (local)
Swap (all-gather)

100

Local
733 msBottomUp

300

182 ms

100

Init

Lv.0

Lv.1

Lv.2

Lv.3

Lv.4

Lv.5

Lv.6

Lv.7

300

218 ms100

BottomUp
BottomUp
BottomUp
BottomUp
BottomUp

0
Init

Lv.0

Lv.1

Lv.2

Lv.3

Lv.4

Lv.5

Level

Level

128 threads

256 threads

Lv.6

37.70 GE/s

400

Remote 200

Local
438 msBottomUp
BottomUp
BottomUp

0

Traversal (local)
Swap (all-gather)

500

400

Remote 200

BottomUp

600

26.17 GE/s
CPU time (ms)300

L : R = 57% : 43%

Traversal (local)
Swap (all-gather)

500

400

200

600

18.76 GE/s
CPU time (ms)CPU time (ms)500

L : R = 67% : 33%

Lv.7

Local

Remote197 ms

258 msBottomUp
BottomUp
BottomUp
BottomUp

0
Init

Lv.0

Lv.1

Lv.2

Lv.3

Lv.4

Lv.5

Lv.6

Lv.7

Level

512 threads (one-rack)隣接行列の２次元分割※※Andy Yoo, et. all, A Scalable Distributed
Parallel Breadth-First Search Algorithm on
BlueGene/L. SC05.

} 2次元分割BFSでは深さ1レベルの計算で2つの通信フェーズがある

Expand: Fronter頂点を行方向で共有} Fold: Neighbors情報を列方向で通信} （Bottom-upでは行と列が逆になる）
}

C

C

R

1,1

1,2

1,C

2,1

2,2

2,C

R,1

R,2

R,C

プロセッサの２次元配置
32

R

隣接行列の２次元分割

頂点濃度に応じたデータ形式選択による通信
データ量削減} BFSで通信するデータはFrontierの頂点や未訪問頂点} 主に２種類のデータ形式が考えられる
頂点セット 1, 4, 6 を表すデータ形式

1,4,6

0100101

Sparse vector

Bitmap} Frontierや未訪問頂点数が多い＝頂点濃度が高い}

Bitmapの方が有利} Frontierや未訪問頂点数が少ない＝頂点濃度が低い}

Sparse vectorの方が有利

33

頂点濃度に応じたデータ形式選択による通信
データ量削減} トップダウンやボトムアップフェーズにこだわらず、頂点濃度によってBitmap と Sparse vectorから最適なデー
タ形式を選択Graph500グラフにおける典型的な
BFS探索におけるデータ形式選択
Level	
1	
2	
3	
4	
5	
6	
7	
8	
34

Expand	Fold	Sparse vector	
Sparse vector	
Sparse vector Sparse vector	
Sparse vector	
Bitmap	
Bitmap	
Bitmap	
Bitmap	Sparse vector	
Sparse vector	
Sparse vector	
Sparse vector	
Sparse vector	
Sparse vector	
Sparse vector	

Direction	
top-down	
top-down	bottom-up	
bottom-up	
bottom-up	
top-down	
top-down	
top-down	

Level5では、フロンティア頂
点が全頂点の84.5%なので、bottom-upが有利だが、未訪問の頂点はわずか2.4%なので、Sparse vectorで処理したほうがいいLevel 5における通信データ量比較
BitmapSparse vector

32 MB

4.5 MB

Efficient Hybrid Search with 2D Partitioning}

Our approach is based on the
Top-down and bottom-up hybrid
search BFS. [Beamer2011, 2012]}

We realized the hybrid searchwithout any increase of memory
footprint.

Top-down}

Bottom-up}: Graph data owned by a single processor

Sharing the same graph data between
two direction search.

Graph data is shared between two
search directions.

Overlapped communication withcomputation.
}Both top-down and bottom-up utilize
overlapping communication.

「京」における性能評価} Graph500ベンチマークで用いるグラフを使用} 65,536ノードで17,997GTEPSを達成}

ただし、通信時間の増加はまだ最適化の余地あり} 各最適化の効果の検証は今後の課題とするウィークスケーリング
1E+15

実際の性能
リニアにスケールした場合（64ノード基準）

1E+13

1000

17,977
GTEPS

1E+12

713
79 GTEPS GTEPS

計算

64

256

1024
4096
ノード数

600
400
200

1E+10

36

通信待ち

800

1,266 GTEPS

1E+11

1200

81,043
GTEPS

時間(ms)

TEPS

1E+14

ブレークダウン

16384

65536

問題サイズは65536ノードでScale40

0
64ノード

65536ノード

The	
  Graph500	
  	
  
	
  K	
  Computer	
  and	
  TSUBAME	
  2.0	  &	
  2.5
BFS performance on
TSUBAME2.0 and 2.5

Graph500 ranking history for
TSUBAME2.0 and 2.5
1400

List

Rank

GTEPS

Implementation

November 20114

99.858Top-down only

November 201220462.25GPU

June 2014

12

1280

Efficient hybrid

November 2014

??

1345

Efficient hybrid

1280

1200

GTEPS

1000
800
600

462.25400*Every score is obtained using TSUBAME2.0 1366 nodes or
TSUBAME 2.5 1024 nodes

Graph500 ranking history for
K Computer

200

317.0999.8580November June 2012 November June 2014
2011
2012

List

Rank

GTEPS

Implementation

November 2013

45524.12Top-down only

June 2014

1

17977.05

Efficient hybrid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

253

256

15363

15363

15363

K computer
17977

17977
3541

FX10

358 #3317 #4

#4

#4

#4

5524

5524

5524

993

1003

609
462

1280 CPU only
1003

462

462

16
4

44.0

100 #3
18
7

31.6

GPU

131.4
SGI UV2000

104.3
45.7

4-way Xeon server

CPU only

8.2

10.5

3.25

TSUBAME 2.5

TSUBAME-KFC

64

#1

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

The Graph500 List in June 2014
hDp://www.graph500.org	
• Measures performance using TEPS (# of Traversed edges
per second) in graph traversal such as BFS
Fastest	
  of	
  	
  
mulR-­‐node	

Distributed
MemoryDistributed
MemorySharedMemoryFastest	
  of	
  
	
  	
  	
  	
  	
  	
  single-­‐node	

Distributed
MemorySharedMemoryFastest	
  of	
  	
  
	
  	
  	
  	
  	
  	
  single-­‐server	BFS 性能	

BFS 電力性能	

アフィニティ設定毎の GTEPS	  と MTEPS/W
4-way Intel Xeon E5-4640 2.4GHz 上での数値実験	

• BFS	  性能	  GTEPS	
  と	
  BFS	
  電力性能	
  MTEPS/W	
  に共通する性質	
  – 同じスレッド数ならば、ソケット数は多いほうが良い	
  – 同じソケット数ならば、スレッド数は多いほうが良い	
  HTコアの使用は	
電力性能に効果がある	

Kronecker graph (SCALE27; 1.34 億頂点, 21.48 億枝)	25

Degree-aware (GTEPS)
Degree-aware (MTEPS/W)

20

Reference (GTEPS)
Reference (MTEPS/W)

15

NUMA-opt. (GTEPS)NUMA-opt. (MTEPS/W)

1060
64コア使用時には、	
どちらの実装も	
ほぼ同等の電力消費	

50
40
30
20

5

10

0

0

1⇥1
(1)

4⇥1
(4)

4⇥2
(8)

1⇥16
(16)

2⇥8
(16)

4⇥4
(16)

2⇥16
(32)

4⇥8
(32)

4⇥16
(64)

Degree-aware` ⇥ t CPU Aﬃnity (Number of threads)

w/o
(64)

4⇥16
(64)

Ref.

NUMA-opt.

MTEPS/W

GTEPS

30

64 スレッド (4-socket x 16-threads) で使用するソケット数を増やすと電力消費も増えるが、	
29.0 (MTEPS/W)
GTEPS と 45.43
を達成
それ以上の
TEPS の向上により
TEPS/W も改善する	Fig. 6. Performance(GTEPS)and Energy-eﬃciency
of MTEPS/W
our Degree-awareAndroid OS 上での数値実験	
• Android NDK (Native Development Kit) の利用	
– オーバヘッドの少ない C/C++ で実装可能（Java は速度的に不向き）	
– GCC をベースとしたクロス・コンパイラの提供	
– OpenMP によるスレッド並列計算 &高速な GCC 拡張のアトミック関数	

• Android	
  Developer	
  Tools	
  によるログイン・転送 	
Step2. バイナリの転送	
Step1. Android NDK による	
クロスコンパイル	
CC=arm-­‐linux-­‐androideabi-­‐gcc	
  “adb push” コマンド	

Step 2
p
Ste

Step3. Android Developer Tools	
によるログイン、Shell による操作	

スマートフォンSONY Xperia-A-SO-04E
CPU : 4-core Snapdragon
RAM : 2 GB

3

Step4. 実行結果の取得	
“adb pull” コマンド	“adb shell” コマンド	

Android Developers: http://developer.android.com. 	

d overheads of atomic operations, and as a result, we could achieve
mance even on Android devices, which do not have a NUMA arystem. This figure shows that the reference code causes performancen. In comparison, our BFS achieves a maximum performance of 477.63
a Kronecker graph with scale 20 on XperiaA SO-04E with 4 threads.

Xperia-­‐A-­‐SO-­‐04E	
  上での	
  BFS	
  電力性能	• 高速 (高性能) な実装が電力消費も良い
Android OS 端末でもある程度の規模まで扱える	

500

Reference (4)Our BFS (4)

400

MTEPS

1,048,576 (= 220) 点	
16,777,216 (= 224) 枝	cution, suggesting that the eﬀective power is not strongly aﬀected by th
of threads and the algorithm used. With regard to energy-eﬃcient com
100 倍以上の
our BFS is around 性能差
100 times faster than the reference code for rosame eﬀective power of 3.0 W; specifically, our BFS shows an energ
スマートフォン
performance of 153.17 MTESP/W.
SONY Xperia-A-SO-04E

300

200

100

CPU : 4-core Snapdragon
RAM : 2 GB

0
10

11

12

13

14

15

16

17

18

19

20

Numberof verticeslog (n) (SCALE)
Table
10.
Energyeﬃciency of BFS for Kronecker graph with on XperiaA
2Implementation SCALE MTEPS watt MTEPS/W. 5. MTEPS of reference BFS and our BFS on XperiaA SO-04E.
Reference (p = 1)20
3.25 3.15
1.03
Reference (p = 4)20
4.58 3.22
1.42This study (p = 1)
20
136.29 3.23
42.25
使用スレッド数と0 summaries the energy eﬃciency in
termsof MTEPS,
power 248.08 2.99
This
study
(p = 2) eﬀective20
82.92
電力消費の依存性は低い
MTEPS/W for BFS on a Kronecker
graph
with
scale
This
study
(p =
4) 20. The20table 477.63 3.12
153.17

all algorithms have an eﬀective power of around 3.0 W for BFS exe-

The Green Graph500 List in June 2014	

hDp://green.graph500.org	
• Measures power-eﬃciency using TEPS/W ratioBig	
  Data	  category	

Kyushu’s University
GraphCREST-SandybridgeEP-2.4GHz
is ranked

No.1
in the Big Data category of the Green Graph 500
Ranking of Supercomputers with59.12 MTEPS/W on Scale 30
on the third Green Graph 500 list published at theInternational Supercomputing Conference, June 23, 2014.
Congratulations from the Green Graph 500 ChairIntel	
  Xeon	  E5-­‐4640	
  

	
  	
  	
  	
  59.12	  MTEPS/W	
  (28.48	
  GTEPS)	

George Washington University’s
Colonial
is ranked

No.1
in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
445.92 MTEPS/W on Scale 20
on the third Green Graph 500 list published at theInternational Supercomputing Conference, June 23, 2014.
Congratulations from the Green Graph 500 ChairSONY	
  Xperia-­‐Z1-­‐SO-­‐01F	
  

	
  	
  	
  	
  235	
  MTEPS/W	
  (1.03	
  GTEPS)	

NVIDIA	  JetsonTK1	
  

	
  	
  	
  	
  204	
  MTEPS/W	
  (1.63	
  GTEPS)	

Small	
  Data	  category	グラフ解析と最適化の今後
九州大学「センター・オブ・イノベーション（COI）プログラム」

共進化社会システム創成拠点
Center  for  Co-‐‑‒Evolutional  Social  System

共進化社会システム創成拠点

実問題に対する大規模グラフ解析
超大規模ネットワークに対する探索アルゴリズムとクラスタリングアルゴリ
ズムの高速実装
数百万頂点〜数兆頂点、数億枝〜数百兆枝からなる超大規模なグラフ解析
数百万人の被災者の避難経路の計算では数千万頂点のグラフ(１スレッドあたりのメモリ要求量1Gbytes)に対して、同時に数百万スレッド単位で各被災者毎の最短路計算と各点の重要度判定

新しい産業応用の開拓 à １：ヒト/モノ ２：エネルギー ３：情報のモビリティ→
数理モデルとスパコンを用いた最適化 (整数計画問題に対する並列ソルバー等）
交通データに対する経路探索動的に変化する交通量等から高速な重要度判定を行い、交通管制等に活用ソーシャルネットワークデータに対する動的な重要度、影響度の判定各点の周辺、および広域内における影響（情報の伝播力）を推定

BODIC.org	
  (BigData	
  &	
  OpenData	
  in	
  the	
  Cloud)	
他情報システム

データサイエンティスト
データ解析
アプリケーション

解析ツール
レポジトリ

API

ビッグデータ

解析モデル
レポジトリ

ビッグデータ&オープンデータ
レポジトリ

クラウドIaaS(Infrastructure-as-a-Service)

センシング
データ
オープン
データ

47	

「ビッグデータ&オープンデータを活用した創業」支援策	
  [20140729PR]	
1.	
  福岡市が有するビッグデータ&オープンデータ活用基盤	

3.	
  人流センシングデータ活用で可能となる多様な創業	

BODIK	  (ビッグデータ&オープンデータ研究会	
  in	  九州)	  [例1]	  店舗向けリアルタイムマーケッティングサービス&
顧客向け店舗ナビゲーションサービスビジネス	[福岡市、URC、ISITが共同で昨年12月に発足]	

顧客の購買履歴や好み、店舗の品揃え、等に基づいたパーソ
ナル店舗ナビゲーション	

DSS4K	  (データサイエンススクール	
  for	  九州)	  [ISITが企画中]	

BODIC.org	
  (BigData	
  &	
  OpenData	
  in	
  the	
  Cloud)	
  [ISIT&九大共同開発中、本年10月からISITが運用開始予定]	
データ解析ツール	

データサイエンティスト	

周辺顧客の属性、購買履歴や好み、動線、等に基づいたリアルタイ
ムマーケッティング情報提供	

[例2]	
  スマーターモバイル”XXX”サービスビジネス	
人流に応じて様々な移動型（モバイル）サービスを提供	

データ貯蔵庫	センサーネットワーク	
福岡市オープン
データサイト	  [10月開設予定]	

業務	
  
データ	

2. 規制緩和でもっと容易になる「人流センシング」	
[現状]	
  携帯電話キャリア各社による位置情報収集	
  &空間統計情報提供	
基地局で収集した携帯端末の位置情報を基に空間統計情報を作成	例)	  NTTドコモ モバイル空間統計	

[規制緩和後]	
  Wi-­‐Fiアクセスポイントを用いた位置情報
収集&BODIC.org経由のリアルタイムな元データ提供	

３つの課題	
  1. キャリアが情報独占	
  2. リアルタイムでの情報提供は未実施	  3. 元データへのアクセス不可（統計情報のみ利用可）	

規制	
  
緩和	

Wi-­‐Fiアクセスポ
イントは、技術
的には周辺の携帯端末の識別情報（MACアドレス）が収集可能。しかし、現在は未活用（利用不可）	
※九大伊都で実証実験中	

２つの規制緩和案	
  1. Wi-­‐Fiアクセスポイント
での携帯端末識別情報収集を許可	  
2. 携帯端末所有者の合意の下、収集した識別
情報の元データの２次利用を可能に	
48	

グラフ探索及び数理最適化ライブラリによる大規模グラフ処理	

大	
 上層：NP	
  困難な最適化アルゴリズムの実行	  1. MIP(混合整数計画問題)の場合:	
  0-­‐1	
  整数変数の数 =	
  n	
  で計算量はおよそ O(2n)	
  2. 前処理による変数の削除と並列計算の適用（CPUコア中心の大規模スレッド並
列：分枝カット法の適用)	
  3. データ量は	
  105	  以下（整数変数の数)	
  4. 施設配置問題、集合被覆（分割）問題、スケジューリング問題などの最適化問題	
  小	

中層：多項式時間最適化アルゴリズムの実行	
  

ー
量

	

	

計
算
量

1. SDP(半正定値計画問題)の場合:	
  n	
  =	
  行列の大きさ,	
  m	
  =	
  制約式の数で計算量はおよそ O(n3	  	  +	
  m3)	  	
  2. 疎性の追求と前処理さらに並列計算の適用（CPUコア中心の大規模スレッド並列が中心だが、今後は	
  CPU	  +	  GPU	
  による高速化)	
  3. データ量は	
  108	  以下(非負変数の数)	
  ： 106	
  以下(制約条件数)	
  
4. グラフ分割、センサーネットワーク、サポートベクターマシンなどの最適化問題	
  下層：グラフ解析アルゴリズムの実行	  小	

1. ダイクストラ法(１対全最短路問題：ヒープ付き)の場合:	
  n	
  =	
  点数,	  m	  =	  枝数で計算量はおよそ O((n	  +	  m)log	
  n)	
  	
  
2. グラフ探索の局所的な評価では優先キュー(ヒープ木)を用いる⇒実行時間、メ
モリ消費量が安定的（CPUコア中心の大規模スレッド並列が中心だが、高速ス
トレージ技術による超大規模グラフ処理)	
  3. データ量は	
  1012～14	
  以下（グラフの点数と枝数)	
  4. 最短路計算、ネットワーク内での各点の重要度を推定。各点の周辺、及び広域内における影響（情報の伝播力)を計算	  大	

下層：グラフ解析アルゴリズムの実行	  1. ダイクストラ法(１対全最短路問題：ヒープ付き)の場合:	
  n	
  =	
  点数,	  m	  =	  枝数で計算量 O((n	  +	  m)log	
  n)	
  	
  
2. グラフ探索の局所的な評価では優先キュー(ヒープ木)を用いる⇒実行時間、メモリ消費量が安定的（CPUコア中心の大規模スレッド並列が中心＆高速ストレージ技術による超大規模グラフ処理)	
  3. データ量は	
  1012～14	
  以下（グラフの点数と枝数)	
  4. 最短路計算、ネットワーク内での各点の重要度を推定。各点の周辺、及び広域内における影響（情報の伝播力)を計算	
  

•
•
•
•

BFS(幅優先探索)	
  à	
  Graph500	
  :	
  京コンピュータ上で	  Scale	  40	
  (240点,	
  244	  枝）のグラフに対して 18	
  TeraTEPS	
  の性能	  (Top-­‐down	
  &	
  BoDom-­‐up	  	
  &	
  Level	  Synchronized	
  BFS)	
  	
  	
  Shortest	
  Path	  (最短路)	
  à	  IBM	
  BG/Q	
  上で	
  Scale	
  38	
  (238点,	
  242枝）のグラフに対して3.1TeraTEPSの性能(Delta	  Stepping	
  &	
  Bellman	
  Ford	  のハイブリッド)	
  à	
  静的なグラフに対してはHighway	
  hierarchies	  などの前処理が有効	
  Maximum	  Flow	
  	
  (最大フロー)	  à	
  Push	  Relabel	
  法の実装	  à	  最速フローに適用	
  à約4,588万点,	
  18,537万枝のグラフに対して最大フローの	  4〜5分の実行時間	
  Centrality	
  (中心性)	
  à	
  前処理や並列計算等も有効	
  
–
–
–
–

各点に接続されている枝数（Degree	
  Centrality）	
  各点が最短路に含まれる回数（Betweenness	
  Centrality）	
  最も遠い点までの最短距離（Graph	
  Centrality）	
各点までの最短距離（Closeness	
  Centrality）	
  • その他のアルゴリズムとツールも多数存在	
  
–
–
–
–

Minimum	
  spanning	
  tree	  ： 全域木	  Strongly	
  connected	
  component ： 強連結成分	
  Spectral	
  clustering ： グラフの行列表現(Laplacian	  Matrix)	
  à	
  固有値計算	  à	  クラスタリング 	
  51	
Hyper	
  ANF	  :	  Neighborhood	
  関数の近似 ： 点	
  x	
  から	
  t	
  hop	
  で到達する点	
  y	
  à	
  (x,y)	
  の計算	
  

グラフ探索及び数理最適化ライブラリによる大規模グラフ処理基盤••

大規模センサーから到着するストリーミングデータに対して精緻な解析を実現す
る大規模グラフ処理基盤を開発する
大規模グラフ処理基盤は以下の処理系から構成される–––

グラフ解析アルゴリズムの実行： 最短路計算、ネットワーク内での各点の重要度を推定。各点の周辺、及び広域内における影響（情報の伝播力)を計算 → 重要な要素を失うことなくデータ量を削減する
数理最適化アルゴリズムの実行： 施設配置問題、集合被覆（分割）問題、スケジューリング、配送計画問題などの数理最適化問題 → モビリティに関する改善提案
大規模なセンサーデータを高速かつ重要性を失うことなく縮約することよって、精緻な解析を実現• 計算及びデータ蓄積の基盤となる次世代スパコン– 並列数の爆発的増大、不均質化、高密度化 ＆ 記憶装置の多階層化・大容量化
大量のセンサー情報	
• ヒト
• モノ
• 情報	
• その他

グラフ解析アルゴリズムの実行とデータ量の削減	

数理最適化アルゴリズムの実行と評価	

データソース	

データソース	次世代スパコン(高密度演算装置＋階層型データストア）	
  数理計画問題（最適化問題）と2015年予想（目標）	
• 非常に応用が広範（企業、社会、公共政策）à	
  高性能なソルバーを作ること自体が最適化問題	
  • センサーデータによる最適化問題の複雑＆巨大化	  • 半正定計画問題(SDP)と混合整数計画問題(MIP)が２大注目数理計画問題	
  • 汎用ソルバーの必要性（個別の問題に対する仮定やチューニング
は効果が低い）	
  • 入力は疎データと密データの混合	  – 疎データ：多数のCPUコアによる処理（浮動小数点演算性能に非依存：密デー
タへ変換） à	
  GPU	
  系による処理	  – 密データ：GPU	
  系による処理	  – 理論的性能限界等からボトルネック箇所を特定	
  – 数値演算能力とメモリバンド等のトレードオフ関係を把握	  – 計算量とデータ移動量の正確な推定、疎性やサイズなどのデータ特性と性能値の見極め	
  

• 計算量とポストペタスパコンでの想定：	
  – 計算量O(n3)	
  à	
  数百万程度,	
  O(n	
  log	  n)	  à	
  100億以上,	
  O(n)	
  à	
  100兆以上