單源最短路徑問題并行算法分析

單源最短路徑問題并行算法分析實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)名稱單源最短路徑問題并行算法分析。二、實(shí)驗(yàn)?zāi)康姆治鰡卧醋疃搪窂紻ijkstra并行算法和MPI源程序，并分析比較Dijkstra并行算法和Moore并行算法的性能。三、實(shí)驗(yàn)內(nèi)容1、分析單源最短路徑Dijkstra并行算法和MPI源程序。2、分析單源最短路徑問題的Moore并行算法，比較兩種并行算法的性能。四、實(shí)驗(yàn)步驟1、問題描述單源最短路徑問題即指：已知一個(gè)n結(jié)點(diǎn)有向圖G=(V,E)和邊的權(quán)函數(shù)c(e)，求由G中某指定結(jié)點(diǎn)v0到其他各個(gè)結(jié)點(diǎn)的最短路徑。這里還假定所有的權(quán)值都是正的。2、比較串行Dijkstra算法和Moore算法2.1、Dijkstra算法基本思想假定有一個(gè)待搜索頂點(diǎn)表VL，初始化時(shí)做：dist(s)-0；dist(i)—8(i^s)；VL—V。算法執(zhí)行時(shí)，每次從VL(26)中選取這樣一個(gè)頂點(diǎn)u，它的dist(u)值最小。將選出的u作為搜索頂點(diǎn)，若<u，v>EE，而且dist(u)+w(u,v)<dist(v)，則更新dist(v)為dist(u)+w(u,v)，直到VL=0時(shí)算法終止。算法描述如下：輸入：加權(quán)鄰接矩陣W，約定i，j之間無邊連接時(shí)w(i,j)=8,且w(i,i)=8；輸出：dist(1:n)，其中，dist(i)表示頂點(diǎn)s到頂點(diǎn)i的最短路徑(1^i^n)obegin/*初始化*/dist(s)—0；fori—1tondoifi#sthendist(i)—8endifendfor；VL—V；fori—1tondo/*找最短距離*/findavertexuEVL,suchthatdist(u)isminimal；foreach(<u，v>EE)A(vEVL)doifdist(u)+w(u,v)<dist(v)thendist(v)—dist(u)+w(u,v)endifendfor；VL—VL-{u}endforend.2.2、Moore算法的基本思想設(shè)源點(diǎn)為sEV,從s到其它各頂點(diǎn)的最短路徑長度用一個(gè)一維數(shù)組dist存儲(chǔ)。首先置dist(s)=0,dist(v)—8,v#s,vEV。Moore算法同Dijkstra算法不同之處是：將Dijkstra算法中的待搜索頂點(diǎn)表替換成待搜索隊(duì)列。算法開始執(zhí)行時(shí)，隊(duì)列僅含源點(diǎn)s。以后每次只要待搜索隊(duì)列非空，則將隊(duì)頭的頂點(diǎn)從隊(duì)列中移出作為本次搜索的頂點(diǎn)，然后檢查u的所有射出邊<u,v>EE。若dist(u)+w(u,v)<dist(v),則此時(shí)找出了一條從s到v的更短路徑，置dist(v)等于dist(u)+w(u,v)。若v不在搜索隊(duì)列中，則把v加入到隊(duì)列的隊(duì)尾。如此重復(fù)進(jìn)行，直到整個(gè)待搜索隊(duì)列空時(shí)，算法終止。單處理器上的Moore算法如下：輸入：有向圖G(V,E)的加權(quán)鄰接矩陣W={w},i,jEV；輸出：從源s到所有其它頂點(diǎn)i(i^s)的最短路徑dist(i)，iEV。beginfori—1tondo/*初始化*/callINITIALIZE(i)endfor;insertsintothequeue;/*插入s到隊(duì)列中*/whilethequeueisnotemptydocallSEARCHendwhileend.ProcedureSEARCH;begindequeuevertexu;/*從隊(duì)列中刪去頂點(diǎn)u*/foreachedge(u,v)EEdo(i)new_dist—dist(u)+w(u,v);(ii)ifnew_dist<dist(v)thendist(v)—new_distendif;(iii)ifvisnotinthequeuethenenqueuevertexvendifendforend.ProcedureINITIALIZEbegindist(s)—0dist(v)—8(v#s,veV)queue—0end2.3、兩種算法的性能比較Dijkstra算法是由E.W.Dijkstra于1959年提出的一個(gè)適用于所有弧度權(quán)均為非負(fù)的最短路徑算法，也是目前公認(rèn)的高效經(jīng)典算法之一。其時(shí)間復(fù)雜度為O(n2)，其中n為結(jié)點(diǎn)個(gè)數(shù)。Moore算法分別由Bellman,Ford和Moore在五、六十年代提出。其時(shí)間復(fù)雜度是O(nm)，期中m是邊/弧數(shù)。目前這樣的時(shí)間復(fù)雜度在所有帶有負(fù)權(quán)弧頂最短路徑算法中是最好的。但其實(shí)際運(yùn)算效果卻往往不及Dijkstra算法。3、串行算法并行化3.1、Dijkstra并行算法每個(gè)處理器分配n=N/p各節(jié)點(diǎn)進(jìn)行初始化(N為節(jié)點(diǎn)數(shù)，p為處理器個(gè)數(shù))。首先每個(gè)處理器分配n個(gè)節(jié)點(diǎn)分別求局部最小值，然后再p個(gè)處理器和作求全局最小值，最后再將這一最小值廣播出去。P個(gè)處理器合作方法：當(dāng)p為偶數(shù)時(shí)，后p/2個(gè)處理器將自己的局部最小值分別發(fā)送到對(duì)應(yīng)的前p/2個(gè)處理器中，由前p/2個(gè)處理器比較出2個(gè)局部最小值中相對(duì)較小者并保留。當(dāng)p為奇數(shù)時(shí)，設(shè)p=2h+1,則后h個(gè)處理器的值分別發(fā)送到前h個(gè)處理器中，比較并保留最小值。一次這樣的循環(huán)過程后，p個(gè)最小值減少了一半，兩次后，變?yōu)?/4,如此一層一層的比較，logp次循環(huán)后，就可以得出唯一的全局最小值，然后將其廣播出去。每個(gè)處理器分配n個(gè)頂點(diǎn)，然后獨(dú)立進(jìn)行更新dist的操作。其中廣播實(shí)現(xiàn)步驟如下：輸入：數(shù)據(jù)u(存放在單元B(1)中)；輸出：將u廣播到數(shù)組B的所有單元中去。BeginB(1)-u；fori—0to「logp】-1doforeachj:2i+1^j^2i+1pardoB(j)—B(j-2j)endforendforEnd.3.2、Moore并行算法首先，隊(duì)列用源點(diǎn)初始化。然后創(chuàng)建了許多異步進(jìn)程，每個(gè)進(jìn)程都從隊(duì)列中刪除一個(gè)頂點(diǎn)，檢查其射出邊，將已發(fā)現(xiàn)有更短路徑的頂點(diǎn)加入到隊(duì)列。算法的第(1)步采用預(yù)調(diào)(Prescheduling)方法很容易并行化。而第(3)步的while循環(huán)需作適當(dāng)?shù)男薷模瑸榇艘雰蓚€(gè)用于同步的變量：數(shù)組變量waiting，它記住哪一個(gè)進(jìn)程正處于等待狀態(tài)；布爾變量halt，僅當(dāng)隊(duì)列為空和所有進(jìn)程處于等待狀態(tài)時(shí)為真。INITIALIZE過程置數(shù)組waiting中的第一個(gè)元素為假。SEARCH過程亦必須作適當(dāng)?shù)男薷?。因?yàn)閷?duì)隊(duì)列的插入、刪除操作不是原子操作，所以執(zhí)行上述操作時(shí)必須給隊(duì)列上鎖；其次，在一個(gè)進(jìn)程將剛找到的v路徑new_dist與當(dāng)前的最短路徑dist(v)比較之前，變量dist(v)也必須上鎖，否則兩個(gè)進(jìn)程有可能同時(shí)修改它；最后，若一個(gè)進(jìn)程發(fā)現(xiàn)隊(duì)列為空時(shí)，則置waiting中的相應(yīng)元素為真。若第一個(gè)進(jìn)程處于等待狀態(tài)，則它要檢查每個(gè)進(jìn)程是否都處在等待狀態(tài)，如果是，則halt置為真，而在第一個(gè)進(jìn)程檢查每個(gè)進(jìn)程是否都處于等待狀態(tài)時(shí)，隊(duì)列亦必須上鎖。算法描述：MIMD緊耦合多處理機(jī)上的單源最短路徑算法輸入：有向加權(quán)圖G的權(quán)矩陣W；輸出：從源s到其余頂點(diǎn)i(i<>s)的最短路徑dist(i),i屬于V。BEGIN(1)foreachi:1Wi忍ppar-do/*p為進(jìn)程數(shù)*/forj=itonsteppdo/*初始化*/INITIALIZE(J)EndforEndfor(2)enqueues/*s入隊(duì)*/⑶halt<falseforeachi:1Wi忍ppar-dowhilenothaltdoSEARCH(i)endwhileendforENDProcedureSEARCH(i)Beginlockthequeue/*隊(duì)列上鎖*/ifqueueisemptythen/*隊(duì)列空時(shí)，等待進(jìn)程為真*/waiting(i)<trueifi=1then/*進(jìn)程1等待時(shí)，其他進(jìn)程均須等待*/halt<waiting(2)Awaiting(3)八...八waiting(p)endifunlockthequeue/*隊(duì)列開鎖*/elsedequeueu/*從隊(duì)列中刪除u*/waiting(i)6falseunlockthequeue/*隊(duì)列開鎖*/foreveryedge(u,v)ingraphdo/*檢查每條射出邊*/new_dist—dist(u)+w(u,v);lock(dist(v))/*dist(v)上鎖*/ifnew_dist<dist(v)thendist(v)—new_dist/*更新new_dist*/unlock(dist(v))/*dist(v)開鎖*/ifv!Equeuethenlockthequeue/*隊(duì)列上鎖*/enqueuev/*v入隊(duì)*/unlockthequeue/*隊(duì)列開鎖*/endifelseunlock(dist(v))/*dist(v)開鎖*/endifendforendifend值得指出的是：雖然創(chuàng)建更多的進(jìn)程會(huì)縮短各個(gè)算法的執(zhí)行時(shí)間(因?yàn)榭梢酝瑫r(shí)檢查若十個(gè)頂點(diǎn)的射出邊)，但每個(gè)進(jìn)程對(duì)隊(duì)列的插入和刪除要進(jìn)行互斥控制，所以最大加速比最終還是受限制的。3.3、兩種并行算法的性能比較Djkstra算法復(fù)雜性分析：根據(jù)以上步驟可得并行算法使用了p個(gè)處理器，其時(shí)間復(fù)雜度為O(N2/p+nlogp)。這里應(yīng)該注意的是處理器0只進(jìn)行輸入/輸出工作，不參與任何其他的計(jì)算，因此實(shí)際參加運(yùn)算的處理器為p-1個(gè)，所以有n=N/(p-1)。在圖搜索中，若使用Dijkstra算法則要求首先檢查最近的頂點(diǎn)，因而Dijkstra算法在這個(gè)階段中進(jìn)行圖的搜索時(shí)則必須按照順序處理的方式進(jìn)行搜索。這樣Dijkstra算法在圖的搜索階段的并行性能也就大大降低了。這無形中給多處理機(jī)系統(tǒng)的應(yīng)用帶來了極大的負(fù)面影響。這時(shí)在Moore算法中，不必以特定的次序檢查這些邊，所以，多選用Moore算法。4、并行算法實(shí)現(xiàn)4.1、Dijkstra并行算法實(shí)現(xiàn)以下是Dijkstra并行算法的核心代碼：輔助數(shù)據(jù)結(jié)構(gòu)：FILE*fp;/*存儲(chǔ)圖的鄰接矩陣數(shù)據(jù)，第一個(gè)數(shù)值為矩陣的維數(shù)(即圖中點(diǎn)的個(gè)數(shù))，剩余數(shù)據(jù)為按行存儲(chǔ)的邊權(quán)值，且如果兩點(diǎn)之間無邊相連，則權(quán)值由M或者m表示*/Double*W;/*按行存儲(chǔ)的圖的鄰接矩陣*/intS=0;/*源點(diǎn)s的序號(hào)*/輔助函數(shù)原型說明：4.1.1、voidfatal(char*err)函數(shù)功能：打印出錯(cuò)信息，并退出程序；輸入?yún)?shù)：出錯(cuò)信息字符串；輸出參數(shù)：無；函數(shù)返回：無。4.1.2、voidGetChar(char&ch,FILE*fp)函數(shù)功能：從文件fp中讀出一個(gè)字節(jié)數(shù)據(jù)，存入變量ch；輸入?yún)?shù)：文件指針fp；輸出參數(shù)：字符引用&ch；函數(shù)返回：無；附加說明：文件中的合法字符為：數(shù)字、M、m，該函數(shù)要求過濾掉非法字符。4.1.3、doubleGetNextNum()函數(shù)功能：逐個(gè)讀出文件fp中的數(shù)值；輸入?yún)?shù)：無；輸出參數(shù)：無；函數(shù)返回：double型數(shù)值；附加說明：該函數(shù)調(diào)用GetChar()函數(shù)，并用于讀出鄰接矩陣的維數(shù)以及邊權(quán)值。4.1.4、voidReadMatrix()函數(shù)功能：從文件fp讀入鄰接矩陣W并分配存儲(chǔ)空間，從終端讀入源點(diǎn)的序號(hào)S；輸入?yún)?shù)：無；輸出參數(shù)：無；函數(shù)返回：無。核心函數(shù)說明及其實(shí)現(xiàn)：4.1.5、intmain(intargc,char**argv)函數(shù)功能：算法主函數(shù)；輸入?yún)?shù)：intargc,char**argv；輸出參數(shù)：無；函數(shù)返回：int型函數(shù)執(zhí)行結(jié)果；函數(shù)實(shí)現(xiàn)：intmain(intargc,char**argv){intgroup_size=0;/*所有參加運(yùn)算的進(jìn)程個(gè)數(shù)*/intmy_rank=0;/*當(dāng)前正在運(yùn)行的進(jìn)程的標(biāo)識(shí)*/MPI_Statusstatus;inti,j;intep;intmynum;MPI_Init(&argc,&argv);/*MPIbegin*/MPI_Comm_size(MPI_COMM_WORLD,&group_size);MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);/*每個(gè)進(jìn)程分配n=N/p個(gè)節(jié)點(diǎn)進(jìn)行初始化(N為節(jié)點(diǎn)數(shù)，p為計(jì)算進(jìn)程(不包括0號(hào)進(jìn)程)個(gè)數(shù))*//*0號(hào)進(jìn)程讀入鄰接矩陣，并把頂點(diǎn)個(gè)數(shù)和源點(diǎn)標(biāo)識(shí)廣播給其他各個(gè)計(jì)算進(jìn)程*/if(my_rank==0){ReadMatrix();for(i=1;i<group_size;i++){MPI_Send(&nodenum,1,MPI_INT,i,i,

MPI_COMM_WORLD);MPI_Send(&S,1,MPI_INT,i,i,

MPI_COMM_WORLD);}}else{/*非0號(hào)計(jì)算進(jìn)程接收0號(hào)進(jìn)程廣播的頂點(diǎn)個(gè)數(shù)和源點(diǎn)標(biāo)識(shí)*/MPI_Recv(&nodenum,1,MPI_INT,0,my_rank,MPI_COMM_WORLD,&status);MPI_Recv(&S,1,MPI_INT,0,my_rank,MPI_COMM_WORLD,&status);}/*0號(hào)進(jìn)程不參與運(yùn)算，所以計(jì)算的進(jìn)程只group_size-1個(gè)*//*保證epnodenum/(group_size-1)向上取整*/ep=nodenum/(group_size-1);if(ep*group_size-ep<nodenum)ep++;if(ep*my_rank<=nodenum)/*每個(gè)進(jìn)程分到節(jié)點(diǎn)數(shù)ep*/{mynum=ep;}elseif(ep*my_rank<nodenum+ep)/*最后一個(gè)進(jìn)程分配的節(jié)點(diǎn)數(shù)可能小于平均值ep*/{mynum=nodenum-ep*(my_rank-1);}elsemynum=0;if(my_rank==0)mynum=0;/*0號(hào)進(jìn)程不參與計(jì)算*//*初始化各進(jìn)程數(shù)據(jù)*/Init(my_rank,group_size,ep);/*輸出圖的鄰接矩陣*/OutPutMatrix(my_rank,group_size,ep,mynum);/*單源最短路徑主算法*/FindMinWay(my_rank,group_size,ep,mynum);OutPutResult(my_rank,group_size,ep,mynum);MPI_Finalize();free(W);free(dist);free(bdist);return0;}4.1.6、voidInit(intmy_rank,intgroup_size,intep)函數(shù)功能：初始化各個(gè)進(jìn)程數(shù)據(jù)輸入?yún)?shù)：intmy_rank:本進(jìn)程在該通信域中的標(biāo)識(shí)；intgroup_size:該通信域中并行的進(jìn)程個(gè)數(shù)；intep:每個(gè)計(jì)算進(jìn)程處理的平均節(jié)點(diǎn)個(gè)數(shù)。輸出參數(shù)：無函數(shù)返回：無函數(shù)實(shí)現(xiàn)：voidInit(intmy_rank,intgroup_size,intep){inti=0;MPI_Statusstatus;/*0號(hào)進(jìn)程發(fā)送節(jié)點(diǎn)數(shù)據(jù)到其他各個(gè)計(jì)算進(jìn)程，發(fā)送的數(shù)據(jù)為：按行劃分的鄰接矩陣數(shù)值，ep為該計(jì)算進(jìn)程需要處理的節(jié)點(diǎn)個(gè)數(shù)，nodenum為鄰接矩陣的維數(shù)，則發(fā)送給該計(jì)算進(jìn)程的數(shù)值個(gè)數(shù)應(yīng)為ep*nodenum，且該段數(shù)據(jù)的緩存起始地址為&W(ep*(i-1),0)，該消息的標(biāo)識(shí)即為接收進(jìn)程的標(biāo)識(shí)*/if(my_rank==0){for(i=1;i<group_size;i++){MPI_Send(&W(ep*(i-1),0),ep*nodenum,MPI_DOUBLE,i,i,MPI_COMM_WORLD);}}/*計(jì)算進(jìn)程為得到的數(shù)據(jù)進(jìn)行空間分配*/else{/*從源節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的最短路徑*/dist=(double*)malloc(sizeof(double)*ep);/*是否找到了最短路徑*/bdist=(int*)malloc(sizeof(BOOL)*ep);W=(double*)malloc(sizeof(double)*ep*nodenum);if(W==NULL||dist==NULL||bdist==NULL){fatal("Dynamicallocatespaceformatrixfail!");}/*從0號(hào)進(jìn)程接收需要處理的節(jié)點(diǎn)數(shù)據(jù)*/MPI_Recv(W,ep*nodenum,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD,&status);/*輪詢分配到的節(jié)點(diǎn)：如果分配到的節(jié)點(diǎn)i是源節(jié)點(diǎn)S，則初始化dist[i]=0,bdist[i]=TRUE；否則，dist[i]=W(I,S);bdist[i]=FALSE；*/for(i=0;i<ep;i++){if(i+(my_rank-1)*ep==S){dist[i]=0;bdist[i]=TRUE;}else{dist[i]=W(i,S);bdist[i]=FALSE;}}}}4.1.7、voidOutPutMatrix(intmy_rank,intgroup_size,intep,intmynum)函數(shù)功能：輸出鄰接矩陣輸入?yún)?shù)：intmy_rank:本進(jìn)程在該通信域中的標(biāo)識(shí)；intgroup_size:該通信域中并行的進(jìn)程個(gè)數(shù)；intmynum:本進(jìn)程需要處理的節(jié)點(diǎn)個(gè)數(shù)。輸出參數(shù)：無函數(shù)返回：無函數(shù)實(shí)現(xiàn)：鄰接矩陣的輸出格式為：Processor1:XXXXProcessor1:XXXXvoidOutPutMatrix(intmy_rank,intgroup_size,intep,intmynum){inti,j;if(my_rank!=0){for(i=0;i<mynum;i++){printf("Processor%d:\t",my_rank);for(j=0;j<nodenum;j++){if(W(i,j)>1000000)printf("M\t");elseprintf("%d\t",(int)W(i,j));}printf("\n");}4.1.8、voidOutPutResult(intmy_rank,intgroup_size,intep,intmynum)函數(shù)功能：輸出結(jié)果輸入?yún)?shù)：intmy_rank:本進(jìn)程在該通信域中的標(biāo)識(shí)；intgroup_size:該通信域中并行的進(jìn)程個(gè)數(shù)；intmynum:本進(jìn)程需要處理的節(jié)點(diǎn)個(gè)數(shù)。輸出參數(shù)：無函數(shù)返回：無函數(shù)實(shí)現(xiàn)：最短路徑結(jié)果格式如下：nodei:Xnodej:YvoidOutPutResult(intmy_rank,intgroup_size,intep,intmynum){inti,j;if(my_rank!=0){for(i=0;i<mynum;i++){printf("node%d:\t%d\n",(my_rank-1)*ep+i,(int)dist[i]);}}}4.1.9、voidFindMinWay(intmy_rank,intgroup_size,intep,intmynum)函數(shù)功能：算法主循環(huán)輸入?yún)?shù)：intmy_rank:本進(jìn)程在該通信域中的標(biāo)識(shí)；intgroup_size:該通信域中并行的進(jìn)程個(gè)數(shù)；intmynum:本進(jìn)程需要處理的節(jié)點(diǎn)個(gè)數(shù)。輸出參數(shù)：無函數(shù)返回：無函數(shù)實(shí)現(xiàn)：voidFindMinWay(intmy_rank,intgroup_size,intep,intmynum){inti,j;intindex,index2;doublenum,num2;intcalnum;MPI_Statusstatus;intp=group_size;for(i=0;i<nodenum;i++){index=0;num=M;/*每個(gè)進(jìn)程計(jì)算局部最短路徑*/for(j=0;j<mynum;j++){if(dist[j]<num&&bdist[j]==FALSE){num=dist[j];index=ep*(my_rank-1)+j;/*j在圖中的序號(hào)*/}}MPI_Barrier(MPI_COMM_WORLD);/*同步路障*/calnum=group_size-1;/*while循環(huán)對(duì)各個(gè)計(jì)算進(jìn)程局部最小值進(jìn)行規(guī)約*/while(calnum>1){/**節(jié)點(diǎn)數(shù)目為偶數(shù)時(shí)**/if(calnum%2==0){calnum=calnum/2;/*后p/2個(gè)進(jìn)程將自己的局部最小值發(fā)到對(duì)應(yīng)的前p/2個(gè)進(jìn)程*/if(my_rank>calnum){MPI_Send(&index,1,MPI_INT,my_rank-calnum,my_rank-calnum,MPI_COMM_WORLD);MPI_Send(&num,1,MPI_DOUBLE,my_rank-calnum,my_rank-calnum,MPI_COMM_WORLD);}/*前p/2個(gè)進(jìn)程接收后p/2個(gè)進(jìn)程發(fā)過來的局部最小值，并比較得到更優(yōu)的最小值*/elseif(my_rank!=0){MPI_Recv(&index2,1,MPI_INT,my_rank+calnum,my_rank,MPI_COMM_WORLD,&status);MPI_Recv(&num2,1,MPI_DOUBLE,my_rank+calnum,my_rank,MPI_COMM_WORLD,&status);if(num2<num){num=num2;index=index2;}}}/*節(jié)點(diǎn)數(shù)目為奇數(shù)時(shí)，同理*/else{calnum=(calnum+1)/2;if(my_rank>calnum){MPI_Send(&index,1,MPI_INT,my_rank-calnum,my_rank-calnum,MPI_COMM_WORLD);MPI_Send(&num,1,MPI_DOUBLE,my_rank-calnum,my_rank-calnum,MPI_COMM_WORLD);}elseif(my_rank!=0&&my_rank<calnum){MPI_Recv(&index2,1,MPI_INT,my_rank+calnum,my_rank,MPI_COMM_WORLD,&status);MPI_Recv(&num2,1,MPI_DOUBLE,my_rank+calnum,my_rank,MPI_COMM_WORLD,&status);if(num2<num){num=num2;index=index2;}}}/*while一次循環(huán)之后都要進(jìn)行同步*/MPI_Barrier(MPI_COMM_WORLD);}/*廣播最小值*/MPI_Bcast(&index,1,MPI_INT,1,MPI_COMM_WORLD);MPI_Bcast(&num,1,MPI_DOUBLE,1,MPI_COMM_WORLD);/*各個(gè)進(jìn)程根據(jù)廣播的當(dāng)前最小值num,index更新自己的局部值*/for(j=0;j<mynum;j++){if((bdist[j]==FALSE)&&(num+W(j,index)<dist[j]))dist[j]=num+W(j,index);}/*各個(gè)進(jìn)程更新自己的bdist[]數(shù)組*/if(my_rank==index/ep+1){bdist[index%ep]=TRUE;}/*一次for循環(huán)同步一次*/MPI_Barrier(MPI_COMM_WORLD);}}4.2、并行算法的運(yùn)行結(jié)果實(shí)驗(yàn)平臺(tái)：[mapple@Sunny~]$uname-anLinuxSunny?85.fcl3.i686.PAE#1SMPThuMay618:27:11UTC2010i686i686i386GNU/Linux[mapplc@5unny~]$df文件系藐IK-塊已用可用已用％掛載點(diǎn)/dev/mapper/vg_sunny-lv_root2509323235874362023112416%/tmpfs103032006410294561%/dev/shm/dev/sda8495344277424425026*/boot/dev/sda6[mappletasunnv30724280■148387721588556849%/media/DATA以下CPU信息截圖不全，但是從中可以看出2個(gè)cpu：

vendor_idGenuinelnteLcpufamily6model15modelnameIntel(R)Core(TM)2DuoCPUT5550(31.83GHzstepping13cpuMHz1000.000cachesize2048KBphysicalidBsiblings2coreid1cpucores2apicid1initialapicid1fdiv_bugnohitbugnofeefbugnocomabugnofpuyesfpu_exceptionyescpuidlevel10wpyesflag