Chapter 11

GPU-accelerated shortest paths computations for planar graphs

G. Chapuis1; H. Djidjev1; D. Lavenier2; R. Andonov3    1 LANL, Los Alamos, NM, United States2 CNRS, Rennes, France3 University of Rennes 1, Rennes, France

Abstract

We describe three algorithms and their associated graphics processing unit (GPU) implementations for two types of shortest path problems. These implementations target computations on graphs with up to millions of vertices and executions on GPU clusters. The first two algorithms solve the All-Pairs Shortest Path problem. The first of these two algorithms allows computations on graphs with negative edges, while the second trades this ability for better parallel scaling properties and improved memory access. ...

Get Advances in GPU Research and Practice now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.