Communication Avoiding All-Pairs Shortest Paths Algorithm for Sparse Graphs

In this paper, we propose a parallel algorithm for computing all-pairs shortest paths (APSP) for sparse graphs on the distributed memory system with p processors. To exploit the graph sparsity, we first preprocess the graph by utilizing several known algorithmic techniques in linear algebra such as fill-in reducing ordering and elimination tree parallelism. Then we map the preprocessed graph on the distributed memory system for both load balancing and communication reduction. Finally, we design a new scheduling strategy to minimize the communication cost. The bandwidth cost (communication volume) and the latency cost (number of messages) of our algorithm are and O(log 2p), respectively, where S is a minimal vertex separator that partitions the graph into two components of roughly equal size. Compared with the state-of-the-art result for dense graphs where the bandwidth and latency costs are and ), respectively, our algorithm reduces the latency cost by a factor of , and reduces the bandwidth cost by a factor of for sparse graphs with . We also present the bandwidth and latency costs lower bounds for computing APSP on sparse graphs, which are and Ω(log 2p), respectively. This implies that the bandwidth cost of our algorithm is nearly optimal and the latency cost is optimal.