The All‐Pair Shortest‐Path Problem in Shared‐Memory Heterogeneous Systems
Hector Ortega‐Arranz, Yuri Torres, Diego R. Llanos, Arturo González-Escribano · 2014
This chapter deals with the all-pair shortest path (APSP) problem for sparse graphs combining parallel algorithms and parallel-productivity methods in heterogeneous systems. It begins by introducing some basic concepts and notations related to graph theory, and briefly describing both the sequential Dijkstra's algorithm and the parallel version used. Next, the chapter gives some details for both Fermi and Kepler compute unified device architecture (CUDA) architectures, and describes the heterogeneous systems and explains how the load-balancing techniques try to improve their performance in distributing the work load. Then, it explains in depth our Dijkstra graphical processing unit (GPU) implementation using the ideas presented in heterogeneous implementations with different load-balancing methods. Subsequently, the chapter presents the experimental methodology and used platform, and the input sets considered. This is followed by a discussion of the results obtained, and a summarization of the conclusions derived.