2010/01/23 by Ben Lund, Lund, Ben, Justin W. Smith +2
Computer Science · Engineering · #Algorithms and Data Compression #D.1.3 #Distributed #FOS: Computer and information sciences #Low-power high-performance VLSI design #Parallel #Parallel Computing and Optimization Techniques #Performance (cs.PF) #and Cluster Computing (cs.DC) #cs.DC #cs.PF
paper · pdf · doi:10.48550/arxiv.1001.4108
9 pages, 7 figures, 1 table
openalex publication_date 2010/01/23 · arxiv created 2010/02/25 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.