Single-Source Shortest Paths
Problem Description
This benchmark computes the shortest path from a source node to all nodes in a directed graph with non-negative edge weights by using a modified Bellman-Ford algorithm [1,2].
[1] http://en.wikipedia.org/wiki/Bellman-Ford_algorithm
[2] http://www.walden-family.com/public/bf-history.pdf
Algorithm
The computation is implemented in a topology-driven manner; all the graph edges are tried for relaxation in every iteration and another iteration is executed if at least one edge was relaxed in the previous iteration. This continues until a fixed-point.for all nodes src { dsrc = dist[src]; for each edge <src, dst, wt> { ddst = dist[dst]; if ddst > dsrc + wt { dist[dst] = dsrc + wt; anotheriteration = true; } } }The body of the outer for loop is implemented as the kernel. The kernel is repeatedly called from the host until a fixed-point is reached.
Performance
The benchmark is written in CUDA.Compile as: make
Execute as: sssp-wlc <graphfile>
e.g., sssp-wlc USA-road-d.NY.gr
Graph | Time (ms) |
---|---|
rmat22 | 649.61 |
USA | 126655.91 |
random23 | 265.95 |
The above performance is observed on a 1.45 GHz Quadro 6000 with 6 GB of main memory and 448 cores distributed over 14 SMs. It has 64 kB of fast memory per SM that is split between the L1 data cache and the shared memory.