Gunrock BFS on soc-LiveJournal1

[jowens]

We believe the following measurements are consistent with our concern that the Groute paper's characterization of Gunrock's performance on BFS on soc-LiveJournal1 was not representative of its actual performance.

Non-idempotent, not direction optimized:

We note the following runs we did on BFS with soc-LiveJournal1, all "on original input" (MatrixMarket):

• K40+METIS: avg: 40.49 ms, min: 40.00 ms, max: 51.54 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs_k40mx2_metis_soc-LiveJournal1.txt
• K40+random: avg: 37.45ms, min: 37.02ms, max: 47.80ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs_k40mx2_rand_soc-LiveJournal1.txt
• K80+METIS: avg: 38.01 ms, min: 33.80ms, max: 61.02 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs_k80x2_metis_soc-LiveJournal1.txt
• K80+random: avg: 35.43 ms, min: 31.67 ms, max: 57.12 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs_k80x2_rand_soc-LiveJournal1.txt

Idempotent, not direction optimized:

Yuechao notes that he fixed a correctness bug in idempotence mode on 4 October 2016 (gunrock/gunrock@23490d3). For our testing in idempotence mode only, we measured Gunrock versions both immediately before and immediately after this bug was fixed ("the performance differences were very small"). We believe running on any July-October Gunrock build would give similar performance results. Anyway, for idempotence:

• K40+METIS+idempotent: avg: 29.53 ms, min: 27.63 ms, max: 38.99 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs-idem_k40mx2_metis_soc-LiveJournal1.txt
• K40+random+idempotent: avg: 29.26 ms, min: 28.12 ms, max: 38.59 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs-idem_k40mx2_rand_soc-LiveJournal1.txt
• K80+METIS+idempotent+Market: avg: 32.96 ms, min: 30.78 ms, max: 49.34 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs-idem_k80x2_metis_soc-LiveJournal1.txt
• K80+random+idempotent: avg: 31.35 ms, min: 25.89ms, max: 52.96ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/bfs-idem_k80x2_rand_soc-LiveJournal1.txt

DOBFS

Multi-GPU DOBFS was added to BFS primitive, and single-GPU direction_optimizing_bfs was removed as of 26 April 2016 (gunrock/gunrock@1fbbc85). Gunrock's DOBFS has different behavior to Groute's (or anyone else's) BFS, which makes performance differences challenging to explain.

• K40+DOBFS: avg: 27.29 ms, min: 26.18ms, max: 27.84 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/dobfs_k40mx1_soc-LiveJournal1.txt
• K80+DOBFS: avg: 31.20 ms, min: 26.45 ms, max: 39.19 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/dobfs_k80x1_soc-LiveJournal1.txt
• K40+DOBFS+idempotence: avg: 23.40 ms, min: 19.95 ms, max: 24.65 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/dobfs-idem_k40mx1_soc-LiveJournal1.txt
• K80+DOBFS+idempotence: avg: 23.13 ms, min: 21.77 ms, max: 24.94 ms
  https://github.com/gunrock/io/blob/master/gunrock-output/20170303/dobfs-idem_k80x1_soc-LiveJournal1.txt