Academic
Publications
A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA-Compatible GPU

A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA-Compatible GPU,10.1109/ISPA.2008.40,Tomohiro Okuyama,Fumihik

A Task Parallel Algorithm for Computing the Costs of All-Pairs Shortest Paths on the CUDA-Compatible GPU   (Citations: 3)
BibTex | RIS | RefWorks Download
Abstract This paper proposes a fast method,for computing,the costs of all-pairs shortest paths (APSPs) on the graph- ics processing unit (GPU). The proposed method is imple- mented using compute unified device architecture (CUDA), which offers us a development,environment for performing general-purpose computation on the GPU. Our method is based on Harish’s iterative algorithm that computes,the cost of the single-source shortest path (SSSP) for every source vertex. We present that exploiting task parallelism in the APSP problem allows us to efficiently use on-chip mem- ory in the GPU, reducing the amount of data being trans- ferred from relatively slower off-chip memory.,Further- more, our task parallel scheme is useful to exploit a higher parallelism, increasing the efficiency with highly threaded code. As a result, our method is 3.4‐15 times faster than the prior method. Using on-chip memory, our method elim- inates approximately 20% of data loads from off-chip mem- ory.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: