Enhanced OpenMP Algorithm to Compute All-Pairs Shortest Path on x86 Architectures

图表已经成为不同领域建模和解决问题的关键工具。Floyd-Warshall（FW）算法计算图中所有顶点对之间的最短路径，应用于通信网络、交通路由、生物信息学等领域。然而，FW的计算和空间成本很高，因为它需要O（n^3）操作和O（n^2）内存空间。随着图形变得越来越大，并行计算变得必要，以在可接受的时间范围内提供解决方案。在本文中，我们研究了一个针对Xeon Phi KNL处理器开发的FW代码，并将其适配到任何Intel x86处理器上，从而失去了前者的特异性。为此，我们逐个验证了原始代码提出的优化方案，在必要时对基础代码进行调整，并分析了其在两个不同测试场景下在两个Intel服务器上的性能。此外，提出了一种新的优化，以增加并行算法的并发度，并使用两种不同的同步机制进行了实现。实验结果表明，所有优化在选定的两个x86平台上都是有益的。最后，新的优化提案提高了最多23％的性能。

优化Floyd-Warshall算法在大型图中的计算效率和空间利用率

通过对原有Floyd-Warshall算法的优化和并行计算，提高算法的计算效率和空间利用率

通过对原有代码的优化，使得算法在x86平台上运行效率更高，同时提出了一种新的优化方案，通过并行计算提高算法的并发度，使得在两种不同的同步机制下，算法的性能都有所提升，最高提升了23%的性能。实验使用了两个不同的Intel服务器进行测试，论文提供了开源代码。

在Floyd-Warshall算法的优化和并行计算方面，已经有一些相关的研究。例如：Parallelization of the Floyd–Warshall Algorithm on a GPU Using CUDA；A Parallel Algorithm for the All-Pairs Shortest-Path Problem on the GPU。