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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Performance Analysis of Floyd-Warshall Algorithm: Sequential and Parallel Execution Using Intel oneAPI


    Beteiligte:
    Kumar, Sanjay (Autor:in) / Karthik, S (Autor:in) / Srilakshmi, S (Autor:in) / Dharun Viginesh, P (Autor:in)


    Erscheinungsdatum :

    06.11.2024


    Format / Umfang :

    432642 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Floyd J. Lupton

    Online Contents | 1995



    A Parallel CFD Algorithm on the Intel PARAGON[TM] Computer

    Tsai, M. C. | British Library Conference Proceedings | 1993