research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleOn the Implementation of Parallel Shortest Path Algorithms on a Supercomputer
Bibtex cite IDRACTI-RU1-2006-46
Booktitle International Symposium on Parallel and Distributed Processing and Applications
Series Lecture Notes in Computer Science
Year published 2006
Month July
Volume 4330
Pages 406-417
Publisher Springer Berlin / Heidelberg
Organization ISPA 2006
We investigate the practical merits of a parallel priority queue through its use in the development of a fast and work-efficient parallel shortest path algorithm, originally designed for an EREW PRAM. Our study reveals that an efficient implementation on a real supercomputer requires considerable effort to reduce the communication performance (which in theory is assumed to take constant time). It turns out that the most crucial part of the implementation is the mapping of the logical processors to the physical processing nodes of the supercomputer. We achieve the requested efficient mapping through a new graph-theoretic result of independent interest: computing a Hamiltonian cycle on a directed hyper-torus. No such algorithm was known before for the case of directed hypertori. Our Hamiltonian cycle algorithm allows us to considerably improve the communication cost and thus the overall performance of our implementation.
Di Stefano, G.
Petricola, A.
Zaroliagis, Christos
fulltext.pdf (main file)
Publication ID119