Solving Path Problems on the GPU

Aydin Buluc, John R. Gilbert, Ceren Budak
Computer Science Department, University of California, Santa Barbara, CA 93106-5110
Parallel Computing (17 December 2009)


   title={Solving path problems on the GPU},

   author={Bulu{c{c}}, A. and Gilbert, J.R. and Budak, C.},

   journal={Parallel Computing},






   publisher={Elsevier Science Publishers BV}


We consider the computation of shortest paths on Graphic Processing Units (GPUs). The blocked recursive elimination strategy we use is applicable to a class of algorithms (such as all-pairs shortest-paths, transitive closure, and LU decomposition without pivoting) having similar data access patterns. Using the all-pairs shortest-paths problem as an example, we uncover potential gains over this class of algorithms. The impressive computational power and memory bandwidth of the GPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. We implemented a recursively partitioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations. The alternate schedule of path computations allowed us to cast almost all operations into matrix
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: