Accelerating all-pairs shortest path search on GPUs

Abstract

The All-Pairs Shortest Path (APSP) problem has many applications, such as driving directions in online map services and connection analysis in social networks. With the need for fast APSP search on large graphs, e.g., social networks of millions of nodes, we study how to accelerate APSP search on a GPU cluster. There are three wellknown sequential algorithms for the APSP problem, namely Dijkstra's, Bellman-Ford's, and Floyd-Warshall's. Various parallel versions of these algorithms have also been proposed. We identify a state-of-the-art single GPU-based parallel APSP algorithm proposed by Katz and Kider, and extend this KK algorithm to work on multiple GPUs on a single node (KK_SN) and on multiple nodes of the cluster (KK_MN). We study the performance of our extended algorithms in comparison with the original algorithm on an 11-node cluster with two multicore CPUs and four NVIDIA M2090 GPUs on each node. The results show that our extended algorithms scale well to the number of GPUs in a single node and the number of nodes in the cluster.

Date of Award	2013
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology