loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07)
A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment
Hsinchu, Taiwan
December 05-December 07
ISBN: 978-1-4244-1889-3
ASCII Text
x 
 
T. Srinivasan, R. Balakrishnan, S. A. Gangadharan, V. Hayawardh, "A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment," Parallel and Distributed Systems, International Conference on, vol. 1, pp. 1-8, 13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/ICPADS.2007.4447721,
author = {T. Srinivasan and R. Balakrishnan and S. A. Gangadharan and V. Hayawardh},
title = {A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment},
journal ={Parallel and Distributed Systems, International Conference on},
volume = {1},
year = {2007},
isbn = {978-1-4244-1889-3},
pages = {1-8},
doi = {http://doi.ieeecomputersociety.org/10.1109/ICPADS.2007.4447721},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Systems, International Conference on
TI - A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment
SN - 978-1-4244-1889-3
SP1
EP8
A1 - T. Srinivasan,
A1 - R. Balakrishnan,
A1 - S. A. Gangadharan,
A1 - V. Hayawardh,
PY - 2007
KW - null
VL - 1
JA - Parallel and Distributed Systems, International Conference on
ER -
 
T. Srinivasan, Department of Computer Science and Engineering, Sri Venkateswara College of Engineering, Pennalur, Sriperambudur 602105, TN, India
R. Balakrishnan, Department of Computer Science and Engineering, Sri Venkateswara College of Engineering, Pennalur, Sriperambudur 602105, TN, India
S. A. Gangadharan, Department of Computer Science and Engineering, Sri Venkateswara College of Engineering, Pennalur, Sriperambudur 602105, TN, India
V. Hayawardh, Department of Computer Science and Engineering, Sri Venkateswara College of Engineering, Pennalur, Sriperambudur 602105, TN, India
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.
Citation:
T. Srinivasan, R. Balakrishnan, S. A. Gangadharan, V. Hayawardh, "A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment," icpads, vol. 1, pp.1-8, 13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.