并行計(jì)算流水線計(jì)算

,單擊此處編輯母版標(biāo)題樣式,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,a4,a3,a2,a4,a3,a2,a1,a1,a4,a3,a2,a4,a3,第五章 流水線計(jì)算,Pipelined Computations,流水線計(jì)算是通過將任務(wù)按功能劃分成若干個級,(pipeline stage),或子任務(wù)，每個級可以同時執(zhí)行，且一級的輸出是下一級的輸入。,流水線計(jì)算是串行程序設(shè)計(jì)的基礎(chǔ)。,每個子任務(wù)由不同的處理部件執(zhí)行。,P,0,P,1,P,2,P,3,P,4,a4,例,1,：將數(shù)組,a,的所有元素累加到,sum,中的順序算法,for(i=0;i 0),recv(sum,P,i-1,);,sum=sum+number;,if (processnum 0,recv(b,P,i-1,);,b=b+a,j,*x;,if (process n,，每個實(shí)例的平均計(jì)算時間（,R,的,1,個分量）：,t,average,=t,total,/m,2(1+t,startup,+,t,data,),如果任務(wù)分解的級的數(shù)量比流水線中處理機(jī)的數(shù)量多時，每個處理機(jī)就分到一組流水線級。,另外，我們往往希望任務(wù)的最終結(jié)果在流水線結(jié)構(gòu)中的第一個節(jié)點(diǎn)上，則需要處理機(jī)的通信結(jié)構(gòu)應(yīng)是環(huán)狀網(wǎng)絡(luò)。,假設(shè),r=n/p,為一整數(shù)（,n,為矩陣的列數(shù)）,P,i,P,2,P,p,P,1,我們把,A,按列分為,p,個,m*r,的小矩陣,A,1,A,2,A,p,把,X,按行分為,p,個,r*1,的小向量,X,1,X,2,X,p,計(jì)算,A*X,就轉(zhuǎn)化為計(jì)算：,A,1,X,1,+A,2,X,2,+A,p,X,p,處理器,P,i,（其中,1,i,p,）將,A,i,和,X,i,存放在自己的局部存儲器中，各處理器首先計(jì)算,A,i,X,i,，然后利用通信（流水線方式）實(shí)現(xiàn)數(shù)據(jù)求和。,X,1,(r*1),X,2,(r*1),X,p,(r*1),A=A,1,A,2,A,p,X=,(m*r)(m*r)(m*r),算法,2,：帶有流水線處理方式的矩陣向量相乘算法,輸入：處理器數(shù),p,，,/SPMD,第,i,個,A,矩陣分量,A,i,于,B,中，,第,i,個,X,向量分量,X,i,于,w,中,;,輸出：,A*X,于,P,1,變量,R,m,x,1,中。,compute z=Bw;,/z,有,m,個分量,if (i=1),R=0;,/R,有,m,個分量,else,receive(R,left);,R=R+z;,send(R,right);,if (i=1),receive(R,left);,p1,p3,p2,p4,計(jì)算,z=Bw,計(jì)算,z=Bw,計(jì)算,z=Bw,計(jì)算,z=Bw,R=0,rec(R,p1),rec(R,p2),rec(R,p3),R=R+z,send(R,p2),send(R,p3),send(R,p4),rec(R,p4),send(R,p1),R=R+z,R(1),R=R+z,R(2),R=R+z,R(3),R(4),結(jié)束,算法,2,的執(zhí)行時間分析：,t,total,=,一個流水線周期時間*任務(wù)所用的周期數(shù),+,非流水線計(jì)算時間,=(t,comp,+t,comm,)*p+,非流水線計(jì)算時間,非流水線計(jì)算時間：,m(2 r)=2m(n/p)=2mn/p,t,comp,=m,/R=R+z,表示,m,個分量相加,t,comm,=2(t,startup,+m,t,data,),/,接收和發(fā)送,m,個分量,所以整個算法,2,的執(zhí)行時間為：,=(m+2(t,startup,+m,t,data,)*p+2 m n/p,該算法中，每個實(shí)例的平均計(jì)算時間（,R,的,1,個分量）：,t,average,=t,total,/m,=,(1+2(t,startup,/m+,t,data,)*p+2n/p,算法,1,和算法,2,的執(zhí)行時間的比較,算法,1,中,m n,，每個實(shí)例的平均計(jì)算時間（,R,的,1,個分量）：,t,average,=t,total,/m,2,+,2(t,startup,+,t,data,),算法,2,中，每個實(shí)例的平均計(jì)算時間（,R,的,1,個分量）：,t,average,=t,total,/m,=,p+2n/p,+,2p*(t,startup,/m+,t,data,),一般情況下，算法,1,的平均時間,算法,2,的平均時間,2,、數(shù)列排序,任務(wù)：將一個數(shù)列從大到小（或從小到大）排列。,排序方法：,流水線上的第一個進(jìn)程每次接收一個準(zhǔn)備排序數(shù)列中的數(shù)；,如果剛剛接收的數(shù)比自己目前擁有的數(shù)大，則保存新的數(shù)據(jù)，并將原有的較小的數(shù)據(jù)發(fā)送給下一個進(jìn)程；否則將剛剛接收（較?。┑臄?shù)據(jù)發(fā)送給下一個進(jìn)程。,隨后的各個進(jìn)程也同樣從上一級接收新的數(shù)據(jù)，保留其中較大的數(shù)據(jù)，同時發(fā)送較小的數(shù)據(jù)。,直到所有數(shù)據(jù)均被處理完。,流水線排序方法的機(jī)器結(jié)構(gòu),:,可將結(jié)果返回給主進(jìn)程的雙向流水線機(jī)器結(jié)構(gòu),:,未排序,的數(shù)列,P,0,P,1,P,p-1,主進(jìn)程,從進(jìn)程,未排序,的數(shù)列,P,0,P,1,P,p-1,主進(jìn)程,從進(jìn)程,已排序,的數(shù)列,算法,3,：進(jìn)程,P,i,的排序算法,right_procnum=n-i-1;,/n,為進(jìn)程總數(shù),recv(x,P,i-1,);,for (j=0;j x),send(x,P,i+1,);,x=number;,else,send(number,P,i+1,);,排序算法的執(zhí)行過程,P,0,P,1,P,2,P,3,P,4,流水線時間,將要被排序的數(shù)列：,5,2,1,3,4,1,5,4,2,3,5,4,1,3,2,5,4,2,3,1,5,5,3,1,2,4,5,4,2,3,1,5,2,2,5,1,1,5,2,3,3,1,5,2,4,最壞情況下的排序算法的執(zhí)行過程,P,0,P,1,P,2,P,3,P,4,流水線時間,將要被排序的數(shù)列：,1,2,3,4,5,1,5,4,2,3,5,4,1,3,2,5,4,2,3,1,1,5,3,1,2,4,5,4,2,3,1,1,2,1,2,3,2,3,1,4,3,1,4,2,5,顯然這種排序算法屬于流水線計(jì)算中的第二種類型，即同樣的數(shù)據(jù)被不同的進(jìn)程多次操作。,算法,3,的執(zhí)行時間分析：,如果有,n,個數(shù)要排序，同時有,n,個流水線進(jìn)程，那么該并行算法的實(shí)現(xiàn)需要：,對第一個進(jìn)程來說，需要,n,個流水線周期得到全部的,n,個數(shù)；,隨后的進(jìn)程則需要,n-1,個流水線周期來進(jìn)行接收、比較和發(fā)送操作。,所以整個算法的時間復(fù)雜性為：,n+n-1=2n 1,個流水線周期,當(dāng)然，我們還可以將排序后的數(shù)據(jù)傳給主進(jìn)程。離主進(jìn)程越近的從進(jìn)程傳送結(jié)果的通信時間越少，反之，通信時間越多。,算法,3,：進(jìn)程,P,i,的排序算法（排序結(jié)果傳給主進(jìn)程）,right_procnum=n-i-1;,recv(x,P,i-1,);,for (j=0;j x),send(x,P,i+1,);,x=number;,else send(number,P,i+1,);,send(x,P,i-1,);,for (j=0;j right_procnum;j+),recv(number,P,i+1,);,send(number,P,i-1,);,3,、生成質(zhì)數(shù),問題：對給定的正整數(shù),n,，求出,2,到,n,內(nèi)所有的質(zhì)數(shù)。,篩法求質(zhì)數(shù)方法：,對數(shù)列,(2.n),從小到大逐個掃描，找到當(dāng)前最小的質(zhì)數(shù)，然后篩去數(shù)列中所有為該質(zhì)數(shù)的倍數(shù)的數(shù)；,重復(fù)尋找下一個大于當(dāng)前質(zhì)數(shù)的最小質(zhì)數(shù)作為當(dāng)前質(zhì)數(shù)，并篩去數(shù)列中為當(dāng)前質(zhì)數(shù)的倍數(shù)的所有的數(shù)；,直到找到大于,sqrt(n),的當(dāng)前質(zhì)數(shù)為止。,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,29,23,19,17,13,11,7,5,3,2,最終結(jié)果,篩法求質(zhì)數(shù)串行算法,for(i=2;i=n;i+)do primei=1;,/,初始化,NextPrime=2;,while NextPrime=sqrt(n),for(i=NextPrime;i=n div NextPrime),primei*NextPrime=0;,/,篩掉當(dāng)前質(zhì)數(shù)的倍數(shù),repeat,/,找下一個新質(zhì)數(shù),NextPrime=NextPrime+1;,until primeNextPrime,for(i=2;i sqrt(n),為止。,假設(shè)每一次,標(biāo)記質(zhì)數(shù)的倍數(shù),花費(fèi)一個單位時間,串行算法的執(zhí)行時間：,假設(shè)有,k,個,Sqrt(,N),的質(zhì)數(shù),:,1,2,k,T,s,=,N,-,1,2,+1,1,N,-,2,2,+1,2,N,-,k,2,+1,k,+,+,=,N,+1,-,1,2,1,N,+1,-,2,2,2,N,+1,-,k,2,k,+,+,=,N,-,3,2,N,-8,3,N,+1,-,k,2,k,+,+,當(dāng),N,=1000,時,串行算法的時間為,1411(,單位時間,),。,并行算法的執(zhí)行時間（不考慮通信的情況）：,假設(shè)有,k,個,Sqrt(,N),的質(zhì)數(shù),:,1,2,k,0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500,2,3,5,7,11,13,17-31,2,7,17,3,5,11,13,3,11,2,5,7,13,加速比,=1411/7062,并行效率,2/2 1,加速比,=1411/4992.83,并行效率,2.83/3 0.94,當(dāng)處理器的個數(shù)為,4,時，加速比,=1411/499 2.83,利用流水線方法解決生成質(zhì)數(shù)問題,具體方法：,首先將整個數(shù)列輸入到流水線的第一個進(jìn)程中，該進(jìn)程篩去數(shù)列中,2,的倍數(shù)，隨后將未被篩去的剩余數(shù)列和下一個質(zhì)數(shù)發(fā)送給第二個進(jìn)程；,隨后的各個進(jìn)程首先從上一個進(jìn)程接收剩余的數(shù)列和新質(zhì)數(shù)，隨后篩去數(shù)列中新質(zhì)數(shù)的倍數(shù)，將未被篩去的剩余數(shù)列和下一個質(zhì)數(shù)發(fā)送給下一個進(jìn)程。,這種處理方法要求進(jìn)程的個數(shù)必須等于,sqrt(n),之內(nèi)的質(zhì)數(shù)的個數(shù)。,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,P,0,篩去,2,的倍數(shù),篩去,3,的倍數(shù),P,1,篩去,5,的倍數(shù),P,2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,7,11,13,17,19,23,29,5,7,11,13,17,19,23,25,29,并行算法：,recv(x,P,i-1,);,/,得到下一個質(zhì)數(shù),recv(number,P,i-1,);,/,從上一個進(jìn)程接收一個數(shù),if (number%x)!=0),send(number,P,i+1,);,因?yàn)槊總€進(jìn)程需要從上一個進(jìn)程接收的數(shù)列元素個數(shù)不確定，故我們引入一個數(shù)列結(jié)束標(biāo)志,terminator,。,recv(x,P,i-1,);,/,得到下一個質(zhì)數(shù),for (i=0;i n;i+),recv(number,P,i-1,);,if (number=terminator)break;,if (number%x)!=0)send(number,P,i+1,);,表示傳送下一個質(zhì)數(shù),表示數(shù)列結(jié)束標(biāo)志,表示純計(jì)算時間（被傳送來的數(shù)據(jù)量）,進(jìn) 程,P,1,P,2,P,0,P,3,P,4,時間,4,、回代法求解上三角線性方程組,a,n-1,0,x,0,