Dijkstra's algorithm performs the best sequentially on a single CPU core. Bellman-Ford implementations and variants running on the GPU outperform this sequential Dijkstra case, as well as parallel Delta-Stepping implementations on multicores, by several orders of magnitude for most graphs. However, there exist graphs (such as road-networks) that perform well only when Dijkstra's algorithm is used. Therefore, which implementation and algorithm should be used for generic cases?
Maleki et al. achieved improvements over delta-stepping:
Saeed Maleki, Donald Nguyen, Andrew Lenharth, María Garzarán, David Padua, and Keshav Pingali. 2016. DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem. In Proc.\ 2016 International Conference on Supercomputing (ICS '16). ACM, New York, NY, USA, Article 32, DOI: https://doi.org/10.1145/2925426.2926287.
At the end of the Abstract they write:
"Our results show that DSMR is faster than the best previous algorithm, parallel [Delta]-Stepping, by up-to 7.38x".
Page 9, col 1, line -3:
"Machines: Two experimental machines were used for the evaluation: a shared-memory machine with 40 cores (4 10-core Intel(R) Xeon^TM E7-4860) and 128GB of memory; the distributed[-]memory machine Mira, a supercomputer at Argonne National Lab. Mira has 49152 nodes and each node has 16 cores (PowerPC A2) with 16GB of memory."
Best wishes,
Frank
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms