Type of publication: | Inproceedings |
Entered by: | |
Title | On the Implementation of Parallel Shortest Path Algorithms on a Supercomputer |
Bibtex cite ID | RACTI-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 |
Abstract | 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. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments | |
Publication ID | 119 |