并行计算流水线计算

a4a3a2…a4a3a2a1a1…a4a3a2…a4a3第五章流水线计算PipelinedComputations流水线计算是通过将任务按功能划分成若干个级(pipelinestage)或子任务，每个级可以同时执行，且一级的输出是下一级的输入。流水线计算是串行程序设计的基础。每个子任务由不同的处理部件执行。P0P1P2P3P4…a4…例1：将数组a的所有元素累加到sum中的顺序算法for(i=0;in;i++)sum=sum+a[i];aSinSoutaSinSouta[1]aSinSouta[2]aSinSouta[3]a[0]sum每个处理机（流水线中的中间级）需要执行相同的操作：recv(sum,Pi-1);sum=sum+a;send(sum,Pi+1);aSinSoutaSinSouta[1]aSinSouta[2]aSinSouta[3]a[0]sum这个过程写为SPMD程序：假设第i个处理机将数组的第i个元素存入局部变量number。if(processnum0){recv(sum,Pi-1);sum=sum+number;}if(processnumn-1)send(sum,Pi+1);流水线技术在以下三种计算中将会得到很好的并行效益：1.如果对同一个问题有多个实例需要执行；2.如果有一系列数据项要处理，而每个数据项需要多次操作；3.如果进程在完成自己的全部操作之前能够提供下一个进程启动所需的信息。第1种情况：同一个问题有多个实例需要执行实例1实例1实例1实例1实例1实例1实例2实例2实例2实例2实例2实例2实例3实例3实例3实例3实例3实例3实例4实例4实例4实例4实例4实例4实例5实例5实例5实例5实例5…实例6实例6实例6实例6…实例7实例7实例7…P0P1P2P3P4P5时间p-1m假设每个流水线级均用一个流水线周期，对有p级流水线和m个问题实例而言，算法的执行时间：=m+p-1个流水线周期第2种情况：每个数据项需要多次操作d0d1d0d1d0d2d1d0d2d3d4d3d1d0d2d0d5d4d2d1d3d1d0d2d7d6d4d3d5d1d0d2d3d8d7d5d4d6d4d3d1d0d2d9d8d6d5d7d1d0d6d5d3d2d4d2d1d3d4d9d8d6d5d7d3d2d4d9d8d6d5d7d4d3d9d8d6d5d7d4d9d8d6d5d7d9d8d6d5d7TimeP9P8P7P6P5P4P3P2P1P0p-1m…输入序列d9d8d7d6d5d4d3d2d1d0P1P2P3P4P5P6P7P8P9P0第3种情况：在进程执行结束之前传递信息给流水线中的下一个进程，使其能够开始工作。启动下一个进程必须的信息传输当任务分解的级的数量比流水线中处理机的数量多时，每个处理机就分到一组流水线级。P0P1P2P3P4P5P6P7P8Processor0Processor1Processor2流水线应用的计算平台流水线操作的方式决定了它最适合于线性网络结构，即相邻的处理机之间有直接通信链路。很容易得到结论：线性网络可以膨胀系数1（完美嵌入）的形式嵌入到2维网格和超立方体中。主机Processors多处理机系统因为工作站群机系统NOWs中处理器间的物理连接通常是星形的，所以它不适于流水计算。各种类型的流水线的应用实例1.矩阵向量相乘2.数列排序3.生成质数4.回代法求解上三角线性方程组1、矩阵向量相乘已知：一个m*n矩阵A和一个n元向量X，求Rmx1=Amxn•Xnx1a11a12a13……a1n-1a1na21a22a23……a2n-1a2nA=a31a32a33……a3n-1a3n……..am1am2am3……amn-1amnx1x2X=x3…xn假设流水线系统拥有n个处理机；第i个处理机的局部存储器中应存有A矩阵的第i列数据a1,a2,…,am，以及X的第i个分量xi。算法1：在流水线机器结构上的矩阵向量相乘算法(SPMD)输入：处理器数n（1~n），A矩阵第i列存于Pi的局部数组变量[a1,a2,…,am]中，X向量第i个分量xi存于Pi的局部变量x中;输出：A*X存于Pn变量R中。forj=1tomdo{if(process==1)b=aj*x;else{//process0recv(b,Pi-1);b=b+aj*x;}if(processn)send(b,Pi+1);elseR[j]=b;}矩阵向量相乘执行过程：1k1a1kxk1k2a1kxk1k1a2kxk1k3a1kxk1k2a2kxk1k1a3kxk1k4a1kxk1k3a2kxk1k2a3kxk1k1a4kxkR[1]1k5a1kxk1k4a2kxk1k3a3kxk1k2a4kxk1k1a5kxkP5P4P3P2P1时间1k5a3kxk1k4a4kxk1k3a5kxkR[3]1k5a2kxk1k4a3kxk1k3a4kxk1k2a5kxkR[2]该算法的执行结果是从最后一个进程得到的。第一种类型的流水线处理仅对问题拥有多个实例的情况非常有效，且当实例的个数越多，并行效率越高。即：流水线的启动和结束时间相对并行计算阶段的时间可以忽略不计，从而提高了整个并行任务的并行效率。对矩阵向量乘法问题而言，我们很容易将任务分为均匀的级来处理。假设各个进程在每个流水线周期内执行的操作近似，那么算法执行的总时间为ttotal：一个流水线周期时间*任务所用的周期数ttotal=(tcomp+tcomm)*(m+p-1)其中m为问题的实例数，p为进程数(流水线的级数)。一个实例的平均执行时间：taverage=ttotal/m算法1的执行时间估计：tcomp=2//一次乘法和一次加法tcomm=2(tstartup+tdata)n=p所以整个算法1的执行时间为：(tcomp+tcomm)*(m+p-1)=2(1+tstartup+tdata)*(m+n-1)该算法中mn，每个实例的平均计算时间（R的1个分量）：taverage=ttotal/m2(1+tstartup+tdata)如果任务分解的级的数量比流水线中处理机的数量多时，每个处理机就分到一组流水线级。另外，我们往往希望任务的最终结果在流水线结构中的第一个节点上，则需要处理机的通信结构应是环状网络。假设r=n/p为一整数（n为矩阵的列数）PiP2PpP1我们把A按列分为p个m*r的小矩阵A1,A2,…,Ap把X按行分为p个r*1的小向量X1,X2,…,Xp计算A*X就转化为计算：A1X1+A2X2+…ApXp处理器Pi（其中1ip）将Ai和Xi存放在自己的局部存储器中，各处理器首先计算AiXi，然后利用通信（流水线方式）实现数据求和。X1(r*1)X2(r*1)…Xp(r*1)A=A1A2…ApX=(m*r)(m*r)(m*r)算法2：带有流水线处理方式的矩阵向量相乘算法输入：处理器数p，//SPMD第i个A矩阵分量Ai于B中，第i个X向量分量Xi于w中;输出：A*X于P1变量Rmx1中。computez=Bw;//z有m个分量if(i==1)R=0;//R有m个分量elsereceive(R,left);R=R+z;send(R,right);if(i==1)receive(R,left);p1p3p2p4计算z=Bw计算z=Bw计算z=Bw计算z=BwR=0rec(R,p1)rec(R,p2)rec(R,p3)R=R+zsend(R,p2)send(R,p3)send(R,p4)rec(R,p4)send(R,p1)R=R+zR(1)R=R+zR(2)R=R+zR(3)R(4)结束算法2的执行时间分析：ttotal=一个流水线周期时间*任务所用的周期数+非流水线计算时间=(tcomp+tcomm)*p+非流水线计算时间非流水线计算时间：m(2r)=2m(n/p)=2mn/ptcomp=m//R=R+z表示m个分量相加tcomm=2(tstartup+mtdata)//接收和发送m个分量所以整个算法2的执行时间为：=(m+2(tstartup+mtdata))*p+2mn/p该算法中，每个实例的平均计算时间（R的1个分量）：taverage=ttotal/m=(1+2(tstartup/m+tdata))*p+2n/p算法1和算法2的执行时间的比较算法1中mn，每个实例的平均计算时间（R的1个分量）：taverage=ttotal/m2+2(tstartup+tdata)算法2中，每个实例的平均计算时间（R的1个分量）：taverage=ttotal/m=p+2n/p+2p*(tstartup/m+tdata)一般情况下，算法1的平均时间算法2的平均时间2、数列排序任务：将一个数列从大到小（或从小到大）排列。排序方法：流水线上的第一个进程每次接收一个准备排序数列中的数；如果刚刚接收的数比自己目前拥有的数大，则保存新的数据，并将原有的较小的数据发送给下一个进程；否则将刚刚接收（较小）的数据发送给下一个进程。随后的各个进程也同样从上一级接收新的数据，保留其中较大的数据，同时发送较小的数据。直到所有数据均被处理完。流水线排序方法的机器结构:可将结果返回给主进程的双向流水线机器结构:未排序的数列P0P1Pp-1主进程从进程未排序的数列P0P1Pp-1主进程从进程已排序的数列算法3：进程Pi的排序算法right_procnum=n-i-1;//n为进程总数recv(x,Pi-1);for(j=0;jright_procnum;j++){recv(number,Pi-1);if(numberx){send(x,Pi+1);x=number;}elsesend(number,Pi+1);}排序算法的执行过程P0P1P2P3P4流水线时间将要被排序的数列：5,2,1,3,41542354132542315531245423152251152331524最坏情况下的排序算法的执行过程P0P1P2P3P4流水线时间将要被排序的数列：1,2,3,4,51542354132542311531245423112123231431425显然这种排序算法属于流水线计算中的第二种类型，即同样的数据被不同的进程多次操作。算法3的执行时间分析：如果有n个数要排序，同时有n个流水线进程，那么该并行算法的实现需要：对第一个进程来说，需要n个流水线周期得到全部的n个数；随后的进程则需要n-1个流水线周期来进行接收、比较和发送操作。所以整个算法的时间复杂性为：n+n-1=2n–1个流水线周期当然，我们还可以将排序后的数据传给主进程。离主进程越近的从进程传送结果的通信时间越少，反之，通信时间越多。算法3’：进程Pi的排序算法（排序结果传给主进程）right_procnum=n-i-1;recv(x,Pi-1);for(j=0;jright_procnum;j++){recv(number,Pi-1);if(numberx)send(x,Pi+1);x=number;}elsesend(number,Pi+1);}send(x,Pi-1);for(j=0;jright_procnum;j++){recv(number,Pi+1);send(number,Pi-1);}3、生成质数问题：对给定的正整数n，求出2到n内所有的质数。筛法求质数方法：对数列(2..n)从小到大逐个扫描，找到当前最小的质数，然后筛去数列中所有为该质数的倍数的数；重复寻找下一个大于当前质数的最小质数作为当前质数，并筛去数列中为当前质数的倍数的所有的数；直到找到大于sqrt(n)的当前质数为止。234567891011121314151617181920212223242526272829302345678910111213141516171819202122232425262728