1 - GPU Technology Conference

Tegra K1 プロセッサ上での高速かつ
省電力なグラフ探索ソフトウェアの開発
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
Core Research for Evolutional Science and Technology
Core Research for Evolutional Science and Technology
2014年07月16日
NVIDIA GTC Japan 2014
Core Research for Evolutional Science and Technology
Core Research for Evolutional Science and Technology
Step2
グラフ
Input
parameters
generation
Graph construction
BFS
Graph
generation Graph
Graph
construction
グラフ解析
事象同士の関係 Step1
- SCALE
(Rela)onships)
応用分野
Input parameters
交通ネットワーク - SCALE
ソーシャルネットワーク Input parameters
- edgefactor
サイバーセキュリティ バイオインフォマティクス - SCALE
脳科学 - edgefactor
防災計画策定
Graph generation
- edgefactor
TwiDer
ソーシャルネットワーク
6,160万点　& 14億7千万枝 全米道路ネットワーク
2,400万点 & 5800万枝
Graph construction
BFS
Step3
分析と理解
解析結果
BFS
Validation
Validation
TEPS
ratio
TEPS
ratio
64
Iterations
Valida
-S
-e
Result
-B
-T
- SCALE - T
- edgefactor
- BFS Time
64 Ite
- Traversed
e
- TEPS
64 Iterations
•  並列グラフ探索 (幅優先探索) •  最適化 (最短路, 最大フロー, 最小費用フロー) •  クラスタリング (グラフ分割, コミュニティ抽出) ニューラル・ネットワーク @ Human Brain Project
890億点 & 100 兆枝
サイバーセキュリティ
150億/日 のアクセスログ 大規模グラフ解析：緊急に取り組むべき課題と実社会へのインパクト
防災計画策定
交通・災害復興・
避難・ロジスティクス
エネルギー・省電力
ソーシャル
ネットワーク解析
インターネットマップ
ニューラルネットワーク
ソーシャルネットワーク サイバーセキュリティ
交通(時空間)ネットワーク
スモールワールドやスケールフリー性などの特性を持つ超巨大グラフ　(1兆点以上) 上での高速探索技術（アルゴリズム、実装技術、高速計算）
45
京スパコン: 65536ノード Graph500: 17977 GTEPS
Human Brain Project Graph500 (Huge)
Symbolic
Network
Graph500 (Large)
1 兆枝
40
Graph500 (Medium)
グラフの枝数
35
(
m
)
l
o
g2
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
log2
(n)
グラフの点数
35
１０億点
40
45
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位
メモリ階層構造を考慮した大規模グラフ処理の高速化
日本数式処理学会
is ranked
No.1
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 the
International 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 the
International Supercomputing Conference, June 18, 2013.
Congratulations from the Green Graph 500 Chair
安井 (中央大学, CREST)
Chuo University’s
GraphCREST-Intel-NUC
is ranked
1位
2位
22 / 31
Chuo University’s
GraphCREST-Mac-mini
Chuo University’s
GraphCREST-MBA13
is ranked
Bottom-up 探索
Congratulations from the Green Graph 500 Chair
No.4
in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
53.472 MTEPS/W on Scale 24
on the first Green Graph 500 list published at the
International 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 the
International 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ツリーを検証）
1
3
始点をランダムに64個選択
64回
繰り返す
※CSR: Compressed Sparse Row, CSC: Compressed Sparse Column
6
Graph500技術の応用
Twitter ネットワークの解析
ユーザ 21,804,357 からの幅優先探索の結果
•  フォロー・ネットワーク
ホップ数
–  ユーザ数 （点数）
41,652,230
–  フォロー関係（枝数）2,405,026,092
•  Graph500 ベンチマーク
–  幅優先探索の性能「１秒間に通過し
た枝数 TEPS」を用いて、コン
ピュータの性能を比較する
–  同じコンピュータであっても、実行
するプログラムの性能で 100 倍差が
でることもある
合計
ユーザ数
割合 (%)
累積割合 (%)
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.00
41,652,230
100.00
-
0.069 秒で探索可能
21.28 GTEPS（109 TEPS）
MAT
R-MAT 67,108,864
A-road-d.NY
USA-road-d.NY
264,346
A-road-d.LKS
USA-road-d.LKS
2,758,119
A-road-d.USA
USA-road-d.USA
23,947,347
i-Talk
wiki-Talk2,394,385
Patents cit-Patents
3,774,768
-LiveJournal1
soc-LiveJournal1
4,847,571
tter-rv
twitter-rv
61,578,415
67,108,864
1,073,741,8241,073,741,824
26.00
16.00
26.00 (256,
16.00
2)
264,346
733,846
18.01
733,846 2.78
18.01 ( 64,2.78
4)
2,758,119
6,885,658
6,885,658
21.40
2.50
21.40 ( 64,2.50
4)
23,947,347
58,333,344 58,333,344
24.51
2.44
24.51 ( 64,2.44
4)
2,394,385
5,021,410
5,021,410
21.19
2.10
21.19 (256,16)
2.10
3,774,768
16,518,948 16,518,948
21.85
4.38
21.85 ( 32,32)
4.38
4,847,571
68,993,773 68,993,773
22.21
14.23
22.21 ( 32,32)
14.23
61,578,415
1,468,365,1821,468,365,182
25.88
23.85
25.88 ( 32,32)
23.85
18.604
(256,
0.012
( 64,
0.022
( 64,
0.072
( 64,
(256,1
0.476
0.754
( 32,3
2.642
( 32,3
5.796
( 32,3
Numerical results for real-­‐world networks
•  efficient for low-­‐diameter graph •  Not efficient for high-­‐diameter graph
instance
n
r
Kronecker
67,108,864
R-MAT 67,108,864
d-d.NY
USA-road-d.NY
264,346
d-d.LKS
USA-road-d.LKS
2,758,119
d-d.USA
USA-road-d.USA
23,947,347
wiki-Talk2,394,385
ts cit-Patents
3,774,768
ournal1
soc-LiveJournal1
4,847,571
twitter-rv
61,578,415
Table: ID 付け直し後
Table: ID 付け直し後
Less than 100 MTEPS for high-­‐diameter graph n m
log2 n m m/n
log2 n (α , βm/n
)
67,108,864
1,073,741,8241,073,741,824
26.00
16.00
26.00 ( 64,
16.00
4)
67,108,864
1,073,741,8241,073,741,824
26.00
16.00
26.00 (256,
16.00
2)
264,346
733,846
18.01
733,846 2.78
18.01 ( 64,2.78
4)
2,758,119
6,885,658
6,885,658
21.40
2.50
21.40 ( 64,2.50
4)
23,947,347
58,333,344 58,333,344
24.51
2.44
24.51 ( 64,2.44
4)
2,394,385
5,021,410
5,021,410
21.19
2.10
21.19 (256,32)
2.10
3,774,768
16,518,948 16,518,948
21.85
4.38
21.85 ( 32,4.38
4)
4,847,571
68,993,773 68,993,773
22.21
14.23
22.21 ( 16,
14.23
4)
61,578,415
1,468,365,1821,468,365,182
25.88
23.85
25.88 ( 32,32)
23.85
GTEPS
(α , β )
11.149
( 64, 4)
18.604
(256, 2)
(0.017
64, 4)
(0.030
64, 4)
(0.086
64, 4)
(256,32)
1.111
(1.178
32, 4)
(4.338
16, 4)
(8.055
32,32)
Exceed 1 GTEPS for low-­‐diameter graph 4-­‐way Intel Xeon E5-­‐4640 (SandyBridge-­‐EP arch.)
s
Our achievements : Graph500
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 #3
317 #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 mulJ-­‐node
Distributed
Memory
Distributed
Memory
Shared
Memory
Fastest of single-­‐node
Distributed
Memory
Shared
Memory
Fastest of single-­‐server
Graph500 June 2014 list
16384
8096
K computer
我々のエントリ (順位)
その他のエントリ (順位)
4
4096
2048
TSUBAME 2.5
1024
26
34
35
17
24
25
33
36
44
42
45
46
49 TSUBAME
50
51
56
GTEPS
512
256
SGI UV2000
128
4-way Xeon servers
64
52
54
55
57
64
32
16
8
81
4
100
101
106
2
1
128
26
58
59
60
61
62
68
69
74
77
76
75
89
91
85
86
95
92
109
104
105
110
112
124
125
139
30
116
116
120
122
129
132
107
111
113
122
127
130
133
137
27
28
29
12
3
70
71
72
78
79
37
39
96
103
31
32
73
82
88
90
5
FX10
15
23
38
47
48
-KFC
53
65
80
87
93
98
6
7
12
13
14
16
66
84
83
34
35
108
33
SCALE
36
37
38
39
40
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 論理コア）
ローカルメモリ
RAM
shared L3 cache
リモートメモリへのアクセス（アクセスコスト大）
8-core Xeon E5 4640
データアクセスが不均一であるため
•  並列時の偏りが生じるため、並列効率を向上することが難しい
•  本来の性能を予想することが難しい
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)
10
60
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 Affinity (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-efficiency
of MTEPS/W
our Degree-aware
NVIDIA Tegra3 タブレット上での Green Graph500
•  ASUS Pad TF700T
– 
– 
– 
– 
NVIDIA Tegra 3 mobile processor (4cores), 1GB RAM
消費電力: 2.44 W (動画再生時)
SCALE20 (点数 220, 枝数 224) の Kronecker graph に対し幅優先探索を 0.11 秒で実行
64.119 MTEPS/W (154 MTEPS) を達成し、1st Green Graph500 で 1 位を獲得
•  C 言語で実装し Android NDK で(クロス)コンパイル
–  基本的に Linux だが、ポーティングにはいくつか修正が必要
–  スレッド並列計算のために OpenMP を有効にする
–  サポートしていない atomic 関数の書き直しを行う
•  Graph500 提出には SCALE 20 以上が必要
–  SCALE 20 には 1GB RAM が必要
–  搭載メモリが全て使えないためメモリ確保が失敗する
–  省メモリ化を行い 714MB に抑えた
Chuo University’s
GraphCREST-Tegra3
is ranked
•  実行方法により性能が異なる (未確認情報含む)
–  タブレットに仮想端末アプリでログイン
–  ssh によるログイン
–  PC と USB 接続し adb コマンドでログイン
並列計算が無効？
ssh のオーバーヘッド
並列計算が有効
No.1
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 the
International Supercomputing Conference, June 18, 2013.
Congratulations from the Green Graph 500 Chair
Graph Green500 List (June 2013) 各 BFS の終了時に, 計算結果である BFS 木を用いて検証を行い, TEPS 値を算出する.
現在のルールでは, 64 回中 Medial の TEPS 値で評価を行い, 高い方がより高い順位となる.
hDp://green.graph500.org GreenGraph500
⃝ 有効電力あたりの BFS 探索性能「GTEPS/kW」で評価
RemotePDU: Omron RC3008
測定機器の解像度が荒くうまく測定できない場合, 指定した時間 BFS を繰
り返し計算する energy loop を追加.
the Small Data category
• 
Rank MTEPS/W Site • 
Graph&
Graph&
Machine Genera)on
Construc)on
BFS GTEPS Valida)on
Scale Nodes 1 64.12 Chuo University GraphCREST-­‐Tegra 20 0.15 1 2 53.82 Chuo University GraphCREST-­‐Intel-­‐NUC 23 1.08 1 3 53.47 Chuo University GraphCREST-­‐Mac-­‐mini 24 1.94 1 52.02 Chuo University GraphCREST-­‐MBA13 23 1.23 メモリ階層構造を考慮した大規模グラフ処理の高速化
1 5 51.62 Chuo University GraphCREST-­‐ReJna15 24 1.99 1 6 39.29 Changsha, China TH-­‐IVB-­‐FEP/C 1 4 安井 (中央大学, CREST)
26 9.74 上位を独占
日本数式処理学会
19 / 31
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” コマンド
スマートフォン
SONY Xperia-A-SO-04E
CPU : 4-core Snapdragon
RAM : 2 GB
Step 2
p3
Ste
Step3. Android Developer Tools
によるログイン、Shell による操作
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 performance
n. 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 effective power is not strongly affected by th
of threads and the algorithm used. With regard to energy-efficient com
100 倍以上の
our BFS is around 性能差
100 times faster than the reference code for ro
same effective 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
Number
of vertices
log (n) (SCALE)
Table
10.
Energy
efficiency of BFS for Kronecker graph with on XperiaA
2
Implementation 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.42
This study (p = 1)
20
136.29 3.23
42.25
使用スレッド数と
0 summaries the energy efficiency in
terms
of MTEPS,
power 248.08 2.99
This
study
(p = 2) effective20
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 effective power of around 3.0 W for BFS exe-
The Green Graph500 list in Nov. 2013
hDp://green.graph500.org
•  Measures power-­‐efficiency using TEPS/W raJo •  Results on various system such as TSUBAME-­‐
KFC Cluster and Android mobiles Big Data category
TSUBAME-­‐KFC 6.72 MTEPS/W (44.01 GTEPS)
Small Data category
SONY Xperia-­‐A-­‐SO-­‐04E 153 MTEPS/W (0.48 GTEPS)
Tegra K1 (Jetson TK1) での Graph500 & Green Graph500
高いTEPS 値: 1.64GTEPS à Intel Core i3 に相当 非常に高い電力性能 200MTEPS/W を超える à Android モバイル機器に匹敵
Submission Type: Both Number of nodes: 1 Number of cores: 5 (4) Main memory size: 2.0 gigabytes Total system power (Kernel 1, BFS): 8.0 WaDs Total system power (Kernel 2, SSSP): 0.0 WaDs Graph 500 implementaJon used: Custom (OpenMP, Degree-­‐aware BFS) SCALE 21 Kernel 1 (BFS) GTEPS: 1.635028 Kernel 2 (SSSP) GTEPS: 0.0 Graph construcJon Jme: 40.153 seconds à 204.38 MTEPS/W NVIDIA JETSON TK1
•  Tegra K1 SOC
32-bit, 2.3 GHz
low power
–  CPU : NVIDIA 4-Plus-1 quad-core ARM Cortex A15 + Companion core
–  GPU : 192 CUDA core NVIDIA Kepler
1.64 GTEPS
•  2GB RAM
1.8
1.6
1.4
CPU
CPU
CPU
CPU
only
only
only
only
204.4 MTEPS/W
(1)
(2)
(4)
(4)
(64-bit)
(64-bit)
(64-bit)
(32-bit)
Tokyo’s Institute of Technology
EBD-GoldenBox-Prototype
CPU Only
is ranked
Using
32bit int.
No.4
x2.7
Future work: CPU/GPU Hybrid
GTEPS
1.2
in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
204.38 MTEPS/W on Scale 21
on the third Green Graph 500 list published at the
International Supercomputing Conference, June 23, 2014.
Congratulations from the Green Graph 500 Chair
1.0
x1.8
#4 in June2014 list
0.8
0.6
x1.0
0.4
0.2
Kronecker graph with SCALE 21
1M (220) vertices and 16M (224) edges
0.0
18
19
20
SCALE
21
NVIDIA JETSON TK1
Mobile Embedded Supercomputer
The Green Graph500 List in June 2014
hDp://green.graph500.org
•  Measures power-efficiency using TEPS/W ratio
Big 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 with
59.12 MTEPS/W on Scale 30
on the third Green Graph 500 list published at the
International Supercomputing Conference, June 23, 2014.
Congratulations from the Green Graph 500 Chair
Intel 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 the
International Supercomputing Conference, June 23, 2014.
Congratulations from the Green Graph 500 Chair
SONY Xperia-­‐Z1-­‐SO-­‐01F 235 MTEPS/W (1.03 GTEPS)
NVIDIA JetsonTK1 204 MTEPS/W (1.63 GTEPS)
Small Data category