This repo contains a case study for parallel graph search algorithms, specifically Bellman Ford, Dijkstra and A-star algorithms.
This repo uses (GNU) make
buildsystem and nvcc
CUDA compiler in order to compile and link the source files. Also, you might want to edit the Makefile
and change the -arch sm_72
flag according to your GPU's compute capability.
In order to compile, link and run, just run:
make all
./pg_search
You can find a detailed write-up about the code and performance evaluation at my website: https://khizar-anjum.github.io/projects/pgsearch.html
We used the following references in our implementation:
- Yichao Zhou and Jianyang Zeng. 2015. Massively parallel a* search on a GPU. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15). AAAI Press, 1248?1254.
- 9th DIMACS Implementation Challenge - Shortest Paths
- rapidcsv by d99kris
- Leskovec, Jure, and Andrej Krevl. "SNAP datasets: stanford large network dataset collection; 2014." URL http://snap. stanford. edu/data (2016): 49.