并行计算流水线计算.ppt

《并行计算流水线计算.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、a4a3a2…a4a3a2a1a1…a4a3a2…a4a3第五章流水线计算PipelinedComputations流水线计算是通过将任务按功能划分成若干个级(pipelinestage)或子任务，每个级可以同时执行，且一级的输出是下一级的输入。流水线计算是串行程序设计的基础。每个子任务由不同的处理部件执行。P0P1P2P3P4…a4…例1：将数组a的所有元素累加到sum中的顺序算法for(i=0;i

2、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(processnum>0){recv(sum,Pi-1);sum=sum+number;}if(processnum

3、um,Pi+1);流水线技术在以下三种计算中将会得到很好的并行效益：如果对同一个问题有多个实例需要执行；如果有一系列数据项要处理，而每个数据项需要多次操作；如果进程在完成自己的全部操作之前能够提供下一个进程启动所需的信息。第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…P0P1P2P3P4

4、P5时间p-1m假设每个流水线级均用一个流水线周期，对有p级流水线和m个问题实例而言，算法的执行时间：=m+p-1个流水线周期第2种情况：每个数据项需要多次操作d0d1d0d1d0d2d1d0d2d3d4d3d1d0d2d0d5d4d2d1d3d1d0d2d7d6d4d3d5d1d0d2d3d8d7d5d4d6d4d3d1d0d2d9d8d6d5d7d1d0d6d5d3d2d4d2d1d3d4d9d8d6d5d7d3d2d4d9d8d6d5d7d4d3d9d8d6d5d7d4d9d8d6d5d7d9

5、d8d6d5d7TimeP9P8P7P6P5P4P3P2P1P0p-1m…输入序列d9d8d7d6d5d4d3d2d1d0P1P2P3P4P5P6P7P8P9P0第3种情况：在进程执行结束之前传递信息给流水线中的下一个进程，使其能够开始工作。启动下一个进程必须的信息传输当任务分解的级的数量比流水线中处理机的数量多时，每个处理机就分到一组流水线级。P0P1P2P3P4P5P6P7P8Processor0Processor1Processor2流水线应用的计算平台流水线操作的方式决定了它最适合于线性网络

6、结构，即相邻的处理机之间有直接通信链路。很容易得到结论：线性网络可以膨胀系数1（完美嵌入）的形式嵌入到2维网格和超立方体中。主机Processors多处理机系统因为工作站群机系统NOWs中处理器间的物理连接通常是星形的，所以它不适于流水计算。各种类型的流水线的应用实例矩阵向量相乘数列排序生成质数回代法求解上三角线性方程组1、矩阵向量相乘已知：一个m*n矩阵A和一个n元向量X，求Rmx1=Amxn•Xnx1a11a12a13……a1n-1a1na21a22a23……a2n-1a2nA=a31a32a3

7、3……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;e

8、lse{//process>0recv(b,Pi-1);b=b+aj*x;}if(process