研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

Graph500, Green Graph 500 (June 2013)

2013-06-19 02:48:39 | Weblog
Graph 500 と Green Graph 500 が更新された。

◯ Graph 500 - http://www.graph500.org/results_jun_2013
上位を IBM - BlueGene/Q が独占するという状況に大きな変化なしだが、主な変更点は以下のエントリーだろう。
・2 位:mira (49152 nodes, SCALE40, 14328 GE/s) の更新(前回は 32768 node, SCALE39, 10461 GE/s)。
・6 位:Tianhe-2 (4096 nodes, SCALE36, 1427 GE/s 8192 nodes, SCALE 36, 2061.48 GE/s) で追加。
・13 位:Oakleaf-FX (4800 nodes, SCLAE38, 992.6 GE/s) の更新(前回は 4800 nodes, SCLAE38, 609.37 GE/s)。

なお 13 位の Oakleaf-FX は Graph CREST チーム(東工大チーム)の成果であり、
前回の 609.37 GE/s から 992.6 GE/s へ 1.6 倍の性能向上となっており、
前回と同様の計算機環境と SCALE なので実装やアルゴリズムによる高い性能向上が示された。
非 BlueGene/Q ということも注目して頂きたい。


◯ Green Graph 500 - http://green.graph500.org/lists.php
今回が第1回目のリスト発表となったが、案の定(?)、Big Data category と Small Data category に分けての発表に。
SCALE 30 がしきい値になっている模様で、無理にでも SCALE 30 を解かなかったことが正直悔やまれる。

● Big Data category
・1位:JUQUEEN が 5.41 MTEPS/W
・2位:Mira が 4.42 MTEPS/W
・3位:Sequoia が 3.55 MTEPS/W
このように Big Data category では上位を IBM - BlueGene/Q が独占するという Graph 500 と同様の結果に。



● Small Data category
続いて Small Data category では、私の実装が上位 5 エントリーを占め、
上位 12 エントリーでも私の実装が 11つを占めているという状況でこちらは予想通りの結果となっている。

解説すると、まず 1位の GraphCREST-Tegra は名前から連想されるように Android タブレット機での実験となっており、
Android NDK を用いてポーティングしているが、色々と細かい Linux との違いにより簡単ではなかった印象。
また 2, 3, 4, 5 位のうち 2位と3位 が低電力デスクトップ機、4位と5位がノートPC機とよく似た計算機構成で、
いずれも 53.82 MTEPS/W と 53.47 MTEPS/W 、52.02 MTEPS/W と 51.62 MTEPS/W で同等の性能となっている。
一方、サーバ機としては 6 位の TH-IVB-FEP/C (Tianhe-2 1node) に最高値 39.29 MTEPS/W となっている。
油冷サーバ機である 8 位の ULP2012 ultra-green oil-cooled server: GraphCREST の 30.41 MTEPS/W を超えてきたところを考えると、
Tianhe-2 は電力効率もかなり考慮されていると予想される。


Graph500 参照実装に Hybrid algorithm が追加。

2013-06-03 07:52:17 | Weblog
今回の Graph500 も締切である 6/9 が迫ってきている。
tar.gz の形では 2.1.4 が最新版であるが、
gitorious として https://www.gitorious.org/graph500/graph500 で最新版が公開されている。
なお最新の OpenMP 版の参照実装では Beamer's hybrid algortihm が選択され、
bfs_top_down_step 関数と bfs_bottom_up_step 関数が ./omp-csr/omp-csr.c に実装されている。

早速、以下の環境で試したところ、
性能は max_TEPS は 0.138 GTEPS から 0.506 GTEPS へ 4 倍ほど向上しているもののあまり高くなく、
こちらの top-down だけの結果 0.9 GTEPS の半分ほどに留まっている。


◯ reference 2.1.4 (top-down only)
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 1.23237174159999991e+01
construction_time: 3.05671973749999992e+01
nbfs: 64
min_time: 3.88694007799999985e+00
firstquartile_time: 4.68514209449999974e+00
median_time: 5.03964143450000002e+00
thirdquartile_time: 5.32009851299999958e+00
max_time: 5.88019123399999977e+00
mean_time: 4.98084942437500011e+00
stddev_time: 4.85448413602338535e-01
min_nedge: 5.36865498000000000e+08
firstquartile_nedge: 5.36865498000000000e+08
median_nedge: 5.36865498000000000e+08
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 5.36865498000000000e+08
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 9.13006867694670707e+07
firstquartile_TEPS: 1.01863404233317941e+08
median_TEPS: 1.06898666529981360e+08
thirdquartile_TEPS: 1.15519255795902520e+08
max_TEPS: 1.38120343310319483e+08
harmonic_mean_TEPS: 1.07785932128909156e+08
harmonic_stddev_TEPS: 1.32352296245960379e+06


◯ gitorious 版 reference (6/2) (hybrid algorithm)
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 3.86461791213000026e+02
construction_time: 2.06101513767999990e+02
nbfs: 64
min_time: 6.54244530000000074e-02
firstquartile_time: 6.65645294999999970e-02
median_time: 6.69244999999999979e-02
thirdquartile_time: 1.36217951174999996e+00
max_time: 1.74811406399999991e+00
mean_time: 6.78686857937500054e-01
stddev_time: 6.71586582494595130e-01
min_nedge: 0.00000000000000000e+00
firstquartile_nedge: 0.00000000000000000e+00
median_nedge: 0.00000000000000000e+00
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 2.51655702187500000e+08
stddev_nedge: 2.70025835680461287e+08
min_TEPS: 0.00000000000000000e+00
firstquartile_TEPS: 0.00000000000000000e+00
median_TEPS: 0.00000000000000000e+00
thirdquartile_TEPS: 3.94570124163497090e+08
max_TEPS: 5.05953774048208296e+08
harmonic_mean_TEPS: 8.34498407303683162e+08
harmonic_stddev_TEPS: 1.15107849422285736e+08


◯ 計算機環境
Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
4-way x 8-cores x 2-HT = 64 threads
512 GB RAM
gcc 4.4.7