多核平臺并行單源最短路徑算法

1 概述

單源最短路徑(Single-source Shortest Path, SSSP)問題是被深入研究的基本網絡分析算法，其目標是計算圖中給定源結點與其他各結點間長度最短的路徑，路徑長度是路徑上所有弧段權值之和。SSSP 在理論研究與實際應用中，都具有較重要意義。近年來，交通網絡、互聯網、物聯網等大規(guī)模網絡數據管理系統為人民生產生活提供便利，迅速增長的數據規(guī)模，也對網絡分析算法效率提出新的需求。雖然高效的串行算法不斷出現，如文獻[1]提出的 ISODATA 算法，但由于處理器主頻不能無限制提高，而數據規(guī)模不斷增長，因此傳統串行算法不再能夠高效解決 SSSP 問題。隨著多核處理器技術的發(fā)展，并行計算受到廣泛關注，基于多核平臺的并行SSSP 算法在解決大尺度網絡分析問題中發(fā)揮著重要作用。

文獻[2]提出需要 O(m+nlbn)工作量及 O(nlbn)時間算法。文獻[3]提出需要 O(m+nlbn)工作量及 O(n)時間算法。這些算法都按照與 Dijkstra’s 算法相同的順序依次獲得各結點的最短路徑，進行弧段松弛時使用并行堆排序，并行程度有限，其時間復雜度不可能小于Ω (n)。文獻[4]提出的 Δ-Stepping 算法將 Dijkstra’s 算法計算過程分成若干階段，每個階段內弧段松弛并行執(zhí)行。對于隨機圖，該算法僅需要 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 次弧段松弛。由以上分析可知，最短路徑算法不具有規(guī)則的結構，不容易從串行算法直接轉化為高效的并行算法。

更多內容請查看pdf