逄淑玲,王曉升

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

Dijkstra算法的并行實現(xiàn)

逄淑玲,王曉升

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

文章研究了一種多核架構(gòu)下基于OpenMP的Dijkstra并行算法，以Dijkstra算法為基礎(chǔ)設(shè)計并行程序。對傳統(tǒng)Dijkstra算法進行分析，明確優(yōu)化方向，再利用OpenMP開發(fā)工具對并行程序進行優(yōu)化調(diào)試。結(jié)果表明，文中算法易于操作，并充分利用了多核處理器并行計算的優(yōu)勢，提高了算法的運行效率，驗證了算法的優(yōu)越性。

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

0 引言

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

1 OpenMP

OpenMP是一種支持跨平臺共享內(nèi)存方式的多線程并發(fā)編程模型,開發(fā)過程中無需考慮數(shù)據(jù)分布，具有良好的可移植性、可擴展性，同時支持C、C++和FORTRAN語言。OpenMP提供一系列體系結(jié)構(gòu)和編程平臺，建立簡潔高效的編程指導(dǎo)命令和并行編程方式，并提供各類串行程序并行化的可行方案[1]。OpenMP不是獨立的并行語言，通過在適當(dāng)位置加入編譯指令和運行庫函數(shù)來并行化串行程序。OpenMP從主線程開始執(zhí)行，一直串行地執(zhí)行該線程，當(dāng)線程某些點需要并行執(zhí)行時，程序則派生出額外的線程，組成一個線程組,這些線程在并行域的代碼區(qū)中并行執(zhí)行，線程到達整個并行區(qū)域的末尾時等待，直到整個線程組都到達，最終相連接，這時只有主線程繼續(xù)執(zhí)行直到下一個并行區(qū)域或程序結(jié)束[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編譯指導(dǎo)語句“#pragma omp parallel for”將for循環(huán)里的內(nèi)容并行執(zhí)行，從而提高效率。

2 Dijkstra最短路徑算法

2.1 算法思想

Dijkstra算法是典型的單源最短路徑，以起始點為中心向外層層擴展，直到拓展到終點為止。假設(shè)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)重復(fù)上述步驟，直到將目標頂點V2放入集合S中，即可求出頂點V1到V2間的最短距離，得到最短路徑[5]。

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

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

2.2 算法分析

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

3 基于OpenMP的并行Dijkstra算法

3.1 算法的并行化思想

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

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

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

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

圖2 并行算法的程序設(shè)計流程圖

3.2 并行算法設(shè)計與實現(xiàn)

Dijkstra算法的并行化通過兩部分實現(xiàn)：Parallel_GetShort-estPath()函數(shù)實現(xiàn)主算法流程，SearchNextVertex()函數(shù)實現(xiàn)并行計算第M個最近頂點的算法流程[9]。并行算法的實現(xiàn)代碼如下[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開始循環(huán)執(zhí)行*/

{

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;

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

Break;

}

}

else{ /*最短路徑總是存在的，此處應(yīng)該不會被執(zhí)行*/

break;

}

ppSNode[x]=pTNode;

}

free(ppNode);

free(pnDis);

free(ppSNode);

return nTagDis;

/*返回目標節(jié)點到源節(jié)點的最短路徑*/

}

4 實驗與結(jié)果分析

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

表1 算法性能統(tǒng)計表

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

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

[10] 董俊,黃傳河. 改進Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究[J]. 計算機科學(xué),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算法的并行實現(xiàn)[J].微型機與應(yīng)用，2017,36(9)：25-27.

2016-12-01)

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

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