Best implementation of BFS (Breadth-first search) and SSSP


I’m looking for best implementations of BFS and SSSP applications for CUDA and OpenACC.

In terms of BFS,
I could find BFS rodinia benchmark and this library( But i think rodinia has quite naive implemention of BFS. Is there any better implementation ?

Thanks in advance

You have a few options in terms of libraries.

There is the MapGraph Open Source Library(funded by DARPA no less);

And there is also the Gunrock library, which seems to offer much of the same functionality(also funded by DARPA);

While I not used either of these libraries, as I tend to ‘roll my own’ CUDA graph algorithms, these both are open source and appear to be well regarded.

Hi @CudaaduC thanks for replying.
Yes, gunrock has implementation of this paper PPoPP '12 paper Scalable GPU Graph Traversal. As I’ve found, it seems the better bfs option.

What about the others ?

Hi All,

We have implemented and open sourced one GPU based BFS which is virtually one order of magnitude faster than PPoPP '12 Scalable GPU Graph Traversal.

The source can be found here:
And the paper is “[SC '15] Enterprise: Breadth-First Graph Traversal on GPUs”