A Multi-Stage CUDA Kernel for Floyd-Warshall

We present a new implementation of the Floyd-Warshall All-Pairs Shortest Paths algorithm on CUDA. Our algorithm runs approximately 5 times faster than the previously best reported algorithm. In order to achieve this speedup, we applied a new technique to reduce usage of on-chip shared memory and allow the CUDA scheduler to more effectively hide instruction latency.

• Publication year

  2010

• Venue

  arXiv.org

• Publication date

  2010-01-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1001.4108
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving path problems on the GPU

  2010cited by this paper
• All-pairs shortest-paths for large graphs on the GPU

  2008influential reference
• Accelerating Large Graph Algorithms on the GPU Using CUDA

  2007influential reference
• Network analysis using transitive closure: New methods for exploring networks

  2006cited by this paper
• Program generation for the all-pairs shortest path problem

  2006cited by this paper
• Parallel FPGA-based all-pairs shortest-paths in a directed graph

  2006cited by this paper
• A blocked all-pairs shortest-paths algorithm

  2003cited by this paper
• Cache-friendly implementations of transitive closure

  2001cited by this paper
• A Theorem on Boolean Matrices

  1962cited by this paper

• Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units

  2022cites this paper
• SIMD2: a generalized matrix instruction set for accelerating tensor computation beyond GEMM

  2022cites this paper
• A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process

  2021cites this paper
• A new exact algorithm for the shortest path problem: An optimized shortest distance matrix

  2021cites this paper
• Efficient Execution of Dynamic Programming Algorithms on Apache Spark

  2020cites this paper
• Efficient parallel implementations to compute the diameter of a graph

  2020cites this paper
• Comparison of HPC Architectures for Computing All-Pairs Shortest Paths. Intel Xeon Phi KNL vs NVIDIA Pascal

  2020cites this paper
• Patient-Centric Facility Design for Physical Rehabilitation Hospitals

  2019cites this paper
• Toward efficient architecture-independent algorithms for dynamic programs: poster

  2019cites this paper
• Accelerating GPU implementation of All Pairs Shortest Path Algorithm

  2019influential citation
• GENERALIZED BLOCKED FLOYD – WARSHALL ALGORITHM

  2019cites this paper
• Efficient GPU Implementations to Compute the Diameter of a Graph

  2019cites this paper
• Accelerating Johnson ' s All-Pairs Shortest Paths Algorithm on GPU Conference

  2017cites this paper
• GPU Parallel Implementation of Isometric Mapping for Hyperspectral Classification

  2017cites this paper
• GPU-ACCELERATED VLSI ROUTING USING GROUP STEINER TREES

  2017cites this paper
• Route relaxations on GPU for vehicle routing problems

  2017cites this paper
• Graph algorithms on GPUs

  2017cites this paper
• Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks

  2016cites this paper
• Automatic Discovery of Efficient Divide-&-Conquer Algorithms for Dynamic Programming Problems

  2016cites this paper
• SOLUTION OF GRAPH PROBLEMS BY MEANS OF THE STAR-MACHINE BEING IMPLEMENTED ON GPUS

  2016cites this paper
• Оценка локальности параллельных алгоритмов, реализуемых на графических процессорах

  2016cites this paper
• Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem

  2016cites this paper
• Impact Of Thread Scheduling On Modern Gpus

  2014cites this paper
• Mapping dynamic programming algorithms on graphics processing units

  2014cites this paper
• Parallelization of Shortest Path Graph Kernels on Multi-Core CPUs and GPUs

  2013cites this paper
• Simulating large topologies in ns-3 using BRITE and CUDA driven global routing

  2013cites this paper