Group colloquium: Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths

When: March 22, 2018, 15:45-16:45

Where: RA 3334

Graph processing algorithms have a significant impact on several domains of applications as graphs are used to model conceptual networks, systems and natural phenomena. One of the most important problems in graph processing is the Single-Source Shortest Path (SSSP) problem that has applications in a variety of contexts (e.g., traffic routing, circuit design, formal analysis of computing systems). Due to the significance of the time/space efficiency of solving SSSP on large graphs, researchers have proposed parallel/distributed algorithms. Amongst these, the algorithms that harness the computational power of Graphical Processing Units (GPUs) using NVIDIA’s Compute Unified Device Architecture (CUDA) have attracted noticeable attention in research community. However, efficient utilization of the computational power of GPUs is a challenging (and problem-dependent) task. In this talk we present a highly efficient method that solves SSSP on GPUs for road networks with large dimensions.

	Home > News and Events > Events
<< EEMCS (EWI) Home News and Events » Group Colloquium » Events » In the Media People Research Education Vacancies Intranet Contact	Group colloquium: Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths When: March 22, 2018, 15:45-16:45 Where: RA 3334 Who: Mohsen Safari Graph processing algorithms have a significant impact on several domains of applications as graphs are used to model conceptual networks, systems and natural phenomena. One of the most important problems in graph processing is the Single-Source Shortest Path (SSSP) problem that has applications in a variety of contexts (e.g., traffic routing, circuit design, formal analysis of computing systems). Due to the significance of the time/space efficiency of solving SSSP on large graphs, researchers have proposed parallel/distributed algorithms. Amongst these, the algorithms that harness the computational power of Graphical Processing Units (GPUs) using NVIDIA’s Compute Unified Device Architecture (CUDA) have attracted noticeable attention in research community. However, efficient utilization of the computational power of GPUs is a challenging (and problem-dependent) task. In this talk we present a highly efficient method that solves SSSP on GPUs for road networks with large dimensions.