A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment

Author

Srinivasan, T. ; Gangadharan, B.R. ; Gangadharan, S.A. ; Hayawardh, V.

Author_Institution

Dept. of Comput. Sci. & Eng., Sri Venkateswara Coll. of Eng., Sriperambudur

Volume

2

fYear

2007

fDate

5-7 Dec. 2007

Firstpage

1

Lastpage

8

Abstract

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 distributed environment, communication costs between nodes have to be taken into consideration. We present a novel algorithm, Phased Floyd-Warshall, for a distributed environment, which optimally overlaps computation and communication. Our algorithm is compared with a register optimized version of the blocked all pairs shortest path algorithm [6, 4, 1] which is adapted for a distributed environment. 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.

Keywords

cache storage; graph theory; mainframes; parallel algorithms; parallel machines; workstation clusters; all-pairs shortest path algorithm; cache performance; distributed environment; high performance cluster environment; register usage; scalable parallelization;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 2007 International Conference on

Conference_Location

Hsinchu

ISSN

1521-9097

Print_ISBN

978-1-4244-1889-3

Electronic_ISBN

1521-9097

Type

conf

DOI

10.1109/ICPADS.2007.4447721

Filename

4447721