多核平臺(tái)并行單源最短路徑算法

1 概述

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

文獻(xiàn)[2]提出需要 O(m+nlbn)工作量及 O(nlbn)時(shí)間算法。文獻(xiàn)[3]提出需要 O(m+nlbn)工作量及 O(n)時(shí)間算法。這些算法都按照與 Dijkstra’s 算法相同的順序依次獲得各結(jié)點(diǎn)的最短路徑，進(jìn)行弧段松弛時(shí)使用并行堆排序，并行程度有限，其時(shí)間復(fù)雜度不可能小于Ω (n)。文獻(xiàn)[4]提出的 Δ-Stepping 算法將 Dijkstra’s 算法計(jì)算過(guò)程分成若干階段，每個(gè)階段內(nèi)弧段松弛并行執(zhí)行。對(duì)于隨機(jī)圖，該算法僅需要 O(m+n)工作量和O(lb2n)時(shí)間，這是目前最高效并行 SSSP 算法。以上實(shí)驗(yàn)表明，對(duì)于度為 3 結(jié)點(diǎn)數(shù)為 219 的隨機(jī)圖，該算法在 16 個(gè)處理單元上得到 9.2 的加速比。

隨著理論研究不斷突破，實(shí)驗(yàn)研究也取得較大進(jìn)展。并行算法的計(jì)算平臺(tái)分為 2 類：多處理器(或多核處理器，CPU)，例如 Cray 公司的 MTA-2 包含 40 個(gè)處理器;圖形處理單元(GPU)，例如 GTX 590 包含 1 024 個(gè) CUDA 核心。文獻(xiàn)[5]在MTA-2 上的并行 SSSP 算法獲得接近 30 的加速比。文獻(xiàn)[6]使用 GTX8800 GPU 在約 1.5 s 內(nèi)計(jì)算出包含 1 000 萬(wàn)結(jié)點(diǎn)的SSSP。以上述內(nèi)容為基礎(chǔ)，本文提出基于多核平臺(tái)的并行SSSP 算法。

2 本文算法原理

設(shè)圖 G=(V, E)的結(jié)點(diǎn)數(shù)為 n 弧段數(shù)為 m，每個(gè)弧段 e∈E由函數(shù) l：E→R 定義一個(gè)非負(fù)的實(shí)數(shù)權(quán)值，路徑權(quán)值是路徑上所有弧段權(quán)值之和。給定源結(jié)點(diǎn) s∈V，單源最短路徑問(wèn)題被定義為求解源結(jié)點(diǎn) s 到圖中其他結(jié)點(diǎn)權(quán)值最小的路徑 δ(v)。

大多數(shù) SSSP 算法為每個(gè)結(jié)點(diǎn)記錄一個(gè)實(shí)驗(yàn)權(quán)值 tent(v)，其初始值為∞，通過(guò)松弛弧段逐步減小 tent(v)，直至成為 δ(v)。根據(jù)松弛弧段策略不同，SSSP 算法分為 2 類，即標(biāo)記設(shè)定(Label-setting)和標(biāo)記較正(Label-correcting)。標(biāo)記設(shè)定算法(如 Dijkstra’s 算法)只松弛已經(jīng)確定最短路徑(tent(v)=δ(v))和尚未確定最短路徑(tent(v)≠δ(v))結(jié)點(diǎn)之間的弧段。使用該 算法解決單源最短路徑問(wèn)題最多需要 m 次弧段松弛。標(biāo)記較正算法(如 Bellman-Ford 算法)除需要松弛與標(biāo)記設(shè)定算法相同的弧段外，還需要松弛 2 個(gè)尚未確定最短路徑結(jié)點(diǎn)之間的弧段。該算法解決單源最短路徑問(wèn)題最多需要 mn 次弧段松弛。由以上分析可知，最短路徑算法不具有規(guī)則的結(jié)構(gòu)，不容易從串行算法直接轉(zhuǎn)化為高效的并行算法。

更多內(nèi)容請(qǐng)查看pdf