Experimentell utvärdering av GPU-lösningar för SSSP-problemet

Originally designed for computer graphics, the modern graphics processing unit (GPU) has now become a potential powerhouse for parallel calculations through the use of platforms such as CUDA and OpenCL. This paper presents an experimental evaluation of GPU- and CPU-parallel as well as CPU-sequential implementations for solving the single source shortest path problem. The algorithms tested are versions of Dijkstra’s algorithm, the Bellman-Ford algorithm, and Delta-Stepping, from the Boost Graph Library, Parallel Boost Graph Library, Gunrock and LoneStarGPU. Testing the implementations on large graphs modeled on road networks over USA, results indicate that the sequential Boost implementation of Dijkstra’s algorithm gives the best performance if memory transfer time to and from GPU is taken into account. The paper also presents a discussion on possible reasons for this result.Grafikkort, vars ursprungliga syfte är beräkningar inom datorgrafik, kan idag användas för generella beräkningar via plattformar såsom CUDA och OpenCL. Denna rapport presenterar en undersökning av GPU- och CPU-parallella samt CPU-sekventiella implementationer ämnade att lösa SSSP-problemet. De testade algoritmerna är versioner av Dijkstras algoritm, Bellman-Ford-algoritmen, samt Delta-Stepping, från Boost Graph Library, Parallel Boost Graph Library, Gunrock, och LoneStarGPU. Då implementationerna testas på stora grafer modellerade på vägnätverk över USA indikerar resultaten att den sekventiella implementationen av Dijkstras algoritm når snabbast resultat om överföringstid till och från GPU beaktas. Rapporten presenterar även en diskussion kring möjliga anledningar för de funna resultate