FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

GAP Benchmarkについて調べる

gap.cs.berkeley.edu

github.com

GAPベンチマーク・スイートは、評価の標準化によってグラフ処理研究を支援することを目的としている。 グラフ処理評価の差異を少なくすることで、異なる研究努力の比較や改善の定量化が容易になる。 このベンチマークは、グラフカーネル、入力グラフ、評価方法を規定するだけでなく、最適化されたベースライン実装（このレポ）も提供している。

  • Breath First Search (BFS) : 方向最適化
  • Single-Source Shortest Paths (SSSP) : デルタステップ法
  • PageRank (PR) : プル方向の反復法
  • Connected Component (CC) : Afforest & Shiloach-Vishkin
  • Betweenness Centrality (BC) : ブランデス
  • Triangle Count (TC) : 順序不変、再ラベリング可能

GAP Benchmark Suiteのコンパイル方法

まずはx86でのコンパイルを試行する。

# リポジトリのダウンロード
$ git clone https://github.com/sbeamer/gapbs.git

$ make bench-graphs
$ make bench-run

bench-graphsはダウンロードしたベンチマーク・テストセットから、ベンチマーク・プログラムに入力するために型の変換を行う。

bench-runは実際にベンチマークプログラムの実行を行う。通常の実行であれば、大きめのサーバであっても数時間を要する。

./pr -f benchmark/graphs/road.sg -i1000 -t1e-4 -n16 > benchmark/out/pr-road.out
./cc -f benchmark/graphs/road.sg -n16 > benchmark/out/cc-road.out
./bc -f benchmark/graphs/road.sg -i4 -n16 > benchmark/out/bc-road.out
./bfs -f benchmark/graphs/kron.sg -n64 > benchmark/out/bfs-kron.out
./pr -f benchmark/graphs/kron.sg -i1000 -t1e-4 -n16 > benchmark/out/pr-kron.out
./cc -f benchmark/graphs/kron.sg -n16 > benchmark/out/cc-kron.out
./bc -f benchmark/graphs/kron.sg -i4 -n16 > benchmark/out/bc-kron.out
./tc -f benchmark/graphs/kronU.sg -n3 > benchmark/out/tc-kron.out
./bfs -f benchmark/graphs/urand.sg -n64 > benchmark/out/bfs-urand.out
./pr -f benchmark/graphs/urand.sg -i1000 -t1e-4 -n16 > benchmark/out/pr-urand.out
./cc -f benchmark/graphs/urand.sg -n16 > benchmark/out/cc-urand.out
./bc -f benchmark/graphs/urand.sg -i4 -n16 > benchmark/out/bc-urand.out
./tc -f benchmark/graphs/urandU.sg -n3 > benchmark/out/tc-urand.out
./sssp -f benchmark/graphs/twitter.wsg -n64 -d2 > benchmark/out/sssp-twitter.out
./sssp -f benchmark/graphs/web.wsg -n64 -d2 > benchmark/out/sssp-web.out
./sssp -f benchmark/graphs/road.wsg -n64 -d50000 > benchmark/out/sssp-road.out
./sssp -f benchmark/graphs/kron.wsg -n64 -d2 > benchmark/out/sssp-kron.out
./sssp -f benchmark/graphs/urand.wsg -n64 -d2 > benchmark/out/sssp-urand.out
./tc -f benchmark/graphs/twitterU.sg -n3 > benchmark/out/tc-twitter.out
./tc -f benchmark/graphs/webU.sg -n3 > benchmark/out/tc-web.out
./tc -f benchmark/graphs/roadU.sg -n3 > benchmark/out/tc-road.out

結果は実行時間で取得できる。

for out in `ls -1 *.out`
do
    echo -n  ${out} ':' 
    grep Average ${out}
done
bc-kron.out :Average Time:        78.94669
bc-road.out :Average Time:        829.96082
bc-twitter.out :Average Time:        39.44177
bc-urand.out :Average Time:        94.57923
bc-web.out :Average Time:        20.79808
bfs-kron.out :Average Time:        4.07169
bfs-road.out :Average Time:        206.68253
bfs-twitter.out :Average Time:        4.17816
bfs-urand.out :Average Time:        4.29056
bfs-web.out :Average Time:        3.77706
cc-kron.out :Average Time:        4.39335
cc-road.out :Average Time:        0.36037
cc-twitter.out :Average Time:        1.37252
cc-urand.out :Average Time:        3.68049
cc-web.out :Average Time:        0.89868
pr-kron.out :Average Time:        32.72281
pr-road.out :Average Time:        1.25165
pr-twitter.out :Average Time:        18.62348
pr-urand.out :Average Time:        39.28258
pr-web.out :Average Time:        4.29745
sssp-kron.out :Average Time:        49.12129
sssp-road.out :Average Time:        56.80930
sssp-twitter.out :Average Time:        33.54466
sssp-urand.out :Average Time:        46.43984
sssp-web.out :Average Time:        51.23079
tc-kron.out :Average Time:        330.52365
tc-road.out :Average Time:        0.03027
tc-twitter.out :Average Time:        45.55035
tc-urand.out :Average Time:        84.87536
tc-web.out :Average Time:        18.31299