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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
