基于神威平台的Floyd并行算法的实现和优化

摘要：

求解全源最短路径的Floyd算法是许多实际应用基础上的关键构建块,由于其时间复杂度较高,串行Floyd算法不适用于大规模输入图计算,针对不同平台的并行Floyd算法设计可为解决现实问题提供有效帮助.针对Floyd算法与国产自主研发处理器匹配滞后的问题,首次提出基于神威平台的Floyd并行算法的实现和优化.根据SW26010处理器主-从核架构的特点,采用主从加速编程模型进行并行实现,并分析了影响该算法性能的关键因素,通过算法优化、数组划分和双缓冲技术进行优化,逐步提升算法性能.测试结果表明,与主核上串行算法相比,基于神威平台的Floyd并行算法在单个SW26010处理器上可以获得106倍的最高加速.

关键词：SW26010、Floyd算法、并行计算、数组划分

所属期刊栏目：48

分类号：TP391(计算技术、计算机技术)

资助基金：之江实验室重大科研基金资助项目2018FD0ZX01

在线出版日期：2021-06-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：34-40