GPU-Based All Pairs Shortest Paths Lgorithm’s Research And Application

Gerneral purpose Grpah Processing Units （GP GPUs） computing hasbecome a hotspot of the High Performance Computing in recently years.It has high computation power and costs low. GPU’s parallel computationability is very useful for sciencifical computing and enterprise’s dataanalysis with a huge amount of data.Shortest path problem is a classical question in graph theory, whichhas high value both on theoretical research and applications.Floyd-Warshall algorithm can efficiently solve the APSP （All-pairsShortest Paths） problem. Floyd algorithm has been used in logisticsenterprise for searching an appropriate location as its districbution center.However, the time complexity of Floyd algorithm is O(n³), which meanslarge graphs involving millions of vertices are a big challenge. If we canimplement this algorithm in a parallel way, it must apparently acceleratecomputing process.In this situation, implementation of Floyd algorithm on the Nvidia GPUs using the CUDA parallel model can solve the shortest pathsproblem much more quickly. It helps logistics enterprise to choose anappropriate place from mass vertices in a real map. Based on CUDAarchitecture, this paper achieved the following work:1, Design the parallel strategy of the Floyd algorithm based on GPU,and implement its CUDA program on Tesla M2050. Compared to serialprogram, the speedup is over151.43x.2. After the research of Venkataraman’s idea of tiled matrix, weanalyze and prove the method of tiled parallel of FLoyd on GPU. Then,we implement the improved CUDA program, and earn the speedup about6x.3. Using those results talked above, on a real map （contains8000vertices）, the program can calculate all shortes paths in very short timeabout50seconds. The results give the best place with the least weightsand costs to be the distribution center, which makes max benefits.