基于OpenMP的Floyd并行算法研究  

A Floyd Parallel Algorithm Based on OpenMP

作　　者：彭瑾 杨勇 PENG Jin;YANG Yong(School of Electronic Information Engineering,Anhui Water Conservancy Technical College,Hefei Anhui 231603,China;Research and Development Centre,Anhui USTSUN Technology CO.LTD.,Hefei Anhui 230008,China)

机构地区：[1]安徽水利水电职业技术学院电子信息工程学院,安徽合肥231603 [2]安徽科大擎天科技有限公司研发中心,安徽合肥230008

出　　处：《鞍山师范学院学报》2023年第4期49-54,共6页Journal of Anshan Normal University

基　　金：2021年度安徽省职业与成人教育学会课题(AZCJ2021136);2022年度安徽省高校科学研究项目(2022AH052295).

摘　　要：Floyd算法是求解两点之间最短路径的算法之一,但因其时间复杂度较高,在面对大规模的图数据求解最短路径时效率并不高.通过使用OpenMP编程模型对Floyd算法进行并行优化,使其在求解最短路径时可以充分利用多核CPU资源,发挥多核性能,降低时间代价.与依赖于特定硬件的算法相比,基于OpenMP的Floyd并行算法具有更高的通用性和可移植性,可以在各种通用计算平台上实现,包括普通的多核CPU和共享内存系统.相较依赖于特定平台的算法,基于OpenMP实现的Floyd并行算法更具有普适性,可以让更多的研究人员和开发者受益.实验结果表明,并行优化后的Floyd算法在执行效率上得到了显著提升.Floyd algorithm is one of the algorithms for the shortest paths between two points.However,since the time complexity of Floyd algorithm is relatively high,its efficiency is not high when solving the shortest path in the face of large-scale graph data.In this article,the Floyd algorithm is optimized by using OpenMP to make full use of multi-core CPU to play the performance of CPU so as to reduce the running time.Compared to hard-ware-specific algorithms,the OpenMP-based Floyd parallel algorithm offers higher versatility and portability.It can be implemented on various general-purpose computing platforms,including regular multi-core CPUs and shared memory systems.In contrast to platform-specific algorithms,the OpenMP-based implementation demon-strates greater universality,benefiting a wider range of researchers and developers.The experiment result shows the efficiency of parallel optimization Floyd algorithm is obviously improved.

关 键 词：多核 多线程 Floyd并行算法 OPENMP 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]