On the Implementation of Parallel Shortest Path Algorithms on a Supercomputer
On the Implementation of Parallel Shortest Path Algorithms on a Supercomputer
复制标题
并行最短路径算法在超级计算机上的实现
DOI：
10.1007/11946441_40
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
C. Zaroliagis
中科院分区：
文献类型：
--
作者：
G. Stefano;A. Petricola;C. Zaroliagis
我们研究了并行优先队列的实际优点，通过它在开发一个快速和工作效率高的并行最短路径算法中的应用，该算法最初是为EREW PRAM设计的。我们的研究表明，在真正的超级计算机上有效地实现需要相当大的努力来降低通信性能（理论上假设需要恒定的时间）。事实证明，实现中最关键的部分是将逻辑处理器映射到超级计算机的物理处理节点。我们通过一个新的独立感兴趣的图论结果实现了所要求的高效映射：计算有向超环面上的哈密顿循环。对于有向超环面的情况，以前还没有这样的算法。我们的哈密顿循环算法使我们能够大大提高通信成本，从而提高实现的整体性能。
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.