Single Source Shortest Path Algorithm on GPUs
Implement
the topology and data-driven version of SSSP on GPU. Implement GPU
optimizations that are applicable, e.g., coalesced memory access. Check
the correctness of the results with a sequential CPU implementation.
Compare the execution times of the three versions: topology-driven,
data-driven and sequential versions for the graph given below. Use the
turning gpu machine for the assignment.
Use vertices with vertex ids 0, 500, 1000, 10000, 50000 and 100000 for comparison.
Graph data
The above graph is in METIS format. Section 4.1.1 of the below manual described the METIS format.
Manual for METIS format.