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

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

安井雄一郎

中央大学, CREST

ERATO

2012.12.12

Outline

1

NETAL (NETwork Analysis Library)

ネットワーク解析

最短路問題と中心性指標

計算機資源の要求量を考慮した高速化

計算機のメモリ階層構造を考慮した効率的なスレッド並列計算手法

NUMA

アーキテクチャを考慮したデータ参照の改善

数値実験

2

並列

BFS

アルゴリズム

Graph500, GreenGraph500

Kronecker Graph

Level Synchronized parallel BFS

Hybrid Algorithm for Parallel BFS

NUMA

を考慮した

Hybrid Parallel BFS

性能比較実験

5th Graph500 / (1st) GreenGraph500

背景

!

ネットワーク解析

は

,

様々な応用の存在し

,

近年の重要性が高まっている

医療

,

ソーシャルネットワーク

,

知識

,

生物

,

電力網

,

モデリング

,

シミュレーション

, ...

で生じるデータの関係性からネットワークを構築し構造を解析する

特に

最短路を用いた中心性指標

は重要なカーネル

!

中心性指標

に対する既存実装は

性能が十分でない

GraphCT

:

多機能ネットワーク解析ツール

枝長を考慮しないBC (Betweenness,媒介中心性)を計算 道路ネットワーク USA-road-d.LKS.gr (n = 2.76M, m = 6.89M) : 20.6日間 特許引用ネットワーク cit-Patents (n = 3.77M, m = 16.52M) : 23.6時間 性能を引き出すためには特殊な計算機環境(CRAY XMT)が必要

ボトルネック

となる

最短路計算

に対する汎用的な実装は存在しない

⇒

高性能ネットワーク解析ライブラリ

NETAL

の開発と性能評価

枝長を{考慮した, 考慮しない}CC, GC, SC, BCを同時に計算 道路ネットワーク USA-road-d.LKS.gr (n = 2.76M, m = 6.89M) : 19.4時間 特許引用ネットワーク cit-Patents (n = 3.77M, m = 16.52M) : 2.52時間 汎用的な NUMA アーキテクチャを有した Intel/AMD サーバ上で高性能を達成

複数中心性指標の同時計算

複数中心性指標の同時計算に対する Brandes’ algorithm*

closeness (CC) CC(v) =_∑ 1 t∈VdG(v,t) graph (GC) CG(v) =_max 1 t∈VdG(v,t) stress (SC) CS(v) =

∑

s!v!t∈V

σ

st(v) betweenness (BC) CB(v) =

∑

s!v!t∈V

σ

st(v)

σ

st multipathBFS→ 重みなし中心性 multipathSSSP→ 重み付中心性 6行目: ShortestPath phase 8-20行目: UPdate phase 入力: 有向グラフ G = (V,E) 出力: 中心性指標CC[v], CG[v], CS[v], CB[v], ∀v ∈ V (0 で初期化) 1: for s ∈ V parallel do 2: /* σ[v] 点 v における最短路通過数 */ 3: /* S 始点からの訪問履歴 */ 4: /* P[v] 点 v での最短路における直前点リスト */ 5: /* dG[v] 点 v での始点からの最短距離 */ 6: σ,S,P,dG← multipathBFS(G,s) 7: 8: CC[s] ←_{∑t∈V dG(s,t)}1 9: CG[s] ←_{maxt∈V dG(s,t)}1 10: while S ! /0 do 11: pop w ← S 12: for v ∈ P[w] do 13: δS[v] ← (1 + δS[w]) 14: δB[v] ← δB[v] +σ[w]σ[v]· (1 + δB[w]) 15: end for 16: if w ! s then 17: CS[w] ← CS[w] +σ[w] ·δS[w] 18: CB[w] ← CB[w] +δB[w] 19: end if 20: end while 21: end for * U. Brandes, A Faster Algorithm for Betweenness Centrality, (2001)

最短路問題

最短路問題は最も基本的な組合せ最適化問題の

1

つで現在も盛んに研究されている

1 2 3 4 5 6 7 8 9 10 11 12 2 2 3 3 2 1 1 3 2 1 2 1 2 3 1 1 1 始点 1 とした 1 対全最短路

−−−−−−−−−−−−−−−−−−−−→

1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 1 2 2 1 1 1 有向グラフ G = (V,E), 点数 n = |V|, 枝数 m = |E|, 枝長 ! : E → R+

始点と終点の個数に応じて問題を分類する

始点 ×1 終点 ×n → 1対全最短路 SSSP (重みなし: 幅優先探索BFS) 始点 ×β 終点 ×n → 複数対全最短路 MSSP (SSSP ×

β)

始点 ×n 終点 ×n → 全対全最短路 APSP → 更に出力(距離, パス, 代替パス) に応じた分類 (例: SSSP)

distanceSSSP

1 distance 0 2 2 3 3 2 3 4 5 6 7 8 910 11 12 4 5 5 4 6 7 7 最短路距離を出力

singlepathSSSP∗

1 distance 0 2 2 3 3 2 3 4 5 6 7 8 910 11 12 4 5 5 4 6 7 7 1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 1 2 2 1 1 1 単純な最短パスを出力

multipathSSSP

1 distance 0 2 2 3 3 2 3 4 5 6 7 8 910 11 12 4 5 5 4 6 7 7 1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 2 1 2 2 1 1 1 1 代替を考慮した最短パスを出力

∗

多くの既存実装の対象は

singlepath

SSSP

2-HEAP:

メモリ階層構造を考慮した高速化を行った

Dijkstra’s algorithm

優先キュー付ダイクストラ法に対し, 並行実行した場合の性能低下率を評価. 効率的に高速化に行うための解析手法を提案. 既存実装に比べ, 並行実行時の性能低下率が最も低い効率的なダイクストラ法 2-HEAP を開発. 9th DIMACSの参照実装 MLB は同時実行時の性能低下が大きく, 並列実行の効果が得られにくい. 全米道路ネットワークに対する singlepathSSSP 交差点を点,交差点間の道路を枝で表現 点数 n = 23.95M 枝数 m = 58.33M 2-way Xeon X5460 3.16GHz (4 cores × 2) における SSSP あたりの実行時間 [ms]

CPU time (speedup) RAM [GB] 2-HEAP* (sequential) 5300.8 (× 1.00) 0.90 2-HEAP* ( 2 threads) 2734.4 (× 1.94) 1.27 2-HEAP* ( 4 threads) 1451.3(× 3.65) 2.00 2-HEAP* ( 8 threads) 1031.7 (× 5.14) 3.46 MLB (sequential) 5873.0 2.17 *安井, 藤澤, 笹島, 後藤: 大規模最短路問題に対するダイクストラ法の高速化 安井 (中央大学, CREST) メモリ階層構造を考慮した大規模グラフ処理の高速化 ERATO 6 / 28

同時実行時の性能低下率による

,

メモリ階層構造上のボトルネック解析

bottleneck diff-procs diff-L2 same-L2

processor ↔ RAM bandwidth down down down processor inside bandwidth - down down

L2 cache sharing - - down

Arithmetic performance - - -RAM same processor, different L2 caches same processor, same L2 cache different processors 共有する計算機資源に応じた 2 コアの組合せ diff-procs :異なるソケット diff-L2 :同一ソケットだが L2 は非共有 same-L2 :同一ソケットで L2 を共有 2-way Xeon X5460上での SSSP (USA-road-d.USA.gr) に対する同時実行性能

sequential diff-procs diff-L2 same-L2

2-HEAP* 5.34 s (± 0.00%) 5.44 s (- 1.93%) 5.62 s (- 5.05%) 6.63 s (-18.94%) d-heap 7.23 s (± 0.00%) 7.26 s (- 0.41%) 7.59 s (- 4.74%) 8.79 s (-17.75%) Fib-heap 15.95 s (± 0.00%) 16.09 s (- 0.87%) 16.56 s (- 3.68%) 18.17 s (-12.22%) Dial’s 4.38 s (± 0.00%) 4.54 s (- 3.52%) 5.01 s (-12.58%) 6.38 s (-31.35%) double buckets 4.65 s (± 0.00%) 4.88 s (- 4.71%) 5.25 s (-11.43%) 6.64 s (-29.97%) MLB 5.69 s (± 0.00%) 5.85 s (- 2.74%) 6.17 s (- 7.78%) 7.73 s (-26.39%) ∆-stepping 11.74 s (± 0.00%) 12.06 s (- 2.66%) 12.55 s (- 6.41%) 16.49 s (-28.76%) *安井, 藤澤, 笹島, 後藤: 大規模最短路問題に対するダイクストラ法の高速化

NETAL (NETwork Analysis Library)

実ネットワークに対するAPSPと中心性計算 (CC,GC,SC,BC)において最も高速

計算機のメモリ階層構造を考慮した効率的なスレッド並列計算手法

各コアに独立した最短路計算を割り当てる非常に単純な並列化である

NUMAアーキテクチャを考慮したアフィニティ設定 (CPU コアと使用 RAM のバインド)

による高いスケーラビリティの実現

APSPに対する 3 種類の戦略

全対全最短路 (APSP)

戦略 アルゴリズム 最短路

n-BFS BFS multipathBFS × n n-Dijkstra Dijkstra’s with binary-heap multipathSSSP × n n/β-MLSC MLSC with binary-heap distanceMSSP × n/β

∗ 我々の先行研究2-HEAPの成果を適用

中心性に対する 2 種類の戦略

中心性計算

戦略 アルゴリズム 中心性指標

n-BFS BFS CC,GC,SC,BC

n-Dijkstra Dijkstra’s with binary-heap 重み付 CC,GC,SC,BC ∗ 同時に4種類の中心性指標を計算

APSP

multipath (unweighted)

NETAL (NETwork Analysis Library)

multipath distance Centrality weighted CC, GC, SC, BC CC, GC, SC, BC 1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 2 1 2 2 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 2 1 2 2 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 2 2 2 1 1 2 1 2 2 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 0 2 2 3 3 2 3 4 5 6 7 8 9 10 11 12 4 5 5 4 6 7 7 1 2 32 0 4 3 5 2 3 3 6 4 5 5 2 4 0 1 1 4 5 3 2 4 5 5 1 0 2 2 3 3 2 3 4 5 6 7 8 9 10 11 12 4 5 5 4 6 7 7 1 2 3 2 0 4 3 5 2 3 3 6 4 5 5 2 4 0 1 1 4 5 3 2 4 5 5 1 0 2 2 3 3 2 3 4 5 6 7 8 9 10 11 12 4 5 5 4 6 7 7 1 2 3 2 0 4 3 5 2 3 3 6 4 5 5 2 4 0 1 1 4 5 3 2 4 5 5 in parallel n-BFS n-Dijkstra n/b-MSLC

Y.Yasui et al.: NETAL:High-Performance Implementation of Network Analysis Library Considering Computer

Memory Hierarchy, 2011.

NUMA

アーキテクチャを考慮したデータ参照の改善

4-way opteron 6174 (12 cores × 4 sockets) 上の APSP に対する CPU コアと参照 RAM のアフィニティ設定 各コア (各スレッド) は独立した最短路計算を行う. 各ローカル RAM にグラフデータの複製を配置して高いスケーラビリティを実現. affinityとメモリレイアウト RAM RAM G CPU/Memory affinity Graph Data RAM RAM worst: 48 × 1-affinity 設定 1箇所にグラフデータを配置 RAM RAM G CPU/Memory affinity RAM RAM G G G Graph Data G G G G best: 6 × 8-affinity 設定 各 RAM にグラフデータを配置 USA-road-d.NY.gr (n = 264K, m = 734K) : TEPS値 (speedup)

affinity n-BFS n-Dijkstra n/β-MSLC(β= 32) sequential 20.5 M (×1.0) 10.8 M (×1.0) 122.4 M (× 1.0) 12 threads worst_best 239.4 M (×11.7)_{299.3M (×14.6)} 120.2 M (×11.1)_{134.3M (×12.4) 1430.9}1136.6 M (× 9.2)_{M (×11.7)} 24 threads worst_best 387.8 M (×18.9)_{549.4M (×26.8)} 213.0 M (×19.7)_{249.8M (×23.1) 2634.0}2060.8 M (×16.8)_{M (×21.5)} 48 threads worst_{best 948.6}565.4 M (×27.5) 353.0 M (×32.6) 3805.6 M (×31.1)

アフィニティ設定による実行時間のばらつき

4-way opteron 6174 (12 cores × 4 sockets) に対する afffnity とメモリレイアウトの設定

affinityとメモリレイアウト RAM RAM G CPU/Memory affinity Graph Data RAM RAM worst: 48 × 1-affinity 設定 1箇所にグラフデータを配置 RAM RAM G CPU/Memory affinity RAM RAM G G G Graph Data G G G G best: 6 × 8-affinity 設定 各 RAM にグラフデータを配置 0 50 100 150 200 250 300 350 400 450 500 550 600 650 1 5 10 15 20 25 30

CPU time [seconds]

trials n-BFS (best) n-SSSP (best) n/β-MSSP (best) n-BFS n-SSSP n/β-MSSP n-BFS (worst) n-SSSP (worst) n/β-MSSP (worst) 30回実行したときの実行時間を計測 適切な affinity 設定 (best)は高速かつ安定 不適切な affinity 設定 (worst)は低速かつ不安定 安井 (中央大学, CREST) メモリ階層構造を考慮した大規模グラフ処理の高速化 ERATO 10 / 28

全対全最短路問題

(APSP)

に対する数値実験結果

全米道路ネットワーク USA-road-d.USA.gr 点数 n = 23.95M, 枝数 m = 58.33M

既存実装では1.5∼9.2 年要する distanceAPSP に対 し, n/

β

-MSLCは7.75日間で計算可能 (MLB に比べ 229倍高速, ∆-stepping に比べ 432 倍高速)

n-Dijkstra (multipathSSSP)は MLB, ∆-stepping に比 べ 18 ∼ 34 倍高速

LiveJournal

ネットワーク soc-LiveJournal1 点数 n = 4.85M, 枝数 m = 68.99M

既存実装では数ヶ月要する distanceAPSP に対し, n/

β

-MSLCは2.78日間で計算可能 (MLB に比べ 43 倍高速, ∆-stepping に比べて 104 倍高速)

n-Dijkstra (multipathSSSP)は MLB, ∆-stepping に比べ 13 ∼ 30 倍高速 USA-road-d.USA.gr soc-LiveJournal1

n-BFS 70 days 7.51 days

n-Dijkstra 99 days 9.63 days

n/

β

-MSLC 7.75 days(

β

= 16) 2.78 days(

β

= 32) LS-BFS 557 days (= 1.5 years) 79.25 days MLB 1774 days (= 4.9 years) 120.55 days ∆-stepping 3351 days (= 9.2 years) 288.22 days

中心性指標

(USA-road-d.LKS.gr (n = 2.76M, m = 6.89M))

NETALは 4 種類の中心性指標 CC,CG,CS,CB を計算する

重みなし中心性 (上段, n-BFS で19.4時間),重み付中心性 (下段, n-Dijkstra で22.8時間) GraphCTは枝長を考慮しない BC のみに 20.6 日間要する (4-way Opteron 6174)

closeness CC(v) = 1 ∑t∈VdG(v,t) graph CG(v) = 1 maxt∈VdG(v,t) stress CS(v) =

∑

s!v!t∈V

σ

st (v) _{betweenness CB(v) =}

_∑

s!v!t∈V

σ

st(v)

σ

st 安井 (中央大学, CREST) メモリ階層構造を考慮した大規模グラフ処理の高速化 ERATO 12 / 28

中心性に対する数値実験結果

n-BFS

と

n-Dijkstra

は

,

それぞれ

,

重み有

/

無の中心性指標

C

C

,C

G

,C

S

,C

B

を計算する

GraphCT

との性能比較

GraphCTは多機能グラフ解析ツールキットで, 重みなし CBを計算する NETAL(n-BFS)は4種類の中心性を計算しつつ, GraphCT の13∼26 倍高速である 重みを考慮した中心性計算 NETAL(n-SSSP) には, NETAL(n-BFS) の1.2∼1.3 倍ほどの実行 時間が必要となる

instance n m _(C n-BFS n-Dijkstra GraphCT

C,CG,CS,CB) (weighted CC,CG,CS,CB) (CB) USA-road-d.LKS.gr 2.8M 6.9M 19.35 h (SP 55 %, UP 45 %) 22.84 h (SP 69 %, UP 31 %) 493.8 h cit-Patents 3.8M 16.5M 1.87 h (SP 27 %, UP 73 %) 2.52 h (SP 40 %, UP 60 %) 23.6 h ネットワークに応じて最短路計算 (SP) と中心性指標更新 (UP) の割合が異なる

SSCA#2

との性能比較

SSCA#2は中心性指標 CB計算を用いたベンチマークソフトウェア (マルチスレッドに対応) SSCA#2に対して,n-BFSは 3.8 倍高速, n-Dijkstra は 2.4 倍高速 GraphCTはエラー終了

instance n m _(C n-BFS n-Dijkstra GraphCT SSCA#2

C,CG,CS,CB) (weighted CC,CG,CS,CB) (CB) (CB)

Graph500, GreenGraph500

Graph500

! BFS

性能

「

TEPS ratio

（

Traversed edges per second

）」

で評価

人工的に生成した Kronecker Graph に対する 64 回の BFS を計算.

入力パラメータ SCALE, edgefactor(= 16) で, 点数 n = 2SCALE_{,枝数 m = edgefactor ·n を決定.}

各 BFS の終了時に, 計算結果である BFS 木を用いて検証を行い, TEPS 値を算出する. 現在のルールでは, 64 回中 Medial の TEPS 値で評価を行い, 高い方がより高い順位となる.

GreenGraph500

!

有効電力あたりの

BFS

探索性能

「

GTEPS/kW

」

で評価

測定機器の解像度が荒くうまく測定できない場合, 指定した時間 BFS を繰 り返し計算する energy loop を追加. RemotePDU: Omron RC3008 • 

•  _Genera)onGraph& _Construc)onGraph& BFS Valida)on

Kronecker Graph

クロネッカー積 ⊗ で生成される人工グラフ Kronecker Graph

SCALE

回の

kronecker

積を用いて生成される

.

G

SCALE

= G

1

⊗ G

1

⊗ ... ⊗ G

1

!!!!!!!!!!!!!!!!!!!!!!"#!!!!!!!!!!!!!!!!!!!!!

$

SCALE回

Graph500

では

, 2 × 2

の初期行列を

G

1

=

%

0.57 0.19

0.19 0.05

&

として

,

無向グラフを生成

.

Kronecker Graphの次数分布 SCALE 26, edgefactor 16 有向グラフ 点数 n = 226_{= 67.1M} 枝数 m = 231_{= 2147.5M} 100 101 102 103 104 105 106 107 100 ₁₀1 ₁₀2 ₁₀3 ₁₀4 ₁₀5 ₁₀6 ₁₀7 number of nodes node degree

Level Synchronized parallel BFS

Level Synchronized parallel BFS

深さ毎に同期を行う基本的な並列

BFS

アルゴリズム

.

各点はただ一つの親を持つため

,

同じ深さ内の探索では

atomic

命令に行う必要あり

.

同じ深さの点が少ないと並列化の効果が得られにくい

.

Hybrid Algorithm for Parallel BFS

[Beamer,2012] Direction Optimizing Breadth-First Search

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

Hybrid Algorithm

における

Top-down ↔ Bottom-up

の切り替え

採用する探索方針によって実行時間が大きく異なるため, 切り替えに失敗すると性能が出ない Top-down ⇒ Bottom-up では, 探索枝が急激に増加するため, 正確な見積もりが要求される Bottom-up ⇒ Top-down では, 探索枝がなだらかに減少するため, 近似的な見積もりで十分 mf mu nf n 安井 (中央大学, CREST) メモリ階層構造を考慮した大規模グラフ処理の高速化 ERATO 18 / 28

NUMA

を考慮した

Hybrid Algorithm

の性能

Intel(R) Xeon(R) CPU E5-2690 @ 2.90GHz ×2 (HT32 コア) (α

= 20,

β

= 4)

スレッド数を変化させたときの TEPS 値 (SCALE=26) 0.0e+00 5.0e+09 1.0e+10 1.5e+10 2.0e+10 2.5e+10 3.0e+10 1 2 4 8 16 32

Traversed Edges Per Second (TEPS)

#threads edgefactor= 8

edgefactor=16 edgefactor=32 edgefactor=64

SCALEを変化させたときの TEPS 値 (#threads=32)

0.0e+00 5.0e+09 1.0e+10 1.5e+10 2.0e+10 2.5e+10 3.0e+10 20 21 22 23 24 25 26 27

Traversed Edges Per Second (TEPS)

scale edgefactor= 8

edgefactor=16 edgefactor=32 edgefactor=64

Graph500(/(GreenGraph500

SCALE n m / ( (TEPS) BFS( ( )( (W)( TEPS/kW WestmreEX 80 ( Xeon(E7@(4870(@(2.40GHz((10(cores)(x(4

26 2

26

₂

31

_10.495(G

_102.697

_1010.1

_10.390(G

SandyBridgeEP 32 ( Xeon(E5@2690(@(2.90GHz((16(cores)(x(2

25 2

25

₂

30

_6.777(G

_79.436

_362.7

_18.684(G

MagnyCours((48)( Opteron(6174(@(2.20GHz((12(cores)(x(4

25 2

25

₂

30

_6.335(G

_86.114

SandyBridgeEP 32 ( Xeon(E5@2690(@(2.00GHz((16(cores)(x(2

25 2

25

₂

30

_5.883(G

_91.660

_298.5

_19.710(G

Xeon(E5@2620(@(2.0GHz((12(threads)(x(2(

24 2

24

2

29

4.675(G

57.910

171.0

27.339(G

WestmereEP((24)( Xeon(X5670(@(2.93GHz((12(cores)(x(2(

25 2

25

₂

30

_2.730(G

_197.361

Core(i7@3820QM(@(2.70GHz((2(cores)(

24 2

24

2

29

1.987(G

136.365

38.5

51.620(G

Core(i7@3820QM(@(2.70GHz((2(cores)(

21 2

21

2

26

0.953(G

35.808

23.6

40.395(G

安井 (中央大学, CREST) メモリ階層構造を考慮した大規模グラフ処理の高速化 ERATO 25 / 28

Graph500(/(GreenGraph500

SCALE n m / ( (TEPS) BFS( ( )( (W)( TEPS/kW WestmreEX 80 ( Xeon(E7@(4870(@(2.40GHz((10(cores)(x(4

26

2

26

₂

31

_10.495(G

_102.697

_1010.1

_10.390(G

SandyBridgeEP 32 ( Xeon(E5@2690(@(2.90GHz((16(cores)(x(2

25

2

25

₂

30

_6.777(G

_79.436

_362.7

_18.684(G

MagnyCours((48)( Opteron(6174(@(2.20GHz((12(cores)(x(4

25

2

25

₂

30

_6.335(G

_86.114

SandyBridgeEP 32 ( Xeon(E5@2690(@(2.00GHz((16(cores)(x(2

25

2

25

₂

30

_5.883(G

_91.660

_298.5

_19.710(G

Xeon(E5@2620(@(2.0GHz((12(threads)(x(2(

24

2

24

2

29

4.675(G

57.910

171.0

27.339(G

WestmereEP((24)( Xeon(X5670(@(2.93GHz((12(cores)(x(2(

25

2

25

₂

30

_2.730(G

_197.361

Core(i7@3820QM(@(2.70GHz((2(cores)(

24

2

24

2

29

1.987(G

136.365

38.5

51.620(G

Core(i7@3820QM(@(2.70GHz((2(cores)(

21

2

21

2

26

0.953(G

35.808

23.6

40.395(G

1

2

3

4

5

11

CPU(

(1node(

1

st

_{GraphGreen500-List}

• 

GraphCREST-

-• 

-ISC-

-Graph500 -114- :-GraphCREST8Tegra3-/-SCALE20(/(0.123919(GTEPS(

• 

まとめ

NETAL (NETwork Analysis Library)

汎用的な NUMA アーキテクチャを有した Intel/AMD サーバ上で動作する高速な中心性計算と最短路計算 既存実装では 1.5∼9.2 年要する全対全最短路問題に対し, 7.75 日間で計算可能

道路ネットワークに対する CC, GC, SC, BC : 19.4 時間 (既存: 20.6 日間) 特許引用ネットワークに対する CC, GC, SC, BC : 2.52 時間 (既存: 23.6 時間)

Graph500

Kronecker Graphに対する高速な高効率な BFS アルゴリズム. (small-world 性や scale-free 性を持つ他のグ ラフでも有効であると考えている)

CPUベースの 1node 上で HT 80 コアでスケールし, 最高速 10.390 GTEPS を達成 非公式ながら GreenGraph500 で, 1 ∼ 5 位を独占