Setting Parameters for Direction-Optimized BFS

Beamer et al.'s direction-optimized breadth first search defined two tuning parameters, alpha and beta. Alpha indicates where to switch from top-down to bottom-up; beta indicates where to switch back to top-down at the end. These parameters are architecture- and dataset-dependent.

S. Beamer, K. Asanovic, and D. Patterson, Direction-optimizing breadth-first search, SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2012. DOI

In Beamer et al.'s implementation (on multi-socket CPU servers), alpha and beta were relatively insensitive to the dataset. Gunrock's alpha and beta (which we call do_a and do_b) are considerably more dependent on the dataset. The following experiments show performance, measured in MTEPS, when we sweep do_a and do_b on 8 datasets: hollywood-2009, indochina-2004, rmat_n22_e64, rmat_n23_e32, rmat_n24_e16, road_usa, soc-LiveJournal1, and soc-orkut.

Note that while the "islands" of high performance (the dark regions) for each dataset are relatively large, they are in different regions of do_a and do_b for different datasets. It appears to be an interesting research problem to automatically set these two tuning parameters in Gunrock, with possible approaches to pursue either a static decision (given static characteristics of a graph like vertex and edge count) or a dynamic decision (as the computation is running).

hollywood-2009 source data