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

今回の 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