The Floyd-Warshall algorithm is a widely utilized graph-based technique designed to address the all-pairs shortest path problem. However, its cubic time complexity $O\left(n^{3}\right)$ creates performance bottlenecks when applied to large graphs, especially in sequential execution. This paper explores the use of Intel oneAPI’s Data Parallel C++ (DPC++) programming model to optimize the performance of the Floyd-Warshall algorithm through parallel processing. A comparative performance analysis between sequential and parallel implementations on an Intel Xeon(R) CPU highlights up to a $43 \%$ improvement in execution time for graphs with 800 nodes. The results underscore the potential of parallel computing in significantly reducing computational time for large-scale graph algorithms.
Performance Analysis of Floyd-Warshall Algorithm: Sequential and Parallel Execution Using Intel oneAPI
06.11.2024
432642 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Online Contents | 1995
Partitioning Programs for Parallel Execution: A Case Study in the Intel iPSC/2 Environment
British Library Online Contents | 1997
|A Parallel CFD Algorithm on the Intel PARAGON[TM] Computer
British Library Conference Proceedings | 1993
|Truck News - Clarke and Floyd close
Online Contents | 2003