Scalability on multiple GPUs

Scalability of DOBFS, BFS, and PR. {Strong, weak edge, weak vertex} scaling use rmat graphs with {224, 219, 219 × |GPUs|} vertices and edge factor {32, 256 × |GPUs|, 256} respectively. DOBFS runs have idempotence disabled, though results with idempotence enabled have similar runtimes.

While providing both weak-vertex and -edge scaling, DOBFS doesn't have good strong scaling, because its computation and communication are both roughly on the order of O(|Vi|). This effect is more obvious on P100, as computation is faster but inter-GPU bandwidth stays mostly the same. BFS and PR achieve almost linear weak and strong scaling from 1 to 8 GPUs.

DOBFS

BFS

PageRank

[DOBFS source data] [BFS source data] [PageRank source data], with links to the output JSON for each run