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