基于GPU的并行APSP问题的研究

张凌洁，赵 英

（北京化工大学 北京 100029）

最短路径问题是图论中的一个典型问题，已经得到广泛的研究和应用。此问题包含两类：1）单源最短路径（SSSP，Single Source Shortest Paths），求给定始末顶点之间的最短路径，如旅行商问题；2）所有顶点间最短路径（APSP，All Pair Shortest Paths），求图中所有顶点对之间的全部最短路径。

目前针对此问题的相关研究成果已被广泛应用于众多领域，如城市物流规划、图形学图像分割等。由此可见最短路径问题不仅具有较高的科研意义，还具有相当高的实际应用价值。

另一方面，当今社会已步入信息化时代。海量数据以及复杂的科学计算都对计算机处理能力提出了更高的要求。HPC已经成为热点研究问题。其中GPU作为低成本低功耗的新型高性能技术得到广泛关注和长足的发展。尤其是在CUDA平台出现后，打破了图形处理编程与普通编程之间的壁垒，对于GPU的发展可谓是如虎添翼，使得更多的程序员跨入到GPU通用计算的研究当中[1-2]。

在GPU成为研究热点的背景下，利用其高性能和低成本的优势，通过对APSP最短路径并行算法的研究，解决Floyd算法在GPU并行化中产生的问题。并根据GPU特点，提出相应改进策略，从而进一步加快计算速度。希望将来可以把研究成果运用到如物流配送中心的选址，城市规划等实践中。

1 Floyd-W arshall算法简介

APSP问题就是求解给定图中所有顶点对之间的全部最短路径。此问题有两种解法：

第1种解法是，每次以一个顶点作为起始顶点，依次将其他顶点作为终止顶点求它们之间的最短路径，然后更换起始顶点，依次再求其他顶点间的最短路径。……