A Scalable Parallelization of All-Pairs Shortest Path Algorithm for a High Performance Cluster Environment

We present a parallelization of the Floyd-Warshall all pairs shortest path algorithm for a distributed environment. A lot of versions of the Floyd-Warshall algorithm have been proposed for a uniprocessor environment, optimizing cache performance and register usage. However, in a dis-tributed environment, communication costs between nodes have to be taken into consideration. We present a novel algorithm, Phased Floyd-Warshall, for a distributed envi-ronment, which optimally overlaps computation and com-munication. Our algorithm is compared with a register op-timized version of the blocked all pairs shortest path algo-rithm [6, 4, 1] which is adapted for a distributed environ-ment. We report speedups of 2.8 in a 16-node cluster and 1.2 in a 32-node cluster for a matrix size of 4096. 1