逄淑玲,王曉升
（山東女子學院 信息技術學院,山東 濟南 250300）
摘要：文章研究了一種多核架構下基于OpenMP的Dijkstra并行算法,，以Dijkstra算法為基礎設計并行程序,。對傳統(tǒng)Dijkstra算法進行分析，明確優(yōu)化方向,，再利用OpenMP開發(fā)工具對并行程序進行優(yōu)化調試,。結果表明，文中算法易于操作,，并充分利用了多核處理器并行計算的優(yōu)勢,，提高了算法的運行效率，驗證了算法的優(yōu)越性。
關鍵詞：多核,；Dijkstra算法,；OpenMP；并行算法
中圖分類號：TP312文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.09.008
引用格式：逄淑玲,王曉升.Dijkstra算法的并行實現(xiàn)［J］.微型機與應用,，2017,36（9）：25-27.
0引言
隨著多核的發(fā)展,串行執(zhí)行程序的缺點暴露無遺,，傳統(tǒng)的Dijkstra算法是串行算法，搜索過程易懂,，程序設計簡單,，但大量內存空間與計算時間的耗費成為此算法的瓶頸，而有效解決的途徑之一就是并行計算,。為將計算能力最大化,需將一個應用程序劃分為多個相對獨立的任務并交由多個計算核執(zhí)行,。為從語言成分上直接支持并行，完全擺脫串行語言的束縛,設計了一種全新的程序設計模型,，該并行算法與以往傳統(tǒng)算法相比能夠更有效地提高運行效率,，充分發(fā)揮高性能多核處理器的功效。
1OpenMP
OpenMP是一種支持跨平臺共享內存方式的多線程并發(fā)編程模型,開發(fā)過程中無需考慮數(shù)據(jù)分布,，具有良好的可移植性,、可擴展性，同時支持C,、C++和FORTRAN語言,。OpenMP提供一系列體系結構和編程平臺，建立簡潔高效的編程指導命令和并行編程方式,，并提供各類串行程序并行化的可行方案［1］,。OpenMP不是獨立的并行語言，通過在適當位置加入編譯指令和運行庫函數(shù)來并行化串行程序,。OpenMP從主線程開始執(zhí)行,，一直串行地執(zhí)行該線程，當線程某些點需要并行執(zhí)行時,，程序則派生出額外的線程,，組成一個線程組,這些線程在并行域的代碼區(qū)中并行執(zhí)行，線程到達整個并行區(qū)域的末尾時等待,，直到整個線程組都到達,，最終相連接，這時只有主線程繼續(xù)執(zhí)行直到下一個并行區(qū)域或程序結束［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.\\n”);
return 0;
}
這段程序就是使用OpenMP編譯指導語句“#pragma omp parallel for”將for循環(huán)里的內容并行執(zhí)行,，從而提高效率。
2Dijkstra最短路徑算法
2.1算法思想
Dijkstra算法是典型的單源最短路徑,，以起始點為中心向外層層擴展,，直到拓展到終點為止,。假設Len（v）表示一個頂點到給定頂點U的最短距離，w(u,v)表示兩個頂點間的距離,。給出兩個頂點V1,、V2，求兩頂點之間最短距離,。算法描述如下［4］：
?。?）給定頂點V1，標記這個頂點并初始化所有的頂點,，將頂點V1放入集合S,。
（2）對于集合S中的所有頂點Vi,，計算Vi相鄰的所有頂點Uj的md(ui,vi)=w(ui,vj)+Len（vj）值并找出最小的md(u,v)值的頂點U,，將頂點U放入集合S中。
?。?）重復上述步驟,，直到將目標頂點V2放入集合S中，即可求出頂點V1到V2間的最短距離,，得到最短路徑［5］,。
Dijkstra最短路徑算法流程圖如圖1所示［4］。
2.2算法分析
通過對該算法的分析得出該算法的不足之處,，在每次迭代中,，未標記節(jié)點以無序的形式存放在一個數(shù)組或一個鏈表內，每次選擇最短路徑節(jié)點都必須把所有未標記節(jié)點掃描一遍,，當節(jié)點數(shù)目較大時,，這將成為制約計算速度的關鍵因素。
3基于OpenMP的并行Dijkstra算法
3.1算法的并行化思想
在編程時,，代碼并行執(zhí)行不僅限于某個函數(shù)的并行化,，而是函數(shù)內部也需創(chuàng)建線程使關鍵計算并行執(zhí)行。頻繁創(chuàng)建線程會使工作開銷額外增加［6］,，借助OpenMP在有效的并行化程序的同時也可解決多核編程時線程創(chuàng)建問題,。
(1)Dijkstra并行算法設計思想
從Dijkstra最短路徑算法可看出，集合S每次循環(huán)迭代之后定點個數(shù)都會加1,，每次迭代都依賴于上次迭代的結果,，循環(huán)之間存在依賴關系，所以外層循環(huán)不能直接并行化［7］,，因此提出對內層循環(huán)并行化。每個線程計算一個頂點的所有邊,，從中取得最小邊并保存在一個數(shù)組的不同位置,，然后從數(shù)組中找出最小的值,，得到最近距離的一個頂點［8］。繼續(xù)執(zhí)行外層循環(huán),，直到找到最近距離頂點和目標節(jié)點為止,。
(2)并行算法的程序設計流程圖［4］如圖2所示。
3.2并行算法設計與實現(xiàn)
Dijkstra算法的并行化通過兩部分實現(xiàn)：Parallel_GetShortestPath()函數(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; i<pGraph>nNodeCount; 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; x<pGraph>nNodeCount; 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<x;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{ /*最短路徑總是存在的,，此處應該不會被執(zhí)行*/
break;
}
ppSNode［x］=pTNode;
}
free(ppNode);
free(pnDis);
free(ppSNode);
return nTagDis; /*返回目標節(jié)點到源節(jié)點的最短路徑*/
}
4實驗與結果分析
為驗證并行化后Dijkstra算法的性能,，設計實驗進行驗證，分別采用傳統(tǒng)的Dijkstra算法與并行化的Dijkstra算法進行實驗,，測試了不同節(jié)點數(shù)和弧段數(shù)下運行時間分析對比,，評估出并行化后的性能［10］，結果如表1所示,。
從表1中可看出,，在執(zhí)行相同節(jié)點數(shù)與弧段數(shù)的情況下，并行Dijkstra算法比串行Dijkstra算法更加省時,，大幅度提高了運行速度,。
5結論
本文對傳統(tǒng)Dijkstra算法進行分析，為節(jié)省計算機存儲空間,，提高運行效率,，在OpenMP模型下對Dijkstra算法的并行設計進行了研究，通過數(shù)據(jù)的采集與分析驗證并行化后Dijkstra算法的性能,，結果表明：該并行算法與以往傳統(tǒng)算法相比能夠更有效地提高運行效率,，充分發(fā)揮高性能多核處理器的功效。
參考文獻
?。?］ 王樹西,吳政學.改進的Dijkstra最短路徑算法及其應用研究［J］.計算機科學,2012,39(5):223-228.
?。?］ 王智廣,王興會,李妍.一種基于Dijkstra最短路徑算法的改進算法［J］.內蒙古師范大學學報(自然科學漢文版),2012,41(2):195-200.
［3］ 彭曦,顧炳根,李展?jié)?基于多核的OpenMP并行程序設計［J］.硅谷,2010,(16):97-98.
?。?］ 周偉明.多核計算與程序設計［M］.武漢：華中科技大學出版社,，2009.
［5］ 龔向堅,鄒臘梅,胡義香.基于OpenMP的多核系統(tǒng)并行程序設計方法研究［J］.南華大學學報(自然科學版),2013,27(1):64-68.
?。?］ 葉仕灝,王伊蕾.一種優(yōu)化Dijkstra算法的研究［J］.計算機應用與軟件,2011,28(9):272274.
?。?］ 李健.基于Dijkstra最短路徑算法的優(yōu)化研究［J］.渭南師范學院學報,2009,24(5):6164.
［8］ 計會鳳,徐愛功,隋達嵬.Dijkstra算法的設計與實現(xiàn)［J］.遼寧工程技術大學學報(自然科學版),2008,27(S1):222-223.
?。?］ 任小西,唐玲,張杰. 基于OpenMP多線程動態(tài)負載均衡技術研究［J］. 世界科技研究與發(fā)展,2008,30(3):281-285.
?。?0］ 董俊,黃傳河. 改進Dijkstra算法在GIS導航應用中最短路徑搜索研究［J］. 計算機科學,2012,39(10):245-247，257.