Home
We have implemented an algorithm to solve Single Source Shortest Path (SSSP) problem on GPU. Our algorithm is vertex-based, it means we assign threads to vertices in graphs. In fact, we assign one thread to two vertices to increase the workload of each thread. We have used Compressed Sparse Row (CSR) representation as our data structure to store graphs. We introduce the idea of locality-based relaxation where threads assigned to vertices update the distance of neighbor vertices up to k steps. This idea increases the workload of each kernel launch and decreases the total number of iterations of the algorithm. By having a preprocessing phase, we also decrease CPU-GPU communication. Our implementation uses only one atomic operation, one kernel to launch in each iteration of the algorithm and no intra-block synchronization. We have experimented our approach on real-world road network graphs of some cities and regions in the United States. Please refer to our paper for the details of our method along with the experimental results:
- Safari, M., & Ebnenasir, A. (2017, September). Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths. In International Conference on Topics in Theoretical Computer Science (pp. 43-58). Springer, Cham.
The implementation of our algorithm along with the input graphs are publicly available. You can download the implementation in CUDA from Download tab.