Dijkstra算法的并行實現

逄淑玲,王曉升

(山東女子學院 信息技術學院,山東 濟南 250300)

Dijkstra算法的并行實現

逄淑玲,王曉升

(山東女子學院 信息技術學院,山東 濟南 250300)

文章研究了一種多核架構下基于OpenMP的Dijkstra并行算法，以Dijkstra算法為基礎設計并行程序。對傳統Dijkstra算法進行分析，明確優化方向，再利用OpenMP開發工具對并行程序進行優化調試。結果表明，文中算法易于操作，并充分利用了多核處理器并行計算的優勢，提高了算法的運行效率，驗證了算法的優越性。

多核；Dijkstra算法；OpenMP；并行算法

0 引言

隨著多核的發展,串行執行程序的缺點暴露無遺，傳統的Dijkstra算法是串行算法，搜索過程易懂，程序設計簡單，但大量內存空間與計算時間的耗費成為此算法的瓶頸，而有效解決的途徑之一就是并行計算。為將計算能力最大化,需將一個應用程序劃分為多個相對獨立的任務并交由多個計算核執行。為從語言成分上直接支持并行，完全擺脫串行語言的束縛,設計了一種全新的程序設計模型，該并行算法與以往傳統算法相比能夠更有效地提高運行效率，充分發揮高性能多核處理器的功效。

1 OpenMP

OpenMP是一種支持跨平臺共享內存方式的多線程并發編程模型,開發過程中無需考慮數據分布，具有良好的可移植性、可擴展性，同時支持C、C++和FORTRAN語言。OpenMP提供一系列體系結構和編程平臺，建立簡潔高效的編程指導命令和并行編程方式，并提供各類串行程序并行化的可行方案[1]。OpenMP不是獨立的并行語言，通過在適當位置加入編譯指令和運行庫函數來并行化串行程序。OpenMP從主線程開始執行，一直串行地執行該線程，當線程某些點需要并行執行時，程序則派生出額外的線程，組成一個線程組,這些線程在并行域的代碼區中并行執行，線程到達整個并行區域的末尾時等待，直到整個線程組都到達，最終相連接，這時只有主線程繼續執行直到下一個并行區域或程序結束[2]。舉例說明[3]：

int main(int argc,char*argv[]){

#pragma omp parallel for

for(int i=0;i<10;i++)

{

printf(“i=%d/n”,i);

}

printf(“finished. ”);

return 0;

}

這段程序就是使用OpenMP編譯指導語句“#pragma omp parallel for”將for循環里的內容并行執行，從而提高效率。

2 Dijkstra最短路徑算法

2.1 算法思想

Dijkstra算法是典型的單源最短路徑，以起始點為中心向外層層擴展，直到拓展到終點為止。假設Len(v)表示一個頂點到給定頂點U的最短距離，w(u,v)表示兩個頂點間的距離。給出兩個頂點V1、V2，求兩頂點之間最短距離。算法描述如下[4]：

(1)給定頂點V1，標記這個頂點并初始化所有的頂點，將頂點V1放入集合S。

(2)對于集合S中的所有頂點Vi，計算Vi相鄰的所有頂點Uj的md(ui,vi)=w(ui,vj)+Len(vj)值并找出最小的md(u,v)值的頂點U，將頂點U放入集合S中。

(3)重復上述步驟，直到將目標頂點V2放入集合S中，即可求出頂點V1到V2間的最短距離，得到最短路徑[5]。

Dijkstra最短路徑算法流程圖如圖1所示[4]。

圖1 Dijkstra最短路徑算法流程圖

2.2 算法分析

通過對該算法的分析得出該算法的不足之處，在每次迭代中，未標記節點以無序的形式存放在一個數組或一個鏈表內，每次選擇最短路徑節點都必須把所有未標記節點掃描一遍，當節點數目較大時，這將成為制約計算速度的關鍵因素。

3 基于OpenMP的并行Dijkstra算法

3.1 算法的并行化思想

在編程時，代碼并行執行不僅限于某個函數的并行化，而是函數內部也需創建線程使關鍵計算并行執行。頻繁創建線程會使工作開銷額外增加[6]，借助OpenMP在有效的并行化程序的同時也可解決多核編程時線程創建問題。

(1)Dijkstra并行算法設計思想

從Dijkstra最短路徑算法可看出，集合S每次循環迭代之后定點個數都會加1，每次迭代都依賴于上次迭代的結果，循環之間存在依賴關系，所以外層循環不能直接并行化[7]，因此提出對內層循環并行化。每個線程計算一個頂點的所有邊，從中取得最小邊并保存在一個數組的不同位置，然后從數組中找出最小的值，得到最近距離的一個頂點[8]。繼續執行外層循環，直到找到最近距離頂點和目標節點為止。

(2)并行算法的程序設計流程圖[4]如圖2所示。

圖2 并行算法的程序設計流程圖

3.2 并行算法設計與實現

Dijkstra算法的并行化通過兩部分實現：Parallel_GetShort-estPath()函數實現主算法流程，SearchNextVertex()函數實現并行計算第M個最近頂點的算法流程[9]。并行算法的實現代碼如下[4]：

#pragma omp parallel for

num_thread(pgraph->nnodecount,MIN_ITERATOR_NUM))

for(i=0; inNodeCount; i++)

{

pGraph->ppNodeArray[i]->nMagic=-1;

/*初始化為-1，表示未計算過最短路徑的總距離*/

pGraph->ppNodeArray[i]->pMagic=NULL;

/*指針為空*/

}

ppSNode[0]=pSrcNode;

ppSNode[0]->nMagic=0;

/*初始化為0*/

ppSNode[0]->pMagic=NULL;

for(x=1; xnNodeCount; x++)

/*x從1開始循環執行*/

{

DISTANCE nTotalDis;

GRAPHNODE *pTNode;

pTNode=NULL;

NTotalDisGRAPH_MAX_DISTANCE;

SearchNextVertex(pGraph,ppSNode,x,ppNode,pnDis);

INT index=-1;

for(i=0;i

{

if(nTotalDis>pnDis[i])

{

nTotalDis=pnDis[i];

index=i;

}

}

if(index !=-1)

{

pTNode=ppNode[index*2];

pTNode->nMagic=nTotalDis;

pTNode->pMagic=ppNode[index *2+1];

if(pTNode==pTagNode)

{

nTagDis=nTotalDis;

/*計算出源節點到目標節點的最短路徑*/

Break;

}

}

else{ /*最短路徑總是存在的，此處應該不會被執行*/

break;

}

ppSNode[x]=pTNode;

}

free(ppNode);

free(pnDis);

free(ppSNode);

return nTagDis;

/*返回目標節點到源節點的最短路徑*/

}

4 實驗與結果分析

為驗證并行化后Dijkstra算法的性能，設計實驗進行驗證，分別采用傳統的Dijkstra算法與并行化的Dijkstra算法進行實驗，測試了不同節點數和弧段數下運行時間分析對比，評估出并行化后的性能[10]，結果如表1所示。

表1 算法性能統計表

從表1中可看出，在執行相同節點數與弧段數的情況下，并行Dijkstra算法比串行Dijkstra算法更加省時，大幅度提高了運行速度。

5 結論

本文對傳統Dijkstra算法進行分析，為節省計算機存儲空間，提高運行效率，在OpenMP模型下對Dijkstra算法的并行設計進行了研究，通過數據的采集與分析驗證并行化后Dijkstra算法的性能，結果表明：該并行算法與以往傳統算法相比能夠更有效地提高運行效率，充分發揮高性能多核處理器的功效。

[1] 王樹西,吳政學.改進的Dijkstra最短路徑算法及其應用研究[J].計算機科學,2012,39(5):223-228.

[2] 王智廣,王興會,李妍.一種基于Dijkstra最短路徑算法的改進算法[J].內蒙古師范大學學報(自然科學漢文版),2012,41(2):195-200.

[3] 彭曦,顧炳根,李展濤.基于多核的OpenMP并行程序設計[J].硅谷,2010,(16):97-98.

[4] 周偉明.多核計算與程序設計[M].武漢：華中科技大學出版社，2009.

[5] 龔向堅,鄒臘梅,胡義香.基于OpenMP的多核系統并行程序設計方法研究[J].南華大學學報(自然科學版),2013,27(1):64-68.

[6] 葉仕灝,王伊蕾.一種優化Dijkstra算法的研究[J].計算機應用與軟件,2011,28(9):272-274.

[7] 李健.基于Dijkstra最短路徑算法的優化研究[J].渭南師范學院學報,2009,24(5):61-64.

[8] 計會鳳,徐愛功,隋達嵬.Dijkstra算法的設計與實現[J].遼寧工程技術大學學報(自然科學版),2008,27(S1):222-223.

[9] 任小西,唐玲,張杰. 基于OpenMP多線程動態負載均衡技術研究[J]. 世界科技研究與發展,2008,30(3):281-285.

[10] 董俊,黃傳河. 改進Dijkstra算法在GIS導航應用中最短路徑搜索研究[J]. 計算機科學,2012,39(10):245-247，257.

Parallel inplementation of Dijkstra algorithm

Pang Shuling, Wang Xiaosheng

(School of Information Technology, Shandong Women’s University, Jinan 250300, China)

In this paper, a Dijkstra parallel algorithm based on OpenMP is designed, and a parallel program is designed based on Dijkstra algorithm. The traditional Dijkstra algorithm is analyzed, the direction of optimization is clarified, and the parallel program is optimized and debugged by OpenMP. The results show that the proposed algorithm is easy to operate and takes full advantage of the parallel computing of multi-core processors, and improves the running efficiency of the algorithm and verifies the superiority of the algorithm.

multi-core;Dijkstra algorithm;OpenMP; parallel algorithm

TP312

A

10.19358/j.issn.1674- 7720.2017.09.008

逄淑玲,王曉升.Dijkstra算法的并行實現[J].微型機與應用，2017,36(9)：25-27.

2016-12-01)

逄淑玲(1994-)，女，本科生，主要研究方向：計算機科學與技術。

王曉升(1963-)，男，碩士，教授，主要研究方向：智能信息處理、并行計算。