Abstract: As for the all-pairs shortest path problem in the graph, based on parallel algorithm in the CPU cluster envi- ronment, depending on parallel speedup mechanism on the GPU, in order to increase the parallelism and locality, chess- board division method was chosen for task division in this parallel algorithm on the GPU. Because the graph scale is lar- ger than the display memory, the asynchronous parallel algorithm on the GPU was presented. hhe experimental data proves that the algorithm has accelerating effects below compared with CPU with single core: first, for the small graph whose vertexes arc less than 10000, it is about 155 times faster; second,for the large graph whose vertexes arc more than 10000,it is about 25 times faster.

Key words: Shortest path, GPU, Chessboard division, Floyd