多核平台并行单源最短路径算法

1 概述

单源最短路径(Single-source Shortest Path, SSSP)问题是被深入研究的基本网络分析算法，其目标是计算图中给定源结点与其他各结点间长度最短的路径，路径长度是路径上所有弧段权值之和。SSSP 在理论研究与实际应用中，都具有较重要意义。近年来，交通网络、互联网、物联网等大规模网络数据管理系统为人民生产生活提供便利，迅速增长的数据规模，也对网络分析算法效率提出新的需求。虽然高效的串行算法不断出现，如文献[1]提出的 ISODATA 算法，但由于处理器主频不能无限制提高，而数据规模不断增长，因此传统串行算法不再能够高效解决 SSSP 问题。随着多核处理器技术的发展，并行计算受到广泛关注，基于多核平台的并行SSSP 算法在解决大尺度网络分析问题中发挥着重要作用。

文献[2]提出需要 O(m+nlbn)工作量及 O(nlbn)时间算法。文献[3]提出需要 O(m+nlbn)工作量及 O(n)时间算法。这些算法都按照与 Dijkstra’s 算法相同的顺序依次获得各结点的最短路径，进行弧段松弛时使用并行堆排序，并行程度有限，其时间复杂度不可能小于Ω (n)。文献[4]提出的 Δ-Stepping 算法将 Dijkstra’s 算法计算过程分成若干阶段，每个阶段内弧段松弛并行执行。对于随机图，该算法仅需要 O(m+n)工作量和O(lb2n)时间，这是目前最高效并行 SSSP 算法。以上实验表明，对于度为 3 结点数为 219 的随机图，该算法在 16 个处理单元上得到 9.2 的加速比。

随着理论研究不断突破，实验研究也取得较大进展。并行算法的计算平台分为 2 类：多处理器(或多核处理器，CPU)，例如 Cray 公司的 MTA-2 包含 40 个处理器;图形处理单元(GPU)，例如 GTX 590 包含 1 024 个 CUDA 核心。文献[5]在MTA-2 上的并行 SSSP 算法获得接近 30 的加速比。文献[6]使用 GTX8800 GPU 在约 1.5 s 内计算出包含 1 000 万结点的SSSP。以上述内容为基础，本文提出基于多核平台的并行SSSP 算法。

2 本文算法原理

设图 G=(V, E)的结点数为 n 弧段数为 m，每个弧段 e∈E由函数 l：E→R 定义一个非负的实数权值，路径权值是路径上所有弧段权值之和。给定源结点 s∈V，单源最短路径问题被定义为求解源结点 s 到图中其他结点权值最小的路径 δ(v)。

大多数 SSSP 算法为每个结点记录一个实验权值 tent(v)，其初始值为∞，通过松弛弧段逐步减小 tent(v)，直至成为 δ(v)。根据松弛弧段策略不同，SSSP 算法分为 2 类，即标记设定(Label-setting)和标记较正(Label-correcting)。标记设定算法(如 Dijkstra’s 算法)只松弛已经确定最短路径(tent(v)=δ(v))和尚未确定最短路径(tent(v)≠δ(v))结点之间的弧段。使用该 算法解决单源最短路径问题最多需要 m 次弧段松弛。标记较正算法(如 Bellman-Ford 算法)除需要松弛与标记设定算法相同的弧段外，还需要松弛 2 个尚未确定最短路径结点之间的弧段。该算法解决单源最短路径问题最多需要 mn 次弧段松弛。由以上分析可知，最短路径算法不具有规则的结构，不容易从串行算法直接转化为高效的并行算法。

更多内容请查看pdf