单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,a4,a3,a2,a4,a3,a2,a1,a1,a4,a3,a2,a4,a3,第五章 流水线计算,Pipelined Computations,流水线计算是通过将任务按功能划分成若干个级,(pipeline stage),或子任务，每个级可以同时执行，且一级的输出是下一级的输入流水线计算是串行程序设计的基础每个子任务由不同的处理部件执行P,0,P,1,P,2,P,3,P,4,a4,例,1,：将数组,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,，每个实例的平均计算时间（,R,的,1,个分量）：,t,average,=t,total,/m,2(1+t,startup,+,t,data,),如果任务分解的级的数量比流水线中处理机的数量多时，每个处理机就分到一组流水线级另外，我们往往希望任务的最终结果在流水线结构中的第一个节点上，则需要处理机的通信结构应是环状网络。
假设,r=n/p,为一整数（,n,为矩阵的列数）,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,计算,A*X,就转化为计算：,A,1,X,1,+A,2,X,2,+A,p,X,p,处理器,P,i,（其中,1,i,p,）将,A,i,和,X,i,存放在自己的局部存储器中，各处理器首先计算,A,i,X,i,，然后利用通信（流水线方式）实现数据求和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,：带有流水线处理方式的矩阵向量相乘算法,输入：处理器数,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,计算,z=Bw,计算,z=Bw,计算,z=Bw,计算,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),结束,算法,2,的执行时间分析：,t,total,=,一个流水线周期时间*任务所用的周期数,+,非流水线计算时间,=(t,comp,+t,comm,)*p+,非流水线计算时间,非流水线计算时间：,m(2 r)=2m(n/p)=2mn/p,t,comp,=m,/R=R+z,表示,m,个分量相加,t,comm,=2(t,startup,+m,t,data,),/,接收和发送,m,个分量,所以整个算法,2,的执行时间为：,=(m+2(t,startup,+m,t,data,)*p+2 m n/p,该算法中，每个实例的平均计算时间（,R,的,1,个分量）：,t,average,=t,total,/m,=,(1+2(t,startup,/m+,t,data,)*p+2n/p,算法,1,和算法,2,的执行时间的比较,算法,1,中,m n,，每个实例的平均计算时间（,R,的,1,个分量）：,t,average,=t,total,/m,2,+,2(t,startup,+,t,data,),算法,2,中，每个实例的平均计算时间（,R,的,1,个分量）：,t,average,=t,total,/m,=,p+2n/p,+,2p*(t,startup,/m+,t,data,),一般情况下，算法,1,的平均时间,算法,2,的平均时间,2,、数列排序,任务：将一个数列从大到小（或从小到大）排列。
排序方法：,流水线上的第一个进程每次接收一个准备排序数列中的数；,如果刚刚接收的数比自己目前拥有的数大，则保存新的数据，并将原有的较小的数据发送给下一个进程；否则将刚刚接收（较小）的数据发送给下一个进程随后的各个进程也同样从上一级接收新的数据，保留其中较大的数据，同时发送较小的数据直到所有数据均被处理完流水线排序方法的机器结构,:,可将结果返回给主进程的双向流水线机器结构,:,未排序,的数列,P,0,P,1,P,p-1,主进程,从进程,未排序,的数列,P,0,P,1,P,p-1,主进程,从进程,已排序,的数列,算法,3,：进程,P,i,的排序算法,right_procnum=n-i-1;,/n,为进程总数,recv(x,P,i-1,);,for (j=0;j x),send(x,P,i+1,);,x=number;,else,send(number,P,i+1,);,排序算法的执行过程,P,0,P,1,P,2,P,3,P,4,流水线时间,将要被排序的数列：,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,最坏情况下的排序算法的执行过程,P,0,P,1,P,2,P,3,P,4,流水线时间,将要被排序的数列：,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,显然这种排序算法属于流水线计算中的第二种类型，即同样的数据被不同的进程多次操作。
算法,3,的执行时间分析：,如果有,n,个数要排序，同时有,n,个流水线进程，那么该并行算法的实现需要：,对第一个进程来说，需要,n,个流水线周期得到全部的,n,个数；,随后的进程则需要,n-1,个流水线周期来进行接收、比较和发送操作所以整个算法的时间复杂性为：,n+n-1=2n 1,个流水线周期,当然，我们还可以将排序后的数据传给主进程离主进程越近的从进程传送结果的通信时间越少，反之，通信时间越多算法,3,：进程,P,i,的排序算法（排序结果传给主进程）,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,、生成质数,问题：对给定的正整数,n,，求出,2,到,n,内所有的质数筛法求质数方法：,对数列,(2.n),从小到大逐个扫描，找到当前最小的质数，然后筛去数列中所有为该质数的倍数的数；,重复寻找下一个大于当前质数的最小质数作为当前质数，并筛去数列中为当前质数的倍数的所有的数；,直到找到大于,sqrt(n),的当前质数为止。
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,最终结果,筛法求质数串行算法,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;,/,筛掉当前质数的倍数,repeat,/,找下一个新质数,NextPrime=NextPrime+1;,until primeNextPrime,for(i=2;i sqrt(n),为止。
假设每一次,标记质数的倍数,花费一个单位时间,串行算法的执行时间：,假设有,k,个,Sqrt(,N),的质数,:,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,+,+,当,N,=1000,时,串行算法的时间为,1411(,单位时间,),并行算法的执行时间（不考虑通信的情况）：,假设有,k,个,Sqrt(,N),的质数,:,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,当处理器的个数为,4,时，加速比,=1411/499 2.83,利用流水线方法解决生成质数问题,具体方法：,首先将整个数列输入到流水线的第一个进程中，该进程筛去数列中,2,的倍数，随后将未被筛去的剩余数列和下一个质数发送给第二个进程；,随后的各个进程首先从上一个进程接收剩余的数列和新质数，随后筛去数列中新质数的倍数，将未被筛去的剩余数列和下一个质数发送给下一个进程。
这种处理方法要求进程的个数必须等于,sqrt(n),之内的质数的个数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,的倍数,筛去,3,的倍数,P,1,筛去,5,的倍数,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,);,/,得到下一个质数,recv(number,P,i-1,);,/,从上一个进程接收一个数,if (number%x)!=0),send(number,P,i+1,);,因为每个进程需要从上一个进程接收的数列元素个数不确定，故我们引入一个数列结束标志,terminator,recv(x,P,i-1,);,/,得到下一个质数,for (i=0;i n;i+),recv(number,P,i-1,);,if (number=terminator)break;,if (number%x)!=0)send(number,P,i+1,);,表示传送下一个质数,表示数列结束标志,表示纯计算时间（被传送来的数据量）,进 程,P,1,P,2,P,0,P,3,P,4,时间,4,、回代法求解上三角线性方程组,a,n-1,0,x,0,。
