language: en

Implementing Parallel Shortest Paths Algorithms

Marios Papaefthymiou
Department of Electrical Engineering and Department of Computer Science Yale University
Joe Rodrigue
Department of Computer Science Yale University

Abstract We have implemented a parallel version of the Bellman-Ford algorithm for the single-source shortest paths problem. Our software has been developed on the CM-5 using C with CMMD communication primitives. We have empirically compared the efficiency of our implementation with a sequential implementation of the Bellman-Ford-Moore algorithm developed by Cherkassky, Goldberg and Radzik. We have performed our experiments using fifty randomly generated graphs with vertex counts in the range between 2 10 and 2 15 and edge counts in the range between 2 11 and 2 21 . In our experiments, the parallel implementation becomes faster than the sequential implementation when the average degree of the input graphs exceeds 2 5 or 2 6 . For the dense graphs in our test suite, we obtain speedups of up to 3.3 on 32 processors and up to 8.3 on 128 processors. In the implementation we discuss in this paper, several design decisions were taken in view of the limited time we had to complete a working version of our software. For example, instead of performing any kind of dynamic load balancing, we try to keep the computation load balanced by applying a straightforward data distribution scheme at the beginning of the computation. Moreover, in the code that runs on each processor, we avoid any sophisticated data structures and only use linear arrays. We are currently experimenting with alternative implementations that may lead to improved speedups, particularly on the denser graphs of our test suite.

1 Introduction