MPI下單源點(diǎn)最短路徑的并行算法設(shè)計(jì)與分析

黎 源，王會(huì)進(jìn)

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州510632)

隨著高性能技術(shù)的發(fā)展，并行處理在解決人類(lèi)重大挑戰(zhàn)問(wèn)題方面發(fā)揮著越來(lái)越重要的作用。并行計(jì)算從傳統(tǒng)的超級(jí)計(jì)算機(jī)平臺(tái)，轉(zhuǎn)移到一組高性能節(jié)點(diǎn)或工作站/PC機(jī)構(gòu)成的稱(chēng)之為集群的計(jì)算平臺(tái)上，機(jī)群成為并行計(jì)算平臺(tái)的一個(gè)趨勢(shì)。并行程序設(shè)計(jì)是并行處理的核心技術(shù)。MPI(Message Passing Interface)即消息傳遞接口，是一個(gè)由眾多并行計(jì)算機(jī)廠商、軟件開(kāi)發(fā)單位/組織、并行應(yīng)用單位等共同維護(hù)的標(biāo)準(zhǔn)，是目前最流行的分布存儲(chǔ)并行編程環(huán)境。本文基于MPI進(jìn)行并行程序設(shè)計(jì)的研究工作。

1 研究背景

平面中帶權(quán)圖中的最短路徑問(wèn)題是計(jì)算機(jī)科學(xué)中一個(gè)被廣泛研究的對(duì)象，目前出現(xiàn)了大量并行求解最短路徑問(wèn)題的算法。Chandy和Misra提出了一種計(jì)算k個(gè)最短路徑問(wèn)題的并行算法，該計(jì)算將所有頂點(diǎn)到給定頂點(diǎn)的k個(gè)最短路徑之間的復(fù)雜度表示為O(m+nlog2n+nk)[1]。已知的最好的算法是Cohen[2]提出的運(yùn)行在EREW PRAM上的算法，該算法在空間復(fù)雜度為O(n3/2)時(shí)的時(shí)間復(fù)雜度為O((log2n)4)。Traff[3]等人基于前綴計(jì)算、列表分級(jí)、排序等方法實(shí)現(xiàn)了Dijkstra串行算法的并行版本。Adamson、Tick[4]和 Traff[5]使用一個(gè)分布的共享存儲(chǔ)器使標(biāo)簽設(shè)定算法并行化。由于同一時(shí)刻只是具有最短距離標(biāo)簽的節(jié)點(diǎn)才能從隊(duì)列中取出，因此實(shí)驗(yàn)中觀察到標(biāo)簽設(shè)定算法具有弱并行性。Traff通過(guò)允許處理器取出多于一個(gè)的節(jié)點(diǎn)來(lái)改善性能。Romeijn和Smith[6]通過(guò)在分布式網(wǎng)絡(luò)中求解近似最短路徑樹(shù)來(lái)嘗試減少標(biāo)簽設(shè)定算法的通信要求。Bertsekas等人[7]對(duì)幾個(gè)并行標(biāo)簽算法在有8個(gè)處理器的共享存儲(chǔ)機(jī)器上作了實(shí)驗(yàn)比較，結(jié)果發(fā)現(xiàn)有一些算法有超線性加速比，一些則沒(méi)有。Papaefthymiou和Rodrigue在CM-5上實(shí)現(xiàn)了Bellman-Ford-Moore算法，并比較了粗粒度劃分和細(xì)粒度劃分之間的差異。此外，其他衍生出來(lái)的算法，還有平衡二叉樹(shù)的標(biāo)簽設(shè)定算法、單隊(duì)列的標(biāo)簽修正算法、雙隊(duì)列的標(biāo)簽修正算法等。本文基于多進(jìn)程環(huán)境把Dijkstra串行算法轉(zhuǎn)化為并行算法，該算法采用按列分塊，適合于無(wú)向圖或有向圖的求解。

2 Dijkstra并行算法的設(shè)計(jì)

設(shè)圖G(V，E)是一個(gè)有向加權(quán)網(wǎng)絡(luò)，其中V是頂點(diǎn)的集合，E是邊集合。使用連接矩陣W來(lái)表示圖，邊上權(quán) 值 w[i][j]>0,i,j∈V，V={0，1，…，n-1}，dist(i)表 示 為最短路徑長(zhǎng)度。

2.1 數(shù)據(jù)劃分

為了使程序由各個(gè)處理器獨(dú)立地執(zhí)行，必須要找到可以并行性的操作。

常用的數(shù)據(jù)劃分方法有行劃分、列劃分和分塊劃分等。由于每次內(nèi)循環(huán)都要使用到某一定點(diǎn)到其他頂點(diǎn)的權(quán)值，而且當(dāng)圖G(V，E)是有向圖的時(shí)候，權(quán)值矩陣非對(duì)稱(chēng)，因此此算法不適宜使用行劃分。在此使用按列分解的方法。

分別為每個(gè)處理器分配若干的節(jié)點(diǎn)求得局部最小值，然后再將各個(gè)處理器求得的最小值進(jìn)行歸約，將歸約得出的最小值廣播到每個(gè)處理器中。

為了得到一種能夠負(fù)載平衡的數(shù)據(jù)分解方法，可以對(duì)每個(gè)進(jìn)程分配?n/p」或「n/p?個(gè)元素。這里使用的是按列分解方法，假設(shè)有節(jié)點(diǎn)數(shù)目是n，進(jìn)程數(shù)是p，進(jìn)程 i控制的第一列是?in/p」，進(jìn)程 i控制的最后一列是?(i+1)n/p」-1，對(duì)于特定的列 j，控制它的進(jìn)程是?(p(j+1)-1)/n」，任意兩個(gè)進(jìn)程控制的列數(shù)相差不會(huì)超過(guò)1。數(shù)據(jù)分割的結(jié)果如圖1所示。

按圖1所示的數(shù)據(jù)劃分，則分布在不同進(jìn)程i上的數(shù)據(jù)分別是 w(n，i×n/p：(i+1)×n/p-1)，其中 i×n/p：(i+1)×n/p-1代表取第 i×n/p列到第(i+1)×n/p-1列的數(shù)據(jù)。

2.2 Dijkstra并行算法實(shí)現(xiàn)

Dijkstra并行算法偽代碼可表示為：

(1)MPI_Init(&argc，&argv)；

(2)MPI_Comm_size(MPI_COMM_WORLD，&p)；

MPI_Comm_rank(MPI_COMM_WORLD，&my_rank)；

(3)0處理器讀入鄰接矩陣和起始點(diǎn)s，分發(fā)鄰接矩陣到各個(gè)處理器，廣播s。

(4)//初始化各個(gè)處理器的數(shù)據(jù)

(5)//每次循環(huán)分別求出到達(dá)一個(gè)結(jié)點(diǎn)的最小值

③/*通信域中的每一個(gè)進(jìn)程通過(guò)local結(jié)構(gòu)把它的（數(shù)值、下標(biāo)）對(duì)傳遞給MPI_Allreduce。當(dāng)函數(shù)返回時(shí)，最小值和相關(guān)的下標(biāo)存放在global結(jié)構(gòu)中。

④//更新源點(diǎn)s到每個(gè)頂點(diǎn)的距離

⑤//把頂點(diǎn) global.index對(duì)應(yīng)處理器的//bdist[i]值改為true

⑥MPI_Barrier(MPI_COMM_WORLD)；

(6)輸出各個(gè)處理器求出的dist[i]值。

(7)MPI_Finalize()；

3 算法分析

3.1 算法復(fù)雜度

串行版本的Dijkstra算法的時(shí)間復(fù)雜度為O(n2)。

初始化各個(gè)處理器數(shù)據(jù)的時(shí)間復(fù)雜度為 O(n/p)，在算法的內(nèi)循環(huán)①部分求出局部最小值以及相應(yīng)的索引，最多執(zhí)行「n/p?次，因此時(shí)間復(fù)雜度為 O(n/p)；③部分對(duì)一個(gè)長(zhǎng)度為1的數(shù)據(jù)進(jìn)行全歸約。由于歸約p個(gè)處理器需要「log2p?個(gè)消息傳遞步驟，總的時(shí)間復(fù)雜度為O(「log2p?)；④更新源點(diǎn)到其他頂點(diǎn)距離的時(shí)間復(fù)雜度為O(n/p)；⑤更新最小值對(duì)應(yīng)的bdist[i]需常數(shù)時(shí)間。

最外層執(zhí)行n-1次。

因此，并行算法的總的時(shí)間復(fù)雜度為：

即O(n2/p+nlog2p)

3.2 加速比和效率

設(shè)Ψ(n，p)表示為p個(gè)處理器上解決問(wèn)題規(guī)模為 n的問(wèn)題的加速比，ε(n，p)表示為在 p個(gè)處理器上解決規(guī)模為n的并行計(jì)算效率。作以下定義：

定義1：加速比=串行執(zhí)行時(shí)間/并行執(zhí)行時(shí)間。

定義2：效率=加速比/使用處理器數(shù)。根據(jù)定義得到：

隨著數(shù)據(jù)規(guī)模的增大，計(jì)算量增加速度比通信量開(kāi)銷(xiāo)增加更快，因此該系統(tǒng)隨著數(shù)據(jù)規(guī)模的增大可以取得更好的加速比和效率值。

3.3 等效指標(biāo)

在研究中發(fā)現(xiàn)并行算法可以分為以下3類(lèi)：

(1)必須串行執(zhí)行的計(jì)算，用 σ(n)表示；

(2)可以并行執(zhí)行的部分，用 φ(n)表示；

(3)并 行 開(kāi) 銷(xiāo)(通 信 操 作 和 冗 余 計(jì) 算)， 用 κ(n，p)表示。則得出一個(gè)加速比的完整的表達(dá)式為：

定義T0(n，p)代表所有進(jìn)程花費(fèi)在原有串行算法以外操作的全部時(shí)間。其組成是(p-1)個(gè)進(jìn)程花在進(jìn)程的內(nèi)在串行部分的時(shí)間，以及p個(gè)進(jìn)程花費(fèi)在處理器通信和冗余計(jì)算上的時(shí)間。 所以將 T0(n，p)=(p-1)σ(n)+pκ(n，p)代入上式，得到：

T(n，1)代表串行執(zhí)行時(shí)間，即：

如果效率不變，那么 ε(n，p)/(1-ε(n，p))是一個(gè)常數(shù)，上面公式可以化為：

由于在處理器個(gè)數(shù)增加時(shí)并行開(kāi)銷(xiāo)會(huì)增大，因此要保持效率就要增加問(wèn)題的規(guī)模。假定一個(gè)并行系統(tǒng)具有等加速比關(guān)系：n≥f(p)。如果M(n)表示規(guī)模為n的問(wèn)題所需的內(nèi)存大小，M-1(n)≥f(p)則表示為了保持效率不變所需的內(nèi)存與處理器個(gè)數(shù)p的函數(shù)關(guān)系。M(f(p))/p稱(chēng)為可擴(kuò)展函數(shù)，其復(fù)雜度確定了可保持常數(shù)效率的處理器個(gè)數(shù)范圍。

Dijkstra串行算法的時(shí)間復(fù)雜度是O(n2)。并行算法中全歸約的復(fù)雜度是O(nlog2p)，每個(gè)處理器都參與了此步驟，因此

T0(n，p)=O(nplog2p)，因此并行算法的等效關(guān)系為：

串行算法中問(wèn)題規(guī)模n所需的內(nèi)存容量為n2，即M(n)=n2，此系統(tǒng)的可擴(kuò)展性函數(shù)為：

即每個(gè)處理器的容量隨p增加。由于內(nèi)存容量的限制,處理器的個(gè)數(shù)不能一直增加，因此此系統(tǒng)處理器的個(gè)數(shù)應(yīng)在內(nèi)存允許的范圍之內(nèi)才能取得最好的效果。

本文在mpi環(huán)境下設(shè)計(jì)了求單源點(diǎn)最短路徑的Dijkstra并行算法，分析了該算法的時(shí)間復(fù)雜度、加速比、效率以及等效指標(biāo)。理論證明了利用多處理器共同計(jì)算的優(yōu)點(diǎn)，使若干臺(tái)計(jì)算機(jī)就能完成大型計(jì)算機(jī)所完成的計(jì)算功能，解決了單計(jì)算機(jī)內(nèi)存不足的問(wèn)題，降低了計(jì)算成本，提高了程序的效率。在實(shí)際應(yīng)用中，還要考慮到計(jì)算機(jī)之間的通信速度，這對(duì)計(jì)算性能的提高與否有重大影響。并行計(jì)算在未來(lái)的大規(guī)模計(jì)算中也會(huì)日益發(fā)揮重要的作用，如何提高并行性和進(jìn)一步減少通信開(kāi)銷(xiāo)是將來(lái)要改進(jìn)的工作。

[1]袁貞明，張量.GIS的前k個(gè)最短路徑分布式多線程實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2005，31(9)：37-38，162.

[2]COHEN E.Efficient parallel shortest-paths in digraphs with a separator decomposition[J].Algorithms，1996(21)：331-357.

[3]TRAFF J L，ZAROLIAGIS C D.A simple parallel algorithm for the single2source shortest path problem on planar digraphs[J].Journal of Parallel and Distributed Computing，2000，60(9)：1103.

[4]ADAMSON P，TICK E.Greedy partitionecd algorithms for the shortest path problem[J].International Journal of Parallel Programming，1991，20：271-298.

[5]TRAFF J L.An experimental comparison of two distributed single-source shortest path algorithmns[J].Parallel Computing，1995，21：1505-1532.

[6]ROMEIJN H E，SMITH R L.Parallel algorithms for solving aggregated shortest path problems[D].The University of Michigan，September 1993.

[7]BERTSEKAS D，GUERRIERO F，MUSMANNO R.Parallel asynchronous label-correcting methods for shortest paths[J].Journal of Optimization Theory and Applications，1996，88：297-320.