科 学 技 術 計 算 分 科 会

選 出

SS 研 HPC フォーラム 2014 より新ベンチマークプログラム：
HPCG の概要と「京」における性能

南 一生(理化学研究所)

サイエンティフィック・システム研究会

2014 年 8 月 26 日

SS 研 HPC フォーラム 2014 資料

新ベンチマークプログラム：
HPCG の概要と「京」における性能
南 一生
独立行政法人 理化学研究所(計算科学研究機構)[アブストラクト]
世界で最も高速なコンピュータシステムの上位 500 位までを定期的にランク付けし、評価するプロジェクトとして、TOP500 がある。TOP500 プロジェクトは、1993 年に発足したが、用いられているベンチマークプログラム：LINPACK が、浮動小数点演算性能の評価に重きを置いているために、近年、実アプリケーションとの乖離が指摘されることもあった。
そこで、LINPACK の開発者である J. Dongarra 博士より、実アプリケーションで使われる計算手法の性能評価に重きを置いたベンチマーク・プログラム:HPCG が提案されている。２０１４年６月に開催された ISC14 において、正式なランキ
ングではないものの、世界のトップクラスのスパコンを含む HPCG のランキングのミニリストが発表され、日本の「京」が２位に位置づけられた。本講演では、HPCG の概要および「京」における性能について報告する。

[キーワード]スーパーコンピュータ、ベンクマーク、共役勾配法、チューニング、HPCG

1. はじめに
世界で最も高速なコンピュータシステムの上位 500 位までを定期的にランク付けし、評価するプロジェクトとして、TOP500 がある。独立行政法人 理化学研究所と富士通で共同開発した、スーパーコンピュータ「京」は 2011 年
６月の TOP500 で１位を獲得し、その後 2011 年 11 月の SC11 でも１位をキープした。2014 年の現時点では４位の位置につけている。
TOP500 プロジェクトは、1993 年に発足したが、用いられているベンチマークプログラム ：LINPACK は、密行列に対する並列の連立一次方程式の直接解法であり、行列・行列積の計算が主である。したがって LINPACK
は、浮動小数点演算性能の評価に重きを置くことになり、近年、実アプリケーションとの乖離が指摘されることもあった。そこで、LINPACK の開発者である J. Dongarra 博士より、実アプリケーションで使われる計算手法の性能評価に重きを置いたベンチマーク・プログラム:HPCG が提案されている。

2. HPCG(High Performance Conjugate Gradient)とは実アプリケーションで良く使われる連立一次方程式の解法として、疎行列に対する反復解法がある。その中でも前処理付き共役勾配法(PCG 法)は、一般的によく使われる手法である。HPCG は前処理として、ガウス・ザイデ
ル法をベースとしたマルチグリッド法を採用している。
計算科学的な特長から言うと、HPCG は、疎行列・ベクトル積であり、アプリケーションが要求する B/F 値が大きいタイプの計算となる。そのために CPU 単体性能が出しにくいアプリケーションである。また、リストベクトルを使用するため、通常の要求 B/F 値が大きいアプリケーションより、さらに性能が出しにくい。この意味では、要求
B/F 値が小さい LINPACK とは、対極にあるベンチマークプログラムであると言える。

3. HPCG ベンチマークプログラムの概要
HPCG ベンチマークプログラムは非構造格子を扱うことができるプログラムとなっているが、実際のベンチマーク
データは、構造格子である。プログラム内で構造格子をリストアクセスすることにより、非構造格子のように処理している。ベンチマークのセットアップ段階で、このようなメッシュの作成をプログラムの内部で行っている。次の段階で、プログラムのチューニングや行列の最適化に問題がないか検証を行う。計測フェーズの最初に、オリジナ
ルの処理とチューニング後の処理の実行時間の差を検証し、計測のためのパラメタを決定している。その後、計測フェーズを実施する。最後に、レポート出力フェーズを実施する。ここで、検証フェーズに問題があった場合は、不合格となる。

4. HPCG のチューニングと性能
まず、HPCG ベンチマークプログラムが大規模並列に対応可能なようにプログラムの修正を実施した。その後デフォルトで設定されている問題を使用し 32000 ノードまでのウィークスケーリング測定とコスト分析を実施した。ウィークスケーリングについては良好であり、また、通信時間は６%程度であった。さらにマルチグリッド前処理と行
列・ベクトル積の処理のコストが大きいことが分かった。特にマルチグリッド前処理については、ガウスザイデル法
をベースとしているため、オリジナルコードのままではスレッド並列化ができない。そこで今回は節点データをカラーリングにより、リオーダリングすることでスレッド並列に対応した。その結果、CPU 単体性能として、オリジナル
プログラムの 19.2 倍、フルノードまでの良好な並列性能を達成した。
上記の結果、２０１４年６月に開催された ISC14 において、正式なランキングではないものの、世界のトップクラスのスパコンを含む HPCG のランキングのミニリストが発表され、0.427Pflops の性能で日本の「京」が２位に位置づけられた。「京」が達成した性能は、他のスパコンとピーク性能比で比較すると、群を抜いている。これは、「京」の良好な性能バランスとアプリケーションのチューニングの努力によるものである。

[参考文献](1) Hasegawa, Y., Iwata, J.I., Tsuji, M., Takahashi, D., Oshiyama, A.,Minami, K., Boku, T., Shoji, F., Uno,
A., Kurokawa, M., Inoue, H.,Miyoshi, I., Yokokawa, M.: “First-principles calculations of electron statesof a silicon nanowire with 100,000 atoms on the K computer.”，Proceedings of 2011 International
Conference for High Performance Computing, Networking, Storage and Analysis. pp. 1:1–1:11. SC ’11,
ACM, New York, NY, USA (2011)(2) 黒田 明義, 長谷川 幸弘, 寺井 優晃, 井上 俊介, 市川 真一, 小松 秀実, 大井 憲行, 安藤 琢也, 山崎 隆
浩, 大野 隆央, 南 一生. :"ナノ材料第一原理分子動力学プログラム PHASE の京速コンピュータ「京」上の計算性能最適化"，ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集, pp.144-152(2012)(3) 南 一生，井上 俊介，堤 重信，前田 拓人，長谷川 幸弘，黒田 明義，寺井 優晃，横川 三津夫.："「京」コンピュータにおける疎行列とベクトル積の性能チューニングと性能評価"ハイパフォーマンスコンピューテ
ィングと計算科学シンポジウム論文集, pp.23-31 (2012)(4) Kiyoshi Kumahata, Shunsuke Inoue, Kazuo Minami.: Kernel performance improvement for the FEM-based
fluid analysis code on the K computer,Procedia Computer Science,Volume 18, 2013, Pages 2496–
2499,2013 International Conference on Computational Science(5) 井上俊介, 堤重信,前田拓人,南一生.:スーパーコンピュータ「京」におけるメモリインテンシブな アプリケー シ ョ ン の 評 価 お よ び 高 性 能 化 , 先 進 的 計 算 基 盤 シ ス テ ム シ ン ポ ジ ウ ム SACSIS2013 論 文集,pp,123(2013)(6) Masaaki Terai, Eiji Tomiyama, Hitoshi Murai, Kazuo Minami and Mitsuo Yokokawa.: "K-scope: aJava-based Fortran Source Code Analyzer with Graphical User Interface for Performance Improvement",
Third International Workshop on Parallel Software Tools and Tool Infrastructures (PSTI2012).

?=>A年E月?C日研フォーラム

新ベンチマークプログラム：
HPCGの概要と「京」における性能
理化学研究所 計算科学研究機構
運用技術部門 ソフトウェア技術チーム
南一生

           ?
OUTLINE?=>A年E月?C日研フォーラム• ŠŏŨŞƧ
• ǈǆǊǌƾǀǇƧ
• ǅǌǀǄśŠƧ
• ǅǌǀǄƗƦƊƘĹŽƖƥžơƚƧ
• ǅǌǀǄşƊƞĹƐƦžś¤ñ

年月日研フォーラム@?=>A年E月?C日研フォーラムはじめに

年月日研フォーラムA
スパコン世界一をめぐる競争?=>A年E月?C日研フォーラム

スパコン世界一の推移

A*cjnl&.Sequoia「京」 Titan 天河2

A
A@@@



A@@



A@



A



A@@@



A@@



A@



平均すると1年に約1.9倍の性能向上！
「京」は、世界初のスパコンCRAY-1（1976年）の約7000万倍！
年月日研フォーラム

ちなみに?=>A年E月?C日研フォーラムB
世界初のスパコンCRAY-1の演算性能は、約160メガフロップス
一方、iPhone4Sの演算性能は、約140メガフロップス

AEDC

B@AA
b

年月日研フォーラムC
最近のスパコンランキングの推移?=>A年E月?C日研フォーラム

Jun. 2011>

Nov.2011>

Systemcountry

PFLOPS

Systemcountry

1

K computerJPN> 8.16

K computer
JPN

2

TianheA
CHN

> 2.57

TianheA
CHN

3

JaguarUSA

1.76

JaguarUSA

4

Nebulae
CHN

1.27

NebulaeCHN

5

TSUBAME2.0
JPN

> 1.19TSUBAME2.0
JPN

>
>

Jun. 2012>

PFLOPS

Systemcountry> 10.51

SequoiaUSA> 2.57

K computer
JPN

>

PFLOPS>

SystemcountryJun. 2014>

PFLOPS

Systemcountry

PFLOPS

Titan
USA

17.59

Tianhe-2(CHN)> 10.51

SequoiaUSA> 16.32

Titan
USA

17.59

8.16

K computerJPN

> 10.51

SequoiaUSA> 17.17

8.16

K computer
JPN

>

Mira
USA

1.27

SuperMUC
GER

> 1.19TianheA
CHN

>Jun. 2013〜> 16.32

1.76>

Nov. 2012> 2.90

Mira
USA

>

> 2.57JUQUEEN
GER

> 4.14> 33.86

>

>

Mira
USA

> 10.518.59

年月日研フォーラム

D?=>A年E月?C日研フォーラム

LINPACK

年月日研フォーラム

High Performance ?=>A年E月?C日研フォーラム
LINPACK(HPL) E
5 世界で最も高速なコンピュータシステムの上位位までを定期的にランク付
けし、評価するプロジェクトとして がある
5 B==は、米国のテネシー大学の 博士によって開発された密行列計

算による連立一次方程式を解くベンチマーク・プログラム：

 が用いられている
5

 を用いたB==プロジェクトは、年に発足

5 が浮動小数点演算性能のベンチマーク・テストに重きを置いている

年月日研フォーラム

HPLのプロセス分割
F?=>A年E月?C日研フォーラム「京」の例
N(8-"+l)p(1 vll



)

































N

q(1 vl
l0)nb( v

l1f6.io0m )



nb

年月日研フォーラム

HPLの計算手順>=?=>A年E月?C日研フォーラム(1)Lパネル分解

p(2) 分解済みLパネル放送

nb

p

q

DTRSM
(三角行列計算)nbq>G[[XSaYW_>

0>QZ^W[Z\W>
T_]_VUS`a(3)Uブロック行放送とPivot行交換
p
nb
q

>
QZ^W[Z\W>
T_]SVUS`a>G[[XSaYW_

年月日研フォーラム

HPLの計算手順>>?=>A年E月?C日研フォーラム(5) 列パネル更新(4) Uブロック分解

p

p

nb

nb
q

q

DTRSM
(三角行列計算)

DGEMM(行列行列積計算)の計算

この更新計算が計算時間の大半を占める年月日研フォーラム>?
TOP500ベンチマークの成功と失敗?=>A年E月?C日研フォーラム

6:7HPCG WorkShop,?B. &.?=>A.Bethesda, MD開催より• ¥RƧ– ŰņŭŪŐōƧ
– ƄƅƌƚaË¤ñśş±>¹*Ƨ

• ĚÌâƧ
– xĚÌśşĲĥƧ• õ¿ŎřƲưðŇ?Ƨ• xcşųƖƢſĹƄƠƦŚ2ŨŬůŮ¤ñġDśşĲĥƧ

• ǏǪǫǥǪƧǤǘǚǟǠǥǜşõűÖŐŮƧ– ÖŐŉŮxYr)Ƨ
• ãÓņŬşxYŝŜxYr)ÎűEçÓ
年月日研フォーラム>@?=>A年E月?C日研フォーラム

HPCGとは

年月日研フォーラム>A
HPCGベンチマークの提案?=>A年E月?C日研フォーラム

6:7HPCG WorkShop,?B. &.?=>A.Bethesda, MD開催より• ƗƦƊƘĹŽuÆşƧ– ǅǌǀǄƩǅǠǞǟƧǌǜǨǝǦǨǤǘǥǚǜƧǀǦǥǡǫǞǘǪǜƧǄǨǘǛǠǜǥǪƪƧ
– ǒǜǨǩǠǦǥƧƲşƧ• ǐǋǌƵưưśş*<Ƨ– Ðň'ńŮũşŚŠŝłƧ
• ǐǋǌƵưưşƢƅƎŞĭűØŎřǅǌǀǄƅƀųũĂtŐŮŝŜşŁŭƧ• ǓǏhzşŝņŚŠĢÞŞÐň'ńŮŤňśłŃ FũŁŗŔ

年月日研フォーラム

>B
連立一次方程式と共役勾配法(CG法)?=>A年E月?C日研フォーラム^ şūŃŝľsGşĩ ŚĀĊĒÝvűŊśŐŮĵƧ
ĬśŎřĿâ_ĊŚ_ĊĵGşĀĊĒÝvŠĴ_ĊŞūŭĮħsĒÝvű
ŊpŞ/Òĵ

Ax = bf (x) =

1 2
ax − bx2

f(x)の最小値問題

1
f (x) = (x,Ax)(x,Axx) − (b,x)
2∂ f (x) 1 n
1 n= ∑ aikk xi + ∑ akjk x j − bk
∂xk
2 i=1
2 j=1

f '(x) = ax − b = 0

本式を解く事と同値∂ f (x) n= ∑ aki xi − bk = 0∂xk
i=1
年月日研フォーラム>C
共役勾配法(CG法)?=>A年E月?C日研フォーラム1
f (x) = (x,Ax) − (b,x)
2ǀǄēųƣƁƢƆƚş-Ĕ>ĵƧ
ŌşÃŞųƣƁƢƆƚşò¨>ŁŭĵƧ
ǝƩǭƪŇaÏŇêŬůŮūŃŞǭǠşĭ
ű2ŨŮĵƧ
ǨǠƧŠj_ƗŽƎƣŚŁŭOłŞ×QŎ
sìħŚŁŮĵƧ
j_ƗŽƎƣŠǊGşĮħsĒÝvŞŠǊLŎņÂdŎŝłĵƧ
ǊGşĮħsĒÝvŠ[ĸǊşù
ĈŚ~½ŐŮĵƧ
ťŔƾşNĝÏŇŎřłŮņėŎřłůš~½ŇÀŊŝŮ¤wűqŘĵ
年月日研フォーラム

>D
前処理付き共役勾配法(CG法)?=>A年E月?C日研フォーラム

M = UT U

Ux = xU −T b = bƾŞ7ł§ÏÇYĭƺǉűXńƀƤƅŻĹ
ĊŐŮĵƧ
ŌşūŃŝǭƬǙƬƾşÐň'ńűYŃĵƧ


U −T AU −1 = A

 = U −T AU −1 ≈ I
AÐň'ńŔƾş¤wŠÍ YĭŞ7łĵƧ
Ðň'ńŔYĭƾşNĝÏŠƱşŭŞėŎřłŮƧ

 x = bAÐň'ńŔYĭśƗŽƎƣŞÇŐŮĮħsĒÝvş~½Š¸łũşś.Èĵ

この前処理により法が広く使用されるようになった年月日研フォーラム>E
前処理付き共役勾配法(CG法)?=>A年E月?C日研フォーラムă&³ƀƤƅŻĹĊŞūŮ²ĤǀǄēųƣƁƢƆƚş-Ĕ>ĵƧ
@iŠYĭƗŽƎƣ©ĶƗŽƎƣƅŹơ©ĶƗŽƎƣşıĶí©ĶiŚW¥ōůŮĵƧ
ª±ŚtŎŔ²ĤćĊŠ²ÊïĶPÉÊïŚ@iōůŮĵ
ステップ1:

αk = (rik •(LL T )−1 rik )/(Apik • p ik )ステップ2:

xi = xi +α pi

ステップ3:

ri k+ 1 = ri k − αk Apik

ステップ4:

β k = (rik+1 •(LLT ) −1 rik+1 ) /(ri k •(LLT ) −1 rik )ステップ5:

pi = (LL ) ri + β pi

k+ 1

k+ 1

k

k

k

T −1 k+1

k k年月日研フォーラム

>F
前処理としてのマルチグリッド法?=>A年E月?C日研フォーラム

連立一次方程式の解法としてのマルチグリッド法の例
Rytv~w
qtw
qt

x|w

年月日研フォーラム?=
前処理としてのマルチグリッド法?=>A年E月?C日研フォーラム

連立一次方程式の解法としてのマルチグリッド法の例(NPB MG)
ƘƣƊžƢƋƏũYĭƗŽƎƣ©ş@iŇÓ

Rytv~w
qtw
;1:

fk = Rk+1→k fk+1
fk−1 = Rk→k−1 fk
fk−2 = Rk−1→k−2 fk−1
f1 = R2→1 f2
x|w

Ak+1uk+1 = rk+1

rk+1 = fk+1 − Ak+1uk+1

uk+1 = Rk→k+1uk

Ak uk = rk 75$5
rk = fk − Ak uk #6.

uk = Rk−1→k uk−1 91:
年月日研フォーラム

?>
LINPACKとHPCGの単体性能比較?=>A年E月?C日研フォーラム

High Performance

A Processor Performance

OMPQGINF>>

0?

uz uw/@

3$H?JfhsfzA

3$H?Jfdfsf2<

B

3$H?Jf=d

C

3$H?Jf=h{rv}{p'

0

,k

ge/

4!0 l8-"+l )5%>0 0 ,l6.fLQIKF>
4!(0 l8-"+l 5%>(0 v,fLow Performance年月日研フォーラム??

?=>A年E月?C日研フォーラム

HPCGベンチマークプログラム

年月日研フォーラム

?@

HPCGベンチマーク?=>A年E月?C日研フォーラム• ĮħsĒÝvƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧű²ĤĄǀǄēŚŊcş¤ñűƗ
Ax = bƦƊƘĹŽƧ
– ²ĤŠǒǜǨƮƲƮưZŠǉǫǣǪǠƭǄǨǠǛēűbĠ
ƩǒǜǨƱƮƱťŚŠǄǘǫǩǩƭǏǜǠǛǜǣēƪƧ• <¢YĭƾŠĝKġµēşYĭƧ– ´ŚÇƧ– 9ÆÞŞŠ×ĒÆĩ

ű0¼ÞŞĊ%ŎŔũşƧ• ëÔƧ– ǈǆǊǌƾǀǇśþŎřÙĶƛƜƢųŽƇƅşþŇ[łƧ– ƛƜƢųŽƇƅŠƢƅƎųŽƇƅŚŁŭĴūŭ[łƛƜƢ¤ñŇāġƧ
– ǀƫƫŚņůřłŮŇďģŝǀśŎřŎņkŗřłŝł
年月日研フォーラム

?A

前処理

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム
初期化• ËťņŞƴŘşćĊŞĊŋŬůŮƧ

&$!"()%'

²ĤƧ
• ƛƜƢ#ĐŝŜş.Ƨ• ĚÌ¬ÚĴYĭşaßƧ

検証! ( $#'( #'&#% J  " #'

ĳĳĳEƧ• ƟĹƃĹƊƞĹƐƦžş§å¤EƧ• fÄŝƍĹƉ¾ÚƧ&# " #'

測定

%( " -()%'

後処理

%( " - " #'
%$&(')!('

¾ÚƧ
• xYr)şĞ¾Ƨ
• Ĕý¾ÚƧƩƱr)ƪƧ
PĤƧ

PĤ
ここでは各部分の主要な処理に• Bű¦ĤŎÜŐŮƍĹƉűe¥ついて紹介年月日研フォーラム

?B

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム• 各軸に割り当てるプロセス数の決定

前処理

初期化

#&($"(&,67関数
• 連立方程式+Lを作成

&$!"()%'

#&(&$!"67関数
••! ( $#'( #'

行列をプロセス内ローカルなものに変換
袖通信用の通信相手の情報を作成

検証()%!$67関数

&#% J  " #')!( 3& のデータ構造を作成•

#&($&'&$!"67関数

&# " #'•

ユーザー定義のデータ最適化
%( " -&$!"67関数

%( " -()%'

測定

標準では何もしない
これを独自に実装して%( " - " #'

最適化を行う

後処理

所要時間は計測される

%$&(')!('
年月日研フォーラム?C

GenerateProblem
関数の処理?=>A年E月?C日研フォーラム
連立一次方程式+Lを設定する 6この時点ではグローバルな節点番号で作成7
AE

=

A?

>

?A

@K@K@節点
?プロセスの場合-

節点番号は+N,N-の順
②行の内容
列番号
値

?B

>E

>F

C

+

=

>
Oと隣接

?

節点Oに

?F
?@

>B

E

@B

?E
??

>A

D

@A

?D

?>

>@

A>

@@

Oと隣接

?=

>?

,

?C

AD

A=

@?

B@

AC

@F

@E
@>

B?

AB

AA

@D
@=

B>

B=

A@

@C

例7

に動く

AF

>C

F
@

>D

>=
A

>>
B

相当する
行に着目

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ･･･ 53-1 26 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
赤字は外部節点への参照

実際の格納形式  形式
・・ 26 27
非ゼロ番号 0 1 2 3 4 5 6 7 8 9 10 11 12 ・
・
・
・
列番号
1 2 3 7 8 9 19 20 21 25 26 27
・・・値-1 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

非ゼロ個数は 27個/行 に固定
global_int_t型(実体はint)
doulbe型
年月日研フォーラム

?D

GenerateCoarseProblemの処理?=>A年E月?C日研フォーラム
用の粗いメッシュに対応する係数行列を作成
初期メッシュ

粗いメッシュ

粗い格子は@レベル作成しての節点数を>2?にして合計Aレベルの格子データ作成プロセスを先頭から再度呼ぶ

データ作成
プロセス




 


行列データの構造体

行列データの構造体

格子の情報

格子の情報

• の節点数• のプロセス形状
• (





 


行列の情報


 
 

• 行数，行毎の非ゼロ数
• 列番号，非ゼロ値
• (

行列の情報


 
 

袖通信の情報 

• 隣接数
• 隣接相手• 送信節点情報



 
   

粗い行列データへのポインタ
細MN粗間の節点対応表• の節点数• のプロセス形状
• (• 行数，行毎の非ゼロ数
• 列番号，非ゼロ値
• (
袖通信の情報 

• 隣接数
• 隣接相手• 送信節点情報



 
   

粗い行列データへのポインタ
細MN粗間の節点対応表
年月日研フォーラム

?E

前処理

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム
初期化
&$!"()%'

検証! ( $#'( #'&#% J  " #'&# " #'

測定

%( " -()%'

後処理

%( " - " #'
%$&(')!('

演算関数は

基準版?種類存在
チューニング版

$"%)(4&67
標準では単にラッパー$"%)(67ŹĹƑƣşƊƞĹƐƦžŪYĭşaßŇ§ŎłņűƊŷƋŽƧ
ǐǜǩǪǀǄƩƪƧ
• ƊƞĹƐƦžúǀǄ*¢ŞĴ4ŊÇ$Ĝ ŝYĭűğńřĴ0Ý¢Ś~½ŐŮņűøÚƩ~½øÚÏƱƮưļƱưƭƱƲƪƧ
• ²ĤŝŎŝŬƱƲíƧ• ²ĤŁŭŝŬƲíƧ

DŠƧ
AŨÅŖ

ǐǜǩǪǏǮǤǤǜǪǨǮƩƪƧ
• ǋǧǪǠǤǠǯǜǌǨǦǙǣǜǤƩƪŚaßŎŔYĭŇÇ
ŞŝŗřłŮņƊŷƋŽ
年月日研フォーラム

?F

前処理

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム
初期化- úşǏǌǉǒƩ´YĭƗŽƎƣ©ƪśǉǄƩǉǫǣǪǠƭ
ǄǨǠǛƪ*¢şxYr)ű@¾Ƨ

&$!"()%'ǀǦǤǧǫǪǜǏǌǉǒǗǨǜǝƩƪƧ
• - úş´YĭƗŽƎƣ©ĳĳƧ&# " #'ŌşrşǏǌǉǒśǉǄşƱåŭşċ5r)ű2
ŨŮƧ

%( " -()%'ǎǜǧǦǨǪƧǎǜǩǫǣǪćŚƧ
ĳƧǋǧǪǠǤǠǯǜǌǨǦǙǣǜǤƩƪşr)śĴŌşċ5ĳƧr)śşþƧ
űĪŎřłŮ

%( " - " #'

後処理

>=回

ǀǦǤǧǫǪǜǉǄǗǨǜǝƩƪƧ
• - úşǉǄƧ

&#% J  " #'

測定検証

! ( $#'( #'

%$&(')!('
年月日研フォーラム

@=

前処理

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム
初期化
&$!"()%'

検証! ( $#'( #'ƊƞĹƐƦžúǀǄűƱxYŎĴġŎŔr)ű¾ÚƧ&#% J  " #'

測定&# " #'
%( " -()%'>回実行時間後処理

%( " - " #'ǀǄƩƪƧ• ƊƞĹƐƦžúǀǄƧ• ùĈKŠƵưư~½øÚŠǀǄǗǨǜǝƩƪűxYŎř2ŨŔǨǜǝǗǪǦǣǜǨǘǥǚǜƩƱƮưǂƭƳÝäƪĳƧ• ƱŕŋxYƧŌşr)űGŞĴsşƔŷĹƆŚǀǄƩƪűxYŐŮņűAÚ

%$&(')!('?=>A年=@月>?日6水7

の京における状況説明年月日研フォーラム

@>

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラムĔý¾ÚƧ
ƊƞĹƐƦžúǀǄűĉ¢xYŎ¾ÚƧ

&$!"()%'

解は実行の度にゼロクリア

検証! ( $#'( #'&#% J  " #'&# " #'

測定

ǀǄƩƪƧ
• ƊƞĹƐƦžúǀǄƧ• ùĈKŠ¯ş>xYşùĈ¢6~½øÚŠ=ŝşŚāőlÚ¢ùĈ
ŐŮ7Ƨ
• \@xY¢ŠĴ¯Ş@ŗŔƱşxYr)űGŞĴïĪƍĹƉŚlÚŎŔr)śŝŮūŃAÚƧ
提出は>時間以上必要

%( " -()%'>回実行時間%( " - " #'

後処理

ĉ¢

前処理

初期化

ǐǜǩǪǊǦǨǤǩƩƪƧ
• `J¤ĶÚ¤şƊŷƋŽƧ• ǀǄşxYĕŞƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧƧşÏű1į
r50 2 r0 2
ŎřŅňĴƕƤŇŝłņƊŷƋŽĳĳ

%$&(')!('

分散が>0=K>=3C以下なら合格

年月日研フォーラム

MGの処理

N
N
⎫
1 ⎧
( ) ?=>A年E月?C日研フォー(k + 12 )?=>A年E月?C日研フォーラム= ⎨ri − ∑ aij z j − ∑ aij z (jk )⎬ ーラ
zi
aii ⎩
j <i
j >i
⎭
k + 12z = MG ( A, r )



z =0



後退*%kLN〜>





@?

前進*%k L>〜Nzi(k +1) =



N
N
⎫
1 ⎧
(k + 12 )−−raz
aij z (jk +1)⎬
⎨ i ∑ ij j
∑
aii ⎩
j <i
j >i
⎭

!+( $#,)''3

!6&3'"$$( #7Az = r'(& (

袖通信


z
最細
Az
A = A ⋅ z 袖通信
L=
&3'"$$( #細かい格子での値を' )!
rcoarse = Restrict (r − Az )粗い格子上に補間 '(& (再帰&$!$#(zcoarse = MG ( Acoarse , rcoarse ) 6再帰呼び出し7
A
 
補間7

 

再帰 r
粗い格子での値をzz = z + Prolongate( zcoarse )格子サイズが>/?の整数
細かい格子上に補間 倍なので，補間といって
&$!$#(!+( $#,)''3

!6$'(3'"$$( #7Az = rも代入するだけ$'(3"$$( #coarsecoarsecorase

袖通信

再帰 
!+( $#,)''3!
Az = r

最粗
!+

袖通信
年月日研フォーラム

@@

HPCGベンチマークアプリの概要?=>A年E月?C日研フォーラム
初期化
&$!"()%'ÜŐŮxYBűĪƧƩǅǌǀǄƭƿǜǥǚǟǤǘǨǢƭƲƮƱƭðCîr]ƮǮǘǤǣƪƧ

%( " - " #'Čĭ¢ĶƅƤƋƏ¢Ƨ³ÆĚÌƂŵƆƧ
ƖƥƇƅ>ƧƱƒĹƏåŭşĚÌƂŵƆƧ
ƘƣƊžƢƋƏ ¶ŚşYĭşY¢śÿƈƥ¢Ƨ• ƊƞĹƐƦžş§å¤EBƧ• `J¤ƊŷƋŽBƧ• ¾ÚBƩ ŹĹƑƣś³ÆƪƧ• ǂǣǘǧǩǜr)Ƨ
• ĤİÞŝĆè¢âi¢Ƨ• ǄǃǈǋǌǏÏƧ

%$&(')!('

EƔŷĹƆŚă\!ŇŁůšǃƾǆǈǂǁƬƧ§ŝŬǒƾǈǆǁĻǄǃǈǋǌǏÏŇĪōůŮ! ( $#'( #'&#% J  " #'&# " #'
%( " -()%'

•
•
•
•
•

年月日研フォーラム

@A?=>A年E月?C日研フォーラム

HPCGのチューニングと性能

年月日研フォーラム

@B

HPCG テスト実行
on 京?=>A年E月?C日研フォーラム•ƀĹƏŠƾǩƧǆǩœşťťƧ
– ŔŕŎËČĭţşÇśŎřćşč¢ş=űčVƧ– ǄǜǦǤǜǪǨǮƮǟǧǧÓşǪǮǧǜǛǜǝōůřłŮ=űǠǥǪņŬǣǦǥǞƧǣǦǥǞŞčVƧ

•ǉǘǢǜĒēƧ
– ǍǑǆǀǇǏǐƾǎǐƮǐǔǐŞŗřxYƧ

•ƌƅƎĚÌƧ
– ƍƔŸƣƎşƱưƴļƱưƴļƱưƴƽƱƱƲĖ­âƯƖƥƇƅűģĠƧ
– ¾ÚrşǀǄ:ŭĎŎ¢ŠƵƧƩĔĢŠƱr)ĊŚěƵưƪ

年月日研フォーラム@C

ウィークスケール測定結果?=>A年E月?C日研フォーラムùĈKŠƵưƧǀǄxY¢ŠƵŞNÚƧËČĭŚèņŐūŃćč¢ş=űčV

>B??? 6=0@CI7
FE@B 6=0?@I7ƸČĭƳƲƷƶƸČĭşƴưƹƶôŚƧ
ǄǃǈǋǌǏÏŠƧ
ČĭSĦƧ
ƴưƵƴôƧƩƗƦƊBƪƧƴưƴưôƧƩƖƥƔŲŵơƪ
ƹƸƨ

Eスレッド2プロセス@回平均• ƸČĭņŬƳƲƷƶƸČĭťŚČĭ¢ű'ń¾ÚƧƗƦƊBśƖƥƔŲŵơśŚƱƮƵ
• ƗƦƊBĳĳǅǌǀǄƀĹƏŇuŚiŎŔƩÜŐŮƪƧǄǃǈǋǌǏÏƧ ôÝäş_ŇŁŮƧƧ• ƖƥƔŲŵơƧƧƧƧƧƖƥƔŲŵơűģĠŎřiŎŔƧǄǃǈǋǌǏÏƧ
Ćè¢âi¢ŹŶƦƎĒvş
• ƳƲƷƶƸČĭťŚşü ŚŠŶŴĹŽƅſĹƣ¤ñŠĨUłŇH年月日研フォーラム年
年月日研フォ ラム

@D

測定値のプロファイラとの違いについて?=>A年E月?C日研フォーラムƖƥƔŲŵơŚşĆè¢âi¢Ƨ•¾Ú8)Śõ¨ŐŮĆè¢âi³řŇŹŶƦƎÇƧ•iæŠĉ¢şĆè¢âiśŎřŹŶƦƎƧ

ǅǌǀǄŚşĆè¢âi¢Ƨ•ĤİÞŞāġŝişŃŖĴ{ġŝũşşŦűŹŶƦƎ
ŎřŅŭĴĘoŎřłŮũşũŁŮ 
x = CG( A, b , x0 , ε , max) x = SYMGS( A, b , x )

SPMV()
 WAXPBY()  ※?0Aではカウントするようになった
DotProductfor(k=1; k<max && !conv; k++){MG()
DotProduct() 
WAXPBY()
SPMV()
}

for(i=0; i< ; i++){for(j=0; j<nz[i]; j++){col = A.mtxIndL[i][j] sum -= val[j] * x[col];}sum += x[i] * Diag[i];sum = sum / Diag[i];}  年月日研フォーラム@E

通信の比率変化?=>A年E月?C日研フォーラム
A+A+A
E+E+E

通信はおおむねCI程度?+?+?

xYrşƖƥƇƅ¢lÚŠǄǜǥǜǨǘǪǜǄǜǦǤǜǪǨǮŚƧ
AÚŎŔƳsG>Ş\ŰŒŔ@回平均• ƖƥƔŲŵơŚ@¾ŎŔǉǌǆşƀƅƎşĴÇ³ƀƅƎþĦƧ• ÙşƀƅƎş%\ŠĴƵƱƲČĭŚŠƂƊŗřňřŅŭĴ\@ƶƨÝä年月日研フォーラム

@F

HPCGコスト分析?=>A年E月?C日研フォーラム
$"%)($(&$)(4&AC3DF

+#!$4&BF3D=

$"%)( 4&BF3D=

$"%)( 4&BA3>=@

E>F?並列のもの6他もほぼ同じ7• ƖƥƔŲŵơŚb|ŎŔǀǄíŚMŢ}ÁňşƀƅƎĊąƧ•  ƴŘŚƹƸƨű°ŨŮƩƾǣǣǨǜǛǫǚǜƬƧǆǩǜǥǛƬƧǆǨǜǚǬƬƧǓǘǠǪű+ŧƪƧ• ƊƞĹƐƦžŠťőÍÆ¤ñşTǀǦǤǧǫǪǜǏǕǉǄǏśǀǦǤǧǫǪǜǏǌǉǒŇ{,Ş年月日研フォーラムA=

単体性能チューニング
?=>A年E月?C日研フォーラム
メモリ領域の連続化
メモリ確保部ソース

行列の各行の情報を保持する配列は

for(int i=0; i<nrow; ++i){
matrixValues[i] = new double[27];mtxIndL[i] = newint[27];}

行毎に#*されているので，メモリ上

メモリ空間
0"(& +!)'8=9で不連続になっている

0"(+ # 8=9

0"(+ # 8#&$*3>9

1

1

1

0"(& +!)'8#&$*3>9
0"(+ # 8>9

1

1

0"(& +!)'8>91

年月日研フォーラム

A>

単体性能チューニング
?=>A年E月?C日研フォーラム
メモリ領域の連続化
メモリ確保部ソース
double* tmp1 = new double[nrow * 27];
double* tmp2 = newint[nrow * 27];

メモリ確保を一括して行い，各行の情報が連続するように変更for(int i=0; i<nrow; ++i){
matrixValues[i] = &(tmp1[i*27]);
mtxIndL[i] = &(tmp2[i*27]);}

ムダな領域もなくなった

メモリ空間
0"(& +!)'8=9 0"(& +!)'8>91
11111110"(& +!)'8#&$*3>91

0"(+ # 8=9 0"(+ # 8>9
0"(+ # 8#&$*3>91
1111111

年月日研フォーラムA?

単体性能チューニング
?=>A年E月?C日研フォーラム
ケース


実行時間



連続化

 


メモリスル スループ
ープット

ット



 
ミス率ミス率ロード・ストア ロード・ストア  


数

数

 


 
 

ǀǄƩƪņŬ×«MšůŮǏǌǉǒŞŘłřĴ
xYr)śĴŻƝƋƄƞƙƅĦĴƅƣĹƖƋ
ƎæűÕŤŔƧƧ
ƧǉǄƩƪņŬMšůŮĊŠƧ

K?0@高速化ƛƜƢĩ şĮÁşSŞūŭŻƝƋ
ƄƞƙƅĦIĴƅƣĹƖƋƎTƧxYr)ŠƱƯƲƮƳŞÎEプロセス，Eスレッド2プロセス
年月日研フォーラム

A@

その他のチューニングを実施?=>A年E月?C日研フォーラム※から呼ばれるもののみ※ 以下の . 等の合計>C0? 
>0BEI

?0@ 
=0??I

?0A

@0?
@F0> @0E?I

D0? =0DI

• ǅǌǀǄuŇ¾ÚŎŔÜŐŮƍĹƉņŬö¡ŎŔũşƧ

?0C =0?BI

• Ǐǌǉǒşr)ǀǄƩƪņŬMšůŮĊşŦşr)Ƨ
• ²ĤǉǄŠǏǌǉǒƬǏǕǉǄǏæĸű+ŧr)Ƨ

@0?
E0A =0E?I• Ʋâş(ÍŝƊƞĹƐƦžŕŋŚƳƮƲôş
[ÀŇêŬůŔƧ
• YĭşƛƜƢĩ şĮÁƧ• ǏǕǉǄǏşƿƾǇƣĹƖŚşƣĹƖĒTşùáƧ
年月日研フォーラム

AA

前処理のマルチスレッド化?=>A年E月?C日研フォーラム
種別

関数名

行番号

$"%)( 4&F@3FC$"%)( 4&
DA3DD
$"%)( 4&CD3CE• ƖƥƔŲŵơŚb|ŎŔ }ÁňşƣĹƖÍ şƀƅƎþĦƧ
• ǀǦǤǧǫǪǜǏǕǉǄǏşƣĹƖŠƘƣƊƅƤƋƏōůřŅŬőÑsŚèeƧ
• ŌŌŚŠǀǦǤǧǫǪǜǏǕǉǄǏşƘƣƊƅƤƋƏűxm
年月日研フォーラム

AB
カラーリング?=>A年E月?C日研フォーラムǏǕǉǄǏŠÇYĭŞŘłřźŶƅĶƃŵƍƣēűkĠŎŔƘƣƊžƢƋ
ƏĤűYŃĵƧ
i−1
n
(m+1)
(m+1)
)
= − ∑ aij x j− ∑ aij x (m+ kjźŶƅĶƃŵƍƣēƧ aii xi
j
j=1

j=1+1

ƩǤƫƱƪ£ÊşűêŮŔŨŞƩǤƫƱƪ£Êşg$YĭűkĠŎřƩƢŹ
ƤƦƅşõ¨ƪĵ(a)オリジナル(c)RED-BLACK２色カラーリング

参照関係
計算順序
(スイープ順序)年月日研フォーラムAC
カラーリング?=>A年E月?C日研フォーラムǔǕǖ ĒTşīŭśyŨűérŞhŐŮƲƷâƧ
ƅƌƦƄƣŝşŚĴƸāġfor(int i=0; i<nrow; i++){最内ループ の外側ループ}ŹơĹűŐ»ƣĹƖØŚƳƧǝǦǨƩǠǥǪƧǠǚƽưƻƧǠƼƸƻƧǠǚƫƫƪǰƧ
ƧƧƧƢŹƤƦƅŇŝłşŚƍŴƤŽƌŴƕ
ƧƧƧ·ïŚČĭƧ#pragma omp parallel for
for(int i=st; i<=ed ++){
最内ループ
}
}
E色

z y
x

iűčVŎŹơĹĕŞĤŐŮŌśŚƧ
ČĭŇñŞ
年月日研フォーラム

AD
カラーリング?=>A年E月?C日研フォーラムişčVŞ÷łĴƛƜƢŚş`óÐũYłĴƛƜƢųŽƇƅűĮÁƱYĊşđ

1

値?D個の$)!

1

列番号?D個の #(

メモリ空間
行列の情報

>行

?行

@行

A行

B行

C行

D行

E行

F行

>=行

11

3>行

行

B行

C行

D行

E行

F行

>=行

11

3>行

行

11 >==行 >=>行 >=?行 >=@行

11

3?行

3>行

行

カラーリング
メモリ空間
行列の情報

>行

?行

@行

A行

並び替えて連続化
メモリ空間
行列の情報

>行

?行

@行

A行

年月日研フォーラムAE
カラーリング?=>A年E月?C日研フォーラム

>

B

?

C

>

B

F

>@ >= >AF>@ >= >A

@

D

@

D

A

E

>> >B >? >C

?

A

C

E

>> >B >? >CƛƋƄƞâş
žƣĹƖƛƜƢóÐ
>

?

@

A

ŹơĹƱ

B

C

D

E ・・・

ŹơĹƲ

・・・
F >= >> >? >@ >A >B >CŹơĹƳ• ŌŌŚ®ęŎŔŀŹơĹƢƦžŠĚÌ
şWºÞŝƛƋƄƞWºű²ÜśŎŔƖƥžơƙƦžű6nŐŮƤżƞƤĹƄƠ
ƦŞÛŐŮĵƧ
• œşŔŨũŗśûÞŝŹơĹƢƦž
}ēŞčVĵƧ
• ƛƋƄƞâűĉ¢ťśŨřžƣĹƖű
W¥ŐŮĵƧ
• œşžƣĹƖĕŞŹơĹƢƦžűxmĵƧ
• ŹơĹíŚŠžƣĹƖ)ŚƢŹƤƦƅŠõ¨ŎŝłĵƧ
• œŌűƅƤƋƏČĭŞģĠĵ

ŹơĹƴ
年月日研フォーラム

AF
カラーリング?=>A年E月?C日研フォーラム※データサイズ>=A@N>>?@に変更

カラー化によりコスト上位のループが全て並列化$"%)( >AA3>AD$"%)( 
ED3EE
$"%)( >>A3>>D※全ての を含むコスト







 
 



  



 

 

 



 





















 





 



 












年月日研フォーラム

B=
トータル性能?=>A年E月?C日研フォーラム





















 















  



 



 








 



   


















 





  



年月日研フォーラム

B>
ISCʼ14?=>A年E月?C日研フォーラム
Site

Computer

Cores

HPL
Rmax
(Pflops)

HPL
Rank

HPCG
(Pflops)

HPCG/
HPL

33.9

1

.580

1.7%

HPL
HPCG

天河２

Tianhe-2 NUDT,NSCC / Guangzhou Xeon 12C 2.2GHz + Intel Xeon 3,120,000
hi 57
57C
C + Custom
Phi

「京」

RIKEN Advanced
Inst for Comp Sci

K computer Fujitsu SPARC64
VIIIfx 8C + Custom

705,024

10.5

4

.427

4.1%

 (#

DOE/OSOak Ridge Nat Lab

Titan Cray XK7 AMD 16C +Titan,
Nvidia Kepler GPU 14C +Custom

560,640

17.6

2

.322

1.8%

&

DOE/OS
Argonne Nat Lab

Mira BlueGene/Q, Power BQC
16C 1.60GHz + Custom

786,432

8.59

5

.101#

1.2%

Swiss CSCS

Piz Daint, Cray XC30, Xeon 8C+ Nvidia Kepler 14C + Custom

115,984

6.27

6

.099

1.6%

Leibniz
Rechenzentrum

SuperMUC, Intel 8C + IB

147,456

2.90

12

.0833

CEA/TGCC-GENCI

Curie tine nodes Bullx B510
Intel Xeon 8C 2.7 GHz + IB

79,504

1.36

26

.0491

2.9% * scaled to reflect the sam
number of cores# unoptimized implementa
3.6%

62,640

3.00

11

.0489

1.6%

132,8401.65

18.0439 #

2.7%

78,848

.881*

7

.0161

1.8%

79

.0110

2.4%

80

.00998

2.4%

Exploration and
HPC2, Intel Xeon 10C 2.8 GHz
Production+ Nvidia Kepler 14C + IB
Eni S.p.A.
DOE/OS
Edison Cray XC30, Intel Xeon
L Berkeley Nat Lab
12C 2.4GHz + Custom
Texas Advanced
Stampede, Dell Intel (8c) +Computing Center
Intel Xeon Phi (61c) + IB
Beaufix Bullx B710 Intel Xeon
Meteo France
12C 2.7 GHz + IB
Prolix Bullx B710 Intel Xeon
Meteo France
2.7 GHz 12C + IB
CALMIP Bullx DLC Intel Xeon
U of Toulouse
10C 2.8 GHz + IB

24,192
23,760.469(.467*).464(.415*)

12,240.255

184.00725

2.8%

Cambridge U

Wilkes, Intel Xeon 6C 2.6 GHz+ Nvidia Kepler 14C + IB

3584

.240

201

.00385

1.6%

TiTechTUSBAME-KFC Intel Xeon 6C
2.1 GHz + IB

2720

.150

436

.003702.5%
年月日研フォーラム

B?
ISCʼ14?=>A年E月?C日研フォーラム• ǆǏǀĺƱƴŚŠ§vşƗƦƊƘĹŽŚŠŝŊhXşƙƐ
ƢƅƎśŎřõĂƧ
• 3ŠŌşƙƐƢƅƎŚľ ű"êƧ• Ľ şàľŠƓĹŽ¤ñŚ3şĿôÝäƧ• ǅǌǀǄş¤ñ_ŠƱƮƳôƧ
• ǅǌǀǄƯǅǌǈ¤ñþķƴƮƱƨŠ;űöłřłŮƧ
• ǅǌǀǄŠǏǀĺƱƴŚ§vşƗƦƊƘĹŽśŝŮĞÚ

年月日研フォーラム

B@
まとめ?=>A年E月?C日研フォーラム• ŠŏŨŞƧ
• ǈǆǊǌƾǀǇƧ
• ǅǌǀǄśŠƧ
• ǅǌǀǄƗƦƊƘĹŽƖƥžơƚƧ
• ǅǌǀǄşƊƞĹƐƦžś¤ñ

年月日研フォーラム

科 学 技 術 計 算 分 科 会

選 出

科学技術計算分科会 2014 年度会合 より

スーパーコンピュータを用いた大規模グラフ解析と Graph500 ベンチマーク

藤澤 克樹(九州大学)

サイエンティフィック・システム研究会
科学技術計算分科会 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 Graphgeneration
Input paramet ers Input
GraphgeneratGraphconstruct 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

ValidatResultionsResult s- SCALE- edgefactor
Result
sTEPS
- BFS
Time
ratio
- Traversed edges- SCALE - TEPS- SCALE- edgefactor- BFS Time- Traversed edges- TEPS- edgefactor- BFS Timeratio
64 Iterations
edges
64
Iterations - 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

#4

5524

5524

5524

993

1003

256

609

317 # 4462

1280 C PU o n ly
1003

462

462
131.4
SGI U V2 0 0 0

TSU BA M E-K FC

64

44.0

100 # 3
18

104.3
45.7

4 -w ay X eo n server

7
CPU o n ly

4

31.6

GPU

16

×3 .2 5TSU BA M E 2 . 5

358 # 3
253

#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/ȘɇȫɇȓɅȮȽɇȜȅõǘǦlĴÖȐȿȯķÍǮƂ
+*"MHHȳɅȞȷɇȏ
藤澤 克樹
九州大学マス・フォア・インダストリ研究所＆ JST CREST
6TāĊĢɐŧƂÁQɉÌl?9rƂŲŢ>
1&$(?9!ĪƂ9æƂ`m9é¢ƂČ>Ìl?

l?9ũÊƂńmŢɉ($2 +,$-5)&& " 

2014年10月29日
ȕȈȉɅȡȇȯȇȟȏɆȖȘȡȹāĊƂĆq¤ĬĹđ:ĆƂJHILSØ ȅµǚȃ¤Ĭ
ホーテルオークラ神戸ƂǲāĊĹ÷ǲÓı• ØȶȘȣȴȜȘȫȓɅǭǲķÞǤǷǞŁžǲîs–;¸ǲíúühlǒbŌHǒƁxH– ĺįĠǲkű~HɆlwŨH– ȆɁȔɀșȹüǒȖȘȡȹüǱÔǔǰķÞǤǷǞŁžǮ]Ŷǝp_• lĴÖȐȿȯķÍMǵ¸ôÃŠHȖȘȡȹƂ– ĝǱOȂĘǼǷǞŁžǮtăǶǲȈɅȫȏȣǑǑ– +*"MHH@+(+*"MHHAȳɅȞȷɇȏ@lȐȿȯ8A• IJ:KMP@øɎA8P;IM@IȨɇȤøIA• IJ:MMJL@øɏA8IH;LQM@IȨɇȤøIA• IK:N;IIQ>%@øIA• IK:N;OJ>%@#!-IA8IMK;IO>%@'&&-IA• IL:IOQOO@øɌA8MQ;IJ>%@#!-IA– ¸ôĹ÷ZžɉA:@øĺŪÂ»ɐJKK?ĕƂ9I;OIK&)*,A• IJ@";**+A8 ILǰǯɐƂùDxȢɇȜĹđ@JL8LPHȓȆƂD
LHPHAǑɐǑǑ½ÉȋȴɂɇȖȾɅșɀȕɇȞqāĊŋǒ   *(Ã/ąȶȘȜɇúĭŋĎ• ÃŠHǮ ĔāĊĢǲȶȘȣȴȜȘȫȓɅǭǲƂƂƂƂƂƂƂƂƂƂƂƂƂƂƂƂǑǑǑǑ)?,#!(ǱȀȃķÞ• ȶȘȣȴȜȘȫȓɅǭǲeýțȯȣǲ¹-ǱŇñǤȃǮ6ǱrƂƂƂ
r4ǰăǲtóȅþ©ǤŏlĴÖȐȿȯÃŠHȖȘȡȹǲ®ÐřɆëvĦɆšŶɆɃȗȘȡȇȏȘŶɆɃȗȘȡȇ
ȇȏȘȏȘŮëĹ÷ďsțɇȖȼɁǍ
ȧȟȣɄɇȏķÍȉȧɁȎɇɆÿŷDŏlĴÖȐȿȯÃŠHȖȘȡȹŏllĴÖȐȿȯÃŠH
ŏlĴÖȚɅȕɇ• ĶèȢɇȜ• ȘȷɇȣȐɀȟȤ• řɆŔŘ
• SNS (Twitter)lĴÖȐȿȯPĵH
<HK

<HM

ɀȆɁȜȈȹlĴÖȐȿȯȘȣɀɇȹ8ôķÍȢɇȜțɇȘ<HOȐȿȯªėMǵ¸ôÃŠH
<HQ
<II
II
I

ÃĀęŒ
Zž

ȏȿȘȜ
ɀɅȐ

( 4$("ȿȈȰȿɀǱȀȃlĴÖȐ
ȿȯ8ô

KÙs,
Ĺ÷Zž

ɀȆɁȜȈȹ
Șȣɀɇȹ8ôĔȢɇȜțɇȘÃŚȯɃɇZž
åS¹¸Ĺ÷ZžFEĸŀ8ôĔ

FEEĖȲȡɃȗȦȆȘȘȫȓɅlĴÖȐȿȯȘȣȆ
ǑǑ
Ǒ

õ:ŧ

Ȑȿȯ

ŅTiǲŭ)
řȧȟȣɄɇȏ.)(,"#*,AțɇȖȼɁȧȟȣɄɇȏ @&.)(,"#*,AȕȈȪɇȚȍȽɀȡȇȪȈȋȈɅȯȊȷȡȇȏȘĤĆqŮëĹ÷ďs3#0+țɇȖȼɁȧȟȣɄɇȏ

N8INHìǑDIL.OJÏ-*J
ȐȿȯķÍ

ķÍĚÎ-*I
*-*K
-*K:ÍǮôķ
:ÍǮôķķ• ;Ȑȿȯªė@/2ªėA• ÃŠH@ÃĀŒ8ÃlȯɃɇ8ÃzŊõȯɃɇA• ȏȿȘȜɀɅȐ@Ȑȿȯ:B8ȓȸȽȦȡȇ¦9A
ȦȽɇȿɁɆȧȟȣɄɇȏE 1'(+#(+)$-
PQH.ìƂDIHH1Ï

4ēŝŒȧȟȣɄɇȏȕȈȪɇȚȍȽɀȡȇ

J8LHHìƂDMPHHÏ

IMH.>½ƂǲȆȏȚȘɃȐlĴÖȐȿȯķÍɐĝǱOȂĘǼǷǞŁžǮtăǶǲȈɅȫȏȣŮëĹ÷ďsřɆëvĦɆšŶɆɃȗȘȡȇȏȘȉȧɁȎɇɆÿŷDțɇȖȼɁǍ
ȧȟȣɄɇȏķÍȈɅȜɇȧȟȣȷȟȱȦȽɇȿɁȧȟȣɄɇȏțɇȖȼɁȧȟȣɄɇȏ ȕȈȪɇȚȍȽɀȡȇř(ÀċŬ)ȧȟȣɄɇȏȘȻɇɁɄɇɁȤǿȘȑɇɁȯɀɇǰǯǲîȅ¨ǪŏlȐȿȯǑǑ(11ì) ǭǲƁŚªė¤ĬɉȆɁȔɀșȹǒtį¤ĬǒƁŚĹđɊƂƏƐȘȫȓɅ:NMMKNȨɇȤ
+*"MHH:IOQOO
ƟǃƼưƽƂƙǀưƸƽƂƧǀƾƹƴƲǂ
ƾƹƹƴƲǂ ƂƂƞǀưƿƷƐƋƋƂƄƟǃƶƴƅ
ƞǀưƿƷƐƋƋ ƄƟǃƶƴƅ
ƶ 
Symbolic
NetworkƂƞǀưƿƷƐƋƋƂƄƣưǀƶƴƅ
ưƿƷ
ƿƷƐƋƋ
Ƌ Ƅƣưǀƶƴƅƅ

1 兆枝

ƂƏƋ

ƞǀưƿƷƐƋƋƂƄƤƴƳƸǃƼƅ

Ƅ
Ƽ
ƅ
ƻ
ƾ
ƶ
ƍ

グラフの枝数ƂƎƐƂƞǀưƿƷƐƋƋƂƄƨƼưƻƻƅƂƂƞǀưƿƷƐƋƋƂƄƤƸƽƸƅ

1０億枝
ƂƎƋ

ƂƂƂƞǀưƿƷƐƋƋƂƄƩƾǇƅƪƨƘƈǀƾưƳƈƳƉƪƨƘƉƶǀƪƂƍƐƪƨƘƈǀƾưƳƈƳƉƣƢƨƉƶǀ
ƪƨƘƈǀƾưƳ
ƪƨ
Ƴ


ƂƍƋ

Twitter (tweets / day)ƪƨƘƈǀƾưƳƈƳƉƥƮƉƶǀƂ
ǀƾưƳưƳƈƳƉƥƮ
ƮƉƶǀ 
ƂƌƐƂƍƋ

(+)#²Ƃ:?HI(*+!)(LI;O 6LȓȆ:J
I;HK:JKM;HN>

全米道路ネットワーク

１兆点

Twitter (バルス:2013/08/02)
ƂƍƐ

ƂƎƋ
ƻƾƶƍ
Ƅƽƅ

グラフの点数

ƂƎƐ

１０億点

ƂƏƋ

ƂƏƐ

4ē×ºǲÃĀŒɐƂJLHHì8MPHHÏƂĕJćǭĹđ>K?
ȕɅȢȇȉȔǜȁIÌţǲȺɇɅǺǭǲÃĀŒɉŎɐÃĀőŵǒŸɐÃĀÀŬɊ:"0*:>>)*-;#'#;%51,"1?1;;$*>

超大規模ネットワークにおける高速探索技術の開発コアとなるアルゴリズムやソフトウェアのカーネル部分の実装と評価• 超大規模ネットワークデータ（点数１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 Centralityyclosenessgraph

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

s-t 間最短路数

betweenness4ēȐȿȯǱyǤȃŦı>

?ǲĹđ• ȧȟȣɄɇȏ7ǭǲRìǲŦ
Ŧıȅ¬s• RìǲWŕǒMǵd7ǱǛǟȃŻɉfǲ³D?ȅ¬sǤȃ• ŏlĴÖȧȟȣɄɇȏȢɇȜǭǲĀÀŬǱlŨǲȐȿȯªėȅīǙıǝǗȃƚƻƾǁƴƽƴǁǁƞǀưƿƷ

ƨǂǀƴǁǁƄy¸ƅƙƴǂǅƴƴƽƽƴǁǁ";;&-+#+##0*:<<333;(*+;)+"<- '*&- ,<,-)+5<,-)+5;*#*8,-)+5 PFFENNLHNM

&-+#&(-+&#-5,1+, )+&-+#)3++#1&(+#&#-5(&5,#,
(!8;9!&#)(8;9")',8; ;GEFE全米道路ネットワークに対する全対全最短路問題
点数 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ȆɁȔɀșȹ
ƛƸƹƺǁǂǀưǊǁƂưƻƶƾǀƸǂƷƼ4y4ÃĀŒ ƁŚHò 各2点間の最短路長を
1.1ns で求めることができる
ƐƌƍƂ
ƈƈǉƈǁǂƴƿƿƸƽƶƔƉƌƂ

ƑƋƂ+ƤǃƻǂƸƈƣƴǄƴƻƂƙǃƲƺƴǂǁƏƉƔƂ

ƌƌƋƂ+

ƤƨƣƚƂƆƂƥƪƤƘȅġǢǦÃŠHƒƉƓƂ½ ƍƏƇƋƋƋƂ+

厳密な
全対全最短路長を
約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ƥƮȢɇȜǱyǤȃƄƙƚƅǲĹđĚÎɉÃĀŒZžɊǐȕɇȪɌƂƄƍƚƧƪƂǆƂƏƂȓȆƂƗƂƓƂȓȆƅtīÀŬƂƌƔƐƒƉƑƐƍƂćƂƕƂƓȘɂȟȤƚƧƪƂƕƂƘƤƛƂƦƿǂƴǀƾƽƂƍƎƐƑƂƍƉƎƞƟǈƂǆƂƍȺȻɀƂƕƂƎƍƞƙƦƨƂƕƂƫƸƽƴƂƣƸƽǃǆƂƐƉƌƂƵƾǀƂƭƓƑƯƑƏǐȕɇȪɍƂƄƌƚƧƪƂǆƂƏƂȓȆƂƗƂƏƂȓȆƅtīÀŬƂƍƋƐƓƉƏƏƎƂćƂƕƂƏȘɂȟȤƚƧƪƂƕƂƠƽǂƴƻƂƚƾǀƴƂƸƒƂƔƑƐƂƎƉƍƞƟǈƂǆƂƌȺȻɀƂƕƂƌƍƞƙƦƨƂƕƂƚƴƽǂƦƨƂƐƉƐƂƵƾǀƂǆƓƑƯƑƏǐȕɇȪɎƂƄƏƂƚƧƪƂǆƂƑƂȓȆƂƗƂƍƏƂȓȆƅtīÀŬƂƑƎƍƉƓƐƔƂćƂƕƂƍƏȘɂȟȤƚƧƪƂƕƂƘƤƛƂƦƿǂƴǀƾƽƂƓƏƎƔƂƍƉƓƋƞƟǈƂǆƂƏƤƴƼƾǀǇƂƕƂƌƍƓƞƙƦƨƂƕƂƝƴƳƾǀưƂƌƎƂƵƾǀƂǆƓƑƯƑƏǐƂȕɇȪɏƂƄƍƂƚƧƪƂǆƂƏƂȓȆƂƗƂƓƂȓȆƅtīÀŬƂƌƎƌƔƉƋƐƏƂćƂƕƂƓȘɂȟȤƚƧƪƂƕƂƠƽǂƴƻƂƭƴƾƽƂƐƐƐƋƂƍƉƑƑƞƟǈƂǆƂƍƤƴƼƾǀǇƂƕƂƒƍƞƙƦƨƂƕƂƝƴƳƾǀưƂƌƎƂƵƾǀƂǆƓƑƯƑƏ

既存の GraphCT では
BC のみの計算で20.6 日かかる4ē×ºǲÃĀŒɐƂJLHHì8MPHHÏƂĕJćǭĹđ>K?
ȕɅȢȇȉȔǜȁIÌţǲȺɇɅǺǭǲÃĀŒɉŎɐÃĀőŵǒŸɐÃĀÀŬɊ:"0*:>>)*-;#'#;%51,"1?1;;$*>

ジョージ・ワシントン橋9ニューヨークを
通過する全米横断最短路

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 リストを作成◯ 高速な幅優先探索の実装 BFS•◯ Green Graph500 (June 2013)

計算機性能を引き出す汎用的な高速化
領域 (小)
1位

   

上位独占



Top-down 探索
2位
Chuo University’s
GraphCREST-Tegra3

領域 (大)
3位

   

Chuo University’s
GraphCREST-Intel-NUC

is ranked

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 ﬁrst 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 ﬁrst Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

Congratulations from the Green Graph 500 Chair

Congratulations from the Green Graph 500 Chair

1位

Chuo University’s
GraphCREST-Mac-mini

Chuo University’s
GraphCREST-MBA13

is ranked

Bottom-up 探索

is ranked

No.3

No.4

in the Small Data category of the Green Graph 500
Ranking of Supercomputers with
53.472 MTEPS/W on Scale 24on the ﬁrst 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 ﬁrst Green Graph 500 list published at theInternational Supercomputing Conference, June 18, 2013.

Congratulations from the Green Graph 500 Chair

4位

2位

3位

Congratulations from the Green Graph 500 Chair

4位

$# BH>C+:5MIW
$#!$&"!
,\F;A9JN-

  



$#"!%&$'&"!
"!

\F;A93Y[08165@+<"$4SV

$&$%&$&"!
/25G+G3?F+9PQ-


RO9EH=D4

ULZ

K
X7T0

." #$%%#$%")" #$%%#$%"' !
Graph500技術の応用
Twitter ネットワークの解析
ユーザ 21,804,357 からの幅優先探索の結果• フォロー・ネットワーク

ホップ数– ユーザ数（点数）
41,652,230– フォロー関係（枝数）2,405,026,092

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）

グラフ処理と幅優先探索
応用分野
•
•
•
•

交通
Social network
Cyber-security
生命科学

グラフ
関係性

Step2
グラフ処理

結果

Step1
Step3
応用分野の理解• 幅優先探索• 最短路問題• 極大独立集合

幅優先探索• 中心性指標• 最大流• コミュニティ検出• クラスタリング

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

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

BFS

入力：
グラフと始点Level 3

始点

始点

Level 1 Level 2

Level-synchronized parallel BFS (Top-down)• Started from source vertex
and executes following twophases for each level
Traversal … ﬁnds unvisited
adjacency vertices fromcurrent frontier QF andappend to neighbor QN  QN
 
QF
Level kLevel k+1

Swap … swaps thefrontier QF and theneighbor QN for next level

Algorithm 1: Level-synchronized Parallel BFS.
: 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.
Input

π(v) ← −1, ∀v ∈ V
π(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
2

QF ← QN
QN ← ∅

13
14

Swap

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

Top-down algorithm••

Eﬃcient for small-frontier
Uses out-going edges••

Eﬃcient for large-frontier
Uses in-coming edges    

   

Beamer2012

Bottom-up algorithm

Candidates of
Candidates
Cneighborsn       

Input : Directed graph G = (V, AF ), Queue QF
Data : Queue QN , visited, Tree π(v)Input : Directed graph G = (V, AB ), Queue QF
Data : Queue QN , visited, Tree π(v)QN ← ∅
Current frontier
for v ∈ QF in parallel dofor w ∈ AF (v) do
if w  visited atomic thenπ(w) ← v
Unvisited
visited ← visited ∪ {w}}neighbors
QN ← QN ∪ {w}
QF ← QN

QN ← ∅
for w ∈ V \ visited in parallel dofor v ∈ AB (w) do
if v ∈ QF thenπ(w) ← v
visited ← visited ∪ {w}w}
NN
Q ← Q ∪ {w}
break
QF ← QN

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
g at each level

Beamer2012

Number of traversal edges of Kronecker graph with SCALE 26|V| = 226, |E| = 230*#Distance from source
Dis

Level
L
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
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 reduceslunnecessary edge traversals

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

NUMAノード最大

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

ローカルメモリへのアクセス（アクセスコスト小） 

NUMAノード








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

リモートメモリへのアクセス（アクセスコスト大）

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

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,Swap on Remote RAM * %
*# 
 !!

 +• * %
 *!

QN 0
 

QN1
Q N2

NUMA-opt. requires two CSR graphs• Out-going edges for Top-down• In-coming edges for Bottom-up※ ! 

QN3
QF

QF

Q N2

?)*-;)&1'(?3#,+*"+..)(#(!• $2$ ,S@8A$(-)*+.&%S@%8%A($(,&)&%;
– %$,, -)!% (5&$,--#-#)&,#()'#(!!,-)%;

)&1'(?3#,!+*"*+..)(#(!)3?3#,!+*"*+..)(#(!


%






%

$(5'-+#4
4





@'A )&'')+5,,,)(&5)&'
,,,)(&5)(&5&$(5'-+#4

+)(.+

2&%RI
2&%RI

@'A'),-&5()(?&)&'')+5,,,
@'A'),-&5()(?
')+5,,,,,,,

#!")+,#!")+,
2&%#!")+,
2&%

+)(.+

2&%RI
2&%RI

NUMA-opt. parallel hybrid BFS（Graph500 1ノード最速）• 計算の大部分をローカルなメモリアクセス上で実行レベル内の計算の例
 から次のレベルの を探索

BFS の主要な計算（ローカルなメモリアクセス）



        
         

 
         

          )! )( * % *&  !  * $ 

Local Edge Traversal
0th NUMA node








QF



QF








visitedd0

3th NUMA node

Q N0

Q N1

QF



1st NUMA nodevisitedd1*  •  ,-',㱨㱨-

Q N3

2nd NUMA node•  QF•  "  kn (k + 1)nVk = v j ∈ V | j ∈,,visitedd3

QF

visitedd2

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




   





% !

    !"# $

512 threads
1.0 TBytes   





 % !

!
!
% !
% !

% !
% !
















 


!



! !
%
!
%














 











 

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




Out of memory 

 





  !"# $

64 threads
ds
400 GBIntel Xeon E7-8837 @ 2.67GHz
512-threads = 8-cores x 64-nodes
4.0 TBytes RAM  !"# $

512 threads
2.0 TBytes   





 



!
% !
% !



% 
!
% !











 









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%

L : R = 67% : 33%

L : R = 57% : 43% !"# $ !"# $ !"# $

18.76 GE/s

26.17 GE/s

37.70 GE/s 

















% 
!
% !

733
3 ms







182
8 ms

438
3 ms

218
1 ms
% 
!
% !
















 
197 mss% !
% !
% !
% !

% !
% !
% !

% !
% !
% !






258
5 ms
s





































128 threads

256 threads

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
1,1

1,2

1,C

2,1

2,2

2,C

R,1

R,2

R,C

R

R

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





隣接行列の２次元分割

頂点濃度に応じたデータ形式選択による通信
データ量削減 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

ExpandFoldorSparse vectorSparse vector
orSparse vector Sparse vector
Sparse vector
Bitmap
Bitmap
Bitmap
BitmapSparse vector
Sparse vectorSparse vector
Sparse vectorSparse vector
Sparse vectorSparse vector

Direction
Dire
rre
ect
c ion
topto
p downtop-down
top-down
top-downbottom-up
bottom-up
bottom up
bottom-up
bottom-up
top-down
top-down
top-down

Level5では、フロンティア頂
点が全頂点の84.5%なので、bottom-upが有利だが、未訪
b問の頂点はわずか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

Graph data is shared between two
search directions.

Overlapped communication withcomputation.
Sharing the same graph data between
two direction search.

Both top-down and bottom-up utilize
overlapping communication.

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


ただし、通信時間の増加はまだ最適化の余地あり

 各最適化の効果の検証は今後の課題とするウィークスケーリング
1E+15

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

ブレークダウン
1200

81,043
GTEPS

1000

17,977
GTEPS

1,266 GTEPS

1E+12
1E+11

713
79 GTEPS GTEPS

600
400
200

1E+10
64
36

計算

800

1E+13

時間(ms)

TEPS

1E+14

通信待ち

256

1024
4096
ノード数

16384

65536

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

0
64ノード

65536ノード"+*"MHH )'*1-+(J;HDJ;M
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

1280

1200

1345

GTEPS

1000
800
600

462.25

Efficient hybrid
400*Every score is obtained using TSUBAME2.0 1366 nodes or

200

TSUBAME 2.5 1024 nodes

317.0999.8580Graph500 ranking history for
K Computer

November 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Ȟɇȹǲ Î
16384

Top 1
K-computer
TSUBAME 2.5 (2.0)
FX-10
SGI UV2000
TSUBAME-KFC
4-way Xeonn serverGTEPS (in logscale)

4096
1024

15363

253

15363

K computer
9 7
17977

179 7
17977
3541

FX10

256

15363

355 #3
358
1 #4
317

#4

#4

#4

5524

5524

5524

993

1003

609
462

1280 CPU only
1003

462

462

16
7

4

44.0

0 #3
100
18

31.6

GPU

14
131.4
SGI UV2000

104.3
5
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

#0*:<<333;"+*#JEE;)+"
• Measures performance using TEPS (# of Traversed edges
per second) in graph traversal such as BFS
,-,-)!
'1&.=() 

Distributed
MemoryDistributed
MemorySharedMemory,-,-)!
,$("& =() 

Distributed
MemorySharedMemory,-,-)!
,$("& =, +2 +ƙƝƨƂģƙƝƨƂŷDģȆȯȇȦȡȇĻsÛǲƂGTEPSǮƂMTEPS/WƏƈǅưǇƂƠƽǂƴƻƂƭƴƾƽƂƜƐƈƏƑƏƋƂƍƉƏƞƟǈƂǭǲ¸,tƀ• ģǮŷDģ<Ǳ6řǤȃŌ– Tǣスレッド数ǰȁǴǒソケット数ǳkǘǸǙǝĨǘ– Tǣソケット数ǰȁǴǒスレッド数ǳkǘǸǙǝĨǘƟƩȓȆǲ$õǳŷDģǱEÎǝǗȃƢǀƾƽƴƲƺƴǀƂƶǀưƿƷƂƄƨƚƘƣƜƍƒƖƂƌƉƎƏƂ.żìƇƂƍƌƉƏƓƂ.Ïƅ
30

20

Reference (GTEPS)
Reference (MTEPS/W)

15

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

1050
ƑƏȓȆ$õÀǱǳǒǯǨȁǲtįǾǸǹTĎǲŷDäŊ

40
30
20

5

MTEPS/W

GTEPS

25

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

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.

64 スレッド (4-socket x 16-threads) で29.0 GTEPS と 45.43 MTEPS/W を達成$õǤȃțȑȟȣ¸ȅhǿǤǮŷDäŊǾhǚȃǝǒǥȄǲƂƩƜƧƨƂǲUǱȀȂƂƩƜƧƨƊƬƂǾ¶[ǤȃƘƽƳǀƾƸƳƂƦƨƂǭǲ¸,tƀ• ƘƽƳǀƾƸƳƂƥƛƢƂƄƥưǂƸǄƴƂƛƴǄƴƻƾƿƼƴƽǂƂƢƸǂƅƂǲ=õ– ȋɇȪȲȟȤǲ{ǰǘƂƚƊƚƆƆƂǭtįPģɉơưǄưƂǳŚüǱUǞɊ– ƞƚƚƂȅȳɇȘǮǢǦȏɃȘɆȓɅȫȈȿǲ®&– ƦƿƴƽƤƧƂǱȀȃȘɂȟȤ ;ĹđƂƃƁŚǰƂƞƚƚƂ§ǲȆȣȸȟȏŭ¸• (+)$ 2 &)* +))&,ǱȀȃɃȐȈɅɆœŘƂ
Step2.ƂȪȈȥɀǲœŘ
Step1.ƂƘƽƳǀƾƸƳƂƥƛƢƂǱȀȃȏɃȘȓɅȫȈɁƚƚƗ+'=&$(14=(+)$ $="ǋưƳƱƂƿǃǁƷǌƂȓȷɅȤ

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

Step 2

p3

Ste

Step3. ƘƽƳǀƾƸƳƂƛƴǄƴƻƾƿƴǀƂƩƾƾƻǁǱȀȃɃȐȈɅǒƨƷƴƻƻƂǱȀȃ´#

Step4.ƂtīĚÎǲOǋưƳƱƂƿǃƻƻǌƂȓȷɅȤ

ǋadb shellǌƂȓȷɅȤƘƽƳǀƾƸƳƂƛƴǄƴƻƾƿƴǀǁƕƂƷǂǂƿƕƊƊƳƴǄƴƻƾƿƴǀƉưƽƳǀƾƸƳƉƲƾƼƉƂ* +$===EIǭǲŷDģ
• 高速 (高性能) な実装が電力消費も良いƘƽƳǀƾƸƳƂƦƨƂčÈǭǾǗȃĉǲĴÖǺǭ£ǚȃƂƂƌƇƋƏƓƇƐƒƑƂƄƗƂƍƍƋƅƂìƌƑƇƒƒƒƇƍƌƑƂƄƗƂƍƍƏƅƂÏ&! "'() "







100 倍以上の
性能差




























スマートフォン
ォン
SONY Xperia-A-SO-04E
04E
gon
CPU : 4-core Snapdragon
RAM : 2 GB !" #$%"Implementation SCALE MTEPS watt MTEPS/W
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
This study (p = 2)20
248.08 2.99
82.92
This study (p = 4)
20477.63 3.12
153.17

使用スレッド数と電力消費の依存性は低い

The Green Graph500 List in June 2014

#0*:<<"+ (;"+*#JEE;)+"
• Measures power-eﬃciency using TEPS/W ratio
#!-- ")+5

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 Chair(- & )(J=IKIEJN;FG<>GM;IM?

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 Chair* +$=F==EFGHJ<>F;EH?   -,)( FGEI<>F;KH?

'&&-- ")+5

グラフ解析と最適化の今後 
$&%%&!$'(#"  
!&$"$"("'&"!"*%&





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

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

>$"-B* (-$(-# &)1?
他情報システム

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

API

解析ツール
レポジトリ

ビッグデータ

解析モデル
レポジトリ

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

センシング
データ

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

オープン
データ

Əƒ

ǕȭȟȐȢɇȜBȋɇȱɅȢɇȜȅáõǢǦCÑǖµ±ď@GEFIELGNA
F;Ą ǝÅǤȃȭȟȐȢɇȜBȋɇȱɅȢɇȜáõeý @ȭȟȐȢɇȜDȋɇȱɅȢɇȜāĊ#(BĄ

B%ICħUǟɀȆɁȜȈȹȷɇȑȟȡȇɅȐȕɇȭȘDſuUǟħȥȭȒɇȖȾɅȕɇȭȘȭȗȧȘ

A

ǒǒ  ǝ6Tǭ¿IJÄǱúŐC

L @ȢɇȜȕȈȉɅȘȘȏɇɁ )+

H;âȚɅȖɅȐȢɇȜáõǭPģǮǰȃkÔǰCÑſuǲōŉÚǿnǻǒħǲY­ǚǒĎǱeǫǘǦȫɇțȥɁħȥȭȒɇȖȾɅAB  ǝ÷ C ;)+!@#!-D*(-#(-"&)1AB  D l6TūúǒÉIHÄǜȁ  ǝŜõūo

ȢɇȜķÍȠɇɁȢɇȜȜWŕſuǲ}ǒōŉÚǿnǻǒFĞǒĎǱeǫǘǦɀȆɁȜȈȹȷɇȑȟȡȇɅȐf®&ȹsC

ȢɇȜȕȈȉɅȡȇȘȣȘȣȘȣ

BB%JCȘȷɇȜɇȻȪȈɁ==ȕɇȭȘȭȗȧȘ%JCȘȷ
âǱǣǬÔǔǰĈFcɉȻȪȈɁɊȕɇȭȘȅ®&ȢɇȜňĩ
Ȝňĩ
ňĩ
ĩ

ȚɅȕɇȧȟȣɄɇȏĄ ȋɇȱɅɅȢɇȜȕȈȣ@FEÄūĻ sA

ÑG
ÑG
ȢɇȜ

ƍƉƂĴ?ğXǭǾǩǮw¾ǱǰȃǕâȚɅȖɅȐǖBóïC²ŷĿȍȼɀȆRăǱȀȃĠfNųĠfNųDċŬěĹf®&
ea|ǭNųǢǦ²čÈÈěĹǲĠfȅeǱċŬěĹ
fȅ# 

%?ȤȓȻƂȻȪȈɁċŬěĹBĴ?
BĴ?ğXC#?#ȆȏȚȘȶȈɅȣȅõǘǦĠfNųD ;)+!ęöǲɀȆɁȜȈȹǰ0ȢɇȜ®&Nų
$=$ȆȏȚȘȶ
ȈɅȣǳǒ¤ĬüǱǳWŕǲ²čÈǲŃ
<fɉȆȤɂȘɊǝNų
PģǓǢǜǢǒ
ó_ǳÇáõ
ɉ=õPɊ

ɎǪǲŁž
F; ȍȼɀȆǝfðLG; ɀȆɁȜȈȹǭǲf®&ǳÇt¼
H; 0ȢɇȜǶǲȆȏ
ȚȘPɉěĹ
fǲǻ=õPɊ

Ĵ?
ğX

ǎ

lŤǭtĽtƀ

ɍǪǲĴ?ğXÐF; $=$ȆȏȚȘȶȈɅȣ
ǭǲ²čÈŃ<fNųȅļPG; ²čÈ¡ÅĢǲSǲǒNųǢǦŃ<fǲ0ȢɇȜǲɍØ=õȅPģǱƏƓȐȿȯªėMǵ¸ôÃŠHȿȈȰȿɀǱȀȃlĴÖȐȿȯ8ôl ~ɐ]ŶǰÃŠHȆɁȔɀșȹǲtī

I; @åS¹¸Ĺ÷ZžAǲgS:E=F¹¸j¸ǲ¸ƂP(ǭĹđŨǳǛȀǥƂ>G(?zG; A8ôǱȀȃj¸ǲ@ŰǮ ;ĹđǲŠõɉȓȆ ǲlĴÖȘɂȟȤ;ɐ:ÏȌȟȣßǲŠõ?
K;ȢɇȜŨǳIHMɉ¹¸j¸ǲ¸AI; ¼ĻťĠZžǒųSĮĲɉ:BɊZžǒȘȑȗȽɇɀɅȐZžǰǯǲÃŠHZž~ɐkŽÀŬÃŠHȆɁȔɀșȹǲtī



ɇ












I;@KÙs,Ĺ÷ZžAǲgS:(Pī;ǲlǞǡ9'P?ĕǲ¸ǭĹđŨǳ
ǛȀǥƂ>(HO'H?
G; ùǲŗÜǮA8ôǡȁǱ ;ĹđǲŠõɉȓȆ ǲlĴÖȘɂȟȤ;ǝ ǧǝǒǳOǱȀȃƁŚH?
K;ȢɇȜŨǳIHP@źņj¸ǲ¸AɐƂIHN@?ĕË¸AI; Ȑȿȯ:BǒȚɅȕɇȧȟȣɄɇȏǒȕȶɇȣȳȏȜɇȷȖɅǰǯǲÃŠHZž

~ɐȐȿȯķÍȆɁȔɀșȹǲtī

z

I;ȝȈȏȘȣȿß>Ɍy4ÃĀŒZžɐȬɇȱǞ?ǲgS:(Pì¸9'PÏ¸ǭĹđŨǳǛȀǥƂ>>(O'?&)"(?G; Ȑȿȯªėǲ|¡üǰľ(ǭǳ/2ȍȽɇ>ȬɇȱÆ?ȅõǘȃǏtīÀŬǒȺȻɀäŊŨǝrsüɉȓȆ ǲlĴÖȘɂȟȤ ;ǝ ǧǝǒƁŚȘ
ȣɂɇȗ¤ĬǱȀȃŏlĴÖȐȿȯ8ô?
K;ȢɇȜŨǳIHIJɑILɉȐȿȯǲì¸ǮÏ¸A
I; ÃĀŒĹđǒȧȟȣɄɇȏ7ǭǲRìǲŦıȅ¬sǓRìǲWŕǒMǵd7ǱǛǟȃŻɉfǲ³D?ȅĹđl~ɐȐȿȯķÍȆɁȔɀșȹǲtī

I;ȝȈȏȘȣȿß>Ɍy4ÃĀŒZžɐȬɇȱǞ?ǲgS:(Pì¸9'PÏ¸ǭĹđŨƂ>>(O'?&)"(?G; Ȑȿȯªėǲ|¡üǰľ(ǭǳ/2ȍȽɇ>ȬɇȱÆ?ȅõǘȃǏtīÀŬǒȺȻɀäŊŨǝrs
üɉȓȆ ǲlĴÖȘɂȟȤ ;ǝ ɈƁŚȘȣɂɇȗ¤ĬǱȀȃŏlĴÖȐȿȯ8ô?
K;ȢɇȜŨǳIHIJɑILɉȐȿȯǲì¸ǮÏ¸A
I; ÃĀŒĹđǒȧȟȣɄɇȏ7ǭǲRìǲŦıȅ¬sǓRìǲWŕǒMǵd7ǱǛǟȃŻ
ɉfǲ³D?ȅĹđ

•
•

•
•

>/2ªė?+*#JEE:ȓɅȮȽɇȜǭ& IE>GIEì9GIIÏɊǲȐȿȯǱyǢǬƂFM +ǲģ>)*=)3(B)0)'=1*B 2 &5(#+)($6 ?
#)+- ,--#>ÃĀŒ? <ǭ& HM>GHMì9GIGÏɊǲȐȿȯǱyǢǬƂ
H;F +ǲģ> &-- **$("B &&'()+ǲȩȈȰɀȟȤ?ŹüǰȐȿȯǱyǢǬǳ $"#35#$ ++#$ ,ǰǯǲA8ôǝÅE4$'1'&)3>ÃlȯɃɇ?1,# & &ßǲtįÃŚȯɃɇǱŠõĕ
I9JMMì9FM9JHLÏǲȐȿȯǱyǢǬÃlȯɃɇǲIJ:ǲtīÀŬ (-+&$-5> ?A8ôǿ ;ĹđĎǾÅE––––RìǱ«ĜǡȄǬǘȃÏ¸ɉ "+  (-+&$-5ɊRìǝÃĀŒǱVǺȄȃ\¸ɉ -3 (( ,, (-+&$-5ɊÃǾşǘìǺǭǲÃĀőŵɉ+*# (-+&$-5ɊRìǺǭǲÃĀőŵɉ&), ( ,, (-+&$-5Ɋ• ǥǲǲȆɁȔɀșȹǮȠɇɁǾk¸p_– $($'1',*(($("-+ ɐǑ4dÆ– -+)("&5)(( - )'*)( (-ǑɐǑśĚ :– * -+&&1,- +$("ǑɐǑȐȿȯǲī;ĭó> *&$(-+$4?^Å,ĹđȏȿȘȜɀɅȐƂ
Ɛƌ
Ɛƌ
Ɛ
ƌ
– 5* +: $"#)+#))ŭ¸ǲŖƂɐƂì4ǜȁ-#)*ǭ>ŞǤȃì5>495?ǲĹđȐȿȯªėMǵ¸ôÃŠHȿȈȰȿɀǱȀȃlĴÖȐȿȯ8ôeý
••

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

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

ȐȿȯķÍȆɁȔɀșȹǲtīǮȢɇȜŨǲ@ç¸ôÃŠHȆɁȔɀșȹǲtīǮľ(ȢɇȜțɇȘȢɇȜțɇȘǑØØȘȫȓɅ@ƁxêđįĠɋű~cȢɇȜȘȣȆɊ¸ôĹ÷ZžɉÃŠHZžɊǮGEFJ ɉþÕɊ• źǱõǝĒĒɉÑǒăǒ56·ďɊƁģǰțɁȪɇȅ#ȃǠǮĥ"ǝÃŠHZž• ȚɅȕɇȢɇȜǱȀȃÃŠHZžǲİŴɈlH• KÙsĹ÷Zž@AǮåS¹¸Ĺ÷Zž@ Aǝɍlàþ¸ôĹ÷Zž• ÝõțɁȪɇǲıɉ*<ǲZžǱyǤȃsǿȞȽɇȦɅȐǳEÎǝ ǘɊ• 3DǳùȢɇȜǮxȢɇȜǲåS– ùȢɇȜɐk¸ǲȓȆǱȀȃ8ôɉãFz¸ìêđģǱź'pɐxȢɇȜǶj¯ɊƂĔǱȀȃ8ô– xȢɇȜɐĔǱȀȃ8ô– ôłüģůøĎǜȁȵȣɁȧȟȏĐ¡ȅîs– ¸,êđģDǮȺȻɀȪɅȤĎǲȣɂɇȤȋȯŭ)ȅ¥°– ĹđŨǮȢɇȜĈFŨǲÙĂǰ¬sǒùǿȕȈșǰǯǲȢɇȜîǮģ,ǲĳÒǽ

• ĹđŨǮȶȘȣȴȜȘȫȓɅǭǲsɐ– ĹđŨ@(KA¸ûĉ8@(&)!(AIHH.8@(AIHH1